kicad-developers team mailing list archive

[Wayne Stambaugh <stambaughw@xxxxxxxxx>]

On 6/2/2015 2:32 PM, Tomasz Wlostowski wrote:
> On 01.06.2015 19:09, jp charras wrote:
>> Le 01/06/2015 18:23, Tomasz Wlostowski a écrit :
>>> Hi all,
>>>
>>> I did a small investigation of the polygon-related
>>> segfaults/miscalculations. It looks like Boost.polygon badly handles
>>> cases where intersection points of the edges of the polygons lie close
>>> to each other or overlap, causing the 'snap rounding' algorithm used in
>>> boost to go haywire. This is the case for complex zones, with a lot of
>>> thermal holes or via patterns (i.e. a thermal pad under a QFN with a via
>>> field).
>>>
>>> See last comment from https://svn.boost.org/trac/boost/ticket/10642.
>>>
>>> There's a variety of effects I observed.
>>> - a segfault.
>>> - an incorrect or empty resulting polygon: merging the holes before
>>> subtraction from the main outline (polyset_holes in
>>> AddClearanceAreasPolygonsToPolysList) using boost::assign or subtracting
>>> the holes one-by-one (instead of the whole set) fixes the segfault, but
>>> I know at least one case where the resulting zone is incorrectly
>>> calculated. I'll attach the test cases to the bug report on Launchpad
>>> later in the evening.
>>
>> I am not sure subtracting the holes one-by-one (instead of the whole
>> set) fixes the segfault. Because the segfault depends on the geometry,
>> it does not happen when you changes the calculations for a given case,
>> but can happen in an other case which previously did not crash.
>>
>>>
>>> For the reasons above, I would strongly consider dropping
>>> boost::polygon. There are also non-technical issues:
>>> - It hasn't been maintained for ~1.5 years. The last activity of the
>>> official maintainer was 3 years ago.
>>> - the code is a mess (look at example below).
>>>
>>>
>>>
>>> @Jean Pierre: do you think Clipper is stable enough for our use? (at
>>> least in case of a bug, it's actively developed and the author offers
>>> support). I'm not asking about speed, it's not important if Kicad
>>> crashes or produces incorrect polygons.
>>>
>>> Tom
>>
>> I don't think we can easily replace boost::polygon by Clipper.
>>
>> They have complementary features, but neither boost::polygon nor Clipper
>> have all features we need ( for instance transform a self intersecting
>> polygon into a set of not intersection polygons is easy with clipper,
>> not with boost::polygon).
>>
>> A major issue (or lack of feature) is the fact Clipper does not handle
>> holes inside a polygon by connecting holes by overlapping segments
>> (to create only one polygon), which is needed in draw (and some other)
>> functions
> 
> Hi,
> 
> I'm almost done with SHAPE_POLY_SET class for the geometry library, a
> Clipper wrapper adding some missing Clipper features needed in Kicad
> (e.g. polygon fracturing). I'll send a patch soon (affecting only
> AddClearanceAreasPolygonsToPolysList), so that we can compare how well
> it performs wrs to Boost.Polygon.
> 
> Cheers,
> Tom

Great work Tom.  Thanks.

Wayne

>>
>> I also tried to use Clipper to replace the polygon set subtracting which
>> crashes Pcbnew.
>>
>> But if Clipper gives good results to subtract 2 polygons, this is not
>> the case to subtract 2 set of polygons (when polygons inside each set
>> overlap, the result is strange, whatever the settings used in calculations).
>>
>> Therefore, replacing boost::polygon by clipper is not trivial.
>>
>> If we drop boost::polygon (due to this bug, and the lack of
>> maintenance), one can consider Clipper (which looks stable enough now)
>> but also CGAL.
>> Clipper needs not trivial rework to calculate the zone filling.
>> I do not have used CGAL, but it is a large geometry library, actively
>> maintained, and it could be considered before taking a decision.
>>
> 
> 
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help   : https://help.launchpad.net/ListHelp
>