Advertisement

Variable subdivision creating artifacts

Started by September 18, 2024 08:34 PM
0 comments, last by Chillzy 1 day, 16 hours ago

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

None

Advertisement