Re: [Boost-users] [polygon] Valgrind errors when normalizing any angle polygons

Subject: Re: [Boost-users] [polygon] Valgrind errors when normalizing any angle polygons
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-11-05 15:44:29

Josh Pieper wrote:
> On Thu, Nov 4, 2010 at 10:28 PM, Simonson, Lucanus J
> <lucanus.j.simonson_at_[hidden]> wrote:
>> No, I fully expect the library may crash or exhibit other undefined
>> behaviors if coordinates are too large and gmp is not used.  If the
>> coordinates are small enough that the numerator and denominator of
>> the line intersection equation fit in the floating point
>> representation without roundoff then the library may work correctly
>> without the need for gmp, but in general I don't advise using the
>> library without gmp.  You will quickly find that in order to avoid
>> rounding error issues you want to scale your data up, which won't
>> work if you are trying to keep things within a ~16 bit range.        
> 
> Would it be worth it to BOOST_ASSERT if data too large for the given
> types is passed in without gmp enabled?  I would expect that an
> assertion is probably more desirable than undefined behavior.

It is an interesting idea, I'll think about it.  There is a chance the library would succeed for large coordinates, so asserting in cases where it would succeed seems not desirable.  Also I don't want to guarentee that it succeed for small coordinates since it wasn't really my intent to make it rubust in that way.  Computing the scale of data where problems can occur is a little complex.  I don't know how to detect how many bits are in the mantissa of the long double data type at compile time.  Is an assert, which is an excpetion better than the valgrind exception or whatever other exception you get?  The library is exception safe and you should be able to catch any of them and conclude that there was a precision problem due to not using gmp.

> For a platform with a given maximum floating point resolution, what is
> the maximum integral value that may be used without triggering
> instability?  On this system, a long double has 64 bits of mantissa.
> Does that mean the gmp-less boost::polygon is limited to 64/4 = 16
> bits of resolution?  We're using gmp now, so this is purely for my
> curiosity.

        x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2); 
        
d** = scale + 1

Scale + (scale + 1)  + (scale + 1) + 1 + 1 + 1 = bits required.
If bits required = 64 then
59/3 = your max bit range in the input, so 19 actually.  I didn't think long double had a 64 bit mantissa, I thought it was 54.  With 54 you get 49/3 = 16 bit range.  That is why I said 16 before.

>> I just checked into the trunk today a couple changes that should
>> make the library more reliable without the use of gmp.  My version
>> number for the checkin is 66403.  The sandbox version is older than
>> the 1.44 release.  I stopped syncing the sandbox once I merged to
>> the release branch and now do all development on the trunk.
>> Included in this checkin were several fixes for resizing that didn't
>> make it in time for the 1.45 release.  If you plan to use resizing
>> you should update.       
>> 
>>> Is this merely a mis-use of the API?
>> 
>> I would say yes, but only because you expected the library to be
>> reliable without using gmp.  Right now I can't provide that and make
>> no promises about reliability if gmp is not used.  
> 
> Fair enough.

Even if you stick to the 16 bit range I don't want to promise 100% robustness.  I don't know why it might fail, but that doesn't mean it won't.

>> You mentioned a number of oddities but describe only one.  What else
>> have you run into? 
> 
> We had hoped to use resizing, ran into the aforementioned problems,
> then ran into different ones after trying trunk.  I believe they were
> related to using beveled corners, but I still need to reduce our
> problems to minimal cases.

I'm looking forward to seeing minimal cases.  Beveled corners should work except for the snap rounding issues encountered when edges being convolved result in parallelograms narrower than the grid resolution.  This error is bounded to the snapping distance, however.  I'm eager to fix any bugs found both for a better 1.46 release and for our own use of the library.

Thanks,
Luke