Control points of offset bezier curve
If I have a cubic Bezier segment specified by two endpoints and two control points, how can I find an offset curve which is "parallel" to the original at some given distance, after i have determined the other 2 endpoints?
The red dots in the image are the endpoints, and the red squares are the control points of the initial bezier segment. Everything red is known, and i need to find the blue squares, that is, the control points of the second curve, such that the second curve is parallel to the first one(must also take into account that the dimension varies, as if it was below the original bezier, the second curve would be smaller).
I am sorry for the graphics of the image, it has only a illustrative purpose and i am not good at drawing. Thank you for the help!
Solution 1:
The simplest heuristic approximation method is the one proposed by Tiller and Hanson. They just offset the legs of the control polygon in perpendicular directions:
The blue curve is the original one, and the three blue lines are the legs of its control polygon. We offset these three lines, and intersect/trim them to get the points A and B. The red curve is the offset. It's only an approximation of the true offset, of course, but it's often adequate.
If the approximation is not good enough for your purposes, you split the curve into two, and approximate the two halves individually. Keep splitting until you're happy. You will certainly have to split the original curves at inflexion points, if any, for example.
Here is an example where the approximation is not very good, and splitting would probably be needed:
There is a long discussion of the Tiller-Hanson algorithm plus possible improvements on this web page.
The Tiller-Hanson approach is compared with several others (most of which are more complex) in this paper.
Another good reference, with more up-to-date materials, is this section from the Patrikalakis-Maekawa-Cho book.
For even more references, you can search for "offset" in this bibliography.
Solution 2:
I keep on doing jobs that involve path offsets
I've set out more roads and machine tooling paths than I can count, and now I'm designing font glyphs! So perhaps I can help.
I just implemented my own method, similar to the Tiller-Hanson algorithm. They don't seem too difficult to come up with -- almost not worth tying anyone's name to the algorithm!
The above answer is already pretty good so I'll just describe mine as a variation on Tiller-Hanson.
First,
Let C be the intersection of the red tangents.
Let D, E, F be the points that generate A, B, C when the hull is offset.
Let b and r be tangent points at the left-hand ends.
(b & r for blue and red, and lower case to avoid conflict)
Notice in the diagram that position of A on the line (r, C) is proportionately much less than its blue equivalent, the position of D on the line (b, F).
In other words, the ratio (A - r) : (C - r) has visibly decreased, as this particular offset occurs.
The difference is simply that my ratio stays constant.
For the quadratic case this turns out to be identical to Tiller-Hanson; the control point is simply the intersection, and the ratio remains 1:1 in both algorithms.
In cubic (or greater) cases I believe it has some advantages. The resulting operation on the hull is actually much simpler than a linear offset to implement, and it seems better in many ways that when the curve is offset in the inward direction, the control lines never vanish until the curve itself does.
Of course the two methods share many dangers in common, like most offsetting algorithms. Both methods really require a bit of curve subdivision first, to make them more accurate, and in both, you still have to cope with vanishing path segments. In fact for a cubic or greater order, subdivisions of the curve can vanish too.
In my current Javascript/SVG implementation, I have yet to account for vanishing path segments and so I am limited to 'small' offsets or carefully designed paths. (This is fine for my use in font creation, for now.)
I recommend (but have yet to implement) reducing the orders of subdivisions to below that of the whole curve. Yes, it compromises accuracy before it's strictly necessary, but in a computationally very sensible way.
This section will be edited down once I can comment. I haven't been on this particular 'stack' site for long.
I usually try not to respond to other answers but as I already based mine on the above, and called it 'pretty good' I will take issue with three things.
Keep splitting until you're happy.
Well, that sounds dangerous for at least some of us, who have yet to implement a way to deal with vanishing path segments on an inward offset. Subdivisions near the ends of the curve can cause serious problems if they're comparable to the size of the offset.
Perhaps we should mention that not many subdivisions should be necessary to make the curve look "excellent".
You will certainly have to split the original curves at inflexion points, if any, for example.
No you won't certainly have to, and identifying inflexion points involves square roots; we don't know how performance-critical this code is.
And lastly, at least the first link is poor quality. It opened a rudely obtrusive aspx page that kept opening other tabs and windows! Sorry for the criticism; perhaps it's gone downhill and could be revised; maybe the others are better and it was just bad luck that the first one put me off them all. But I'm sure there's better out there. It was hard to read even when I could keep the focus on it!
Otherwise thankyou. Great diagram, it's concise compared to mine, and has good searchable terms and names that will probably benefit me even after years of thinking I was good at this.
Solution 3:
An offset curve to a cubic Bézier curve is not a Bézier curve. There are approximations but not an exact polynomial solution.
On the other hand, if you want to translate the original Bézier curve, then it is enough to translate the control points.
Solution 4:
May be you get interested with my paper about to offset a quadratic bezier
Quadratic bezier offsetting with selective subdivision
Gabriel Suchowolski, Jul 10, 2012
http://i.stack.imgur.com/bZS7a.png
Here: http://microbians.com/?page=math