0
\$\begingroup\$

I have a set of vertices and another set of indices. Sometimes I find that I have duplicate vertices in my mesh.

I tried at first to check if two identical vertices were in the array of vertices but that didn't work because I remembered that more that if one vertex represents multiple edges then the vertex would be validly represented as multiple vertices in the vertices array.

Then I remembered that the indices help represent how the vertices are structured but I didn't know how to use them. So I came here to ask how to use them to detect duplicate vertices in a mesh.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – user116458
    May 26, 2018 at 16:49
  • \$\begingroup\$ "if one vertex represents multiple edges then the vertex would be validly represented as multiple vertices in the vertices array." This is not true. That's the job of the indices array. A unique vertex (including all attributes like normals/UVs/colours/etc, if used) that occurs in multiple triangles should still occur exactly once in the vertices array. It will just be referenced multiple times by the indices array. Multiple identical vertex entries in the vertices array is exactly the error that the answer below solves. If these dupes were correct as-is, we wouldn't need to fix anything. \$\endgroup\$
    – DMGregory ♦
    Aug 8, 2018 at 17:01

1 Answer 1

Reset to default
0
\$\begingroup\$

First you'll need a lookup structure to look up vertices you've processed so far. This could be, for example, a dictionary keyed on the position of your vertices, or an octree/k-d tree/etc. Each entry will hold the updated index of the de-duplicated vertex at that position.

(If you're using this for display meshes, you'll want to count vertices with different normals/UVs as distinct, but if I recall correctly you're working on collision meshes so we can ignore this detail and treat vertices as pure positions)

Next you'll need a re-indexing list the same size as your initial list of vertex positions. This will hold the new index of each vertex after de-duplication.

Initialize a vertex count to zero. Iterate over your list of vertices, checking to see if each position (or one within a small rounding tolerance) is already in your lookup collection.

  • If there's no vertex recorded yet at that point, set the current vertex's new index to your current vertex count, and increment that count. Write this vertex and its new index into your lookup structure.

  • If you already have a vertex recorded at that point, set the current vertex's index to that recorded index and do not increment the vertex count.

Either way, write the new index you've chosen for this vertex into the re-indexing list.

At the end, or as you go, you can build your new vertex list, using only the first vertex with each new index.

Then you need to update your index list. For each entry in the list, replace it with the corresponding new index looked from your re-indexing list. ie. indices[i] = reindex[indices[i]];

Lastly, check to see whether any triangles have become degenerate (two or three indices all pointing to the same vertex) - if so, you can delete that whole triangle. (Swapping 3 indices from the end of the list, or moving the rest of the indices back 3 spaces to fill the gap)

Improve this answer
\$\endgroup\$
0

You must log in to answer this question.