Polygon Fragmentation using Voronoi Regions
The goal for this project was to explore how to fragmentate convex polygons into smaller, coherent polygons, starting in 2D, in my own personal C++ Engine.
This fragmentation can be done through the use of Delaunay's Triangulation, which in turn, creates Voronoi regions that depict how the polygon will be split.
First, the polygon has to be triangulated, using as few triangles as possible, using the super-triangle technique.
Triangulating the Polygon
Currently Implemented
-
Delaunay's Triangulation 2D
-
Voronoi Regions 2D
-
Step-by-step fragmentation algorithm
-
Separating Axis Theorem (SAT)
-
Simple 2D convex polygon collision physics
-
Delaunay's Triangulation 3D
-
Voronoi Regions 3D
Role
Engine and Physics Programmer
Engine
Custom C++ Engine
Tools and Languages
C++, DirectX11, Visual Studio
Development Time
1.5 Months
Voronoi Regions
Incidentally, the formed triangles can be connected so as to form Voronoi regions that contain the polygon. And if these regions are clipped by the polygons edges, there will be a perfect outline of smaller convex polygons contained within the original polygon.
Creating Voronoi Regions
Getting the Voronoi edge from the triangles is much easier by creating some helper functions first, the following code finds the shared edges between triangles and created the Voronoi regions from them.
Fragmenting the Polygon
By fragmenting the polygon, using those regions, we then get new polygons, which can also be subsequently fragmented, by using the same algorithms.
Fragmenting the Polygon
Newly Created Polygons
Artificial Points
Artificial points can be included in the triangulation, so as to introduce triangles and increase the amount of Voronoi regions in a determined section of the polygon.
Triangulation using Artificial Interest Points
Resulting Voronoi Regions
The end result presents a more typical fragmentation expected when objects break.
"Broken" Polygon
Next Steps
This algorithm is scalable to 3D, with some necessary modifications, as tetrahedrons are now used, instead of triangles.
Initial 3D Polygon
Delaunay's triangulation algorithm is upscaled using 3D math tools, but the principle remains applicable. Resulting Voronoi regions still describe the polygon.
