Volume-Surface Trees

Computer Graphics Forum (Proceedings of EUROGRAPHICS 2006), Volume 25, Number 3, page 399--406 - 2006
Download the publication : VSTree.pdf [9.8Mo]   VS-Trees - Eurographics 2006.ppt [4.6Mo]  
Many algorithms in computer graphics improve their efficiency by using Hierarchical Space Subdivision Schemes (HS^3), such as octrees, kD-trees or BSP trees. Such HS^3 usually provide an axis-aligned subdivision of the 3D space embedding a scene or an object. However, the purely volume-based behavior of these schemes often leads to strongly imbalanced clustering. In this article, we introduce the VS-Tree, an alternative HS^3 providing efficient and accurate surface-based hierarchical clustering via a combination of a global 3D decomposition at coarse subdivision levels, and a local 2D decomposition at fine levels near the surface. First, we show how to efficiently construct VS-Trees over meshes and point-based surfaces, and analyze the improvement it offers for cluster-based surface simplification methods. Then we propose a new surface reconstruction algorithm based on the volume-surface classification of the VS-Tree. This new algorithm is faster than state-of-the-art reconstruction methods and provides a final semi-regular mesh comparable to the output of remeshing algorithms.

2 Awards:
  • Gunter Enderle Award for the Best Paper
  • Best Student Paper Award

Images and movies

 

BibTex references

@Article{BHGS06,
  author       = "Boubekeur, Tamy and Heidrich, Wolfgang and Granier, Xavier and Schlick, Christophe",
  title        = "Volume-Surface Trees",
  journal      = "Computer Graphics Forum (Proceedings of EUROGRAPHICS 2006)",
  number       = "3",
  volume       = "25",
  pages        = "399--406",
  year         = "2006",
  keywords     = "Hierarchical Space Subdivision Data-Structure, Clustering, Simplification, Reconstruction",
  url          = "http://iparla.labri.fr/publications/2006/BHGS06"
}

Other publications in the database