[Bf-committers] IRC meeting minutes, may 16, 2004

[Jean-Luc Peurière]

Le 18 mai 04, à 16:18, Ton Roosendaal a écrit :

> - The SubSurf creases patch still needs revision on 'correctness' or =

> compatibility with standards for creasing. Also issue is finding good =

> method to expand Blender meshes with edge info.
>

I discussed with Ton  about this a bit in IRC, pointing to the fact 
that real edge support more largely in blender data structures would be 
very useful for many purposes :

- creasing subsurfaces
- edge edit mode
- more efficient versions of many edit modes functions especially those 
needing to take in account neighbouround
- automatic charting for LCSM UV and other uses
- traversal operations like curvature smoothing or fairing
- remeshing
- discrete trim surfaces (bevel which not modify original mesh) which 
can operate on a per edge basis
- multi-leve and hierarchical subsurfaces

Not all of this is needed at once, but each need edge support or are 
easier with it. True edge support would also avoid the dichotomy 
mesh/edit mesh when complete.

Now, I'm aware of 3(not including variations) fast and efficient 
datastructures supporting edges :

- the infamous winged edges is the oldest and best known.
    this data structure has some serious drawbacks,  it is really fitted 
for 2-manifold jointed, oriented & closed surfaces which is a rather 
strict subset, and worse storing orientation data is a bit cumbersome.  
Traversal is not really efficient too as there is a test to do for each 
face. Most functions being also best executed as euler operators 
combinations, n-gons support is more or less mandatory (at least 5-gons 
during integrity ops, this can be faked, but is an hassle).

- By cutting a winged edge in 2, we obtain an halfedge. This structure 
solves most of the winged edges problem by supressing the orientation 
problem at the cost of 2 pointers (each halfedges point to its 
reverse). Traversal is more efficient. n-gons support is not needed 
either. Even if the basic halfedge support the same subset as winged 
edge, it can easily expanded to support open surfaces and inner 
boundaries. Supporting non 2-manifold or disjointed is a bit harder but 
doable at a reasonable cost.

- Quad-edge data structure is IMHO too specialized in its use, and 
although very storage space efficient not really usable for us (it 
would force to redefine completly the MFace structure).

google "Designing a Data Structure for Polyhedral Surfaces/Lutz 
Kettner" for a more in-depth comparison of these structures (the author 
wrote the CGAL library).

The halfedge struct has a cost of 4 to 10 pointers per edge (fixed but 
depending of what we store) + 1 back pointer per face and eventually 1 
per vertice, which in a time where memory is huge and cheap seems 
reasonable when you see the advantages. For a 100k edge mesh that means 
a little less than 5 Mo of memory in the worse case (the case of 7 
pointers is more likely).

One good point is that it can coexist with the editmesh struct  and be 
used only when needed like UV for example. One other is that it seems 
to be largely used in every recent CG research paper I stumble on, and 
the de-facto standard for the university community.

What do you think of that ?
-- 
Jean-luc