Integration of parametric geometry and non-manifold topology in geometric modeling

Various types of parametric surfaces in surface modeling are useful for precise and concise representation of complicated geometric shapes. However, the lack of a notion of solids in surface modeling makes many important interrogations in geometric modeling difficult. The major advantage of solid modeling is the unambiguous representation of solid objects. A recent advancement is the extension to non-manifold topological (NMT) modeling. In such environments, entities of different dimensions can coexist and operate. Such mixed-dimension representation schemes enable the modeling of objects in different levels of abstraction. However, most of the existing NMT modeling environments are restricted to linear or quadric geometry. Integrating the parametric geometry into the non-manifold topological modeling system is the trend for the new generation geometric modeler. The major technical challenge of the integration comes from the complexity of the set Boolean operations in such a system.; This thesis discusses various issues of this integrated system. First, the geometric information of such a system is much richer than the polyhedral counterparts. The design of the data structure for representing the NMT models should take into account the representation of the geometric information. Second, the previous efforts for representing trimmed surfaces have been restricted to two-manifold configurations. An augmentation of the topological data structure is proposed to handle the geometric representation of trimmed surfaces in NMT models. The conciseness of the geometrical representation and the representation of non-regular geometric entities is also addressed.; The second part of the thesis concerns the frequently used set Boolean operations. In this thesis, a bottom-up intersection algorithm is proposed. The intersection computation is executed in the order of ascending dimension. This arrangement minimizes the discrepancy which might arise in finite-precision implementation. A particular focus of the intersection discussion is the surface-surface intersection problem. The difficulty of such an operation is two-fold: topologically, many configurations can occur and every case needs to be accounted for. Geometrically, the detection of small intersection loops and computation of intersection curves near singularities are challenging tasks. A new loop detection technique, the augmented lattice method, is proposed in this thesis. This method does not employ the recursive subdivision methodology. Our experience shows that the method is quite effective for handling various types of singular configurations. Also, several techniques have been presented for enhancing the robustness of the computation of the intersection curve using the marching method. In addition to the decomposition at the characteristic points, the utilization of the orientation of the curve and the characteristic curves is proposed.; The algorithms in this thesis have been implemented in a prototype system using the non-uniform rational B-spline as the central geometric representation.