Map an xyz coordinate inside a hexahedron to normalized 0-1 space

Question

The problem I am trying to solve is as follows:

• I have 8 coordinates in a 3D space that define a hexahedron (a distorted cube).

• Next, I have a new arbitrary 3D coordinate in that space.

• How do I map this new coordinate into the hexahedron's space where 0-1 defines the space inside the hexahedron in each axis?

Research I have done leads me to think the answer lies in matrix math "change of basis" operations. However, since it appears that the solution would need to account for a non-linear transformation (the coordinates of any face of the hexahedron could form a trapezoid, for example) I am not sure where to look next. It seems the solution should be a fairly straightforward matrix math... but what? I am not sure where to even look next.

If you can please reply carefully, as I am from a non-math background.

Answer 1

The tri-linear parametrisation that I recommend is

$$ {\vec x} = {\vec A} +{\vec B}\xi +{\vec C}\eta +{\vec D}\omega+ {\vec E}\xi\eta+ {\vec F}\eta\omega+ {\vec G}\xi\omega+ {\vec H} \xi\eta\omega $$

Where $\xi, \eta, \omega \in [0,1]$ and the vectors ${\vec A \cdots \vec H}$ can be calculated in succession from the 8 vertices characterising the hexahedron.

Note that this parametrisation also applies to a distorted hexahedron where the faces are non-planar but are governed by a bi-linear map. The edges are of course, straight.

With respect to the figure below, I've deliberately not labeled the axes as $x$, $y$ or $z$. All that's needed is a Right-Handed Coordinate system and the vertex coordinates of any two opposite faces of the hexahedron such that the opposite pairs $\{\vec{x_0}, \vec{x_1}, \vec{x_2}, \vec{x_3} \}$ and $\{{\vec x_4}, {\vec x_5}, {\vec x_6}, {\vec x_7}\}$ are both ordered clockwise looking in from the respective outward normals to the faces. There is also absolutely no requirement that ${\vec x_7}$ lie "above" or alongside ${\vec x_0}$ which is just illustrated thusly for convenience of rendering the hexahedron (I also didn't want to push the limits of my very meager artistic talent!)

With this ordering, the vectors ${\vec A \cdots \vec H}$ of the parametrisation are

$$ {\vec A} = {\vec x_0} \\ {\vec B} = {\vec x_1}-{\vec x_0} \\ {\vec C} = {\vec x_3}-{\vec x_0} \\ {\vec D} = {\vec x_7}-{\vec x_0} \\ {\vec E} = {\vec x_2}-{\vec x_1}-{\vec x_3}+{\vec x_0} \\ {\vec F} = {\vec x_4}-{\vec x_3}-{\vec x_7}+{\vec x_0} \\ {\vec G} = {\vec x_6}-{\vec x_1}-{\vec x_7}+{\vec x_0} \\ {\vec H} = {\vec x_5}+{\vec x_1}+{\vec x_3}+{\vec x_7}-{\vec x_6}-{\vec x_4}-{\vec x_2}-{\vec x_0} $$

Note the following:

1) The qualifier "Distorted" is necessary because the classical definition of polyhedra requires planar faces. The faces with the current parametrisation can of course be planar, but is is the user's responsibility to ensure that such is the case.

2) the polyhedron can be distorted and twisted as long as

(a) The tri-linear parametrisation still holds

(b) No two faces of the hexahedron intersect

(c) The 8 vertices are ordered as described above with two pairs of 4 vertices each corresponding to opposite faces.

The way to calculate ${\vec A \cdots \vec H}$ is as follows:

Each vertex has a specific and distinct set of $\xi$, $\eta$ and $\omega$ coordinates in parametric space.

First set $\xi=\eta=\omega=0$ in the parametrisation. This corresponds to the vertex ${\vec x}_0$ giving you at once

$${\vec A}={\vec x_0}$$

Now set $\xi=1; \eta=\omega=0$ corresponding to vertex ${\vec x}_1$ which then gives you

$${\vec B}={\vec x_1}-{\vec x_0}$$

and likewise for ${\vec C}$ (with $\eta=1; \xi=\omega=0$ at vertex $\vec x_3$ ) and ${\vec D}$ (with $\omega=1; \xi=\eta=0$ at vertex $\vec x_7$ )

Now corresponding to vertex ${\vec x_2}$, we have $\xi=\eta=1;\omega=0$ which gives you

$${\vec x}_2= = {\vec A} +{\vec B} +{\vec C} + {\vec E}$$

which substituting the known values of ${\vec A}$, ${\vec B}$ and ${\vec C}$

is

$${\vec E} = {\vec x_2}-{\vec x_1}-{\vec x_3}+{\vec x_0}$$

and likewise for ${\vec F}$ (with $\eta=\omega=1;\xi=0$ at vertex $\vec x_4$ ) and ${\vec G}$ (with $\xi=\omega=1;\eta=0$ at vertex $\vec x_6$ ).

Finally, substituting $\xi=\eta=\omega=1$ (vertex ${\vec x_5}$)gives you

$$ {\vec x_5} = {\vec A} +{\vec B} +{\vec C} +{\vec D}+ {\vec E}+ {\vec F}+ {\vec G}+ {\vec H} $$

and substituting in the know values of ${\vec A \cdots \vec G}$ results in

$$ {\vec H} = {\vec x_5}+{\vec x_1}+{\vec x_3}+{\vec x_7}-{\vec x_6}-{\vec x_4}-{\vec x_2}-{\vec x_0} $$

Answer 2

In the very special case of a regular hexahedron to be placed in correspondence with a cube, here is how one can proceed.

It suffices to take the matrix

$$M=\begin{pmatrix} 1/2 & -1/4 & -1/4\\ 0 & \sqrt{3}/4 & -\sqrt{3}/4\\ \sqrt{3}/2 & \sqrt{3}/2 & \sqrt{3}/2 \end{pmatrix}=\begin{pmatrix} 0.5000 & -0.2500 & -0.2500\\ 0 & 0.4330 & -0.4330\\ 0.8660 & 0.8660 & 0.8660 \end{pmatrix},$$

where the columns of $M$ are the images of vectors of canonical basis $\begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix} 0\\ 0\\ 1 \end{pmatrix}$ resp.

giving the transformation formulas:

$$\begin{cases} x' &=& 0.5000 x & - & 0.2500y & - & 0.2500z\\ y' &=& & & 0.4330 y & -& 0.4330z\\ z' &=& 0.8660x & + & 0.8660y & +& 0.8660z \end{cases}$$

($(x,y,z)$, coordinates attached to the cube, $(x',y',z')$ attached to the hexahedron).

Remark 1 : the mutual dot products of the colomns of $M$ are obtained as the coefficients of the matrix:

$$M^TM=\begin{pmatrix} 1 & 5/8 & 5/8\\ 5/8 & 1 & 5/8\\ 5/8 & 5/8 & 1 \end{pmatrix}.$$

One can see thus

• they are all with norm 1,

• all dot-products are the same, giving rhombi (the faces of the hexahedron) acute angles acos$(5/8) \approx 51.3^{\circ}.$

Remark 2 :

If you want to do the reverse (passing from coordinates in the hexahedron to coordinates in the cube), take the coefficients of the inverse of matrix $M$,

$$ M^{-1}=\begin{pmatrix} 1.3333 & -0.0000 & 0.3849\\ -0.6667 & 1.1547 & 0.3849\\ -0.6667 & -1.1547 & 0.3849\end{pmatrix}.$$

Answer 3

If you want the inverse transformation, then I personally cannot think of a way around solving a non-linear set of equations in $\xi$, $\eta$ and $\omega$. However this task can be simplified somewhat by constructing 3 vectors that are orthogonal to the 3 pairs $\vec E$ and $\vec H$, $\vec F$ and $\vec H$, and $\vec G$ and $\vec H$ as

$$ \vec J=\vec E\times \vec H \\ \vec K=\vec F\times \vec H \\ \vec L=\vec G\times \vec H $$

Now, if you dot the given vector $\vec x$ with each of them, you have a set of equations that is at most bi-linear according to:

$$ f(\xi, \eta,\omega)= ({\vec B\cdot\vec J})\xi +({\vec C\cdot\vec J})\eta +({\vec D\cdot\vec J})\omega +({\vec F\cdot\vec J})\eta\omega +({\vec G\cdot\vec J})\xi\omega +({\vec A-\vec x})\cdot\vec J=0 $$

$$ g(\xi, \eta,\omega)=({\vec B\cdot\vec K})\xi +({\vec C\cdot\vec K})\eta +({\vec D\cdot\vec K})\omega +({\vec E\cdot\vec K})\xi\eta +({\vec G\cdot\vec K})\xi\omega +({\vec A-\vec x})\cdot\vec K=0 $$

and

$$ h(\xi, \eta,\omega)= ({\vec B\cdot\vec L})\xi +({\vec C\cdot\vec L})\eta +({\vec D\cdot\vec L})\omega +({\vec E\cdot\vec L})\xi\eta +({\vec F\cdot\vec L})\eta\omega +({\vec A-\vec x})\cdot\vec L=0 $$

which can be solved by a 3-dimensional version of the Newton-Raphson iteration. Convergence should not take more than a handful of iterations.

In fact if the initial guess is good enough, you might even be able to get by with linearising the set of equations (i.e., freezing the non-linear terms at the current estimates of $\xi$, $\eta$ and $\omega$, solving the linear system and updating the non-linear terms during each iteration.