Introduction
In fields such as computer vision, medical imaging, and physics simulations, data is frequently collected as "point clouds"—unstructured sets of coordinates representing a physical shape. Converting these raw points into a usable model, such as a 3D mesh, typically requires knowing the topological dimension of the underlying shape.
Most existing reconstruction algorithms are "dimension-specific." For instance, a surface reconstruction tool expects a 2D manifold; providing it with points from a 1D curve often results in unusable artifacts. Real-world datasets are frequently "mixed," containing curves, surfaces, and solids within the same scene. This paper introduces a Voronoi-based algorithm designed to automatically detect the local topological dimension at every sample point, enabling robust shape reconstruction across mixed-dimensional datasets without prior structural knowledge.
Methodology: Voronoi-Based Dimension Detection
The core of the proposed approach leverages the geometric properties of Voronoi Diagrams. For any sample point $p$, its Voronoi cell $V_p$ consists of all points in space closer to $p$ than to any other sample.
Voronoi Subpolytopes and Height Ratios
The authors introduce a recursive method to decompose the Voronoi cell into "subpolytopes" by identifying "poles"—the farthest points within these cells. The "elongation" of a Voronoi cell directly encodes the normal space of the manifold at that point.
By defining "height ratios" ($H_p^i$) for these subpolytopes, the DIMENSION algorithm classifies points:
- 1D (Curve): The Voronoi cell is elongated in two directions (the normal plane).
- 2D (Surface): The cell is elongated in one direction (the surface normal).
- 3D (Solid): The cell is relatively isotropic, with no dominant direction of elongation.
The COCONESHAPE Algorithm
Once dimensions are assigned, the COCONESHAPE algorithm generalizes the "Cocone" surface reconstruction method. It filters $k$-dimensional simplices from a Delaunay triangulation that align with the detected local dimension $k$. This allows for the simultaneous reconstruction of different topological structures within a single dataset.
Sampling Conditions and Insights
A key theoretical contribution is the $(\epsilon, \delta)$-sampling condition. While standard "dense" sampling ($\epsilon$-sampling) is often sufficient for surface reconstruction, it can be ambiguous for dimension detection. For example, points on a surface arranged in tight, isolated clusters might be misidentified as 1D features. The authors introduce a $\delta$ condition to ensure points are not too close to each other, mathematically disambiguating the local dimension.
This approach allows for dimension-independent reconstruction, making the algorithm robust in "non-manifold" cases where different shapes (e.g., a curve meeting a surface) intersect.
Experimental Results
The algorithms were evaluated on various 3D datasets, including homogeneous structures like CURVES (1D) and FOOT (2D), as well as complex mixed-dimension scenes. The "SCENE" dataset (approx. 30,000 points) contained objects of various dimensions, and the algorithm successfully segmented and reconstructed these components simultaneously.
The process is computationally efficient; for the 30k-point SCENE dataset, dimension detection and shape approximation were completed in under seven minutes on a 933 MHz processor. Furthermore, the algorithm showed unexpected robustness at boundaries. Points on the edge of a 2D surface were often classified as 1D, which is topologically accurate as the boundary of a 2D shape is a 1D curve.
Conclusion and Future Directions
The Voronoi-based framework provides a powerful, automated way to handle complex, multi-dimensional point clouds. While highly effective in 3D, future work includes developing a more rigorous theoretical framework for manifolds with boundaries in higher dimensions. Additionally, the authors suggest that the rich geometric information within Voronoi cells could be further exploited to automatically identify sharp features like edges and corners.
Summary updated