simpson@trwrb.UUCP (Scott Simpson) (12/16/87)
I am trying to get a simple spline algorithm and am having a heck of a time.
I purchased the book "Computer Graphics" by Donald Hearn and M. Pauline Baker,
Prentice-Hall 1986 because I saw they had a spline algorithm in it.
Unfortunately, I have come to the conclusion their spline equation is wrong.
The computer seems to agree with me when I test it. The equation they give
for the blending function is the recursive equation
{ 1 if u <= u < u
N (u) = { k k+1
k,1 {
{ 0 otherwise
u-u u - u
k k+t
N (u) = --------- N (u) + ---------- N (u)
k,t u - u k,t-1 u - u k+1,t-1
k+t-1 k k+t k+1
This is a parametric equation for a spline. There are n+1 control points
and u varies from 0 to n-t+2. We set up n+t subintervals. If the denominators
evaluate to 0, the term is assigned 0.
The book has some pictures of 5 blending functions that seems to make
sense. In the first one, N (u), the blending function with u equal zero
0,3
has the value 1, and the rest of the pictures have the value 0. This means
that we should get the first point at u=0 if we combine all the blending
functions. However, the equation above never yields the value 1 at u=0
as it should. If we substitute N (0) in the above equation, we get
0,3
0 rather than 1. Here is why: the first term of N (0) is
0,3
zero because the numerator u-u = u-u = 0. The second term is also zero
k 0
since N (0) is zero. The reason N (0) is zero is because it expands
1,2 1,2
into a function with the two "N" terms N (0) and N (0). Now notice
1,1 2,1
that we must go to ending condition of the recursion. This ending condition
will only be 1 if k=0, which it is not in either of these two "N" terms.
Consequently, N (0) always yields zero. Do any spline experts out there
0,3
have a fix? I have perused many spline books and papers and I am not
making any headway. I'm not a math expert so please don't inundate me
with theory.
--
Scott Simpson
TRW Space and Defense Sector
...{decvax,ihnp4,ucbvax}!trwrb!simpson (UUCP)
trwrb!simpson@trwind.trw.com (ARPA)mae%vygr@Sun.COM (Mike Ekberg, Sun {Graphics Product Division}) (12/18/87)
Nelib has source code for splines from De Boors(sp?) book on splines. Why re-invent the wheel(is a circle a spline?). mike (sun!mae), M/S 5-40 "Maybe I'm a dreamer, but I'm not the only one."
simpson@trwrb.UUCP (Scott Simpson) (12/18/87)
Spencer Thomas of the University of Utah answered my question. It seems I
was using the wrong knot vector. If you use the knot vector
{ 0 if j < t
u = { j-t+1 if t<=j<=n
j { n-t+2 if j>n
where t-1 is the degree of your polynomial and n+1 is the number of control
points it seems to work. Many others volunteered valuable references to
spline books for computer programmer idiots like myself. Stu Friedberg at
Rochester sent me a bunch of spline code. To all of you, thanks a lot!
--
Scott Simpson
TRW Space and Defense Sector
...{decvax,ihnp4,ucbvax}!trwrb!simpson (UUCP)
trwrb!simpson@trwind.trw.com (ARPA)trainor@CS.UCLA.EDU (12/27/87)
Brian Barsky's book should've been published by now. Anyone seen it? douglas
rhbartels@watcgl.waterloo.edu (Richard Bartels) (12/29/87)
In article <10054@shemp.UCLA.EDU>, trainor@CS.UCLA.EDU writes: > > Brian Barsky's book should've been published by now. Anyone seen it? > One book of approximately that description is: An Introduction to Splines for Use in Computer Graphics and Geometric Modeling Richard Bartels, John Beatty, and Brian Barsky Morgan Kaufmann Publishers, Palo Alto, California (1987)