Efficient Representation and Extraction of 2-Manifold Isosurfaces Using kd-Trees

In proceedings of The 11th Pacific Conference on Computer Graphics and Applications (PG '03), pages 364-376, IEEE Computer Society, Oct. 2003
Presented at The 11th Pacific Conference on Computer Graphics and Applications (PG '03)
 

Abstract

In this paper, we propose the utilization of a kd-tree based hierarchy as an implicit object representation. Compared to an octree, the kd-tree based hierarchy is superior in terms of adaptation to the object surface. In consequence, we obtain considerably more compact implicit representations especially in case of thin object structures. We describe a new isosurface extraction algorithm for this kind of implicit representation. In contrast to related algorithms for octrees, it generates 2-manifold meshes even for kd-trees with cells containing multiple surface components. The algorithm retains all the good properties of the Dual Contouring approach by Ju et al. [ACM Trans. Graphics 21 (2002) 339-346] like feature preservation, computational efficiency, etc. In addition, we present a simplification framework for the surfaces represented by the kd-tree based on quadric error metrics. We adapt this framework to quantify the influence of topological changes, thereby allowing controlled topological simplification of the object. The advantages of the new algorithm are demonstrated by several examples.

Keywords: Hierarchical Structures, Isosurfaces, Mesh Generation, Topological Simplification

Note: An extended version of this paper, published in the Graphical Models journal, is also available.

Images

Download Paper

Download Paper

Bibtex

@INPROCEEDINGS{gress-2003-efficient,
      author = {Gre{\ss}, Alexander and Klein, Reinhard},
       pages = {364--376},
       title = {Efficient Representation and Extraction of 2-Manifold Isosurfaces Using kd-Trees},
   booktitle = {The 11th Pacific Conference on Computer Graphics and Applications (PG '03)},
        year = {2003},
       month = oct,
   publisher = {IEEE Computer Society},
    keywords = {Hierarchical Structures, Isosurfaces, Mesh Generation, Topological Simplification},
    abstract = {In this paper, we propose the utilization of a kd-tree based hierarchy as an implicit object
                representation. Compared to an octree, the kd-tree based hierarchy is superior in terms of
                adaptation to the object surface. In consequence, we obtain considerably more compact implicit
                representations especially in case of thin object structures. We describe a new isosurface
                extraction algorithm for this kind of implicit representation. In contrast to related algorithms for
                octrees, it generates 2-manifold meshes even for kd-trees with cells containing multiple surface
                components. The algorithm retains all the good properties of the Dual Contouring approach by Ju et
                al. [ACM Trans. Graphics 21 (2002) 339-346] like feature preservation, computational efficiency,
                etc. In addition, we present a simplification framework for the surfaces represented by the kd-tree
                based on quadric error metrics. We adapt this framework to quantify the influence of topological
                changes, thereby allowing controlled topological simplification of the object. The advantages of the
                new algorithm are demonstrated by several examples.},
        isbn = {0-7695-2028-6},
  conference = {The 11th Pacific Conference on Computer Graphics and Applications (PG '03)}
}