algorithm - 以随机顺序访问三角形中的点

Question

对于由整数方程 aX + bY <= c 指定的直角三角形

我想以伪随机顺序绘制三角形中的每个像素 (*) 一次且仅一次，并且不存储先前命中点的列表。

我知道如何用 0 和 x 之间的线段来做到这一点

pick a random point'o' along the line,
pick 'p' that is relatively prime to x
repeat for up to x times: O_next = (O_cur + P) MOD x

要为三角形做这个，我会
1.需要统计triangle sans列表中的像素个数
2. 将整数 0..points 映射到 x,y 对中，该对是三角形内的有效像素

我希望任何解决方案都可以推广到金字塔和更高维的形状。

(*) 我将 CG 项像素用于整数点对 X、Y，以满足方程式。

Answer 1

由于您希望保证访问每个像素一次且仅一次，因此考虑像素而不是真正的三角形可能更好。您可以水平切片三角形并获得一堆水平 scan lines .将扫描线连接在一起，您已将“三角形”转换为长线。将您的点访问算法应用于您的长扫描线链。

顺便说一句，这个映射只需要在纸上发生，你所需要的只是一个函数，它可以沿着虚拟扫描线返回给定(t)的(x，y)。

编辑:要将两个点转换为线段，可以查找Bresenham's scan conversion .将 3 条线段转换为一系列点后，您可以将所有点放入桶中并按 y 对所有点进行分组。在相同的 y 值内，按 x 对点进行排序。 y 值中最小的 x 是扫描线的起点，y 值中最大的 x 是扫描线的终点。这称为“扫描转换三角形”。您可以通过 Google 找到更多信息。