[Bf-committers] IRC meeting minutes, may 16, 2004
Jean-Luc Peurière
bf-committers@blender.org
Wed, 19 May 2004 01:51:24 +0200
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