1
$\begingroup$

I have a unit sphere transformed by a given $4\times 4$ affine transform (it is a 3D transform; using homogenous coordinates with $w=1$ allows representing translation).

I now need to calculate a bounding sphere of this transformed sphere. How can I do this?

For completeness, I should mention I've thought of some bad ways to do it.

For example, one could take the sphere's axis-aligned bounding box, transform that, and then compute the minimal bounding sphere of those 8 points. This is unsatisfactory because the bounding sphere will be very coarse. E.g. if the transform were the identity, we can see that the new bounding sphere will have $3 \sqrt{3} ~\times$ the volume.

So as additional requirements: the preferred method will produce a fairly tight bounding sphere and also be reasonably simple ($O(1)$ time, small constant).

$\endgroup$
1
  • 1
    $\begingroup$ You can SVD the transformation in order to find the longest principle axis of the ellipsoid (the transformed sphere), and the center. Then this tells you the smallest sphere you can put. (I think.) en.m.wikipedia.org/wiki/Singular-value_decomposition $\endgroup$
    – Elle Najt
    Apr 29, 2018 at 4:45

1 Answer 1

Reset to default
-1
$\begingroup$

Okay, well I thought about it some more, and it's actually pretty easy. Here are some algorithms, all of which produce the optimal bounding sphere:

  1. In your example, don't consider the axis-aligned box's corners. Consider its face-centers.

  2. As a refinement of this, forward transform the origin as well as the points $<1,0,0>, <0,1,0>, <0,0,1>$. The transformed origin is the center of the new bounding sphere, and the longest vector from the transformed origin to one of those transformed points is the radius.

  3. Decompose matrix into position/rotation/scale. As a commenter mentioned one can use SVD, but because it's affine, there's also an easier way. Then the radius of the bounding sphere is the max scaling along any axis, and the position is the translation (or you can find it by forward-transforming the origin).

$\endgroup$
1
  • $\begingroup$ This is incorrect. None of your proposed methods work for the transformation $\begin{bmatrix}1&1&0&0\\0&0&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}$, for which you will estimate a radius of $1$ instead of $\sqrt2$. Ultimately, this is because you assume that the matrix can be decomposed as $TRS$, but this one cannot. Most affine transformation matrices are of the form $TR_1SR_2$, which is precisely what the SVD of the $3\times3$ block gives you. (While the above transformation is singular, most invertible transformations will also work. This is just the easiest to work out by hand.) $\endgroup$
    – user856
    Apr 29, 2018 at 5:28

You must log in to answer this question.

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