Voronoi Destruction

[0xDE57]

The technical vision is to have Asteroids break apart into smaller polygons based on a voronoi graph.

I have a prototype that feels very close to working but suffers from broken edge cases. I tried to derive the voronoi points by connecting the circumcenters of the delaunay points. Due to under estimation of complexity to implement, I have deferred this for now.

Asteroid destruction is currently done using delaunay triangulation for simplicity. Delaunay is the dual-graph for Voronoi, and still retains the desired effect of:

1. asteroids satisfyingly shatter into pieces that make up the original body
2. shattered pieces maintain 1-to-1 surface area and mass of parent body
3. asteroids and all shattered pieces are simple convex polygons (easy collision detection)

Current triangulation algorithm is based on: https://paulbourke.net/papers/triangulate/

Stretch goal once working; would be to release the voronoi stuff as a separate library for libgdx for others to use.

[0xDE57]

Alternative to fortunes algo, there is Qhull. I was surprised to find out that my attempt was the same as QHULL (the difference being that I never finished solving it...)

"Qhull computes the Voronoi diagram via the Delaunay triangulation. Each Voronoi vertex is the circumcenter of a facet of the Delaunay triangulation. Each Voronoi region corresponds to a vertex (i.e., input site) of the Delaunay triangulation. " http://www.qhull.org/html/qvoronoi.htm