Extension of half-edges for the representation of multiresolution subdivision surfaces

We address in this paper the problem of the data structures used for the representation and the manipulation of multiresolution subdivision surfaces. The classically used data structures are based on quadtrees, straightforwardly derived from the nested hierarchy of faces generated by the subdivision schemes. Nevertheless, these structures have some drawbacks: specificity to the kind of mesh (triangle or quad); the time complexity of neighborhood queries is not optimal; topological cracks are created in the mesh in the adaptive subdivision case.

We present in this paper a new topological model for encoding multiresolution subdivision surfaces. This model is an extension to the well-known half-edge data structure. It allows instant and efficient navigation at any resolution level of the mesh. Its generality allows the support of many subdivision schemes including primal and dual schemes. Moreover, subdividing the mesh adaptively does not create topological cracks in the mesh. The extension proposed here is formalized in the combinatorial maps framework. This allows us to give a very general formulation of our extension.

P. Kraemer , D. Cazier , D. Bechmann

Visual Computer , Volume 25 , Number 2 , page 149--163 - 2009

@Article{2-KCB09,
 author = {Kraemer, P. and Cazier, D. and Bechmann, D.},
 title = {Extension of half-edges for the representation of multiresolution subdivision surfaces},
 journal = {Visual Computer},
 number = {2},
 volume = {25},
 pages = {149--163},
 year = {2009},
 publisher = {Springer},
 keywords = {geometric modeling, topological model, combinatorial maps, multiresolution meshes, subdivision surfaces},
 doi = {10.1007/s00371-008-0211-6},
 x-international-audience = {Yes},
 x-language = {EN},
 url = {http://publis.icube.unistra.fr/2-KCB09}
}