Re: [Algorithms] (no subject)

[David H. <da...@hu...>]

So long as the grid is regular this should be pretty easy - for =
non-uniform grids you either need to somehow make the grid uniform again =
or use something else. Uniform in this sense doesn't mean the vertices =
are distributed evenly in space merely that they are connected together =
in the form of a grid.

Given a subsection of the surface defined by a 4x4 block of vertices
[p00,p01,p02,p03]
[p10,p11,p12,p13]
[p20,p21,p22,p23]
[p30,p31,p32,p33]
to interpolate a new point on the surface in the centre square
[p11,p12]
[p21,p22]
at u,v where u and v vary between 0 and 1 and (0,0) is at p11 and (1,1) =
is at p22.

Q(u,v)=3D    [B0(u),B1(u),B2(u),B3(u)][p00,p01,p02,p03][B0(v)]
                                    [p10,p11,p12,p13][B1(v)]
                                    [p20,p21,p22,p23][B2(v)]
                                    [p30,p31,p32,p33][B3(v)]
Where=20
B0(x)=3D(1-x)^3/6      =20
B1(x)=3D(3*x^3-6*x^2+4)/6  =20
B2(x)=3D(-3*x^3+3*x^2+3*x+1)/6
b3(x)=3Dx^3/6        =20

The B?(x) functions are called the basis functions and as x is confined =
to [0..1] can be precalculated to some resolution eg. 1/100ths and =
stored in a table.=20
So for a trivial example u,v=3D(0,0)
B0(u)=3D1/6 B0(v)=3D1/6
B1(u)=3D4/6 B1(v)=3D4/6
B2(u)=3D1/6 B2(v)=3D1/6
B3(u)=3D0   B3(v)=3D0
Q(u,v)=3D[1/6,4/6,1/6,0][p00,p01,p02,p03][1/6]
                      [p10,p11,p12,p13][4/6]
                      [p20,p21,p22,p23][1/6]
                      [p30,p31,p32,p33][0]

Thats a BSpline. Something to bear in mind is that this derivation of =
the basis functions can only be used to interpolate over the period =
between the 2nd and 3rd vertices in either direction. So to interpolate =
over
p22,p23
p32,p33
for instance requires we make a new point matrix with p11 at the top =
left. One side effect of this is that we loose one row/column of patch =
squares off each edge of the full grid - this is countered by either 1/ =
Enlarging the full grid by 1 invisible vertex in each +/- direction =
which is commonly done by graphics packages. 2/ Wrapping the edges to =
form a cylinder/sphere 3/ Deriving a new set of basis functions defined =
over the periods between the 1st to 2nd and 3rd to 4th sections.

BSplines behave quite nicely but are very unlikely to actually pass =
through the vertices defining them. Catmull Rom (untensioned Cardinals) =
actually pass through all control vertices and behave well until you =
really start to fold the surfaces back on themselves when they start to =
bulge.
For Catmull Rom swap the basis functions above with
B0(x)=3D(-x^3+2x^2-x)/2
B1(x)=3D(3x^3-5x^2+2)/2
B2(x)=3D(-3x^3+4x^2+x)/2
B3(x)=3D(x^3-x^2)/2


Don't know if this helps.


David Hunt=20

----- Original Message -----=20
From: kristian <fir...@ya...>
To: <gda...@li...>
Sent: Wednesday, October 18, 2000 8:03 PM
Subject: [Algorithms] (no subject)


> I want to fit a bspline sort of surface (i'm not
> picky, could be something else) to a grid of
> heightfield type data points.  I'm starting with
> evenly spaced points, but don't want to restrict it to
> that.  I want to get out something to fit triangles
> to, and that I can do modest collision checking with
> (nearest point on surface, above below surface).=20
> Isthis asking a lot?
>=20
> Anyone who can point me towards the math I need to do
> this? Web (i.e., free) resources are most appreciated.
>=20
> regards,
> kristian olivero
>=20
>=20
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Messenger - Talk while you surf!  It's FREE.
> http://im.yahoo.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list