Foundation of a Computable Solid Modeling

摘要

Correctness of algorithms in computational geometry are usually proved using the unrealistic Real RAM machine model of computation with the undesirable result that correct algorithms, when implemented, turn into unreliable programs. In this paper, we use a domain-theoretic approach to recursive analysis to develop the basis of an effective and realistic framework for solid modeling. This framework is equipped with a well-defined and realistic notion of computability which reflects the observable properties of real solids. It is closed under the Boolean operations, admits non-regular sets and supports a design methodology for actual robust algorithms. Within this model, some unavoidable limitations of solid modeling computations are proved and a sound framework to design specifications for feasible modeling operators is provided. Some consequences in computation with the boundary representation paradigm are sketched that can incorporate existing methods into a general, mathematically well-founded theory. Moreover, the model is able to capture the uncertainties of input data in actual CAD situations.