Mail Archives: geda-user/2015/12/22/10:42:09
Oh - one thing else I'd say (which you may have already realised...)
These are two things I learned whilst trying to add support for
primitive arc-segments, and make poly-curve outlines:
It is _really_ easy to make a change to the polygon code which breaks
something in subtle ways elsewhere.
It is _really_ easy to make a tiny change to the collecting code,
which means a bad test-case will now pass - but in fact, it just
no-longer hits the still-existing bug.
It turns out that adding arcs into polygons makes a whole extra load
of pain, and I never got it completely working. I actually got much
better results (or approximations to the correct result), by leaving
the computation in line-segments, but tracking along with each segment
whether it was an original line-segment, or a straight line
approximation to some other curve (the details of which you can attach
and record with the data-structure).
Arcs in polygons (or at least approximating them) was a highly desired
feature for producing better board outlines for 3D export - where such
outlines might have specified arc geometry, or intersect with a via /
pin barrel etc., to include it.
Peter
On 22 December 2015 at 15:33, Peter Clifton
<petercjclifton AT googlemail DOT com> wrote:
> 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 -