Algorithm for a geodesic sphere

Question

I have to make a sphere out of smaller uniformely distributed balls. I think the optimal way is to build a triangle-based geodesic sphere and use the vertices as the middle points of my balls. But I fail to write an algorithm generating the vertices. Answer in C++ or pseudo-code will be better.

Example of a geodesic sphere: https://i.stack.imgur.com/iNQfP.png

Crockett

Answer 1

Using the link @Muckle_ewe gave me, I was able to code the following algorithm: Outside the main()

class Vector3d {  // this is a pretty standard vector class
public:
    double x, y, z;
    ...
}

void subdivide(const Vector3d &v1, const Vector3d &v2, const Vector3d &v3, vector<Vector3d> &sphere_points, const unsigned int depth) {
    if(depth == 0) {
        sphere_points.push_back(v1);
        sphere_points.push_back(v2);
        sphere_points.push_back(v3);
        return;
    }
    const Vector3d v12 = (v1 + v2).norm();
    const Vector3d v23 = (v2 + v3).norm();
    const Vector3d v31 = (v3 + v1).norm();
    subdivide(v1, v12, v31, sphere_points, depth - 1);
    subdivide(v2, v23, v12, sphere_points, depth - 1);
    subdivide(v3, v31, v23, sphere_points, depth - 1);
    subdivide(v12, v23, v31, sphere_points, depth - 1);
}

void initialize_sphere(vector<Vector3d> &sphere_points, const unsigned int depth) {
    const double X = 0.525731112119133606;
    const double Z = 0.850650808352039932;
    const Vector3d vdata[12] = {
        {-X, 0.0, Z}, { X, 0.0, Z }, { -X, 0.0, -Z }, { X, 0.0, -Z },
        { 0.0, Z, X }, { 0.0, Z, -X }, { 0.0, -Z, X }, { 0.0, -Z, -X },
        { Z, X, 0.0 }, { -Z, X, 0.0 }, { Z, -X, 0.0 }, { -Z, -X, 0.0 }
    };
    int tindices[20][3] = {
        {0, 4, 1}, { 0, 9, 4 }, { 9, 5, 4 }, { 4, 5, 8 }, { 4, 8, 1 },
        { 8, 10, 1 }, { 8, 3, 10 }, { 5, 3, 8 }, { 5, 2, 3 }, { 2, 7, 3 },
        { 7, 10, 3 }, { 7, 6, 10 }, { 7, 11, 6 }, { 11, 0, 6 }, { 0, 1, 6 },
        { 6, 1, 10 }, { 9, 0, 11 }, { 9, 11, 2 }, { 9, 2, 5 }, { 7, 2, 11 }
    };
    for(int i = 0; i < 20; i++)
        subdivide(vdata[tindices[i][0]], vdata[tindices[i][1]], vdata[tindices[i][2]], sphere_points, depth);
}

Then in the main():

vector<Vector3d> sphere_points;
initialize_sphere(sphere_points, DEPTH);  // where DEPTH should be the subdivision depth
for(const Vector3d &point : sphere_points)
    const Vector3d point_tmp = point * RADIUS + CENTER;  // Then for the sphere I want to draw, I  iterate over all the precomputed sphere points and with a linear function translate the sphere to its CENTER and chose the proper RADIUS

You actually only need to use initialize_sphere() once and use the result for every sphere you want to draw.

Crockett

You don't update the triangle list connectivity? – Defect

Answer 2

I've done this before for a graphics project, the algorithm I used is detailed on this website

http://www.opengl.org.ru/docs/pg/0208.html

just ignore any openGL drawing calls and only code up the parts that deal with creating the actual vertices

Mu

Using the link you gave to me, I was able to code the algorithm (see my answer). Thanks a lot. – Crockett

Answer 3

There are well known algorithms to triangulate surfaces. You should be able to use the GNU Triangulated Surface Library to generate a suitable mesh if you don't want to code one of them up yourself.

Biddle

Answer 4

It depends on the number of triangles you want the sphere to have. You can potentially have infinite resolution.

First focus on creating a dome, you can double it later by taking the negative coordinates of your upper dome. You will generate the sphere by interlocking rows of triangles. Your triangles are equilateral, so decide on a length. Divide 2(pi)r by the number of triangles you want to be on the bottom row of the dome. This will be the length of each side of each triangle.

Next you need to create a concentric circle that intersects the surface of the sphere. Between this circle and the base of the dome will be your first row. You will need to find the angle that each triangle is tilted. (I will post later when I figure that out)

Repeat process for each concentric circle (generating row) until the height of the row * the number of rows approximately equals the 2(pi)r that u started with.

I will try to program it later if I get a chance. You could also try posting in the Math forum.

Dreda