BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Aiming for a robust Boolean algorithm using approximate arithmetic
  - Julian Smith
DTSTART:20070920T131500Z
DTEND:20070920T141500Z
UID:TALK8085@talks.cam.ac.uk
CONTACT:Neil Dodgson
DESCRIPTION:Robust implementations of the Boolean operation on boundary re
 presentations of shapes are highly problematic when the computations are b
 ased on inexact machine arithmetic.  The arithmetic computations required 
 can yield inconsistencies in the results\, hindering the possibility of cr
 eating a topologically correct boundary.  These difficulties are compounde
 d by the fact that most operations perturb the boundary\, which can lead t
 o geometric errors such as boundary self-intersections.\n\nI present a top
 ologically robust Boolean algorithm for polygonal/polyhedral shapes.  It i
 s based on a hierarchy of interdependent operations guaranteed to yield co
 nsistency in the intermediate results.  Hence\, the algorithm provably alw
 ays generates a topologically correct final result from topologically corr
 ect input\, irrespective of the extent of any numerical rounding.  The alg
 orithm is tolerant to geometric errors\, but does not resolve them.  For t
 he result to be acceptable to end-users\, it is generally desirable to app
 ly 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 rob
 ust algorithm for resolving geometric errors in a (topologically correct) 
 shape representation.  I discuss both algorithms in the context of the req
 uirements for a robust approximate algorithm.\n
LOCATION:SS03\, William Gates Building
END:VEVENT
END:VCALENDAR