kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

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.
> 
Hi Jean-Pierre,

It just eliminates the segfault, but doesn't fix the problem. I've seen
cases in which I got an empty or incorrect polygon as a result.

>>
>> 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
Fracturing polygons is easily doable.
> 
> I also tried to use Clipper to replace the polygon set subtracting which
> crashes Pcbnew.
In case of Clipper we can at least count on its author and his support,
he's actively developing it.

> 
> 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.
CGAL is a powerful, but huge beast and building it (think of Windows/OSX
users) is not trivial. I would give Clipper a try first.

Cheers,
Tom