大多数二维准随机方法设计用于单位平方采样。 但是，三角形在计算机图形学中也非常重要。 因此，我描述了一种简单的直接构建方法，用于均匀覆盖任意形状的三角形的点序列。


图1.一种新的直接方法，用于构造任意形状和大小的三角形中具有低散度的开放（无限）拟随机序列。 该图显示了前150个点在15个随机三角形中的点分布。

简短评论

均匀采样/填充正方形的低差异序列已被积极研究了近一百年。 这些准随机序列中的大多数都可以通过简单的拉伸而扩展为矩形，而不会显着破坏差异。

但是，在这篇文章中，我们将考虑对序列进行有趣且重要的扩展，并将其低发散成任意三角形。

据我了解，很少关注点和三角形均匀分布的点集的构造。 Basu [2014] ， Pillands [2005]和Brandolini [2013]近年来值得注意的著作是有关该主题的主要文章，即使不是仅有的文章。

这些作者通常从非常理论和分析的角度考虑此问题，并且几乎总是针对单个正三角形解决此问题。 与它们相反，我的帖子主要用于开发渲染图形的实用技术。

帖子描述了一种直接构造的简单方法，不需要接受/排除或丢弃或递归； 最重要的是，它可以应用于任意大小和形状的三角形。

该帖子包括四个部分：

1. 平方随机序列
2. 在三角形上覆盖单位正方形。
3. 减少失真
4. 进一步概括

1.点的准随机序列

您可能会认为，将100个点放置在一个正方形中以使相邻点之间的最小距离保持尽可能大会很容易。 但是，如果您需要放置13分怎么办？ 47？ 那2019点呢？！

事实证明，低散度的点序列提供了解决此问题的系统方法。 从简单的Holton序列到更复杂的Sable序列，有许多低散度的准随机序列。 这些序列中的每一个都有其自身的优点和缺点。 例如，霍尔顿序列在将对象放置在一个区域中时更有用，因为它具有优化的局部距离度量，例如最近的邻居。 黑貂序列倾向于形成更多的“拥挤”，但是点的全局分布非常均匀，因此具有出色的正交特性。

我喜欢使用另一个序列，它具有出色的局部和全局属性。 这是顺序 $$$R_2$ 我以前的文章“准随机序列的意外效率”中对此进行了详细介绍。

简而言之，我们定义了一个无限的二维序列 $$$R_2$ 这样

$$

$$\ pmb {t} _n = \左\ {n \ pmb {\ alpha} \右\} \ quad n = 1,2,3，... \ pmb {t} _n = \左\ {n \ pmb {\ alpha} \ right \} \ quad n = 1,2,3，...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = \左（\ frac {1} {g}，\ frac {1} {g ^ 2} \ right），$$

$$

$$\ textrm {和} \; g \ simeq 1.32471795572 \标签{1}$$

阅读有关此特殊含义的更多信息。 $$$g$ ，通常称为“塑性常数”，可以在Wikipedia或Mathworld上阅读。

结果，图2显示了具有低差异的不同序列的比较（以及用于比较的简单均匀随机样本）。 如您所见，此随机样本演示了点的累积。 此外，它包含的区域根本不包含点（“白噪声”），而低散度的准随机序列是一种确定性地构造（无限）点序列的方法，以便在任何阶段，放置的点在整个过程中均匀分布空间。


图2.各种低散度准随机序列的前150个成员的图示。 请注意，与简单的均匀随机分布（左下图）相比，它们在空间中创建的分布点更均匀。

2.在三角形上加一个单位正方形

有三种众所周知的方法可确保从三角形进行均匀的随机采样：

1. 平行四边形法
2. 克莱默的方法和
3. 逆概率分布法。

图3.平行四边形方法

平行四边形方法如下。

对于三角形 $$$\ pmb {ABC}$ 考虑平行四边形 $$$\ pmb {ABCA’}$ 。

对于单位平方的点 $$$（r_1，r_2）$ 设定这样的观点 $$$\ pmb {P}$ 那 $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ 。

该点将始终位于平行四边形内。 但是，如果它出现在另一个三角形中 $$$\ pmb {ABC}}$ 然后我们需要将其翻转回三角形 $$$\ pmb {ABC}$ 。

也就是说，如果 $$$r_1 + r_2 <1$ 然后 $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ 但是如果 $$$r_1 + r_2> 1$ 然后 $$$\ pmb {P} =（1-r_1）\ pmb {AC} +（1-r_2）\ pmb {AB}$ 。

但是，非常重要的一点是要理解，即使这些方法提供了一个三角形的均匀采样，但这并不意味着这样的变换将保持我们的准随机点分布的均匀空间排列（即低散度）。

例如，在平行四边形方法的情况下，反射通常会导致一个点非常接近另一个现有点。 显然，这破坏了低散度结构并显示为变形/条状。

同样，逆概率分布方法将非线性失真应用于点。 在Holton和Sable序列中，这意味着两个点经常将自己推得很近。

图4显示了使用平行四边形方法将区域从单位正方形转换为三角形时，在各种准随机序列中的低差异保持得如何。


图4.三角形中各种准随机序列的变换比较。 上面是Holton序列，中间是黑貂序列，下面是序列 $$$R_2$ 。 可以看出，在霍尔顿序列中发生了明显的点拥挤，在索博尔序列中出现了显着的条带形成。 与他们相比，依次 $$$R_2$ 点的分布非常均匀，几乎没有明显的拥挤或条纹。

在三种不同的三角剖分方法和许多不同的准随机序列中，平行四边形方法应用于该序列方法 $$$R_2$ 是唯一不断产生可保持低方差而不失真的可接受结果的组合。

可以在图5中更详细地检查这种组合的出色结果。


图5.您可以看到转换后的序列 $$$R_2$ 提供了一种非常简单但有效的方式来平均分配许多 $$$N$ 点在三角形中。 它适用于锐角和钝角三角形。 （颜色表示排列方式）。

3.其他方面

失真度

平行四边形方法需要选择三角形的两侧作为基础向量。

如果以随机顺序标记顶点，则点的图案通常类似于图6所示。


图6.通过随机选择顶点顺序获得的点的模式。 请注意，在大多数情况下，失真显而易见。

但是，事实证明，通过仔细选择顶点的顺序，可以显着减少失真。 最值得注意的是，如果您标记三角形，以便 $$是最大角度（即，最大的一面是靠着它） $$$\ pmb {AB}$ 和 $$$\ pmb {AC}$ 用作平行四边形的两侧。

如果接受此顺序，我们将得到上面图1、4和5中所示的点的模式。

但是，即使具有一定的顶点顺序，在某些情况下，扭曲效果仍然很明显。 当三角形中的一个角度很小时，它们最为明显。 在钝角三角形的情况下，当最小角度小于30度时，会出现一些变形；在锐角三角形的情况下，当最小角度小于20度时，可以看到变形。 （如果采样的三角形是Delaunay网格的一部分，则这种变形问题可以最小化，因为Delaunay三角剖分是专门设计用于最小化小角度三角形的数量。）

其他形状

不幸的是，平行四边形技术不能用于其他形状，因为它使用了三角形对称性。 对于某些数字，使用逆概率分布方法可以获得良好的结果。 下面是一个示例如何序列 $$$R_2R_2$ 散度低时，您可以转换为以高斯曲线为边界的区域，同时保持点之间的均匀距离。