CS294-3: Algorithms in the Real World (Guy Blelloch, Fall 97)

# Assignment 4 (Triangulation and N-body)

Due: Wednesday Nov 5, 1997 (Possibly later if an implementation turns out to be much harder than expected).

Implement one of the following algorithms:

• Rupert's Meshing Algorithm
• Garland and Heckbert's Surface Modeling Algorithm
• Callahan and Kosaraju's Well-Separated Pair Decomposition Algorithm
• Feel free to work in groups of two, although I will expect a better job from a group of two. Also feel free to come and discuss the algorithms with me. I've described each of these algorithms in class and have also made papers available that describe the algorithms in more detail. Two of the papers are available on the web, and the third is in a JACM issue that is available the CS reading room (Soda 681).

Note: Source code for some of these algorithms is available on the web. If you choose to do a problem, please do not look at anyone elses source until you have handed in your implementation. You should feel free, however, to use other peoples code for various subroutines such as implementing a heap. Make sure you reference the code.

I have made some code for incremental Delaunay Triangulation available, which you might find useful for either of the first two algorithms. This is taken from the book "Graphics Gems IV", edited by Paul Heckbert, Academic Press, 1994. A copy of the associated chapter is available outside my door. The code is also available as part of a compressed tar file associated with the book. You might find, however, that it is just as easy if not easier to design your code from scratch since deciphering the code is not trivial. Also, as I mentioned in class, you might find a triangle based representation simpler (the code uses the quadedge representation). If you do use any part of the code, make sure to note in your code which parts you used.

You might also find Jonathan Shewchuk's Show-me code (showme.c) useful for plotting a set of triangles, or boundaries. It compiles for me using

`gcc -o showme showme.c -I/usr/sww/X11R6/include -L/usr/sww/X11R6/lib -lX11`
and for drawing triangles you can use .ele and .node files.

### Rupert's Meshing Algorithm

You should implement the algorithm and run it on the test sets given below and report back the number of triangles for minimum angles in the ranges specified. Ideally you should generate a postscript drawing of the final triangulations. Although the drawings are not required they will certainly help you debug your program. The algorirthm is described in:
Jim Rupert. ``A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation.'' Journal of Algorithms, 18(3):548-585, May 1995.
The test data files: (Note: these use the Poly format from Jonathan Schewchuk's Triangle code)
• The letter A from Rupert's paper. (corresponding postscript) Run this from 15 to 25 degrees in steps of 2 degrees.
• Lake Superior from Rupert's paper. (corresponding postscript) Run this from 10 to 15 degrees in 1 degree steps. Note that this input has an internal angle that is just slightly larger than 15 degrees, so it will not work with larger angles.
• A guitar from Jonathan Schewchuk. (corresponding postscript) Run this from 15 to 25 degrees in steps of 2 degrees.
• Note that all data is included in a bounding box. This simplifies the problem of dealing with exterior triangles (all triangles in the box are considered interior). In your implementation you don't need to remove the triangles in the exterior (between box and surface) nor in the "holes". You can therefore ignore the "holes" data at the end of the .poly files. If you do chose to remove the triangles, however, you can use the "holes" data by starting at each triangle with the hole point and removing triangles outwards until you hit a boundary segment. If you choose to remove them please state this in your results.

### Garland and Heckbert's Surface Modeling Algorithm

You should implement the algorithm and run it on the test sets given below and report back the number of triangles for a range of maximum errors. Again generating a drawing of the triangulation will be helpful but is not necessary. The algorirthm is described in:
Michael Garland and Paul Heckbert. ``Fast Polygonal Approximation of Terrains and Height Fields.'' CMU-CS-95-181, CS Dept, Carnegie Mellon U., Sept. 1995.
The algorithm I want you to implement is number III in the paper (the version I described in class).

The test data files: (Note: these are binary files in STM format)

• Crater lake
• Ashby Gap, Virginia
• Desert around Mt. Tiefort, California
• Ozark, Missouri
• The following files contain C++ code for reading data in the STM (Simple Terrain Model) format. (stmops.c and stmops.h)

### Callahan and Kosaraju's Well-Separated Pair Decomposition Algorithm:

You should implement the algorithm in 2 or 3 dimensions and run it on the Kuzmin model with 10K and 100K points (I originally said Plummer model, but I cannot find an equation for generating a Plummer distribution...if you do, please feel free to use it, but tell me.) For both sizes you should report the number of interactions as a function of the separation constant s ranging from 1 to 2 in increments of .2. The algorirthm is described in:
Paul B. Callahan and S. Rao Kosaraju. ``A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields.'' JACM, 42(1):67-90, January 1995
Available for copying in the CS reading room.

Points can be generated in the Kuzmin model by first generating a random point p within a circle of radius 1. This can be done by generating a random point within a square [-1,1],[-1,1] and throwing the point out if it is not in the circle and trying again. Now scale the radius by

r_new = (1/(1-r)2)-1

In particular

x_new = (x/sqrt(x^2 + y^2))((1/(1-sqrt(x^2 + y^2))2)-1)

y_new = (y/sqrt(x^2 + y^2))((1/(1-sqrt(x^2 + y^2))2)-1)

Repeat this process for each pont.

You can use a similar technique in 3 dimensions (by generating points in a unit cube). For the scaling, however, you should use

r_new = (1/(1-r)3)-1

in 3 dimensions.

Back to the Algorithms in the Real World page.
Guy Blelloch, guyb@cs.berkeley.edu.