CODEWITHSUNDEEP
algorithm
astrofrog
astrofrog

Reputation: 34091

Generating points uniformly on a sphere

I'm interested in generating points that are 'uniformly' (and non-randomly) distributed around a sphere, much like the dimples of a golf ball or the vertices of the hexagons on a soccer ball. Are there well defined algorithms to do this?

Note: I know that the points are not really 'uniformly' distributed on a sphere, but they are distributed in a way that the distribution of points looks the same from any direction that looks straight at any of the points - this is what I am interested in.

Upvotes: 3

Views: 5392

Answers (7)

kuroi neko
kuroi neko

Reputation: 8661

I tried once the following algorithm:

  • start with a regular tetrahedron with the submits on the sphere.
  • pick one of the triangles with the biggest surface (initially it will be any of the 4 sides)
  • replace selected face with a 3 sided pyramid where the 4th point is the elevation of the face center to the sphere surface.
  • repeat until enough points have been created.

This works as long as precision does not ruin uniformity. The resulting points form figures akin to a geode.

You don't need to compute any surface, since each new triangle is no greater than all previous ones. Simply handle them in FIFO order.

Upvotes: 0

orion elenzil
orion elenzil

Reputation: 5433

if you're okay with having only certain allowable numbers of vertices, then the subdivision methods above are definitely the way to go. if you want an arbitrarily-specified number of vertices, then i recommend:

first, distribute points randomly and uniformly over the sphere. i talk at length about doing this at http://elenzil.com/progs/randompoints . i believe my method is at least as performant as that at worlfram.

second, "relax" the distribution by treating the points as a particle system where each particle repels every other particle. the difficulty here is making sure the system doesn't become unstable, and deciding when to stop. i have an example of this here: http://elenzil.com/progs/separate unfortunately these were the days before i included source code with my projects, so that code is lost.

Upvotes: 0

Anton Sherwood
Anton Sherwood

Reputation: 11

Choose u,v randomly from [0,1]. 2πu is longitude. asin(2v-1) is latitude. Only two random variables, and no rejections.

By the way, my link collection has a new address: http://bendwavy.org/sphere.htm

And I've copied it over to http://cgafaq.info/wiki/Evenly_distributed_points_on_sphere

Upvotes: 1

jonderry
jonderry

Reputation: 23633

Here's a simple way to do it.

  1. Randomly, sample from the unit cube, [0, 1]^3

  2. Test for inclusion in the sphere. Reject if the sampled point is not in the sphere of diameter 1 that is contained in the unit cube, and go to step 1.

  3. Normalize the point to be on the surface of the sphere, by projecting the point outward from the center of the sphere.

This will typically succeed after a few samples. If you want, you can also reject samples that are near the center of the sphere to minimize rounding errors and help make the distribution closer to uniform.

Upvotes: 1

Mads Elvheim
Mads Elvheim

Reputation:

Subdividing an octahedron and normalizing the vertices afterwards gives very good results. Look here for more details. Paul Bourke has a lot of interesting stuff.

Here's some psuedo C++ code I wrote up in five minutes now:

/* 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;
}

This code will work with any polyhedron made of counter-clockwise triangles, but octahedrons are best.

Upvotes: 1

fringd
fringd

Reputation: 2528

depending on your needs http://iquilezles.untergrund.net/www/articles/patchedsphere/patchedsphere.htm may work well too. not exactly uniform, but very fast to compute.

Upvotes: 0

Jim Brissom
Jim Brissom

Reputation: 32919

While this article talks about randomly picking points on a sphere, it is also about drawing points from a uniform distribution while at the same time taking the sphere characteristic into consideration. I guess it's still a decent read for your question:

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

Upvotes: 0

Related Questions