Advanced Topics in Computer Graphics

The Blob


   

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:
A good algorithm should also be fast.

BONUS:
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.

Code:

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.

Input models:

You can find some input here.