X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f X-Recipient: geda-user AT delorie DOT com X-Original-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=zWhlMQMV8BEdi0Pjfz3PiIvmp3FIk4Em1bruoOdEPyg=; b=T0K9KGth0JHYNi6rA/hTAH+NXBSGQGP8BOnM8ABGARrkVbz4iK2BafTEgoCJOVveN0 kIsxsUCND+brLJSysIKMnjeUD+ZQ/yPWYhC/QuDQJYgeCoGvXljDBIjMd8LMYt9RhvMd 5i9NVVEr38JJHbkmnIT9iLwi5NoeofDHsugIIBgxeF/1FA4joDmWfws24hrCASAy4ldz eQoepe1JtAuk/5l6xfRqiGGLXO/IDV1SxK+P4PbmR8omj+808Kf50LiExiXzW/m1kxk9 gC2ToX5NGb9IRHF17i2JWXThBD0V8Yj1Sey0zFAUEBATGvPu+dO0k0HmYbnSnT2Egdv8 zbfQ== MIME-Version: 1.0 X-Received: by 10.60.97.2 with SMTP id dw2mr11947435oeb.40.1450823614730; Tue, 22 Dec 2015 14:33:34 -0800 (PST) In-Reply-To: <20151222215730.GQ14853@abax> References: <20151222144719 DOT GN14853 AT abax> <20151222184519 DOT GO14853 AT abax> <20151222215730 DOT GQ14853 AT abax> Date: Tue, 22 Dec 2015 22:33:34 +0000 Message-ID: Subject: Re: [geda-user] Self-intersecting polygon appears because of intersection coordinates rounding From: "Peter Clifton (petercjclifton AT googlemail DOT com) [via geda-user AT delorie DOT com]" To: gEDA User Mailing List Content-Type: text/plain; charset=UTF-8 Reply-To: geda-user AT delorie DOT com Errors-To: nobody AT delorie DOT com X-Mailing-List: geda-user AT delorie DOT com X-Unsubscribes-To: listserv AT delorie DOT com Precedence: bulk On 22 December 2015 at 21:57, Martin Beranek 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