godotgodot4procedural-generation

Missing triangles in icosphere when using ArrayMesh


I am trying to create a Goldberg sphere (sphere with hexagons and pentagons) from an icosphere using Godot 4, but some triangles are not appearing: The icosahedron All the vertices exist.

I tried different ways of adding the new vertices to the array new_faces:

  1. All of them at the same time (creating a new array)
  2. One by one, using append
  3. One by one, usingpush_back

I tried coloring differently all the new triangles I create in function subdivide, and it looks like the one I create using the centers of the edges is the one that is missing.

Code:

Icosahedron generation and subdivision

    var vertices:PackedVector3Array = []
    
    var faces = []
    func generate_icosphere():
        var t = (1.0 + sqrt(5.0)) / 2
        
        vertices.push_back(Vector3(-1, t, 0).normalized())
        vertices.push_back(Vector3(1, t, 0).normalized())
        vertices.push_back(Vector3(-1, -t, 0).normalized())
        vertices.push_back(Vector3(1, -t, 0).normalized())
        vertices.push_back(Vector3(0, -1, t).normalized())
        vertices.push_back(Vector3(0, 1, t).normalized())
        vertices.push_back(Vector3(0, -1, -t).normalized())
        vertices.push_back(Vector3(0, 1, -t).normalized())
        vertices.push_back(Vector3(t, 0, -1).normalized())
        vertices.push_back(Vector3(t, 0, 1).normalized())
        vertices.push_back(Vector3(-t, 0, -1).normalized())
        vertices.push_back(Vector3(-t, 0, 1).normalized())
        
        faces.push_back(Triangle.new(vertices[0], vertices[11], vertices[5]))
        faces.push_back(Triangle.new(vertices[0], vertices[5], vertices[1]))
        faces.push_back(Triangle.new(vertices[0], vertices[1], vertices[7]))
        faces.push_back(Triangle.new(vertices[0], vertices[7], vertices[10]))
        faces.push_back(Triangle.new(vertices[0], vertices[10], vertices[11]))
        faces.push_back(Triangle.new(vertices[1], vertices[5], vertices[9]))
        faces.push_back(Triangle.new(vertices[5], vertices[11], vertices[4]))
        faces.push_back(Triangle.new(vertices[11], vertices[10], vertices[2]))
        faces.push_back(Triangle.new(vertices[10], vertices[7], vertices[6]))
        faces.push_back(Triangle.new(vertices[7], vertices[1], vertices[8]))
        faces.push_back(Triangle.new(vertices[3], vertices[9], vertices[4]))
        faces.push_back(Triangle.new(vertices[3], vertices[4], vertices[2]))
        faces.push_back(Triangle.new(vertices[3], vertices[2], vertices[6]))
        faces.push_back(Triangle.new(vertices[3], vertices[6], vertices[8]))
        faces.push_back(Triangle.new(vertices[3], vertices[8], vertices[9]))
        faces.push_back(Triangle.new(vertices[4], vertices[9], vertices[5]))
        faces.push_back(Triangle.new(vertices[2], vertices[4], vertices[11]))
        faces.push_back(Triangle.new(vertices[6], vertices[2], vertices[10]))
        faces.push_back(Triangle.new(vertices[8], vertices[6], vertices[7]))
        faces.push_back(Triangle.new(vertices[9], vertices[8], vertices[1]))
    func subdivide(_radius):
        var new_faces = []
        for face in faces:
            var vert0 = face.vertices[0]
            var vert1 = face.vertices[1]
            var vert2 = face.vertices[2]
            var center0_1:Vector3 = lerp(vert0, vert1, 0.5).normalized()
            var center1_2:Vector3 = lerp(vert1, vert2, 0.5).normalized()
            var center2_0:Vector3 = lerp(vert2, vert0, 0.5).normalized()
            new_faces.push_back(Triangle.new(vert0, center0_1, center2_0))
            new_faces.push_back(Triangle.new(vert1, center0_1, center1_2))
            new_faces.push_back(Triangle.new(vert2, center1_2, center2_0))
            new_faces.push_back(Triangle.new(center0_1, center1_2, center2_0))
            print(face, new_faces)
        return new_faces
    func generate(subdivisions,radius):
        generate_icosphere()
        var result_faces:Array = []
        result_faces = subdivide(20)
        return result_faces
    class Triangle:
        var vertices:PackedVector3Array = []
        func _init(a, b, c):
            vertices.push_back(a)
            vertices.push_back(b)
            vertices.push_back(c)

Thanks in advance.


Solution

  • I found how to do it with a bit of help from ChatGPT :-). It looks like I needed indices because sometimes two vertices were the same. The code:

    func generate_icosahedron():
        var t = (1.0 + sqrt(5.0)) / 2.0
    
        var vertices = [
            Vector3(-1,  t,  0).normalized(), Vector3( 1,  t,  0).normalized(), Vector3(-1, -t,  0).normalized(), Vector3( 1, -t,  0).normalized(),
            Vector3( 0, -1,  t).normalized(), Vector3( 0,  1,  t).normalized(), Vector3( 0, -1, -t).normalized(), Vector3( 0,  1, -t).normalized(),
            Vector3( t,  0, -1).normalized(), Vector3( t,  0,  1).normalized(), Vector3(-t,  0, -1).normalized(), Vector3(-t,  0,  1).normalized()
        ]
    
        var faces = [
            [0, 11, 5], [0, 5, 1], [0, 1, 7], [0, 7, 10], [0, 10, 11],
            [1, 5, 9], [5, 11, 4], [11, 10, 2], [10, 7, 6], [7, 1, 8],
            [3, 9, 4], [3, 4, 2], [3, 2, 6], [3, 6, 8], [3, 8, 9],
            [4, 9, 5], [2, 4, 11], [6, 2, 10], [8, 6, 7], [9, 8, 1]
        ]
    
        return [vertices, faces]
    func get_face_center(p0: int, p1: int, p2: int, vertex_vertices: Array, vertices: Array):
        var point0 = vertex_vertices[p0]
        var point1 = vertex_vertices[p1]
        var point2 = vertex_vertices[p2]
        var middle = (point0 + point1 + point2) / 3.0
        middle = middle.normalized()
        if vertices.has(middle):
            return [vertices.find(middle), middle, false]
        var index = vertices.size()
        return [index, middle, true]
    func generate_icosphere(subdivisions: int):
        var data = generate_icosahedron()
        var vertices = data[0]
        var faces = data[1]
    
        for i in range(subdivisions):
            var new_faces = []
            var middle_point_cache = {}
    
            for face in faces:
                var v1 = face[0]
                var v2 = face[1]
                var v3 = face[2]
    
                var a = get_middle_point(v1, v2, vertices, middle_point_cache)
                var b = get_middle_point(v2, v3, vertices, middle_point_cache)
                var c = get_middle_point(v3, v1, vertices, middle_point_cache)
    
                new_faces += [[v1, a, c], [v2, b, a], [v3, c, b], [a, b, c]]
            faces = new_faces
    
        for k in range(vertices.size()):
            vertices[k] = vertices[k].normalized()
    
        return [vertices, faces]
    func get_middle_point(p1: int, p2: int, vertices: Array, cache: Dictionary) -> int:
        var smaller_index = min(p1, p2)
        var greater_index = max(p1, p2)
        var key = str(smaller_index) + "-" + str(greater_index)
        if cache.has(key):
            return cache[key]
    
        var point1 = vertices[p1]
        var point2 = vertices[p2]
        var middle = (point1 + point2) / 2.0
        middle = middle.normalized()
    
        var index = vertices.size()
        vertices.append(middle)
    
        cache[key] = index
    
        return index
    

    So, for anyone interested, it return vertices and an array of faces.