假设我们有3个点,分别是A, B, C,如何在这3个点构成的三角形内随机取点呢?下面我们来看看一些常用的实现方式以及他们的优缺点
1. 在AB上随机抽取一个点,命名为D,然后再在CD上随机抽取一个点
不过这样的算法得出来的点是非均匀分布的,越接近C点的分布就越密集,并不能算真正的“随机”
2. 通过使用Trilinear 坐标来随机取点,不过这个方法得到的结果也是非均匀分布的,越中间越密集
3. 用两个同样形状的三角形拼接成一个四边形,然后在四边形内随机取点并通过投射的方法投影到我们之前的三角形内,这个方法倒是能做到均匀分布,不过过程还是略消耗性能
4. 通过算法
P = (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + sqrt(r1) * r2 * C,
A, B, C分别是三角形的三个顶点,r1, r2 是两个[0, 1]的随机数
大家对这个算法的由来感兴趣的话可以去看看Princeton大学发布的报告:
http://www.cs.princeton.edu/~funk/tog02.pdf
通过算法得出的随机取点相比于前3种算法来说更容易实现,并且这个算法得出的点是均匀分布的。