Mail Archives: geda-user/2015/12/22/10:33:30
Oh - and Martin,
I'd be interested to know how you got on running your board against
this old branch of mine:
http://www.repo.or.cz/geda-pcb/pcjc2.git/shortlog/refs/heads/for_master2
Take a look at the commit log, and you will see fixes and descriptions
of a number of polygon bugs. One or more might impact upon your recent
fix for the Collect1 routine - but as you've been studying the code
more recently than I, you're probably in a better place to assess
these.
FWIW, I've seen less problems running this code in anger, and haven't
bumped into any new ones.
Testing these polygon fixes for changes in behaviour takes some time!
- Looks like about 8 months since I last touch my branch :(.
Peter
On 22 December 2015 at 15:22, Peter Clifton
<petercjclifton AT googlemail DOT com> wrote:
> Clever solutions exist, and fall into the category of "snap rounding"
> algorithms.
>
> They are moderately complex, and as I'm sure you will appreciate
> having dug into PCB's code - so is our existing algorithm.
>
> If you're interested in working on this, I can dig out some papers and
> references. Most start with an assumption of exact arithmetic, which
> makes things "interesting". In reality, you may just need to guarantee
> "enough" precision.
>
> FWIW, the BOOST polygon intersection algorithm looks like a good one.
> (Although I don't think it does online edits quite as efficiently as
> we might - it is WAY better in terms of computational complexity in
> the start-from-scratch case). It also solves the snap-rounding problem
> on the fly.
>
> Boost isn't the immediate answer to all problems though.... KiCAD uses
> it, and I know they have at least one test-case which causes it to
> crash and burn fairly repeatedly. (I had meant to dig into that for
> them is a cross-project peace offering, but I ran out of time last
> time I started digging).
>
> Peter
>
> On 22 December 2015 at 14:47, Martin Beranek <martin AT mb5 DOT cz> wrote:
>> Hi,
>>
>> I was tracing down the cause for a bug when a polygon sometimes
>> disappears after component was moved and "Error while clipping PBO_SUB: 3"
>> is printed. And I have discovered quite nasty issue related to
>> intersections calculation and rounding.
>>
>> The little PCB which shows this bug is attached (click in the center of
>> upper-left silk screen dot in component labeled "*MOVE_ME* and drop it
>> over second dot, that is 0.2 mm down and 0.1mm right), but I think the
>> problem behind is much more general.
>>
>>
>> Imagine part of contour A--B--C such that A->B edge goes approximately
>> in bottom right direction and B->C edge goes back to the left (located
>> below A->B, the exact value of angle ABC is not important, say about 45
>> degrees). The inside of the polygon is "between" points 'A' and 'C'.
>>
>> Then let's have edge C->D which is part of second contour and which
>> intersects edge AB really close to the point B.
>>
>> Calculating the intersection point 'E' and consequent rounding can
>> result in coordinate which is actually bellow (!) edge BC, not above it
>> as it should be. So we get contour A-E-B-C which intersects itself (the
>> edges A-E and B-C intersects and the order of edges and inner/outer
>> areas is thus wrong at 'E'.
>>
>> Bit ascii-art of the result:
>>
>>
>> A.
>> \
>> \
>> C-___ \
>> \ `--\-__
>> `-,_ \ `-.
>> `---E----B
>> \__
>> `----,
>> `-----D
>>
>>
>> It seems that current polygon code leave things like this (first contour
>> A->E->B->C and second C->E->D).
>>
>> The edge C->E of second contour is labeled "outer" as it lies below
>> 'B->C', so far mostly OK, I guess. But next labeling step at 'E' results
>> in (wrong) label "inner" because the assumption that inside of the
>> polygon is to the right from the edge is violated there.
>>
>>
>> The actual coordinates which lead to this kind of bug are:
>>
>> A = [4309892, 10990108]
>> B = [4331483, 11008549]
>> C = [3998398, 10981358]
>> D = [6078476, 11151160]
>>
>> Calculating intersection between A-B and C-D gives [4331482.44, 11008548.52]
>> which is rounded to
>>
>> E = [4331482, 11008549]
>>
>> Note that point E is directly to the left from 'B', so below 'B->C'. And
>> the point 'B' is above 'E->D'. It feels strange that such intersection
>> and rounding can actually exists, but there is real-world case. And it
>> totally breaks polygon code.
>>
>> (I have seen such polygon-disappearing quite often in more complicated
>> boards, but it is not so easy to make minimal example and trace the
>> actual cause, so I can not tell it is the same issue every time ...)
>>
>>
>>
>> What I am wondering about is if there is any sane solution to this
>> issue. Some 'clever' rounding which avoids self-intersecting lines would
>> be probably quite complicated to code and maybe computation intensive as
>> well(?). Maybe still leading to unsolvable situations sometimes?
>> But is there any other, better way how to avoid this?
>>
>>
>> Martin
>>
>>
- Raw text -