Advanced Topics in Computer Graphics
The purpose of this exercise is to develop and implement an algorithm
that creates a watertight mesh that closely approximates an input polygon
soup or a point cloud. A polygon soup is a collection of polygons (triangles)
that does not form a consistent watertight connectivity. For example, trees
are often represented by such soups. In this exercise, however, we assume
that the polygons originate from sampling some smooth surface.
To approximate a given polygon soup or point cloud with a watertight mesh,
the algorithm should grow a "blob" from inside
the surface. The blob
will develop and grow until it sticks tightly to the input geometry. The
growth of the blob is controlled by some energy functional: you define an
energy, and the blob tries to minimize it by expanding itself step-by-step.
When the blob expands, it can possibly refine its connectivity by subdivision,
and of course change the geometric position of its vertices. In every step
the blob keeps its property – it is a watertight legal mesh. The energy functional
should consist of some reasonable ingredients, preferably as few as possible,
to keep the process efficient. The ingredients can reflect some distance
measure between the blob surface and the input geometry; the smoothness of
the blob surface, etc.
For the “blob” to grow, it should find a correspondence to the input geometry.
The correspondence between points finds for each point on one shape the closest
point on the other. The distance metric used for point correspondence should
account the Euclidean distance and the similarity of the local curvatures.
However, any other criteria to measure shape similarity can be used. To find
best matching and alignment you can use the ICP algorithm (see Reference
4). This algorithm iteratively finds the best correspondence and alignment
between two shapes. In each iteration a closest point correspondence is found
and an alignment that minimizes its distance. The process stops when further
deformation of the shapes does not improve the distance between corresponding
points, or when the deformation transformation results in the identity matrix.
Define what is a good result. What do you consider as a good blob? The
minimal requirements are that the blob is:
- close to the input geometry
- fairly smooth
- does not contain much more triangles / vertices than the input
A good algorithm should also be fast.
The basic exercise is to handle genus-zero surfaces (no holes). As a bonus,
try to extend your algorithm to automatically handle higher-genus surfaces,
so that the growing blob will change its topology when necessary.
Here are some references that you may find useful.
But try to be creative and invent your own optimization process.
- A Method for Registration of 3-D Shapes
Paul J. Besl and Neil D. McKay
IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992,
volume 14, pp 239-256.
You can use the following
code as a quick start for rendering 3D meshes. It’s a Visual C++ 6.0 project.
The project uses the GLUI library for GUI and GLUT for handling windows.
If you don’t have these libraries, download from here:
The application allows to
load a triangle mesh from a VRML file or PLY2 file and to render it in different
modes (solid, wireframe,
solid with edges, draw vertices as small balls, etc...). To choose specific
rendering options, work with the Rendering Modes menu.
Navigation: to rotate
the mesh, hold down the left mouse button and move the cursor. To zoom
in/out, also hold down the Ctrl key.
To move the mesh, hold down the Shift key.
Colors: you can change the color of the mesh by choosing a colored
light, or by changing the material color. To do the latter, click in the
mesh viewport area and then press + or -. This will scroll the palette down/up.
The main class is called
TexturedMesh (the name might be misleading - you don't need to load textures).
You can of course use another
renderer and/or write your own application if you like. The provided application
is by no means guaranteed
to be bug-free or particularly efficient.
You can find some input here