3
$\begingroup$

I've been looking at various examples of a circle parametrized as a degree-2 NURBS curve, e.g.:

Each of these examples represents the circle in sections (arcs) delimited by double knots; that is, at each transition from one section to the next, two control points are discarded, while another two control points come into play.

That seems a bit heavy-handed. I was wondering, is there a way to express a circle as a degree-2 NURBS curve using only single knots? That is, at each intermediate knot, only one control point is discarded, while another single control point comes into play.

$\endgroup$
1
$\begingroup$

This is only a partial answer, but it shows that it can't be done with uniform knots.

The basis functions are defined recursively as

$$N_{i,0} = [k_i \le u < k_{i+1}]$$ $$N_{i,n} = f_{i,n} N_{i,n-1}+g_{i+1,n}N_{i+1,n-1}$$ $$f_{i,n} = \frac{u-k_{i}}{k_{i+n}-k_{i}}$$ $$g_{i,n} = \frac{k_{i+n}-u}{k_{i+n}-k_{i}}$$

Expanding out,

$$N_{i,2} = \begin{cases} f_{i,1} f_{i,2} & \textrm{if } k_i \le u < k_{i+1} \\ g_{i+1,1} f_{i,2} + f_{i+1,1} g_{i+1,2} & \textrm{if } k_{i+1} \le u < k_{i+2} \\ g_{i+2,1} g_{i+1,2} & \textrm{if } k_{i+2} \le u < k_{i+3} \\ 0 & \textrm{otherwise} \end{cases}$$

The curve is $$C(u) = \frac{\sum_{i=1}^k N_{i,n} w_{i} \mathbf{P}_i}{\sum_{i=1}^k N_{i,n} w_{i}}$$

For a circle centred at the origin, $C(u) \cdot C(u) = 1$ so $$\sum_{i=1}^k \sum_{j=1}^k N_{i,n} N_{j,n} w_i w_j (\mathbf{P}_i \cdot \mathbf{P}_j - 1) = 0$$ as an identity, so for each range between two knots we get $n^2+1$ polynomial constraints on the $n+1$ knots, weights, and control points with support in that range.

E.g. in the range $k_3 \le u < k_4$ we have

$$g_{3,1}{}^2 g_{2,2}{}^2 w_1^2 (\mathbf{P}_1 \cdot \mathbf{P}_1 - 1) + \\ (g_{3,1} f_{2,2} + f_{3,1} g_{3,2})^2 w_2^2 (\mathbf{P}_2 \cdot \mathbf{P}_2 - 1) + \\ f_{3,1}{}^2 f_{3,2}{}^2 w_3^2 (\mathbf{P}_3 \cdot \mathbf{P}_3 - 1) + \\ 2 g_{3,1} g_{2,2} (g_{3,1} f_{2,2} + f_{3,1} g_{3,2}) w_1 w_2 (\mathbf{P}_1 \cdot \mathbf{P}_2 - 1) + \\ 2 g_{3,1} g_{2,2} f_{3,1} f_{3,2} w_1 w_3 (\mathbf{P}_1 \cdot \mathbf{P}_3 - 1) + \\ 2 (g_{3,1} f_{2,2} + f_{3,1} g_{3,2}) f_{3,1} f_{3,2} w_2 w_3 (\mathbf{P}_2 \cdot \mathbf{P}_3 - 1) = 0$$


Define $\delta_{a,b} = k_b - k_a$ and $W_{a,b} = w_a w_b (\mathbf{P}_a \cdot \mathbf{P}_b - 1)$. Expand and multiply through by $\delta_{2,4}^2 \delta_{3,4}^2 \delta_{3,5}^2$:

$$\delta_{3,5}^2 (k_4-u)^4 W_{1,1} + \\ \left(\delta_{3,5}(k_4-u)(u-k_2) + \delta_{2,4}(u-k_3)(k_5-u)\right)^2 W_{2,2} + \\ \delta_{2,4}^2(u-k_3)^4 W_{3,3} + \\ 2 \delta_{3,5}(k_4-u)^2 \left(\delta_{3,5}(k_4-u)(u-k_2) + \delta_{2,4}(u-k_3)(k_5-u)\right) W_{1,2} + \\ 2 \delta_{2,4}\delta_{3,5}(k_4-u)^2 (u-k_3)^2 W_{1,3} + \\ 2 \left(\delta_{3,5}(k_4-u)(u-k_2) + \delta_{2,4}(u-k_3)(k_5-u)\right) \delta_{2,4}(u-k_3)^2 W_{2,3} = 0$$

Serious constraint: uniform knots

Then wlog $k_2 = 0$, $k_3 = 1$, $k_4 = 2$, $k_5 = 3$, $\delta_{a,b} = b-a$.

Equating coefficients from $u^4$ down to $u^0$: $$ \begin{matrix} W_{1,1} &+ 4 W_{2,2} &+ W_{3,3} &- 4 W_{1,2} &+ 2 W_{1,3} &- 4 W_{2,3} &= 0 \\ % u^4 -2 W_{1,1} &+ 6 W_{2,2} &- W_{3,3} &+ 7 W_{1,2} &- 3 W_{1,3} &+ 5 W_{2,3} &= 0 \\ % u^3 12 W_{1,1} &+ 18 W_{2,2} &+ 3 W_{3,3} &- 32 W_{1,2} &+ 65 W_{1,3} &- 14 W_{2,3} &= 0 \\ % u^2 -8 W_{1,1} &&- W_{3,3} &+ 12 W_{1,2} &- 6 W_{1,3} &+ 3 W_{2,3} &= 0 \\ % u^1 16 W_{1,1} &&+ W_{3,3} &&+ 8 W_{1,3} &&= 0 \\ % u^0 \end{matrix} $$

If we have two arcs in a row we get the same constraints with all of the indices incremented, which is to say 10 linear constraints on 9 $W_{a,b}$, and performing row reduction leads to a contradiction.

So either one arc is enough or uniform knots are impossible.

One arc

Then $C(k_3) = C(k_4)$:

$$\frac{g_{3,1} g_{2,2} w_1 \mathbf{P}_1 + (g_{3,1} f_{2,2} + f_{3,1} g_{3,2}) w_2 \mathbf{P}_2 + f_{3,1} f_{3,2} w_3 \mathbf{P}_3}{g_{3,1} g_{2,2} w_1 + (g_{3,1} f_{2,2} + f_{3,1} g_{3,2}) w_2 + f_{3,1} f_{3,2} w_3} \Bigg\vert_{u=k_3} = \\ \frac{g_{3,1} g_{2,2} w_1 \mathbf{P}_1 + (g_{3,1} f_{2,2} + f_{3,1} g_{3,2}) w_2 \mathbf{P}_2 + f_{3,1} f_{3,2} w_3 \mathbf{P}_3}{g_{3,1} g_{2,2} w_1 + (g_{3,1} f_{2,2} + f_{3,1} g_{3,2}) w_2 + f_{3,1} f_{3,2} w_3} \Bigg\vert_{u=k_4}$$

or

$$\frac{\delta_{3,4} w_1 \mathbf{P}_1 + \delta_{2,3} w_2 \mathbf{P}_2}{\delta_{3,4} w_1 + \delta_{2,3} w_2} = \frac{\delta_{4,5} w_2 \mathbf{P}_2 + \delta_{3,4} w_3 \mathbf{P}_3}{\delta_{4,5} w_2 + \delta_{3,4} w_3}$$

So any of the control points is a linear combination of the other two, meaning that they are colinear and by the convex hull property we cannot have a full circle.

$\endgroup$
0
$\begingroup$

A rational quadratic Bezier curve can only represent a circular arc of angular span up to 180 degree (but not including 180 degree) without using negative weight. This is the reason that you need to use multiple rational quadratic Bezier curves for representing a full circle (or any circular arc with angular span >= 180 degree) and therefore the double knots happen for interior knots.

$\endgroup$
  • $\begingroup$ I believe that a single quadratic Bezier curve can represent only less than 180 degrees of arc. But I don't see how that implies you need any double interior knots. E.g. instead of 0,0,0,1,1,2,2,3,3,4,4,4, couldn't the knot sequence look something like like 0,0,0,1/2,3/2,5/2,7/2,4,4,4? (Obviously not with the original control points and weights, but for some other set of control points and weights). If not, why not? $\endgroup$ – Don Hatch Dec 13 '18 at 7:47
  • 1
    $\begingroup$ @Don: Two rational quadratic Bezier curves representing two adjacent circular arcs of same radius and same center are C1 continuous in Cartesian coordiante system. However, they are only C0 continuous in homogenous coordinate system. Therefore, there has to be double interior knots at the joint. $\endgroup$ – fang Dec 13 '18 at 18:43
  • $\begingroup$ Why must they be only $C^0$ continuous in homogeneous space? It sounds like that's the crux of it. $\endgroup$ – Don Hatch Dec 13 '18 at 21:17
  • $\begingroup$ @DonHatch, the image in the Wikipedia link from the question showing a cone and the parabolae which perspective-map to circle arcs hints at the intuition behind why the arcs are only $C^0$ continuous. I suspect that some knowledge of conic sections would allow an elegant proof, but unfortunately my knowledge of conic sections is highly deficient. $\endgroup$ – Peter Taylor Dec 13 '18 at 21:35
  • $\begingroup$ @DonHatch, using the data in the Wikiperdia page as example, the two rational quadratic Bezier curves have control point with weight = 1.0 at the common point and weight = sqrt(2)/2 for the middle control point. Therefore, in the homogeneous space the 3 control points are not collinear and therefore the two curves are only joined with C0 continuity in homogeneous space even though the projected image are joined in C1 manner. $\endgroup$ – fang Dec 14 '18 at 2:14
0
$\begingroup$

You can represent a circular arc as a rational quadratic b-spline with positive weights and single knots provided its angular span is less than $360$ degrees. If the angular span is $< 180$ degrees, it's easy -- just use a Bézier curve. If the angle is $\ge 180$ degrees, take the Bézier representation (which will have a negative weight), and add a single interior knot using Boehm's algorithm. The weights of the resulting curve will all be positive.

An example for a semi-circle (angle $=180$):

  • Control points: $(1,0), (1,1), (-1,1), (-1,0)$
  • Weights: $1, \tfrac12, \tfrac12, 1$
  • Knots: $0,0,0, \tfrac12, 1,1,1$

Note that the resulting curve is $C^\infty$, considered either as a mapping into $\mathbb{R}^3$ or $\mathbb{R}^4$. To see why, recall that we started out with a single segment, which is obviously $C^\infty$, and adding a knot does not change this.

$\endgroup$

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.