pcb-rnd knowledge pool
Planning curve support
| curves by Tibor 'Igor2' Palinkas on 2018-05-05 | Tags: developer, curve, spline, bezier |
Abstract: Planning curve support. Describe objectives and enumerate possibilities.
1. Objectives: what problem we are trying to solve
The only curve pcb-rnd supports is arc. We have full support for circular arcs and partial support for elliptical arcs. Implementing the missing code for elliptical arcs is rather difficult and the calculations are not looking efficient either, CPU-usage-wise.
The objective of this node is to research whether switching from arcs to another kind of curve can solve this problem. If such a curve algorithm is found, a later version of pcb-rnd would have these features:
- no arc object in the data model - the curve object would work for arcs
- the code (core, HIDs and non-file-format plugins) would need to deal with only one kind of curve and no arcs
- keep the arc object in the file format, as it is a real common case that is convenient when the file is written/modified manually or by 3rd party software
- loading an arc from a file would still result in the curve object in memory, flagged to be an arc
- arc-flagged curves would be edited as arcs on the GUI and would be saved as arcs in the file
- the GUI would have a curve tool for editing curves - using the curve tool on an arc-flagged curve would remove the arc flag immediately
What we expect from a suitable curve algorithm:
- can aproximate circular arc well
- can approximate elliptical arc to some acceptable level
- can easily calculate the center point and radii of an approximated arc
- doesn't require too many data (e.g. too many control points)
- preferably it stores the endpoints of the curve explicitly, as part of the data used for the interpolation (e.g. as control points; but not as extra, alien data glued onto an algorithm that otherwise doesn't need this info)
- efficient computation of intersection
- efficient rendering
- offseting, for "stroke draw"
The simpler approach is to have one curve object only the minimal set of control points and let the user combine multiple curves for a longer trace. This is how we do lines (there are no polylines). However, this wouldn't make it easy to guarantee continuity on object boundaries, which is one of the important extras curves could add.
We may need to have a multi-segment curve, that is a "polyline" kind of object with many control points. This would guarantee smoothness but would complicate calculations and would also make them more expensive because of the large bboxes.
2. non-objectives: what problem we are NOT trying to solve
We do not have to introduce curves - while they are useful in some rare cases, they are not essential features. Thus curves will not happen as an addition to the model, just for the sake of having curves. Curves can happen as an arc replacement in the model, if the resulting new model is not much more complicated than the arc based model.
3. Candidates
Cubic Bezier
Pros: intuitive editing, simple rendering
Cons: poor arc approximation: 0.027253% or 0.019608% error
Many formats (ps, svg, ttf (quadratic!)) approximate arcs with Bezier curves and live with the error. Using 2 Bezier curves per quadrant may reduce error to 4ppm but that works only if the curve object is multi-segment . However, even the above poor arc approximation works only if a Bezier is a quadrant, approximating a full circle wouldn't be possible without multi-segment curves.
Akima-spline
Pros: relatively intuitive rendering, good arc approximation
Cons: TODO
spline, B-spline
TODO