**What's this?**

A script that generates random camouflage patterns.

It's a toy, a product of my interest in military camouflage and joy of programming.

It uses a **binary space partitioning** algorithm. It starts with an empty canvas which it breaks into smaller pieces (usually a three to five-sided polygon). Each polygon is then divided further, until a sufficient level of detail is reached (the *polygon size* parameter).

Each polygon is assigned a color. *Color bleed* determines how many polygons are painted with each "stroke". Low values (0) yields a very random color distribution while higher values form cohesive blobs.

Following this *spots* are added. These have randomized radii and placement. Spot *sampling* variation determines how far away the color is fetched - a low value will result only in fuzzy edges, while higher values introduce more noise.

The final step is *pixelization* which reduces the resolution and gives a "blocky" look. This also has a sampling variation parameter.

It can emulate polygon-based (such as swedish M90 or german Splittermuster) and modern "digital" camouflage quite well.

My main motivation was to study how BSP could be applied to arbitrary polygons. While I had written BSP algorithms before (for generating random levels in games), they were strictly grid-based and could only generate rectangles.

Writing this has given me a better understanding of geometry. I learned the PHP GD library and also picked up a bit of JavaScript.

Things that can be improved:

- I need to come up with a way to smooth polygon corners to make "organic" patterns. The user should be able to finetune the amount of smoothing.
- I have ideas for different paint modes (stripes, etc).
- The interface could be better. At least, it should describe the min/max values of the parameters.

Some other thoughts:

- Why is the image generated on the server? With the scripting capabilities of modern browsers, this could be entirely a client-side application.
- While it is feasible to generate tileable patterns, no attempt was made. I just didn't want to get into it.
- It uses discrete color values. It is no technical challenge to use gradients, but that's not how military camouflage is designed (unlike civilian "hunter" that sometimes have pictures of actual vegetation printed on the fabric). For the human eye, dithering does a better job concealing than smooth color curves. Also, using fewer colors is cheaper.

The color picker is JSColor. It is an excellent, light-weight package.

Except for the color picker, everything is self-contained in the same script file. While this is hardly the best way to design a script, it was an exercise in PHP and makes distribution simple. You are free to view the source.

This script was written by Ulf Åström (happyponyland.net). If you have questions, find bugs or make improvements to it, you can contact me.

With love,

/Happy Pony Land

**Note: There are currently a couple of bugs I need to fix and some features I'd like to add, but I don't have time or motivation to work on this right now. I might rewrite it in the future.**

What's this? Read the explanation.

x = $new_x;
$this->y = $new_y;
}
}
/*
A set of vertices that are supposed to make up a solid face (the
last vertex connects to the first, forming the final edge).
*/
class Polygon
{
public $color_index;
public $vertex_list = array();
public $neighbour_list = array();
/*
Sums the length of all edges of the polygon.
*/
function circumference()
{
$total = 0;
$edges = count($this->vertex_list);
for ($i = 0; $i < $edges; $i++)
{
$a = $this->vertex_list[$i];
$b = $this->vertex_list[($i + 1) % $edges];
$total += edge_length($a, $b);
}
return $total;
}
}
class Pattern
{
public $poly_list = Array();
public $polys = 0;
public $poly_size = 500;
public $spots = 2000;
public $spot_radius1 = 10;
public $spot_radius2 = 20;
public $spot_sampling = 30;
public $pixelize = 50;
public $pixel_sampling = 10;
public $pixel_dens_x = 10;
public $pixel_dens_y = 10;
public $bleed_amount = 5;
public $bleed_mode = 0;
public $color = Array();
}
$pat = new Pattern();
/*
Checks for GET parameters.
*/
function read_options($pat)
{
if (isset($_GET["poly_size"]) && is_numeric($_GET["poly_size"]))
$pat->poly_size = $_GET["poly_size"];
if (isset($_GET["spots"]) && is_numeric($_GET["spots"]))
$pat->spots = $_GET["spots"];
if (isset($_GET["spot_sampling"]) && is_numeric($_GET["spot_sampling"]))
$pat->spot_sampling = $_GET["spot_sampling"];
if (isset($_GET["spot_radius1"]) && is_numeric($_GET["spot_radius1"]))
$pat->spot_radius1 = $_GET["spot_radius1"];
if (isset($_GET["spot_radius2"]) && is_numeric($_GET["spot_radius2"]))
$pat->spot_radius2 = $_GET["spot_radius2"];
if (isset($_GET["pixelize"]) && is_numeric($_GET["pixelize"]))
$pat->pixelize = $_GET["pixelize"];
if (isset($_GET["pixel_dens_y"]) && is_numeric($_GET["pixel_dens_y"]))
$pat->pixel_dens_y = max(1, $_GET["pixel_dens_y"]);
if (isset($_GET["pixel_dens_x"]) && is_numeric($_GET["pixel_dens_x"]))
$pat->pixel_dens_x = max(1, $_GET["pixel_dens_x"]);
if (isset($_GET["pixel_sampling"]) && is_numeric($_GET["pixel_sampling"]))
$pat->pixel_sampling = $_GET["pixel_sampling"];
if (isset($_GET["bleed_amount"]) && is_numeric($_GET["bleed_amount"]))
$pat->bleed_amount = $_GET["bleed_amount"];
if (isset($_GET["bleed_mode"]) && is_numeric($_GET["bleed_mode"]))
$pat->bleed_mode = $_GET["bleed_mode"];
/*
if (isset($_GET[""]) && is_numeric($_GET[""]))
$pat-> = $_GET[""];
*/
for ($i = 0; $i < 8; $i++)
{
if (isset($_GET["c" . $i]))
{
$temp = $_GET["c" . $i];
$r = base_convert(substr($temp, 0, 2), 16, 10);
$g = base_convert(substr($temp, 2, 2), 16, 10);
$b = base_convert(substr($temp, 4, 2), 16, 10);
array_push($pat->color,
hexdec(str_pad(dechex($r), 2, 0, STR_PAD_LEFT) .
str_pad(dechex($g), 2, 0, STR_PAD_LEFT) .
str_pad(dechex($b), 2, 0, STR_PAD_LEFT)));
}
}
if (count($pat->color) == 0)
{
array_push($pat->color, 0x00000000);
}
$pat->poly_size = max(MIN_POLY_SIZE, $pat->poly_size);
$pat->spots = min(MAX_SPOTS, $pat->spots);
$pat->spot_radius1 = max(5, min($pat->spot_radius1, MAX_SPOT_RADIUS));
$pat->spot_radius2 = max(5, min($pat->spot_radius2, MAX_SPOT_RADIUS));
$pat->pixel_dens_x = max(10, $pat->pixel_dens_x);
$pat->pixel_dens_y = max(10, $pat->pixel_dens_y);
return;
}
/*
A and B should be Vertex. Returns a third point between A and
B. FRAC should be a number between 0 and 1 and determines the
distance between A - new Vertex - B (0.5 places it in the middle).
*/
function edge_split($a, $b, $frac)
{
if ($a->x < $b->x)
$new_x = $a->x + (abs($b->x - $a->x) * $frac);
else
$new_x = $a->x - (abs($b->x - $a->x) * $frac);
if ($a->y < $b->y)
$new_y = $a->y + (abs($b->y - $a->y) * $frac);
else
$new_y = $a->y - (abs($b->y - $a->y) * $frac);
return new Vertex(floor($new_x), floor($new_y));
}
/*
A and B should be Vertex. Returns its length (in pixels).
*/
function edge_length($a, $b)
{
return sqrt(pow(abs($b->x - $a->x), 2) + pow(abs($b->y - $a->y), 2));
}
/*
A and B should be arrays with a "value" key. Returns negative if A
is worth less than B, otherwise positive.
If equal... the result is random.
*/
function value_cmp($a, $b)
{
if ($a["value"] == $b["value"])
{
if (rand() % 2)
return -1;
else
return 1;
}
else if ($a["value"] < $b["value"])
return 1;
else
return -1;
}
function new_edge($pat, $a1, $a2, $b1, $b2)
{
$ret = array();
$a_frac = 0.4 + (rand() % 3) / 10;
$b_frac = 0.4 + (rand() % 3) / 10;
/*
Pick a random point along the edges A and B. We will split the
polygon between these two.
*/
$a_vert = edge_split($a1, $a2, $a_frac);
$b_vert = edge_split($b1, $b2, $b_frac);
array_push($ret, $a_vert);
array_push($ret, $b_vert);
return $ret;
}
/*
Draws all polygons in PAT on IMAGE. If USE_INDEX is true, the
polygon index is used as color (for detecting neighbours). If
USE_INDEX is false, the corresponding truecolor value of the
polygons color index is used.
*/
function draw_polygons($image, $pat, $use_index)
{
for ($i = 0; $i < $pat->polys; $i++)
{
$polygon = $pat->poly_list[$i];
/*
GD wants polygons in a slightly different format. Go through all
vertices and push them onto a new array, with alternating X and
Y values. While we're at it, count the edges so we won't need to
do a count() call ( / 2 ).
*/
$coords = array();
$edges = 0;
foreach ($polygon->vertex_list as $pair)
{
array_push($coords, $pair->x, $pair->y);
$edges++;
}
if ($use_index)
$color = $i;
else
$color = $pat->color[$polygon->color_index];
/* Fill the polygon. */
imagefilledpolygon($image, $coords, $edges, $color);
imagepolygon($image, $coords, $edges, $color);
}
}
/*
Among the neighbours of polygon INDEX in PAT, count how many are
COLOR. Pardon my inconsistent spelling.
*/
function colored_neighbours($pat, $index, $color)
{
$polygon = $pat->poly_list[$index];
$count = 0;
foreach ($polygon->neighbour_list as $neig_index)
{
$other_poly = $pat->poly_list[$neig_index];
if ($other_poly->color_index !== FALSE &&
$other_poly->color_index == $color)
{
$count++;
}
}
return $count;
}
/*
Fills polygon INDEX in PAT (and at most BLEED adjacent polygons) with COLOR.
*/
function color_polygon($pat, $index, $color, $bleed)
{
$polygon = $pat->poly_list[$index];
$polygon->color_index = $color;
/* Max recursion depth reached. */
if ($bleed <= 0)
return;
/*
Make a list of the neighbours for this polygon that do not have a
color set. Sort these according to who has the most neighbours of
the same color - this will make polygons of the same color more
like to clump together.
*/
$candidates = array();
foreach ($polygon->neighbour_list as $neig_index)
{
if ($pat->poly_list[$neig_index]->color_index !== FALSE)
continue;
array_push($candidates,
array("index" => $neig_index,
"value" => colored_neighbours($pat, $neig_index, $color)));
}
if (count($candidates) > 0)
{
usort($candidates, "value_cmp");
color_polygon($pat, $candidates[0]["index"], $color, $bleed - 1);
}
return;
}
/*
Main generator function. PAT is the pattern specification to use
(this is a separate reference from the global $pat - even if we
usually point both to the same thing). POLYGON is the area we wish
to draw our pattern on (usually the whole max_width * max_height).
Recursion won't reach further than DEPTH.
*/
function bsp_split($pat, $polygon, $depth)
{
/* We set this to true to end recursion. */
$end_rec = false;
/*
How many edges this polygon has. Since all edges are connected, we
just count the number of points that make it up.
*/
$edges = count($polygon->vertex_list);
/*
Make a list of all edge lengths. Go through all Vertex in the
polygon, calculate the distance to the next to get the length of
the edge.
Store each point as an array with keys "value" (length) and
"index", which is the index of its starting Vertex _within the
polygon_. We can then sort the length array without losing
length->index association.
*/
$edge_len = Array();
for ($i = 0; $i < $edges; $i++)
{
$len = edge_length($polygon->vertex_list[$i], $polygon->vertex_list[($i + 1) % $edges]);
$edge_len[$i] = array("index" => $i, "value" => $len);
}
/*
Sum the edges of this polygon. If it's small enough to fit inside
the polygon size parameter we don't need to break it up further.
*/
$size = 0;
for ($i = 0; $i < $edges; $i++)
$size += $edge_len[$i]["value"];
if ($size < $pat->poly_size)
$end_rec = true;
/* If we've reached the maximum depth for our recursion. */
if ($depth <= 0)
$end_rec = true;
if ($end_rec)
{
array_push($pat->poly_list, $polygon);
return;
}
/*
This polygon needs to be divided at least once more!
Sort the edges by length, then pick the two longest to split
along. This should ensure a somewhat uniform distribution.
*/
usort($edge_len, "value_cmp");
$a_edge = $edge_len[0]["index"];
$b_edge = $edge_len[1]["index"];
/*
We need to have these in order for the polygon splitting to work
properly. If A has a higher index than B, exchange them.
*/
if ($a_edge > $b_edge)
{
$temp = $b_edge;
$b_edge = $a_edge;
$a_edge = $temp;
}
/* These will be the new polygons. */
$a_poly = new Polygon();
$b_poly = new Polygon();
/*
Modulo $edges means we go back to the first point in the polygon
if we run over the last one.
*/
$a1 = $polygon->vertex_list[$a_edge];
$a2 = $polygon->vertex_list[($a_edge + 1) % $edges];
$b1 = $polygon->vertex_list[$b_edge];
$b2 = $polygon->vertex_list[($b_edge + 1) % $edges];
/*
Generate the dividing edge(s) C, extending from somewhere along A
to somewhere along B.
*/
$c = new_edge($pat, $a1, $a2, $b1, $b2);
/*
Stitch together two new polygons, each consisting of "half" of the
old polygon. The dividing edge(s) C are included in both.
*/
for ($i = 0; $i <= $a_edge; $i++)
array_push($a_poly->vertex_list, $polygon->vertex_list[$i]);
foreach ($c as $c_vert)
array_push($a_poly->vertex_list, $c_vert);
for ($i = $b_edge + 1; $i < $edges; $i++)
array_push($a_poly->vertex_list, $polygon->vertex_list[$i]);
/* Second polygon. */
for ($i = $a_edge + 1; $i <= $b_edge; $i++)
array_push($b_poly->vertex_list, $polygon->vertex_list[$i]);
$c = array_reverse($c);
foreach ($c as $c_vert)
array_push($b_poly->vertex_list, $c_vert);
/* Now that we have two new polygons, try to repeat the process on them. */
bsp_split($pat, $a_poly, $depth - 1);
bsp_split($pat, $b_poly, $depth - 1);
return;
}
/* Main execution starts here. */
read_options($pat);
/*
Generate the "big polygon", i.e. the full area we wish to generate a
pattern on. We'll distort this a little by actually giving it 8
edges - this somewhat removes its tendency to generate pure squares or
90-degree triangles (happens with 0.5 a/b_frac values).
*/
$distort = array();
for ($i = 0; $i < 4; $i++)
$distort[$i] = (rand() % 10) / 11;
$start_poly = new Polygon();
$start_poly->vertex_list = Array(new Vertex(WIDTH, 0),
new Vertex(WIDTH * $distort[0], 0),
new Vertex(0, 0),
new Vertex(0, HEIGHT * $distort[1]),
new Vertex(0, HEIGHT),
new Vertex(WIDTH * $distort[2], HEIGHT),
new Vertex(WIDTH, HEIGHT),
new Vertex(WIDTH, HEIGHT * $distort[3]));
/* Generate a rough sketch how we want the pattern to look. */
bsp_split($pat, $start_poly, MAX_PASSES);
/* This only needs to be done once, since the number of polygons isn't going to change. */
$pat->polys = count($pat->poly_list);
/* This is so painting methods should make no assumptions about polygon order. */
shuffle($pat->poly_list);
/* Build an image for the result. */
$image = imagecreatetruecolor(WIDTH, HEIGHT);
imagefilledrectangle($image, 0, 0, WIDTH - 1, HEIGHT - 1, $pat->color[0]);
/*
We want to draw a minimal border around each polygon (in the same
color). They sometimes end up with insufficient overlap and we want
to avoid 1-pixel lines of the background shining through.
*/
imagesetthickness($image, 2);
/*
Draw each polygon with its index as color (this really results in a
lot of dark blue shades). We will use these to detect which polygons
border each other. Check every corner of every polygon, with a
sample point just a few pixels outside. The color found there will
be the index of the polygon there, and the two polygons will be
marked as neighbours.
*/
draw_polygons($image, $pat, true);
foreach ($pat->poly_list as $i => $polygon)
{
$edges = count($polygon->vertex_list);
for ($e = 0; $e < $edges; $e++)
{
/*
We need to compare the (c)urrent corner to the (n)ext and
(p)revious and determine in which direction it's pointing.
For example, if the previous corner is to the right and the next
is below, it should be pointing northwest. This is the direction
we will place our sample point.
*/
$c = $polygon->vertex_list[$e];
$n = $polygon->vertex_list[($e + 1) % $edges];
$p = $polygon->vertex_list[($e + $edges - 1) % $edges];
$x_speed = 0;
$y_speed = 0;
/* NE, NW, SW, SE */
if ($n->x < $c->x) $x_speed++;
if ($p->y > $c->y) $y_speed--;
if ($p->x > $c->x) $x_speed--;
if ($n->y > $c->y) $y_speed--;
if ($n->x > $c->x) $x_speed--;
if ($p->y < $c->y) $y_speed++;
if ($p->x < $c->x) $x_speed++;
if ($n->y < $c->y) $y_speed++;
$c_nx = $c->x + $x_speed;
$c_ny = $c->y + $y_speed;
/*
To see where the sample points end up, enable this (and don't
redraw anything later!).
imageellipse($image, $c_nx, $c_ny, 3, 3, 0x00FF0000);
*/
/* Only check sample points that are within the map. */
if ($c_nx >= 0 && $c_nx < WIDTH &&
$c_ny >= 0 && $c_ny < HEIGHT)
{
$sample = imagecolorat($image, $c_nx, $c_ny);
/* If we got a valid index add it to the neighbour list. */
if ($sample < $pat->polys && $sample != $i)
{
array_push($polygon->neighbour_list, $sample);
array_push($pat->poly_list[$sample]->neighbour_list, $i);
}
}
}
}
/*
A polygon might have several corners pointing towards the same
neighbour, and these will have been duplicated in the neighbour
lists. Remove the duplicates.
*/
foreach ($pat->poly_list as $i => $polygon)
{
$polygon->neighbour_list = array_unique($polygon->neighbour_list);
}
/* Remove the color of all polygons */
for ($i = 0; $i < $pat->polys; $i++)
{
$polygon = $pat->poly_list[$i];
$polygon->color_index = FALSE;
}
/*
Go through every polygon, fill those that don't have a color. Color
bleed will usually fill more than one polygon (recursively), so the
further we get through the loop we are less likely to find empty
polygons and need to call it again.
*/
for ($i = 0; $i < $pat->polys; $i++)
{
$polygon = $pat->poly_list[$i];
if ($polygon->color_index === FALSE)
{
$start_polygon_index = $i;
color_polygon($pat, $start_polygon_index, rand() % count($pat->color), $pat->bleed_amount);
}
}
/* Draw the polygons again, with proper coloring. */
imagefilledrectangle($image, 0, 0, WIDTH - 1, HEIGHT - 1, 0x00FF0000);
draw_polygons($image, $pat, false);
/* Postprocessing */
$spots_to_add = $pat->spots;
while ($spots_to_add--)
{
/* Decide where to put this spot and how large it should be. */
$spot_x = rand() % WIDTH;
$spot_y = rand() % HEIGHT;
/* These can be either order. */
$spot_radius = min($pat->spot_radius1, $pat->spot_radius2)
+ rand() % (abs($pat->spot_radius1 - $pat->spot_radius2) + 1);
/* Pick a sampling point slightly off (usually) the spot center. Make sure it's on the canvas. */
$sample_x = $spot_x - $pat->spot_sampling + rand() % ($pat->spot_sampling * 2 + 1);
$sample_y = $spot_y - $pat->spot_sampling + rand() % ($pat->spot_sampling * 2 + 1);
$sample_x = max(0, min($sample_x, WIDTH - 1));
$sample_y = max(0, min($sample_y, HEIGHT - 1));
/*
Pick a color and draw it. Note: I've tried having different radii, it doesn't improve anything.
*/
$spot_color = imagecolorat($image, $sample_x, $sample_y);
imagefilledellipse($image, $spot_x, $spot_y, $spot_radius, $spot_radius, $spot_color);
}
/* If we don't want any pixelization we can skip this entirely. */
if ($pat->pixelize > 0)
{
/*
Calculate how large each "pixel" should be. read_options()
guarantees densities will be nonzero.
*/
$pixel_w = WIDTH / $pat->pixel_dens_x;
$pixel_h = HEIGHT / $pat->pixel_dens_y;
/*
Loop through each pixel. For each there is a random chance we
won't touch it (pixelization >= 100 guarantees all will be
touched). Sample a color slightly off the pixel center and draw
this as a filled rectangle.
*/
for ($x = $pixel_w / 2; $x < WIDTH; $x += $pixel_w)
{
for ($y = $pixel_h / 2; $y < HEIGHT; $y += $pixel_h)
{
if (1 + rand() % 100 > $pat->pixelize)
continue;
$sample_x = $x - $pat->pixel_sampling + rand() % ($pat->pixel_sampling * 2 + 1);
$sample_y = $y - $pat->pixel_sampling + rand() % ($pat->pixel_sampling * 2 + 1);
$sample_x = max(0, min($sample_x, WIDTH - 1));
$sample_y = max(0, min($sample_y, HEIGHT - 1));
$color = imagecolorat($image, $sample_x, $sample_y);
imagefilledrectangle($image,
$x - $pixel_w / 2, $y - $pixel_h / 2,
$x + $pixel_w / 2, $y + $pixel_h / 2,
$color);
}
}
}
/*
Flush the image. The if is for debug purposes.
*/
if (1)
{
header('Content-type: image/png');
imagepng($image);
}
imagedestroy($image);
?>