International Journal of Shape Modeling, Vol. 2, No. 2&3 (1996) 103{116cfWorld Scienti c Publishing Company

REPARAMETRIZATION OF NURBS CURVESGIULIO CASCIOLAyand SERENA MORIGIz
Department of Mathematics , University of Bologna
P.zza di Porta San Donato 5, 40127 Bologna, Italy
Received 1 March 1996
Revised 9 September 1996
Communicated by B. Falcidieno
In geometric design, it is often useful to be able to give an arc length reparametrization
for NURBS curves, that keeps the curve a NURBS too. Since parametric rational curves,
except for straight lines, cannot be parametrized by arc length, we developed a numericalmethod of approximating the arc length parametrization function. In this way it waspossible to obtain a good parametrization of a NURBS curve with respect to arc length.
Numerical results show a good behaviour of the proposed method on several test curves.
Keywords : Reparametrization; NURBS; Arc length parametrization; Approximation.

1. Introduction

We are concerned with the problem of parametric NURBS curve reparametrization.
This consists in changing the current parameter of a curve with another parameter using a reparametrization function. It should be noted that the shape of thecurve remains unchanged during this process; only the way the curve is describedis altered.
In our case, the fact that the curve is de ned as a ratio of two polynomial
splines enables us to apply a rational polynomial function that will keep the curve
a NURBS.
In particular, if it is important that the degree of the curve should be kept
unchanged, we may choose a rational linear reparametrization function.
In this case [1] and [2] give an explicit expression for the reparametrized NURBS
curve.
The most common and useful parametrization, from a computational point ofview, is the arc length, where a unit change in the parametrizing variable results
in a unit change in curve length. Such a parametrization is unfortunately almost
never possible for NURBS, unless for straight lines (see [3]). These considerations
lead us to search for a parametrization that best ts the arc length.
 This research was supported by CNR-Italy, Contract n.95.00730.CT01.
y e-mail: casciola@dm.unibo.itz e-mail: serena@csr.unibo.it

1

2 International Journal of Shape ModelingTo our knowledge no author in the literature has considered this problem, while
in several papers numerical techniques to compute arc length were developed (see,for example, [4] and [5]).
This paper is essentially in two parts. In the rst, we consider the reparametrization problem on a single interval, and in the second part we extend this result
to deal with adaptive piecewise reparametrization.
In the next section we consider some essential motivations that led us to consider
this topic.
In section 3 a formulation of arc length reparametrization is given; while insection 4 we introduce the concept of approximate reparametrization. Reparametrization on a single interval is considered in section 5, studying the particularreparametrization function used in this paper and the numerical method applied
to compute it. In order to establish the quality of the proposed reparametrization
method, we present two evaluation parameters in section 6, and in section 7 wereport the results obtained on several test curves. The second part of the paper isintroduced by a description of a C 0 adaptive piecewise reparametrization techniquein section 8, followed by the respective experimental results in section 9. Finally,an extension to C 1 reparametrization is considered and some concluding remarks
are given.

2. Motivation

To date, NURBS are the most general parametric representation in geometric modelling. The most frequently used NURBS design techniques are the speci cation ofa control polygon, and the interpolation or approximation of data points to generate the initial shape. This is then re ned into the desired nal shape through theinteractive adjustment of control points and weights.
A possible shortcoming of this process is that small changes in the shape of thecurve can also lead to a bad parametrization with respect to the arc length.
Figure 1 shows a curve modi ed in shape by increasing weights w3 and w4. The
curves, before and after modi cation, are evaluated and drawn at parameter values
uniformly spaced in the parametric domain (see, the drawing in dots in Fig. 1). We
can observe the e ects of signi cant changes in the parametrization; note that thearc length parametrization would yield points spaced uniformly on the curve.
Moreover, when a badly parametrized curve is used in the construction of surfaces (cross-sectional techniques) badly parametrized surfaces are obtained.
Any numerical method, or simply the rendering procedure, applied to curves orsurfaces, are a ected by their particular parametrization in terms of computational
complexity and numerical stability, as shown in the following example.
We consider the Bottle/Plane intersection computed by a Surface/Surface Intersection algorithm (SSI) based on a geometric-numerical approach (see [6]). The
geometric phase is concerned with the evaluation of some Starting Points (SP),while the numerical phase consists in a marching algorithm that, starting from theSPs determines the intersection curves through a certain Number of Points (NP).

Reparametrization of NURBS curves 3

Fig. 1. The initial shape (top); the nal shape after the adjustment of weights w3 and w4 (bottom).

We will compare case A of the intersection between the two well-parametrized
surfaces (see Figure 2) with case B relating to the intersection between the same
surfaces, in which the Bottle surface is badly parametrized; in fact it is built as arevolving surface with a badly parametrized circular trajectory curve (see Figure
3).
If the SSI algorithm uses the smallest number of SPs, corresponding to the piecesof the intersection curve on the parametric domain (3 in the example above), in case
A 397 NPs are computed, compared with 794 NPs of case B.
This increased computational cost is due to the fact that the solution for theparametric domain in case A is given by a smoother curve than in case B. In case
B the marching phase encounters problems in the spans of higher curvature making
it impossible to nd a solution in less than 794 NPs.
Allowing algorithm SSI to use a larger number of SPs, a solution is reached incase A with 253 NPs as against 590 NPs in case B.
Other examples where working with badly parametrized curves or surfaces canbe disadvantageous are both uniform and adaptive rendering, motion control incomputer animation, curve/curve intersection, ray/surface intersection in ray tracing, implicitization.

3. Arc length reparametrization of NURBS curves
Let c(t) be a NURBS curve of order m (degree m 1), expressed asc(t) =

K
X
i= m+1

Pi Ri;m (t=wi m+1;    ; wi) t 2 [0; 1]

4 International Journal of Shape ModelingFig. 2. Well-parametrized surfaces; Bottle domain (top), Plane domain (bottom).

Fig. 3. Badly parametrized surfaces; Bottle domain (top), Plane domain (bottom).

Reparametrization of NURBS curves 5

where Pi 2 IR2 are the control points, wi their corresponding positive real weights,
and Ri;m the rational B-spline basis functions de ned on the knot sequence (ti )i= m+1;;m+K where t0 = 0 and tK +1 = 1.
We denote by ri the multiplicity of knot ti , 1  i  K (that is, the numberof times ti occurs in the knot sequence). We assume that ri is always less than orequal to m 1.
Note that at knot ti , 1  i  K, the order of continuity of the homogeneous
curve is m ri 1, since this curve is a nonrational B-spline curve in 3D space.
The arc length parametrization function (t) for c(t) is de ned as : [0; 1] =) [0; L]
 = (t) =with L =

Zt
0

Z1
0

jjc0 (u)jj2du
jjc0 (u)jj2du

where L denotes the length of the curve c(t). Note that the (t) function is strictlyincreasing. In gure 6 two examples of (t) are shown.
Let a reparametrization function be a (t) satisfying the following conditions:: [0; 1] =) [0; ]0(t) > 0 t 2 [0; 1]

then a reparametrized curve can be de ned as^c() = c(1())  2 [0; ]A curve will be reparametrized by arc length when the (t) is the (t) function.
We now assume that ^c() is a reparametrized curve by arc length.
In general ^c() is not a NURBS curve, unless c(t) is a straight line.
We remind the reader that the following relationship holds:

jj^c0 (t)jj2 = 1 8 t 2 [0; 1]This means that the scalar speed of a point moving along the curve is constantand equal to 1. We will assume this to be the property that characterizes the arc
length parametrization of a curve.

4. Approximate reparametrization

Since, as mentioned above, (t) is not a rational function unless c(t) is a straight line,
and because of the need to consider a rational reparametrization function in order6 International Journal of Shape Modelingto obtain a NURBS curve, we are led to determine a (t) approximation by meansof a rational function (t). In this way we hope to obtain a good approximation ofarc length parametrization.
We are searching for a (t) that satis es the following conditions:
1: (t) rational linear function
2: (0) = (0); (1) = (1)3: (t) shape preserving of (t)4: jj (t) (t)jj1 small
Condition 1. is necessary to guarantee that the reparametrized curve remains a
NURBS curve in a space with the same dimension as c(t); condition 2., necessary forthe reason we will describe in the following, together with condition 4., involve thesolution of a problem similar to the best uniform approximation problem (b.u.a.)with interpolatory constraints, by means of a rational linear function. Finally, condition 3. is used to guarantee a small minmax value as a solution to the constrained
b.u.a. problem.
Since in the literature no result relating to the constrained rational b.u.a. problem is known, but results concerned with constrained polynomial b.u.a. problem(see [7]) and with rational b.u.a. problem (see [8]) are known, we have proceeded
as if the results were also valid in the constrained rational case. Hence, we searched
for a (t) function from the set of all functions characterized by the property of
having an error function, (t) (t), that equioscillates at least on two points(m + n + 2 equioscillation points, with m and n respectively the degrees of thenumerator and denominator of the (t) function, minus two points corresponding
to the interpolation constraints at the endpoints).
This way of proceeding guarantees a solution to our problem even with no theoretical support for the b.u.a. problem.

5. Reparametrization on a single interval

The objective of this section is to make a suitable choice for (t). To do this we
will give a characterization of (t) and provide the numerical method used in orderto achieve it.

5.1. Approximate reparametrization function

We consider the following reparametrization function:t) + w(b)(t a) w > 0 t 2 [a; b](t) = (a)(b(b t) + w(t a)which is a linear rational function that interpolates (t) at the endpoints of a genericinterval [a; b].
From a study of its behaviour, for any w we have 0 (t) > 0 8t, that is, the (t)is strictly increasing throughout [a; b]; this implies that it is an invertible function
and therefore can be used as a reparametrization function.

Reparametrization of NURBS curves 7

Moreover, 00 (t) 6= 0 8t, hence the (t) function is either concave or convex on
the interval [a; b]. This property, together with monotonicity, lead us to apply the(t) approximation function only to intervals [a; b] in which (t) is either concave
or convex and this makes us satisfy condition 3 of section 4.

5.2. The second Remez algorithm

The object is to nd a (t) as an approximation of the (t) which is the limit of asequence of (t) that have an error function that alternates on at least two points.
To do this we use the second Remez algorithm (see [8]) in which at each iteration
we check that the maximum error function is still decreasing. If this does not occur,
the procedure is stopped and the penultimate (t) found in the sequence is taken
as the solution.
The following non-linear system, with unknowns d and w, satis es the equioscillation constraints:(ti ) (ti ) = ( 1)i d i = 0; 1that is:
(a)(b t0 ) + w(b)(t0 a) + ( d (t0 ))[b t0 + w(t0 a)] = 0(1)
(a)(b t1 ) + w(b)(t1 a) + (+d (t1 ))[b t1 + w(t1 a)] = 0

Procedure

1. ymax old = 1
2. Let t0 = a + (b 4 a) and t1 = b (b 4 a)
3. Compute d and w explicitly from (1)4. Let e(t) = (t) (t) be the error function and (t0 ; y0 ), (t1 ; y1) such that
y0 =

max
t

sgn(e(t)) = sgn(e(t0))je(t)j and y1 =maxtsgn(e(t)) = sgn(e(t1))je(t)jymax = max(y0 ; y1 )5. If ymax old < ymax then w = w old; go to step 9.
6. Update (t0 ; t1) with (t0; t1) so that the error function has two variations in sign
7. w old = w; ymax old = ymax
8. If ymax jdj >  go to step 3.
9. endProposition System (1) always provides a unique function (t) satisfying theequioscillation property on two points.
Proof. The second equation of (1) can be solved for d so that after substitution in
the rst equation we can reduce the problem to the solution of the following second
degree equation:
w2 + w + = 0

8 International Journal of Shape Modelingwith= [2(b) (t1 ) (t0)](t1 a)(t0 a)= [(a) + (b) (t1 ) (t0 )][(b t0)(t1 a) + (b t1)(t0 a)]= [2(a) (t1 ) (t0)](b t1)(b t0 )Note that the discriminant  is always positive and furthermore  > jbj; this
implies that we obtain two real solutions that are di erent in sign. Hence, theunique alternating function derives from considering the positive w solution 2.

6. Evaluation parameters

In order to test the good or bad quality of approximate reparametrization, we chosethe two parameters p and q and de ned them as follows.
Let0
p :=kk c (t) k2 1 k1
be the displacement from the unit speed; in the case of arc length reparametrization,p is equal to 0.
We consider a uniform subdivision of the parametric domain (i )i=1;;N and wede ne byR
maxi=2;;N  1 k c0 (t) k2 dtRq :=mini=2;;N  1 k c0 (t) k2 dt
i

i
i

i

the displacement from the uniform distribution of the points on the curve; in fact
q is the ratio between the segment of maximum and minimum length of the curve,
where a segment is de ned as a span of curve in between two consecutive points i .
In the case of an arc length parametrization q is equal to 1, as points on the curve
are uniformly spaced.
Parameter q provides more information than parameter p; in fact, 0if the approximation
strip of the unit speed is de ned as that given by [min k c (t) k2; max k
c0 (t) k2 ], parameter p provides only partial information about the strip while q gives
more complete information of its size; in fact
0
max
k
c
(t) k2q  min k c0 (t)k2holds.

7. Numerical results: part 1

In this initial phase seven test curves have been considered, all having convex (t)over the whole parametric domain in order to apply a single approximation (t) as
indicated in section 5.
The curves considered here are chosen of di erent degrees 1, 2, 3 and 4, as
pointed out from their names, and are badly parametrized with respect to arc

Reparametrization of NURBS curves 9

length; the conv1 curves all have uniformly spaced control points and increasing
weights, while the conv2 curves have control points placed at increasing distancesand equal weights.
Table 1 reports the initial value of the evaluation parameters p and q, denoted by
p0 and q0 , and the values after applying a single rational reparametrization to thetest curves. The last column gives the maximum error function e(t) indicated with
MinMax since, in all the cases in our experimentation, Remez algorithm found theb.u.a.; in fact the divergence test of the maximum error function was never positiveand convergence was always reached in three or four iterations.
Further proof that the approximation found was the constrained b.u.a. is givenby the fact that reparametrizing the curve a second time the same parametrization
was obtained.
In fact, it must be remembered that the double reparametrization obtained
through the two functions 1 and 2 is equivalent to a single reparametrization
with the composite 2 ( 1 (t)), which is still a linear rational function; therefore, thefact that the reparametrization does not vary means that the 2 ( 1(t))  1 (t),and then 1 is already the constrained b.u.a. of the (t) with MinMax given byk (t) 1 (t) k1 .
Finally, we can observe that the conv1 d1 curve is a straight line and that our
method manages to reparametrize it exactly at arc length.
Table 1. Reparametrization on a single interval.

T EST CURV ES
conv1 d1
conv1 d2
conv2 d2
conv1 d3
conv2 d3
conv1 d4
conv2 d4

p0

p

q0

3:00
0 15:88
0:80 0:10 3:99
0:69 0:074 3:49
2:20 0:25 7:94
1:33 0:14 4:93
2:24 0:21 12:38
0:93 0:22 5:64

q

1
1:17
1:20
1:48
1:24
1:39
1:45

MinMax0
0:0064
0:012
0:017
0:00780:025
0:036

8. Piecewise adaptive reparametrization
In practice, a c(t) curve will have a strictly increasing (t) which will not be simply
all concave or convex and is therefore dicult to approximate it with a single linear
rational function, that is to satisfy condition 4 of section 4.
As already mentioned, the idea is to approximate the (t) in spans which are
only concave or convex by means of a (t) function.
In other words once a tolerance has been assigned, we propose an adaptive
method that consists in carrying out an adaptive approximation on concave/convex
spans (pieces of (t) function only concave or convex) until the requested toleranceof approximation has been reached on every span. The rst step is to compute an
approximate (t) over the whole parametric domain; if tolerance is not reached, theparametric interval is divided in two intervals to respect the concave/convex spansor divided in half if the correspondent span is already concave or convex.

10 International Journal of Shape Modeling

The approximation is then repeated on each span, dividing it again if necessary
in order to reach tolerance value.
Once the piecewise linear rational function (t)  i (t), with t 2 [si ; si+1 ] 8i,
has been obtained, the reparametrization process consists in subdividing the curvein correspondence of each si by inserting knots (each with multiplicity m), and applying the respective reparametrization i (t) to each curve span c([si ; si+1 ]) (see [1]and [2]). As (t) function will be C 0, see condition 2 of section 4, the reparametrized
curve will be C 0. Note that c(t) consists of many pieces of curve (interior knots
with multiplicity m).
To make it as a NURBS curve once again a procedure of knot-removal is applied
to all knots (see [9]). If this phase is preceded by a suitable scaling of the weightsof each piece of curve (this do not modify the parametrization), the knot-removal isbound to be successful at least once on each knot si by reducing their multiplicity
to at least m 1.
This procedure implies the representation of the reparametrized curve in a spaceof larger dimension than that of the original curve because of the above-mentioned
knot insertion.
To make the assigned tolerance curve length independent ( : [0; 1] =) [0; L]),
we have established to assign a tolerance value as if the curve was of unit length andthen scale it according to the real length of the curve. This involves the invarianceof the reparametrization with respect to a scaling of the curve.
Table 2. Piecewise adaptive reparametrization; tol = 0:005.
T EST CURV ES
conv1 d2
conv2 d2
conv1 d3
conv2 d3
conv1 d4
conv2 d4

9. Numerical results: part 2

p0

0:80
0:69
2:20
1:33
2:24
0:93

p

q0

0:046 3:99
0:039 3:49
0:072 7:94
0:056 4:93
0:098 12:38
0:064 5:64

q

1:07
1:07
1:10
1:11
1:18
1:09

NoI

2
2
3
2
3
2

In this second phase the accuracy of the piecewise adaptive approximation technique is assessed in order to use it as a semi-automatic method to obtain a wellparametrized curve with respect to arc length.
A threshold value of good parametrization has been chosen in the value q = 1:25,
below which parametrization could be considered accurate with regard to arc length;
this value considers the segment of maximumlength as 1=4 greater than the segmentof minimum length of the curve.
Table 1 shows that it is not always possible to arrive at this threshold value
using a single approximation.
In Table 2 we nd the results of the adaptive piecewise approximation method
applied to the same test curves as Table 1, apart from the conv1 d1, with atolerance of tol = 0:005.

Reparametrization of NURBS curves 11

Table 3. Piecewise adaptive reparametrization by approximation function.
T EST CURV ES
coil
sole
flowerstar
heart
guitar

tol

0:01
0:005
0:0005
0:01
0:005
0:0005
0:01
0:005
0:0005
0:01
0:005
0:0005
0:01
0:005
0:0005
0:01
0:005
0:0005

p0

4:71
0:82
1:17
0:72
1:86
1:27

p

0:59
0:59
0:08
0:22
0:16
0:06
0:38
0:26
0:15
0:83
0:21
0:061
0:69
0:62
0:10
0:84
0:84
0:14

Fig. 4. Flower.

q0

q

14:17 1:73
1:68
1:09
2:88 1:49
1:38
1:08
15:71 2:08
1:48
1:19
5:06 4:98
1:46
1:10
32:22 4:09
3:24
1:19
12:56 3:93
3:93
1:25

NoI

6
7
13
4
5
14
6
11
21
8
11
23
4
5
17
12
12
32

12 International Journal of Shape Modeling

The results show that the threshold value has been reached for all the curves.
The last column, marked NoI, reports the number of intervals in which the method
has subdivided the initial parametric domain in order to reach the approximate
precision requested.
Table 3 reports the results relative to six more complex test curves (the (t) is
not always convex), varying in degree, shape and initial parameter values p0 and
q0 .
Figures 4 and 5 show two of the test curves considered, with their relative control
points; the curve and its drawing in dots relating to the initial parametrization are
given above, and below is the nal result after reparametrization with tol = 0:0005.
Figure 6 illustrates the graphs of the initial (t) functions relative to the test
curves of Figures 4 and 5.
An asymptotic reduction of the parameter values p and q, due to a decreasing
tolerance, can be observed in the tests summarized in Table 3, even though this isobtained using numerous subdivisions.
It is observed that all the curves undergoing a tol = 0:0005 go below the threshold value, although the initial values are extremely varied.
However, with bigger tolerances the NoI is fewer, and parametrization is still
accurate. Note that in a geometric design system we can accept a non-optimal
parametrization in order to avoid to split the curve too much.

10. C reparametrization function
1

If the initial curve is at least C 1 it could be useful to determine a reparametrized
curve that is at least C 1. This is made possible by approximating (t) with a (t)that is C 1.
In our piecewise adaptive scheme this was obtained by using the piecewise linear
rational interpolation function (t)  i (t), with t 2 [si ; si+1 ] 8i, de ned as in [10]that is on every two consecutive intervals [si ; si+1 ]; [si+1; si+2 ] such thati0 (si )i (si )
i0 +1 (si+2 )
i+1 (si+2 )
i0 (si+1 )i (si+1 )

= (s
i );
= 0 (si );= (si+2 );= 0 (si+2 );= i0 +1 (si+1 );= i+1 (si+1 ):Table 4, that must be compared with Table 3, reports the results of the method
just described on the six test curves already presented.
We can observe that, in order to avoid excessive subdivisions into spans, a higher
tolerance values must be given. In fact, in order to satisfy the C 1 condition, therequested tolerance value is reached only by making a lot of subdivisions.
However, all these subdivisions lead to a good reparametrization.
As in case C 0, also in C 1 reparametrization, an asymptotic reduction of theparameter values p and q can be experimentally observed.

Reparametrization of NURBS curves 13

Fig. 5. Guitar.

Fig. 6. (t) functions of ower (left) and guitar (right).

14 International Journal of Shape Modeling
Table 4. Piecewise adaptive reparametrization by interpolation function; tol = 0:005.
T EST CURV ES
coil
sole
flowerstar
heart
guitar

p0

p

q0

q

4:71 0:062 14:17 1:12
0:82 0:073 2:88 1:13
1:17 0:13 15:71 1:25
0:72 0:076 5:06 1:12
1:86 0:11 32:22 1:19
1:27 0:19 12:56 1:45

NoI

17
15
29
23
21
42

When the number of subdivisions is the same, the C 0 reparametrization is shown
to be better than the C 1 reparametrization.

11. Conclusions

In this paper we considered the problem of parametric NURBS curves reparametrization. We proposed a concave/convex piecewise adaptive technique in order toapproximate the arc length parametrization function. A linear rational approximation function with constraints was applied to each span. This experimentally proved
to be the best uniform approximation. The proposed method can be used both globally and locally as a semi-automatic technique for improving the parametrizationof curves in a geometric design system in order to reduce the computational costand increase the stability of the numerical methods within the system.

References
1. E.T.Y. Lee and M.L. Lucien , Mobius reparametrization of rational B-splines, Computer
Aided Geometric Design 8 (1991) 213-215.
2. L. Alt , Rational linear reparametrization of NURBS and the blossoming principle,
Computer Aided Geometric Design 10 (1993) 465-467.
3. R.T. Farouki and T. Sakkalis , Real rational curves are not 'unit speed', Computer
Aided Geometric Design 8 (1991) 151-157.
4. B. Guenter and R. Parent , Computing the Arc Length of Parametric Curves, IEEE
Computer Graphics & Applications (May 1990) 72-78.
5. R.J. Sharpe and R.W. Thorne , Numerical method for extracting an arc length parameterization from parametric curves, Computer-Aided Design 14 (1982) 79-81.
6. G. Casciola and S. Morigi , Il problema SSI nella modellazione solida con super ci
NURBS, Accademia delle Scienze dell' istituto di Bologna serie V, n.6 (1995) 107-127.
7. F. Deutsch , On uniform approximation with interpolatory constraints, Journal of
Mathematical Analysis and Applications 24 (1968) 62-79.
8. E.W. Cheney , Introduction to Approximation Theory (McGraw-Hill, 1966).
9. W. Tiller , Knot-removal algorithms for NURBS curves and surfaces, Computer-Aided
Design 24 (1992) 445-453.
10. R.D. Fuhr and M. Kallay , Monotone linear rational spline interpolation, Computer
Aided Geometric Design 9 (1992) 313-319.