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