Derivative of B-Spline basis function..........

Derivative of B-Spline basis function..........

Post by Stuart McKinno » Sun, 13 Apr 2003 01:06:07



hi,

could you please help me?

i'm at the stage of writing a surface interrogation program where everything
is in place and it should all work.

but, for some reason my unit normal calculator is giving me incorrect
results.

I think the problem lies in my derivatives of the B-Spline basis function
(i'm using NURBS).

could anyone point me in the direction of a correct, working version of the
b-spline derivative?

thanks
STU

p.s. just to make sure i'm not being stupid:
to calculat the normal at a point on a NURBS surface, do the cross product
of the two tangent vectors.
to get these tangent vectors (one for u and one for v(the paameters)) you
apply the same NURBS formula as to find a point but replace either the u or
v basis functions with its derivative.

correct????

 
 
 

Derivative of B-Spline basis function..........

Post by Dave Eberl » Sun, 13 Apr 2003 02:05:29



Quote:> i'm at the stage of writing a surface
> interrogation program where everything
> is in place and it should all work.

> but, for some reason my unit normal
> calculator is giving me incorrect
> results.

> I think the problem lies in my derivatives
> of the B-Spline basis function (i'm using
> NURBS).

> could anyone point me in the direction of
> a correct, working version of the
> b-spline derivative?

I think my version computes these correctly.
http://www.magic-software.com/Surface.html

Quote:> p.s. just to make sure i'm not being stupid:
> to calculat the normal at a point on a NURBS
> surface, do the cross product of the two
> tangent vectors.

Yes, And remember to normalize the result to
get a unit length vector.

Quote:> to get these tangent vectors (one for u and
> one for v(the paameters)) you apply the same
> NURBS formula as to find a point but replace
> either the u or v basis functions with its
> derivative.

This should work.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Stuart McKinno » Sun, 13 Apr 2003 02:34:56


hi

sorry, where exactly are they??
i can't seen to find what i'm looking for

thanks
STU




> > i'm at the stage of writing a surface
> > interrogation program where everything
> > is in place and it should all work.

> > but, for some reason my unit normal
> > calculator is giving me incorrect
> > results.

> > I think the problem lies in my derivatives
> > of the B-Spline basis function (i'm using
> > NURBS).

> > could anyone point me in the direction of
> > a correct, working version of the
> > b-spline derivative?

> I think my version computes these correctly.
> http://www.magic-software.com/Surface.html

> > p.s. just to make sure i'm not being stupid:
> > to calculat the normal at a point on a NURBS
> > surface, do the cross product of the two
> > tangent vectors.

> Yes, And remember to normalize the result to
> get a unit length vector.

> > to get these tangent vectors (one for u and
> > one for v(the paameters)) you apply the same
> > NURBS formula as to find a point but replace
> > either the u or v basis functions with its
> > derivative.

> This should work.

> --
> Dave Eberly

> http://www.magic-software.com
> http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Dave Eberl » Sun, 13 Apr 2003 02:47:50



Quote:> sorry, where exactly are they??
> i can't seen to find what i'm looking for

I assume you got to the HTML page?  On that
page are sections:
  "B-spline rectangle patch surfaces (tensor product spline)."
and
  "NURBS rectangle patch surfaces (tensor product spline)."

There are links to files.  The files
MgcBSplineBasis.{h,inl,cpp} implement the
B-spline basis functions and their derivatives.

The files MgcBSplineRectangle.{h,inl,cpp} have
an implementation of a B-spline rectangle patch
including member functions to compute position
and derivatives.

The files MgcNURBSRectangle.{h,inl,cpp} have
an implementation of a NURBS rectangle patch
including member functions to compute position
and derivatives.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Stuart McKinno » Sun, 13 Apr 2003 03:14:26


hi

yes i've got those, but i don't understand the code!!

i was looking for the actual equation.

thanks

STU




> > sorry, where exactly are they??
> > i can't seen to find what i'm looking for

> I assume you got to the HTML page?  On that
> page are sections:
>   "B-spline rectangle patch surfaces (tensor product spline)."
> and
>   "NURBS rectangle patch surfaces (tensor product spline)."

> There are links to files.  The files
> MgcBSplineBasis.{h,inl,cpp} implement the
> B-spline basis functions and their derivatives.

> The files MgcBSplineRectangle.{h,inl,cpp} have
> an implementation of a B-spline rectangle patch
> including member functions to compute position
> and derivatives.

> The files MgcNURBSRectangle.{h,inl,cpp} have
> an implementation of a NURBS rectangle patch
> including member functions to compute position
> and derivatives.

> --
> Dave Eberly

> http://www.magic-software.com
> http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Dave Eberl » Sun, 13 Apr 2003 03:47:33



Quote:> yes i've got those, but i don't understand
> the code!!

> i was looking for the actual equation.

Ah, yes.  The ever elusive "equation"...

I implemented this code by reading Dave Roger's
book "An Introduction to NURBS:  with Historical
Perspective".  The key observation is that rather
than apply the recursive B-spline basis function
formula from the top-down, you work from the
bottom-up (Roger's "dependency" picture for the
bottom-up is not quite right).  By doing this
you gain some efficiency in the calculations.
The function BSplineBasis::Compute(...) is what
implements this.

I wish I could say that the implementation is a
simple coding of an "equation", but in fact that
is not the case.  Getting it implemented and
getting it right do take a bit of effort.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Stuart McKinno » Sun, 13 Apr 2003 03:56:54


hi

surly the equation is what SHOULD be implemented?!?!?

for example, the B-Spline basis function is defined by:

N_i_p(t)    =    N_i_p-1(t)    *    (t - T_i)  /  (T_i+p - T_i)

     +    N_i+1_p-1(t)    *    (T_i+p+1  - t)  /  (T_i+p+1  -  T_i+1)

where T is the knot vector, p is the degree and t is the parameter

is the derivative basis function not just the derivative of this? (ignoring
computational efficiency!)

thanks again
STU

> Ah, yes.  The ever elusive "equation"...

> I implemented this code by reading Dave Roger's
> book "An Introduction to NURBS:  with Historical
> Perspective".  The key observation is that rather
> than apply the recursive B-spline basis function
> formula from the top-down, you work from the
> bottom-up (Roger's "dependency" picture for the
> bottom-up is not quite right).  By doing this
> you gain some efficiency in the calculations.
> The function BSplineBasis::Compute(...) is what
> implements this.

> I wish I could say that the implementation is a
> simple coding of an "equation", but in fact that
> is not the case.  Getting it implemented and
> getting it right do take a bit of effort.

> --
> Dave Eberly

> http://www.magic-software.com
> http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Dave Eberl » Sun, 13 Apr 2003 04:16:16



Quote:> surly the equation is what SHOULD be implemented?!?!?

> for example, the B-Spline basis function is defined by:

> N_i_p(t)    =    N_i_p-1(t)    *    (t - T_i)  /  (T_i+p - T_i)

>      +    N_i+1_p-1(t)    *    (T_i+p+1  - t)  /  (T_i+p+1  -  T_i+1)

> where T is the knot vector, p is the degree and t is the parameter

> is the derivative basis function not just the derivative of this?
(ignoring
> computational efficiency!)

Yes, you just take the derivative.  However, my implementation
does not ignore the computation efficiency :)  When you implement
NURBS on top of this, you have the additional complication of
taking the derivative of ratios X/W, Y/W, and Z/W.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Stuart McKinno » Sun, 13 Apr 2003 04:25:38


what do you mean by taking the derivative of ratios?

don't you just calculate the 4 coordinates (x, y, z & w) then devide the
first three by the fourth?

do this for partial derivetive in u and v then take the cross product?

thanks
STU

> Yes, you just take the derivative.  However, my implementation
> does not ignore the computation efficiency :)  When you implement
> NURBS on top of this, you have the additional complication of
> taking the derivative of ratios X/W, Y/W, and Z/W.

> --
> Dave Eberly

> http://www.magic-software.com
> http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Just d' FAQ » Sun, 13 Apr 2003 05:02:41


On Fri, 11 Apr 2003 17:06:07 +0100, "Stuart McKinnon"


>p.s. just to make sure i'm not being stupid:
>to calculat the normal at a point on a NURBS surface, do the cross product
>of the two tangent vectors.
>to get these tangent vectors (one for u and one for v(the paameters)) you
>apply the same NURBS formula as to find a point but replace either the u or
>v basis functions with its derivative.

What if I discuss the derivative for a curve, and you tell me if
that's what you do? It would be nice if we could use the easy method
non-rational curves allow, but division by a polynomial prevents us.

Let's do a first quadrant circular arc, with classic p = [x/w,y/w]:

  x(t) = 1 - t^2
  y(t) = 2t
  w(t) = 1 + t^2

Without the weights, w, no problem. The quadratic Bezier curve with
control points Q0, Q1, Q2 has derivative with linear Bezier difference
control points L0 = 2(Q1-Q0) and L1 = 2(Q2-Q1).

  Q0 = [1,0]    Q1 = [1,1]    Q2 = [0,2]
  L0 = [0,2]    L1 = [-2,2]

Our w control values are 1, 1, and 2; so our rational Bezier curve has
control points

  C0 = [1,0;1]    C1 = [1,1;1]    C2 = [0,1;2]

We *cannot* simply difference these to get derivative controls! For,
the horizontal values and vertical values are given by

  h = (1-t^2) / (1+t^2)
  v = 2t / (1+t^2)

with derivatives

  h' = -4t / (1+2t^2+t^4)
  v' = (2-2t^2) / (1+2t^2+t^4)

Clearly we will need a quartic rational Bezier curve just to handle
the weights.

Does this fit your idea? If not, you need to get the right formulae;
otherwise, it's probably just a coding typo.

 
 
 

Derivative of B-Spline basis function..........

Post by Dave Eberl » Sun, 13 Apr 2003 05:11:12



Quote:> what do you mean by taking the derivative of ratios?

> don't you just calculate the 4 coordinates (x, y, z & w) then devide the
> first three by the fourth?

> do this for partial derivetive in u and v then take the cross product?

To summarize what 'Just' said:  The derivative of a quotient is
*not* the quotient of the derivatives.  Perhaps this is where
your code is producing unexpected results.

If you have computed the B-spline (x,y,z,w), then
the 3D surface is X = x/w, Y = y/w, and Z = z/w.
The partial derivative of X with respect to u is
  dX/du = (w*dx/du - x*dw/du)/w^2
Similar for the other two components.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Derivative of B-Spline basis function..........

Post by Stuart McKinno » Sun, 13 Apr 2003 05:47:45


Thanks,

i think that might solve the problem.  just a slight oversight!!!

thanks again
STU

> To summarize what 'Just' said:  The derivative of a quotient is
> *not* the quotient of the derivatives.  Perhaps this is where
> your code is producing unexpected results.

> If you have computed the B-spline (x,y,z,w), then
> the 3D surface is X = x/w, Y = y/w, and Z = z/w.
> The partial derivative of X with respect to u is
>   dX/du = (w*dx/du - x*dw/du)/w^2
> Similar for the other two components.

> --
> Dave Eberly

> http://www.magic-software.com
> http://www.wild-magic.com

 
 
 

1. --Derivatives from recursive Bsplines?

Greetings!

I am currently looking to expand my newly created bspline interpolation
routine to include derivatives.  While I am currently able to approximate
the curve through my data points to get f(x) for every x, I would also
like to return at least f'(x), but preferably f''(x) as well.

I have seen several methods to calculate derivatives from a bspline
implementation that explicitly solves the relevant system of linear
equations.  I have not seen, however, methods to calculate derivatives
from the very common recursive algorithm.

For a bit of background, here is the core of my recursive method:

        double blend (int k, int n, int *u, double v) {

           /* declarations, base case, branches, etc....
            *
            *   n = order of spline
            *   k = number of polynomial segments
            *   u = uniform knot vector (multiplicity n at each end)
            *   v = interval on spline
            */

           value =   (v-u[k]) / (u[k+n-1]-u[k]) * blend(k  ,n-1,u,v) +
                   (u[k+n]-v) / (u[k+n]-u[k+1]) * blend(k+1,n-1,u,v);

           /* ... */

           return value
        }

        void spline_pnt (...) {
           /* ... */

           for (k=0; k<nc; k++) {    /* nc = number of control points */
              temp = blend(k,n,u,v); /* cx, cy = control point coords. */
              (*sx) += temp*cx[k];   /* sx, sy = spline coords (x, f(x))*/
              (*sy) += temp*cy[k];
           }

           /* ... */
        }

Is there a clean way to simultaneously back out the derivatives with
the interpolated points using the recursive approach?  At this point
I would prefer to keep what I have developed so far instead of switching
methods.  While I can certainly go back and apply finite differences to
f(x), I have to believe that the derivatives are available recursively
as well.

Any pointers would be much appreciated as my attempts have been
unsuccessful to date... of course, I have a nasty tendency to mess
up my indexing occasionally!

BTW, are there any other relevant newsgroups to post this too?  I'm just
beginning to explore the details of splines, but even so, I know that they
have been effectively applied in all sorts of disciplines.  Many thanks!

-Brian

2. program games in Taiwan

3. HELP! basis derivatives

4. Removing jags on captured video frames?

5. Explicitely specifying first derivative in cublic spline algorithm

6. 2nd Annual International AVS User Group Conference (AVS '93)

7. Function derivative over a mesh

8. Derivative of sampled 2D functions

9. Better Bspline Function evaluators?

10. curves: hermite, bezier, spline, bspline, nurbs

11. Spline and BSpline

12. Fast interpolation using radial basis functions