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

Question

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

我想绘制三角形中的每个像素（*），仅一次，并以伪随机顺序进行，而无需存储先前命中点的列表。

我知道如何在0和x之间的线段上执行此操作

沿着线条选择一个随机点'o'，
选择与x相对质数的'p'
重复最多x次：O_next = (O_cur + P) MOD x

要对三角形执行此操作，我将需要
1. 不包括列表计算三角形中像素的数量
2. 将0..points的整数映射到三角形内部的有效像素的x,y对

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

（*）我使用CG术语像素表示满足方程的整数点对X,Y。

- Procedural Throwback

Answer 1

由于您想要保证每个像素只被访问一次，因此最好考虑像素而不是实际的三角形。您可以将三角形水平切割并获得一堆水平扫描线。将扫描线连接在一起，就将您的“三角形”转换成了一条长线。将您的点访问算法应用于扫描线的长链。

顺便说一句，这种映射只需要在纸上发生，您只需要一个函数，可以在虚拟扫描线上给出（t）返回（x，y）。

编辑： 要将两个点转换为线段，可以查找布雷森汉姆扫描转换。一旦您将3条线段转换为一系列点，就可以将所有点放入桶中，并按y分组所有点。在相同的y值内，按x对点进行排序。在y值内最小的x是扫描线的起始点，在y值内最大的x是扫描线的终点。这称为“扫描转换三角形”。如果您搜索，可以找到更多信息。

- eed3si9n

---

这似乎需要一个扫描线列表，并确定给定数字表示哪一行需要遍历结构（平衡树？）尝试泛化这个过程似乎很快失控了。 - Procedural Throwback

它只需要映射到正确的(x, y)集合，因此在函数内部，它可以使用Windows程序员的方法从边界矩形中选择点，并在不在三角形中时返回“false”。 - Eugene Yokota

从您的方程中选择三个点（x1，y1），（x2，y2），（x3，y3）。 （Min（x），Min（y）），（Max（x），Max（y））定义了您的边界框。宽度为Max（x）- Min（x），因此这是扫描线的长度。扫描线数为Max（y）- Min（y）。 x = t％width + Min（x），y = t / width + Min（y）。 - Eugene Yokota

workmad3 - 我尝试解决这样的方程，但是我数学比较生疏，无法弄清楚。我甚至不能可靠地计算出一个三角形中的“像素”数量，而不是迭代线条（随着维度增加变得非常复杂）。 - Procedural Throwback

我也无法在不迭代线条的情况下计算三角形中的像素数量。这就是为什么我发布了我的丑陋的hack。 - Windows programmer

Answer 2

这是Triangle Point Picking的解决方案。

你需要选择三角形的两个向量（边），将它们分别乘以0到1之间的随机数，然后将它们加起来。这样可以在由这两个向量定义的四边形内提供均匀分布。你需要检查结果是否位于原始三角形内；如果不是，则将其转换回去或直接丢弃并重试。

- efotinis

---

分布在浮点空间中，但它是否仍适用于整数像素？我无法看出这如何用于获得完整的覆盖范围... 只能说可能可以获得完整的覆盖范围？ - Procedural Throwback

你说得对。我写完后意识到那不是你所要求的。我本来想删除我的回答，但也许其他人会发现它有用。:0) - efotinis

Answer 3

一种方法是将所有像素放入一个数组中，然后对数组进行洗牌（复杂度为O(n)），然后按照洗牌后的顺序访问像素。但这可能需要相当多的内存空间。

- 1800 INFORMATION

Answer 4

这里有一个方法，它会浪费一些 CPU 时间，但可能不会像更复杂的方法那样浪费那么多。

计算一个包围三角形的矩形。很容易将该矩形“线性化”，每个扫描线跟随下一个。使用您已经知道的算法来遍历矩形的像素。当您遇到每个像素时，请检查该像素是否在三角形内，如果不是，则跳过它。

- Windows programmer

Answer 5

我会将三角形的边看作单条线段，然后将其切割成若干小段并存储在一个数组中。每个小段的长度和在总线段长度中的偏移量也会被存储下来。根据O的值，你可以选择包含所需像素的数组元素，并根据该元素中的值绘制像素。

- sveinna