CODEWITHSUNDEEP
pythonopenglgraphicsrenderingpolygon
vwertuzy
vwertuzy

Reputation: 211

How do I a generate a list of edges from a given list of vertex indices?

I have a face-vertex mesh like the following image has.

Face-Vertex Mesh

I have 'face_list' and 'vertex_list' data sets, but not sure how to efficiently calculate a list of edges.

Upvotes: 1

Views: 1273

Answers (1)

Rabbid76
Rabbid76

Reputation: 211258

Compute the normal vectors of the faces. If the normal vectors of 2 adjacent faces point in different directions, the two vertices shared by the face form an edge.

The normal vectors of a face can be computed with the Cross product. For a face with the vertices A, B, C, the unit normal vector is:

N = normalized(cross(B-A, C-A))

The normal vectors of the faces can be compared with the Dot product. 2 normal vectors N1 and N2 are equal directed if:

equally_directed = abs(dot(N1, N2)) == 1

Use a library for the vector arithmetic. For example OpenGL Mathematics (GLM) library for Python or NumPy.

Minimal example:

import glm, math

vertices = [(-1,-1,-1), ( 1,-1,-1), ( 1, 1,-1), (-1, 1,-1), (-1,-1, 1), ( 1,-1, 1), ( 1, 1, 1), (-1, 1, 1)]
faces = [(0,1,2), (0,2,3), (5,4,7), (5,7,6), (4,0,3), (4,3,7), (1,5,6), (1,6,2), (4,5,1), (4,1,0), (3,2,6), (3,6,7)]

v = [glm.vec3(vertex) for vertex in vertices]
nv_list = [glm.normalize(glm.cross(v[i1]-v[i0], v[i2]-v[i0])) for i0,i1,i2 in faces]

edge_threshold = 0.99
edges = []
for i, f1 in enumerate(faces):
    for j, f2 in enumerate(faces[i+1:]):
        edge_candidates = [(f1[0], f1[1]), (f1[1], f1[2]), (f1[2], f1[0])]
        for ei0, ei1 in edge_candidates:
            if ei0 in f2 and ei1 in f2:
                cos_nv = math.fabs(glm.dot(nv_list[i], nv_list[j+i+1]))
                if  abs(cos_nv) < edge_threshold:
                    edges.append((ei0, ei1))

print(len(edges))
print(edges)

Output:

12
[(1, 2), (0, 1), (3, 0), (2, 3), (4, 7), (5, 4), (6, 5), (7, 6), (4, 0), (3, 7), (1, 5), (6, 2)]

Upvotes: 2

Related Questions