Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space

Question

I am looking for a numerically efficient algorithm to get a triangular surface mesh of the convex hull given by 8 points in three-dimensional space.

For context, the use case is the following:

I have a numerical Simulation calculating the time evolution of a field with three components on a lattice. Say we have lattice coordinates $(i,j,k)$, then every lattice point $(i,j,k)$ has a field vector $(\phi_1, \phi_2 , \phi_3)$ attached.

For relevant physics, I need to now take unit cells on my lattice, so the 8 corners of a little cube of my lattice. I take the field vectors $(\phi_1, \phi_2 , \phi_3)$ of every corner of my unit cell and then interpret their convex hull as a closed volume in $\phi$-space, with $\phi$-space being the 3D space given by the $(\phi_1,\phi_2,\phi_3)$ coordinates.

I am now interested if the volume spanned by these 8 points in $\phi$-space does the following things:

1. If it contains the origin, $(0 ,0 ,0 )$

2. If a Ray traveling from the origin in $(-1,0,0)$-direction pierces my given volume

The idea to evaluate both 1.) and 2.) at the same time is to decompose the surface of the convex hull into triangles. For a triangle in 3-Dimensional space, it is easy to evaluate whether it is pierced by my given Ray in $(-1,0,0)$ direction. I can then count how many triangles are pierced. If exactly two triangles are pierced (because of convexity), I know the cell satisfies condition 2.). If exactly one triangle is pierced, I know the origin has to lie inside my volume, that is condition 1.) is satisfied. Lastly, when no triangles are pierced, none of the above apply.

I think this approach is probably relatively fast. Speed is critical, because I have approximately $10^6 ... 10^9$ cells to evaluate per sweep across my lattice.

I'd be interested in any other approaches as well, though.

Update: So, I think possibly a 3D-Gift-Wrapping algorithm would atleast produce the required result, because it creates the convex hull by consecutively finding triangles on the surface? I will have to try that out tomorrow.

Can I do better than that in terms of efficiency?

Answer 1

You don't actually need the convex hull. This is a simple linear programming instance: find $a_i$ such that $$0 \le a_i \\ \sum a_i = 1 \\ \sum a_i \phi_{i, 1} \le 0 \\ \sum a_i \phi_{i, 2} = 0 \\ \sum a_i \phi_{i, 3} = 0$$ maximising $\sum a_i \phi_{i, 1}$. There are optimised LP solvers out there which you can use.