3
$\begingroup$

I plan to draw approximate circles using a piecewise cubic Bezier representation. The representation should use four Beziers and be defined by four interpolating control points (let us call them anchors).

Formulas to compute the control points of the Bezier pieces are well known. Also see Approximation of a Cubic Bezier Curve by Circular Arcs and Vice Versa.

In the case of circular arcs, the number of Bezier pieces can be lowered from four down to one, depending on the amplitude. And due to the presence of endpoints, the number of required anchors goes from five to two.

So far so good.

Now I want to deform the curves by moving the anchor points. The question is: how do I recompute the control points so that the smoothness is preserved ?

enter image description here

$\endgroup$
  • 2
    $\begingroup$ Not question related but: fun fact: NURBS can reproduce a real circle, not just an approximation. $\endgroup$ – SteeveDroz Aug 6 '14 at 7:36
  • $\begingroup$ Indeed. You can answer the same question for these if you like :) $\endgroup$ – Yves Daoust Aug 6 '14 at 7:38
  • $\begingroup$ Hehe, I answered the question but NURBS curves don't have this problem as they are only made of one segment that can be circular. $\endgroup$ – SteeveDroz Aug 6 '14 at 8:19
  • $\begingroup$ Yep, but you can impose anchor points as well and move them... $\endgroup$ – Yves Daoust Aug 6 '14 at 8:22
  • $\begingroup$ What do you mean by "smoothness"? Do you want C2 continuity? G2? Something else? $\endgroup$ – Peter Taylor Aug 6 '14 at 9:28
2
$\begingroup$

Suppose you want to deform the circle (and its enclosing square) using some affine transformation $f(\mathbf{x}) = \mathbf{M} \mathbf{x} + \mathbf{b}$. Here $\mathbf{M}$ is a $2 \times 2$ matrix. This will cover translations, rotatations, uniform and non-uniform scaling, reflection, and shearing kinds of deformations.

To get the control points of the deformed curve, you simply apply the transformation to the control points of the original curve. So, if the original curve had control points $\mathbf{p}_1, \ldots, \mathbf{p}_n$, then the deformed curve has control points $f(\mathbf{p}_1), \ldots, f(\mathbf{p}_n).$

The same applies to rational curves (i.e. NURBS curves).

Now, on to the question you asked in a comment below. If you want to create a closed curve that interpolates four points, proceed as follows. Suppose the four given points are $\mathbf{p}$, $\mathbf{q}$, $\mathbf{r}$, $\mathbf{s}$, arranged in a roughly circular fashion. Draw lines through $\mathbf{q}$ and $\mathbf{s}$ that are parallel to the vector $\mathbf{r} - \mathbf{p}$. Similarly, draw lines through $\mathbf{p}$ and $\mathbf{r}$ that are parallel to the vector $\mathbf{s} - \mathbf{q}$. These four lines give you a parallelogram with vertices $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$, $\mathbf{d}$, as shown below.

enter image description here

The parallelogram construction is similar to the idea used in Catmull-Rom splines -- the tangent at a given point is in the direction of the chord between the preceding and following points. But there's nothing really special about the parallelogram construction -- all we need is a convex quadilateral $\mathbf{abcd}$ whose sides contain the four given points $\mathbf{p}$, $\mathbf{q}$, $\mathbf{r}$, $\mathbf{s}$. I don't suppose the parallelogram approach is optimal in any sense. You may be able to invent a technique that works better.

Now we need to figure out how to construct a cubic Bezier curve in each of the four "quadrants" of our quadrilateral (parallelogram, here). The construction should be one that produces good approximations of circular arcs, when possible. and reasonably smooth curves in all cases.

Let's focus on the quadrant $\mathbf{paq}$; the other three quadrants can be handled similarly, of course. The cubic curve should start at the point $\mathbf{p}$, obviously, and its first interior control point should be on the line segment $\mathbf{pa}$. Similarly, the curve should end at $\mathbf{q}$, and should have an interior control point on the line segment $\mathbf{aq}$. So, the only unknowns are the two distances $d_0$ and $d_1$ shown in the picture below:

enter image description here

There are several ways to calculate suitable values for $d_0$ and $d_1$. One is the method developed by John Hobby for use in the Metafont system. For details, see this paper. A simpler approach (which gives results just as good as Hobby's, in my experience) is to set $$ d_0 = \frac{2c}{3(1 + \cos\alpha_1)} \quad ; \quad d_1 = \frac{2c}{3(1 + \cos\alpha_0)} $$ Note the swapping of indices in these formulae -- we use $\alpha_1$ to compute $d_0$, and $\alpha_0$ to compute $d_1$.

If $\mathbf{pa} = \mathbf{qa} = 1$, and the angle $\mathbf{paq}$ is a right angle, then we have $c = \sqrt2$ and $\alpha_0 = \alpha_1 = \pi/4$, and so we get $$ d_0 = d_1 = \frac{4}{3}(\sqrt2 - 1) $$ So this method reproduces the well-known cubic Bezier approximation of a quarter of a circle.

$\endgroup$
  • $\begingroup$ Interesting. The four anchor points introduce 8 degrees of freedom, which cannot be covered by an affine transform (6 DOF). But a bilinear transform could do. $\endgroup$ – Yves Daoust Aug 9 '14 at 10:06
  • 1
    $\begingroup$ You're right. The process I suggested won't work, because the curve won't interpolate the four points. My apologies -- it was written in an airport after 16 hours on a plane. A bilinear transform would work, but will give a rational curve. Please see modified answer. $\endgroup$ – bubba Aug 9 '14 at 23:51
  • 1
    $\begingroup$ The construction I described produces a parallelogram, which effectively reduces the number of degrees of freedom from 8 to 6. Then an affine transform will work. But the resulting curve won't pass through the 4 given points. $\endgroup$ – bubba Aug 9 '14 at 23:55
1
$\begingroup$

When drawing a Bézier curve, the thing you have to know it that the beginning and end of the curve are tangent to the line between the extremity and the closest control point. Knowing that, you simply have to make sure that the two control points that surround a segment end and that segment end itself are aligned.

Moving a control point should only create recalculations for 2 other control points (for a quadratic interpolation): those that are separated by a segment end from the moving one.

Step by step procedure:

Let's call the end points $e_0$ through $e_3$ for a 4 points approximation circle.
Let's call the control points $c_0$ through $c_3$ for the same circle.
The points are ordered $e_0,c_0,e_1,c_1,e_2,c_2,e_3,c_3$.

1) Move the control point $c_n$.

2) Identify the adjascent end points and control points: $e_n$, $e_{n+1}$, $c_{n-1}$ and $c_{n+1}$. Hint: using modulo will be easier to connect the first and last ones.

3) Calculate the line that passes through $c_n$ and $e_n$, move $c_{n-1}$ to that line so that it stays aligned to the control point on its other side (e.g. the line that passes through $e_{n-2}$ and $c_{n-2}$).

4) Do the same for $c_{n+1}$.

Notes:

  • As the points must be aligned, it's not possible to have a single Bézier piece approximation; the only points involved are $e_0$ and $c_0$, as $e_1=e_0$.
  • A 2-pieces Bézier is possible but not very interresting, as all the points must be constantly aligned in order to keep the smoothness, which means only a 1d approximation of a curve.
  • If you use cubic interpolation (2 control points in each segment), you only have to move one other point. The control point located in the same segment can be anywhere and doesn't have to be recalculated.
$\endgroup$
  • $\begingroup$ I am using cubics. But what if you move all anchors at the same time ? (Maybe I should have asked "how do you create a closed smooth curve through four points in such a way that when they are in a square the curve well approximates a circle ?".) $\endgroup$ – Yves Daoust Aug 6 '14 at 8:25
  • $\begingroup$ Oh well, sorry then, it's a bit too complicated for me. $\endgroup$ – SteeveDroz Aug 7 '14 at 5:33
  • $\begingroup$ Thanks anyway for the proposal. $\endgroup$ – Yves Daoust Aug 7 '14 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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