Curve bounding box  fast computation
Curve bounding box  fast computation
Hi all,
I'm currently looking for an approach to compute the bounding box of a cardinal curve (I use cardinal because the curve pass through the control points), in 2D !
You can look here for more explanations about the problem, and all the math stuffs : http://math.stackexchange.com/questions ... ndingboxe
The problem is that I have write a "processing" program to draw the curve and the bounding box. But it does not gives the desired result... !
I attach the "processing" code if you are interested.
Any idea ?
Thx
I'm currently looking for an approach to compute the bounding box of a cardinal curve (I use cardinal because the curve pass through the control points), in 2D !
You can look here for more explanations about the problem, and all the math stuffs : http://math.stackexchange.com/questions ... ndingboxe
The problem is that I have write a "processing" program to draw the curve and the bounding box. But it does not gives the desired result... !
I attach the "processing" code if you are interested.
Any idea ?
Thx
 Attachments

 curves_multi_cardinals.zip
 (1.88 KiB) Downloaded 205 times
Spectral
OMPF 2 global moderator
OMPF 2 global moderator

 Posts: 7
 Joined: Wed Jan 25, 2012 10:20 am
Re: Curve bounding box  fast computation
If you change the basis of your curve from CatmullRom to Bezier, the curve is contained into the convex hull of the new control points (this is a property of Bezier curves; this is also true for Bezier surfaces). The bounding box you need is then simply built from the list of control points.
Re: Curve bounding box  fast computation
Thanks,
It looks promising.... so my question is now : how to convert my 4 control point of the cardinal curve to the 4 control points of the Bezier curve ? right ?
Have you any reference please ?
It looks promising.... so my question is now : how to convert my 4 control point of the cardinal curve to the 4 control points of the Bezier curve ? right ?
Have you any reference please ?
Spectral
OMPF 2 global moderator
OMPF 2 global moderator

 Posts: 7
 Joined: Wed Jan 25, 2012 10:20 am
Re: Curve bounding box  fast computation
Quite simply
For each component (x, y, z) of your control points, do
For detailed explanations, look at http://therndguy.com/papers/curves.pdf
Code: Select all
// The transformation matrix you need  Matrix4 is a 4x4 matrix
Matrix4 fromCatmullRom = Matrix4( 1, 3, 3, 1, 3, 6, 3, 0, 3, 3, 0, 0, 1, 0, 0, 0 ).inverse() // to bezier space
* Matrix4( 1, 3, 3, 1, 2, 5, 4, 1, 1, 0, 1, 0, 0, 2, 0, 0 ) / 2; // from catmullrom space
Code: Select all
Vector4 oldControlPoints// = {x0, x1, x2, x3};
Vector4 newControlPoints = fromCatmullRom * oldControlPoints; // matrix  vector multiply
Re: Curve bounding box  fast computation
I have try using the following formulas : http://www.ibiblio.org/enotes/Splines/Cardinal.htm
It seems to work, and so quick to compute... but the problem is that it is not really the minimum bounding box !
BTW, I will look at your paper right now... thanks
It seems to work, and so quick to compute... but the problem is that it is not really the minimum bounding box !
BTW, I will look at your paper right now... thanks
Spectral
OMPF 2 global moderator
OMPF 2 global moderator
Re: Curve bounding box  fast computation
But the convex hull property is really interesting on the other side
Thanks
Thanks
Spectral
OMPF 2 global moderator
OMPF 2 global moderator

 Posts: 89
 Joined: Thu Apr 11, 2013 5:15 pm
Re: Curve bounding box  fast computation
The bounding box isn't minimal, but you can get closer by cutting the Bezier curve in half via de Casteljau subdivision and then taking the bounding box of all of the resulting control points. You can get arbitrarily tight bounds by subdividing recursively. You don't need to subdivide curves if the "interior" control points lie inside the bounding box containing just the endpoints, so this converges pretty quickly.

 Posts: 7
 Joined: Wed Jan 25, 2012 10:20 am
Re: Curve bounding box  fast computation
I tried this optimization in my renderer. On a scene with thousands of curves, it decreased the rendering times by 10%. Thanks !!