4
$\begingroup$

I am trying to find the minimum bounding box of an ellipsoid. In my search, I found this answer and also some other nice descriptions like this one to the problem. I am not a mathematician (I need this in an program for my own field of astronomy), I wanted to consult you on the affine transformation that is necessary to define an ellipsiod to use in those solutions.

Let's say we define the orientation of the ellipsoid from its major axis (the largest axis of the ellipsoid). Assuming the 3 axes of the ellipsoid to be on the three coordinates with lengths of $a$, $b$ and $c$ along each axis (with $a\ge{b}$ and $a\ge{c}$), then only a single affine transformation (to a sphere) is necessary:

$$ \left[\matrix{a&0&0&0 \\ 0&b&0&0 \\ 0&0&c&0 \\ 0&0&0&1}\right] $$

Now, if we first rotate the major axis by $\theta$ from the first axis towards the second axis, and then rotate it by $\phi$ from the (rotated) first axis towards the third axis, the combined affine transformation becomes:

$$ \left[\matrix{a&0&0&0 \\ 0&b&0&0 \\ 0&0&c&0 \\ 0&0&0&1}\right] \left[\matrix{cos\theta&-sin\theta&0&0 \\ sin\theta&cos\theta&0&0 \\ 0&0&1&0 \\ 0&0&0&1}\right] \left[\matrix{cos\phi&0&-sin\phi&0 \\ 0&1&0&0\\ sin\phi&0&cos\phi&0 \\ 0&0&0&1}\right]$$

Is the multiplied matrix (from left to right) the correct affine transformation that must go into the equations in the links above?

Thanks in advance.

$\endgroup$
  • $\begingroup$ Are you looking for a bounding box aligned with the coordinate planes, or one with faces perpendicular to the principal axes of the ellipsoid? $\endgroup$ – amd Jul 6 '17 at 23:14
3
$\begingroup$

Euler angles (and Tait-Bryan angles) are evil. They can be defined in a number of ways, and even when people remember to specify the axes and the order they are rotated, it all gets too hairy too fast. Instead, I show how to easily deal with this using only elementary vector algebra.


Let's say you have an ellipsoid centered at $\vec{c}$ with semi-principal axes $\vec{r}_1 $, $\vec{r}_2$, and $\vec{r}_3$: $$\vec{r}_1 = \left [ \begin{array}{c} r_{11} \\ r_{21} \\ r_{31} \end{array} \right ], \qquad \vec{r}_2 = \left [ \begin{array}{c} r_{12} \\ r_{22} \\ r_{32} \end{array} \right ], \qquad \vec{r}_3 = \left [ \begin{array}{c} r_{13} \\ r_{23} \\ r_{33} \end{array} \right ]$$

The surface of the ellipsoid passes through points $\vec{c} \pm \vec{r}_1$, $\vec{c} \pm \vec{r}_2$, and $\vec{c} \pm \vec{r}_3$.
The semi-principal axes are all perpendicular: $\vec{r}_1 \cdot \vec{r}_2 = 0$, $\vec{r}_1 \cdot \vec{r}_3 = 0$, and $\vec{r}_2 \cdot \vec{r}_3 = 0$.

The axis-aligned bounding box for the above ellipsoid is defined by $$\begin{array}{c} x = c_x \pm \sqrt{r_{11}^2 + r_{12}^2 + r_{13}^2} \\ y = c_y \pm \sqrt{r_{21}^2 + r_{22}^2 + r_{23}^2} \\ z = c_z \pm \sqrt{r_{31}^2 + r_{32}^2 + r_{33}^2} \end{array}$$

Note that this applies also to the case where the homogenous transformation matrix $\mathbf{M}$ that transforms the unit sphere to the ellipsoid is $$\mathbf{M} = \left [ \begin{array}{cccc} r_ {11} & r_{12} & r_{13} & c_x \\ r_{21} & r_{22} & r_{23} & c_y \\ r_{31} & r_{32} & r_{33} & c_z \\ 0 & 0 & 0 & 1 \end{array} \right ]$$


We can describe the transformation of the unit sphere to the above ellipsoid using $$\vec{p}(u, v, w) = \vec{p}(\vec{t}) = \vec{c} + u \vec{r}_1 + v \vec{r}_2 + w \vec{r}_3 = \vec{c} + \mathbf{R} \vec{t} \tag{1}\label{1}$$ where $\vec{t} = ( u , v , w )$ fulfills $$\left\lVert \vec{t} \right\rVert = 1 \qquad \iff \qquad u^2 + v^2 + w^2 = 1$$ on the surface of the ellipsoid, and $$\left\lVert \vec{t} \right\rVert \lt 1 \qquad \iff \qquad u^2 + v^2 + w^2 \lt 1$$ within the ellipsoid, and matrix $\mathbf{R}$ has the semi-principal axes as column vectors, $$\mathbf{R} = \left [ \begin{array}{ccc} \vec{r}_1 & \vec{r}_2 & \vec{r}_3 \end{array} \right ] = \left [ \begin{array}{ccc} r_{11} & r_{12} & r_{13} \\ r_{21} & r_{22} & r_{23} \\ r_{31} & r_{32} & r_{33} \end{array} \right ]$$

Essentially, we scale the unit sphere by the semi-principal axes, rotate it to the new orientation, and translate the center.


The above operation is invertible, if the ellipsoid is not degenerate; that is, if $\left\lVert\vec{r}_1\right\rVert \gt 0$, $\left\lVert\vec{r}_2\right\rVert \gt 0$, and $\left\lVert\vec{r}_3\right\rVert \gt 0$.

Since rotation matrices are orthonormal, its inverse is its transpose. To counteract the scaling, we scale by the inverses of the semi-principal axes.

The scaling vectors are now row vectors of the transformation matrix, with lengths inverse to the corresponding semi-principal axis length; i.e. $$\vec{s}_n = \left ( \frac{\vec{r}_n}{\left\lVert \vec{r}_n \right\rVert^2} \right)^{T}, \qquad n = 1, 2, 3$$ so that $$\left\lVert \vec{s}_n \right\rVert = \left\lVert \vec{r}_n \right\rVert^{-1}, \qquad n = 1, 2, 3$$ i.e. $$\vec{s}_1 = \frac{\vec{r}_1}{\left\lVert\vec{r}_1\right\rVert^2} = \left [ \begin{array}{ccc} s_{11} & s_{12} & s_{13} \end{array} \right ]$$ $$\vec{s}_2 = \frac{\vec{r}_2}{\left\lVert\vec{r}_2\right\rVert^2} = \left [ \begin{array}{ccc} s_{21} & s_{22} & s_{23} \end{array} \right ]$$ $$\vec{s}_3 = \frac{\vec{r}_3}{\left\lVert\vec{r}_3\right\rVert^2} = \left [ \begin{array}{ccc} s_{31} & s_{32} & s_{33} \end{array} \right ]$$ $$s_{i j} = \frac{r_{j i}}{ r_{1 i}^2 + r_{2 i}^2 + r_{3 i}^2 }, \qquad i = 1, 2, 3; \; j = 1, 2, 3$$ $$\mathbf{S} = \left [ \begin{array}{ccc} s_{11} & s_{12} & s_{13} \\ s_{21} & s_{22} & s_{23} \\ s_{31} & s_{32} & s_{33} \end{array} \right ]$$

Now, $$\vec{t}(\vec{p}) = \vec{s}_1 \cdot ( \vec{p} - \vec{c} ) + \vec{s}_2 \cdot ( \vec{p} - \vec{c} ) + \vec{s}_3 \cdot ( \vec{p} - \vec{c} ) = \mathbf{S}\left(\vec{p} - \vec{c}\right) \tag{2}\label{2}$$


Essentially, $\eqref{1}$ and $\eqref{2}$ are the inverse of each other.

If you insist on using Euler or Tait-Bryan angles or other similar angular convention, I recommend you use them to calculate the semi-principal axes $\vec{r}_1$, $\vec{r}_2$, and $\vec{r}_3$ only, and then apply the above vector solution.

$\endgroup$
  • $\begingroup$ Thank you for the great explanation and great suggestion, indeed Euler angles can be very confusing compared to an approach like this. I nicely understood all the way until equation 2, but I couldn't follow what happens next. How does the vector t equal the Matrix S? $\endgroup$ – astroboy Jul 6 '17 at 22:17
  • $\begingroup$ I think I understood, by $\vec{t}(\vec{p})$ you mean $\vec{t}$ as a function of $\vec{p}$. But by $\mathbf{S}(\vec{p}-\vec{c}$) you mean $\mathbf{S}$ multiplied by the vector ($\vec{p}-\vec{c}$). $\endgroup$ – astroboy Jul 6 '17 at 22:24
  • $\begingroup$ @astroboy: Yes to your latter comment: Equation (2) calculates $\vec{t}$ as a function of $\vec{p}$; which is matrix $\mathbf{S}$ multiplied by vector $(\vec{p} - \vec{c})$. Conversely, equation (1) calculates $\vec{p}$ as a function of $\vec{t}$ (which is vector $\vec{c}$, plus matrix $\mathbf{R}$ multiplied by vector $\vec{t}$). $\endgroup$ – Nominal Animal Jul 6 '17 at 23:05
  • $\begingroup$ I think I just noticed a typo in the derivation above: shouldn't the $s_{ij}$ equation have the following form: $s_{ij}=r_{ji}/(r_{1j}^2+r_{2j}^2+r_{3j}^2)$ $\endgroup$ – astroboy Jul 9 '17 at 21:18
  • $\begingroup$ @astroboy: Yes, exactly, because $\vec{s}_1 = ( s_{11} , s_{12} , s_{13} )$ is defined by $\vec{r}_1 = ( r_{11} , r_{21} , r_{31} )$, and so on. (Embarrassing!). Good catch, thanks! Fixed in the answer. $\endgroup$ – Nominal Animal Jul 10 '17 at 0:04
0
$\begingroup$

The correct way to transform the matrix $Q$ of a quadratic form such as that representing an ellipsoid is via conjugation. That is, instead of computing $QB$ you need to compute $B^TQB$. You can see why this is by going back to the equation represented by $Q$, namely $\mathbf x^TQ\mathbf x=0$. (Here, $\mathbf x=(x,y,z,1)^T$.) For the transformation $\mathbf x'=M\mathbf x$, you would replace $\mathbf x$ by $M^{-1}\mathbf x'$ in the equation, getting $$(M^{-1}\mathbf x')^TQ(M^{-1}\mathbf x')={\mathbf x'}^TM^{-T}QM^{-1}\mathbf x'=0$$ so the transformed matrix is $M^{-T}QM^{-1}$. Notice, too, that the matrix of the quadratic form is transformed by the inverse of the matrix that transforms points.

You can generate any affine transformation via a sequence of scaling, rotation and transformation, as described in Nominal Animal’s answer, and then use those to transform the unit sphere, which has the matrix $\operatorname{diag}(1,1,1,-1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.