In article <3b17c237@news.povray.org>, Warp  <war### [at] tagpovrayorg> wrote:
>Ron Parker <ron### [at] povrayorg> wrote:
>: Not really.  Bezier patches/bicubic patches are neither non-uniform nor
>: rational.

Ok, there's about 4 types of curves being discussed here, from (mathematically)
simplest to most complex, they are:

	Bezier curves
	Bicubic patches
	B-Splines (uniform, non-rational)
	NURBS (which stands for non-uniform, rational, b-spline)

All of them are based on the idea of a set of control points, and a set of
blending functions.

Starting in 2 dimensions, with Bezier curves:

A curve can be defined in terms of a single parameter, (typically 's' or 't'
are used, depending on your mathematical background) which represents the
normalized distance along the curve, from it's starting point (control point 0) 
towards it's ending point (for a Bezier curve, this is control point 3, 
although the algorithim could be generalized to any number of points).  By
'normalized distance' I mean that the parameter (I'll use 't') is 0 at the 
starting point, and 1 and the ending point.

Each control point will have an x and y co-ordinate (<x0,y0> to <x3,y3>), and
an associated blending function.  

For Bezier curves, the blending functions are just the standard expansion
of ( t * (1-t) ) ^3, seperated according to the power of the 't' term.

(Historically, I don't think this was the motivation for development of
 this set of blending functions, but this is how it works out)

So blending function 3 is t^3.
	b.f. 2 = 3 * (t ^2)*(1-t)
	b.f. 1 = 3 * t * ( (1-t)^2)
	b.f. 0 = (1-t)^3

For any value of t, it is then possible to evaluate an <x,y> position by
the formula:

	R = (point 0 * blending function 0) + (p1 * bf1) + (p2 * bf2) +
		(p3 * bf3)

If you examine the blending functions, you'll notice that at t=0 blending
functions 1 to 3 are all 0, and blending function 0 is 1, so R = point 0.
Similarly at t=1, blending functions 0 to 2 are all 0, and blending fucntion3
is 1, so R = point 3.  I.e. the curve passes through the start and end points.
It does not, however, always pass through points 1 and 2 (although there are
cases where it does)

The curve is drawn by evaluating <x,y> for various values of t, and joining
the results with line segments.  Obviously the more values of t you evaluate
for, the smoother the curve that will be drawn.

Bicubic patches are generalizations of Bezier curves into 3-dimensional
sheets.  Instead of a single parameter, the position on the sheet is determined
by 2 parameters, <u,v>.

The blending functions are also generalizations into two parameters.  I think
(I'm doing this from memory, so don't take this as the final word) that they
can be given by doing the same seperation, according to powers of both u and
v, of the expansion of ( u * v * (1-u) * (1-v) ) ^3

Note that for a bicubic patch, the control points are not numbered 
sequentially, but in a grid, and the blending functions are likewise seperated
on two axis.  So:
	bf0,0 = (1-u)^3 * (1-v)^3
	bf1,0 = 3 * u * (1-u)^2 * (1-v)^3
	bf2,0 = 3 * u^2 * (1-u) * (1-v)^3
	bf3,0 = u^3 * (1-v)^3

	bf0,1 = (1-u)^3 * v * (1-v)^2
	bf1,1 = 3 * u * (1-u)^2 * v * (1-v)^2
	bf2,1 = 3 * u^2 * (1-u) * v * (1-v)^2
	bf3,1 = u^3 * v * (1-v)^2

	And so on.

The final point is then given by:
	
	R = sum(i from 0 to 3) {
		sum (j from 0 to 3) {
			point i,j * blending function i,j
		}
	    }

Uniform, non-rational b-splines are again generated as a function of control
points an blending functions.  However, the functions used are more complicated
than the simple polynomial expansion the Bezier/bi-cubics use.  These blending
functions are products of something called the knot vector.

The knot vector is a list of numbers (I think they might have to be integers,
but I'm not sure about that) in non-decreasing order.  The generation of the
blending functions from the knot vectors is some ugly algebra.  There are
relationships between the number of knots (the elements of the knot vector),
the degree of the B-spline, and the number of control points, but I'm not
sure exactly what they are.  For our purposes, the only thing that matters is
that the word 'uniform' implies that the spacing between knots is uniform.

There will be one knot vector for each dimension of the surface.  So a curve
has a single knot vector, while a surface patch has two.

The non-rational part of the word means that each control point has the
same weight (i.e. all have weight 1)

And now, finially, NURBS.  Non-uniform, rational, B-splines.  A further 
generalization of B-splines.  The 'non-uniform' adjective means that the
elements in the knot vector(s) do not have to be evenly spaced (although
they are still non-decreasing).  Repeating elements allows for sharp corners
and discontinuities.

Rational means that each control point has a weight associated with it.  I'm
not sure how the weights interact with the points and blending functions, 
but I believe that it's something like:

	R = sum(i from 0 to 3) {
		sum (j from 0 to 3) {
			weight i,j * point i,j * blending function i,j
		}
	    } / sum{all weights}

Ok, and that's enough math for one afternoon.

Jamie

Post a reply to this message