top of page

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


Engine and Physics Programmer


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.

3D Voronoi Regions

bottom of page