kicad-developers team mailing list archive

[Wayne Stambaugh <stambaughw@xxxxxxxxx>]

On 6/1/2015 1:09 PM, 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
> 
> 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.
> 

JP,

How difficult would it be to modify the sample file you created for the
boost bug report you filed to use Clipper and cgal?  At least you would
be able to verify that the result is a valid polygon before you attempt
to replace boost::polygon with either library.  I realize that there
could be other cases where cgal or clipper fail and boost::polygon does not.

I also just looked and there are mingw32 and mingw64 pacman packages of
cgal in the msys2 project so that would make life easier if we need to
switch to cgal.  There is no clipper package.

Wayne