Volume-surface trees

Tamy Boubekeur*, Wolfgang Heidrich, Xavier Granier, Christophe Schlick

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


Many algorithms in computer graphics improve their efficiency by using Hierarchical Space Subdivision Schemes (HS3), such as octrees, kD-trees or BSP trees. Such HS3 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 surface clustering. In this article, we introduce the VS-Tree, an alternative HS3 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.

Original languageEnglish (US)
Pages (from-to)399-406
Number of pages8
JournalComputer Graphics Forum
Issue number3
StatePublished - Sep 2006
Externally publishedYes

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Volume-surface trees'. Together they form a unique fingerprint.

Cite this