Aiming for a robust Boolean algorithm using approximate arithmetic

Add to your list(s) Download to your calendar using vCal

• Julian Smith
• Thursday 20 September 2007, 14:15-15:15
• SS03, William Gates Building.

If you have a question about this talk, please contact Neil Dodgson.

Practice run for workshop presentation

Robust implementations of the Boolean operation on boundary representations of shapes are highly problematic when the computations are based on inexact machine arithmetic. The arithmetic computations required can yield inconsistencies in the results, hindering the possibility of creating a topologically correct boundary. These difficulties are compounded by the fact that most operations perturb the boundary, which can lead to geometric errors such as boundary self-intersections.

I present a topologically robust Boolean algorithm for polygonal/polyhedral shapes. It is based on a hierarchy of interdependent operations guaranteed to yield consistency in the intermediate results. Hence, the algorithm provably always generates a topologically correct final result from topologically correct input, irrespective of the extent of any numerical rounding. The algorithm is tolerant to geometric errors, but does not resolve them. For the result to be acceptable to end-users, it is generally desirable to apply a smoothing post-process to remove marginal gaps, slivers and overlaps. I go on to discuss my present work, which concerns how to devise a robust algorithm for resolving geometric errors in a (topologically correct) shape representation. I discuss both algorithms in the context of the requirements for a robust approximate algorithm.

This talk is part of the Rainbow Graphics Seminars series.

This talk is included in these lists:

• SS03, William Gates Building

Note that ex-directory lists are not shown.