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?