<p>While it's an old question, someone may find the following approach useful nonetheless.</p>
<ol>
<li>Calculate the (axis aligned) bounding box for your input point cloud.</li>
<li>From that, calculate the (axis aligned) bounding cube centered around the centroid of the bounding box (so the two are either identical or the bounding box is fully enclosed in the bounding cube).</li>
<li>Scale the bounding cube up by a factor of three about its centroid (so the scaling will not implicitly transform it in worldspace).</li>
<li>Derrive any of the regular tetrahedra embedded in the cube. That is, take the diagonals of two opposing faces of the cube, more precisely the top- and bottom-face, but such that both diagonals are orthogonal rather than colinear. The four cube vertices connected to those two diagonals are the vertices of your bounding (regular) tetrahedron.</li>
</ol>
<hr />
<p><a href="https://i.sstatic.net/eMddF.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eMddF.jpg" alt="Regular octahedron (red) and embedded (dual) cube (yellow)" /></a>
The yellow cube's vertices touch the red octahedron's faces on their centroids.</p>
<p><a href="https://i.sstatic.net/iu8Nt.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/iu8Nt.jpg" alt="Regular tetrahedron (yellow) embedded in cube (blue)" /></a>
The red octahedron's vertices are the centroids of the blue cube. The blue cube's edge length is three times that of the yellow cube. The red octahedron is identical in both images.</p>
<p><a href="https://i.sstatic.net/LwVNi.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LwVNi.jpg" alt="Regular octahedron (orange) embedded in (yellow) regular tetrahedron" /></a>
The orange octahedron's vertices are the midpoints of the yellow regular tetrahedron. The yellow tetrahedron's bounding box is the blue cube shown above.</p>
<hr />
<hr />
<p>Explanation: A cube's dual is a regular octahedron. So if we take the centroid of each cube face, we get the embedded (dual) octahedron.</p>
<p>This octahedron's volume equals one third of the cube's volume. As the duality works both ways, we can, for a given minimum bounding cube, imagine a regular octahedron inside which our cube is embedded itself.
This bounding octahedron naturally has to be three times the size of the bounding cube.</p>
<p>A regular octahedron on the other hand can be neatly embedded in a regular tetrahedron, where the octahedron's vertices are the midpoints of the tetrahedron's edges.</p>
<p>A regular tetrahedron can be embedded in a cube such that four vertices of the cube make up for the tetrahedron's vertices and the tetrahedron's edges are all diagonals of the cube's face.</p>
<p>It follows we can imagine a regular octahedron which embeds our original bounding cube while itself being embedded in a regular tetrahedron (which we need), itself embedded in a larger cube. The volume of the tetrahedron is exactly one third of that of the large cube, which is where the above-mentioned scaling factor comes from.</p>

CC BY-SA 4.0
2024-01-09T15:03:59.753Z
2024-01-11T00:00:06.027Z
2024-01-11T00:00:06.027Z
Herbert Jensch
<p>I'm wondering how to compute a bounding tetrahedron from a set of points so i can initialize a delaunay triangulation</p>
<p>My first approach was to find the bounding box to my set of points and then compute a tetrahedron going from the bounding box .</p>
<p>I'm searching for a robust method for doing it .</p>

CC BY-SA 4.0
2021-01-02T18:22:29.760Z
Is the tetrahedron oriented?
pmw1234
CC BY-SA 4.0
2021-01-03T12:23:32.570Z
@pmw1234 not necesseraly
Tawfik
CC BY-SA 4.0
2021-01-05T23:43:04.747Z
A good algorithm that isn't necessarily the fastest is to pick several directions.(somewhere between 11 and 16 usually works well) Then compute a tetrahedron oriented on each direction. After computing the tetrahedron for that direction compute it's area only keeping the tetrahedron with the smallest total area. This won't always find the absolute best fit, but it is usually good enough. And it boils the fit algorithm down to finding the best fit for an axis aligned tetrahedron where the current direction is the up axis.
pmw1234
CC BY-SA 4.0
2021-01-05T23:45:58.443Z
Here is a link to a discussion on Axis Aligned Tetrahedrons. https://medium.com/@bromanz/axis-aligned-bounding-tetrahedra-and-octahedra-for-ray-tracing-bounding-volume-hierarchies-683751d84bca
pmw1234
<computational-geometry><geometry><triangulation>
How to compute a bounding tetrahedron
Tawfik
# How to compute a bounding tetrahedron

(Asked by: username_0 on 2020-12-30)

I'm wondering how to compute a bounding tetrahedron from a set of points so i can initialize a delaunay triangulation

My first approach was to find the bounding box to my set of points and then compute a tetrahedron going from the bounding box .

I'm searching for a robust method for doing it .

**Tags:** computational-geometry, geometry, triangulation

> **Comments:**
> **username_1**: Is the tetrahedron oriented?  
> **username_0**: @username_1 not necesseraly  
> **username_1**: A good algorithm that isn't necessarily the fastest is to pick several directions.(somewhere between 11 and 16 usually works well) Then compute a tetrahedron oriented on each direction. After computing the tetrahedron for that direction compute it's area only keeping the tetrahedron with the smallest total area. This won't always find the absolute best fit, but it is usually good enough. And it boils the fit algorithm down to finding the best fit for an axis aligned tetrahedron where the current direction is the up axis.  
> **username_1**: Here is a link to a discussion on Axis Aligned Tetrahedrons. https://medium.com/@bromanz/axis-aligned-bounding-tetrahedra-and-octahedra-for-ray-tracing-bounding-volume-hierarchies-683751d84bca  

---

## 1 answers

### Answer by username_2 on 2024-01-09. Score: 2 | Accepted answer

While it's an old question, someone may find the following approach useful nonetheless.

1. Calculate the (axis aligned) bounding box for your input point cloud.
2. From that, calculate the (axis aligned) bounding cube centered around the centroid of the bounding box (so the two are either identical or the bounding box is fully enclosed in the bounding cube).
3. Scale the bounding cube up by a factor of three about its centroid (so the scaling will not implicitly transform it in worldspace).
4. Derrive any of the regular tetrahedra embedded in the cube. That is, take the diagonals of two opposing faces of the cube, more precisely the top- and bottom-face, but such that both diagonals are orthogonal rather than colinear. The four cube vertices connected to those two diagonals are the vertices of your bounding (regular) tetrahedron.

---

[![Regular octahedron (red) and embedded (dual) cube (yellow)](https://i.sstatic.net/eMddF.jpg)](https://i.sstatic.net/eMddF.jpg)
The yellow cube's vertices touch the red octahedron's faces on their centroids.

[![Regular tetrahedron (yellow) embedded in cube (blue)](https://i.sstatic.net/iu8Nt.jpg)](https://i.sstatic.net/iu8Nt.jpg)
The red octahedron's vertices are the centroids of the blue cube. The blue cube's edge length is three times that of the yellow cube. The red octahedron is identical in both images.

[![Regular octahedron (orange) embedded in (yellow) regular tetrahedron](https://i.sstatic.net/LwVNi.jpg)](https://i.sstatic.net/LwVNi.jpg)
The orange octahedron's vertices are the midpoints of the yellow regular tetrahedron. The yellow tetrahedron's bounding box is the blue cube shown above.

---

---

Explanation: A cube's dual is a regular octahedron. So if we take the centroid of each cube face, we get the embedded (dual) octahedron.

This octahedron's volume equals one third of the cube's volume. As the duality works both ways, we can, for a given minimum bounding cube, imagine a regular octahedron inside which our cube is embedded itself.
This bounding octahedron naturally has to be three times the size of the bounding cube.

A regular octahedron on the other hand can be neatly embedded in a regular tetrahedron, where the octahedron's vertices are the midpoints of the tetrahedron's edges.

A regular tetrahedron can be embedded in a cube such that four vertices of the cube make up for the tetrahedron's vertices and the tetrahedron's edges are all diagonals of the cube's face.

It follows we can imagine a regular octahedron which embeds our original bounding cube while itself being embedded in a regular tetrahedron (which we need), itself embedded in a larger cube. The volume of the tetrahedron is exactly one third of that of the large cube, which is where the above-mentioned scaling factor comes from.


---

