Mail Archives: geda-user/2015/12/22/17:33:42
On 22 December 2015 at 21:57, Martin Beranek <martin AT mb5 DOT cz> wrote:
> For the polygon.c -- yes, I am aware that there are (in main branch)
> bugs in frac_circle function and its usage. It was, in fact, one of
> main reasons why I started to analyze the polygon code. But, exactly as
> you have written, because modifications in polygon.c can hide bugs
> in polygon1.c, I have decided to go after bugs there first, at least as
> long as I have a board producing reproducible bug there.
>
> Originally, I believed that disappearing copper fills would be some
> 'real' bug in a code which just need to be fixed, but it turned out to
> be more fundamental problem. :-/
Sadly, we cured most of the "easy" bugs in polygon1.c some while ago..
the remaining ones are often truly nasty. Sometimes (like the one I
think we both found), there are still dumb logic bugs hanging around
that don't fall into the class of "complex numerical problem".
> Back to the polygons and your points:
>
> 1) I see, you have modified the frac_circle() in your branch. What I
> have noticed is that various calls to frac_circle() does not agree on
> the fact if first or last point is included, so it leads to long edges
> between arcs to be not exactly parallel with line or pad (it is not
> rounding error but missing first/last point in circle approximation).
Yes - I got very confused over those. At one point, I had two
versions, one doing each. I'm struggling to remember it now, but which
you use has an impact upon some of the more "interesting" stuff I was
playing with, such as tagging the approximated linear segments with
info as to what radius and centroid of arc they are approximating.
I think I had (in a branch somewhere) most of the geometry fixed,
except thermal.c. Its hard enough to follow with the rounded rectangle
type geometry, and the thermal stuff is more complex. (And possibly
wrong - in some cases).
> My idea for fix was to change the circle code so that it will produce
> polygon into which actual exact arc is inscribed. So, transition from
> straight edge to the circle approximation would be tangent point, not
> vertex. Coding it this way, some problems related to (not) including
> first and last point can disappear automatically and the minimal
> clearance to the object inside is correct without need for adding extra
> epsilon to radius.
One idea I never pursued - which will greatly reduce complexity of
output polygons, is to force-align the circular approximation against
fixed angular steps. Say you had two lines meeting at 10 degrees...
why not have the end-cap vertices at the coincident ends match? (Just
need to figure out a scheme for stitching the nearest
arc-approximating vertex sensibly into the straight line portion.
(Ideally, leave the straight line portion un-molested, as shifting it
could potentially cause other rendering / output problems).
If you dig into the past, someone (not me) cleverly changed the arc
approximation from straight lines inside, to straight-lines outside,
the ideal circular arc. (I forget which we have now). I remember being
annoyed at the time, as in fixing whatever DRC bug they were chasing,
the change simultaneously a similar problem elsewhere due to the
expansion (or contraction - I forget) of the arcs.
You might find somewhere in the branch (I can't recall), I'm messing
with trying to revert that change...
Regarding linear segments approximating arcs etc.. in our polygon
code, vertices are used to stash edge information... (edges and
vertices are 1-1 related for our cases, so why not... its just
confusing). This is true, certainly in my branches, but to a lesser
extent - also in the upstream polygon1.c processing IIRC. I always got
terribly muddled about whether the vertex which stashed edge
information was the one which started, or ended the edge. (I think I
tried both at one point when implementing stashing of arc-data in the
edge segments approximating it). - FWIW, this worked really well BTW -
must pick it up again at some point.
I have a recollection that the choice of adding the first point or
last point in frac_circle, impacted upon how convenient it was to
stash this information at the time of edge creation.
> I have not read your code yet, so I can not tell how different is my
> approach compared to yours.
>
>> 2. Sometimes we get rounding errors, that make polygon edges which
>> should end up as exactly straight, out by 1 or 2 nm over their length
>> - which produces tiny little polygon slivers that are prone to
>> problems, and rounding.
>
> I am not aware of this one. (Given it is really rounding bug and not
> consequence of point 1.)
Rounding bug is fine (consequence of multiplying the starting
arc-approximation vertex with the rotation matrix that creates each
segment step I think)... either that, or in the line thickness
applying code.
Whilst the geometry is (nearly) valid, it does tend to act to create
nearly degenerate cases to trip up the polygon code. Most 3D cad
systems apply a tolerance factor, and declare "near enough is
touching" or some such.
>> 3. Polygon routines that can (under certain circumstances - I forget
>> _all_ the details) - walk along the wrong contour, and produce
>> completely incorrect results.
>
> This (or at least part of this issue) is what I have fixed in my
> previous patch, I believe.
>
> But your changes are quite different. I'll try to find out if these fix
> the same or different issue (I have no idea just now, sorry -- similar
> parts of the code are changed, but in different way).
This is the real shame I find with my patches languishing in the
branch... I can't remember how I got to the results I had... there are
the comments in the commit messages which _try_ to explain it, but I
can't come back so many months later and recall the level of
understanding I'd got to in creating the changes.
>> Martin - I can't promise a lot of availability, but would you be up
>> for some shared effort on this (perhaps chat on IRC at some point?) to
>> try to dig to the bottom of these issues once and for all?
>
> Availability is an issue for me to. :-/ But yes, sounds good in general.
> I am not sure I will be much help just now, as I am still spending most
> of the time trying to understand existing code, but I am about to
> improve this part. :) We can at least move the discussion to private
> emails (I am not sure if anyone else in maillist is interested anymore
> at this point), IRC is OK for me too.
OK, I'm needing to finish some work at the moment (spent the day at
home waiting for a parcel - which of course, didn't arrive, then came
into the office after everyone else went home!).
>> I doubt we'll solve snap-rounding (with any elegant algorithm - unless
>> we do a mad re-write), but according to Harry Eaton's old comments- It
>> appears he thought the iterative intersection + edge splitting
>> approach taken within PCB ought to have avoided the problem.
>
> As far as I understand the current code solves the fact that we can get
> new intersection when straight line is replaced by two segments with
> integer endpoints, but 1) only intersections between A and B polygons
> are checked (not self-intersections) and 2) even if we would detect the
> self-crossing, it is not enough as we would need to do subsequent
> modification to polygon (split into more parts, change edge directions
> and add holes) in order to make the contour correct according to the
> rules. (I am not sure about consequences of such changes during
> intersection search though.)
>
> Modifying the intersection calculating code in a way it avoids
> generating self-intersecting polygons would be much nicer I think (given
> it is possible).
You are probably correct here - although you can also cheat somewhat,
and address the sources of geometry that create higher risks of
creating these situations.
Probably a two-pronged approach would be good - especially if
simplifying the geometry has benefits in reduced vertex count in the
output. (A killer for 3D cad export really, since the 3D systems get
very grumpy if you throw in lots of vertices a few nm apart from each
other along an approximated cutout shape - due to two capped lines
with about 1-2nm of rounding error producing intersections at the cap
end straight-line approximations, rather than landing exactly on each
other, creating and segments of slightly more sensible lengths).
Peter
- Raw text -