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:
If it contains the origin, $(0 ,0 ,0 )$
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?