Half-edge mesh review

role and goal

Blender current mesh format is very simple, and dont allow easily advanced tools. If face and edge modes were added recently, internally the format makes coding complex. Also this format can only fake faces with more than 4 vertexs (ngons).

Joeedh propose to use a new mesh based on half-edge.

the half-edge data structure is an elvolved Brep structure which has the following characteristic :

store topological informations of the mesh (neighbouring)
provide fixed time (and fast) access to this information
allow traversals and queries. Many advanced algorithms are described for decimation, feature preserving smoothing, remeshing and others cool stuff
allow ngons.
clear definition of outside/inside regions, thanks to the orientation.
most of the operations on mesh can be expressed as combination of Euler operators which guarantee fitness of operations

Of those features, the ngons one, if the reason why this was proposed, is not the most important. Traversals, in particular, will allow the creation of tools which are not possible currently, or very clumsy (edge loops for example are a breeze).

The drawback of this structure is that it implies restriction on the topology of the mesh. The most basic one support only single shell, single component closed 2-manifold of genus 0 (topologicaly a sphere), but many extensions exist, relaxing the restrictions (the only one to always stay is the 2 manifold one).

These extensions means changes in both the structure and the internals used. It is so very important to define from the start what will and will not be supported and stick to it. The limit conditions must also be checked against other part of blender like the renderer and the mapping stuff. Faces in particular should be kept convex to avoid preview or renderer error.

common kinds of half-edges -- what is possible

basic HE
HE with single outer boundary
HE with inner boundaries
HE of any genus
holes in faces
faces in faces
multiples shells, multiples components
exceptional vertexs (eg 2 pyramids joined by the point, handling change if hole in faces or not) *reflexive half edges ( edge with same face on each side, ie tube with one seam) ? * tube with no seam ( from a topological point of view, if open at each end, it is the same as a face with hole, but change the requirements on structs if not)
degenerates cases (eg edge with no face, isolated vertices)

(the 2 marked ' would cause problems to other parts of blender i think)

The 4 first ones are pretty straightforward, complexities begin with the rest.

Multiples shells (completly separates parts) are easy too and needed.

multiples components means we have one of the following situations :

exceptional vertex (2 pyramids or more joined at the point)
halfedge(s) with no corresponding faces linking 2 valids shells
self intersecting projection along the normal faces, so not convex.

Only the first one should be supported and that can be faked by replacing the vertex with a tiny triangle (it can be even a virtual one, more on that later), or simply having 2 different vertex with or without a link.

Non supporting the second case avoid also to have to support degenerate cases. One half edge or its pair must link to a face. The minimal HE mesh is then a triangle. Only bridge tool allowed is also face(s) one in this case

holes in faces and faces in faces are not really needed, you can alway cut the face in 2 and solve the problem. If theses exensions are quite powerfull, the changes on the structures are importants

btw, a boundary can be always seen as a special void face (with no restriction on its shape). This can simplify handling by making things homegeneous, but has some drawbacks too. others solutions use flags to mark boundary half-edges. Choice to make here.

To summarize, for a simple handling we can go for a multiple shell, single component open or closed mesh of any genus. Exceptionals vertex will be splitted to be in multiple shell case. this has limited drawbacks and can handle nicely almost all cases.

How we handle the boundaries is up to the coder (but i advise to avoid fake void faces). we will see possible solutions. My preference goes to always generate the 2 half-edges with NULL pointers to missing faces, hop pointers allowing to go past boundaries.

Validation criterias

half-edges have coherent orientation

all variants applicable to our case verify the following Euler Formula for each shell :

     V - E + F= 2 (C - G) - B
     V : number of vertex     E : number of edges     F : number of faces     
     C : number of connected components, C = 1 constant     G : genus of the mesh     
     B : number of boundary loops
     rewrite without C :
     V - E + F + B = 2 - 2g
     the euler formula dont change when an euler operator is applied to the mesh.      
     Only operations that change genus need to be validated again.

each face boundary is a simple loop, face is (reasonably) convex and flat

no reflexive face, no edge without face on at least one side

one pair of vertices can have at most one half-edge and its pair

Datas structures

base half-edge structs are as follow (refer to http://www.flipcode.com/articles/article_halfedge.shtml) :

struct HE_edge { 
     HE_vert* vert;   // vertex at the end of the half-edge 
     HE_edge* pair;   // oppositely oriented adjacent half-edge
     HE_face* face;   // face the half-edge borders 
     HE_edge* next;   // next half-edge around the face    
};

struct HE_vert { 
     float x; float y; float z;
     HE_edge* edge;  // one of the half-edges emantating from the vertex  
};  

struct HE_face { 
     HE_edge* edge;  // one of the half-edges bordering the face \
};

These structs are enough to do any query needed or access all information needed. They rely on the fact the validations criterias are met.

datas structures (relevant bits only) proposed by Joeedh outside edit mode :

typedef struct HE_Vert { 
     float co[3]; 
     float no[3]; 
     int edge;
} HE_Vert;

typedef struct HE_EdgeInfo { 
     unsigned int f, h; 
     float crease; 
     int e1, e2; 
     int v1, v2; 
     char seam, cpad1; 
     short spad2;
} HE_EdgeInfo;

typedef struct HE_Edge { 
     int v1, v2, iedge, pair, face, next, prev; 
} HE_Edge;

typedef struct HE_Face { 
     int edge; 
     float nor[3]; 
     float dot[3];
} HE_Face;   

typedef struct HE_Mesh { 
     ID id; 
     HE_Face *faces; 
     int totfaces; 
     HE_Edge *half_edges; 
     HE_EdgeInfo *iedges;
     HE_Vert *verts;
     int totedges;
     int totiedges;
     int totverts;
} HE_Mesh;

We remark that the pointers have been replaced by array indexes. Althought this is an efficiency loss, the SDNA requirements and the similarities with the standard mesh structures make this a correct design choice as these dont elvove once allocated. the loss in this mode is bearable as, if as it should be, things are allocated in order, access is possible by the_array[index]

HE_Vert, HE_Mesh, HE_Face dont call for particular comments.

an equivalent to the TFace structure is missing and there is changes to the edges structures

HE_Edge :

V1 is unneeded : V1 = HE_Vert[(HE_Edge[pair])->[V2]]

Of course this is much more efficient wih pointers, but keeping duplicated datas increase housekeeping complexity and risks

Prev is needed only in some cases for dealing with boundaries and not the best solution imho. hop pointers (or indexes) is more general when you have to deal with eg grid like missing faces cases. in the case there is no voids or they are specially marked faces you can cycle around vertex to find prev. As the number of incident edges to a vertex is low, this is not a problem.

HE_EdgeInfo hold mostly redundant info or things that should be in edge.

for dealing neatly with multiples shells, an index is missing, as well as a struct pointing to one halfedge of each shell (to be blender style, that could be a BLI_List). Also storing the calculated genus of each shell would be handy

All in all this is acceptable design, but HE_EdgeInfo must be imho phased out.

however in drawing code we find things like :

mef = &me->faces[i]; this should be simply by pointer arithmetic

mef = (me->faces) + i or using directly pointers

still not very big deal.

in drawing code too, no provision is made to mark edges, so each will be drawn twice

Editmode structures

typedef struct HE_EditVert { 
     Link link;
     float co[3], ssco[3]; /*subsurf coordinates*/ 
     float no[3]; 
     struct HE_EditEdge *edge;
     struct HE_EditVert *newvert; /*this next one is ONLY for edge lookup!  Trust me, maintaining adjacency info like this is not necassary and very slow*/ 
     ListBase hashedges; /*linked list of hash_references*/
} HE_EditVert;

typedef struct HE_Ref { 
     Link link;
     void *ref;
} HE_Ref;

typedef struct HE_EditEdge { 
     Link link;
     char fast;
     struct HE_EditEdge *pair;
     struct HE_EditVert '''v1, '''v2;
     struct HE_EditFace *face;
     struct HE_EditEdge '''enext, '''eprev;
     struct HE_EditEdgeInfo *ieed; /** half-edges are invisible to the user, as such they have no "offical' flags (e.g. a ->f member).*/ 
     unsigned int f1, f2, f3, freed;
     short uv[2];
} HE_EditEdge;

typedef struct HE_HashEdge { 
     Link link;
     struct HE_EditEdge *eed;
     char fast; //struct HE_EditVert *eve;
} HE_HashEdge;

typedef struct HE_EditEdgeInfo { 
     Link link;
     unsigned int f, f1, f2, h;
     char seam, fast, hl; /*mouseover highligt*/
     float crease;
     HE_EditEdge '''e1, '''e2;
     unsigned int glname;
} HE_EditEdgeInfo; 

typedef struct HE_EditFace {
     Link link;
     struct HE_EditEdge *edge;
     float nor[3];
     float cent[3];
} HE_EditFace;   

typedef struct HE_EditMesh {
     ListBase faces; 
     ListBase edges; 
     ListBase verts; 
     ListBase einfo; 
     ListBase draw_edges; 
} HE_EditMesh;

Structs closer to the base ones here, only remark, why use link struct, next, prev directly in struct is nicer imho in such struct

some notes :
the hashedge which are a direct copy ot the original mesh ones should be phased out, for an half-edge based version
with the correct traversals defined, there is no need to use ListBase of faces and vertex, all access can and should be done via half-edges. this will be as fast, and you get the benefit of possibles adjacency optimisations
for half-edges a listBase can be handy, but a struct pointing to one half-edge of each shell is enough. same remark for HE_EditEdgeInfo than previously

code

no real traversals defined, what is used is list structs similar to those in blender mesh. This is rather unwise as we dont profit of the topology info stored in the halfedges (there is many variants available of flood or moving boundary algorithms to choose from. take one and define its variant for vertices, faces and edges)
this also mean we cannot use any of the hundred advanced algorithm availables to do cool stuff. they all rely on traversals.
triangulation code (for render) should use Delaunay triangulation, as well as its criteria to choose from the 2 possibles ones of a quad (or you could get rendering artifacts)
validation code need to be improved and made differently
all tools assume a single boundary around verts (rewind with the prev pointer), this will break in a checker like missing faces pattern.
there is a lot of temp allocated inside functions. that does not seem smart. If scratch area is needed, allocate it ouside of any function and reuse it when needed. Allocations are always one of the slowest things and should be reduced to the minimum
there is stack allocated arrays of 6000 verts pointers in almost all tools. That is silly !
validation is not insured everywhere
cleaning urgently needed

design

One of the nice properties of half-edge structure is that, as long genus and number of shell dont change, it is possible to define operators that guarantee that structure integrity is preserved. All operations can be defined as combination of these base operators (the most commons are split/merge edge split/merge vertice extrude edge ). it is imho mandatory to proceed this way
other tools (eg bridge) need a full validation of the mesh, before and after.
the limit conditions must be defined and enforced (degenerates cases). This is incompletly done actually.
the set of tools defined should be equivalent to the ones in normal mesh. It is bad design to tie closely other subprojects (tool recording, construction history, mouseover) to this mesh type, especially when important stuff (UV, orco) dont work. if those subprojects are to be used, they must be everywhere and are parts of a separate project. provision for future support in HMesh can be done, but not entangled like this.
naming conventions are rather strange. comments in the code are more reminder for the coder than real explanation

test and conclusion

I've experimented some crash on test cases (likeky due to illegal operations).

A lot of work is needed to redesign the operations to enforce correctness. cleaning base code too

Works however rather correctly, but some slowdown experimented on mesh bigger than 1k

All in all, this is rather acceptable once the validations problem is solved -- DeveloperWikiJLucPeuriere - 20 Mar 2005

Dev:Source/Modeling/HeMesh/Review

目次