c++algorithmgeometrytessellationgeodesic-sphere

Algorithm for a geodesic sphere


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.sstatic.net/iNQfP.png


Solution

  • 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.