Bspline Curve and Surface Evaluation
Abstract
Using the Taylor expansion, a Bspline segment can be efficiently represented in
the power basis. Consequently, we can use the Horner algorithm to evaluate points
and derivatives with respect to a given set of parameters. Our approach is a
generalization of W. Böhm's algorithm.
1 Introduction
A vectorvalued rational curve may be represented as
R(t)=[(P(t))/W(t)], where P:Â®Â^{d} and W:Â®Â
are polynomials. Using the Leibnitz formula, we can derive that the mth
derivative of R(t) is given by
R^{(m)}(t)= 
P^{(m)}(t) 
m å
i=1

C_{m}^{i}R^{(mi)}(t)W^{(i)}(t) 
W(t)

, 

where, C_{m}^{i}=[m!/(i!(mi)!)]. Similarly, differentiating a rational
surface, S(u,v)=[(P(u,v))/W(u,v)], m times in u and l times
in v yields:
S^{(m+l)}_{umvl}(u,v)= 
P^{(m+l)}_{umvl}(u,v) 
(m,l) å
(i,j) ¹ (0,0)

C_{l}^{j}C_{m}^{i}S_{umivlj}^{(lj+mi)}(u,v) W^{(j+i)}_{uivj}(u,v) 
W(u,v)

. 

As it is seen, the evaluation of a rational curve/surface is actually based on
evaluation of a polynomial curve/surface. Therefore, we limit our discussion to
polynomial curves and surfaces in this paper.
A piecewise polynomial Bspline curve of order k (or degree n=k1) may be
given by
P(t)= 
å
i

d_{i} N_{i,k}(t), 
 (11) 
where, d_{i} Î Â^{d} are the de Boor (control) points and N_{i,k}(t) the
Bspline basis functions.^{3} In CAGD applications, we often need to
evaluate points and derivatives on a certain Bspline segment with respect to
a given set of parameters. In this case, we may represent this segment in the
power basis and evaluate it efficiently using the Horner algorithm.
One way to represent a Bspline segment in the power basis is to convert the
segment first into the Bézier basis using knot insertion technique, then
into the power basis. Böhm proposed an alternative approach in which he
computes the Taylor expansion of a Bspline segment.^{2} His approach is
more efficient than the first one. In this paper, we extend his algorithm to
Bspline surfaces and give details for implementation.
2 Taylor expansion of Bspline curves
A Taylor expansion of a Bspline segment was proposed by Böhm.^{2} For
completeness, we briefly review his method in this section and give our
pseudocode that minimizes the use of computer memory.
Let d^{0,0}_{i}=d_{i} with d_{i} being the de Boor points in (11).
Then, the mth derivative of P(t) is given by:^{4,5}
P^{(m)}(t)=(k1)(k2)¼(km) 
å
i

d_{i}^{m,m}N_{i,km}(t) 

where,
d_{i}^{m,m}= 
d_{i}^{m1,m1}d_{i1}^{m1,m1} t_{i+km}t_{i}

= 
d_{i}^{m1,m1}d_{i1}^{m1,m1} g_{i}^{m}

(m=1,¼,n). 
 (21) 
Using the de Boor's knot insertion method, we may represent P^{(m)}(t) in
a lower degree form:
P^{(m)}(t)=(k1)(k2)¼(km) 
å
i

d_{i}^{p,m}N_{i,kp}(t) 

where,^{2,3}
d^{p,m}_{i}=d^{p1,m}_{i1}+(tt_{i})d^{p,m+1}_{i} = d^{p1,m}_{i1}+b_{i}d^{p,m+1}_{i} (p=m+1,¼,n). 
 (22) 
For t Î (t_{j},t_{j+1}), N_{i,1}(t)=d_{i,j} (d_{i,j}=1 if i=j,
otherwise d_{i,j}=0). Therefore, when p=n, we have
P^{(m)}(t)=(k1)(k2)¼(km)d_{j}^{n,m} (m=0,1,¼, n). 

Accordingly, the evaluation of a point and m (m £ n) derivatives at
t Î (t_{j},t_{j+1}) reduces to computing d^{n,0}_{j},d^{n,1}_{j},¼,d^{n,m}_{j}. When m > n, P^{(m)}(t)=0 since P(t) is a polynomial
curve of degree n.
For t^{*} Î (t_{j},t_{j+1}), it is known N_{i,k}(t^{*}) > 0 if i=jn,jn+1,¼,j and N_{i,k}(t^{*})=0 elsewhere. Therefore, to evaluate a point and
derivatives at t^{*} Î (t_{j},t_{j+1}) requires:
 k relevant de Boor points ranging from d_{jn} to d_{j}.
 2×n relevant knots, ranging from t_{jn+1} to t_{j+n}, to compute g_{i}^{m}.
 n relevant knots, ranging from t_{jn+1} to t_{j}, to compute b_{i}.
In consideration of the above facts, we present the following pseudocode which
minimizes the number of divisions and the amount of memory space used:
(1) Compute g^{p}_{i} and b_{p}:
Let [^t]_{i}=t_{jn+i}, where i=1,¼,2×n.
do p=1, n
do i=p, n
g^{p}_{i} = 1 / ([^t]_{i+kp}
[^t]_{i})
enddo
b_{p}=t^{*}[^t]_{p}
enddo
(2) Compute d^{m,m}_{i} using equation (21):
Let d^{0,0}_{i}=d_{jn+i}, where, i=0,1,¼,n.
do m=1, n
do i=m, n
d_{i}^{m,m}=g^{m}_{i}(d_{i}^{m1,m1} d^{m1,m1}_{i1})
enddo
enddo
(3) From d^{m,m}_{jn+m} we compute d^{p,m}_{jn+p} using
equation (22):
do p=1, n
do m=p1, 0, 1
d^{p,m}_{m}=d^{p1,m}_{m} +b_{p}d^{p,m+1}_{m+1}
enddo
enddo
For d_{i} Î Â^{d}, it is seen that the computation of d^{n,m}_{j}
(m=0,1,¼,n) requires [(n(n+1))/2] divisions and
d×n×(n+1) multiplications. (Evaluation of a point using the knot
insertion algorithm requires [(n(n+1))/2] divisions and
[(d×n×(n+1))/2] multiplications.) After obtaining
d^{n,i}_{j} at t^{*} Î (t_{j},t_{j+1}), the Taylor expansion of the Bspline segment corresponding
to t Î [t_{j},t_{j+1}] is given by
P(t)= 
n å
i=0


P^{(i)}(t^{*}) i!

(tt^{*})^{i} = 
n å
i=0


d^{n,i}_{j} C_{n}^{i}

(tt^{*})^{i}. 

We have assumed that t^{*} Î (t_{j},t_{j+1}). However, if the knot sequence has
a multiplicity r with respect to t^{*}, we may choose j such that
t^{*} Î (t_{j},t_{j+1}] or t^{*} Î [t_{j},t_{j+1}). This depends on whether the
``left'' or ``right'' segment is evaluated.
3 Taylor expansion of Bspline surfaces
A Bspline surface of order k_{u} in u and k_{v} in v is given by
S(u,v)= 
å
i


å
j

N_{i,ku}(u)N_{j,kv}(v)d_{i,j}. 

We may write a Bspline surface as
S(u,v)= 
å
j

N_{j,kv}(v)d_{j}(u), 
 (31) 
where
d_{j}(u)= 
å
i

N_{i,ku}(u)d_{i,j}. 

Assume (u^{*},v^{*}) Î (u_{ju},u_{ju+1})×(v_{jv},u_{jv+1}). By
considering (31) as a Bspline curve with parameter v, we can evaluate
S^{(l)}_{vl}(u,v) (l=0,1,¼,n_{v}) at v^{*} using the same approach
for curve and obtain:
S^{(0)}(u,v^{*})=d_{jv}^{nv,0}(u) = å_{i} N_{i,ku}(u)d_{i,jv}^{nv,0}
S^{(1)}_{v}(u,v^{*})=(k_{v}1)d_{jv}^{nv,1}(u) = å_{i} N_{i,ku}(u)d_{i,jv}^{nv,1}
¼
S^{(l)}_{vl}(u,v^{*})=(k_{v}1)¼(k_{v}l)d_{jv}^{nv,l}(u) = å_{i} N_{i,ku}(u)d_{i,jv}^{nv,l}
Further evaluation of S^{(l)}_{vl}(u,v^{*}) at u^{*} Î (u_{ju},u_{ju+1})
requires only k_{u} de Boor points whose i indices range from j_{u}n_{u} to
j_{u}. Therefore, we should implement the algorithm so that it minimizes the
use of memory space and requires only [(k_{v}×(k_{v}1))/2] divisions
and d×k_{v}×(k_{v}1)×k_{u} multiplications to compute all
S^{(l)}_{vl}(u,v^{*}). Having obtained S^{(l)}_{vl}(u,v^{*}), we can
further evaluate S^{(m+l)}_{umvl}(u,v^{*}) at u^{*}, which is equivalent
to evaluating k_{v} Bspline curves.
The above approach evaluates S(u,v) first in v then in u. However, it
should be noted that if k_{u} < k_{v}, we will save computation time by evaluating
S(u,v) first in u then in v. Since the alternative approach is
symmetric, we shall not discuss it again.
Given all partial derivatives of a polynomial surface S(u,v) at
(u^{*},v^{*}), we can represent the surface in the power basis by the Taylor
expansion:
S(u,v)=S(u^{*},v^{*})+ 
æ ç
è

x 
¶ ¶u

+ y 
¶ ¶v

ö ÷
ø

S(u^{*},v^{*})+¼+ 
1 n!


æ ç
è

x 
¶ ¶u

+y 
¶ ¶v

ö ÷
ø

n

S(u^{*},v^{*}) 

where n=n_{u}+n_{v}, x=uu^{*}, y=vv^{*}, and

æ ç
è

x 
¶ ¶u

+y 
¶ ¶v

ö ÷
ø

k

S(u^{*},v^{*})= 
k å
i=0

C_{k}^{i} 
¶^{k} S(u^{*},v^{*}) ¶u^{ki}¶v^{i}

x^{ki}y^{i} , k=1,2,¼,n 

For a polynomial surface, it is noted that, if ki > n_{u} or i > n_{v},

¶^{k} S(u^{*},v^{*}) ¶u^{ki}¶v^{i}

=0. 

Therefore,

1 k!


æ ç
è

x 
¶ ¶u

+y 
¶ ¶v

ö ÷
ø

k

S= 
k å
i=0


C_{k}^{i} k!


¶^{k} S ¶u^{ki}¶v^{i}

x^{ki}y^{i} = 
min{k,n_{v}} å
i=max{0,kn_{u}}


C_{k}^{i} k!


¶^{k} S ¶u^{ki}¶v^{i}

x^{ki}y^{i}. 

To speed up computation, we may create a coefficient table for
[(C_{k}^{i})/k!]=[1/(i!(ki)!)].
4 Horner algorithm
Given a cubic curve P(t)=a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}
with a_{i} Î Â^{d}, we may evaluate the curve efficiently using the
wellknown Horner method:
P(t) = t[t(a_{3}t+a_{2})+a_{1}]+a_{0}. 

As it is seen, only three multiplications are involved. To evaluate the first
derivative, we may compute first P^{¢}(t)=a_{1}+2a_{2}t+3a_{3}t^{2}, then
the value of the first derivative using the Horner method. In this way, it is
readily checked that d(3n2) multiplications are required to compute a point
and the first derivative. An improved algorithm in computing a point and the
first derivative can be found in Acton's book.^{1} Writing the first
derivative as
P^{¢}(t)=t[a_{3}t+(a_{3}t+a_{2})]+t(a_{3}t+a_{2})+a_{1}, 

reveals the relation between the evaluation of a polynomial and its first
derivative. This is summarized in the following pseudocode:
point = a(n) * t + a(n1)
deriv = a(n)
do j = n2, 0, 1
deriv = deriv * t + pt
point = point * t + a(j)
enddo
It is seen that only d(2n1) number of multiplications involved. Let
eval(j) denote the jth derivative. We extend the improved algorithm to the
evaluation of m derivatives.
eval(0) = a(n) * t + a(n1)
eval(1) = a(n)
do i=n2, 0 , step=1
k = min(m,ni)
do j=k, 1, step=1
eval(j) = eval(j) * t + eval(j1)
enddo
enddo
c multiply derivatives by factorial constant:
k = 1
do i=2, m
k = k * i
eval(i) = eval(i) * k
enddo
It is readily checked that only d([(n(n+1))/2] + 3(n1))
multiplications are required to evaluate a point and all n derivatives.
We can extend the above method to a surface. Given a vectorvalued surface
S(u,v)= 
m å
j=0


n å
i=0

a_{ij}u^{i}v^{j}, 

we may represent it in the following form:
S(u,v)= 
m å
j=0

a_{j}(u) v^{j}, 
 (41) 
where a_{j}(u)=å_{i=0}^{n}a_{ij}u^{i}. By considering (41) as a
polynomial curve in v, we can use the algorithm in evaluating a curve to
obtain S(u,v),S_{v}^{(1)}(u,v),¼. Then, with respect to
S(u,v),S^{(1)}_{v}(u,v) and so on, we compute derivatives in terms of
u.
5 Conclusions
In CAD/CAM systems, curves and surfaces are usually represented in the Bspline
form. Evaluation of a Bspline curve/surface may be carried out using the knot
insertion technique. However, if we want to evaluate a set of points and
derivatives on certain Bspline segments, algorithms based on knot insertion
are very costly. In this case, a better solution is to represent these Bspline
segments in the power basis using the Taylor expansion. Then, evaluation of a
curve/surface can be done efficiently using the Horner method.
6 References
[1] Acton, Forman S.: Numerical Methods That Work, Harper and Row,
New York, 1970.
[2] Böhm, W.: Efficient evaluation of splines, Computing (33), 171177
(1984)
[3] de Boor, C.: A Practical Guide to Bspline, SpringerVerlag,
New York, 1978.
[4] Hoscheck, J. and Lasser, D.: Fundamentals of Computer Aided
Geometric Design, A K Peter, Ltd, 1993.
[5] Farin, G.: Curves and Surfaces for Computer Aided Geometric Design,
Academic Press, Inc, 1988.
RETURN