旋转矩形光栅化算法

Question

简而言之:我想做Bresenham线算法的非近似版本,但是对于矩形而不是线,并且其点不一定与网格对齐.

给定一个正方形网格和一个包含四个非网格对齐点的矩形,我想找到一个由矩形部分或全部覆盖的所有网格方块的列表.

Bresenham的线算法是近似的 - 并非所有部分覆盖的正方形都被识别出来.我正在寻找一种"完美"算法,它没有误报或否定.

Answer 1

Amanatides 和 Woo 的方法可以枚举所有相交的单元 格射线追踪的快速体素遍历算法。
这里是实际的实现。
作为对你的副作用 - 你会得到与网格线的交点 - 如果你需要部分覆盖单元格的区域（用于抗锯齿等），它可能会很有用。