Conventional geometric models inevitably involve defects such as numerical gaps and numerical inconsistencies that are manifested by conflicts of the information stored in the topological structures and geometric representations. Considerable gaps (e.g. missing patches) and inappropriate intersections may also exist in the boundary of a model. Those defects cause severe problems in applications which rely on the continuity of the boundary, for example, finite element analysis, rasterization algorithms and solid free-form fabrication methods. Other defects, such as sliver faces in a model, can also create undesirable features which will cause difficulties in downstream applications (e.g. mathematical singularities in finite element analysis). Identification of the nature of such CAD model defects and development of model rectification techniques suitable for major applications are therefore required. A CAD model rectification system should generate models which are topologically correct and geometrically consistent, and also preserve the designer's intent based on knowledge about erroneous models and user input. In an earlier project we have developed a robust interval solid modeler based on interval geometric representations and evaluations. The interval solid modeling provides a basis for building robust CAD/CAM systems that guarantee the integrity of the model in terms of clear separation of interior and exterior, and topological consistency. We need therefore to develop a mechanism for a graceful transition of the current erroneous geometric models to the interval solid models, which provides the basis for robust modeling and interrogation methods.

Solid free-form fabrication (SFF) processes have placed new demands on the CAD/CAM community in terms of working with heterogeneous material compositions known as functionally graded material (FGM). We propose to investigate the computational issues of modeling, designing, interrogating, and processing for fabrication objects consisting of FGM. Since designing in terms of graded compositions is a new concept, a new design methodology will be outlined, capturing the flow of information between designers, CAD systems, and the manufacturing process. To represent FGM models, the cell tuple data structure will be investigated as a standard capable of representing generalized models of variable composition. Analytic functions will be incorporated into the representation to describe truly variable material composition, a feature not supported by any other method. Compatibility with existing CAD systems will be ensured by establishing methods to convert from a standard finite element (FE) mesh to the FGM data structure. Algorithms for designing graded compositions, a new concept for designers, will be proposed and evaluated. Within the design methodology, design rules are to be defined, capturing inherent limitations in the manufacturing process. Algorithms applying these design rules to the FGM modeling method will allow the evaluation of a model for successful fabrication. Some of these rules might also be formulated as restrictions on FGM creation, allowing their application at design time.

The objective of this project is to develop a numerically robust and topologically reliable unstructured triangular mesh generation algorithm for the faces of complicated boundary representation (B-Rep) models. Towards this objective, we introduced a piecewise linear approximation method for a set of mutually non-intersecting simple composite curves. We have also developed a piecewise linear approximation method for a set of mutually non-intersecting trimmed composite polynomial/rational surface patches using unstructured triangular elements. Our methods satisfy the prescribed approximation error tolerance and guarantees the existence of a homeomorphism between the actual nonlinear geometries and their approximation. For complex 3D objects, the sources of failure in automatic mesh generation algorithms are: (1) Floating point inaccuracy, and (2) Topological inconsistency in the geometry approximation process. To overcome the first problem, we have developed a geometry approximation scheme relying on the interval geometric definitions/computations, which leads to numerical robustness and provides results with numerical certainty and verifiability. For example, a robustness problem in the conventional Delaunay triangulation algorithm was studied and robust decision criteria have been introduced to prevent possible failures in the Delaunay test. The problem of topological inconsistency in the triangular meshes has been solved by robustly identifying and removing the possible inappropriate intersections between each pair of approximating elements. Our surface triangulation algorithm constructs 2D triangulation domains which sufficiently preserve the shape of triangular elements when mapped into 3D space, and the algorithm also provides an efficient method explicitly controlling the aspect ratio of the triangular elements in order to achieve a high quality well-conditioned mesh.

We have laid the framework for a new generation of robust solid modelers for representing and interrogating solid models with curved boundaries in the context of imprecise (discrete) computer arithmetic. This robust modeler is aimed to replace the current inconsistency-prone modelers used in industry. Towards this general objective, we have developed: (1) A robust and efficient nonlinear polynomial solver for overconstrained, underconstrained and balanced polynomial systems based on Bernstein subdivision method and rounded interval arithmetic (RIA); (2) A consistent 2D and 3D interval curved solid modeler, in which objects are bounded by interval polynomial curves and surface patches; (3) A unified algorithm for general geometric intersections including ill-conditioned intersections such as tangential contact point, tangential intersection curve, and overlap of curves and surfaces; (4) An nD novel data structure based on the incidence graph which relies on the cell-tuple data structure for interval geometric entities (points, curves, and surfaces) to permit boundary representation of interval objects; and (5) Boolean operations for 2D and 3D manifold objects, and extended to 2D and 3D non-manifold objects resulting from ill-conditioned intersections.