移植icosphere生成代码到C语言时，细分循环出现段错误

我在项目中移植了icosphere生成代码，基于二十面体细分方案。不细分时代码运行正常，但开启细分（递归级别≥1）就会触发段错误，已定位问题出在细分循环或get_middle_point函数内，编译器指向细分嵌套循环报错。

原问题代码 #

#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;
}

核心错误点及修复方案 #

• add_vertex函数顶点索引错误：每次调用都重置index为0，导致所有顶点覆盖到数组第0位，后续访问必然越界。需要维护顶点计数器，同时修复归一化逻辑（原代码用长度平方做除数，未正确归一化到单位球）。
• get_middle_point函数key生成逻辑错误：用逗号表达式生成key，实际只取第二个值，无法唯一标识顶点对。需将两个32位整数合并为64位key，同时移除无用参数。
• 缓存数组未初始化：middle_point_cache为局部变量，默认值随机，需初始化为-1标记未缓存状态。
• 细分循环三角形数量固定为20：每次细分后三角形数量变为4倍，需动态记录当前三角形数量，而非固定遍历20个。
• 细分逻辑错误：原代码保留了原三角形，导致几何结构混乱，正确做法是将一个三角形拆分为4个小三角形。

修正后的完整代码 #

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

#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

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

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

int add_vertex(struct Point verts[], struct Point point, int* vertex_count)
{
    double length_sq = point.x*point.x + point.y*point.y + point.z*point.z;
    double length = sqrt(length_sq);
    
    verts[*vertex_count].x = point.x / length;
    verts[*vertex_count].y = point.y / length;
    verts[*vertex_count].z = point.z / length;
    
    return (*vertex_count)++;
}

int get_middle_point(int p1, int p2, struct Point verts[], int* vertex_count, int cache[])
{
    uint64_t key = ((uint64_t)MIN(p1,p2) << 32) | MAX(p1,p2);
    
    if (cache[key] != -1)
    {
        return cache[key];
    }
    
    struct Point point1 = verts[p1];
    struct Point point2 = verts[p2];
    struct Point middle = {
        (point1.x + point2.x)/2.0,
        (point1.y + point2.y)/2.0,
        (point1.z + point2.z)/2.0
    };
    
    int idx = add_vertex(verts, middle, vertex_count);
    cache[key] = idx;
    return idx;
}

void create_icosphere(int recursion_level, struct Point verts[], struct Triangle inds[], int* out_vertex_count, int* out_triangle_count)
{
    int middle_point_cache[1000];
    memset(middle_point_cache, -1, sizeof(middle_point_cache));
    
    int vertex_count = 0;
    float t = (1 + sqrt(5)) * 0.5;
    
    add_vertex(verts, (struct Point){-1, t, 0}, &vertex_count);
    add_vertex(verts, (struct Point){1, t, 0}, &vertex_count);
    add_vertex(verts, (struct Point){-1, -t, 0}, &vertex_count);
    add_vertex(verts, (struct Point){1, -t, 0}, &vertex_count);
    
    add_vertex(verts, (struct Point){0, -1, t}, &vertex_count);
    add_vertex(verts, (struct Point){0, 1, t}, &vertex_count);
    add_vertex(verts, (struct Point){0, -1, -t}, &vertex_count);
    add_vertex(verts, (struct Point){0, 1, -t}, &vertex_count);
    
    add_vertex(verts, (struct Point){t, 0, -1}, &vertex_count);
    add_vertex(verts, (struct Point){t, 0, 1}, &vertex_count);
    add_vertex(verts, (struct Point){-t, 0, -1}, &vertex_count);
    add_vertex(verts, (struct Point){-t, 0, 1}, &vertex_count);
    
    int triangle_count = 20;
    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};
    
    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};
    
    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};
    
    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};
    
    for (int i = 0; i < recursion_level; i++)
    {
        struct Triangle faces_2[1000];
        int faces_2_index = 0;
        
        for (int j = 0; j < triangle_count; j++)
        {
            struct Triangle tri = inds[j];
            int a = get_middle_point(tri.v1, tri.v2, verts, &vertex_count, middle_point_cache);
            int b = get_middle_point(tri.v2, tri.v3, verts, &vertex_count, middle_point_cache);
            int c = get_middle_point(tri.v3, tri.v1, verts, &vertex_count, middle_point_cache);
            
            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){a, b, c};
        }
        
        triangle_count = faces_2_index;
        memcpy(inds, faces_2, sizeof(struct Triangle)*triangle_count);
    }
    
    *out_vertex_count = vertex_count;
    *out_triangle_count = triangle_count;
}

int main()
{
    struct Point vertices[1000];
    struct Triangle indices[1000];
    int vertex_count, triangle_count;
    
    create_icosphere(2, vertices, indices, &vertex_count, &triangle_count);
    
    printf("生成成功！顶点数：%d，三角形数：%d\n", vertex_count, triangle_count);
    printf("No errors\n");
    
    return 0;
}

内容的提问来源于stack exchange，提问作者user11487729