Robust tessellation of CAD models without self-intersections

Abstract The tessellation of Computer-Aided Design (CAD) models into high-quality triangular meshes is a fundamental preprocessing step for downstream applications in visualization, numerical simulation, and digital manufacturing. While modern boundary representation models are typically geometrically valid and free of self-intersections, their tessellation frequently introduces artificial geometric artifacts-including self-intersections and gaps-particularly in regions containing narrow features or high-curvature surfaces. This paper presents a robust, general framework for watertight B-rep tessellation with three key contributions. First, we introduce mathematically rigorous definitions of critical points and critical regions that characterize local geometric behavior; our analysis proves that sampling constrained to these regions guarantees intersection-free refinement under arbitrary resolution. Second, we develop an accelerated spatial indexing structure using a novel parallel hexahedron bounding volume hierarchy, which dynamically adapts to geometric complexity while minimizing the number of required critical regions. Third, we propose an improved constrained Delaunay triangulation algorithm that, when guided by critical regions, simultaneously enforces watertightness and optimal element quality across surface patch boundaries. Comprehensive experimental evaluations against state-of-the-art geometric kernels (NetGen, Gmsh, and Open CASCADE) demonstrate our method’s superior performance in generating intersection-free meshes with enhanced geometric fidelity and computational efficiency.