线光栅化：覆盖所有像素，无论线条渐变？
基本上，我想使用行算法来确定哪些单元格可以检查我的raycaster的碰撞。
Bresenham并不是很好，因为它使用统一厚度的方法，这意味着它忽略了至少半覆盖线的细胞。 根本不是很好，因为这意味着我的线路的某些部分没有被检查与单元格的交叉点，导致错误。
我似乎无法找到任何“粗线”算法，任何人都可以帮我找到一个？
格林：我想要什么。
红色：我目前拥有和不想要的东西。
这个线程很老，但我认为将它放在互联网上是值得的：
// This prints the pixels from (x, y), increasing by dx and dy. // Based on the DDA algorithm (uses floating point calculations). void pixelsAfter(int x, int y, int dx, int dy) { // Do not count pixels |dx|==|dy| diagonals twice: int steps = Math.abs(dx) == Math.abs(dy) ? Math.abs(dx) : Math.abs(dx) + Math.abs(dy); double xPos = x; double yPos = y; double incX = (dx + 0.0d) / steps; double incY = (dy + 0.0d) / steps; System.out.println(String.format("The pixels after (%d,%d) are:", x, y)); for(int k = 0; k < steps; k++) { xPos += incX; yPos += incY; System.out.println(String.format("A pixel (%d) after is (%d, %d)", k + 1, (int)Math.floor(xPos), (int)Math.floor(yPos))); } }
不失一般性，假设x2> = x1，那么
int x = floor(x1); int y = floor(y1); double slope = (x2 - x1) / (y2 - y1); if (y2 >= y1) { while (y < y2) { int r = floor(slope * (y - y1) + x1); do { usepixel(x, y); ++x; } while (x < r); usepixel(x, y); ++y; } } else { while (y > y2) { int r = floor(slope * (y - y1) + x1); do { usepixel(x, y); ++x; } while (x < r); usepixel(x, y); --y; } }
楼层调用可能只是作为一个整数来编写。
GPU Gems中有一篇有趣的文章，也许它可以帮到你： 第22章快速预滤波线
Bresenham还有一个额外的约束条件，即不允许对角线移动：使用传统算法生成点，然后作为后处理步骤插入仅进行正交移动所需的额外步骤。
您可以找到光线与水平网格线相交的所有交叉点，然后标记一行上具有交叉点的行上的所有单元格，或者在行上具有交叉点的两个单元格之间。
找到交叉点可以通过从原点开始，将点前进到第一个交点（并在过程中标记单元格），找出从交叉点到下一个交点的向量（这两个操作都是基本相似的三角形） （或触发））然后逐列前进，直到你走得足够远。 逐列前进涉及每列一个向量加法，以及一个小循环以填充具有交叉点的单元格之间的单元格。 如果您正在处理单元格，请将“mark”替换为“process” – 此算法保证仅标记每个单元格一次。
垂直线也可以这样做，但网格通常存储在水平切片中，所以我选择了它。 如果您正在使用trig，则需要使用特殊情况处理直线水平线。
顺便说一句，据我所知，这是基于网格的raycaster“3D”游戏（如Wolfenstein 3D）的完成程度。 我在很久以前就从这本书中读到了这个算法。