1 Reply Latest reply on Jul 12, 2012 1:34 PM by gsellers

    Sorting 3D vertices list


      Hi all,

      I have a 3D vertices list (obtained from Marching Cubes algorithm) and I want to sort this list in order to delete duplicate vertices. How can I do?

      Or is there another way to do that?


        • Re: Sorting 3D vertices list



          This seems like you need a general algorithm for removing duplicates from a list. This isn't really graphics specific because this kind of thing is useful in many fields. A brute force approach would be to sort the vertices in order of x, y, and z coordinates using your favorite sorting algorithm and then look for duplicates vertices which will now be adjacent. Obviously, there are a number of optimizations you could make here - for example, you're not going to get duplicate vertices generated from cubes separated by at least one other cube. Another way to do this is during list generation. Each time you need to generate a new vertex, you can look in the current list for a vertex that matches the one you're trying to add and only add a new vertex if you don't find one. I'm sure there are plenty of more advanced algorithms out there for this kind of thing. The choice of how much effort you want to expend here is somewhat dependent on whether this is a one-off thing, or a tool that you want to use over and over, and whether it's designed to be an offline tool like a preprocessor, or part of a real-time engine, for example.