在球面上均匀生成点

Question

我希望生成在球体周围“均匀分布”的点（而非随机分布），就像高尔夫球表面的凹点或足球上的六边形。是否有明确定义的算法可以实现这一点？

注意：我知道这些点并不是真正“均匀”地分布在球体上，但它们以某种方式分布，从任何直接注视任何点的方向看去，点的分布看起来是相同的 - 这就是我感兴趣的。

- astrofrog

---

这里是相应的谷歌搜索。第一个结果甚至包含了C++和Java代码实现。 - Sven Marnach

我不知道在任意数量的点上，是否存在均匀分布。高尔夫球上凹痕的数量是固定的（虽然我不记得具体数字），足球上六边形顶点的数量也是如此。 - David Thornley

这个主题的链接收集似乎也很有趣。 - Sven Marnach

@David：只要您可以在集合上定义一些度量，任何任意集合都有均匀分布。@astrofrog：嗯，你为什么说“不是真正均匀分布”？球面上确实存在均匀分布，并且它 是（显然）对称的-您可以从任何方向查看它并获得相同的结果。 - ShreevatsaR

更重要的是，您是否真的想从均匀分布中随机采样点，还是试图生成像高尔夫球凹痕一样的固定（非随机）点阵模式？ - ShreevatsaR

Answer 1

从[0,1]中随机选择u,v。 2πu是经度。 asin(2v-1)是纬度。 只有两个随机变量，没有拒绝。

顺便说一下，我的链接收藏有一个新地址：http://bendwavy.org/sphere.htm。

我已经将其复制到http://cgafaq.info/wiki/Evenly_distributed_points_on_sphere。

- Anton Sherwood

---

cgafaq已经死了。 （我试图划掉那行，但我的编辑被拒绝了。） - Anton Sherwood

Answer 2

将八面体进行细分并在之后对顶点进行归一化可以得到非常好的结果。点击这里了解更多详情。Paul Bourke有很多有趣的内容。

以下是我现在花五分钟写的伪C++代码：

/* Assume 'data' initially holds vertices for eight triangles (an octahedron) */
void GenerateSphere(float radius, std::vector<Vector3f>& data, int accum=10)
{
    assert( !(data.size() % 3) );

    std::vector<Vector3f> newData;

    for(int i=0; i<data.size(); i+=3){
        /* Tesselate each triangle into three new ones */
        Vector3f centerPoint = (data[i] + data[i+1] + data[i+2]) / 3.0f;

        /* triangle 1*/
        newData.push_back(data[i+0]);
        newData.push_back(data[i+1]);
        newData.push_back(centerPoint);
        /* triangle 2*/
        newData.push_back(data[i+1]);
        newData.push_back(data[i+2]);
        newData.push_back(centerPoint);
        /* triangle 3*/
        newData.push_back(centerPoint);
        newData.push_back(data[i+2]);
        newData.push_back(data[i+0]);
    }
    data = newData;
    if(!accum){
        /* We're done. Normalize the vertices,
             multiply by the radius and return. */
        for(int i=0; i<data.size(); ++i){
            data[i].normalize();
            data[i] *= radius;
        }
    } else {
        /* Decrease recursion counter and iterate again */
        GenerateSphere(radius, data, accum-1);
    }
    return;
}

这段代码适用于由逆时针三角形构成的任何多面体，但八面体最好。

- Mads Elvheim

Answer 3

如果您只需要特定数量的顶点，则上述细分方法绝对是正确的选择。如果您需要任意指定数量的顶点，则我建议：

首先，在球体上随机均匀地分布点。我在http://elenzil.com/progs/randompoints中详细讨论了如何做到这一点。我相信我的方法至少与worlfram的方法一样有效。

其次，通过将点视为粒子系统来“放松”分布，其中每个粒子都会排斥其他粒子。困难在于确保系统不变得不稳定，并决定何时停止。我在这里有一个示例：http://elenzil.com/progs/separate不幸的是，这些都是在我没有将源代码包含在我的项目中的日子里完成的，因此那段代码已经丢失了。

- orion elenzil

Answer 4

我曾尝试过以下算法：

• 从一个正四面体开始，将其顶点放在球体上。
• 选择表面积最大的三角形之一（最初可以是任意一个面）。
• 用一个三角锥替换所选面，其中第四个点是面心到球面的高度。
• 重复以上步骤，直到创建足够的点。

只要精度不破坏均匀性，这种方法就有效。生成的点形成类似于晶洞的图形。

您无需计算任何表面，因为每个新的三角形都不会比之前的任何一个更大。只需按FIFO顺序处理它们即可。

- kuroi neko

Answer 5

虽然本文讨论了在球体上随机选择点，但它也涉及到从均匀分布中绘制点，同时考虑球体的特性。我想这仍然是一个不错的阅读材料，适合您的问题：

http://mathworld.wolfram.com/SpherePointPicking.html

- Jim Brissom

Answer 6

根据您的需求，http://iquilezles.untergrund.net/www/articles/patchedsphere/patchedsphere.htm 也可能很好用。 不是完全均匀，但计算非常快速。

- fringd

Answer 7

这里有一个简单的方法。

1. 从单位立方体[0,1]^3中随机采样。

2. 测试是否包含在直径为1的球内。如果采样点不在包含在单位立方体中的直径为1的球内，则拒绝并返回步骤1。

3. 通过将点从球心向外投影，将其归一化到球面上。

通常几次采样后就能成功。如果需要，您还可以拒绝接近球心的样本，以最小化舍入误差，并帮助使分布更接近均匀分布。

- jonderry