Tiller-Hanson bezier offsetting

[ecs]

I'm in a situation where I need an approximation of the offset of
bezier curves (the resulting approximation must also be a bezier, and
must have the same number of control points as the original curve -ie:
no more subdivision-). I've implemented this by offsetting the control
polygon, what I believe is the "Tiller-Hanson" algorithm.

However, I haven't found an "official explanation" on *how* to offset
the bezier control polygon in the Tiller-Hanson algorithm. Even their
original paper doesn't mention how to offset the polygon, they just
tell they offset it, but not *how* (maybe that's because they're
talking of NURBS rather than beziers).

The only method I found comes from Jacques De Schepper here at
comp.graphics.algorithms:

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=B861EDFE.AFBB%25jacques.deschepperNOSP%40Martwork-systems.com

That's the procedure I used. However, it can fail: the problem is at
offsetting the middle edge (the p2p3 edge if the bezier is p1p2p3p4),
because the right side for offsetting is not always given by a
rotation of +90 degrees. If the control polygon has a
self-intersection, the right angle is -90. And, unfortunately, the
right angle can also be -90 even if there's no self-intersection.

My bezier curves never self-intersect, but their control polygons can.

Any help greatly appreciated!

[Richard J Kinch]

Post by ecs
Any help greatly appreciated!

<http://groups.google.com/groups?q=parallel+bezier+author%3Akinch>

[ecs]

Post by Richard J Kinch

Post by ecs
Any help greatly appreciated!

<http://groups.google.com/groups?q=parallel+bezier+author%3Akinch>

Thank you.

Btw, in order to implement your approach, do you happen to have the
closed form for the following problem?:

Given (P1, P4, L, a, b, v) compute P2 and P3 so that together with P1
and P4 constitute the complete set of control points P1,P2,P3,P4 for
the bezier curve.

Where,

L=Midpoint in the bezier (ie: for t=0.5)
a=Unitary vector in the P2-P1 direction
b=Unitary vector in the P3-P4 direction
v=Unitary vector tangent to the bezier at L (ie: for t=0.5)

I've been trying to arrive to an elegant solution, but the only
practical way I found is by computing line intersections. If you have
an elegant closed form, I'd like to know.

TIA

[Richard J Kinch]

Post by ecs
I've been trying to arrive to an elegant solution, but the only
practical way I found is by computing line intersections. If you have
an elegant closed form, I'd like to know.

Been a while since I solved and coded that. I recall it was 2 linear
equations in 2 unknowns, so you may have reached the same solution.

[nopa]

Post by Richard J Kinch

Post by ecs
I've been trying to arrive to an elegant solution, but the only
practical way I found is by computing line intersections. If you have
an elegant closed form, I'd like to know.

Been a while since I solved and coded that. I recall it was 2 linear
equations in 2 unknowns, so you may have reached the same solution.

I believe it's not possible to solve the problem as defined by ecs: In
general there's no solution if you also constrain the tangent at the
midpoint, unless you let the "midpoint" happen at a generic t rather
than t=0.5.

If you constrain P1, P4, as well as the midpoint at t=0.5, the tangent
at t=0.5, and the tangents at P1 and P4, you're constraining too many
things. Either you raise the midpoint tangent requisite, or you allow
it to happen at a generic t.

My reasoning is as follows: If you fix P1, P4 and their respective
tangents, and you also fix the midpoint position at t=0.5, then
there's a unique solution for P2 and P3 without specifying the tangent
at t=0.5 (in other words, you don't have control over such tangent).

[Richard J Kinch]

Post by nopa
If you constrain P1, P4, as well as the midpoint at t=0.5, the tangent
at t=0.5, and the tangents at P1 and P4, you're constraining too many
things. Either you raise the midpoint tangent requisite, or you allow
it to happen at a generic t.
My reasoning is as follows: If you fix P1, P4 and their respective
tangents, and you also fix the midpoint position at t=0.5, then
there's a unique solution for P2 and P3 without specifying the tangent
at t=0.5 (in other words, you don't have control over such tangent).

Nope. You have two unknowns, the length of the tangents. Various
combinations of those lengths will send the curve through the specified
midpoint. You need another constraint, the angle of tangency at the
midpoint.

Richard J Kinch
http://www.truetex.com/bezier.htm

[nopa]

Post by Richard J Kinch

Post by nopa
If you constrain P1, P4, as well as the midpoint at t=0.5, the tangent
at t=0.5, and the tangents at P1 and P4, you're constraining too many
things. Either you raise the midpoint tangent requisite, or you allow
it to happen at a generic t.
My reasoning is as follows: If you fix P1, P4 and their respective
tangents, and you also fix the midpoint position at t=0.5, then
there's a unique solution for P2 and P3 without specifying the tangent
at t=0.5 (in other words, you don't have control over such tangent).

Nope. You have two unknowns, the length of the tangents. Various
combinations of those lengths will send the curve through the specified
midpoint. You need another constraint, the angle of tangency at the
midpoint.

Let A(Ax,Ay) be the tangent at P1
Let B(Bx,By) be the (inverted) tangent at P4

Then, P2 = P1 + m*A
and P3 = P4 + n*B

If we constrain the t=0.5 coordinates at L(Lx,Ly), we can apply the
bezier midpoint subdivision rule, and so we get this equation:

L = 0.5*P1 + 0.5*P4 + 0.375*m*A + 0.375*n*B

So, our two unknowns are m and n. They're scalars, but it's a
vectorial equation, so in 2D it's actually two equations with two
unknowns:

Lx = 0.5*P1x + 0.5*P4x + 0.375*m*Ax + 0.375*n*Bx
Ly = 0.5*P1y + 0.5*P4y + 0.375*m*Ay + 0.375*n*By

We have two equations with two unknowns. There's no reference at all
to the midpoint tangent in these equations, so it's not possible to
control it. The solution for P2 and P3 is already unique.

Maybe if we subdivide at a generic t rather than t=0.5, we might be
able to control that tangent.

[Gernot Hoffmann]

Post by Richard J Kinch

Post by nopa
If you constrain P1, P4, as well as the midpoint at t=0.5, the tangent
at t=0.5, and the tangents at P1 and P4, you're constraining too many
things. Either you raise the midpoint tangent requisite, or you allow
it to happen at a generic t.
My reasoning is as follows: If you fix P1, P4 and their respective
tangents, and you also fix the midpoint position at t=0.5, then
there's a unique solution for P2 and P3 without specifying the tangent
at t=0.5 (in other words, you don't have control over such tangent).

Nope. You have two unknowns, the length of the tangents. Various
combinations of those lengths will send the curve through the specified
midpoint. You need another constraint, the angle of tangency at the
midpoint.
Richard J Kinch
http://www.truetex.com/bezier.htm

Yes, this seems to be a good approximation (resumed):
Shift P1 to Q1 by d in normal direction.
Shift P4 to Q4 by d in normal direction.
Shift Pc for t=0.5 to Qc by d in normal direction.
Calculate the slope in Pc and force the new curve to hit Qc with
the slope of Pc. This is done by multiplying the original tangents
in P1, P4 by factors k1 and k4 (which are near to 1 if d is small)
and by using them as new tangents in Q1,Q4.
The factors k1 and k2 can be calculated by solving two linear
equations. But the evaluation of the formulas is tedious (I don´t
have them, so far). Furtheron, if the curve is a straight line
then the solution is not unique. This would lead to an ugly
special case handling.

Opposed to the method as quoted by the OP, this algorithm looks
reasonable for S-like curves as well, if d is not too large.

Best regards --Gernot Hoffmann

[Jack D]

Yes, this seems to be a good approximation (resumed): Shift P1 to Q1 by
d in normal direction. Shift P4 to Q4 by d in normal direction.
Shift Pc for t=0.5 to Qc by d in normal direction.
Calculate the slope in Pc and force the new curve to hit Qc with
the slope of Pc. This is done by multiplying the original tangents
in P1, P4 by factors k1 and k4 (which are near to 1 if d is small)
and by using them as new tangents in Q1,Q4. The factors k1 and k2 can
be calculated by solving two linear
equations. But the evaluation of the formulas is tedious (I don´t
have them, so far). Furtheron, if the curve is a straight line then the
solution is not unique. This would lead to an ugly
special case handling.
Opposed to the method as quoted by the OP, this algorithm looks
reasonable for S-like curves as well, if d is not too large.

This method seems to be more accurate than Tiller Hanson (as the
constraints are visually more restricting). If the quality resulting
from the algorithm isn't accurate enough for your needs, you could add
some adaptive error checking. The check I use calculates points for a
predefined set of t-values and checks the distance between them. It
cuts the bezier at the biggest error value and iterates over both parts.

A lot depends on the quality vs performance ratio you require. In any
case it makes sense to preprocess trivial cases (quarter-ellipse shaped
beziers and all cases with collinear control points).

If you require excellent precision and performance is no issue (e.g.
all offsets are done in precalculation) the best way in my experience
is to approximate the original bezier by a polyline, offset the
polyline and use an iteration method to find the best-fitting
combination of curves and lines. An excellent paper in this regard is
'A Bezier Curve Builder Implemented in APL2' by Gustav Tollet. Despites
some fine-tuning this algorithm provides excellent results.

[ecs]

Post by Gernot Hoffmann
Calculate the slope in Pc and force the new curve to hit Qc with
the slope of Pc. This is done by multiplying the original tangents
in P1, P4 by factors k1 and k4 (which are near to 1 if d is small)
and by using them as new tangents in Q1,Q4.

I followed the steps of nopa and it seems it's not possible to achieve
this pass you describe: If your unknowns are k1 and k4, and you force
the curve to hit Qc at t=0.5, then you already have two equations with
two unknowns without using the slope, because if you subdivide a
bezier in its midpoint, such midpoint must verify the de Casteljau
geometric construction (see Foley/VanDam page 508). Since the equation
which expresses L4 as a linear combination of P1,P2,P3,P4 is a
vectorial equation, in 2D it's actually 2 equations, and you have two
unknowns.

So it seems nopa is right: If the tangents in P1 and P4 are
constraints, then there's a unique pair of P2 and P3 which will make
the curve pass through a given point at t=0.5.

[Gernot Hoffmann]

Post by ecs

Post by Gernot Hoffmann
Calculate the slope in Pc and force the new curve to hit Qc with
the slope of Pc. This is done by multiplying the original tangents
in P1, P4 by factors k1 and k4 (which are near to 1 if d is small)
and by using them as new tangents in Q1,Q4.

I followed the steps of nopa and it seems it's not possible to achieve
this pass you describe: If your unknowns are k1 and k4, and you force
the curve to hit Qc at t=0.5, then you already have two equations with
two unknowns without using the slope, because if you subdivide a
bezier in its midpoint, such midpoint must verify the de Casteljau
geometric construction (see Foley/VanDam page 508). Since the equation
which expresses L4 as a linear combination of P1,P2,P3,P4 is a
vectorial equation, in 2D it's actually 2 equations, and you have two
unknowns.
So it seems nopa is right: If the tangents in P1 and P4 are
constraints, then there's a unique pair of P2 and P3 which will make
the curve pass through a given point at t=0.5.

By appearance such a geometrical solution seems to exist.
Changing just one tangent length allows to hit Qc. One degree of
freedom is left.

Perhaps this assumption is wrong: Qc is at t=0.5 on the new curve.
Correct is the demand: the slopes in Pc and Qc are equal.

But how to solve this ?

Best regards --Gernot Hoffmann

[Gernot Hoffmann]

Post by ecs
I'm in a situation where I need an approximation of the offset of
bezier curves (the resulting approximation must also be a bezier, and
no more subdivision-). I've implemented this by offsetting the control
polygon, what I believe is the "Tiller-Hanson" algorithm.
...

In previous discussions it became obvious that this method doesn´t work:

The control points are called P0,P1,P2,P3
1. Shift P0 orthogonally to Q0 by e
2. Shift P3 orthogonally to Q3 by e
3. Shift Pc orthogonally to Qc by e (c means midpoint for t=0.5)
4. Retain slope at Pc for Qc

The bug: the equivalent value t on the new trajectory Q is NOT at 0.5.

Now a solution:

Use 1-4 . But allow a variation dt for t.
The tangent lengths at Q0 and Q3 are varied by dk0 and dk3.
(tangent lengths multiplied by 1+dk0 and 1+dk3).

The variation for the trajectory is found by

X = A*t^3 + B*t^2 + C*t + P0

dX = [dA*t^3 + dB*t^2 + dC*t] + [3*t^2*A + 2*t*B + C ]*dt

"d" is the delta symbol for variations. t is 0.5 in [].
Variations dA, dB, dC are executed by dk0 and dk3.

The correction for the slope is applied similarly, maybe a
little tricky. The variation is done by linearization.
In fact only t is linearized.

This results in 3 linear equations for dk0, dk3 and dt.

Some examples are here in chapter 6 (150kBytes):
http://www.fho-emden.de/~hoffmann/bezier18122002.pdf

Because of travelling I can´t write down the complete algorithm
in the moment.

Best regards --Gernot Hoffmann

[ecs]

Post by Gernot Hoffmann
http://www.fho-emden.de/~hoffmann/bezier18122002.pdf
Because of travelling I can´t write down the complete algorithm
in the moment.

Thanks a lot for working on this topic and posting your results. The
images in the PDF look very promising, although I'd like to test the
algorithm with more cases.

Btw, if you happen to have a more detailed explanation of the
algorithm, don't hesitate to post it when you have time. It can be
very helpful!

Thanks!

[ecs]

Post by Gernot Hoffmann

Post by ecs
I'm in a situation where I need an approximation of the offset of
bezier curves (the resulting approximation must also be a bezier, and
no more subdivision-). I've implemented this by offsetting the control
polygon, what I believe is the "Tiller-Hanson" algorithm.
...

[...]

Post by Gernot Hoffmann
Because of travelling I can´t write down the complete algorithm
in the moment.

From the results I'm getting, I'm beginning to believe that the
approach of forcing the bezier to have tangent V at a given point P
can result in a bad solution which intersects the original curve that
we wanted to offset, even if such original curve has a "good shape"
(ie: not a "rare" curve).

What I did was:

1- Let BezierBy3Points() be a function which takes three 2D points A,
B, and C, two 2D unit vectors V1 and V2, and one scalar value 't' in
range [0,1], and returns a bezier which starts at A with tangent
parallel to V1, passes through B when the parameter is 't', and ends
at C with tangent parallel to V2.

2- Decide a number of samples. The more, the better the approximated
solution.

3- Call BezierBy3Points() inside a loop which iterates 't' by the
decided number of samples in the range [0,1]. For each iteration,
compute the tangent at 't', and perform a dot product with the wished
tangent.

4- From all iterations in the loop, choose the solution whose dot
product is larger. This is the solution which passes through point B
with a tangent as close to our wished tangent as possible.

After implementing this algorithm, I noticed that the offset curve can
intersect the original in situations when the original is a "quite
common curve".

I got a better result by forgetting about the tangent requirement, and
choosing the solution which has a minimum distance to the ideal offset
curve.

[Gernot Hoffmann]

Post by ecs

Post by Gernot Hoffmann

Post by ecs
I'm in a situation where I need an approximation of the offset of
bezier curves (the resulting approximation must also be a bezier, and
no more subdivision-). I've implemented this by offsetting the control
polygon, what I believe is the "Tiller-Hanson" algorithm.
...

[...]

Post by Gernot Hoffmann
Because of travelling I can´t write down the complete algorithm
in the moment.

From the results I'm getting, I'm beginning to believe that the
approach of forcing the bezier to have tangent V at a given point P
can result in a bad solution which intersects the original curve that
we wanted to offset, even if such original curve has a "good shape"
(ie: not a "rare" curve).
1- Let BezierBy3Points() be a function which takes three 2D points A,
B, and C, two 2D unit vectors V1 and V2, and one scalar value 't' in
range [0,1], and returns a bezier which starts at A with tangent
parallel to V1, passes through B when the parameter is 't', and ends
at C with tangent parallel to V2.
2- Decide a number of samples. The more, the better the approximated
solution.
3- Call BezierBy3Points() inside a loop which iterates 't' by the
decided number of samples in the range [0,1]. For each iteration,
compute the tangent at 't', and perform a dot product with the wished
tangent.
4- From all iterations in the loop, choose the solution whose dot
product is larger. This is the solution which passes through point B
with a tangent as close to our wished tangent as possible.
After implementing this algorithm, I noticed that the offset curve can
intersect the original in situations when the original is a "quite
common curve".
I got a better result by forgetting about the tangent requirement, and
choosing the solution which has a minimum distance to the ideal offset
curve.

Thanks for the feedback.
After four weeks travelling (without access to the Web)
I´ve now added the mathematical description of my
algorithm (chapter 6, total file size 200kBytes):
http://www.fho-emden.de/~hoffmann/bezier18122002.pdf

Maybe there are better solutions, but for my examples
the results look reasonable. A minor bug in the previous
version (July 2004) was corrected.

Best regards --Gernot Hoffmann

[ecs]

Post by Gernot Hoffmann
Thanks for the feedback.
After four weeks travelling (without access to the Web)
I´ve now added the mathematical description of my
http://www.fho-emden.de/~hoffmann/bezier18122002.pdf
Maybe there are better solutions, but for my examples
the results look reasonable. A minor bug in the previous
version (July 2004) was corrected.

Thanks a lot for posting this!! (I don't know PS programming, so I'll
take a look at the mathematical description)

Thanks!

[g***@gmail.com]

Hello! I see this is a very old topic, but I am desperate to find a simple solution of offsetting Bezier cubic spline with same requirements; the same number of points and "handles".
Please, could You help with a code-like algorithm, maybe even with cycles and conditions. Thank You!