Parallel Curves of Cubic Béziers
raphlinus.github.io
raphlinus.github.io
My understanding is that a parallel curve is what you get if you dilate the curve with a circle, ie the curve along the furthest extent of the dilation (see the picture in the wikipedia article) which evidently is not the same as just translating the curve down.
More precisely, it's the curve you get by taking each point (of which there are infinitely many) on the source curve, tracing out a line of some constant length l along the line perpendicular to that point on the source curve, and joining each such new point together.
I assume there's a way to mathematically identify the points that form these unwanted loops, so they can be discarded when drawing the parallel curve - but my maths skills aren't up to the job this morning.
Also this is surprisingly relevant in a lot of weird places. First I encountered this was trying to create a closed polygon "outline" based on a vector graphics font -- the idea was to approximate the concept of "stroke width" on a platform that could not understand strokes and instead only worked with filled polygons.
So while the authors work is certainly impressive, I would keep looking for a more useful definition and implementation of 'curve alongside another curve' than that of the 'parallel curve' (as mathematically defined in the linked Wikipedia article) before using this.
Here's a nice example of a model railroad track plan: https://www.scarm.info/layouts/track_plans.php?gallery=10;0
There's software to help with designing these plans, which I guess must use parallel curves under the hood.
Is there some kind of "compromise" option that uses parallel curves where possible but falls back to translated curve segments when there's a degeneracy? (If that would be useful at all - I have no idea)
Siemens PLM / D-Cubed PGM component is one example of such software.
It's used for the offset function in the sketcher in Siemens PLM own NX/SolidEdge and also in SolidWorks.
> PGM automatically generates valid 2D offset profiles on points, lines, circles, ellipses, splines, general parametric curves, and offset curves.
> Gaps that arise between adjacent edges in an offset loop are automatically capped using a choice of capping techniques. Offset edges that shrink to zero length/radius, and any intersecting geometry is automatically trimmed, including self-intersecting offsets, offsets ellipses, and splines.
https://www.plm.automation.siemens.com/global/en/products/pl...
Disclaimer worked on the predecessor of that code as D-Cubed from 1995-2000.
As a side note, historically, in the Cambridge (UK) school of 3D mechanical CAD, BRep modeling (Parasolid, Acis) the approach to offset (aka parallel) surfaces (and later offset curves with the PGM) has been procedural - thus an offset surface is a pointer to an underlying surface plus a signed offset value. Accordingly, there would be no conversion to Cubic Béziers - all the modelling operations would be made to work with the procedural offset directly. Pretty much all exotic geometry had to be procedural to meet accuracy requirements - that is before the introduction of "Tolerant modeling" in Parasolid around 1992. So, for example, a Rolling ball blend (ie. a constant radius fillet) surface was procedural and had pointers to offset surfaces, which were also procedural. The advantage was accuracy, but the disadvantage was poor performance.
For "corners" on non-smooth curves usually there's some kind of way to resolve the degenerate (or rather, undefined) behavior. Usually this would be something like a stroke-cap property.
The two have to be different: a cap is a fixed piece of geometry, a join style calculates geometry based on the segments it joins.
Others pointed out stroking, and in graphics stroking isn’t just common, it’s ubiquitous and you’re using it right now, because fonts are stroked as are lots of your browser features (I can see stroked rounded edge on my comment edit box, in addition to strokes on vector based SVG icons sprinkled on my screen). Most/all paint and drawing apps have stroked paths, etc., like Photoshop & Illustrator. All the online “whiteboards” use stroked paths. These are all offset curves or parallel curves according to the above definition. 3d graphics uses offset curves too for hair rendering, rigging & simulation, just as one example.
Fonts want this a lot.
It helps more to think about this in terms of a closed curve. If you have an arbitrary closed cubic curve, what does it mean to make it "bigger", "smaller", "thicker", "thinner", etc. For example, a blob sticking out eventually needs to get "flattened" as you shrink the curve.
A lot of the problem with 2D graphics currently is simply that we don't have good underpinning theory and, especially, definitions like we do for 3D graphics. If you don't even agree on what things mean, you can't generate a theory for how to do them.
So, while the translation of a curve is pretty simple the parallel curve can get tricky to deal with analytically.
A good source for this kind of stuff is also Knuth' work on Metafont, even if Metafont iself completely side-steps these issues by just painting many circles along the original curves to produce the parallel.
Could this approach be extended to variable thickness offsets? I mean can you setup an initial offset and a final offset and then interpolate between them along the curve?
My solution was ... not as elegant ... and would fall firmly into the category of "Thus, in practice the approach is almost always to compute an approximation to the true parallel curve."
Luckily I could cheat because, given the domain, the paths were never pathological; though this solution falls apart in the worst cases as well or, I should say, falls apart in a way that wouldn't work for a a machining path or similar problem domain.
I’m curious because I could imagine it’s possible to optimize for the shape of a parallel curve without matching the parameterization at all. You mentioned the parameterization difficulty with cusps, so I’d guess the solution would need to handle discontinuous parameterizations? You could ignore cusps and degenerate cases in my question above and assume continuity…
I could add a correspondence visualization (I thought about something similar when describing the error measurement technique), but you can also see it pretty clearly by looking at the lengths of the control arms. That's easiest to see when accuracy is set to infinity.
I'll probably implement this, as it's very likely what you want in the variable font case.
Since a cubic bezier can always be approximated by quadratics maybe that approach could also be used.
You can of course change curve representations (I did that with the Euler approach), but there are downsides. Just how bad depends on the application. One place where you really want to stay in a cubic representation is in a font or vector graphics editor. If you just want to add a little weight to the font, ideally you don't want the structure to change, or lots of new control points to appear. In other applications it might be fine though.
The actual conversation about motivation to publish a paper is a fairly deep topic. In this particular case, I do think it's worthwhile for a variety of reasons:
* The literature dates back about 40 years, and no really good solution has been published.
* The most commonly cited survey paper is possibly fundamentally wrong.
* One of the most commonly cited and used techniques is surprisingly bad.
* The curve-fitting technique I propose probably has many other applications; in the best case, it could potentially open up a new field of study.
So part of my motivation for publishing the blog post is to see if I can recruit a partner in crime, someone who has incentive for publication in academic circles. We'll see!
https://faculty.engineering.ucdavis.edu/farouki/wp-content/u...
You take the intersection point of the curves's handles and offset curve's handles. Then you calculate the distances from these points to the curve's/offset curve's end points and use these distances to scale the handles of the offset curve.
Here is the code, reformatted so you can basically copy it into your existing code. It should require fewer subdivisions than TH, but more than shape control and your impressive solution.
// This function needs to go into the Point class
scale(s) {
return new Point(this.x * s, this.y * s);
}
handle_scaling() {
// p: points on original curve
// q: points on offset curve
const deriv = this.c.deriv();
const p0 = this.c.p0();
const p1 = this.c.p1();
const p2 = this.c.p2();
const p3 = this.c.p3();
const q0 = p0.plus(this.eval_offset(0));
const q3 = p3.plus(this.eval_offset(1));
const tan0 = deriv.eval(0);
const tan3 = deriv.eval(1);
// s: intersection of handle vectors
const sp = ray_intersect(p0, tan0, p3, tan3);
const sq = ray_intersect(q0, tan0, q3, tan3);
// r: ratios of distances from handle intersection to end points
const r0 = sq.dist(q0) / sp.dist(p0);
const r3 = sq.dist(q3) / sp.dist(p3);
// calculate control points of offset curve
let q1;
let q2;
if (r0 > 0 && r3 > 0) {
q1 = q0.plus(p1.minus(p0).scale(sq.dist(q0) / sp.dist(p0)));
q2 = q3.plus(p2.minus(p3).scale(sq.dist(q3) / sp.dist(p3)));
} else {
q1 = p1.minus(p0).plus(q0);
q2 = p2.minus(p3).plus(q3);
}
return CubicBez.from_pts(q0, q1, q2, q3);
}This solution isn't as good as what Raph describes here and I'm providing it only for reference. :)
If you're talking about a variation of that where you choose some other concept of "normal" relevant to the point, I'd be interested to learn more.
Or perhaps the definition of the curve should be more strict (e.g. the result should contain only points that are exactly at distance x from the given path)
If you imagine dragging an eraser across the 'roadway' produced by the parallel lines, you'll see that the solution with the cusp still obeys the constraint that the lines are a constant distance apart for every point along the road, it's just that it turns so tight your eraser needs to turn in place at the corner.