Geometric Modeling of CAD Surfaces
Résumé
A complex surface is usually represented on a computer aided design (CAD) system by a collection of patches, where each patch is defined by a continuous mapping from a domain of R2 into R3. This paper presents a methodology for defining a discretization (made of quadrilaterals and triangles) that accurately reflects the geometry of a CAD surface. Such a discrete representation is generally available on any CAD system, if only to visualize the parts to be designed. As for us, the method must be robust, fast and capable of generating a discrete geometric support suitable for meshing purpose. In particular, the quality of the geometric support depends on two properties, namely proximity and regularity. Proximity controls the distance between the elements of the support and the surface, while regularity controls the angular gap between tangent planes to the surface and tangent planes to the elements.
The construction of the geometric support of a surface patch can be decomposed into nine steps, briefly enumerated in the following. (1) Discretize the boundary of the surface patch by recursive subdivisions, considering both properties of proximity and regularity w.r.t. curves. (2) Create a quadtree such that the interior of each leaf contains at most a single vertex of the previous discretization (nevertheless several vertices may lie on the leaf boundary). (3) Enforce the edges of the curve discretization into the quadtree: for each edge, its intersections with the leaves of the quadtree defines subedges called traces, and adjacent traces in a same leaf are merged into one straight segment if they are derived from the same curve. (4) Cut each leaf containing one or more traces, making a local “triangulation” (containing a few quadrilaterals and triangles) of the corresponding quadrant that conforms to these traces. (5) Identify the domain definition of the discretized mapping, by removing the elements of the triangulation that are outside the discretized boundaries, now defined by consecutive traces. (6) Homothetically refine each leaf that violates the properties of geometry and regularity w.r.t. the patch. (7) Balance the quadtree by imposing a 2:1 rule between neighboring leaves, in order to improve the quality of the support and to facilitate the next step (i.e. building a conformal triangulation). If a leaf is subdivided, triangulations of its children are constructed and the triangulation of the parent leaf is removed. (8) Make a conformal triangulation from all the local triangulations of the leaves, thus providing the geometric support. (9) Smooth this geometric support by swapping adjacent triangles.
The proposed method has been implemented as a part of a surface mesher called ALIEN. Several examples are provided to show the robustness and computational efficiency of the program, as well as the quality of the geometric support.