Adaptive Precision Based Fast Algorithms for Robust Surface Intersections

Abstract

Most available algorithms for performing surface intersections are very versatile and cover a wide range of particular cases. However, the main problem of such algorithms arises already during the implementations, since they involve geometric calculations that require high degree of accuracy (i.e. most of these algorithms were not designed to work with special codes capable to deal with exact computations). Therefore, such algorithms need to be reformulated in order to consider exact computations, satisfying some error bound, which avoid possible crashes of the system. Thus, a set of fast algorithms for robust surface intersections is proposed in this paper. Three different algorithms are proposed, one which deals with intersections of a plane with a surface; the second algorithm allows inserting a curve on a given surface; whereas the third one is responsible for performing intersections between two surfaces. All the algorithms were adapted in order to allow adaptive precision based fast computations by the direct use of robust and adaptive geometric predicate algorithms. Examples are presented to validate and to demonstrate the capabilities of the proposed algorithms.