Page 1 of 2

How Does Current Half-Edge Development Relate to N-Gons?

Posted: Mon Oct 31, 2005 8:59 pm
by brucegregory
The Blender community is so full of buzz-words . . . like "half-edge" mesh editing. Great communication tools for developers, but they leave the rest of us in the dust. Can someone please comment on what half-edges do, using examples, if possible, for the common Blender user? Will these new "half-edge" developments lead to the implimentation of N-gon mesh editing? Are there some new advantages for the Blender modeler that can be put into use right now?

I think that the only remaining objection to Blender's otherwise excellent set of modeling tools is the way the current knife tool works, (leaving lots of triangles in its wake). Are there new ways of cutting up a mesh that are a result of the new "half-edge" approach being worked on? Which CVS builds contain the tools or keyboard shortcuts that are a direct result of this project?

Lots of questions, but inquiring minds need to know.

Re: How Does Current Half-Edge Development Relate to N-Gons?

Posted: Mon Oct 31, 2005 9:36 pm
by Bellorum
brucegregory wrote:The Blender community is so full of buzz-words . . . like "half-edge" mesh editing. Great communication tools for developers, but they leave the rest of us in the dust. Can someone please comment on what half-edges do, using examples, if possible, for the common Blender user? Will these new "half-edge" developments lead to the implimentation of N-gon mesh editing? Are there some new advantages for the Blender modeler that can be put into use right now?

I think that the only remaining objection to Blender's otherwise excellent set of modeling tools is the way the current knife tool works, (leaving lots of triangles in its wake). Are there new ways of cutting up a mesh that are a result of the new "half-edge" approach being worked on? Which CVS builds contain the tools or keyboard shortcuts that are a direct result of this project?

Lots of questions, but inquiring minds need to know.
Half-edge would allow for N-gons. In fact there already is an implementation of it in Tuhopuu, coded by Joeedh. However, he seems to have falled of the face of earth. :( And since Tuhopuu is now practically dead, hope is diminishing at a rapid rate.

Posted: Tue Nov 01, 2005 2:23 pm
by nemyax
The half-edge structure is similar to Maya's polygons and Max's editable poly.

Posted: Tue Nov 01, 2005 4:27 pm
by eric.m.forsythe
The Blender community is so full of buzz-words . . . like "half-edge" mesh editing. Great communication tools for developers, but they leave the rest of us in the dust.
It's good that you speak up and ask questions. Here's my two cents, but not a complete explanation...

A half-edge data structure is just a different way to store mesh information. As a user, you know that polygon meshes are typically composed vertices, which are combined to make edges, which are combined to make faces. The half-edge stores in the mesh data in a way that allows the developers easy access to the mesh's local structure. Say, a developer needs the answer to one of these questions:

Which vertices are use to make this edge?
Which face(s) use this edge?
Which face(s) are adjacent to this face?

The half-edge data structure answers these questions and a whole lot more.

Put a less technical way, imagine that you are walking on surface of your favorite mesh. You walk up and stand on a vertex. The half-edge data structure allows you to see the area around you. Which edges are connected to the vertex that you are standing on; which faces are around you; and other information. It's like you are holding a candle that illuminates the immediate area. Not using a half-edge data structure can be like walking around in the dark. You can see the vertex that you are standing on, but that might be it (depending on the data structure you are using).

Now image that you have a knife that you are going to use to cut an edge on your favorite mesh. Even without the candle, you might be able to get down on your hands and knees and feel around to find the edge that you want cut, but the candle makes the task a lot easier and faster.

The point is that the half-edge structure makes life easier for developers in some cases. You can still perform most of the same tasks even if you don't have it, but it's going to be harder and it's going to take more time.

Posted: Tue Nov 01, 2005 4:32 pm
by nemyax
It's supposed to be an implementation of the winged edge data structure.
http://www.cs.mtu.edu/~shene/COURSES/cs ... ged-e.html

Posted: Tue Nov 01, 2005 7:56 pm
by lukep
nemyax wrote:It's supposed to be an implementation of the winged edge data structure.
http://www.cs.mtu.edu/~shene/COURSES/cs ... ged-e.html
hmm no.

half-edge is different from winged edge. both provides topology info

Posted: Tue Nov 01, 2005 8:41 pm
by nemyax
Thanks for correcting me. I'd thought they were similar from the start.
How exactly are they different?

Posted: Tue Nov 01, 2005 9:53 pm
by lukep
nemyax wrote:Thanks for correcting me. I'd thought they were similar from the start.
How exactly are they different?
In short (but somehow innacurate way), half-edge is a winged-edge cut in 2 (hence the name). an half-edge and its pair contains same info as a winged edge

the long answer is a bit more complex as extension to the 2 models make them differ a lot afterwards.

Half-edge is a bit more modern and allow more, but needs more careful house-keeping

Posted: Tue Nov 01, 2005 10:54 pm
by Bellorum
So... does anyone know what happened to Joeedh?

Posted: Tue Nov 01, 2005 10:59 pm
by brucegregory
Well, to restate my question: Since the half-edge structure has been implimented, will N-gons be adopted by Blender soon? Will a new knife tool be developed that can cut both edges and inside faces and connect vertices, leaving no unwanted triangle geometry. . . soon?

F-gons are an improvement, for the simple fact that they keep the clutter down. One area where F-gons fail, is when one attempts to extrude an F-gon, (conglomeration of faces) . . . you still need to go through the little "region or individual faces" dialog for each and every extrusion . . . too many steps. Now that we have the incredible "Cntrl-left-click" instant extrusion parallel to the view plane, having to revert to the old dialog method of extruding is tortuous, (torturous?).

The root of the resistance toward N-gons, I think, comes mainly from the modeling purist camp - those who prefer to model polygon by polygon. I simply do not think that this method of modeling is the fastest and most efficient. Box modeling, seems to run circles around poly-by-poly, from a speed standpoint, anyway; and a growing majority of modelers prefer box modeling methodologies. Hence many of the recent poly modeling improvements and edge tools in Blender. I'm sure some of the resistance also comes from those who have to write the code.

The lack of the N-gon and the true knife surely represent the last set of excuses for not using Blender for all aspects of 3D animation production. Why don't we go ahead and jump this hurdle. Make Blender Universal!

Sincerely,

Greg Smith

Posted: Tue Nov 01, 2005 11:51 pm
by LetterRip
joeedh is extremely busy with school, I emailed with him about 2-3 weeks ago.

So he has no time right now to work on hemesh,

LetterRip

Posted: Thu Nov 03, 2005 3:35 am
by ysvry
i was looking forward to he mesches too as i used too model in wings wich is halfedged too. I hope he will continue working on it.

Posted: Sat Nov 26, 2005 12:22 pm
by Sonic TH
I agree, blender's lack of N-gons is really holding it back. Without N-Gons and an improved shader system blender will be behind the curve no matter how great it is otherwise. I hope HE-mesh doesn't fall by the wayside, it'd be a great loss and I doubt anyone else is gonna pick up the torch and carry it forward. At least not in the near future.

Posted: Sun Nov 27, 2005 5:59 pm
by softwork
The root of the resistance toward N-gons, I think, comes mainly from the modeling purist camp - those who prefer to model polygon by polygon. I simply do not think that this method of modeling is the fastest and most efficient. Box modeling, seems to run circles around poly-by-poly, from a speed standpoint, anyway; and a growing majority of modelers prefer box modeling methodologies. Hence many of the recent poly modeling improvements and edge tools in Blender. I'm sure some of the resistance also comes from those who have to write the code.
and I doubt anyone else is gonna pick up the torch and carry it forward
Thanks for voluntering and implementing this great feature in the next (2.41) release. Can't wait to use it.....

Posted: Sun Nov 27, 2005 9:17 pm
by LetterRip
it isn't so much resistance as it is that it would require quite a bit of time and work to redo all of blenders internal code to use ngons.

I think it well might end up being easier/better use of time to extend blender current code to better fake ngons (ie allow internal verts and edges, and possibly allow holes) than it would be to recode to use 'real ngons'.
you still need to go through the little "region or individual faces" dialog for each and every extrusion . . . too many steps. Now that we have the incredible "Cntrl-left-click" instant extrusion parallel to the view plane, having to revert to the old dialog method of extruding is tortuous, (torturous?).
I filed a bug report on a single fgon asking if extrude region or individual faces.

LetterRip