← Back to team overview

kicad-developers team mailing list archive

Re: Bump for arc tracks


I was missing the piecewise linear approximation of the higher order shapes part.

I don't know the answer.

My instinct is that for arcs the direct analytic tests for proximity and intersection are faster tests on an accurate piecewise linear approximation. But on the other hand, if you only have one datatype (triangles) then it's easier to push the calculation onto a GPU.

On 1/07/17 12:57, Greg Smith wrote:
I don't think you are missing anything. I was thinking that converting everything to line segments might make DRC faster. I haven't dug into the DRC code, but perhaps it relies on collision functions provided by the shape type itself (which theoretically could be either "true" arc calculations, or could be calculated with cached converted-to-line-segments shape if needed). If this is the case, maybe there's nothing substantial to do regarding my comment.

Greg S.

On Jun 30, 2017, at 6:24 PM, hauptmech <hauptmech@xxxxxxxxx> wrote:

Interesting idea. It might be a false comparison since we are choosing between a line segement chain and a curve segement chain composed of only lines.

For the maths aspect, the computational speed is equal.

For optimizations involving memory footprint and data structure traversal speed, I'm not able to come up with any that can only be done on the line segement chain and not on a curve segament chain.

Am I missing something?

On 30/06/17 23:57, Greg Smith wrote:
Is SHAPE_LINE_CHAIN a core element that potentially an ARC might be translated to for display, DRC, or other output needs? If so, it seems that they would be separate with a conversion function from ARC to SHAPE_LINE_CHAIN and there would be SHAPE_ARC_CHAIN or SHAPE_SEGMENT_CHAIN (or similar) that would contain both straight lines and arcs (and other non straight shapes).

Main point: seems like a structure for only straight lines would facilitate the speed other features and analysis.

Greg S.

On Jun 30, 2017, at 6:47 AM, hauptmech <hauptmech@xxxxxxxxx> wrote:

At first glance it looks like SHAPE_LINE_CHAIN and TRACK  are the points where the development clings to straight lines the most.

One could add a single variable to line segment data structures so that they could also represent arcs.


One could add a layer of abstraction so that curves and areas were piecewise constructs of whatever curve segments get implemented. (arcs, ellipsoids, spirals, splines, fractals, etc). SHAPE_LINE_CHAIN and TRACK would be lists of curve segments rather than lists of line vertices as they are now.

I'd hesitate to start anything without some support for the full picture.

On 30/06/17 21:11, Tomasz Wlostowski wrote:
On 30.06.2017 11:05, hauptmech wrote:
I asked earlier this year whether there was any interest in arc tracks
and got little response.

My use case was importing altium files.

Are any of the core developers likely to accept work in this direction?

Sure, it would be awesome if someone could work on it. It's not in the
plans for the 5.0 release, although some base code for handling arc
tracks could be already written: geometry functions that we'll need for DRC:

- implement a SHAPE_ARC for the geometry library, describing a non-zero
thickness arc
- write an arc to segment collision function (see SHAPE::Collide)
- write an arc to arc collision function.


Mailing list: https://launchpad.net/~kicad-developers
Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
Unsubscribe : https://launchpad.net/~kicad-developers
More help   : https://help.launchpad.net/ListHelp