Assignment 2

Assignment 2: Line Art

Due date: Monday, June 15th, 2015

Summary

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.

Specification

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.)

17 Responses to "Assignment 2"

Wei-Shou says:

June 5, 2015 at 8:37 pm

At the beginning of section 2 the paper says D is the average distance between the points. My understanding of this is that D is recomputed each iteration based on the points’ locations. But later when talking about resampling, the paper mentions that “the sampling rate can be controlled globally by changing D” which makes it sound like D is a parameter. Is my first interpretation correct? How do we control the sampling rate with D?

Thanks.

Reply
1. Craig Kaplan says:
  
  June 5, 2015 at 9:15 pm
  
  Wei-Shou,
  
  I agree that this is one of the confusing parts of the paper. My best guess is that you should treat D as a global constant. The paper says “Assume that the curves have N sample points and that the average distance between these points is D.”. Perhaps in this context we can interpret the text to mean that we wish to control the spacing of the points to be roughly D, and compute D as the average of the points in any given time step. I think that’s the only interpretation that’s consistent with the text later about changing D.
  
  Reply
  1. Wei-Shou says:
    
    June 7, 2015 at 5:00 pm
    
    Yes, I think this is right. D should be a global constant. Otherwise adding more samples would decrease the average distance, which would decrease the threshold for adding samples, and more and more samples would just keep getting added.
    
    Reply
Xiao-Bo Li says:

June 10, 2015 at 4:30 pm

For the standard normal distribution, what should we put as the variance? Seems like the paper doesn’t say. So is this another parameter to play with?

Reply
1. Xiao-Bo Li says:
  
  June 10, 2015 at 4:33 pm
  
  Also the paper calls sigma variance, but sigma is usually denoting the standard deviation?
  
  Reply
2. Craig Kaplan says:
  
  June 11, 2015 at 4:53 am
  
  In the paper they refer to the variance generically as sigma, but I don’t think it’s meant to be yet another free parameter. I would just assume sigma=1.
  
  Looked at another way, there’s already a parameter f_bm that controls the strength of the Brownian motion force. Any control offered by making sigma into a parameter would already be subsumed by changes to f_bm, so I don’t think you need both.
  
  Reply
Xiao-Bo Li says:

June 10, 2015 at 4:50 pm

For the fairing force, it averages points before and after p_i. So if those points do not exist, say at the beginning and end, we should just take the point that exists and not take the average?

Reply
1. Craig Kaplan says:
  
  June 11, 2015 at 4:56 am
  
  You should treat the path as a closed loop, so indices are taken modulo the number of points in the loop.
  
  (If you actually want to work with open paths, that’s a different story. I suppose you’d have to do something else to deal with the fairing force at the endpoints of an open path. Probably it’s easiest just to leave those points where they are.)
  
  Reply
Xiao-Bo Li says:

June 10, 2015 at 4:53 pm

Actually, for the fairing force, the first and last point should just have 0 for that force I think.

Reply
Reza says:

June 10, 2015 at 6:02 pm

Test latex $latex [\sqrt{a^2+b^2}]$

Reply
1. Craig Kaplan says:
  
  June 11, 2015 at 4:57 am
  
  I tried that too, but it doesn’t work. In theory this page should render embedded LaTeX markup, but I think the plugin that does it is restricted to the post itself and doesn’t work on comments. I suppose that’s smart — writing a WordPress plugin that does arbitrary processing on the text of comments must surely leave you open to unpredictable attacks by malicious outsiders.
  
  Reply
Reza says:

June 11, 2015 at 1:08 pm

Is there a way to evaluate the convergence? I want all segments which already stuck and have nowhere to grow to stop evolving. However, I’ve observed that all points always vibrate. They waste my computation especially when my curve has been evolving really big (> 50000 points).

Reply
Xiao-Bo Li says:

June 12, 2015 at 9:47 am

The attraction-repulsion forces on p_i by nearby points requires us to find the nearby points for p_i. Should we avoid going through all points to find which are nearby?

Reply
1. Reza says:
  
  June 12, 2015 at 10:11 am
  
  The paper says they use octree. I personally use KD-tree to find them.
  
  Reply
  1. Reza says:
    
    June 12, 2015 at 10:18 am
    
    Additional note: Yes, we need to go through all points to find nearby points. Of course, brute force would work. If anyone uses C++ I would recommend NanoFLANN (https://github.com/jlblancoc/nanoflann). It’s a library for K-d tree and It only requires 10-20 lines of code.
    
    Reply
Reza says:

June 12, 2015 at 10:53 am

I’m able to simplify the attraction-repulsion force by removing the entire the conditional |x_ij – p_i| n_min.

I calculate f_ij as in the paper and use a clamping function:

clamp(thrshold, f_ij)
if(f_ij thrshold) f_ij = thrshold;

where thrshold is a constant (I use thrshold = 20.0)

This might not be mathematically correct, but I can avoid f_ij to be infinity/nan and the simulation is quite stable.

For Lennard-Jones constant, I use sigma_lj = 1.0.

Reply
1. Reza says:
  
  June 12, 2015 at 10:55 am
  
  uh, my comment is broken.
  
  here’s the clamping function:
  
  clamp(thrshold, f_ij)
  if(f_ij lower than negative thrshold) f_ij = negative thrshold;
  if(f_ij larger than positive thrshold) f_ij = thrshold;
  
  Reply