Fractal Plants

Originally posted 2014-05-01

Tagged: computer_science

Obligatory disclaimer: all opinions are mine and not of my employer


I’ve been pretty curious about 3D graphics for a while, so I finally checked out Udacity’s 3D graphics class, which was a very well-taught course.

The basics work out something like this:

  • Triangles exist in 3-dimensional space.
  • In conjunction with a light source, a camera, and some vector math to calculate reflection/illumination, the image captured by a virtual cross-section can be computed.
  • The computed image can then be rasterized / rendered to screen - ultimately, the result is a series of colored pixels.
  • Nobody uses triangles directly; for example, you can call THREE.SphereGeometry(radius, latitude_resolution, longitude_resolution) to create a mesh of appropriately placed triangles at desired fineness. Other useful primitives exist, like rectangular prisms, toruses, spline extrusions, and cylinders.
  • Meshes are wrapped in THREE.Object3D(). Objects can be added as children to each other, and their relative orientations specified.
  • Rotation, scaling, and translation operations are applied hierarchically/recursively throughout the entire tree of objects, so that complex objects can be manipulated with respect to each other without much difficulty.

The combination of these ideas suffices to implement this fractal tree generator.

Tree Generator goes here. WebGL/THREE.js might not work on your browser. (Only seems to work on Chrome on my machine.)

I found the quaternion/affine transformation approach to manipulating vectors/points mind-blowing. Think first about how one would represent rotations and scaling operations with matrices. Seems pretty easy - an orthogonal matrix is a rotation, and a diagonal matrix scales in the directions as according to the numbers on the diagonal. Now, how would you represent translations as a matrix? You can’t; they’re not linear. But instead of multiplying n-vectors by nxn matrices, you can instead multiply (n+1)-vectors by (n+1)x(n+1) matrices, and the extra ‘space’ suddenly allows you to represent translations as matrices (subject to constraints that help evade the nonlinearity issue). All graphics cards use this convention and optimize heavily for multiplication of 4x4 matrices.

This ultimately means that the operation of creating a branch (with subbranches), and rotating it, is extremely simple. Each level of nesting simply concatenates another translation, scaling, and rotation matrix to the list of transforms.

On the coding side, this was my first time writing a significant piece of javascript, and my general impression of the language is that javascript sucks and is horribly designed. But we all knew that anyway. I think the saving grace of javascript is that it has top-notch support for functions. This alone means that essentially, anything you could have done in a functional language, you can reimplement in javascript, work with those tools, and ignore the crappiness of the rest of the language. My final code made abundant use of functions and the simplest possible objects, and I’m pretty happy with it.

I experimented with implementing my program using fancier JS constructs, but quickly ran into the issue that the class / inheritance system for Javascript is extremely hacky and there are all sorts of workarounds for the lack of proper inheritance. See this hilarious discussion on the simple act of copying an object. I even ended up using the horrible clone = JSON.parse(JSON.stringify(dict)) at one point. I suppose that copying objects is inherently a tricky business, but at least Python attempts to address it by providing copy and deepcopy handles to implement. Another limitation I quickly ran into was the amorphous boundaries between what is an object, what is a function, and what is an array.

This being said, Javascript has a really vibrant community of open-source code. THREE.js obviously takes center stage, underscore.js made me praise the gods, and where else would I be able to find such a simple drag-and-drop solution to creating a GUI?

Anyway, enough blabbing - twiddle with the tree and share if you stumble on something unusual! The parameter space is not very large, and I hope to create a more ‘natural’-looking fractal tree generator at some point.