Jump to content
  • Advertisement
Sign in to follow this  
kossu

Bounding box of a NURBS curve

This topic is 4714 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does anyone know if there is a method or algorithm to compute a box that just encloses a NURBS curve. That is, how to minimize the bounding box. A bounding box including all the control points of the curve is too large for my use.

Share this post


Link to post
Share on other sites
Advertisement
You could always try an approximate solution. Sample the curve to generate a set of points. Compute the minimum-area bounding rectangle using the method of rotating calipers.

Share this post


Link to post
Share on other sites
Thank you very much for your help. However,I have searched through many web sites and articles to find applicable material. Could you possibly recommend me some helpful links.

Share this post


Link to post
Share on other sites
The home page for rotating calipers. I have an implementation at my Geometric Tools site, the containment page. For an arbitrary set of points, you need to compute the convex hull first (my code does this). The minimum-area bounding rectangle must have an edge coincident with one of the edges of the hull.

Share this post


Link to post
Share on other sites
If I sample the curve to have a set of points, it seems to be very difficult to include the whole curve in the box without leaving no arc of it outside.
One convex hull for a curve can be computed using its control points, but that usually produces much too large a bounding box. Any idea?

Share this post


Link to post
Share on other sites
Quoting myself "You could always try an approximate solution". I am aware that a bounding box of the samples is not guaranteed to contain the curve, but for a suitable number of samples, the box is *close* to a bound. I thought I would suggest this in case an approximation will suffice for your application.

Given the approximate box, you have a center point C and two unit-length and orthogonal axes, U and V. These define a coordinate system. If the NURBS curve is P(t), it may be written in the coordinate system as P(t) = C + x(t)*U + y(t)*V, where x(t) = Dot(U,P(t)-C) and y(t) = Dot(V,P(t)-C).

Compute the extreme values of x(t) and y(t), say xmin <= x(t) <= xmax and ymin <= y(t) <= ymax. A bounding box is the set of points C+x*U+y*V, where xmin <= x <= xmax and ymin <= y <= ymax. This box has the same axis directions as the old, but the center point is K = C + 0.5*(xmin+xmax)*U + 0.5*(ymin+ymax)*V.

Computing the extreme values requires some calculus. For x(t) with 0 <= t <= 1, the extreme values occur where the derivative x'(t) = 0, or at x(0) or x(1). The derivative is also a rational polynomial, but you can multiply through by the denominator in x'(t) = 0 to obtain a polynomial equation in t. Numerically compute the roots. If t1 through tm are the roots, then xmax is the largest of x(0), x(t1), ..., x(tm), x(1).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!