Curve bounding box - fast computation back

(L) [2014/02/26] [tby spectral] [Curve bounding box - fast computation] Wayback!

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 : [LINK http://math.stackexchange.com/questions/691018/cardinal-curve-computing-the-bounding-boxe]
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

(L) [2014/02/26] [tby darkhorse64] [Curve bounding box - fast computation] Wayback!

If you change the basis of your curve from Catmull-Rom 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.

(L) [2014/02/26] [tby spectral] [Curve bounding box - fast computation] Wayback!

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 ?

(L) [2014/02/26] [tby darkhorse64] [Curve bounding box - fast computation] Wayback!

Quite simply
Code: [LINK # 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 catmull-rom space
For each component (x, y, z) of your control points, do
Code: [LINK # Select all]Vector4 oldControlPoints// = {x0, x1, x2, x3};
Vector4 newControlPoints = fromCatmullRom * oldControlPoints; // matrix - vector multiply

For detailed explanations, look at [LINK http://therndguy.com/papers/curves.pdf]

(L) [2014/02/26] [tby spectral] [Curve bounding box - fast computation] Wayback!

I have try using the following formulas : [LINK http://www.ibiblio.org/e-notes/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

(L) [2014/02/26] [tby spectral] [Curve bounding box - fast computation] Wayback!

But the convex hull property is really interesting on the other side [SMILEY :-D]
Thanks

(L) [2014/02/26] [tby friedlinguini] [Curve bounding box - fast computation] Wayback!

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.

(L) [2014/03/04] [tby darkhorse64] [Curve bounding box - fast computation] Wayback!

I tried this optimization in my renderer. On a scene with thousands of curves, it decreased the rendering times by 10%. Thanks !!