Content deleted Content added
mNo edit summary |
Tags: Reverted Newcomer task |
||
Line 106:
Another efficient algorithm for offsetting is the level approach described by
[[Ron Kimmel|Kimmel]] and Bruckstein (1993).<ref>{{cite journal | last1=Kimmel | first1=R. | last2=Bruckstein | first2=A.M. | title=Shape offsets via level sets | journal=Computer-Aided Design | publisher=Elsevier BV | volume=25 | issue=3 | year=1993 | issn=0010-4485 | doi=10.1016/0010-4485(93)90040-u | pages=154–162 | s2cid=8434463 |url=https://www.cs.technion.ac.il/~ron/PAPERS/offsets_cad1993.pdf}}</ref>
The problem of parallel or offset curves has remained challenging for a long time. Parallel curves have applications in 2D graphics (for drawing strokes and also adding weight to fonts), and also robotic path planning and manufacturing, among others. The exact offset curve of a cubic Bézier can be described (it is an analytic curve of degree 10) but it is not tractable to work with. Thus, in practice, the approach is almost always to compute an approximation to the true parallel curve. A single cubic Bézier might not be a good enough approximation to the parallel curve of the source cubic Bézier, so in those cases, it is subdivided into multiple Bézier segments.
A number of algorithms have been published, of varying quality. Many popular algorithms aren’t very accurate, yielding either visually incorrect results or excessive subdivision, depending on how carefully the error metric has been implemented. A modern technique based on curve fitting has been proposed, which tries to find the cubic Bézier that’s closest to the desired curve. This approach applies an array of numerical techniques to make it work, resulting in a visibly more accurate curve even when only one Bézier is used, and a minimal number of subdivisions when a tighter tolerance is applied. In fact, this technique claims O(n^6) scaling: if a curve is divided in half, the error of the approximation will decrease by a factor of 64.
The Euler spiral technique is another approach, which will in general produce considerably more subdivision (with O(n^4) scaling), but it has its advantages. Once the curve is in piecewise Euler spiral form, a result within the given error bounds can be computed directly, with no need to explicitly evaluate an error metric. In addition, the cusps are located robustly with trivial calculation. However, getting a curve into piecewise Euler spiral form is still challenging, and the prototype code uses a rather expensive error metric to achieve that.
This curve fitting technique is quite general and can be adapted to generalized strokes, path simplification, distortions, and other transforms, conversion from other curve representations, accurate plotting of functions, and other applications. The main thing that’s required is the ability to evaluate area and moment of the source curve, and ability to evaluate the distance to that curve (which can be done readily enough by sampling a series of points with their arc lengths).
== Parallel (offset) surfaces ==
| |||