Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-26 11:29:26

Andreas Fabri wrote:
>> A user can easily avoid non-integer intersection artifacts with 45
>> data by multiplying all cordinate values by two.  The output polygon
>> vertices will then be even-even or odd-odd coordinate pairs (such
>> data cannot give rise to non-integer intersection) and can be fed
>> back into the algorithm as many times as desired.    
> 
> 
> Well, if you use an int, you can't multiply that often with 2 without
> getting an overflow, but as you write in the paper, that is not a
> problem, because you can use arbitrary precision integer types like
> GMP.  But doesn't that make it slow in practice?  Will it appear in
> practice, that is do you have situations in your VLSI related
> software that does iterations of Boolean operations? 
 
You only have to scale all inputs by two then any sequence of boolean operations is safe from non-integer intersection.  This may not be immediately obvious, but as long as the end points of two segments are both even coordinates or both odd coordinates their intersection point will allways be either both even or both odd.  A non-integer intersection between 45-degree edges only happens when and "even" edge is intersected with and "odd" edge.  Booleans cannot introduce odd edges, so arbitrarily long sequences of booleans can be performed without the need for scaling between each.
 
> So when you multiply the coordianted of polygon P by two, and feed it
> back the user has to associate the scale factor to P, in order to
> also scale a not-yet scaled polygon Q, before applying a Boolean
> operation on P and Q.  Not a big deal, but wouldn't it make sense
> that the scale factor becomes part of your package? 

I never scale and give the user back scaled coordinates as the result of a boolean.  I do provide an API that they can use to scale if they desire.

Avoiding problems with non-integer intersections in 45-booleans is a part of the package, I scale up by two and down by two for every 45 degree boolean op where non-integer intersection is detected.  I use 64 bit integer if the coordinate was 32 bit integer to avoid overflow.  It is transparent to the user except for the clipped off corners that may be present in the result.  I also provide access to a set of 1x1 unit squares that describe the locations where non-integer intersections occured in the boolean to allow the user to know how much and where precision forced approximations. These error rectangles accumulate when booleans are chained so that they need only be checked in the end result and not in each intermediate result.  I'm adding to my todo to improve documentation of this feature.

As to performance, the 45-degree boolean is roughly 2X slower than manhattan if there are no non-integer intersections and if there are non-integer intersection they are about 8X slower because I have to do quite a bit of extra work scaling, converting to 64 bit and clipping off corners of output polygons.  Since I can't know a-priori whether there will be non-integer intersections I optimistically run the boolean, throw an exception when the first non-integer intersection is detected, catch it myself and handle it by scaling up and clipping odd corners when scaling down.  The algorithm is exception safe because I use RAII for all memory management and we've validated it with valgrind.

You ask some good questions about the 45 booleans.  It took me quite a while to figure out these issues.  Since the specialized 45-degree algorithm can be so much faster than the general algorithms and it is an important special case for VSLI we were very motivated to solve them.  Right now the 45 degree algorithm is used in full scale production on layout data and are stable, generating no issues since the code for handling non-integer intersections was validated.

Thanks,
Luke