NURBS circle without all the double knots?

Question

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

• NURBS circle example on wikipedia
• Philip Schneider's "NURB Curves: A Guide for the Uninitiated"
• David Eberly's "Representing a Circle or a Sphere with NURBS"

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.