Problem description
I have a cardinal curve, ie defined by the following basis functions :
$h1(s) = 2 * s^3 - 3 * s^2 + 1$
$h2(s) = -2 * s^3 + 3 * s^2$
$h3(s) = s^3 - 2 * s^2 + s$
$h4(s) = s^3 - s^2$
So, to compute the curve I use the following interpolation method :
$T1 = tension * (p[2] - p[0]);$
$T2 = tension * (p[3] - p[1]);$
and
$F(s) = h1(s) * p[1] + h2(s) * p[2] + h3(s) * T1 + h4(s) * T2$
where p[...] aree the control points.
So, now I want to compute the bounding box, for this I try to compute where the curve change its direction, ie. where the derivatives = 0. It is a simple extrama (minima,maxima) computation.
So, I derivates and got the following formula to solve :
$(6x^2-6x)a+(6x-6x^2)b+(3x^2-4x+1)c+(3x^2-2x)d=0$
and find the following solutions :
Solution 1
$s=-{{\sqrt{d^2+\left(c-6\,b+6\,a\right)\,d+c^2+\left(6\,a-6 \,b\right)\,c+9\,b^2-18\,a\,b+9\,a^2}-d-2\,c+3\,b-3\,a}\over{3\,d+3 \,c-6\,b+6\,a}}$
when $3*d+3*c-6*b+6*a <> 0$
Solution 2
$s={{\sqrt{d^2+\left(c-6\,b+6\,a\right)\,d+c^2+ \left(6\,a-6\,b\right)\,c+9\,b^2-18\,a\,b+9\,a^2}+d+2\,c-3\,b+3\,a }\over{3\,d+3\,c-6\,b+6\,a}}$
when $3*d+3*c-6*b+6*a <> 0$
Solution 3
$s=c/(c-d)$
when $a=0.5(2b-c-d)$ and $
The problem is that most of the time it works, but in some cases it does not returns the right values !
So, does someone has an idea (or another solution) ? I'm looking for a fast method (few operations) to compute the bounding box, because it is for a computer program (and have millions of calculations to do)!
BTW, I have write a small program in "processing" to test it... if you want is, just ask.
Thanks
Krys
The fastest way to compute a bounding box is to just box the original four Bezier control points, $p[0]$, $p[1]$, $p[2]$, $p[3]$. This works by virtue of the convex hull property of Bezier curves. This approach doesn't give a very "tight" box, but it's often good enough.
Your approach will give a tighter box, but will also be much slower.
Your reasoning is partially correct. You seem to be finding the parameter values of points where either the $x$-component or the $y$-component of the derivative vector is zero. In other words, places where the tangent vector is either horizontal or vertical. This is the right thing to do, but you need to reject any solutions that do not lie in the interval $[0,1]$, since these correspond to extreme points that lie outside the curve segment you're dealing with.
The other thing you need to do is check the end-points of the curve, $p[0]$ and $p[3]$. These could be "extreme" points of the curve, even though the tangents there are not horizontal or vertical.