Enclosing Surfaces for Point Clusters Using 3D Discrete Voronoi Diagrams

Abstract

Point clusters occur in both spatial and non-spatial data. In the former context they may represent segmented particle data, in the latter context they may represent clusters in scatterplots. In order to visualize such point clusters, enclosing surfaces lead to much better comprehension than pure point renderings. We propose a flexible system for the generation of enclosing surfaces for 3D point clusters. We developed a GPUbased 3D discrete Voronoi diagram computation that supports all surface extractions. Our system provides three different types of enclosing surfaces. By generating a discrete distance field to the point cluster and extracting an isosurface from the field, an enclosing surface with any distance to the point cluster can be generated. As a second type of enclosing surfaces, a hull of the point cluster is extracted. The generation of the hull uses a projection of the discrete Voronoi diagram of the point cluster to an isosurface to generate a polygonal surface. Generated hulls of non-convex clusters are also non-convex. The third type of enclosing surfaces can be created by computing a distance field to the hull and extracting an isosurface from the distance field. This method exhibits reduced bumpiness and can extract surfaces arbitrarily close to the point cluster without losing connectedness. We apply our methods to the visualization of multidimensional spatial and non-spatial data. Multidimensional clusters are extracted and projected into a 3D visual space, where the point clusters are visualized. The respective clusters can also be visualized in object space when dealing with multidimensional particle data.