javascript 如何解决这种线光栅化算法中缺乏对称性的问题？

c0vxltue 于 2022-12-25 发布在 Java

关注(0)|答案(1)|浏览(113)

我正在研究一个算法，以捕捉三维线到三维镶嵌空间。
以下是适用于介于-1和1（含）之间的正斜率和负斜率的算法的二维示例。
使用斜率来计算y在每个x处的值会导致浮点计算缓慢且容易出错。解决方案是使用余数变量来模拟除法。
当dx >= dy时，从初始余数变量ry = 0开始，然后，对于每个x增量，将dy添加到ry变量，当它超过dx时，增加y，然后设置ry等于ry - dx。

function line(x1, y1, x2, y2) {
  let points = []
  let dx = Math.abs(x2 - x1);
  let dy = Math.abs(y2 - y1);
  // The remainder variable for y axes. 
  // No rx is created because we are assuming dx >= dy.
  let ry = 0;
  // Current value of y for a given point
  let y = 0;

  // The slope could be positive or negative, so increments coordinates as they go down or up.
  let pointIncrement;
  if (x2 > x1) {
    pointIncrement = 1;
  } else if (x2 < x1) {
    pointIncrement = -1;
    y = y1
  }
  for (let x = x1; pointIncrement < 0 ? x >= x2 : x <= x2; x += pointIncrement) {
    if (ry >= dx) {
      ry -= dx;
      y += pointIncrement;
    }
    // Add dy to ry until it surpasses dx. This simulates the division of dy/dx for slope.
    ry += dy;
    points.push([x, y])
  }
  return points
}

现在，如果调用斜率为1/4的函数：

line(0,0,20,5)

您将得到以下结果：

[[0,0],[1,0],[2,0],[3,0],[4,1],[5,1],[6,1],[7,1],[8,2],[9,2],[10,2],[11,2],[12,3],[13,3],[14,3],[15,3],[16,4],[17,4],[18,4],[19,4],[20,5]]

现在，如果你再次调用它，但方向是负的，那么就颠倒坐标顺序：

line(20,5,0,0).reverse()

您将得到以下结果：

[[0,0],[1,1],[2,1],[3,1],[4,1],[5,2],[6,2],[7,2],[8,2],[9,3],[10,3],[11,3],[12,3],[13,4],[14,4],[15,4],[16,4],[17,5],[18,5],[19,5],[20,5]]

为什么会发生这种情况？
有没有人知道这个问题的解决方法，使负斜率与正斜率对称？

JavaScript

来源：https://stackoverflow.com/questions/74891827/how-to-solve-the-lack-of-symmetry-in-this-line-rasterization-algorithm

1条答案

按热度按时间

gg58donl1#

在向上的方向上，您将计算y = y1 + floor((x-x1) * dy / dx)。在向下的方向上，您将计算y = y1 + ceil((x-x1) * dy / dx)
在这两种情况下，这会产生“不平衡”线，其中dy/dx点具有y == y1，但只有一个点具有y == y2。
你要计算的是y = y1 + round((x-x1) * dy / dx)，这将使线的两端平衡，如果你想让向上和向下的方向完全对称，那么你需要注意确保0.5在两种情况下都是在同一个方向上舍入的。
在这种实现中，完成舍入的一种方法是使用偏移量。如果A和B是整数，并且B是正的，那么round(A/B) == floor((A+floor(B/2))/B)。这个floor(B/2)偏移量可以在开始时加到余数上。
注意确保0.5始终取整，只需将ry的初始值更改为：

let ry = y2 >= y1 ? Math.floor(dx/2) : Math.floor((dx-1)/2);

不过，您的代码中还有一些其他的bug，如果我将它们全部修复，结果如下所示：

function line(x1, y1, x2, y2) {
  let points = []
  // increment direction for x axis
  const incX = x2 >= x1 ? 1 : -1;
  // increment direction for y axis
  const incY = y2 >= y1 ? 1 : -1;
  // absolute span in x and y
  const dx = (x2 - x1) * incX;
  const dy = (y2 - y1) * incY;

  // The remainder variable for y axes. 
  let ry = y2 >= y1 ? Math.floor(dx/2) : Math.floor((dx-1)/2);
  // Current value of y for a given point
  let y = y1;
  
  for (let x = x1; incX < 0 ? x >= x2 : x <= x2; x += incX) {
    if (ry >= dx) {
      ry -= dx;
      y += incY;
    }
    // Add dy to ry until it surpasses dx. This simulates the division of dy/dx for slope.
    ry += dy;
    points.push([x, y])
  }
  return points
}

赞(0）回复(0）举报 2022-12-25

我来回答

javascript 如何解决这种线光栅化算法中缺乏对称性的问题？

1条答案

相关问题

热门标签

最新问答