Many application programs driven from modern CAD/CAM systems often operate on approximate lower order representations of the exact geometric definition. These applications include finite element or boundary element meshing for analysis, fundamental geometric calculations such as integrals, rendering objects on a graphical display, and data exchange between various geometric modelers or design and fabrication systems. For this reason, a robust piecewise linear approximation method of high order and procedural curves and surfaces is necessary.

This thesis presents a piecewise linear approximation method of edges and faces of complicated boundary representation (B-Rep) models within a user specified geometric tolerance. The proposed method uses numerically robust interval geometric representations/computations and also addresses the problem of topological consistency (homeomorphism) between the exact geometry and its approximation. Those are among the most important outstanding issues in geometry approximation problems. The possible inappropriate intersections of the approximating elements are efficiently detected and removed by local refinement of the approximation to guarantee a homeomorphism between the exact geometry and its approximation. We also extract important differential geometric features of input geometry for use in the approximation.

Our surface tessellation algorithm is based on the unstructured Delaunay mesh approach which leads to an efficient adaptive triangulation. A robustness problem in the conventional Delaunay triangulation is discussed and a robust decision criterion is also introduced to prevent possible failures in the Delaunay test. To satisfy the prescribed geometric tolerance, an efficient node insertion algorithm is utilized and furthermore, a new efficient method to compute a tight upper bound of the approximation error is proposed.

Unstructured triangular meshes for free-form surfaces frequently involve triangles with high aspect ratio and accordingly, result in ill-conditioned meshing. Our proposed surface triangulation algorithm constructs which sufficiently preserve the shape of triangles when mapped into 3D space and furthermore, the algorithm provides an efficient method that explicitly controls the aspect ratio of the triangular elements.

Thesis Supervisor : Professor Nicholas M. Patrikalakis