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?


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.

  • $\begingroup$ Thanks for the answer! Are you sure that this approach is going to be faster? I had considered that for a little but decided it wouldn't be very fast by all likelyhood, seeing as (this is really just off the top of my head right now though, feel free to correct me!) it'd probably boil down to using the simplex algorithm. In each step of the simplex I'd need to invert (3x3) Matrices which is somewhere around $O(n^{2.3})$ or so in the best case. Usually takes like two or three corners to find a solution, worst case it would need all of them. $\endgroup$ Jul 11 '19 at 5:52
  • $\begingroup$ 1. Asymptotic performance is largely irrelevant when n is tiny. 2. I recommended using a library rather than rolling your own solver. I don't know which libraries use simplex, crisscross, internal point, or a runtime decision between the three. 3. I don't guarantee it's the fastest solution, but it should be fast to implement and benchmark. $\endgroup$ Jul 11 '19 at 6:50
  • $\begingroup$ Oh well, I like the approach though. If it happens to be too slow I can still worry about that later - if I'm lucky I'll still be memory bandwidth limited on my lattice in which case it doesn't matter either way. Slightly off-topic but, any (personal opinion) recommendations for good solvers when using c++? $\endgroup$ Jul 11 '19 at 7:23
  • $\begingroup$ If you're associated with a physics lab, you could ask around to see whether you've got licences for any commercial offerings. If not, I know GNU has an LP solver. $\endgroup$ Jul 11 '19 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.