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.