![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
I am attempting to comprehend NURBS.
NURBS are of course Non-Uniform Rational B-Splines.
using de Casteljau's algorithm:
Plot(T, P[])
If P[] contains just one point, return it. Otherwise...
Construct Q[] by linearly interpolating between each adjacent pair
of points in P[], at parameter=T.
Recursively call Plot(T, Q[]).
Since Q[] is exactly one element smaller than P[], eventually the
recursion terminates. (And in practice, the initial set of constrol
points is something like 3 or so.)
control points to generate a new, smaller set of control points. Repeat
until you have a single point left.
except that each control point has a "weight". What the algorithm
appears to do is draw the spline in 3D and then perspective-project it
back into 2D. The control points are positioned so that their apparent
2D position is unaltered, but the Z coordinate is the weight. Changing
the weight doesn't alter the apparent position of the control point, but
does alter the way the rest of the curve projects back into 2D. (In
particular, a negative weight puts the control point behind the camera.)
has a "knot vector" which controls how much of the curve is influenced
by a specific control point. A B-spline can be "uniform" (all knots
equally spaced) or "non-uniform" (knot spacing is unequal).
This much I understand. What I don't yet understand is the fine detail
of how B-splines actually work.
A NURBS is simply a B-spline which is (potentially) non-uniform (i.e.,
the knots are adjustable) and rational (i.e., it uses this strange 3D
projection trick). So if I could just understand B-splines, I would be
able to comprehend NURBS.
The degree of a B-spline, the number of control points and the number of
knots are all related in some way which I don't quite understand. The
degree and the knots generate the basis functions, and the curve itself
is just a linear combination of the basis functions multiplied by the
control points. So if I could just figure this last part out...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> using de Casteljau's algorithm:
>
> Plot(T, P[])
> If P[] contains just one point, return it. Otherwise...
> Construct Q[] by linearly interpolating between each adjacent pair
> of points in P[], at parameter=T.
> Recursively call Plot(T, Q[]).
In Haskell:
spline t ps =
case ps of
[] -> error "zero control points"
p:[] -> p
_ -> spline t $ zipWith (\a b -> (a *| (1-t)) + (b *| t)) ps
(tail ps)
It's delightfully simple stuff like this that makes me love Haskell.
> except that each control point has a "weight". What the algorithm
> appears to do is draw the spline in 3D and then perspective-project it
> back into 2D.
This is presumably trivial in almost any language... but in Haskell:
rational_bezier t ps =
let Vector3 x y z = bezier_spline $ map (\(Vector2 x y, k) ->
Vector3 (k*x) (k*y) k) ps
in Vector2 (x/z) (y/z)
Again, beautifully simple (if rather wide to fit on one line...)
> has a "knot vector" which controls how much of the curve is influenced
> by a specific control point. A B-spline can be "uniform" (all knots
> equally spaced) or "non-uniform" (knot spacing is unequal).
>
> This much I understand. What I don't yet understand is the fine detail
> of how B-splines actually work.
>
> A NURBS is simply a B-spline which is (potentially) non-uniform (i.e.,
> the knots are adjustable) and rational (i.e., it uses this strange 3D
> projection trick). So if I could just understand B-splines, I would be
> able to comprehend NURBS.
Uh... yeah. o_O
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
....
> So if I could just understand B-splines, I would be able to comprehend NURBS.
....
Would it help if I show how B-splines and NURBS can be implemented with POV-Ray
SDL ?
--
Tor Olav
http://subcube.com
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 05.07.2010 23:36, schrieb Tor Olav Kristensen:
> Would it help if I show how B-splines and NURBS can be implemented with POV-Ray
> SDL ?
Hum... if they can be implemented in SDL, then it must be possible to
implement them in C++, too - right?
Tell us more.
BTW, do you happen to know a free and easy-to-grok NURBS modeller
capable of exporting the "raw" NURBS data?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> Am 05.07.2010 23:36, schrieb Tor Olav Kristensen:
>
> > Would it help if I show how B-splines and NURBS can be implemented with POV-Ray
> > SDL ?
>
> Hum... if they can be implemented in SDL, then it must be possible to
> implement them in C++, too - right?
Hehe - Maybe ;)
> Tell us more.
I just posted this:
http://news.povray.org/povray.binaries.scene-files/thread/%3Cweb.4c327e199f459e99c734aecd0%40news.povray.org%3E/
From: Tor Olav Kristensen
Subject: NURBS macros etc.
Date: 6 Jul 2010 00:55:00
(I'm to tired right now to explain more, but if you have any questions, I'll try
to find time to answer them later.)
> BTW, do you happen to know a free and easy-to-grok NURBS modeller
> capable of exporting the "raw" NURBS data?
No, sorry.
--
Tor Olav
http://subcube.com
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Tor Olav Kristensen wrote:
> I just posted this:
>
>
http://news.povray.org/povray.binaries.scene-files/thread/%3Cweb.4c327e199f459e99c734aecd0%40news.povray.org%3E/
/*
// If you now limit the ranges that these variables defines,
// then only a part of the surface will be "meshyfied".
// (If you expand these ranges, you'll get an error.)
#declare MinUV = <0.2, 0.0>;
#declare MaxUV = <0.8, 0.9>;
// U will wary from 0.2 to 0.8
// V will wary from 0.0 to 0.9
*/
U will "wary"?
What are you, Elmer Fudd?
Sorry, that just amused me...
Anyway, I'm still wading through the NURBS code. Damn this looks
complicated!
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> Tor Olav Kristensen wrote:
>
> > I just posted this:
> >
> >
http://news.povray.org/povray.binaries.scene-files/thread/%3Cweb.4c327e199f459e99c734aecd0%40news.povray.org%3E/
>
> /*
> // If you now limit the ranges that these variables defines,
> // then only a part of the surface will be "meshyfied".
> // (If you expand these ranges, you'll get an error.)
> #declare MinUV = <0.2, 0.0>;
> #declare MaxUV = <0.8, 0.9>;
> // U will wary from 0.2 to 0.8
> // V will wary from 0.0 to 0.9
> */
>
> U will "wary"?
>
> What are you, Elmer Fudd?
>
> Sorry, that just amused me...
=)
> Anyway, I'm still wading through the NURBS code. Damn this looks
> complicated!
Yes, I too find NURBS a bit complicated. Just take small steps and try to code,
draw and experiment with every little new idea in books and web pages about
NURBS.
Btw.: I hope you are looking at the code in the attached file: NURBS_28_.inc and
not the code you quoted above.
I recommend that you go through these macros (in the listed order) within that
file:
UniformKnotVector(Open, Order, NrOfPoints)
Cox_deBoor(Order, Knots, K)
BlendFunction(Order, Knots, K)
BlendFunctions(Nr, Order, Knots)
NURBS_Function1A(OrderU, KnotsU, Values1A, Weights1A)
ExtractComponent1A(Vectors1A, v0)
ShowFunctions1A3D(xFn, yFn, zFn, WrapU, MinU, MaxU, ResU, Radius)
Show_URBS_1A3D(Points1A3D, Weights1A, OpenU, OrderU, WrapU, DivU, Radius)
NURBS_Function2A(OrderUV, KnotsU, KnotsV, Values2A, Weights2A)
ExtractComponent2A(Vectors2A, v0)
ShowFunctions2A3D(xFn, yFn, zFn, WrapUV, MinUV, MaxUV, DivUV, ResUV, Radius)
Show_URBS_2A3D(Points2A3D, Weights2A, OpenUV, OrderUV, WrapUV, DivUV, ResUV,
Radius)
--
Tor Olav
http://subcube.com
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> has a "knot vector" which controls how much of the curve is influenced
> by a specific control point. A B-spline can be "uniform" (all knots
> equally spaced) or "non-uniform" (knot spacing is unequal).
>
> This much I understand. What I don't yet understand is the fine detail
> of how B-splines actually work.
OK, so now I think I understand.
The knots control the mapping of the parameter space onto the spline
(which would be important if you were using the spline to animate
something), which also influences its shape. Essentially the value of a
given knot determines the parameter value at which a given control point
achieves its maximum "influence" over the spline.
Then there is a set of recursively-defined "basis functions". The spline
itself is made by just multiplying each control point by a basis
function and adding all the products together. So the number of basis
functions controls the number of control points.
The number of 0th-order basis functions is one less than the number of
knots. (E.g., if you have 10 knots, you have 9 of these functions.) The
Nth such function is zero, except that it becomes one when T is between
knots N and N+1.
Now, the recursive part: In the next order up, you have one fewer
functions. And each function is a linear interpolation between two lower
ones (scaled according to the knot values in a way that's slightly fiddly).
Have a look at the attachment. It's an Excel file that plots a simple 2D
(non-uniform) B-spline. It should be possible to alter anything on the
"control" sheet and have the various graphs update. (Don't try to put
any knots outside the range 0<=t<=1 though.)
Post a reply to this message
Attachments:
Download 'b-spline v4.zip' (98 KB)
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> Then there is a set of recursively-defined "basis functions". The spline
> itself is made by just multiplying each control point by a basis
> function and adding all the products together. So the number of basis
> functions controls the number of control points.
Alternatively, apparently there's a modification of de Casteljau's
algorithm that draws B-splines instead of Bezier splines. It's called de
Boor's algorithm.
Looking at it, it's hard to see what the difference is. (Wikipedia
helpfully uses a completely different notation for the two articles.) It
turns out that they both interpolate between the control points, but de
Casteljau's algorithm does so uniformly, while de Boor's algorithm
adjusts the parameterisation based on the knot vector.
Implementing this correctly is going to be amusing...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> Alternatively, apparently there's a modification of de Casteljau's
> algorithm that draws B-splines instead of Bezier splines. It's called de
> Boor's algorithm.
>
> Implementing this correctly is going to be amusing...
After several days of hurting my brain, finally I think I understand.
Post a reply to this message
Attachments:
Download 'b-spline03.pdf' (94 KB)
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |