Ages ago, 2006 or so, I came across a small book, Pamphlet Architecture 27: Tooling by Benjamin Aranda and Chris Lasch. It described several generative, parametric systems. One of the recipes is shown here, cracking.
In this post we’ll build a generative system in Processing to explore the idea. The end result is: https://winterbloed.be/code/triangle.zip.
Except for the initial shape, everything seems to be made up of triangles. Remember from Li(n)e, Processing has a command line() but has no idea what a line is. Same goes for triangle(). We need to add the triangle concept ourselves. Taking the usual approach:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Point { float x, y; Point(float x, float y) { this.x=x; this.y=y; } } class Triangle { Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) { this.p1=new Point(p1.x, p1.y); this.p2=new Point(p2.x, p2.y); this.p3=new Point(p3.x, p3.y); } void draw() { fill(240); stroke(0, 80); triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } } |
Starting off
In this case we decide to start from an equilateral triangle.
For that we need the coordinates of the corner points. With some looking around we’ll undoubtedly find these online but let’s take a different approach.
|
1 2 3 4 |
Point p1=new Point(0, radius); Point p2=p1.rotate(radians(120)); Point p3=p1.rotate(radians(240)); Triangle start=new Triangle(p1, p2, p3); |
What is this p1.rotate()? Imagine that we create the first point p1 of our triangle vertically at some distance radius from the origin, (0, radius). If we rotate this point around the origin by 120° we end up at the second point, another 120° takes us to the third point. A third rotation by 120° gives us a full turn and we get back to the first point.
Rotating a point around the origin in 2D is something that might have come up in our math curriculum, definitely something with sines and cosines. Let’s look it up, nobody expects us to know this from heart (now). With some digging, and ignoring ominous looking matrix notations and trigonometric derivations, diagonally scanning Wikipedia and Stack Overflow we find something that looks like the right thing.
x_{rotated}=x.cos(angle)-y.sin(angle)
y_{rotated}=x.sin(angle)+y.cos(angle)
Let’s build that into our Point.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Point { float x, y; Point(float x, float y) { this.x=x; this.y=y; } Point rotate(float angle) { float ca=cos(angle); float sa=sin(angle); float rotx=ca*x-sa*y; float roty=sa*x+ca*y; return new Point(rotx, roty); } } |
Calling p1.rotate(angle) will return a new Point, p1 rotated about the origin over the specified angle. Trigonometry functions expect their angles to be in radians, but sometimes it’s easier for us to think in degrees. So rather than p1.rotate(2*PI/3.0), I prefer p1.rotate(radians(120)).
That will give us our starting triangle. As our cracking progresses, we’ll need a list to store our ever-growing collection of new triangles. In the beginning that list is empty except for the single triangle start.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
Triangle start; ArrayList<Triangle> triangles; void setup() { size(1000, 1000, P3D); smooth(16); create(); } void create() { float radius=450; triangles=new ArrayList<Triangle>(); Point p1=new Point(0, radius); Point p2=p1.rotate(radians(120)); Point p3=p1.rotate(radians(240)); start=new Triangle(p1, p2, p3); triangles.add(start); } void draw() { background(15); translate(width/2, height/2-100); for (Triangle triangle : triangles) { triangle.draw(); } } void subdivide(){ //TO DO } void mousePressed(){ //TO DO } class Point { ... } class Triangle { ... } |
Subdivision
Writing an iterative subdivision sketch for the first time can be confusing. After all, we’re starting with a single triangle, after a first division we’ll have several more. In the second iteration we want to subdivide those new triangles but not the first, and so on.
My favorite method is like this:
|
1 2 3 4 5 6 7 8 9 10 11 |
void subdivide() { ArrayList<Triangle> subTriangles=new ArrayList<Triangle>(); for (Triangle triangle : triangles) { //subTriangles created here subTriangles.add(subTriangle1); subTriangles.add(subTriangle2); subTriangles.add(subTriangle3); } triangles=subTriangles; } } |
Key feature is that while we are going through triangles, we’re not adding anything to it. In fact, this would result in an error, ConcurrentModificationException. Modifying a list we’re iterating over is rarely a good idea anyway. Especially when adding things to the end of the list it’s easy to create a piece of code that will never end. We don’t have enough time for infinity.
We solve this by storing the new subdivided triangles in a fresh new list every iteration. Once we finish going through triangles, we discard it by overwriting it with the new list subTriangles. That way we go into the new round with only the latest generation of subdivisions.
We skipped over the triangle subdivision itself. The recipe in Tooling calls for creating a new triangle by connecting every side with a center point inside the shape. We add a function to our Triangle that returns a point inside, in this case the average of the corners, the centroid:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Triangle { Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) { this.p1=new Point(p1.x, p1.y); this.p2=new Point(p2.x, p2.y); this.p3=new Point(p3.x, p3.y); } void draw() { fill(240); stroke(0, 80); triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } Point pointInTriangle(float f) { return new Point((p1.x+p2.x+p3.x)/3.0, (p1.y+p2.y+p3.y)/3.0); } } |
We add everything together and we have the first version of our iterative subdivision, cracking sketch.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
Triangle start; ArrayList<Triangle> triangles; int MAX_ITERATIONS; int iterations; void setup() { size(1000, 1000, P3D); smooth(16); iterations=0; MAX_ITERATIONS=12; create(); } void create() { float radius=450; triangles=new ArrayList<Triangle>(); Point p1=new Point(0, radius); Point p2=p1.rotate(radians(120)); Point p3=p1.rotate(radians(240)); start=new Triangle(p1, p2, p3); triangles.add(start); } void draw() { background(15); translate(width/2, height/2-50); for (Triangle triangle : triangles) { triangle.draw(); } } void subdivide() { if (iterations<MAX_ITERATIONS) { iterations++; ArrayList<Triangle> subTriangles=new ArrayList<Triangle>(); Point p1, p2, p3, pc; for (Triangle triangle : triangles) { p1=triangle.p1; p2=triangle.p2; p3=triangle.p3; pc=triangle.pointInTriangle(); subTriangles.add(new Triangle(p1, p2, pc)); subTriangles.add(new Triangle(p2, p3, pc)); subTriangles.add(new Triangle(p3, p1, pc)); } triangles=subTriangles; } } void mousePressed() { subdivide(); } class Point { float x, y; Point(float x, float y) { this.x=x; this.y=y; } Point rotate(float angle) { float ca=cos(angle); float sa=sin(angle); float rotx=ca*x-sa*y; float roty=sa*x+ca*y; return new Point(rotx, roty); } } class Triangle { Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) { this.p1=new Point(p1.x, p1.y); this.p2=new Point(p2.x, p2.y); this.p3=new Point(p3.x, p3.y); } void draw() { fill(240); stroke(0, 80); triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } Point pointInTriangle() { return new Point((p1.x+p2.x+p3.x)/3.0, (p1.y+p2.y+p3.y)/3.0); } } |
Great! Two things of note. One, iterative subdivision grows very quickly. Here every triangle is replaced by 3 triangles, so the total number is multiplied by 3 every cycle. 1, 3, 9, 27, … after only 10 iterations we’re almost up to 60000, 20 iterations and we’re at 3.5 billion. It’s not a bad idea to save ourselves a forceful exit by limiting the number of iterations.
Secondly, every time we run the code, the result will be identical. Time to add some variety.
Variations
One way is to create a random point inside the triangle rather than use the centroid. For example, we can generalize our current equation
p=({\frac 1 3}x_{p1} + {\frac 1 3}x_{p2} + {\frac 1 3}x_{p3}, {\frac 1 3}y_{p1} + {\frac 1 3}y_{p2}+ {\frac 1 3}y_{p3})
to
p=({a}x_{p1} + {b}x_{p2} + {c}x_{p3}, {a}y_{p1} + {b}y_{p2} + {c}y_{p3})
with a,b and c random positive numbers (or zero). An additional condition is that their sum should be 1. Where does this come from? It’s not something that I would likely come up with myself. But when snooping around for something completely else, I came across barycentric coordinates, a way of describing the position of a point in a triangle in relation to its three corner points. Turns out that for every point inside a triangle we can find exactly one unique a,b and c combination, and that their sum is always 1. Conversely, if we make up such a combination that should give us a point in the triangle.
When I came across barycentric coordinates, I didn’t know we could use it for something like this. It was just one of the many odds and ends we picked up along the way. Creative coding is McGyvering our way through the challenges.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Triangle { Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) { this.p1=new Point(p1.x, p1.y); this.p2=new Point(p2.x, p2.y); this.p3=new Point(p3.x, p3.y); } void draw() { fill(240); stroke(0, 80); triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } Point pointInTriangle() { float a,b,c; do{ a=random(1.0); b=random(1.0); }while(a+b>1.0); c=1-a-b; return new Point(a*p1.x+b*p2.x+c*p3.x, a*p1.y+b*p2.y+c*p3.y); } } |
Instead of fixing the centroid, we’re generating random pairs of a and b. c is fixed by the condition that the sum has to be 1. If the sum of a and b turns out to be larger than 1, there’s no room left to create a positive c, so we re-roll until we find a suitable pair.
Definitely more random, but maybe too random? Is there a way to tune the amount of noise, to find some goldilocks zone of randomness? In this case I tackled it by considering that in our first version a, b and c are always 1/3. And in the second, fully random version, they’re some number between 0 and 1. What if we could mix these together. No randomness would give us 1/3, full randomness would give us the randomly generated value, and something in-between would interpolate.
This modification does just that.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Triangle { Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) { this.p1=new Point(p1.x, p1.y); this.p2=new Point(p2.x, p2.y); this.p3=new Point(p3.x, p3.y); } void draw() { fill(240); stroke(0, 80); triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } Point pointInTriangle(float f) { float a,b,c; do{ a=random(1.0); b=random(1.0); }while(a+b>1.0); a=1.0/3.0+f*(a-1.0/3.0); b=1.0/3.0+f*(b-1.0/3.0); c=1-a-b; return new Point(a*p1.x+b*p2.x+c*p3.x, a*p1.y+b*p2.y+c*p3.y); } } |
pointInTriangle() now takes an additional parameter f, randomness. If this is 0, the rolled values don’t matter, a, b and c are always 1/3. If it is 1, the rolled values of a and b are kept. Anything in-between interpolates, with higher values adding more of the random factors into the result.
Take care not to use 1/3 instead of 1.0/3.0. Both 1 and 3 are integers and 1/3 will be interpreted as an integer division and will equal 0! 1.0/3 or 1/3.0 would work fine too.
More
Another way to introduce variation is to relax the rule that every triangle has to be subdivided every iteration. Maybe some can escape annihilation. We add an additional parameter CHANCE and tweak the subdivide() logic.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void subdivide() { if (iterations<MAX_ITERATIONS) { iterations++; ArrayList<Triangle> subTriangles=new ArrayList<Triangle>(); Point p1, p2, p3, pc; for (Triangle triangle : triangles) { float roll=random(100.0); if (roll<CHANCE) { p1=triangle.p1; p2=triangle.p2; p3=triangle.p3; pc=triangle.pointInTriangle(RANDOMNESS); subTriangles.add(new Triangle(p1, p2, pc)); subTriangles.add(new Triangle(p2, p3, pc)); subTriangles.add(new Triangle(p3, p1, pc)); } else { subTriangles.add(triangle); } } triangles=subTriangles; } } |
When going through the triangle list, each triangle gets a roll, when it’s lower than CHANCE, it’s divided and discarded. When it rolls higher, it is saved and allowed to stay another round. Since we’re throwing away the original triangles list at the end, we have to add the saved triangle to the subTriangles list. Otherwise, we’ll get holes where parts go missing – which can be interesting.
The entire thing (https://winterbloed.be/code/triangle.zip):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
Triangle start; ArrayList<Triangle> triangles; int MAX_ITERATIONS; int iterations; float RANDOMNESS; float CHANCE; void setup() { size(1000, 1000, P3D); smooth(16); iterations=0; MAX_ITERATIONS=16; RANDOMNESS=0.0; CHANCE=100; create(); } void create() { float radius=450; triangles=new ArrayList<Triangle>(); Point p1=new Point(0, radius); Point p2=p1.rotate(radians(120)); Point p3=p1.rotate(radians(240)); start=new Triangle(p1, p2, p3); triangles.add(start); } void draw() { background(15); translate(width/2, height/2-50); for (Triangle triangle : triangles) { triangle.draw(); } } void subdivide() { if (iterations<MAX_ITERATIONS) { iterations++; ArrayList<Triangle> subTriangles=new ArrayList<Triangle>(); Point p1, p2, p3, pc; for (Triangle triangle : triangles) { float roll=random(100.0); if (roll<CHANCE) { p1=triangle.p1; p2=triangle.p2; p3=triangle.p3; pc=triangle.pointInTriangle(RANDOMNESS); subTriangles.add(new Triangle(p1, p2, pc)); subTriangles.add(new Triangle(p2, p3, pc)); subTriangles.add(new Triangle(p3, p1, pc)); } else { subTriangles.add(triangle); } } triangles=subTriangles; } } void mousePressed() { subdivide(); } class Point { float x, y; Point(float x, float y) { this.x=x; this.y=y; } Point rotate(float angle) { float ca=cos(angle); float sa=sin(angle); float rotx=ca*x-sa*y; float roty=sa*x+ca*y; return new Point(rotx, roty); } } class Triangle { Point p1, p2, p3; Triangle(Point p1, Point p2, Point p3) { this.p1=new Point(p1.x, p1.y); this.p2=new Point(p2.x, p2.y); this.p3=new Point(p3.x, p3.y); } void draw() { fill(240); stroke(0, 80); triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } Point pointInTriangle(float f) { float a, b, c; do { a=random(1.0); b=random(1.0); } while (a+b>1.0); a=1.0/3.0+f*(a-1.0/3.0); b=1.0/3.0+f*(b-1.0/3.0); c=1-a-b; return new Point(a*p1.x+b*p2.x+c*p3.x, a*p1.y+b*p2.y+c*p3.y); } } |
