Assignment 2


Assignment 2: Line Art

Due date: Monday, June 15th, 2015


There are several interesting algorithms for creating designs from a single long path, or a small set of paths. Some of these techniques produce meandering lines that are geometrically attractive at a low level. Several can be further tuned so that the meandering lines resemble input images.

Question 1: Organic labyrinths

You must implement a self-contained program that simulates the growth of meandering paths in the manner described by Pedersen and Singh in their paper Organic Labyrinths and Mazes (NPAR 2006). The goal is not to reproduce the entire technique described in that paper, only a small subset that demonstrates the basic principle of a smoothly growing organic curve.


Begin by reading the paper linked above. You should focus your attention on Section 2, omitting the subsection related to anisotropy. There are also a few useful details in Section 4.1. (Thus there’s about a page of text you need to read in full detail.)

Now create a standalone program that evolves an organic curve beginning with a simple path. Your program need not have any kind of user interface, though I recommend that you have a window that can display the state of the simulation after every time step, in order to make debugging less painful.

The simulation in the paper is highly configurable through a number of spatially varying parameters. For the purposes of this assignment, it’s fine to simplify these parameters a great deal. The weighting functions f_B, f_f and f_a, which offer spatial control over the effects of Brownian motion, fairing, and attraction-repulsion, can be replaced by three global constants. If path spacing is constant, then I believe it is also possible to fix the function \delta at 1, removing a lot of complexity from the equations in the paper. In the end, I’m interested in seeing a simple proof of concept: a program that can create space-filling labyrinthine paths with constant spacing, like the one in Figure 8(c). It would be great, but not required, if you attempted to augment this base with more of the ideas in the paper.

As with the previous assignment, your program should output a vector drawing as a Postscript, PDF, or SVG file that can be embedded into a document or a web page.

Because of the timing and the nature of the base algorithm, I will not require a “non-trivial extension” or “official artifact” for this assignment. Of course, I’d be excited to see what you’re able to add to this algorithm and what kinds of images you can produce with it (and may award bonus marks for any work beyond the basic requirements). I think it would be very useful to allow multiple disjoint paths, and to mark some path vertices as “fixed” (they can act on other points, but never move). That way, you can create designs with specified boundaries, like that in Figure 16 of the paper.

What to submit

You need to produce a short write-up describing your implementation and showcasing the illustrations you created. Your write-up can either be a PDF document or a web page. Your submission should not contain more than about three or four pages of text, though you’re welcome to make it longer by including lots of pictures. Some time before the deadline, email me either a URL for your web-based write-up or a PDF.

You are free to structure your submission as you desire. But it should include at least the following:

  • Describe your implementation. What set of languages, tools, and libraries did you use? What is the interface? If you created an interactive user interface, include screen shots.
  • If there are aspects of the paper that you didn’t get working, list them. If applicable, explain how you would need to modify your program to complete the implementation.
  • I’m especially interested in hearing about how closely your implementation follows the equations as described in the paper. Where did you deviate, if anywhere? Did you bound point displacement so that the simulation remains stable? Did you experiment with any alternative formulations for the main forces?
  • Include sample output. Because of the random nature of the simulation, be sure to include the results from multiple runs, in order to highlight differences. It would also be good to include examples that show the effects of varying the constants mentioned above, whether or not they’re spatially varying.

You’re welcome to include other comments and observations on the paper, the technique, and the value of this class of algorithms. I’m also interested in ideas for future work.

By default, I’m not going to look at your source code. But I reserve the right to request it as part of marking if it sounds from your description like there’s something worth taking a look at. I also reserve the right to request a live demonstration; this could be important if you create an especially nice interface or a realtime version of the algorithm.

Implementation notes

  • I believe that this algorithm is tricky to get right, even given the simplifications above and all the details in the paper. Part of that is the general difficulty of getting any physical simulation running smoothly—many such simulations walk a fine line between doing nothing and exploding, and require fine tuning of parameter values. But I also think that some of the equations might not work quite as simply as described in the paper. I’d really like to put this paper to rest in my mind. So much the better if we can ferret out these discrepancies once and for all.
  • Brownian motion and fairing are very easy to implement. Curve resampling is slightly trickier, but still well within the everyday toolkit of computer graphics programming. The attraction-repulsion model is the hard part. The Lennard-Jones potential used in the paper has a nasty asymptote at zero, meaning that if two curve points get too close to each other they’ll shoot off to infinity. Can these forces nevertheless be balanced to prevent this degeneracy?
  • If you’re stuck, you may also want to mine the authors’ patent for a second point of view on the algorithm.
  • For the purposes of this assignment, I strongly encourage everyone to exchange information and ideas freely so that we can overcome any challenges. You can email me directly, but I’d prefer some kind of discussion that’s visible to all. You can use the comments section of this page for simple threaded discussion. (If we prefer a closed forum just for the course, I’ll happily set up a Piazza site.)


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.