Archived

This topic is now archived and is closed to further replies.

half-edge datastructure

This topic is 5041 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 there! I want to implement the half-edge data structure. Now my question is, can you have N-Gons with this data structure? Here my quick painting: www.cgcube.de/forum/halfedge.jpg Maybe somebody has allready implemented this data structure

Share this post


Link to post
Share on other sites
There is no problem with N-gons in half-edge. You are yourself demonstrating rectangles in your image - these are basically N-gons with N=4. The half-edge data structure makes no assumption about whether the faces convex or concave, if that is what got you confused regarding N-gons. To solve the problem presented in our image, simply treat the bottom rectangle as a pentagon - its top edge is actually two edges at a 180 degrees angle.

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

Share this post


Link to post
Share on other sites
Yes, the new image is correct.

As a side note, the situation described in your images is not recommended. Ignoring the half-edge data structure for a second, you have two options there: render the bottom face as a rectangle, or render it as a pentagon. If you render it as a pentagon, it would have a 180 degree corner, which may couse incorrect rendering since the hardware assumes all faces to be convex. If you render it as a rectangle, you''ll get a T-junction, which can also cause visual artifacts (albeit of a different kind). It is customary to subdivide such problematic faces such that you keep the middle vertex and at the same time have only convex faces. Another solution would be to move the middle vertex slightly up, such that the angle there is a bit less than 180 degrees (e.g. 179.5 degrees).

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

Share this post


Link to post
Share on other sites