Exact arithmetic solid modeling

Robustness in geometric computation is an important subject and it the topic of a variety of research by many people. Yet, to date, there is no known provably robust algorithm for performing Boolean operations on solids. The primary difficulty lies in performing arithmetic operations where fixed precision floating point numbers are employed to carry out operations that require infinite precision. Consequently, topological decisions based on the results of finite arithmetic operations are error prone. We study the robustness problem in the context of Boolean operations on solids by implementing a solid modeler that is capable of performing both rational arithmetic and floating point arithmetic. The algorithm has been implemented in identical code except for arithmetic. Therefore, it clearly demonstrates the effects of numerical errors on Boolean operations in those cases where the algorithm produces correct results with rational arithmetic but fails with floating point arithmetic. We analyze spatial configurations of solids that could result in failure of Boolean algorithms when floating point arithmetic is adopted. With inevitable numerical errors in floating point arithmetic, it seems attractive to use rational arithmetic when implementing Boolean algorithms. However, as shown by the classification operations, this is feasible only when dealing with linear objects such as lines and planes. We study the precision required for exactly classifying a point, defined as the intersection of two lines or three planes, with respect to a given line or plane. Assuming line and plane equations have bounded integer coefficients, we need roughly four and five times of the input precision for point/line and point/plane classification respectively and we also show that this result is optimal. Next we extend the concept of exact classification to the curve and surface domain. We study a resultant based method to exactly classify a point with respect to a given conic or quadric. The required precision is shown to be too high to be practical. Using piecewise linear approximations of conics and quadrics, the same problem is reduced to the exact point/line or point/plane classification problem which has previously solved. The required precision of the approximations is also analyzed