gdalgorithms-list

[Algorithms] Heightfield to NURBS conversion

[Christian R. M. K. <chr...@pu...>]

After lurking around for some months due to 'transient mesage'
replies, which I don't seem to get anymore, probably because
the list moved to sourceforge, I'd like to introduce myself:

I am Christian Körber, German, study Computer Science in
Hamburg and specialize in computer graphics and geometric
modeling. 

I have a question too:

Could anyone of you point me to an algorithm on heightfield
to NURBS conversion i.e an algorithm which takes as input
an heightfield and returns the control points of the NURBS-
surface which APPROXIMATES the heightfield to a user given
error?
I'd really like to avoid meddling with the later chapters 
of Piegl & Tillers NURBS book! Maybe you even know a pro-
gram?

Christian

Re: [Algorithms] Heightfield to NURBS conversion

[Christian R. M. K. <chr...@pu...>]

"Christian R. M. Koerber" wrote:

> 
> I have a question too:
> 
> Could anyone of you point me to an algorithm on heightfield

actually I meant 'easy, ready to use algorithm'


> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?
> I'd really like to avoid meddling with the later chapters
> of Piegl & Tillers NURBS book! Maybe you even know a pro-
> gram?

Re: [Algorithms] Heightfield to NURBS conversion

[Dave E. <eb...@ma...>]

From: "Christian R. M. Koerber" <chr...@pu...>
> Could anyone of you point me to an algorithm on heightfield
> to NURBS conversion i.e an algorithm which takes as input
> an heightfield and returns the control points of the NURBS-
> surface which APPROXIMATES the heightfield to a user given
> error?

From: "Martin Fuller" <mf...@ac...>
> What you're asking for is a easy solution to what is a very
> very complex problem.  I would suggest instead of using
> NURBS looking at a curve equation that actually
> interpolates the control points. (but break the convex hull)
> Catmull Rom splines immediatly spring to mind.

From: "Christian R. M. Koerber" <chr...@pu...>
> Unfortunately it MUST be NURBS. The project I participate in uses them
> and there is no way around that. And it MUST be approximating since I need
> fewer control points than there are samples in the heightfield.

Well, you can always set up the NURBS as (X(s,t),Y(s,t),Z(s,t),1),
a Bezier surface :)

As folks have pointed out, this is a difficult problem if all the
user gets to specify the error.  I suggest a modification that
fits the N_h x M_h height field with N_b x M_b Bezier
surface patches of low degree (say bicubic patches).  The
control points are set up with (x,y) values as a regular lattice
in the plane.  Assuming some continuous representation of
the height field H(s,t), (linear or bilinear would be easiest),
and letting B(s,t) be the Bezier patch (with to-be-determined
control points) that corresponds to part of the height field,
set up a system of linear equations whose unknown are the
control points by minimizing E(control_points) =
Integral |B(s,t)-H(s,t)|^2 ds dt.

For example, you could try to fit the entire N_h x M_h height
field with a single Bezier bicubic patch and get a 3x3 system
of equations for the control points.  While it might be possible
to calculate in closed form the entries of the coefficient matrix,
it is not necessary.  You can compute these numerically.  Of
course a single patch probably is not accurate enough
(actually compare the E(...) value to your specified tolerance).
If not, "subdivide" in a sense and try a 2x2 set of patches
Minimize four integrals, add up the errors.  If still not within
tolerance, subdivide again and try a 4x4 set of patches, etc.

This least-squares method applies equally well, to NURBS.
The entries of the coefficient matrix become integrals of
rational functions.  Not a problem for numerical integrators.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

RE: [Algorithms] Heightfield to NURBS conversion

[Brian M. <bma...@ra...>]

This might not help a lot but here are couple of references.

Try:
	Pages 101-106 in Advanced Animation and Rendering Techniques - by Alan Watt
/ Mark Watt.

and	Piecewise Smooth Surface Reconstruction - Hughes Hoppe, Tony DeRose, Tom
Duchamp, Mark Halstead
(A Siggraph paper - its available on Hughes Hoppe's sight at Microsoft
research.)

	The first reference goes a little into building a b-spline patch by fitting
individual curves - hard to get the error control it sounds like you need,
but relatively easy to implement.
	The paper details arbitrary surface fitting for b-splines. Thankfully a
regular height field has a nice regular structure so you don't have to worry
about the tricky continuity fitting that arises in general patch networks.
This paper includes subdivision techniques to guarantee the error of the
patch approximation.

	One other thing to think about is fitting bezier patches to small blocks of
the heightfield (something like 4x4 blocks). Then do the standard trick of
using multiple knots to represent the bezier patches inside one b-spline
patch for the terrain. Then you remove the surplus multiple knots. Messy,
but something that's easier to get going with the kind of patch toolkit
people normally have lying around.

	Unfortunately patch fitting is tricky. :-)

-Brian.

Re: [Algorithms] Heightfield to NURBS conversion

[Tom H. <to...@3d...>]

At 01:47 AM 9/6/2000, you wrote:
>Could anyone of you point me to an algorithm on heightfield
>to NURBS conversion i.e an algorithm which takes as input
>an heightfield and returns the control points of the NURBS-
>surface which APPROXIMATES the heightfield to a user given
>error?
>I'd really like to avoid meddling with the later chapters
>of Piegl & Tillers NURBS book! Maybe you even know a pro-
>gram?

What I've seen done is to select a direction (vertical in my example, but 
could use horizontal) in the height filed data and curve fit a spline 
through each row of points (making sure that the curve passes through the 
points .. example of this in Watt and Watt I think).  Next, loft a surface 
between the resulting splines. This makes a very complex NURB with a ton of 
knots, but it works.

Another possibility is to make a series of cubic Bezier patches through the 
height field (four height samples make the four corners of the bezier) and 
preserve continuity between patches (There was a Game Developer article by 
Brian Sharp on this). I believe you can take all of these Bezier's and 
stitch them together into a single NURBS patch, but I've never done it. I 
know you can go the other way (single NURBS patch to multiple Bezier 
patches) so it makes sense that you could do it.

In neither of these situations do you have a "user error". The height field 
will pass through all of the samples and give you a continuous function for 
your height field with interpolation between the samples. The second method 
seems to be the cleanest to me. In both solutions you're going to have a 
ton of knots to deal with, and that will probably slow down your final 
rendering.

One possible way to reduce the number of knots would be to remove height 
samples within an error threshold before doing method #1. This would reduce 
the number of knots for each curve, but would remove the uniform sampling 
and make the lofting between the curves a bit more complex because each 
curve would have a different number of knots.

I don't have a MakeNURBSfromHeightField() function I can give you, but 
hopefully with the above or with some of the other responses you can 
construct what you need.

Tom

[Algorithms] transforming a plane

[Charles B. <cb...@cb...>]

Is there a fast way to transform a plane?

Right now I'm doing it by rotating the normal and tranforming
a point on the plane, then re-generating the 4d-vector form of
the plane.  It seems there should be a way to do it with a
single 4x4 matrix multiply in some funny coordinate space.

On a related note, is there a fast way to transform an
axis-aligned bounding box?  With an AABB defined by a 'min'
and a 'max', I'm doing this :

	// the min transformed :
	VECTOR3D vMinT;

	frXForm.XFormVector(vMinT,min);

	// the three edges transformed :
	VECTOR3D vx,vy,vz;

	vx = (max.x - min.x) * frXForm.Axis(X_AXIS);
	vy = (max.y - min.y) * frXForm.Axis(Y_AXIS);
	vz = (max.z - min.z) * frXForm.Axis(Z_AXIS);

	min.x = vMinT.x + min(vx.x,0) + min(vy.x,0) + min(vz.x,0);
	min.y = vMinT.y + min(vx.y,0) + min(vy.y,0) + min(vz.y,0);
	min.z = vMinT.z + min(vx.z,0) + min(vy.z,0) + min(vz.z,0);
	max.x = vMinT.x + max(vx.x,0) + max(vy.x,0) + max(vz.x,0);
	max.y = vMinT.y + max(vx.y,0) + max(vy.y,0) + max(vz.y,0);
	max.z = vMinT.z + max(vx.z,0) + max(vy.z,0) + max(vz.z,0);

Basically, transform the low corner (the 'min'), and then
transform the edges along x,y, and z.  I can't think of anything
better.




--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] transforming a plane

[Eric L. <le...@c4...>]

> Is there a fast way to transform a plane?
> 
> Right now I'm doing it by rotating the normal and tranforming
> a point on the plane, then re-generating the 4d-vector form of
> the plane.  It seems there should be a way to do it with a
> single 4x4 matrix multiply in some funny coordinate space.

Yes, planes can be transformed with a single 4x4 matrix multiply.  Planes
transform contravariantly like normal vectors do, meaning that you need to
transform it using the inverse transpose of the matrix that you would
transform normal points with.

Suppose you have a 4D column vector V representing a plane and a 4x4
transformation matrix M.  Let V = <Nx, Ny, Nz, -d> where N is the plane's
normal vector and d = (P dot N) for any point P on the plane.  Then the
transformed plane V' is given by

   V' = Transpose(Inverse(M)) * V

-- Eric Lengyel

Re: [Algorithms] transforming a plane

[Charles B. <cb...@cb...>]

Silly me, that comes out of the math trivially.  Assuming an
orthonormal matrix, so Transpose(Inverse(M)) = M, then a point
on the plane initially is 

P = d N

Transformed, you get

P' = MP = M d N = d N' + T

where T is the translation in M.  Then d' is just

d' = N' * P' = d N' * N' + T * N' = d + T * N'

In other words, d += T * N' is all you need to transform a plane
(and rotate the normal) by an orthonormal matrix.

At 11:18 PM 9/6/2000 -0700, you wrote:
>> Is there a fast way to transform a plane?
>> 
>> Right now I'm doing it by rotating the normal and tranforming
>> a point on the plane, then re-generating the 4d-vector form of
>> the plane.  It seems there should be a way to do it with a
>> single 4x4 matrix multiply in some funny coordinate space.
>
>Yes, planes can be transformed with a single 4x4 matrix multiply.  Planes
>transform contravariantly like normal vectors do, meaning that you need to
>transform it using the inverse transpose of the matrix that you would
>transform normal points with.
>
>Suppose you have a 4D column vector V representing a plane and a 4x4
>transformation matrix M.  Let V = <Nx, Ny, Nz, -d> where N is the plane's
>normal vector and d = (P dot N) for any point P on the plane.  Then the
>transformed plane V' is given by
>
>   V' = Transpose(Inverse(M)) * V
>
>-- Eric Lengyel
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

RE: [Algorithms] transforming a plane

[Brian M. <bma...@ra...>]

If you are wanting the AABB that encloses the original after transformation
try:

Arvo, James, Transforming Axis-Aligned Bounding Boxes, p. 548-550
http://www.acm.org/tog/GraphicsGems/gems.html

It works by figuring out which of the corners of the bounding box produces
the largest extent along each axis for the new coordinate space.
I'm not sure if this is what you want - but exploiting the extent properties
of a AABB is normally a good way to get fast code with them so hopefully the
concept may help if nothing else.

-Brian.

Re: [Algorithms] transforming a plane

[Pierre T. <p.t...@wa...>]

Charles,

I think it's best using the Center + Extents way for an AABB. Here's what I
use, for what it's worth. Obviously it does not gives you the minimal AABB
possible after the transformation, but it usually is well enough to handle
most situations correctly.

If some of you know a faster way, I'm deeply interested - I use that one
pretty often.

Pierre

////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////
/**
 * A method to recompute the min & max point of an AABB after an arbitrary
transform by a 4x4 matrix.
 * \param  mtx   the transform matrix
 * \param  aabb  the transformed AABB
 * \return  Self-reference
 */
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////
AABB& AABB::Rotate(Matrix4x4& mtx, AABB& aabb)
{
 // Compute new extents
 Point Ex = mtx.GetRow(0) * mExtents.x;
 Point Ey = mtx.GetRow(1) * mExtents.y;
 Point Ez = mtx.GetRow(2) * mExtents.z;

 aabb.mExtents.x = FastFabs(Ex.x) + FastFabs(Ey.x) + FastFabs(Ez.x);
 aabb.mExtents.y = FastFabs(Ex.y) + FastFabs(Ey.y) + FastFabs(Ez.y);
 aabb.mExtents.z = FastFabs(Ex.z) + FastFabs(Ey.z) + FastFabs(Ez.z);

 // Compute new center
 aabb.mCenter = mCenter * mtx;

 return *this;
}

----- Original Message -----
From: Charles Bloom <cb...@cb...>
To: <gda...@li...>
Sent: Wednesday, September 06, 2000 9:19 PM
Subject: [Algorithms] transforming a plane


>
> Is there a fast way to transform a plane?
>
> Right now I'm doing it by rotating the normal and tranforming
> a point on the plane, then re-generating the 4d-vector form of
> the plane.  It seems there should be a way to do it with a
> single 4x4 matrix multiply in some funny coordinate space.
>
> On a related note, is there a fast way to transform an
> axis-aligned bounding box?  With an AABB defined by a 'min'
> and a 'max', I'm doing this :
>
> // the min transformed :
> VECTOR3D vMinT;
>
> frXForm.XFormVector(vMinT,min);
>
> // the three edges transformed :
> VECTOR3D vx,vy,vz;
>
> vx = (max.x - min.x) * frXForm.Axis(X_AXIS);
> vy = (max.y - min.y) * frXForm.Axis(Y_AXIS);
> vz = (max.z - min.z) * frXForm.Axis(Z_AXIS);
>
> min.x = vMinT.x + min(vx.x,0) + min(vy.x,0) + min(vz.x,0);
> min.y = vMinT.y + min(vx.y,0) + min(vy.y,0) + min(vz.y,0);
> min.z = vMinT.z + min(vx.z,0) + min(vy.z,0) + min(vz.z,0);
> max.x = vMinT.x + max(vx.x,0) + max(vy.x,0) + max(vz.x,0);
> max.y = vMinT.y + max(vx.y,0) + max(vy.y,0) + max(vz.y,0);
> max.z = vMinT.z + max(vx.z,0) + max(vy.z,0) + max(vz.z,0);
>
> Basically, transform the low corner (the 'min'), and then
> transform the edges along x,y, and z.  I can't think of anything
> better.
>
>
>
>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list