Mesh Generation for Self-Intersecting Rational Parametric Surfaces

Zheng Zeng, Xiaohong Jia, Mingyang Zhao, Shiqing Xin, Dong‐Ming YanJournal of Computer-Aided Design & Computer Graphics 2023 · DOI

Abstract

When processing self-intersecting surfaces, existing mesh generation methods encounter issues such as lacking intersection representation, large errors, and diminished triangle quality near intersections. In response to these challenges, a novel mesh generation algorithm for self-intersecting rational parametric surfaces is proposed. Firstly, the moving plane method is utilized to calculate the singular factors of the surface. Secondly, the topologically significant points on the intersections are identified by singular factors and the first fundamental form of the surface. Thirdly, a pairing algorithm for mesh vertices on intersections is developed based on the moving plane method to ensure the neighborhood coordination of mesh intersection. The mesh is finally constructed by a particle-based mesh generation method within the parameter domain. Mesh generation tests are conducted on self-intersecting surfaces with different topologies. The proposed algorithm ensures the correctness of mesh intersection topology. Compared to various typical isotropic mesh generation algorithms that do not pair mesh vertices at intersections, the mean value of minimum angles increased 0.6% on average.

Introduction

In fields such as CAD/CAM, 3D printing, and medical imaging, surfaces frequently exhibit self-intersections—complex geometries where a surface passes through itself, like a twisted ribbon or a knot. Generating high-quality triangular meshes for these surfaces is a significant challenge. Traditional algorithms often suffer from topological errors, such as missing intersection lines or creating gaps and overlaps. Furthermore, numerical methods frequently fail to precisely locate geometric features like pinch points or cusps, leading to poor mesh quality near intersections. These "sliver" triangles can cause instability in downstream engineering simulations like Finite Element Analysis (FEA).

Methodology

The proposed algorithm addresses these issues through a multi-step pipeline that integrates symbolic-numeric techniques with physical optimization.

Moving Plane Method and Vertex Pairing

The core innovation lies in using the moving plane method to calculate "singular factors." These factors provide implicit equations that precisely define the intersection curves within the 2D parameter domain. By analyzing the First Fundamental Form of the surface, the algorithm identifies topologically significant "non-regular points" (e.g., pinch points) where the surface normal is undefined.

A critical challenge in self-intersecting surfaces is that a single point in 3D space corresponds to multiple locations in the 2D parameter domain. The authors developed a pairing algorithm using moving planes to ensure that vertices on these disparate branches are perfectly aligned. This alignment is crucial for preventing topological gaps in the final 3D mesh.

Mapping between the 2D parameter domain (a) and the resulting 3D bi-quadratic surface (b), highlighting the correspondence of intersection points.

Particle-Based Mesh Generation

To populate the surface with triangles, a physics-inspired particle-based method is employed. Particles, representing mesh vertices, are distributed in the parameter domain and subjected to mutual repulsion forces to achieve an optimal distribution. This process is enhanced by incorporating the Jacobian matrix, allowing the 2D optimization to account for the 3D curvature and stretching of the surface. This ensures that the resulting 3D triangles are uniform and high-quality.

The resulting mesh distribution within the parameter domain after particle-based optimization.

Experimental Results

The algorithm was rigorously tested on various mathematically complex surfaces, including Enneper, Rational, Bi-quadric, and Bézier surfaces. It was compared against established methods such as Mesh Optimization (MO), Anisotropic Centroidal Voronoi Diagrams (ACVD), and Variational Anisotropic Surface Meshing (VASM).

Key findings include:

  • Topological Correctness: The method consistently produced gap-free intersections, a feat not achieved by the baseline algorithms.
  • Geometric Accuracy: The algorithm demonstrated lower Hausdorff distances (a measure of geometric deviation) compared to MO and ACVD.
  • Improved Mesh Quality: The mean value of minimum triangle angles increased by an average of 0.6%. While seemingly small, this improvement significantly enhances the stability of numerical simulations.

Conclusion

This research presents a robust framework for meshing self-intersecting rational parametric surfaces. By combining symbolic moving planes for topological anchoring with particle-based optimization for geometric regularity, the method achieves superior results in both accuracy and mesh quality. Future work will focus on extending this approach to NURBS surfaces and leveraging GPU parallelization to improve computational efficiency for high-density meshes.

Summary updated

Abstract

<p indent="0mm">When processing self-intersecting surfaces, existing mesh generation methods encounter issues such as lacking intersection representation, large errors, and diminished triangle quality near intersections. In response to these challenges, a novel mesh generation algorithm for self-intersecting rational parametric surfaces is proposed. Firstly, the moving plane method is utilized to calculate the singular factors of the surface. Secondly, the topologically significant points on the intersections is identified by singular factors and the first fundamental form of the surface. Thirdly, a pairing algorithm for mesh vertices on intersections is developed based on the moving plane method to ensure the neighborhood coordination of mesh intersection. The mesh is finally constructed by a particle-based mesh generation method within the parameter domain. Mesh generation tests are conducted on self-intersecting surfaces with different topologies. The proposed algorithm ensures the correctness of mesh intersection topology. Compared to various typical isotropic mesh generation algorithms that do not pair mesh vertices at intersections, the mean value of minimum angles increased 0.6% on average.
BibTeX
@article{zeng2023mesh,
  author = {Zheng Zeng and Xiaohong Jia and Mingyang Zhao and Shiqing Xin and Dong‐Ming Yan},
  title = {{Mesh Generation for Self-Intersecting Rational Parametric Surfaces}},
  journal = {Journal of Computer-Aided Design \& Computer Graphics},
  year = {2023},
  doi = {10.3724/sp.j.1089.2023.2023-00006},
}
Figure