Geometric Set Operations for Tolerancing in CAD

The aim of this project is to investigate geometric set operations for tolerancing, which is motivated mainly by the tolerance analysis of geometric constructions. There is demand for efficient and reliable computing with imprecisely defined geometric data. An important concept here is the notion of tolerance zone, which is a natural generalization of the basic entities of interval arithmetic on the real number line. If the input data of a geometric algorithm are points, lines, etc., the corresponding toleranced algorithm takes as input sets of points, lines, etc. (the tolerance zones) and computes all possible outputs, if we allow the input data to range independently in the respective tolerance zones. The difficulties here lie not on the conceptual but on the algorithmic side. Even very simple geometric algorithms (such as computing the circle defined by three points) become much more complicated if viewed from the tolerancing standpoint. An exception are linear and affine constructions (which includes most interpolation and approximation algorithms of computer-aided geometric design), which are well understood and whose tolerance analysis relies mostly on the convolution process for curves and surfaces. So the agenda for the proposed project consists of: - A systematic investigation of 2D and 3D geometric constructions relevant for computer-aided design, where not even the 2D case has been exhaustively researched so far, research on toleranced geometric transformations, toleranced curves and surfaces, and probabilistic tolerances. - The geometric methods employed will yield contributions to computational line geometry, computational sphere geometry, and the computational geometry of related fields. - Research on computationally feasibly approximative tolerance zones and test implementations of cases relevant for computer-aided design. - Investigation of convolution curves and surfaces, not only with regard to tolerancing, but also with a view towards other applications, such as the Minkowski product in the complex plane and stability criteria of families of polynomials.

Imprecise data are ubiquitous in applied and numerical mathematics. The problems which arise with their handling have attracted much attention and have led to significant developments in various areas. The research project Geometric Set Operations for Tolerancing in Computer-Aided Design studies a certain aspect, namely worst case tolerances in geometry, which in some sense generalizes interval arithmetic to dimensions greater than one. In our setting, imprecise data are described by tolerance zones. Depending on the nature of these data and the relations between them, various interesting problems arise. We investigated the propagation of errors through implicit geometric constraints (which often enough are multivariate quadratic), and conditions which guarantee that first order approximations do not exceed certain error bounds. We extend the concept of tolerance zone to probabilistic uncertainties via a generalization of the distribution envelope algorithm. A focus of research are imprecisely defined rigid body transformations, which are studied from both the differential geometry and geometry processing viewpoints. An interdisciplinary geoscience application is the smoothing of terrain data under hard constraints which stem from accuracy bounds in the data specification. This is a direct application of the concept of tolerance zone to discrete spline approximation.