Graphics Reference
In-Depth Information
dealing with simple polynomial functions, there are efficient algorithms so that using
them in a modeler is not all that bad.
We start with the problem of computing a B-spline curve p(u) of order k and
degree m = k - 1 with knots vector U = {u
0
,u
1
,...,u
n+k
}. Actually, because tangent
vectors and derivatives of parametric curves are often needed in geometric modeling,
we present an efficient algorithm that computes not only the value p(u) but also its
derivatives up to any order d at the same time.
The first thing that we must do is find the nondegenerate span to which u belongs.
This can be done using Algorithm 11.5.4.1. The function SpanIndex returns the index
r so that u Π[u
r
,u
r+1
), where u
r
< u
r+1
, unless u is the right endpoint u
n+1
of the domain
of the curve and there might not be such an r, in which case we return n and will have
u Π(u
n
,u
n+1
]. To avoid the special case one could also restrict the domain of the curve
to [u
m
,u
n+1
-e], where e is some small positive value.
Now assume that u Π[u
r
,u
r+1
), where u
r
< u
r+1
, or u = u
n+1
and u Π(u
r
,u
r+1
]. We
know that
n
r
Â
Â
()
=
()
=
()
pu
Nu
p
Nu
p
,
ik
,
i
i k
,
i
i
=
0
irm
= -
integer function
SpanIndex (
real array
knots [0.. ];
integer
n, m;
real
u)
{
Inputs:
u
i
= knots[i] , 0 £ i £ n + m + 1 - the knots
n + 1 = number of control points
m - the degree of the B-spline basis functions }
begin
integer
lo, hi, mid;
if
(u = knots[n+1])
return
n;
{ Now do a binary search of u
m
, u
m+1
, º , u
n+1
}
lo := m; hi := n + 1; mid := (lo + hi)/2;
while
(u < knots[mid])
or
(u >= knots[mid+1]
do
begin
if
(u < knots[mid])
then
hi := mid
else
lo := mid;
mid := (lo + hi)/2;
end
;
return
mid;
end
;
Algorithm 11.5.4.1.
A B-spline span-finding algorithm.
