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