Jump to content
  • Advertisement
Sign in to follow this  
swiftcoder

Vertex welding, preserve creases?

This topic is 945 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

I have 'triangle soup' (output of a marching cubes-like algorithm), from which I need remove duplicate vertices and emit indexed triangle lists (aka 'vertex welding'). I currently do this by scanning the vertex list using a hashmap to de-duplicate vertex positions, which is pretty effective.

 

However, normals are currently calculated after this step, which results in smoothing out all the hard edges in the mesh. I could associate face normals with vertices before the welding process, and key the hashmap on (vertex, normal), but then I will get facets instead...

 

Anyone have an algorithm for de-duping vertices with similar normals, while retaining duplicate vertices on crease edges?

Share this post


Link to post
Share on other sites
Advertisement

I'd use a hashmultimap keyed on vertex position and check the precomputed normals' dot product with some threshold to decide if merging is performed or not. Unless you have a degenerate case like a cone where a single vertex exists hundreds of times with wildly different normals this should be fine.

Edited by l0calh05t

Share this post


Link to post
Share on other sites
Is something like Beldner’s edge-split what you’re looking for? I believe the algorithm goes something like:

1. Iterate over all edges.
2. Check angle between the triangles sharing this edge.
3. If the angle is above a certain threshold, then crease this edge by creating new vertices with different normals.

Share this post


Link to post
Share on other sites

Is something like Blender’s edge-split what you’re looking for? I believe the algorithm goes something like:

Yes, something like that. That algorithm you describe is about what I'd reasoned my way to, but it's going to require keeping track of a whole lot more state than I do at the moment (which isn't all that surprising, I guess).

For reference, the method I have been using for welding hitherto looks like this:

void calculateIndices(std::vector<vector3> &vertices, std::vector<unsigned short> &indices) {
   std::unordered_map<vector3, unsigned short> uniques;
   std::vector<vector3> newVertices;

   for (auto v : vertices) {
      if (uniques.find(v) == uniques.end()) {
         uniques[v] = newVertices.size();
         newVertices.push_back(v);
      }
      indices.push_back(uniques[v]);
   }

   vertices.swap(newVertices);
}
Edited by swiftcoder

Share this post


Link to post
Share on other sites

Ugh. I need full mesh connectivity information to accomplish this, don't I? That's unfortunate.

 

I think the algorithm looks something like this:

1. Iterate over all faces, outputting a list of faces, with pointers to their edges (should be a linear scan, if one uses a hashtable to store edges).

2. iterate over all edges, duplicating if the dot product between the faces that share it exceeds a 'crease' constant.

3. Iterate over the faces again, emitting indices for each face.

 

That seem right?

 

Edit: Grr. Not right. You actually have to do duplication at the individual vertex level, based on the crease value of each connected edge. Otherwise you can needlessly create additional duplicates of vertices with more than one creased edge...

Edited by swiftcoder

Share this post


Link to post
Share on other sites

Can you:

 - Iterate over all faces and generate the normals for each vertex, add them to your hash map

 - Begin the de-duping process you were originally using, but if the normals of the vertices are too extreme, create a new vertex?

void calculateIndices(std::vector<Vertex> &vertices, std::vector<unsigned short> &indices) {
   std::unordered_map<Vertex, unsigned short> uniques;
   std::vector<Vertex> newVertices;

   for (auto v : vertices) {
      iter uniqueIt = uniques.find(v);
      if (uniqueIt == uniques.end()
      || normals_too_extreme(newVertices[*uniqueIt].normal, v.normal)) {
         uniques[v] = newVertices.size();
         newVertices.push_back(v);
      }
      else
      {
          unsigned short index = *uniqueIt;
          newVertices[index].normal = blendNormal(newVertices[index].normal, v.normal);
      }
      
      indices.push_back(uniques[v]);
   }

   vertices.swap(newVertices);
}

[Edit:] Bah, this is basically what localhost said. Also: You'd need a multimap.

Edited by Servant of the Lord

Share this post


Link to post
Share on other sites
I think I've been reasoning about this wrong: edges don't form creases by themselves, they form creases because vertices form "angles" (for lack of a better term). I'm not sure if I can operate just at the vertex level, or if I have to handle both vertices and edges.

On the other hand, maybe I'm overthinking this altogether. Maybe the multimap solution is sufficient. However, I don't think I can classify whether or not the normal is extreme without topology information. Hmm. Maybe just sum the dot products as I'm calculating the normals? Edited by swiftcoder

Share this post


Link to post
Share on other sites

Don't quote me on this, But I think the common method is to have edges marked for creases, which will be interperted later.

 

For vertex welding, it usually means that some triangle with an area of zero will be destroyed, but it either leaves behind one of it's edges, or the edge can relay information to the remaining vertexes.

 

Remember that a collapsed triangle of area zero will always leave behind two of it's vertices.

 

So with that in mind, it's legal to transfer information to remaining edges of the triangle. Now to calculate the normals.

A face's normal is typically computed from the average of the vertex normals. If a vertex's normals are dependent on the connections to other faces, then we can assume that if we seperate the traingles at the marked creases, it should theoretically keep similar normals to the crased. The biggest problem Is I'm not sure how smooth it'd be.

Edited by Tangletail

Share this post


Link to post
Share on other sites

Don't quote me on this, But I think the common method is to have edges marked for creases, which will be interperted later.

That makes sense, but unfortunately, I'm doing isosurface extraction, so all I have is triangle soup (i.e. no artist intervention to mark creases).

It looks like I'm going to need to:
1. Build the full mesh topology.
2. Classify creased edges based on face normals.
3. For each vertex iterate through the incoming edges in counterclockwise order, emitting a new vertex every time I encounter a creased edge.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!