Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two points $P_1$ and $P_2$ in the plane. For each of the points, I have two vectors $v_1$ and $v_2$. I want to find a quadratic Bézier curve from $P_1$ to $P_2$ of length $l$ leaving $P_1$ in the direction of $v_1$ and entering $P_2$ in the direction of $v_2$.

Edit: It is not needed that I restrict myself to Bézier curves, it was just my first approach. Other ideas are more than welcome.

Also, as stated in the comments, this is not always possible, but I am only interested in the cases where it is possible.

share|improve this question
2  
Not possible in general. Your problem is overconstrained: $P_1$, $P_2$, $v_1$ and $v_2$ define a unique quadratic Bézier. –  Peter Taylor Mar 4 '11 at 13:29
    
It is obviously correct when you say that it is not possible in general. For example, the vectors could point away from each other, and $l$ could be the minimum distance between $P_1$ and $P_2$. But if I can solve the problem, in which way can I solve the problem? I do not need to restrict myself to Bézier curves. –  utdiscant Mar 4 '11 at 13:39
1  
As long as $l > d(P_1, P_2)$ you should be able to find such a curve, by varying the length of your vectors $v_1$ and $v_2$. However, apparently (steve.hollasch.net/cgindex/curves/cbezarclen.html) there's no closed form for calculating the length of a cubic Bézier curve, so you'd have to use quadrature. –  Rawling Mar 4 '11 at 15:43
add comment

2 Answers

up vote 2 down vote accepted

Let $Q$ be the intersection of the two end tangents defined by $(P_1, v_1)$ and $(P_2, v_2)$.

You can construct a rational quadratic Bezier curve (degree 2) with the required arclength $l$ provided $d(P_1,P_2) \le l < d(P_1,Q) + d(P_2,Q)$, where $d$ denotes the distance between two points. Rational quadratics are just conic section curves.

AFAIK, there is no closed-form solution that lets you construct the curve, for a given $l$, but a simple one-parameter root-finding process will give it to you reliably and quickly.

Unlike cubics, rational quadratics never have inflexions, which might be useful to you. And, for values of $l$ close to $d(P_1,Q) + d(P_2,Q)$, they give a solution that is arguably more "natural".

The basic formulae and some nice pictures can be found on this page.

share|improve this answer
add comment

cubic Bézier curves

The "curves" in most fonts and most other vector graphic formats -- PostScript, Asymptote, Metafont, SVG, etc. -- are Bézier splines composed of cubic Bézier curves.

A cubic Bézier curve is often represented as 4 points P0, P1, P2, P3. P0 is its starting point, P3 is its end point. By placing P1 anywhere along the ray from P0 in the direction of v1, the Bézier curve will leave P0 in the direction of v1. By placing P2 anywhere along the ray from P3 in the direction of -v2, the Bézier curve will enter P3 in the direction of v2.

If you place P1 directly on top of P0 and place P2 directly on top of P3, the "cubic Bézier curve" degenerates to a straight line from P0 to P3 with some minimum length. The further one pushes P1 away from P0 in the desired direction, or pushes P2 away from P3 in the desired direction, or (most likely) both, the arc length monotonically increases, and the curve still has the desired relationships. (If the two rays intersect, then when P1 and P2 are both pushed far enough past the intersection point, the cubic Bézier curve will have a self-intersection point ... somewhere).

The problem is still a little underconstrained -- you can increase the length by pushing P1, or increase it by pushing P2, or both.

If I had this problem, I would obtain some subroutine BezierArcLength(P0, P1, P2, P3) that gave me an adequate approximation of the actual length of some given cubic Bézier curve. Rawling suggested Earl Boebert: "Computing the Arc Length of Cubic Bezier Curves" which looks great; Arc Length of Bézier Curves has more discussion on this topic.

Then I would guess that maybe setting the distance m from P0 to P1 to be the same as the distance from P2 to P3 might be OK. So I would build some subroutine TestPoints(m) that sets P1 a distance m away from P0 along the desired ray, and sets P2 a distance m away from P3 along the desired ray.

Then I would use something like the false position method to find some m that gave me the desired length, with the function f(m) = BezierArcLength(TestPoints(m)) - desired_length.

Initialize by picking a=0, b=4*desired_length, and calculating fa = f(a) and fb = f(b). (TestPoints(0) gives a straight line shorter than your desired length, so fa is negative, and TestPoints(b) gives a curve longer than your desired length, so fb is positive, right?)

Loop:

  • Find some new position m using the false position method: m = (fb*a - fa*b)/(fb - fa).
  • Calculate the Bezier arc length excess over your desired length: fm = f(m).
  • If fa and fm have the same sign, set the new a to m and set the new fa to fm.
  • Otherwise, fb and fm have the same sign, so set the new b to m and set the new fb to fm.
  • loop until fm is "close enough" to zero.

This converges on a cubic Bézier curve that meets your criteria. Other cubic Bézier curve that meets your criteria either push P1 directly towards P0 (making that distance less than m) and push P2 directly away from P3 (making that distance more than m), or vice versa.

quadratic Bézier curve

The "curves" in TrueType fonts are Bézier splines composed of quadratic Bézier curves.

A quadratic Bézier curve (a piece of a parabola) is often represented as 3 points P0, P1, P2. P0 is its starting point, P3 is its end point. By placing P1 anywhere along the ray from P0 in the direction of v1, the curve will leave P0 in the direction of v1. By placing P1 anywhere along the ray from P2 in the direction of -v2, the curve will enter P2 in the direction of v2.

There is only one quadratic Bézier curve that meets these critera on endpoints and end tangents -- the points P0 and P2 are given, and the point P1 is at the intersection of the two rays. There is no other quadratic Bézier curve that meets those critera. As Peter Taylor pointed out, if the length of that parabolic arc does not already have the desired length, it is not possible to find some "other" quadratic Bézier curve that has some other length and also has the given endpoints and the given end tangents.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.