Genuary 2021 Day 10: "Tree"

 

Trees! Who doesn't love trees! So many fractally things to do with trees. Like L-systems! Or fractals that look kind of like trees!

I decided to explore an algorithm I wasn't super familiar with, and whose output I didn't entirely like, and whose name I didn't entirely like. I chose the "Space Colonization" algorithm, which I saw on Coding Train: https://youtu.be/kKT0v3qhIQY

The basic idea is that you generate a pattern of "attractors" (referred to as "leaves" in the Coding Train video, but that's an error), and you grow your network of branches in the direction of the attractors. Each attractor exerts a "pull" on its closest tree branch node, and nodes with more than zero pulls branch off a new branch in the direction of the net pull. Add in some thresholds so that attractors shut off when a tree branch gets close enough, and you've got a pretty straightforward algorithm.

And, indeed, I got something working right away, but it wasn't fast enough for me. So I added quadtrees - which I realized, after I had them implemented and debugged, were more TREES. So, that's even better. There's a LOT of "find the closest <x> to the position of each <y>" going on in this algorithm, so having a spatial data structure to accelerate that made sense.

Giddy off of using spatial distance functions, I added SDFs to my quadtree implementation. There were two big queries that I did into my quadtrees:

• the closest object to this point
• all objects within <r> distance from this point

I was able to use the best distance so far along with the SDF of bounds of child quadtree nodes to quickly prune entire subtrees, and get a lot better performance - if the closest distance I had found so far was 100 units, and the closest point on the bounding box of a later subtree node was 120 units away, I'd know right away that I didn't have to look at any of the points in that subtree. Nice.

So, I got the quadtrees working - mostly? Seems like there were maybe a couple attractors that never got visited. Which I hacked around at first by just adding a count of how many attractors remained, and when that plateaued, I'd stop. Which was OK.

I added in a fancy flourish by adding a projection matrix so I could draw a shadow of the tree, too. Pretty.

And that was reasonably satisfying, until I went to draw it on the AxiDraw. I was getting a lot of tiny little branches, and the pen was jumping all around the tree. I had a bit of logic that would go from the end of a branch up to the root, but only draw branches that hadn't been drawn yet, so that eliminated overdraw at the root, and it gave the pen some longer paths when they were available, but I was starting from the ends of branches going in chronological order of when they had grown, not by any spatial ordering.

Spatial ordering? Aha! I've got a quadtree that I can use to order my branches, which helped keep the pen in one area better than before.

I also added in another hack where a branch could only have a bounded number of children. I picked 6, and the filesize of the generated SVG dropped from 1.2M down to something like 340k, which is a lot better.

I had spent ~35 minutes drawing the first version, before I grew frustrated with the crazy pen movements. The shadow wasn't complete after that time. After the above improvements, I  was able to draw the shadow and the tree in ~11 minutes.

There's still bugs in it - a lot of the circles seem to be drawn 6 times, indicating to me that something's wrong with marking the attractors as being visited. Is there a problem with my quadtree? I suspect probably, yes.

So. An algorithm I'm not a huge fan of, with perhaps the heaviest data structure I've used so far,  for results that are OK, and technical debt besides, if I want to reuse this quadtree class. ::ThumbsUp::

I'd kind of like to get this sorted out and use it to render 3d trees. But I'd need to have a good solid spatial structure for my ray marcher, because it's slow, too.

Tools Used: Pentel pen, printer paper, AxiDraw Mini

Languages Used: Python

Development Time: ~5 hours? I did a chunk in the morning, and then another chunk in the afternoon. It was basically working before I added in the quadtrees, which, I'm sure, doubled the development time.

Drawing Time: ~11 minutes on the plotter (with the v2 optimizations described above), ~2 minutes to generate the SVG.

What's Generative Here: The attractor nodes are randomly placed inside an ellipse of my choosing. The attractor nodes indirectly control the growth of the branches.

This is the abandoned v1 drawing - note a lot of super fine branches.

V2 - shadow drawn, tree in process.

Tree, Shadow against blue background. The shadow might make you want to believe it's 3d, but it's really a 2d shape drawn twice, with a projection to make it look like a shadow.

Genuary 2021 Day 9: "Interference Patterns"

 

One of the first two places my brain went when I was considering "Interference Patterns" was the double slit photon experiment, and the simpler version of that that we did in high school physics (shout out to Mr. Pearson, my physics teacher, and Troy and Becky, my lab partners).  The simpler version was done in a shallow basin of water, with two periodic ripple generators. It's pretty much what's explained here: https://www.physicsclassroom.com/class/light/Lesson-1/Two-Point-Source-Interference

The other thought I had was some sort of Moiré pattern: https://en.wikipedia.org/wiki/Moir%C3%A9_pattern

So, I made two drawable objects, one which made an expanding ripple pattern, and one which made a rotating starburst of rays. I made two of each, and put all of the drawables on their own lissajous curves (which feels sort of interference-y in a different way; complex motion from two sine waves not in sync).

I drew a bunch of frames of this, which I made an animated GIF of, and the above YouTube video, and I also drew one frame out on my AxiDraw. I don't know how easily consumed each is - I like to think that the best version of this is the animated GIF, but the others are probably more accessible.

Genuary 2021 Day 8 (completed one day late) "Curve Only"

 

I had a lot of ideas about how to approach this prompt. I ended up writing only half as much code as I intended to, but it came out really well. I have ideas of where I would like to revisit and expand, but once I saw this, I decided to step away, plot it, and call it good.

I'm going to call this a "flow field" drawing, but there may be other technical terms for it - I remember seeing drawings like this as I was learning Differential Equations.

First thing I did was to generate an irregular grid of points using Bridson's algorithm (see http://extremelearning.com.au/an-improved-version-of-bridsons-algorithm-n-for-poisson-disc-sampling/ and https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf for fast blue noise random grid generation). For each point, I generated a unit vector in a random 2d direction. I then did 10 iterations of smoothing, letting each vector be replaced by a normalized sum of the vectors within 60 units. I called this smoothed set of vectors my "flow grid". Or, you could consider it the velocity as a function of position.

I wrote a function to sample this flow grid, not just at the grid points, but averaging over all the points within a radius. Here, 40 units. I then started a path at each of my initial grid points, stepping in the direction of the flow grid for up to 100 steps, or until I ran off the page.

I count 4 "whorls" that would attract the pen and never release it. I think if I draw more works in this style, I'll do a "capture detection" or density limit. For "capture detection", I'd check to see if the pen has spent the past <n> steps within <m> radius. If the pen has been captured, stop drawing the line. For "density limit", I'd keep a record of points along the path. If there are more than <n> points already drawn withing <m> radius of the pen, stop drawing the line. This would also decrease the likelihood of having a lot of parallel paths overlapping too near to each other. Both of these would change the look of the finished work a little - I'd want to try a few values to see if I like what I come up with.

Other experiments I'd like to try:

• generate the position grid and flow grid, as described above, but when drawing, choose a subset of the page to use as path starts. Maybe points left of a line - it occurred to me that if you have a "horizon"  below one of the whorls, you might draw something like Hokusai's "Great Wave off Kanagawa". Another thing to try would be to try only starting from points within a circle.
• draw fewer lines, but for each start point, draw several lines with an angular offset from the flow grid. This would lead to some interesting spiraling curves, I suspect.
• multiple colored pens - I'd want to generate a couple different SVGs, and then swap pens to make the next layer.

Tools Used: Pentel pen, printer paper, AxiDraw Mini

Languages Used: Python

Development Time: ~2 hours over two days (hard time sleeping. I blame insurrectionists.)

Drawing Time: ~105 minutes

What's Generative Here: The position grid is generated randomly using a blue noise algorithm. For each node in  the position grid, I generate a "flow" vector of unit length and random direction. I then proceed to "smooth" this flow grid by averaging flow vectors with their neighbors. The colors in the SVG are selected by starting with red, and then adding a fixed amount of red, green, and blue, wrapping around when out of gamut, for each path. This is intended to give a coverage of the RGB space, a little like sunflowers use 1/phi for each successive petal, leading to golden ratio spirals.

Genuary 2021 Day 7a: "Rules by Hand"

 Ok, revisiting the prompt for today, which reads:

"Generate some rules, then follow them by hand on paper."

I don't feel like my previous piece really lived up to that first word - and, in so doing, I missed perhaps the most important part.

So, I started over.

I generated some rules this time, from a small list of nouns and a handful of templates. The generated rules ended up:

next to each yellow star with no adjacent purple moon, place one blue waves

fill all spaces next to red circle with green diamond

place one purple moon next to each green diamond

find a space adjacent to green diamond and green diamond. Place a blue waves there.

next to each blue waves with no adjacent blue waves, place one green diamond

find a space adjacent to purple moon and blue waves. Place a yellow star there.

find a space adjacent to purple moon and purple moon. Place a purple moon there.

find a space adjacent to blue waves and blue waves. Place a green diamond there.

place a blue waves next to a green diamond

fill all spaces next to blue waves with green diamond

next to each red circle with no adjacent purple moon, place one red circle

place a yellow star somewhere

And I did this over and over again, until I couldn't. (Actually, I missed a spot, so you can finish the work, if you like.)

The red circles in the rules never had an opportunity to be generated, which I'm sorry about. Maybe next time, I'll seed with a few red circles.

Purple moons definitely provided an "insulating" layer - they would spawn outside of green diamonds, and then not spawn anything but other purple moons. 

Yellow stars would generate blue waves,  which would generate another yellow star, and so we get double stars.

Neat little patterns.

Tools Used: Gel pens, hex grid graph paper

Languages Used: Python

Development Time: ~2 minutes

Drawing Time: ~60 minutes (I was also watching Star Trek: Discovery)

What's Generative Here: The rules were generated. I had a certain amount of freedom to pick things, which made me a randomizing agent within the rules. I was tempted to try to steer the growth, but I kept forgetting what patterns I was trying to set up.

Genuary 2021 Day 7: "Rules by hand"

 

Some sort of space filling road network, maybe?

For this, I decided that I would make a network of connected nodes. My rules, which I sometimes failed to follow exactly, sometimes adapted for conditions I hadn't anticipated:

1. Roll D6 for number of exits

2. Go clockwise, rolling d6 checking if that number is equal to or over the number of exits remaining

3. Roll D6 for distance from those exits

4. Go to 1

Not specified is how to start. So I just picked a center-ish hex on some hex graph paper I had lying around. (You don't have blank hex graph paper within arm's reach? I don't know how you even live.)

I rolled a 2, which led me to two exits from the starting hex. That made a cute little macaroni elbow to begin things. I rolled the distance that each exit would go from the starting hex, got a 2 and a 5 in order, which I drew as tubes or roads or pipes or ganglia.

For each node, I'd roll to see how many exits to open up out of the hex. If the roll was over the amount of available directions to go, or under the number of exits already opened to that hex, then I'd clamp to the facts on the page. To determine which exits to open, I'd roll a d6 for each direction, and open an exit if the roll was less or equal to the number of exits remaining. If the number of exits available on the page were equal to the number of exits that I was supposed to roll, I'd skip rolling, and just fill in the remainder. This isn't exactly balanced, as when there's two sides of the hex remaining, and 1 exit to allocate, the rule says to roll d6, and on a 1 open the first exit, and therefore on a 2-6, you don't open the first exit, but implicitly you must open the last exit. So, this could be reshaped some.

Sometimes, I'd roll that a node has one exit, and that node would already have a road leading up to it, so that's a dead end.

Sometimes, the road would be specified to meet up with (or go through) an open node. In this case, I'd allow the road to meet up with the open node (but not go through, unless the exit rolls said so later). If a road was supposed to go off the page, or meet an existing road, I'd go as far as I could and place a node at the last empty hex.

Several bits of judgement involved - I think I could come up with a v2 of the rules that explain my interpretations of the edge cases.

I'd kind of like to code this up as a street map and drive a car around on it in a computer game.

I'd also kind of like to code this up and generate city street maps - maybe allowing roads to meet each other. Generating buildings on nearby lots would be cool.

Tools Used: Pencil, hex grid graph paper, Chessex Purple with White Translucent D6

Languages Used: English?

Development Time: ~2 minutes

Drawing Time: ~30 minutes

What's Generative Here: At every step, the network expands in a way determined by a random process implemented by a die. 

Genuary 2021 Day 6: "Triangle Subdivision"

This prompt sent me back to copying BASIC programs out of the old "Creative Computing" magazine on our family's Apple II. I dimly recall keying in a program that divided a triangle recursively, giving a heightfield. Our Apple II had 64 kilobytes of RAM, which a good chunk was given over to DOS and the BASIC overhead, so there wasn't a lot of room for fancy data structures or very complicated geometry. Then again, the hi-resolution graphics screen was 280x192 pixels, or less if you were picky about color.

This is a throwback to the output of that program, even though I only recall the basic algorithm. I pick random elevations for the corners of the triangle, and then subdivide the triangle up into four sub-triangles of half the width, and perturb the new vertices based on the parent triangle's vertices. This is similar to the "Diamond/Square" terrain generation algorithm.

After creating a triangular heightfield, I generate lines by projecting each x,y,z world point into a sx, sy point on the page. To honor the hacky BASIC program, I did this by multiplying each x, y, z component by a vector I thought would look nice. No matrix multiplies, per se, no look-vectors. I could rewrite this to use that, but meh.

Another thing this doesn't have is colors (the flat part to the right is maybe water, which could be blue), which would lead me to break my paths into zero or more land parts and zero or more water parts, which could totally be done, but again meh - especially since I was planning to draw this on my AxiDraw, which I wasn't going to load different pens into, so monochrome it is.

And still one more thing that this could have, but doesn't, is hidden surface elimination. I think the original Apple II program implemented this by retaining an array in screen-x that remembered the highest value that had been drawn at that value of X, thus not going "beneath" the horizon. I've used this many times before, I refer to it as "The Joy Division Algorithm". I could do something like that here, but since I'm dealing in a bigger space than the Apple II was, I'd want to do my clipping against the vector path information, rather than some quantized pixel positions. Again, this particular seed value doesn't benefit from this, so I skipped it.

Tools Used: AxiDraw, DrawSVG

Languages Used: Python3

Development Time: ~90 minutes

Drawing Time: ~3 minutes

What's Generative Here: The heightfield is generated using RNG. This might have been the first generative algorithm I ever played with, as a kid.

Genuary 2021 Day 5: "Code Golf"

The full prompt text is:

Do some code golf! How little code can you write to make something interesting? Share the sketch and its code together if you can.

I pushed myself to make something small, but without taking a lot of time to make it smaller than my first working version. I started with a version that just printed a string to the console:

which outputs this:

                  🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲  🏌             ⛳                                  🌳🌳🌳🌳🌳🌳🌳           🌴🌴

(depending on how good your Unicode support is)

I then extended that to output a PNG:

Which takes the previous code's output and renders it to a PNG using PIL and a Unicode font. Not minimal, but relatively tight.

Tools Used: um, Unicode?

Languages Used: Python3

Development Time: ~90 minutes

What's Generative Here: I place 3 different forests of size and position specified by a random number generator. I then place the golfer and hole at random places.