Archived

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

half-edge datastructure

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

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 on other sites
http://www.flipcode.com/tutorials/tut_halfedge.shtml

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 on other sites
thx

so this is right?

www.cgcube.de/forum/halfedge2.jpg

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 on other sites
thx very much technobot

I think I will use opengls polygon tesselation.....haven''t tryed it yet but I think it''s made for such things?

1. 1
Rutin
70
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• Forum Statistics

• Total Topics
633422
• Total Posts
3011800
• Who's Online (See full list)

There are no registered users currently online

×