Editing Non-uniform rational B-spline (section)

== Technical specifications ==
[[File:Surface modelling.svg|250px|right]]
A NURBS curve is defined by its order, a set of weighted control points, and a knot vector.<ref>{{cite book | title = Bio-Inspired Self-Organizing Robotic Systems | url = https://www.springer.com/engineering/computational+intelligence+and+complexity/book/978-3-642-20759-4 | access-date = 2014-01-06 | page = 9 }}</ref>  NURBS curves and surfaces are generalizations of both [[B-spline]]s and [[Bézier curve]]s and surfaces, the primary difference being the weighting of the control points, which makes NURBS curves ''rational''. 

(''Non-rational'', aka ''simple'', B-splines are a special case/subset of rational B-splines, where each control point is a regular non-homogenous coordinate [no 'w'] rather than a [[Homogeneous coordinates|homogeneous coordinate]].<ref>{{cite web|url = https://www.cl.cam.ac.uk/teaching/2000/AGraphHCI/SMEG/node5.html | title = Rational B-splines | website = www.cl.cam.ac.uk }}</ref> That is equivalent to having weight "1" at each control point; ''Rational'' B-splines use the 'w' of each control point as a '''weight'''.<ref>{{cite web|url=https://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/NURBS-def.html|title=NURBS: Definition|website=www.cs.mtu.edu}}</ref>)

By using a two-dimensional grid of control points, NURBS surfaces including planar patches and sections of spheres can be created. These are parametrized with two variables (typically called ''s'' and ''t'' or ''u'' and ''v''). This can be extended to arbitrary dimensions to create NURBS mapping <math>\Reals^n \to \Reals^n</math>.

NURBS curves and surfaces are useful for a number of reasons:
* The set of NURBS for a given order is [[invariant (mathematics)|invariant]] under [[affine transformation|affine]] transformations:<ref>David F. Rogers: An Introduction to NURBS with Historical Perspective, section 7.1</ref> operations like rotations and translations can be applied to NURBS curves and surfaces by applying them to their control points.
* They offer one common mathematical form for both standard analytical shapes (e.g., [[conic]]s) and free-form shapes.
* They provide the flexibility to design a large variety of shapes.
* They reduce the memory consumption when storing shapes (compared to simpler methods).
* They can be evaluated reasonably quickly by [[numerically stable]] and accurate [[algorithm]]s.

Here, NURBS is mostly discussed in one dimension (curves); it can be generalized to two (surfaces) or even more dimensions.

=== Order ===
The ''order'' of a NURBS curve defines the number of nearby control points that influence any given point on the curve.  The curve is represented mathematically by a polynomial of degree one less than the order of the curve.  Hence, second-order curves (which are represented by linear polynomials) are called linear curves, third-order curves are called quadratic curves, and fourth-order curves are called cubic curves.  The number of control points must be greater than or equal to the order of the curve.

In practice, cubic curves are the ones most commonly used.  Fifth- and sixth-order curves are sometimes useful, especially for obtaining continuous higher order derivatives, but curves of higher orders are practically never used because they lead to internal numerical problems and tend to require disproportionately large calculation times.

=== Control points ===
[[File:NURBS 3-D surface.gif|250px|thumb|Three-dimensional NURBS surfaces can have complex, organic shapes. Control points influence the directions the surface takes. A separate square below the control cage delineates the X and Y extents of the surface.]]
The control points determine the shape of the curve.<ref>{{cite book |last=Gershenfeld |first=Neil |author-link=Neil Gershenfeld |year=1999 |page=141 |title=The Nature of Mathematical Modeling |publisher=[[Cambridge University Press]] |isbn=0-521-57095-6}}</ref> Typically, each point of the curve is computed by taking a [[weighted]] sum of a number of control points. The weight of each point varies according to the governing parameter. For a curve of degree d, the weight of any control point is only nonzero in d+1 intervals of the parameter space. Within those intervals, the weight changes according to a polynomial function (''basis functions'') of degree d. At the boundaries of the intervals, the basis functions go smoothly to zero, the smoothness being determined by the degree of the polynomial.

As an example, the basis function of degree one is a triangle function. It rises from zero to one, then falls to zero again. While it rises, the basis function of the previous control point falls. In that way, the curve interpolates between the two points, and the resulting curve is a polygon, which is [[continuous function|continuous]], but not [[Differentiable function|differentiable]] at the interval boundaries, or knots. Higher degree polynomials have correspondingly more continuous derivatives. Note that within the interval the polynomial nature of the basis functions and the linearity of the construction make the curve perfectly smooth, so it is only at the knots that discontinuity can arise.

In many applications the fact that a single control point only influences those intervals where it is active is a highly desirable property, known as '''local support'''. In modeling, it allows the changing of one part of a surface while keeping other parts unchanged.

Adding more control points allows better approximation to a given curve, although only a certain class of curves can be represented exactly with a finite number of control points. NURBS curves also feature a scalar '''weight''' for each control point. This allows for more control over the shape of the curve without unduly raising the number of control points.  In particular, it adds conic sections like circles and ellipses to the set of curves that can be represented exactly. The term ''rational'' in NURBS refers to these weights.

The control points can have any [[dimensionality]]. One-dimensional points just define a [[scalar (mathematics)|scalar]] function of the parameter. These are typically used in image processing programs to tune the brightness and color curves. Three-dimensional control points are used abundantly in 3D modeling, where they are used in the everyday meaning of the word 'point', a location in 3D space.
Multi-dimensional points might be used to control sets of time-driven values, e.g. the different positional and rotational settings of a robot arm. NURBS surfaces are just an application of this. Each control 'point' is actually a full vector of control points, defining a curve. These curves share their degree and the number of control points, and span one dimension of the parameter space. By interpolating these control vectors over the other dimension of the parameter space, a continuous set of curves is obtained, defining the surface.

=== Knot vector ===
The knot vector is a sequence of parameter values that determines where and how the control points affect the NURBS curve. The number of knots is always equal to the number of control points plus curve degree plus one (i.e. number of control points plus curve order). The knot vector divides the parametric space in the intervals mentioned before, usually referred to as ''knot spans''. Each time the parameter value enters a new knot span, a new control point becomes active, while an old control point is discarded.
It follows that the values in the knot vector should be in nondecreasing order, so (0, 0, 1, 2, 3, 3) is valid while (0, 0, 2, 1, 3, 3) is not.

Consecutive knots can have the same value. This then defines a knot span of zero length, which implies that two control points are activated at the same time (and of course two control points become deactivated). This has impact on continuity of the resulting curve or its higher derivatives; for instance, it allows the creation of corners in an otherwise smooth NURBS curve.
A number of coinciding knots is sometimes referred to as a knot with a certain '''multiplicity'''. Knots with multiplicity two or three are known as double or triple knots.
The multiplicity of a knot is limited to the degree of the curve; since a higher multiplicity would split the curve into disjoint parts and it would leave control points unused. For first-degree NURBS, each knot is paired with a control point.

The knot vector usually starts with a knot that has multiplicity equal to the order. This makes sense, since this activates the control points that have influence on the first knot span. Similarly, the knot vector usually ends with a knot of that multiplicity.
Curves with such knot vectors start and end in a control point.

The values of the knots control the mapping between the input parameter and the corresponding NURBS value. For example, if a NURBS describes a path through space over time, the knots control the time that the function proceeds past the control points. For the purposes of representing shapes, however, only the ratios of the difference between the knot values matter; in that case, the knot vectors (0, 0, 1, 2, 3, 3) and (0, 0, 2, 4, 6, 6) produce the same curve. The positions of the knot values influences the mapping of parameter space to curve space. Rendering a NURBS curve is usually done by stepping with a fixed stride through the parameter range. By changing the knot span lengths, more sample points can be used in regions where the curvature is high. Another use is in situations where the parameter value has some physical significance, for instance if the parameter is time and the curve describes the motion of a robot arm. The knot span lengths then translate into velocity and acceleration, which are essential to get right to prevent damage to the robot arm or its environment. This flexibility in the mapping is what the phrase ''non uniform'' in NURBS refers to.

Necessary only for internal calculations, knots are usually not helpful to the users of modeling software.  Therefore, many modeling applications do not make the knots editable or even visible. It's usually possible to establish reasonable knot vectors by looking at the variation in the control points. More recent versions of NURBS software (e.g., [[Autodesk Maya]] and [[Rhinoceros 3D]]) allow for interactive editing of knot positions, but this is significantly less intuitive than the editing of control points.

=== Construction of the basis functions ===
The B-spline basis functions used in the construction of NURBS curves are usually denoted as <math>N_{i,n}(u)</math>, in which <math>i</math> corresponds to the <math>i</math>-th control point, and <math>n</math> corresponds with the degree of the basis function.<ref name=nurbs-book>{{cite book |last1=Piegl |first1=Les |last2=Tiller |first2=Wayne |title=The NURBS Book |date=1997 |publisher=Springer |location=Berlin |isbn=3-540-61545-8 |edition=2. |url-access=registration |url=https://archive.org/details/nurbsbook00pieg }}</ref> The parameter dependence is frequently left out, so we can write {{nowrap|<math> N_{i,n} </math>.}}
The definition of these basis functions is recursive in <math>n</math>.
The degree-0 functions <math>N_{i,0}</math> are [[piecewise]] [[constant function]]s. They are one on the corresponding knot span and zero everywhere else.
Effectively, <math>N_{i,n}</math> is a linear interpolation of <math>N_{i,n-1}</math> and <math>N_{i+1,n-1}</math>. The latter two functions are non-zero for <math>n</math> knot spans, overlapping for <math>n-1</math> knot spans.  The function <math>N_{i,n}</math> is computed as
[[File:nurbsbasisconstruct.svg|thumb|From top to bottom: Linear basis functions <math>N_{1,1}</math> (blue) and <math>N_{2,1}</math> (green) (top), their weight functions <math>f</math> and <math>g</math> (middle) and the resulting quadratic basis function (bottom). The knots are 0, 1, 2, and 2.5]]
<math display="block">N_{i,n} = f_{i,n} N_{i,n-1} + g_{i+1,n} N_{i+1,n-1}</math>
<math>f_i</math> rises linearly from zero to one on the interval where <math>N_{i,n-1}</math> is non-zero, while <math>g_{i+1}</math> falls from one to zero on the interval where <math>N_{i+1,n-1}</math> is non-zero. As mentioned before, <math>N_{i,1}</math> is a triangular function, nonzero over two knot spans rising from zero to one on the first, and falling to zero on the second knot span. Higher order basis functions are non-zero over corresponding more knot spans and have correspondingly higher degree. If <math>u</math> is the parameter, and <math>k_i</math> is the <math>i</math><sup>th</sup> knot, we can write the functions <math>f</math> and <math>g</math> as
<math display="block">f_{i,n}(u) = \frac{u - k_i}{k_{i+n} - k_i}</math>
and
<math display="block">g_{i,n}(u) = 1 - f_{i,n}(u) = \frac{k_{i+n} - u}{k_{i+n} - k_i}</math>
The functions <math>f</math> and <math>g</math> are positive when the corresponding lower order basis functions are non-zero. By [[mathematical induction|induction]] on n it follows that the basis functions are non-negative for all values of <math>n</math> and <math>u</math>. This makes the computation of the basis functions numerically stable.

Again by induction, it can be proved that the sum of the basis functions for a particular value of the parameter is unity. This is known as the '''partition of unity''' property of the basis functions.

[[File:nurbsbasislin2.svg|frame|Linear basis functions]]
[[File:nurbsbasisquad2.svg|frame|Quadratic basis functions]]

The figures show the linear and the quadratic basis functions for the knots {..., 0, 1, 2, 3, 4, 4.1, 5.1, 6.1, 7.1, ...}

One knot span is considerably shorter than the others. On that knot span, the peak in the quadratic basis function is more distinct, reaching almost one. Conversely, the adjoining basis functions fall to zero more quickly. In the geometrical interpretation, this means that the curve approaches the corresponding control point closely. In case of a double knot, the length of the knot span becomes zero and the peak reaches one exactly. The basis function is no longer differentiable at that point. The curve will have a sharp corner if the neighbour control points are not collinear.

=== General form of a NURBS curve ===

Using the definitions of the basis functions <math>N_{i,n}</math> from the previous paragraph, a NURBS curve takes the following form:<ref name="nurbs-book" />
<math display="block">C(u) = \sum_{i=1}^{k} {\frac
	{N_{i,n}(u)w_i}
	{\sum_{j=1}^k N_{j,n}(u)w_j}}
	\mathbf{P}_i = \frac
	{\sum_{i=1}^k {N_{i,n}(u)w_i \mathbf{P}_i}}
	{\sum_{i=1}^k {N_{i,n}(u)w_i}}
	</math>

In this, <math>k</math> is the number of control points <math>\mathbf{P}_i</math> and <math>w_i</math> are the corresponding weights. The denominator is a normalizing factor that evaluates to one if all weights are one. This can be seen from the partition of unity property of the basis functions. It is customary to write this as
<math display="block">C(u) = \sum_{i=1}^k R_{i,n}(u)\mathbf{P}_i</math>
in which the functions
<math display="block">R_{i,n}(u) = {N_{i,n}(u)w_i \over \sum_{j=1}^k N_{j,n}(u)w_j}</math>
are known as the ''rational basis functions''.

=== General form of a NURBS surface ===

A NURBS surface is obtained as the [[tensor product]] of two NURBS curves, thus using two independent parameters <math>u</math> and <math>v</math> (with indices <math>i</math> and <math>j</math> respectively):<ref name="nurbs-book" />
<math display="block">S(u,v) = \sum_{i=1}^k \sum_{j=1}^l R_{i,j}(u,v) \mathbf{P}_{i,j} </math>
with
<math display="block">R_{i,j}(u,v) = \frac {N_{i,n}(u) N_{j,m}(v) w_{i,j}} {\sum_{p=1}^k \sum_{q=1}^l N_{p,n}(u) N_{q,m}(v) w_{p,q}}</math>
as rational basis functions.