Monday, April 27, 2009


Wild Beasts - Brave Bulging Buoyant Clairvoyants. Dir: OneInThree from OneInThree on Vimeo.

The endlessly inventive directing duo oneinthree last year produced a visually scrumptious music video which uses the Droste effect with hypnotic results. Dudes are on their way to the big time, recently producing their first big budget commercials in Europe.

I was inspired to create a realtime version of the effect which can be downloaded here. Only for mac, currently, though if the people clamour for it, I'll recompile for windows.

Update: Here's the PC version! Unzips to a directory containing droste.exe. With any luck you have all the required dependencies. Drop me a line at kevin dot atkinson at gmail dot com if you have issues.

Update:Some Windows users may have to install the VC runtimes.

Almost forgot to mention: if you are running the app, press 'f' for fullscreen, 'w' to return to a window, and 'esc' quits.

Update:I haven't had time to do a full source release, since it is going to require a lot of time for clean up, and putting together a build, since the source files are scattered among different libraries I use. Short of that, here's a link to the file that contains the rendering code, for them as are interested in such things. There's a nice article by Jos Leys explaining the math here.

Monday, April 13, 2009



I needed code for the 2D and 3D distance transform (for my dendrogen toolkit), and the only thing I could find used ITK -- lovely toolkit, but that's a big dependency I didn't want to drag in. I looked up the algorithm, and it turns out it's dead simple.

Curious thing about the distance transform is that approximate algorithms have been around for a while, but so far as I can tell, an efficient (linear in the number of pixels) and exact algorithm was only devised in 2004, by Messrs. Felzenszwalb & Huttenlocher. Their solution is also beautifully simple. The paper contains pseudocode which can be directly translated into C.

The above pic is a slice through a 3d distance transform of a set of points, and the corresponding 3d voronoi diagram.

I added the ability to optionally generate voronoi regions. The code mostly tests with points, but it will work with arbitrary regions as well. It's a VC Express project, but the code is all portable. The test code uses OpenCV just to display results, but the distance transform code itself is in a single header and has no dependencies beyond the C++ standard library.

If you look at the code, you'll notice an OpenMP directive, which sped things up by about 25% on my slow-but-dual-core laptop. The tiny amount I know about OpenMP is from a Doctor Dobb's article I read years ago, so I don't know if I'm using it correctly, except to say that the results appear correct, and it did indeed make it go faster.

Thursday, April 02, 2009



I'm currently making a open source software toolkit for procedural tree generation called dendrogen (I figure every open source project needs a catchy name ;-)

My plan is to create efficient, practical implementations of promising tree generation algorithms, ready for incorporation into modern CG pipelines. So far I've implemented the algorithm from Runion et al's paper Modeling Trees with a Space Colonization Algorithm, and I'm half-way through an implementation of the algorithm in Rodkaew et al's Particle Systems for Plant Modeling.

I currently have no plans to implement L-systems, since 1) it seems that despite their extraordinary power for compactly describing rich plant geometries, they are not very directible -- it's hard for an artist to end up with a tree of a desired target geometry; and 2) I believe there are already well-developed tools in that area. My hope with the tool I am building is that it will be the center of a artist-centric tool that will permit interactive sculpting of foliage envelopes.

If I'm wrong about L-systems, please let me know.

The first phase of the project is to create high quality, well-documented and thoroughly tested C++ implementations, together with python wrappers that will be written in tandem.

The next phase will be creating tools for generating the geometry of the tree itself, using the skeleton generated by the code in the first phase. The tentative plan at this point is use implicit surfaces.

The attached screenshot is from Maya, but there is no Maya dependency in the code.

I'm currently leaning towards an LGPL license. If you would like a snapshot of the current code, let me know (kevin.atkinson at the domain gmail.com).