RE: [Algorithms] Spline Surface Extremal Points ?

[Graham S. R. <gr...@se...>]

By "extremal" I assume you mean maxima and minima with respect to a given
(possibly axis-aligned) coordinate frame. These maxima and minima can define
the height of the optimum bounding box in the given frame. Are you wanting a
solution that runs in real-time (which may not always be possible)? Here's a
rambling discussion, just my thoughts on the matter, from my work in the
past on numerical optimization.

Obviously, the control points can provide good clues to finding the extremal
points, and may be used to find a good default result. A quick and dirty
(non-exact) method is to tesselate the surface, and then iterate through the
points. This is a very reliable method that can be quite fast for coarse
tesselations. Obviously, such brute force methods are not optimum if you
have tons and tons of polygons on a surface----way too slow.

To find the maxima and minima, you are looking for points where the dz/dx
and dz/dy (when looking for the extremes in the z direction) derivatives are
both zero. You also have to check the boundary points, since these points
may be lower or higher than the valleys and peaks of the "hills" of the
surface. Here, the x and y directions are two orthogonal directions in your
coordinate frame of interest. Lets say that uv space happens to be exactly
the xy plane - the easiest case. Your surface can then be written as three
equations:

x = u
y = v
z = f(x, y).

Along a line of constant u (or v), the problem is fairly easy. Just set x =
constant (or y = constant) and solve for y (or x) on the following
equations:

dz/dy = 0 (or dz/dx = 0, if v is constant)

Your solution will yield x (given), y (solved for), and z (computed by
function f) for the *local* maxima and minima along the line of constant x.
You may find multiple values of y and z (1 for 1st and 2nd order curves, up
to 2 for 3rd order curves, etc.). Given a collection of *local* maxima and
minima, you can just go and find the absolute min and max values of z to
determine which points are the true max and min. Again, remember to check
the boundary points as well. For surfaces that are 2nd order in x and y,
this is a problem that is solvable closed form.

The preceeding paragraph does not give the min and max for the entire
surface----only along a line of constant x (or y). To find the local minima
and maxima on an entire surface, you have to simultaneously solve dz/dy = 0
*and* dz/dx = 0 rather than just one of the two. If f(x,y) is linear in both
x and y, you'll have a nice set of linear equations. If f(x,y) is higher
order (e.g., quadratic, etc.) in x or y, then you'll have a nonlinear set of
equations, harder to solve. Look for special cases.

The problem gets worse for a general surface in space, where u and v do not
correspond to the xy plane. The surface may fold over so z is not a
single-valued function in you coordinate frame of interest when you look at
z = f(x,y). You are no longer solving for just the maxima and minima of z,
but also of x and y. Requires that you work in uv space in order to avoid
the possible multi-valued-ness of the surface.

For a general surface, this is an optimization problem that cannot be solved
in closed form. It requires a gradient-based numerical optimization method
such as sequential quadratic programming. For smooth (read continuous)
surfaces that do not have many local maxima and minima, these numerical
methods are fairly robust----and not too slow either---converging in just a
few iterations, but for weird bumpy surfaces they aren't robust and
heuristic methods for choosing a starting point that is near the true
minima/maxima are required. For low-order spline patches, without actually
working out the math, there may sometimes actually be a closed form
solution... Obviously, there are nice special cases where a closed form
solution is known.

I know this is sort of a rambling discussion. As a first cut, you can always
check the control points themselves. If it helps or doesn't help, let me
know. I have a reference or two floating around.

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Tim
> Thomas
> Sent: Friday, August 18, 2000 5:27 PM
> To: gda...@li...
> Subject: [Algorithms] Spline Surface Extremal Points ?
>
>
> Hi !
>
> How do i calculate the extremal points of a given ( tangents, 4 points )
> spline patch ?
>
> Any help welcome, even little hints or links
>
> Thanks in advance
>
> Tim
>
> --
> Sent through GMX FreeMail - http://www.gmx.net
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>