What This Is

A Voronoi Diagram is a set of regions calculated around a given set of seed points, wherein any point within a region is closer to that region's seed than to any other seed. If that doesn't make sense, imagine a set of cell phone towers (seed points) plotted on a map. A voronoi would be useful in determining the exact coverage area of each tower. A person standing at any location on the map would fall into one of the defined regions, which would immediately determine the cell tower they're closest to.


Why Do I Care

I've been exploring ways to dynamically fracture shapes into smaller chunks that could be chipped away or exploded as part of a 2D physics game I'd like to make (eventually). The amount of processing it takes to create an effect is a huge concern in computer graphics, so most attempts to simulate real-world phenomena are largely approximated to save on computation time. Every white paper I found on fracturing used mathematically accurate engineering models to determine the characteristics of various rock types, which, besides being incomprehensible were totally impractical for my needs.
I stumbled upon voronoi diagrams while searching for intersecting line formulas on Wikipedia. They looked nearly identical to the sketches I'd made in previous attempts to solve the problem, so it was a perfect application. The shapes appeared chunky and rock-like, and because voronoi cells are convex by nature, the new chunks would play well with most most 2D physics engines.


There are two ways to calculate voronois that I found. One was easy but incredibly slow; the other was surprisingly fast but far more complicated. You can learn about the methods here, at the American Mathematical Society.


I owe an enormous thanks to Alan Shaw for his AS3 port of Steve Fortune's original sweep line algorithm for quickly calculating voronois.

Relax Mode

Centroid formulas

VIEW SOURCE

The relaxation is accomplished using Lloyd's Algorithm. Over several iterations (in this case every frame) the center point, or centroid, of each polygon is calculated using the formulas at the left (click view source to see my implementation in AS3). They first find the signed area of the polygon, which is then used to calculate the X and Y coordinates of the centroid. Using interpolation, the seeds are slowly moved a percentage towards their respective centroid until they are practically on top of one another. In a group of adjacent regions, this eventually leads to a uniform layout.


Cellular Rendering

Cellular Half Points

VIEW SOURCE

The cellular rendering was achieved by inserting half points (in the example at left, C0 - C4) between the coordinates that make up each polygon (N0 - N4), then drawing arcs between the half points. The N points were then used as bézier control handles to keep the arc inside of the voronoi region. While in cellular rendering mode, I implemented a filter to only morph certain sets of seeds. The filter changes randomly over time to make the cells appear more organic and alive. 

				
private function getPolygonArea($p:Vector.<Point>)
{
	
	var $area:Number = 0;
	//this is starting at the last point in the polygon and going around clockwise
	var $j:uint = $p.length - 1;
	for (var $i:uint = 0; $i < $p.length; $j = $i++) {
		$area = $area + ($p[$j].x+$p[$i].x) * ($p[$j].y-$p[$i].y); 
	}
	return $area / 2 *-1;
}

private function findCentroid($p:Vector.<Point>):Point {
	var $x:Number = 0;
	var $y:Number = 0;
	
	//again, starting at the last point and going around clockwise
	var $j:uint = $p.length - 1;
	var $p1:Point;
	var $p2:Point;
	for (var i:uint = 0; i < $p.length;$j= i++) {
		$p1 = $p[$j];
		$p2 = $p[i];
		$x += ($p1.x + $p2.x)*($p1.x * $p2.y -  $p2.x * $p1.y);
		$y += ($p1.y + $p2.y)*($p1.x*$p2.y - $p2.x * $p1.y)
	}
	var $Area = getPolygonArea($p);
	$x = 1 / (6 * $Area) * $x;
	$y = 1 / (6 * $Area) * $y;
	
	return new Point($x, $y);
}
				
			
				
//draw biological-looking cells if draw mode is set to cellular
//create a polygon of in-between points from the original polygon
var $c:Vector. = new Vector.();
var $j:uint;
for (i = 0; i < $p.length; $j = i++) {
	$j = (i == $p.length - 1) ? 0 : i + 1;
	$c.push(Point.interpolate($p[i], $p[$j], .5));
}

_diagramSprite.graphics.moveTo($c[$c.length -1].x, $c[$c.length-1].y);
var $cp:Point;
for (i = 0; i < $c.length; i++) {
	$cp = (i == $c.length -1) ? $p[i] : $p[i];
	_diagramSprite.graphics.curveTo($cp.x, $cp.y, $c[i].x, $c[i].y);
}
_diagramSprite.graphics.endFill();