交互式详解：DDA Algorithm

The DDA Algorithm, explained interactively

Source | HN Comments

这篇文章通过交互式演示，深入浅出地解释了 DDA 算法在 2D 空间中的工作原理，主要用于光线投射。文章从基础的射线原点和方向入手，逐步推导出算法的核心逻辑：通过计算射线与网格线的交点距离，判断下一个网格空间。文章详细讲解了如何计算距离，并最终给出了完整的 DDA 算法实现代码，以及一些优化技巧，帮助读者理解和掌握该算法。

这是一篇关于 aaaa.sh 的博客文章

交互式详解：DDA Algorithm

我编写过很多体素光线追踪器，它们（至少是好的那些）都使用 Digital Differential Analyzer Algorithm 进行光线投射。我只 "实现" 过一次这个算法，通过从某个地方复制一段代码。从那以后，我就一直使用和重复使用那段代码。但我必须承认：我从来没有真正理解它是如何工作的。我看过它解释得很好，解释得很差，在视频中解释，但我仍然不明白。至少对我来说，它是那种很难理解的几何算法之一。但最近，我在一个光线追踪器中遇到了一些问题，我决定尝试完全理解它。我写了这篇博客文章，为了像我一样的人。

本文中的所有代码都是可编辑的。示例将在您修改它们时更新。

在 2D 空间中，DDA 是一种迭代射线相交的所有网格正方形的算法。对于那些没有见过该算法的人来说，它看起来像这样：

ro.x
ro.y
rdAngle

let rd = { x: cos(rdAngle), y: sin(rdAngle) }
drawPoint(ro, colRed)
drawVector(ro, mul(rd, 10))
let step = sign(rd)
let mapCheck = floor(ro)
let rayUnitStepSize = { 
  x: sqrt(1 + (rd.y / rd.x) * (rd.y / rd.x)), 
  y: sqrt(1 + (rd.x / rd.y) * (rd.x / rd.y)),
}
let rayLength = { x: 0, y: 0 }
let roFract = sub(ro, mapCheck)
if (rd.x < 0) {
  rayLength.x = roFract.x * rayUnitStepSize.x
} else {
  rayLength.x = (1 - roFract.x) * rayUnitStepSize.x
}
if (rd.y < 0) {
  rayLength.y = roFract.y * rayUnitStepSize.y
} else {
  rayLength.y = (1 - roFract.y) * rayUnitStepSize.y
}
for (let i = 0; i < 50; i++) {
  drawGridSpace(mapCheck)
  if (rayLength.x < rayLength.y) {
    mapCheck.x += step.x
    rayLength.x += rayUnitStepSize.x
  } else {
    mapCheck.y += step.y
    rayLength.y += rayUnitStepSize.y
  }
}

[查看所有代码]

如果您理解了以上内容，祝您愉快 :) 如果没有，本文会提供解释。

3Blue1Brown 告诉我们，解释某件事的好方法是从头开始推导它。那么你如何推导出这个划线算法？首先，我们有我们的参数：Ray Origin ro 和 Ray Direction rd。 RD 必须归一化。在本文中，我们使用一个角度来计算它，如下所示：

let rd = { x: cos(rdAngle), y: sin(rdAngle) }

让我们在网格上绘制它们。

ro.x
ro.y
rdAngle

drawPoint(ro)
drawVector(ro, mul(rd, 2))

[查看所有代码]

我们需要填充的第一个网格空间非常简单——它是 ro 所在的网格空间。我们可以对 ro 进行 floor 操作以获得精确的整数空间。

ro.x
ro.y
rdAngle

let gridSpace = floor(ro)
drawGridSpace(gridSpace)

[查看所有代码]

不是很令人兴奋，但这是一个重要的步骤。

现在，我们必须弄清楚_下一个_网格空间是什么。看看你是否能猜到答案：移动上面的点和箭头，猜猜下一个网格空间会在哪里。

乍一看，您可能会认为它与 rdAngle 有关，例如，如果角度朝上，那么应该填充点上方的网格空间，如果角度朝右，则应该填充右侧的网格空间，依此类推。

ro.x
ro.y
rdAngle

if   (rdAngle > Math.PI * 1.75) gridSpace.x += 1
else if (rdAngle > Math.PI * 1.25) gridSpace.y -= 1
else if (rdAngle > Math.PI * 0.75) gridSpace.x -= 1
else if (rdAngle > Math.PI * 0.25) gridSpace.y += 1
else                gridSpace.x += 1
drawGridSpace(gridSpace)

[查看所有代码]

但是如果你摆弄一下射线原点，你会发现这很快就会崩溃。

我们需要考虑从原点到不同网格正方形的距离。如果您最近花了一些时间在几何或绘图计算器上，您可能已经弄清楚这实际上是一个 线相交 问题。如果您重置上面的程序，您可以看到 ro->rd 向量与线 x = 1 和 y = 1 相交。（在本文中，我们假设网格的中心是原点。）让我们把这些交点放在屏幕上：

ro.x
ro.y
rdAngle

// 这些值在其他地方计算。
// 我们稍后会讨论如何计算它们。
drawPoint(xIntersection, colBlue)
drawPoint(yIntersection, colYellow)

[查看所有代码]

黄点是 ro->rd 和 y = 1 之间的交点，绿点是 ro->rd 和 x = 1 之间的交点。

现在，让我们将 ro 和黄点之间的_距离_称为 lengthY。

let lengthY = dist(ro, yIntersection)

类似地，我们可以将 ro 和绿点之间的距离称为 lengthX。

let lengthX = dist(ro, xIntersection)

现在看到当 lengthX 小于 lengthY 时，光线投射线在与 y = 1 相交_之前_与 x = 1 相交，所以下一个网格空间是右边的那个。类似地，当 lengthY 小于 lengthX 时，光线投射线在与 x = 1 相交之前与 y = 1 相交，所以下一个网格空间是上面的那个。

ro.x
ro.y
rdAngle

// 我们可以绘制到这些点的箭头来可视化
// 长度的差异
drawVector(ro, mul(rd, lengthX), colGreen)
drawVector(ro, mul(rd, lengthY), colYellow)
// 这是关键的观察！！！
if (lengthX < lengthY) {
  gridSpace.x += 1
} else {
  gridSpace.y += 1
}
drawGridSpace(gridSpace)

[查看所有代码]

太棒了！我们迈出了第一步。在我们移动到三个正方形之前（你能想象吗？！），让我们谈谈那个相交代码。

重要的是，我们实际上不需要计算交点。我们只需要 lengthX 和 lengthY，它们都是距离。对于这些，我们可以查阅毕达哥拉斯。如果我们把上面的黄线想象成直角三角形的对角线，我们可以用它的腿来计算它的长度，如下图所示，用粉色和蓝色绘制。

另请注意，为了简单起见，我们将使用 ro = {0,0} 一段时间 :')

let ro = {x: 0, y: 0}

// 只是一个视觉效果 :)
drawPoint({x: 0.0, y: 0.0})
drawArrow({x: 0.0, y: 0.0}, {x: 0.88, y: 1}, colYellow)
drawArrow({x: 0.0, y: 0.0}, {x: 0.0, y: 1}, colPink)
drawArrow({x: 0.0, y: 1}, {x: 0.88, y: 1}, colGreen)

[查看所有代码]

粉色线的长度恰好是 1。

let pinkLineDist = 1

我们可以用一些基本的代数来计算蓝线的颜色。我们想找到黄线（以 Slope-intercept form mx+b 呈现）与 y = 1 相交的点。

mx+b=1rdyrdxx+b=1rdyrdxx=1x=rdxrdy\begin{align} mx + b &= 1\\ {\frac{rd_y}{rd_x}}x + b &= 1\\ {\frac{rd_y}{rd_x}}x &= 1\\ x &= \frac{rd_x}{rd_y} \end{align} mx+brdxrdyx+brdxrdyxx=1=1=1=rdyrdx

let blueLineDist = rd.x / rd.y

rdAngle (RO 暂时停留在 {0,0}。)

drawVector(ro, {x: 0, y: pinkLineDist}, colPink)
drawVector({x: 0, y: pinkLineDist}, {x: blueLineDist, y: 0}, colGreen)

[查看所有代码]

使用勾股定理，我们可以计算线的长度。

dist=pinkDist2+blueDist2dist=12+rdxrdy2dist=1+rdxrdy2\begin{align*} \text{dist} &= \sqrt{\text{pinkDist}^2 + \text{blueDist}^2}\\ \text{dist} &= \sqrt{1^2 + {\frac{rd_x}{rd_y}}^2}\\ \text{dist} &= \sqrt{1 + {\frac{rd_x}{rd_y}}^2} \end{align*} distdistdist=pinkDist2+blueDist2=12+rdyrdx2=1+rdyrdx2

let distToY = sqrt(1 + (rd.x / rd.y) * (rd.x / rd.y))

类似地，

let distToX = sqrt(1 + (rd.y / rd.x) * (rd.y / rd.x))

我们可以通过将这些值乘以 rd 并在屏幕上绘制结果向量来验证这些值是否正确：

rdAngle

drawVector(ro, mul(rd, distToY), colYellow)
drawVector(ro, mul(rd, distToX), colGreen)

[查看所有代码]

现在我们所要做的就是使用我们之前使用的比较技巧。

rdAngle

if (distToY < distToX) {
  gridSpace.y += 1
} else {
  gridSpace.x += 1
}
drawGridSpace(gridSpace)

[查看所有代码]

太棒了！现在让我们进入第三个空间。如果我们向右移动，我们想开始测量到_下一条_线 x = 2 的距离。到这条线的距离是到 x = 1 的距离的两倍。另一方面，如果我们向上移动，我们想测量到 y = 2 的距离，这只是到 y = 1 的距离的两倍。让我们尝试根据分支将我们的距离加倍。

rdAngle

if (distToY < distToX) {
  gridSpace.y += 1
  distToY *= 2 // 加倍 se 我们可以查看 y = 2
} else {
  gridSpace.x += 1
  distToX *= 2 // 加倍 se 我们可以查看 x = 2
}
drawGridSpace(gridSpace)
// 这与之前的比较相同，但其中一个值是
// 修改后的，所以我们比较的是到不同对
// 的网格正方形的距离。
if (distToY < distToX) {
  gridSpace.y += 1
} else {
  gridSpace.x += 1
}
drawGridSpace(gridSpace)

[查看所有代码]

在每个步骤中，如果我们向右移动，我们想要增加 distToX，如果我们向上移动，我们想要增加 distToY。我们希望将 yDist 增加 rd 上行之间的距离，将 xDist 增加 rd 上列之间的距离。列之间的距离是从 {0,0} 到 x = 1 的距离，也就是我们之前计算的值。行之间的距离也是如此。

let distBetweenRows  = sqrt(1 + (rd.x / rd.y) * (rd.x / rd.y))
let distBetweenColumns = sqrt(1 + (rd.y / rd.x) * (rd.y / rd.x))

rdAngle

let distToY = distBetweenRows
let distToX = distBetweenColumns
for (let i = 0; i < 10; i++) {
  drawGridSpace(gridSpace)
  if (distToY < distToX) {
    gridSpace.y += 1
    distToY += distBetweenRows
  } else {
    gridSpace.x += 1
    distToX += distBetweenColumns
  }
}

[查看所有代码]

我们仍然必须处理 ro != {0,0} 的情况。初始 distToX 和 distToY 根据 ro 在网格正方形_内部_的位置而变化。让我们称该值为 roFract，因为它表示 ro 的小数部分。

let roFract = sub(ro, gridSpace)

当 y = 0 时，初始 distToY 为 distBetweenColumns，如上所示。当 y = 0.5 时，初始 distToY 为一半的 distBetweenColumns。在一般情况下，要计算初始 distToY，我们只需将 distBetweenColumns 乘以 1 - roFract.y 即可。我们可以对 distToX 做同样的事情。

ro.x (RO 回来了！)
ro.y (比以往任何时候都好)
rdAngle

let distToY = (1 - roFract.y) * distBetweenRows
let distToX = (1 - roFract.x) * distBetweenColumns
for (let i = 0; i < 10; i++) {
  drawGridSpace(gridSpace)
  if (distToY < distToX) {
    gridSpace.y += 1
    distToY += distBetweenRows
  } else {
    gridSpace.x += 1
    distToX += distBetweenColumns
  }
}

[查看所有代码]

我们快完成了——我们只需要确保在 rd.x < 0 或 rd.y < 0 时计算正确的距离。当 rd.x < 0 时，我们测量到 x = 0 而不是 x = 1 的距离，所以 distToX = roFract.x * distBetweenColumns：我们不必从 1 中减去 roFract。类似地，当 rd.y < 0 时，distToY = roFract.y * distBetweenRows。

此外，如果 rd.y < 0，我们需要减少 gridSpace.y，而不是增加 gridSpace.y。我们通过简单地添加 sign(rd.y) 而不是增加常量 1 来概括这两种情况。我们对 rd.x 和 gridSpace.x 做同样的事情。

ro.x
ro.y
rdAngle

let distToY
if (rd.y < 0) {
  distToY = roFract.y * distBetweenRows
} else {
  distToY = (1 - roFract.y) * distBetweenRows
}
let distToX
if (rd.x < 0) {
  distToX = roFract.x * distBetweenColumns
} else {
  distToX = (1 - roFract.x) * distBetweenColumns
}

for (let i = 0; i < 10; i++) {
  drawGridSpace(gridSpace)
  if (distToY < distToX) {
    gridSpace.y += sign(rd.y)
    distToY += distBetweenRows
  } else {
    gridSpace.x += sign(rd.x)
    distToX += distBetweenColumns
  }
}

[查看所有代码]

就是这样！在现实世界中使用了一些修改：

distBetweenRows 和 distBetweenColumns 被组合成一个变量，有时称为 rayUnitStepSize。
sign(rd.x) 和 sign(rd.y) 被组合成一个变量，有时称为 step。
为了避免循环中的比较，您可以使用 boolean vector.

ro.x
ro.y
rdAngle

let rd = { x: cos(rdAngle), y: sin(rdAngle) }
drawPoint(ro, colRed)
drawVector(ro, mul(rd, 10))
let step = sign(rd)
let mapCheck = floor(ro)
let rayUnitStepSize = { 
  x: sqrt(1 + (rd.y / rd.x) * (rd.y / rd.x)), 
  y: sqrt(1 + (rd.x / rd.y) * (rd.x / rd.y)),
}
let rayLength = { x: 0, y: 0 }
let roFract = sub(ro, mapCheck)
if (rd.x < 0) {
  rayLength.x = roFract.x * rayUnitStepSize.x
} else {
  rayLength.x = (1 - roFract.x) * rayUnitStepSize.x
}
if (rd.y < 0) {
  rayLength.y = roFract.y * rayUnitStepSize.y
} else {
  rayLength.y = (1 - roFract.y) * rayUnitStepSize.y
}
for (let i = 0; i < 50; i++){
  drawGridSpace(mapCheck)
  if (rayLength.x < rayLength.y) {
    mapCheck.x += step.x
    rayLength.x += rayUnitStepSize.x
  } else {
    mapCheck.y += step.y
    rayLength.y += rayUnitStepSize.y
  }
}

[查看所有代码]