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 2945: Meshing and Triangulation (Autumn 1999)
Mesh Generation Project
(40% of final grade)
Implement a twodimensional 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.)
 A triangular Delaunay refinement mesh generator.
 An anisotropic triangular bubble mesh generator.
 A triangular advancing front mesh generator.
 A quadtreebased triangular mesh generator.
 A quadrilateral mesh generator based on paving or the Qmorph algorithm.
 A triangular mesh improver, based on optimizationbased smoothing
and topological transformations.
 A surface reconstructor for threedimensional point sets.
 A surface simplifier for twodimensional surface meshes embedded
in threedimensional space.
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 oncampus 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 score4 pointsand
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 twodimensional 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 threedimensional 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 threedimensional 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 quadedge 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 nongeometric data structures,
commandline 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 selfcontained 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:

A description of the algorithm you implemented,
with citations of relevant papers.
The description may be kept brief with regard to details that are
discussed in the cited papers.

Any noteworthy details of your implementation
(especially details not discussed in the cited paper or papers),
including extra or unusual features,
and any departures from the standard algorithms.
Where there are several standard algorithms,
or the algorithm is ambiguous,
how did you resolve the ambiguity?
For instance, in an advancing front algorithm,
how do you choose the apex of the next triangle?

A detailed discussion of your experiments,
and your conclusions as to which approach is best.

Lots of figures demonstrating your algorithm in various circumstances.
If possible, include figures that show the different results achieved
by different choices in your experiments.
(To generate figures, I recommend using xv to convert
Show Me's PostScript output to GIF format,
or to grab images from your screen.
Let me know if you need help.)
A small part of your score will depend on how glitzy/impressive your
figures (especially meshes or triangulations) look.
The following things are optional, and will not affect your grade.

Timings.

A link to the source code.
If you do wish to make your source code public,
it is up to you whether to copyright it,
release it to the public domain,
distribute it under the GNU Public License,
or make some other choice.
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 offcenter 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 twodimensional 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 spacevarying 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 spacevarying (but not tooquickly 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 spacevarying (but not tooquickly 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 quadtreebased 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 Qmorph algorithm for quadrilateral mesh generation.
If you choose the Qmorph 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 Qmorph 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 optimizationbased 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 180^{o},
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 spacevarying 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 threedimensional Delaunay tetrahedralizer
(using the Watson/Bowyer algorithm),
and use it as a subroutine in a crustbased 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 threedimensional 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 conflictbased 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
twodimensional manifold surface meshes embedded in threedimensional 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 topologypreserving edge contractions.
(The algorithm may have to stop early if only topologypreserving
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?