Here's the PostScript version of this page.

Here are some sample input files. The following files are polygons, mostly with holes, though it is easy to manually remove the holes if your mesher doesn't handle them. The outer boundary vertices are in counterclockwise order, and the boundary vertices of each hole are in clockwise order, so that the interior of the region is always to the left of each edge. You may need to automatically or manually break up the longer edges into smaller pieces if you are implementing an advancing front mesher. A.poly, J.poly, africa2.poly, cmu2.poly, guitar.poly, happy.poly, key.poly, point.poly, superior.poly, and yousuck.poly.

The following files are more general PSLGs, in some cases bounding several regions. The vertices are not in any particular order, and the edges are not oriented any particular way. face.poly, layers.poly, s.poly, spokes.poly, and trix.poly.

CS 294-5: Meshing and Triangulation (Autumn 1999)
Mesh Generation Project
 (40% of final grade)

Implement a two-dimensional mesh generator or a project of equal complexity closely related to the material discussed in this class.

You may choose a project from the following list, or devise one of your own in conjunction with me. You are welcome and encouraged to design a project that is related to your research outside this course. (However, please be honorable and don't suggest a project that you've already implemented as part of your research.)

To maintain variety, I will allow at most two students to choose any one item from the list above, and at most one student to choose the first item. The sooner you make your choice, the more likely you'll get the project you want. Details on each of these choices appear later in this document.

If you choose a project from this list, you should also choose some aspect of the algorithm as a point of experimentation. (Some suggestions appear in the individual sections on each choice later in this document, although you may also try an idea of your own.) For instance, with an advancing front mesh generator, you might experiment with various methods of handling front collisions, and determine which works best. With a mesh improver, you might experiment with specific ways of finding good transformations or choosing the next transformation. With a surface simplifier, you might experiment with different utility functions. The experiments need not be elaborate.

Deadlines

November 11: By today, you should have informed me what project you are undertaking, and what approach you plan to take to filling in and experimenting with the details of the algorithm. If your project is not drawn from the list above, you should have discussed the details with me in person.

November 26: You should have arranged a demonstration of the progress of your project, to take place no later than today. Contact me in advance for an appointment, which may be in any on-campus location of your choosing. Your program can still be unfinished and very buggy, but I want to see graphical evidence that you are able to generate the beginnings of a mesh (or simplify one), and that your project is well underway. The demo also presents an opportunity to discuss the details of your project, and whether the direction or scope of the work still seems reasonable. The demo is worth 10% of your score: 4 points. If you demo your program by today, you will probably receive the full four points. For each day your demo is late, you'll lose 10% of those four points.

December 3: The source code for your project, including instructions for compilation and running, are due today. This portion is worth 80% of your score: 32 points. For each day your project is late, you'll lose 10% of your gross assigned score out of 32.

December 6: The HTML public documentation for your project is due today. The public documentation is worth 10% of your score--4 points--and will become a permanent part of the course web site. For each day your documentation is late, you'll lose 10% of those four points.

Language

If you write in any language other than C, you are required to give me very complete instructions on how to compile and run your code. You may also be required to obtain for me an account with which I can run your code. If your submission does not run under Unix, I may need even more help.

Interface

If it's appropriate, your program should use the same file formats as the program Triangle. If it is a two-dimensional mesh generator, it should read a file with the suffix .poly, and write a file with the suffix .ele or .edge. (The latter is a better choice for quadrilateral meshes if you want to view them.) If it is a surface reconstructor for three-dimensional point sets, it should read a file with the suffix .node. All the file formats are documented on the Triangle web pages.

An advantage of using these file formats is that you (and I) can use the Show Me visualization program to view and print your input and output. (If you need a three-dimensional version of Show Me, please ask.)

Geometric primitives and data structures

You may find that you have to create a selection of new geometric predicates and constructors for your project. Since this can occasionally be a surprisingly difficult task, please feel free to ask me for help.

You are at liberty to use any geometric data structures you wish. For some projects, you may find it useful to build on the quad-edge code you wrote for Project I.

Borrowed code

You are welcome to use publicly available libraries or implementations of the following, so long as none of them was produced by any of your classmates: sorting, selection, binary heaps, balanced search trees, other fundamental non-geometric data structures, command-line switch processing, and geometric primitives like the InCircle and CCW predicates. You must write the geometric algorithms all by yourself.

Speed

You should strive to be able to deal with meshes or triangulations with sizes of 1,000 in a reasonable amount of time. Beyond this, please concentrate on functionality, not optimality. Your first priority is to implement a working algorithm, however slow.

Your first submission: the project

My preferred submission method is that you email me the URL of a file or directory containing all your code, so I can download it at my leisure. Alternatively, you could email me a uuencoded archive of your files. If your code doesn't run under Unix, special arrangements will definitely need to be made.

With your code, please send instructions for compiling and running your code. If you use C and Unix, relatively rudimentary instructions will probably do. Be sure to document how to specify the input file, and how to choose between any options you have provided. Please also provide example inputs (including some on which you think your program performs well, and perhaps some that show the algorithm's flaws), and let me know which options work best with these inputs, and what features you think these examples demonstrate.

Your second submission: public documentation

Provide, in HTML format, a self-contained web page or set of web pages that discusses your implementation in a manner accessible to outsiders who have some familiarity with mesh generation. Your public documentation will be copied to become a permanent part of the class web site. Therefore, please use relative URLs (rather than absolute URLs) to link your pages and figures together, but use absolute URLs for links to your personal home pages, research pages, and so forth. You may copyright your public documentation, so long as you offer me perpetual permission to serve your documentation from my web sites. Your documentation should include: The following things are optional, and will not affect your grade.

Project: Delaunay refinement mesh generator

Implement Ruppert's Delaunay refinement algorithm for triangular mesh generation, as described in Section 3.4 of the lecture notes. A working basic implementation (with an experimental component) would merit an A-. For an A+, also implement the modifications for handling small angles described in Section 3.8. (In neither case do you need to use constrained Delaunay triangulations. If you do wish to implement CDTs, I recommend inserting segments incrementally rather than implementing Chew's algorithm.)

For simplicity, you may want to augment the .poly file format so that each segment includes with one or two extra fields, which indicate whether each side of the segment is interior or exterior.

Possible points of experimentation: How much does off-center segment splitting (as described in Examination I) help reduce the number of triangles in the mesh? How much do the simplifications described in the last two paragraphs of Section 3.8 compromise the quality of a mesh, when small input angles and large input angles coincide at a common apex?

Project: Anisotropic bubble meshing

Implement a two-dimensional bubble mesher, perhaps based on the paper by Bossen and Heckbert, the paper by Shimada, or some combination thereof. If you wish, you may assume that the input is a polygon with holes, and the segments are specified in counterclockwise order about the outer boundary, then clockwise about each hole. Allow the use of a space-varying density function (perhaps implemented as a linkable C function call) which dictates the approximate desired edge lengths or element areas at each point in the mesh. A working basic implementation (with an experimental component) would merit an A-. For an A+, also implement support for generating anisotropic meshes using a space-varying (but not too-quickly varying) ellipticity tensor in the place of the density function.

Possible points of experimentation: What force law seems most effective? What rules for creating/destroying nodes seem most effective?

Project: Advancing front meshing

Implement an advancing front mesh generator for triangular meshes. If you wish, you may assume that the input is a polygon with holes, and the segments are specified in counterclockwise order about the outer boundary, then clockwise about each hole. A working basic implementation (with an experimental component) would merit an A-. For an A+, also implement support for generating anisotropic meshes using a space-varying (but not too-quickly varying) ellipticity tensor.

Possible points of experimentation: Experiment with different methods of choosing the best vertex to use when generating a new triangle. (When should you use an existing vertex, and when should you generate a new one? If you generate a new one, when is an equilateral triangle not ideal?) Experiment with different methods of deciding which edge of the front to advance next.

Project: Quadtree meshing

Implement a quadtree-based triangular mesh generator. A working basic implementation (with an experimental component) for polygons with holes would merit an A-. For an A+, also implement support for meshing general PSLGs. A mesh with no small angles is not always possible in this case, but do the best you can. It may take creativity to find warping rules that work well where multiple input segments intersect at a single vertex.

For simplicity, you may want to augment the .poly file format so that each segment includes with one or two extra fields, which indicate whether each side of the segment is interior or exterior.

Possible points of experimentation: How finely does the quadtree need to be subdivided to ensure good element quality? (Hopefully, not as finely as Bern, Eppstein, and Gilbert refine it.) What warping rules tend to produce good elements?

Project: Quadrilateral meshing

Implement the paving or Q-morph algorithm for quadrilateral mesh generation. If you choose the Q-morph algorithm, you may use a preexisting triangular mesh generator (like Triangle) to create input meshes. If you wish, you may assume that the input is a polygon with holes, and the segments are specified in counterclockwise order about the outer boundary, then clockwise about each hole. An implementation of either algorithm that includes enough basic features to support graded element sizes is complicated enough to merit an A+.

Possible points of experimentation: The paving and Q-morph algorithms have parameters that need to be set experimentally.

Project: Triangular mesh improvement

Implement a mesh improver that reads an existing triangular mesh, and uses optimization-based smoothing and topological transformations (including swapping and transformations that insert and delete vertices) to improve angles as much as possible. You may use a preexisting triangular mesh generator (like Triangle) to create input meshes. You may assume that boundary vertices are fixed and interior vertices are not, but it will improve your grade if you allow constrained smoothing of boundary vertices. (If the angle at a boundary vertex is sufficiently close to 180o, you may assume the vertex is allowed to move along the boundary segment.)

An aggressive and effective working implementation (with an experimental component) would merit an A-. For an A+, implement constrained smoothing of boundary vertices, or allow the use of a space-varying density function (perhaps implemented as a linkable C function call) which dictates the approximate desired edge lengths or element areas at each point in the mesh, and use the transformations that insert or delete vertices to bring the element density close to the density specified by the function.

Possible points of experimentation: You will have to define a procedure that searches for good transformations and smoothing opportunities, and prioritizes them. What procedure gives a good combination of speed and high quality?

Project: Surface reconstruction

Implement a three-dimensional Delaunay tetrahedralizer (using the Watson/Bowyer algorithm), and use it as a subroutine in a crust-based surface reconstructor as described by Amenta, Bern, and Kamvysselis. You will have to find your own sources of input points (this link may help), and your own way to display the surfaces you reconstruct. (I can provide a buggy three-dimensional version of Show Me that will display your Delaunay tetrahedralizations, sort of.)

A working implementation (with an experimental component) that uses a walking method for point location would merit an A-. For an A+, implement conflict-based point location. (I have a transparency that briefly explains how to do this in three dimensions; ask me for a photocopy.)

Possible points of experimentation: Amenta, Bern, and Kamvysselis discuss several approaches to choosing poles when an object has sharp corners. Do you agree with their conclusions?

Project: Surface simplification

Implement a mesh simplification program for two-dimensional manifold surface meshes embedded in three-dimensional space. You might consider the algorithms of Hoppe, Garland and Heckbert, other researchers, or some combination thereof. The user should be able to specify the size of the simplified mesh. Provide an option that allows a user to select between general vertex pair contractions (as Garland and Heckbert use), edge contractions, or topology-preserving edge contractions. (The algorithm may have to stop early if only topology-preserving edge contractions are allowed.) You will have to find your own sources of input meshes (this link may help), and your own way to display the surfaces you simplify.

A working implementation (with an experimental component) would merit an A-. For an A+, make sure your implementation handles manifolds with boundary, and that the boundary is preserved as well as possible during simplification, or incorporate color attributes into your simplication implementation.

Possible points of experimentation: Which error measure performs best? What is the best way to preserve manifold boundaries while allowing them to be simplified along with the manifold?