Trees, Quil and Random

Last week I've been playing with random tree generation in Quil. Idea is simple: generate a tree that resembles a real tree and doesn't make you think that it was generated by computer. Suprisingly it's not that hard to do. Tree is represented as a collection of branches. A branch consists of 3 components: start point, angle (from 0 to 2π) and length. Each branch can have 0, 1 or 2 sub-branches. Algorithm for generating sub-branches from a branch:

1. Each branch can have up to 2 sub-branches. Probability of each sub-branch is 90%.
2. For each sub-ranch start point is calculated as end point of parent branch.
3. Sub-branch lengths are randomly selected from [0.7L, 1.0L], where L is parent's length.
4. Sub-branch angles are randomly selected from [α-¼π, α+¼π], where α is parent's angle.
5. Add sub-branches to the tree.

Now, having the function for generating sub-branches, tree generation is easy:

1. Create root: the first branch with angle ½π.
2. Branch-off each branch on previous level.
3. Repeat step 2 as many times as needed. My trees have 14 levels.
4. Concat all levels into single collection and draw them.

Last part is especially easy to do in clojure and each step corresponds to one line:

(defn generate-tree [root levels]
  (->> [root]
       (iterate #(mapcat branch-off %))
       (take levels)
       (apply concat)))

That's it. Now more trees!

White trees on black background look especially cool:

Quil tips

I've shown only static images of trees, but in reality they're animated so you can see how tree grows from a single root to a full tree with thousands of branches.

Initially I used a simple approach and was redrawing all branches on each frame. It works well when you have small number of branches but tree with 14 levels has 7000-10000 branches and drawing 10000 elements on each frame is well... slow. FPS drops from 60 to 10. So I optimized it a little, removed clearing background and changed draw-branch function to skip branches that are already fully drawn. That helped drastically bringing FPS back to 60. The big drawback that you can't do nice transformations now that may require redrawing everything. For example after tree is drawn I wanted to zoom into smallest branch and start drawing new tree from that branch, but it requires redrawing everything during zoom and I gave up this idea.

Another trick I did is around fading background color into tree color (see animations below). The idea is that screen background gradually turns to the same color as tree essentially clearing the tree. To achieve this the tree is drawn on a separate graphics object. Graphics object is transparent and when you copy it to main screen you can see background. With this technique draw function looks like the following:

(defn draw [state]
  ; Clear screen using calculated background screen. Background depends
  ; on tree state: if tree is fully drawn it gradually changes to match the
  ; tree color.
  (q/background (calculate-background-color state))

  ; Draw active branches on graphics object. Note that we don't erase
  ; existing branches, draw-tree only draws active branches. 
  (q/with-graphics (:buffer state)
    (draw-tree state))

  ; Copy buffer graphics to main screen.
  (q/image (:buffer state) 0 0))

And finally endless trees:

Controls (tree must have focus):

• r - regenerate tree;
• up/down - change number of levels;
• i - toggle stats;
• s - save as image (opens in new tab);

You can find source code on GitHub or try it online on quil.info.