Finding the bounding box (axially aligned) of a parametric range of a 3D NURBS surface

I'll apologize in advance in case this is obvious; I've been unable to find the right terms to put into Google.

What I want to do is to find a bounding volume (AABB is good enough) for an arbitrary parametric range over a trimmed NURBS surface. For instance, (u,v) between (0.1,0.2) and (0.4,0.6).

EDIT: If it helps, it would be fine for me if the metho开发者_运维技巧d confined the parametric region entirely within a bounding region as defined in the paragraph below. I am interested in sub-dividing those regions.

I got started thinking about this after reading this paragraph from this paper ( http://www.cs.utah.edu/~shirley/papers/raynurbs.pdf ), which explains how to create a tree of bounding volumes with a depth relative to the degree of the surface:

The convex hull property of B-spline surfaces guarantees that the surface is contained in the convex hull of its control mesh.
As a result, any convex objects which bound the mesh will bound the underlying surface. We can actually make a stronger
claim; because we closed the knot intervals in the last section [made the multiplicity of the internal knots k − 1], each nonempty
interval [ui; ui+1)  [vj; vj+1) corresponds to a surface patch which is completely contained in the convex hull of
its corresponding mesh points. Thus, if we produce bounding volumes for each of these intervals, we will have completely
enclosed the surface. We form the tree by sorting the volumes according tothe axis direction which has greatest extent across the bounding volumes, splitting the data in half, and repeating the process.

Thanks! Sean

You will need to slice out a smaller NURBS surface, which only covers the parameter range you are interested in. Using your example, which I take to mean you are in the region where the u parameter is between 0.1 and 0.4. Let Pu be the degree of the spline in that parameter (A cubic spline has Pu = 3). You need to perform "knot insertion" (There's your Google search term) to get knots of degree Pu located at u=0.1 and u=0.4 Do the same thing on the v parameter to get knots of degree Pv at 0.2 and 0.6. The process of knot insertion will modify (and add to) the array of control points. There's a bit of bookkeeping involved, but you can then find the control_points that determine the surface in the parameter patch you just isolated between inserted knots. The convex property then says the surface is bounded by these control points, so you can use them to determine your bounding volume.

The NURBS reference I like to use for operations like this is: "The NURBS Book", by Les Piegl and Wayne Tiller.