Abstract

There are serious problems in computing the union, intersection or difference between two boundary mesh shapes when using approximate arithmetic, because inaccuracies and inconsistencies in the low-level calculations can lead to an invalid result. Two types of error can occur: topological errors, usually manifested as cracks in the ‘boundary’, and geometrical errors, often manifested as a self-intersecting ‘boundary’. The traditional approach taken by system developers is to invest effort in tuning a system so that it tends to avoid catastrophic failure for typical applications. Others have adopted the approach of resorting to exact arithmetic to achieve 100% reliability. I shall describe the algorithm I devised, based on standard machine arithmetic, that provably generates a topologically valid result. I shall also describe my latest work that addresses the issue of geometric errors.