Getting a segmentation fault in a for loop

Question

I read an article on sphere creation for a project of mine that can be found here and decided to try and port it over to c, the language I'm working with. I chose the icosphere method, where you start with an icosahedron, and subdivide from there. The problem is that i get seg faults, but it happens when i try to subdivide it. But if i leave it as is and don't try and subdivide, the code compiles fine no errors.

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <stdint.h>

struct Point
{
    double x;
    double y;
    double z;
};

struct Triangle
{
    int v1;
    int v2;
    int v3;
};

// normalizes a vertex and then adds it to an array
int add_vertex(struct Point verts[], struct Point point)
{
    double length = (point.x * point.x) + (point.y * point.y) + (point.z * point.z);

    int index = 0;
    
    verts[index].x = point.x / length;
    verts[index].y = point.y / length;
    verts[index].z = point.z / length;
    
    return index++;
}

// gets the middle of a triangle face but checks to make sure that no duplicate vertices are created
int get_middle_point(int p1, int p2, struct Triangle inds[], struct Point verts[], int cache[])
{
    // check to see if the middle point is already calculated
    uint64_t key = (p1 < p2) ? (p1, p2) : (p2, p1);

    if (cache[key] != 0)
    {
        return cache[key];
    }

    // it isn't so calculate it
    struct Point point1 = verts[p1];
    struct Point point2 = verts[p2];
    struct Point middle;
    middle.x = (point1.x + point2.x) / 2.0;
    middle.y = (point1.y + point2.y) / 2.0;
    middle.z = (point1.z + point2.z) / 2.0;

    // add middle vertex to unit sphere
    int i = add_vertex(verts, middle);
    return i;
}

// creates icosphere by subdividing icosahedron
void create_icosphere(int recursion_level, struct Point verts[], struct Triangle inds[])
{
    // cache middle points
    int middle_point_cache[1000];

    // golden ratio
    float t = 1 + sqrt(5) * 0.5;

    // icosahedron cartisean coordinates from wikipedia
    add_vertex(verts, (struct Point){-1, t, 0});
    add_vertex(verts, (struct Point){1, t, 0});
    add_vertex(verts, (struct Point){-1, -t, 0});
    add_vertex(verts, (struct Point){1, -t, 0});

    add_vertex(verts, (struct Point){0, -1, t});
    add_vertex(verts, (struct Point){0, 1, t});
    add_vertex(verts, (struct Point){0, -1, -t});
    add_vertex(verts, (struct Point){0, 1, -t});

    add_vertex(verts, (struct Point){t, 0, -1});
    add_vertex(verts, (struct Point){t, 0, 1});
    add_vertex(verts, (struct Point){-t, 0, -1});
    add_vertex(verts, (struct Point){-t, 0, 1});

    // icosahedron indices

    // 5 faces around point 0
    inds[0] = (struct Triangle){0, 11, 5};
    inds[1] = (struct Triangle){0, 5, 1};
    inds[2] = (struct Triangle){0, 1, 7};
    inds[3] = (struct Triangle){0, 7, 10};
    inds[4] = (struct Triangle){0, 10, 11};

    // 5 adjacent faces
    inds[5] = (struct Triangle){1, 5, 9};
    inds[6] = (struct Triangle){5, 11, 4};
    inds[7] = (struct Triangle){11, 10, 2};
    inds[8] = (struct Triangle){10, 7, 6};
    inds[9] = (struct Triangle){7, 1, 8};

    // 5 faces around point 3
    inds[10] = (struct Triangle){3, 9, 4};
    inds[11] = (struct Triangle){3, 4, 2};
    inds[12] = (struct Triangle){3, 2, 6};
    inds[13] = (struct Triangle){3, 6, 8};
    inds[14] = (struct Triangle){3, 8, 9};

    // 5 adjacent faces
    inds[15] = (struct Triangle){4, 9, 5};
    inds[16] = (struct Triangle){2, 4, 11};
    inds[17] = (struct Triangle){6, 2, 10};
    inds[18] = (struct Triangle){8, 6, 7};
    inds[19] = (struct Triangle){9, 8, 1};

    // subdivide icosahedron
    for (int i = 0; i < recursion_level; i++)
    {
        // create new array for newly created triangle faces
        struct Triangle faces_2[1000];
        int faces_2_index = 0;
        for (int j = 0; j < 20; j++)
        {
            struct Triangle tri = inds[j];

            // get the centroid of each triangle face
            int a = get_middle_point(tri.v1, tri.v2, faces_2, verts, middle_point_cache);
            int b = get_middle_point(tri.v2, tri.v3, faces_2, verts, middle_point_cache);
            int c = get_middle_point(tri.v3, tri.v1, faces_2, verts, middle_point_cache);

            // add new faces to new faces array
            faces_2[faces_2_index++] = (struct Triangle){tri.v1, a, c};
            faces_2[faces_2_index++] = (struct Triangle){tri.v2, b, a};
            faces_2[faces_2_index++] = (struct Triangle){tri.v3, c, b};
            faces_2[faces_2_index++] = (struct Triangle){tri.v1, tri.v2, tri.v3};
        }

        // copy over contents from new array to indices
        for (int j = 0; j < faces_2_index; j++)
        {
            inds[j] = faces_2[j];
        }
    }
}

int main()
{
    // example usage. works with a subdivision level of 0 but anything higher causes a seg fault
    struct Point vertices[1000];
    struct Triangle indices[1000];
    create_icosphere(2, vertices, indices);
    printf("No errors\n");

    return 0;
}

I narrowed the problem down to either the subdivision loop or the get_middle_point function (which is called in the subdivision loop). But i don't know why there would be errors there or how to even solve them. This is currently where my compiler is pointing to for the seg fault error in nested subdivide loop which is inside the subdivision loop.

Answer 1

In the subdivision loop, I created a new array

struct Triangle faces_2[20 * recursion_level];

but then write out of bounds later on with

faces_2[faces_2_index++] = (struct Triangle){tri.v1, a, c};
faces_2[faces_2_index++] = (struct Triangle){tri.v2, b, a};        
faces_2[faces_2_index++] = (struct Triangle){tri.v3, c, b};
faces_2[faces_2_index++] = (struct Triangle){tri.v1, tri.v2, tri.v3};

so to solve my problem, I just needed to increase the size

struct Triangle faces_2[1000];

and it works. I'm keeping it 1000 as a sample size for now but that's soon to change.

Answer 2

It is unlikely that the following code does what you think

int add_vertex(struct Point verts[], struct Point point) {
    double length = (point.x * point.x) + (point.y * point.y) + (point.z * point.z);

    int index = 0;

    verts[index].x = point.x / length;
    verts[index].y = point.y / length;
    verts[index].z = point.z / length;

    return index++;
}

This code accepts an array (pointer to a location in memory) and a "point". You use the point information to calculate a length (distance in 3D space). You then create an "index" at 0 and set the fields of the verts array's zeroth element to a value normalized by length. So far so good (assuming that's your intent).

You then increment 'index' which isn't invalid but it is useless. You declared index in the function making it a stack allocated variable. As soon as the function returns all those values disappear. The next time you call the function you will again set the zero'th element. The function as given will never set anything other than element [0].

There are a couple of things you can do to correct this but they all affect the structure of the calling code. One thing is to pass index in as a function parameter. I.E. specify the index value in each call. If you want to increment the index, you will need to pass the index value as a pointer (int *index) and not initialize it inside the function.

It might be cleaner to simply have the function return a Point struct. HOWEVER to do this you need to understand how memory in C works. You can refer to this question for help with that: Return a `struct` from a function in C

In short, C variables (generally) exist in either "heap" memory (governed by functions like malloc/alloc/free) or on the stack, where they live only as long as the context of the containing function. Seg-faults occur when you step outside of memory you don't own. Often when stepping of the end of an array (which are zero relative).

Often a decent debugger can help you understand where the fault is occurring but not why. The "why" is often simple, but can get very complicated. Still knowing where can help you backtrace to why.