I was planning to make an article from this (may yet happen I guess) but time is – as ever – my greatest enemy. This must be evident from the shoddy/unprofessional nature of my videos, especially of late 🙂
I’ve been working on this on and off for a while now (within 666), and it’s finally ready to be rolled into the Dom itself.
A bit of pre-amble; a ‘hull’ is (like a boat) a convex shape that encapsulates things inside it. For game purposes, we often use hulls to do ‘mid-phase’ collision detection. Which is just short of actually doing object to model triangle collision (which can be expensive and time consuming in real-time for large/complex geometries).
However, I have other plans for this algorithm. I want to use it to generate the shield effects for the vessels and models in the game as well as for collision detection. I also have some ideas on using it for other special effects like explosions/clouds/nebula – though that’s all experimental and still very much ‘in my head’ at the moment!
The basic idea of the Quick Hull algorithm, is to pick a triangle from a cloud of arbitrary points (any will do). Then find the point in the cloud furthest away from one face of the triangle. Now make new triangles to connect the edges of the original, to this point.
If you then iterate all these new triangles again, and again… eventually you inflate your original triangle to be a volume that encloses all the points in the cloud.
Then all you have to do is substitute the cloud of points with the points in your model, and off you go.