Source Code for Quaternion Julia Set Shape Optimization

Proceedings of Symposium on Geometry Processing (SGP) 2015

Theodore Kim
University of California, Santa Barbara
Media Arts and Technology Program

Download the source here


This is the source code release for the SGP 2015 paper Quaternion Julia Set Shape Optimization. The original source code was written for Mac OS X, used Apple's LAPACK implementation, and the Toolkit for Advanced Optimization (TAO), which depends on the PETSc library. These dependencies made the code hard to run on other systems and hard to compile because PETSc is a very heavyweight library.

Both of these dependencies have been removed in this release. The LAPACK calls have been replaced with Eigen, and I have created a stripped version of TAO called "Toupee" that does not need PETSc (Toupee = TAO W/O PETSc). This means that simply calling make should build everything right out of the box without the need to install anything. This has been tested on both OS X (Snow Leopard, Mountain Lion), as well as Ubuntu 12. The bad news is that the underlying optimization is very numerically sensitive, and using these other packages does not produce the exact same shapes as in the paper, but instead, something close.

There is one dependency I was not able to remove, which is the BEM++ library. Porting this in a dependency-free way was not feasible. Instead, I have provided several different usage levels: Beginner, Intermediate, and Advanced. You will only need BEM++ if you want to use this code at the advanced level, i.e. compute the Julia set for a totally new shape. At no point do you need to have BEM++ installed in order to compile this code. If it is needed, it is invoked via a system call.



Installation should be straightforward. Once you have downloaded the code (above), uncompress it, go into the directory QUIJIBO, and invoke make. If the build is successful, in the directory QUIJIBO/bin, you should see the files:

  • bemWrapper
  • cubature
  • marchingCubes3D
  • objToGmsh
  • poissonDisk
  • sdfGen
  • toothOptimizer
  • rosenbrock

Usage: Beginner

At this usage level, you can generate some of the shapes from the paper using optimizations that have already been run for you. Thus, you should be able to obtain the exact same shapes as in the paper. The program to run is marchingCubes3D, and it takes the following arguments:

      marchingCubes3D (input file) (grid resolution) (max recursions) (output OBJ)

The arguments are:

  • (input file): This should be a *.o3d file, i.e. a saved OPTIMIZE_3D object. This file contains the root positions and powers of the optimized rational function.
  • (grid resolution): This is the resolution of the grid for marching cubes. E.g. for the setting 100, a 100 x 100 x 100 grid will be generated containing Julia set values, and marching cubes will be run on it.
  • (max recursions): This is the maximum number of recursions that the rational function will be allowed to compute. Setting it to 1 will give a smooth shape, while setting it to higher values produces rougher, more fractal shapes. Due to the numerical sensitivity of the algorithm, setting it to values higher than 3 can produce unpredictable results.
  • (output OBJ): The filename that you would like to write the final OBJ mesh to.
Some example invocations:

      ./bin/marchingCubes3D ./data/bunny_5000.o3d 300 3 ./data/bunny_5000.obj
      ./bin/marchingCubes3D ./data/frog.1379.o3d 100 3 ./data/frog.1379.obj

Many of the original *.o3d files from the paper are available to be marched in the QUIJIBO/data directory.


Usage: Intermediate

At this level, you can use cubature to generate the initial guess and then run the non-linear optimization. All of the non-trivial components of the algorithm, except for the BEM solve, are included at this level. The toolchain is as follows:

      ./bin/sdfGen ./cfg/tooth.cfg
      ./bin/poissonDisk ./cfg/tooth.cfg
      ./bin/cubature ./cfg/tooth.cfg
      ./bin/toothOptimizer ./cfg/tooth.cfg

The first stage, ./bin/sdfGen, normalizes the mesh to a unit cube, and calls Chris Batty's SDFGen code to generate a signed distance field of the normalized mesh. The second stage, ./bin/poissonDisk, will generate 10,000 blue noise points along the surface of the target shape using vcglib. The third stage, ./bin/cubature, will select a subset of these points to use as an initial guess and assign appropriate weights to them.

The last stage, ./bin/toothOptimizer, runs the non-linear optimization. It can run for a very, very, very long time, especially if you are not running it on a machine with lots of cores (mine had 12). However, it saves its progress every 10 iterations to ./data/tooth/output.obj, so you can kill the program at any time and still have a partial result. The results can then be marched by calling:

      ./bin/marchingCubes3D ./data/tooth/output.o3d 100 3 ./data/tooth/output.obj


Usage: Advanced

This last level is the complete toolchain I used to generate the results for the paper. In order to use this successfully, you will need to:

  • Install BEM++
  • Replace its example program, bempp/examples/tutorial_dirichlet.cpp with the version in QUIJIBO/projects/bemWrapper/tutorial_dirichlet.cpp
  • Get the new version of the example program to build
  • Modify two lines in QUIJIBO/projects/bemWrapper/bemWrapper.cpp,

      string cdCall("cd /Users/tedkim/bempp/build/bempp/examples");
      string exportCall("export DYLD_LIBRARY_PATH=/Users/tedkim/bempp/lib");

    so that when ./bin/bemWrapper tries to call ./tutorial_dirichlet via system(), it finds and runs the binary successfully.

If you can get all that working, the complete toolchain is then:

      ./bin/sdfGen ./cfg/tooth.cfg
      ./bin/objToGmsh ./cfg/tooth.cfg
      ./bin/bemWrapper ./cfg/tooth.cfg
      ./bin/poissonDisk ./cfg/tooth.cfg
      ./bin/cubature ./cfg/tooth.cfg
      ./bin/toothOptimizer ./cfg/tooth.cfg

The first call is the same as in the intermediate usage level. The second call, ./bin/objToGmsh, converts the mesh to the Gmsh format that BEM++ requires. The third call, ./bin/bemWrapper then calls BEM++ on the mesh. This call takes a while to complete, and writes out a potential field when it is done.

The subsequent calls are identical to the intermediate usage level. You should now have the complete toolchain to convert an OBJ file to a Julia set approximation. As noted in the paper, this optimization is a difficult one, so if you try it out on different shapes, don't be surprised if the approximation it finds is not very tight, or if it takes a long time. A good rule of thumb seems to be that the further your shape is from a sphere, the harder the optimization becomes.



Many thanks to the authors who released their code online so that it could be used in this project. These include:

This work was supported by a UCSB Regents Junior Faculty Fellowship, and National Science Foundation CAREER award (IIS-1253948). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. I acknowledge support from the Center for Scientific Computing from the CNSI, MRL: an NSF MRSEC (DMR-1121053) and Hewlett Packard.