3
$\begingroup$

I need to compute a 2D "spherical" bounding volume for the part of a catmull-rom spline $S(t)$ with four control points $P1$, $P2$, $P3$ and $P4$ in the domain $0 \le t \le1$. The purpose is to reduce CPU-time when working with a large set of such splines, so I can not afford to compute the maximums/minimums of the fourth degree polynomial - instead the the bounding volume should be computed directly from the control points.

Do you guys have any suggestions?

Any ideas and thoughts are welcome, but I'll of course prefer a formal proof or argumentation for, that the bounding volume always will contain all of S(t) when $0\le t\le 1$ for any value of $P1$, $P2$, $P3$ and $P4$.

Below is two illustrations of a catmull-rom spline (red curve) and a possible bounding volume (blue disc).

Example1 Example2

For these two examples, we could the distance from P2 to P3. But will this work for any possible control points, and why?

Below is an illustration on the example presented by bubba: Counterexample to the initial approach

$\endgroup$

1 Answer 1

1
$\begingroup$

Let's relabel the four points in your diagram as $\mathbf{P}_1 = \mathbf{A}$, $\mathbf{P}_2 = \mathbf{B}$, $\mathbf{P}_3 = \mathbf{C}$, $\mathbf{P}_4 = \mathbf{D}$, to avoid fiddling with subscripts.

So, according to the Catmull-Rom construction, we are dealing with a cubic segment that starts at the point $\mathbf{B}$, with a start derivative of $\mathbf{U} = \tfrac12(\mathbf{C} - \mathbf{A})$, and ends at the point $\mathbf{C}$, with an ending derivative of $\mathbf{V} = \tfrac12(\mathbf{D} - \mathbf{B})$.

The key idea is to convert this segment to Bezier form, and then find a circle (or sphere) that encloses the Bezier control points.

The first and last Bezier control points of the curve segment are obviously $\mathbf{B}$, $\mathbf{C}$. By well-kown properties of Bezier curves, the inner control point $\mathbf{P}$ adjacent to $\mathbf{B}$ is given by $$ \mathbf{P} = \mathbf{B} + \tfrac13 \mathbf{U} = \mathbf{B} + \tfrac16 (\mathbf{C} - \mathbf{A}) $$ Similarly, the inner control point $\mathbf{Q}$ adjacent to $\mathbf{C}$ is given by $$ \mathbf{Q} = \mathbf{C} - \tfrac13 \mathbf{V} = \mathbf{C} - \tfrac16 (\mathbf{D} - \mathbf{B}) $$ We know that a Bezier curve is contained within the convex hull of its control points, so now all we have to do is find a sphere that encloses the four points $\mathbf{B}$, $\mathbf{P}$, $\mathbf{Q}$, $\mathbf{C}$.

The simplest way to do this is to check the 6 spheres whose diameters are $\mathbf{B}\mathbf{P}$, $\mathbf{B}\mathbf{Q}$, $\mathbf{B}\mathbf{C}$, $\mathbf{P}\mathbf{Q}$, $\mathbf{P}\mathbf{C}$, $\mathbf{Q}\mathbf{C}$. One of these will certainly work. I recommend checking the sphere with diameter $\mathbf{B}\mathbf{C}$ first, because it will probably work in a large percentage of cases, and you can then quit immediately, without checking the other 5 spheres.

So, how do you do the sphere checking quickly? As an example, let's check that the two other points, $\mathbf{P}$ and $\mathbf{Q}$ lie inside the sphere having $\mathbf{B}\mathbf{C}$ as diameter. It's not hard to show that the point $\mathbf{P}$ lies inside this sphere if and only if $(\mathbf{P} - \mathbf{B}) \cdot (\mathbf{C} - \mathbf{P}) \ge 0$. This is related to the fact that the angle in a semi-circle (or a hemisphere) is a right angle. So, you can do this point-inside-sphere test with just a single vector dot product.

In the last paragraph of your question, you asked if using the sphere with diameter $\mathbf{B}\mathbf{C}$ would always work. I haven't proved it, but I suspect that it will not. So, I'd recommend that you test all 6 spheres, as described above. If the sphere with diameter $\mathbf{B}\mathbf{C}$ always works, then the code that tests the other 5 spheres will never get executed, so there is only a small loss of efficiency.

Edit
The sphere with diameter $\mathbf{B}\mathbf{C}$ does not always work. As a counterexample, take $\mathbf{A} = (0,0)$, $\mathbf{B} = (4,3)$, $\mathbf{C} = (3,3)$, $\mathbf{D} = (7,0)$.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks, for the answer and the counterexample. I don't know much about bezier curves - can a catmull-rom spline always be expressed on bezier form? Further I'm curious on how you get the constant \frac{1}{6}. $\endgroup$
    – Morten
    Commented Sep 2, 2014 at 8:23
  • $\begingroup$ Every segment of a Catmull-Rom spline is just a parametric cubic, so it can certainly be expressed in Bezier form. From a mathematical point of view this is just a change of basis in the vector space of cubic polynomials. And the calculations I did give you a concrete general procedure for converting from Catmull-Rom to Bezier form. About the $\tfrac16$ -- see additions to answer. $\endgroup$
    – bubba
    Commented Sep 2, 2014 at 12:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .