Curve bounding box - fast computation

Practical and theoretical implementation discussion.
Post Reply
spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

Curve bounding box - fast computation

Post by spectral » Wed Feb 26, 2014 2:11 pm

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 ... nding-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
Attachments
curves_multi_cardinals.zip
(1.88 KiB) Downloaded 205 times
Spectral
OMPF 2 global moderator

darkhorse64
Posts: 7
Joined: Wed Jan 25, 2012 10:20 am

Re: Curve bounding box - fast computation

Post by darkhorse64 » Wed Feb 26, 2014 4:13 pm

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.

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

Re: Curve bounding box - fast computation

Post by spectral » Wed Feb 26, 2014 4:19 pm

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 ?
Spectral
OMPF 2 global moderator

darkhorse64
Posts: 7
Joined: Wed Jan 25, 2012 10:20 am

Re: Curve bounding box - fast computation

Post by darkhorse64 » Wed Feb 26, 2014 4:47 pm

Quite simply

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 catmull-rom space
For each component (x, y, z) of your control points, do

Code: Select all

Vector4 oldControlPoints// = {x0, x1, x2, x3};
Vector4 newControlPoints = fromCatmullRom * oldControlPoints; // matrix - vector multiply
For detailed explanations, look at http://therndguy.com/papers/curves.pdf

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

Re: Curve bounding box - fast computation

Post by spectral » Wed Feb 26, 2014 4:49 pm

I have try using the following formulas : 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
Spectral
OMPF 2 global moderator

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

Re: Curve bounding box - fast computation

Post by spectral » Wed Feb 26, 2014 5:03 pm

But the convex hull property is really interesting on the other side :-D

Thanks
Spectral
OMPF 2 global moderator

friedlinguini
Posts: 89
Joined: Thu Apr 11, 2013 5:15 pm

Re: Curve bounding box - fast computation

Post by friedlinguini » Wed Feb 26, 2014 6:41 pm

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.

darkhorse64
Posts: 7
Joined: Wed Jan 25, 2012 10:20 am

Re: Curve bounding box - fast computation

Post by darkhorse64 » Tue Mar 04, 2014 10:16 pm

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

Post Reply