Learning Meshing from Delaunay Triangulation for 3D Shape Representation

Academic Background

Surface reconstruction from point clouds is a long-standing problem in computer vision and graphics. Traditional implicit methods, such as Poisson surface reconstruction, compute an implicit function and extract the surface using the Marching Cubes algorithm. While these methods can generate watertight meshes, they often result in loss of detail and over-smoothing when dealing with complex structures. On the other hand, explicit methods, such as Delaunay triangulation, directly construct meshes by triangulating point sets, which can better preserve sharp features and details. However, inferring triangle connectivity in complex topologies remains challenging.

In recent years, learning-based methods have made significant progress in surface reconstruction tasks. However, existing learning-based explicit methods still face difficulties when dealing with complex structures, especially in inferring local shape connectivity, which often leads to artifacts and non-watertight triangles. To address these issues, this paper proposes a learning-based method based on Delaunay triangulation, aiming to achieve high-precision surface reconstruction.

Source of the Paper

This paper is authored by Chen Zhang and Wenbing Tao from the National Key Laboratory of Science and Technology on Multi-spectral Information Processing at Huazhong University of Science and Technology. The paper was submitted on May 9, 2024, accepted on December 28, 2024, and published in the International Journal of Computer Vision in 2025.

Research Process

1. Overview of the Research Process

This paper proposes a novel learning-based method called Delaunay Meshing Network+ (DMNet+) for surface reconstruction from point clouds. The core idea is to model the Delaunay triangulation as a dual graph and use a Graph Neural Network (GNN) to classify tetrahedrons, thereby achieving high-precision surface reconstruction without relying on visibility information.

2. Detailed Research Process

a) Feature Extraction

1. Point Feature Encoding: First, multi-scale geometric information is extracted from the point cloud. The point feature encoder consists of a global encoder and a local encoder. The global encoder extracts global features through max pooling, while the local encoder aggregates local geometric information using Multi-Layer Perceptrons (MLPs) and a distance-based Gaussian kernel function. Finally, global and local features are fused to form the final feature for each point.

2. Graph Feature Encoding: In the Delaunay triangulation structure, each tetrahedron is treated as a node in the dual graph, and triangles are treated as edges. By calculating the geometric center of each tetrahedron and the offset positions of its vertices relative to the center, point features are organically embedded into the structural representation of the Delaunay triangulation. Through an attention mechanism, the network can adaptively select encoded features, thereby better learning the geometric differences between tetrahedrons inside and outside the surface.

b) Local Graph Iteration Algorithm

To enhance the interaction of neighborhood information between nodes and edges in the dual graph, a Local Graph Iteration (LGI) algorithm is designed. This algorithm iteratively processes one-hop node features using simple attention modules and MLPs, without relying on the global adjacency matrix in Graph Convolutional Networks (GCNs). By introducing edge features, LGI can more effectively aggregate neighborhood information, thereby improving the robustness of classification.

c) Multi-Label Supervision Strategy

Due to the complex spatial relationships between tetrahedrons and the ground truth surface, directly generating ground truth labels for tetrahedrons is challenging. To address this, a multi-label supervision strategy is proposed, where reference locations are randomly sampled within each tetrahedron, and the labels of these locations are used to classify the tetrahedrons. This strategy allows the method to obtain accurate supervision without visibility information.

d) Octree-Based Scaling Strategy

To handle large-scale data, an octree-based scaling strategy is proposed. By dividing the nodes of the Delaunay triangulation into octree leaves and processing tetrahedrons in each leaf in batches, the method can effectively handle millions of points.

3. Main Results

Experimental results show that the proposed DMNet+ method performs well on multiple datasets, especially in handling thin structures and sharp edges, outperforming state-of-the-art methods. Additionally, the method exhibits strong adaptability to point clouds of varying densities, maintaining good reconstruction quality even on sparse data.

a) Detail Reconstruction

Experiments on the ShapeNet dataset show that DMNet+ can preserve rich details, especially when dealing with thin structures and sparse data. Compared to other explicit methods, DMNet+ generates meshes with higher watertightness and fewer artifacts.

b) Adaptability to Data of Varying Densities

When handling sparse data, DMNet+ demonstrates strong adaptability. Even with 1k points, DMNet+ can still generate high-quality reconstruction results, showing its robustness to variations in point density.

c) Edge Reconstruction

Experiments on the FamousThingi dataset show that DMNet+ excels in preserving sharp edges. Compared to other methods, DMNet+ generates meshes with higher edge sharpness, demonstrating its strong generalization ability for complex shapes.

d) Noise Robustness

Experiments on noisy data show that DMNet+ has strong robustness to noise. Even with 1% bounding box deviation in high-intensity noise, DMNet+ can still generate high-quality reconstruction results, showing its strong adaptability to noisy data.

4. Conclusion

This paper proposes a novel learning-based method based on Delaunay triangulation for surface reconstruction from point clouds. By modeling the dual graph as a Delaunay triangulation structure and using a GNN to classify tetrahedrons, the method achieves high-precision surface reconstruction without relying on visibility information. Experimental results show that DMNet+ performs well in handling thin structures, sharp edges, and large-scale scanned data, demonstrating its high scientific and application value.

Research Highlights

1. Novel Method: This paper is the first to propose a learning-based surface reconstruction method based on Delaunay triangulation, using a GNN to replace traditional graph cuts and achieve high-precision surface reconstruction.
2. Multi-Scale Geometric Information: By fusing multi-scale geometric information from point clouds and the structural representation of Delaunay triangulation, the method can preserve rich details, especially when handling thin structures and sharp edges.
3. Local Graph Iteration Algorithm: The designed Local Graph Iteration (LGI) algorithm effectively aggregates neighborhood information, enhancing the local processing capability of the dual graph and improving the robustness of classification.
4. Strong Generalization Ability: The method exhibits strong adaptability to point clouds of varying densities, especially performing well on sparse data.
5. Efficient Scalability: Through an octree-based scaling strategy, the method can handle millions of points, demonstrating high computational efficiency.

Research Significance

The proposed DMNet+ method has significant scientific and application value in the fields of computer vision and graphics. It not only achieves high-precision surface reconstruction but also handles large-scale and sparse point cloud data, providing a powerful tool for practical applications. Additionally, the method performs well in handling noisy data and complex topologies, showing its wide application potential in industrial design, virtual reality, and medical imaging.