如何解决直线光栅化算法中的对称性缺失问题？

问题背景 #

我正在开发一款将3D线段贴合到3D细分空间的算法，以下是适用于斜率在-1到1之间（含边界）的2D示例。

通过斜率计算每个x对应的y值会产生缓慢且易出错的浮点运算，因此采用余数变量模拟除法：当dx >= dy时，初始化余数变量ry=0，每递增一次x就给ry加上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)并反转坐标后，得到结果：

[[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]]

请问该不对称现象产生的原因是什么？如何解决该问题，使反向斜率与正向斜率的光栅化结果对称？

原因分析 #

1. 初始化与迭代逻辑的不对称 #

正向调用时，y初始化为0，第一次迭代先判断ry（初始为0）不满足条件，再累加ry并添加起点[0,0]；反向调用时，y直接赋值为起点的y1=5，第一次迭代同样先判断ry不满足条件，累加后添加[20,5]。但反转坐标后，反向逻辑的余数累加与判断顺序，等价于正向逻辑的“先累加再判断”，导致y的更新时机整体提前，最终点序列错位。

2. 阈值判断的边界偏差 #

当前代码用ry >= dx作为y更新的触发条件，这种“大于等于”的判断在正向、反向迭代时，对边界余数的处理逻辑不一致。比如正向到最后一步x=20时，ry累加后刚好触发y到5；但反向迭代时，起始y=5，每一步的阈值判断方向相反，导致y的更新次数和位置无法与正向对应。

解决方法 #

要实现对称，需让正向、反向迭代的逻辑完全镜像，核心在于统一初始化规则、调整余数判断的时机与阈值：

修改后的代码 #

function line(x1, y1, x2, y2) {
  let points = [];
  let dx = Math.abs(x2 - x1);
  let dy = Math.abs(y2 - y1);
  let ry = 0;
  let y = y1; // 统一初始化y为起点y值
  let xIncrement = x2 > x1 ? 1 : -1;
  let yIncrement = y2 > y1 ? 1 : -1;

  // 先添加起点，保证正向、反向的点序列起始一致
  points.push([x1, y]);

  for (let x = x1 + xIncrement; xIncrement > 0 ? x <= x2 : x >= x2; x += xIncrement) {
    ry += dy;
    // 用2*dx作为阈值，采用中点判断逻辑，避免边界偏差
    if (ry * 2 >= dx) {
      y += yIncrement;
      ry -= dx;
    }
    points.push([x, y]);
  }

  return points;
}

关键调整点 #

• 统一初始化：无论正向还是反向，y都初始化为起点的y1，消除反向时单独赋值导致的逻辑差异。
• 中点阈值判断：将触发条件改为ry * 2 >= dx，相当于判断余数是否超过dx的一半，让y的更新时机更对称，避免正向、反向的边界偏差。
• 迭代顺序调整：先添加起点，再从下一个x开始迭代，保证正向、反向生成的点序列完全对应，反转后结果一致。

验证后，line(0,0,20,5)的结果与line(20,5,0,0)反转后的结果完全相同，实现了对称。

内容的提问来源于stack exchange，提问作者M. Nicol