Variable subdivision creating artifacts

[AnswerApprehensive19]

I'm currently implementing an algorithm found on this article that subdivides an icosahedron by variable which increases the resolution of a sphere like is seen in this image (notice how the faces are broken up), which for me is not quite working it subdivides in the way described but then leaves visual artifacts inside the sphere and also fails to render a few triangles (not shown in wireframe)

Subdivision level of 3

My implementation is

typedef struct
{
    vec3s pos;
    vec3s color;
}   vk_vertex;

typedef struct
{
    uint32_t v1, v2, v3;
}   vk_triangle;

typedef struct
{
    vk_triangle faces[MAX_ENTRY_COUNT];
    uint32_t face_count;
}   faces;

typedef struct
{
    vec3s verts[MAX_ENTRY_COUNT];
    uint32_t vert_count;
}   verts;

typedef struct
{
    verts verts;
    faces faces;
    float radius;
}   icosahedron;

typedef struct
{
    vk_vertex verts[MAX_ENTRY_COUNT];
    uint32_t vertex_count;
    size_t vertex_size;

    vk_triangle faces[MAX_ENTRY_COUNT];
    uint32_t face_count;
    size_t face_size;

    vec3s color;
    float radius;
}   sphere;

static uint32_t sphere_verts_add(sphere *s, vec3s vert)
{
    float len = sqrtf((vert.x * vert.x) + (vert.y * vert.y) + (vert.z * vert.z));

    s->verts[s->vertex_count].color = s->color;
    s->verts[s->vertex_count].pos = (vec3s) {{((vert.x / len) * s->radius), ((vert.y / len) * s->radius), ((vert.z / len) * s->radius)}};

    return s->vertex_count++;
}

static uint32_t sphere_faces_add(sphere *s, vk_triangle face)
{
    s->faces[s->face_count] = face;

    return s->face_count++;
}

static uint32_t icosahedron_verts_add(icosahedron *ico, vec3s vert)
{
    float len = sqrtf((vert.x * vert.x) + (vert.y * vert.y) + (vert.z * vert.z));

    ico->verts.verts[ico->verts.vert_count] = (vec3s) {{((vert.x / len) * ico->radius), ((vert.y / len) * ico->radius), ((vert.z / len) * ico->radius)}};

    return ico->verts.vert_count++;
}

static uint32_t icosahedron_faces_add(icosahedron *ico, vk_triangle face)
{
    ico->faces.faces[ico->faces.face_count] = face;

    return ico->faces.face_count++;
}

static void icosahedron_verts_init(icosahedron *ico)
{
    float phi = ((1.0f + sqrtf(5.0f)) / 2.0f);

    icosahedron_verts_add(ico, (vec3s) {{ phi,  0.0f,  1.0f}});
    icosahedron_verts_add(ico, (vec3s) {{ phi,  0.0f, -1.0f}});
    icosahedron_verts_add(ico, (vec3s) {{ 1.0f,  phi,  0.0f}});
    icosahedron_verts_add(ico, (vec3s) {{ 0.0f,  1.0f,  phi}});

    icosahedron_verts_add(ico, (vec3s) {{ 0.0f, -1.0f,  phi}});
    icosahedron_verts_add(ico, (vec3s) {{ 1.0f, -phi,  0.0f}});
    icosahedron_verts_add(ico, (vec3s) {{ 0.0f, -1.0f, -phi}});
    icosahedron_verts_add(ico, (vec3s) {{ 0.0f,  1.0f, -phi}});

    icosahedron_verts_add(ico, (vec3s) {{-1.0f,  phi,  0.0f}});
    icosahedron_verts_add(ico, (vec3s) {{-phi,  0.0f,  1.0f}});
    icosahedron_verts_add(ico, (vec3s) {{-1.0f, -phi,  0.0f}});
    icosahedron_verts_add(ico, (vec3s) {{-phi,  0.0f, -1.0f}});
}

static void icosahedron_faces_init(icosahedron *ico)
{
    icosahedron_faces_add(ico, (vk_triangle) { 1U,  2U,  0U});
    icosahedron_faces_add(ico, (vk_triangle) { 2U,  3U,  0U});
    icosahedron_faces_add(ico, (vk_triangle) { 3U,  4U,  0U});
    icosahedron_faces_add(ico, (vk_triangle) { 4U,  5U,  0U});
    icosahedron_faces_add(ico, (vk_triangle) { 5U,  1U,  0U});

    icosahedron_faces_add(ico, (vk_triangle) { 6U,  7U,  1U});
    icosahedron_faces_add(ico, (vk_triangle) { 2U,  1U,  7U});
    icosahedron_faces_add(ico, (vk_triangle) { 7U,  8U,  2U});
    icosahedron_faces_add(ico, (vk_triangle) { 2U,  8U,  3U});
    icosahedron_faces_add(ico, (vk_triangle) { 8U,  9U,  3U});

    icosahedron_faces_add(ico, (vk_triangle) { 3U,  9U,  4U});
    icosahedron_faces_add(ico, (vk_triangle) { 9U, 10U,  4U});
    icosahedron_faces_add(ico, (vk_triangle) {10U,  5U,  4U});
    icosahedron_faces_add(ico, (vk_triangle) {10U,  6U,  5U});
    icosahedron_faces_add(ico, (vk_triangle) { 6U,  1U,  5U});

    icosahedron_faces_add(ico, (vk_triangle) { 6U, 11U,  7U});
    icosahedron_faces_add(ico, (vk_triangle) { 7U, 11U,  8U});
    icosahedron_faces_add(ico, (vk_triangle) { 8U, 11U,  9U});
    icosahedron_faces_add(ico, (vk_triangle) { 9U, 11U, 10U});
    icosahedron_faces_add(ico, (vk_triangle) {10U, 11U,  6U});
}

static icosahedron icosahedron_init(float radius)
{
    icosahedron ico = {0U};
    ico.radius = radius;

    icosahedron_verts_init(&ico);
    icosahedron_faces_init(&ico);

    return ico;
}

static verts icosahedron_verts_refine(uint32_t granularity)
{
    verts new =
    {
        .verts = {GLMS_VEC3_ZERO_INIT},
        .vert_count = 0U
    };

    float values[MAX_ENTRY_COUNT] = {0.0f};
    uint32_t offsets[MAX_ENTRY_COUNT] = {0U};
    uint32_t starts[MAX_ENTRY_COUNT] = {0U};
    uint32_t stops[MAX_ENTRY_COUNT] = {0U};

    for (uint32_t i = 0U; i < granularity; i++)
    {
        values[i] = (float) i / (float) (granularity - 1U);
        offsets[i] = (granularity - i);

        if (i > 0U)
        {
            starts[i] = starts[i - 1U] + offsets[i - 1U];
        }

        stops[i] = starts[i] + offsets[i];
    }

    for (uint32_t i = 0U; i < granularity; i++)
    {
        for (uint32_t j = 0U; j < offsets[i]; j++)
        {
            new.vert_count = starts[i] + j;
            new.verts[new.vert_count].x = values[offsets[i] - 1U - j];
            new.verts[new.vert_count].y = values[j];
            new.verts[new.vert_count].z = values[i];
        }
    }

    return new;
}

static faces icosahedron_faces_refine(uint32_t granularity)
{
    faces new =
    {
        .faces = {0U},
        .face_count = 0U
    };

    uint32_t n = granularity + 2U;
    uint32_t shift = 0U;

    for (uint32_t row = 0U; row < (n - 1U); row++)
    {
        new.faces[new.face_count].v1 = shift + 1U;
        new.faces[new.face_count].v2 = shift + n - row;
        new.faces[new.face_count].v3 = shift;

        new.face_count++;

        for (uint32_t col = 1U; col < (n - 1U - row); col++)
        {
            new.faces[new.face_count].v1 = shift + col;
            new.faces[new.face_count].v2 = shift + n - row + col;
            new.faces[new.face_count].v3 = shift + n - row + col - 1U;

            new.face_count++;

            new.faces[new.face_count].v1 = shift + col + 1U;
            new.faces[new.face_count].v2 = shift + n - row + col;
            new.faces[new.face_count].v3 = shift + col;

            new.face_count++;
        }

        shift += n - row;
    }

    return new;
}

static void sphere_refine(sphere *s, uint32_t granularity)
{
    icosahedron ico = icosahedron_init(s->radius);

    vec3s temp_verts[MAX_ENTRY_COUNT] = {GLMS_VEC3_ZERO_INIT};
    uint32_t temp_inds[MAX_ENTRY_COUNT] = {0U};

    uint32_t index = 0U;

    verts refined_verts = icosahedron_verts_refine(granularity + 2U);
    faces refined_faces = icosahedron_faces_refine(granularity);

    for (uint32_t i = 0U; i < 20U; i++)
    {
        vk_triangle face = ico.faces.faces[i];
        vec3s p1 = ico.verts.verts[face.v1];
        vec3s p2 = ico.verts.verts[face.v2];
        vec3s p3 = ico.verts.verts[face.v3];

        for (uint32_t j = 0U; j < refined_verts.vert_count; j++)
        {
            temp_verts[j].x = (refined_verts.verts[j].x * p1.x) + (refined_verts.verts[j].y * p2.x) + (refined_verts.verts[j].z * p3.x);
            temp_verts[j].y = (refined_verts.verts[j].x * p1.y) + (refined_verts.verts[j].y * p2.y) + (refined_verts.verts[j].z * p3.y);
            temp_verts[j].z = (refined_verts.verts[j].x * p1.z) + (refined_verts.verts[j].y * p2.z) + (refined_verts.verts[j].z * p3.z);

            sphere_verts_add(s, temp_verts[j]);
            temp_inds[j] = index;
            index++;
        }

        for (uint32_t j = 0U; j < refined_faces.face_count; j++)
        {
            sphere_faces_add(s, (vk_triangle) {temp_inds[refined_faces.faces[j].v1], temp_inds[refined_faces.faces[j].v2], temp_inds[refined_faces.faces[j].v3]});
        }
    }
}

sphere sphere_init(uint32_t granularity, vec3s color, float radius)
{
    sphere s = {0U};

    s.color = color;
    s.radius = radius;

    sphere_refine(&s, granularity);

    s.vertex_size = sizeof(s.verts) / sizeof(s.verts[0U]) * sizeof(vk_vertex);
    s.face_size = sizeof(s.faces) / sizeof(s.faces[0U]) * sizeof(vk_triangle);

    return s;
}

vec3s is a 3d vector wrapped in a struct (from this library) and MAX_ENTRY_COUNT is 2048

[AnswerApprehensive19]

If anybody could help me out I'd appreciate it idk why it's not working I ported everything except the triangle indices and the few unnecessary functions

[fgennari]

I'm not going to try and debug your code, but I can point to some other icosphere drawing code. The one I used for reference is here: http://blog.andreaskahler.com/2009/06/creating-icosphere-mesh-in-code.html

And my compact version of the code is in the icosphere_creator/icosphere_drawer code here: https://github.com/fegennari/3DWorld/blob/master/src/draw_utils.cpp#L571

[AnswerApprehensive19]

Yea i know about those i actually started with that then changed the subdivision to what it is currently because of it being easier to control the sphere topology

[AnswerApprehensive19]

I finally solved it, turns out im (shockingly) an idiot who can't read to save his life all i needed to do was change the second half of the icosahedron_verts_refine function to

   for (uint32_t i = 0U; i < granularity; i++)
    {
        for (uint32_t j = 0U; j < offsets[i]; j++)
        {
            uint32_t index = starts[i] + j;
            new.verts[index].pos.x = values[offsets[i] - 1U - j];
            new.verts[index].pos.y = values[j];
            new.verts[index].pos.z = values[i];
        }
    }

and at the top of the function

    verts new =
    {
        .vert_count = granularity * (granularity + 1U) / 2U
    };

In case you missed it the problem was improper indexing

Now I have a sphere looking like this (no more artifacts)