[HN Gopher] Parallel Curves of Cubic Beziers
___________________________________________________________________
Parallel Curves of Cubic Beziers
Author : raphlinus
Score : 79 points
Date : 2022-09-09 20:27 UTC (2 hours ago)
(HTM) web link (raphlinus.github.io)
(TXT) w3m dump (raphlinus.github.io)
| pcwalton wrote:
| For reference: The quick and dirty solution to make an offset
| curve of distance _l_ is to take the control cage of the original
| curve (i.e. the polyline you get by connecting every Bezier
| control point in sequence) and push out the points that make up
| control cage by the distance _l_ along each point 's normal.
| (Same way you do toon shaded outlines in games.) Since the vector
| between two cubic Bezier curves is itself a cubic Bezier curve,
| the convex hull property lets you easily compute a conservative
| error bound on this. If the error bound is too high, you can
| subdivide and repeat the process.
|
| This solution isn't as good as what Raph describes here and I'm
| providing it only for reference. :)
| raphlinus wrote:
| I'm slightly confused by this. A _point_ on a polyline doesn 't
| have a single normal, as it's incident to two edges, and in
| general those edges have two different normals. If you push out
| the _edge_ by the offset amount, that 's what Tiller and Hanson
| proposed in 1984, and one of the things I found is that it
| performs surprisingly badly. It is in common use though.
|
| 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.
| pcwalton wrote:
| Yes, I'm using the term normal in the usual graphics sense of
| a vertex normal, as the average of the normals of the
| incident edges. It's the Tiller & Hanson 1984 approach.
| raphlinus wrote:
| Gotcha gotcha. I just coded this up, and averaging the two
| incident normals performs about the same as OG Tiller-
| Hanson, slightly worse. The original version (and my
| implementation) displaces the edge, which basically means
| computing the new control point as the intersection of the
| two displaced edges. I believe there are a bunch of T-H
| variations out there, but haven't collected any evidence
| yet that they significantly improve matters.
| upwardbound wrote:
| This is super impressive! Do you need to publish an academic
| paper also, to avoid some unethical scholar "discovering" a
| slight variation of your idea without citing your blog? I don't
| know anything about how academic publishing works, and I'd hate
| to see you be deprived of credit.
| raphlinus wrote:
| I would be quite flattered by an unethical scholar plagiarizing
| from my work, it would be far better than being ignored.
|
| 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!
| version_five wrote:
| If you're like me and first got hung up on the difference between
| a parallel curve and a translation of the curve, the wikipedia
| article (literally the first link) explains it.
|
| 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.
|
| https://en.m.wikipedia.org/wiki/Parallel_curve
| Jasper_ wrote:
| A simple counterexample to imagine is a curve that represents a
| circle (or a circular arc). The parallel curve to this is a
| scaling of the circle, with a bigger/smaller radii, not a
| translation.
| jabbany wrote:
| Though the circle case is a little bit misleading, since it's
| only the same as scaling in that one case. In general,
| finding the parallel curve can't be approximated by affine
| transforms like scaling or translation, which is why it's so
| annoying.
|
| 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.
| upwardbound wrote:
| Yep. A way that helps me visualize it is that a parallel curve
| is what you need to make a set of railroad tracks. The tracks
| have to always be a constant distance apart _when measured
| along the direction locally perpendicular to the tracks - i.e.
| the direction of the train 's axle_.
| orlp wrote:
| Given this definition I think you almost never really want the
| parallel curve though (at least in computer graphics). Its
| behavior on the inside of corners is degenerate and not what
| one is looking for in almost any scenario involving curves.
|
| 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.
| upwardbound wrote:
| (Speaking as someone who likes model trains.) You need
| parallel curves to design railroad tracks. Its behavior
| inside corners is degenerate because in the degenerate case
| there's no possible way you could make a train turn a corner
| that tight! You need to take a larger radius for your turns
| if you don't want your train to end up all crashed in a mess.
| :-P
|
| 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.
| raphlinus wrote:
| I'm not sure "degeneracy" is the best way to think about
| this. If the curvature exceeds the inverse of the offset
| distance, you get a cusp, and in general you need to think
| about how to deal with those. In some cases, that will be
| boolean path operations (stay tuned for an update on
| those!). But I'm not convinced there's any shortcut where
| you can avoid dealing with these cases altogether.
| orlp wrote:
| That makes sense, I have already edited my comment to say
| specifically computer graphics since posting since I
| realized it could have very useful applications in physical
| modeling, or other scenarios where you specifically care
| about the constant distance metric, like you mention.
| upwardbound wrote:
| Nice, makes sense. I don't know much about computer
| graphics. What are some examples where you'd use
| translated curves? Are you referring to stuff like
| modeling strands of hair, and you'd make them using
| translations of a template strand's curve? Or what kind
| of problems do you typically face?
|
| 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)
| pcwalton wrote:
| The easiest way to understand an offset curve is that it's one
| side of the shape you get by "stroking" along the source curve,
| in the SVG sense. Join two offset curves together (one for each
| side), cap off the ends somehow, and you have the entire shape
| of a stroked path. It's easy to see how this isn't the same as
| just translating the path.
|
| 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.
| jabbany wrote:
| The "perpendicular to that point" is rather better defined as
| "perpendicular to all tangents at that point on the source
| curve".
| coffeeaddict1 wrote:
| Interesting! I remember running up into the same problem when I
| was trying to recreate a way to simulate pen ink strokes
| digitally but eventually gave up because it was quite difficult
| to get something working in all cases.
|
| 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?
| raphlinus wrote:
| Yes. The core curve-fitting technique is very general and can
| be adapted to any scenario where you can sample the desired
| curve (with normals) and compute a couple of numerical
| integrals on it. I am confident that includes variable-width
| strokes, though I also imagine it will be a nontrivial amount
| of work to make everything fit together in a satisfying
| fashion.
| Ensorceled wrote:
| As a co-op student in the 80's I needed to solve this problem in
| Fortran IV for a CAD/CAM system that ran CNC milling machines
| that created shoe molds. This really brings back memories.
|
| 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.
| flaminghero wrote:
| For quadratic beziers, another approach I've seen is described
| here
| https://microbians.com/math/Gabriel_Suchowolski_Quadratic_be...
| (similarly here as well
| https://blend2d.com/research/precise_offset_curves.pdf). I've
| used this in the past for a hobby project with very good
| performance and results.
|
| Since a cubic bezier can always be approximated by quadratics
| maybe that approach could also be used.
| raphlinus wrote:
| Yes, and I should probably add those links. Quadratics get you
| O(n^4) scaling, which is pretty good. Figuring out where to put
| the control point is easy, there's basically only one place it
| can go if you want to preserve tangents. Deciding where to
| subdivide is a little trickier, and Suchowolski's approach
| looks pretty good to me. You do still need to deal with cusps
| though.
|
| 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.
___________________________________________________________________
(page generated 2022-09-09 23:00 UTC)