Robust regularized set operations on polyhedra
Beat D. Bruderlin · 2002
Describes a simple, efficient and provably robust implementation of regularized set operations on polyhedral objects. Halfspaces are used as the underlying data structure to simplify the handling of degenerate cases. The geometric operations and relations are computed with floating point arithmetic which is fast but can lead to ambiguous interpretation of degenerate situations. To ensure that the results are still consistent the author implemented a test that detects when dependent decisions contradict each other. The consistency test is very simple, and does not require reasoning about the logical dependencies of the relations. The logical structure and the asymptotic behavior of the algorithm are not influenced by the consistency test, which makes this approach well suited for interactive modeling systems on graphics workstations with floating point accelerators.>