Jump to content
  • Advertisement
Sign in to follow this  
MaartenDeNef

remove duplicate vertices

This topic is 2398 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

I'm making a small project (for school) with marching cubes to generate a terrain.
Now everything works fine except i cant find a way to merge / remove my duplicate vertices in a cpu friendly way.

At the moment i'm just cross checking my list for duplicates (takes alot of time)

Does anyone know an algorithm or something that can help me out.

Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Removing duplicate vertices efficiently can be tricky. If the vertices are EXACTLY the same, you can hash them. If you if don't trust hashing float values (which you shouldn't), you can discretize the values into integers, and then hash. But even that can get you in trouble. What you really need to do is compute the distance from each point to all the other points, and fuse and vertices smaller than a constant error threshold value. But that's O(n^2). What do you do?

What I do is I have a custom 'hashtable' for this, with a special 'hash' function, which is just: spatial_hash(float x, float y, float z) = (x+y+z). What does this do? If two points are close in space, then their x,y and z values are also close, and so is their spatial_hash value. For instance, if for two points, x and y are the same but z differs by .1 units, then the hash will only differ by .1 units. It's easy to see that for any given threshold distance D that you want to use for the error threshold, there is a 'worst-case' maximum spatial_hash delta value. So now we have a function where if two points in 3-dimenstions are close together, their value (which is now one dimenstional) is close together.

So, now you arrange them in buckets, just like a hashtable. What is the bucket_size? Well, each bucket should be the width of the spatial_hash delta value. This guarantees that for a given point, if you figure out what bucket it belongs to, all the points within that threshold distance D are either in that bucket, or one of its immediate neighbors. This makes the problem very close to O(n).

Share this post


Link to post
Share on other sites
Was going to say something like that as well just put them into buckets. Since its terrain, if its a grid all verts will share an x and y with several other verts. Make an array that holds number of vertex rows/columns. Plop a single vertex pointer into those slots, if a slot is already filled then delete it and connect your edges to the vertex already in the bucket.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!