Thursday, October 25, 2012

Removing duplicate vertices; equivalencing vertices at the same location

Triangulated surface after removing duplicate vertices.

In medical imaging one can run into following problem: After creating a triangulated surface  (e.g. with the Marching Cubes algorithm), duplicated vertices exist at the same location. Why is that a problem? Well it is not really a problem but processing duplicated (=same location at x,y,z coordinate) requires more memory and is more expensive on the graphic processing unit (GPU). The simplest way to find vertices at the same location is to compare each vertex with all existing vertices. This can be implemented with loops and is usually ridiculous slow! Another method is to use a "look-up table", a three dimensional array that will hold the number of the according vertex. A vertex pointer (x,y,z coordinate of vertex) is used to fill the according index in the look-up table; if an index is already filled then the vertex already exists. I've implemented such an algorithm in Python. I tested the algorithm with a data set that had originally 707190 vertices and after equivalenving only 117300 (83% reduction!). The total CPU time for this process was 2.899 seconds.

The function can be found at: 

No comments:

Post a Comment