kicad-developers team mailing list archive

[Lorenzo Marcantonio <l.marcantonio@xxxxxxxxxxxx>]

On Sun, Apr 21, 2013 at 07:14:16PM +0200, Lorenzo Marcantonio wrote:
> When comparing distances, yes, that would be a good idea, it's a common
> trick (IIRC it's already done that way during track editing). That
> aside, for what reason should be pcbnew computing distances during
> redraw? Shouldn't a bounding box check suffice for drawing purposes?

OK, self correction I'm an idiot for asking this question :D in about 5 second
of log reading it's evident that's the clipping routine that's using all these
distances (it was added since the OS one had numerical stability issues,
right?).

The relevant partial stack I'm referring to is this:

                0.62    2.32 11652020/11652020     clipLine(EDA_RECT*, int&, int&, int&, int
[8]     51.8    0.62    2.32 11652020         TestForIntersectionOfStraightLineSegments(int,
                1.25    0.89 46579996/46579996     GetPointToLineSegmentDistance(int, int, i
                0.16    0.00 6882403/6890528     FindLineSegmentIntersection(double, double,
                0.02    0.00 3160418/49782402     InRange(double, double, double) [31]

In clipLine the relevant 'easy' culling seems to be done correcty: first a
boundary check, then the trivial but common horizontal/vertical processing.

The general case however seems to be easily reworkable in something better
(*if* the distance checking is what bother you): it test for intersection of the line with the four boundary segments. This is 'slow' for two reasons:

1) It's easy to see if the intersection needs to be computed;
   if you keep x1 <= x2 and y1 <= y2 (a simple regularizing swap at the beginning)
   it's trivial to see that you only need to check with the upper size *only*
   when y1 < minY, and so on.

2) The intersection of a line with an horizontal or vertical line is a much easier thing to
   do than the general case

Another thing: the TestForIntersectionOfStraightLineSegments *can* return the
distance (that was my doubt, why it does that?:P). However these are passed as
optional pointer and only *assigned* if the pointer is not null. It compute the
distance even if it's not requested. Other than that it seems strange to me,
there shouldn't be so many cases for intersection, but I'm a little rusty with
vector algebra :D

If you want that optimization I think these are the place to look into. The
clip routine is a little easier, reworking the intersection test seems more
demanding (especially if it's not done the way you're used to do it!)

Also, for a true-and-tried line clipper look for the Cohen-Sutherland one
(source on wikipedia), it's mostly pluggable in you want to do some performance
tests (you should keep the trivial case to avoid loop into them with the
Sutherland clipper). Still from wikipedia a 'better' (from a vector algebra
viewpoint) is the Liang-Barsky (the parametric form is used elsewhere in
pcbnew). Testing is advised since the pcbnew workload is not exactly 'typical' (lot of horizontal, vertical and mostly 45 degrees lines).

Have fun XD (surely funnier than tracking the AGC glitch on the project I'm working on:((()

-- 
Lorenzo Marcantonio
Logos Srl