In computer graphics, the geometry of 3D object is approximated by using 3D points (vertices). It is easy to see that when fitting a curve, the smoothness and thus accuracy increases as the number of vertices increases. These vertices are then triangulated to generate a mesh. However, the display of high resolution mesh is often constrained due to limited resources, such as bandwidth, time, hardware capacity, and others. Levels-of-detail (LOD) is a computer graphics technique commonly used to allow applications to select meshes of different resolutions. Many algorithms have been developed in the last decade and a few are included in the List of Papers Section. The purpose of this project is to give students a general knowledge of these algorithms, based on which further research into 3D graphics can be built upon.

Example of a head model displayed from fine to coarse (left to right)

Number of vertices are: 1872, 1187, 1128, 1048, 887 and 676.

Note that the face features diminish gradually from fine to coarse.

Timetable:

Guideline:

• If too many students choose the same algorithm, random assignment will apply.
• Make sure you review the papers and understand the algorithms before selecting one for implementation.
• Start the project early; don't wait until the last minute.
• Download Stanford bunny 8171 vertices as the initial mesh.
  
• Choose an implementation platform (e.g. Java or OpenGL for the interface). Follow this input file format .
• IMPLEMENTATION/DEMO I - Develop an interface to render the bunny, with the option to choose between mesh or point display.
• IMPLEMENTATION/DEMO II - (can be an integrated or a separate program, e.g. C, C++, etc.)
  1. Apply a simplification algorithm to remove (i) 5000, (ii) 7000 and (iii) 7750 vertices.
  2. For the original and the 3 simplified versions,
     1. compute the 3D center (average of x,y and z).
     2. For each vertex, calculate the radius from the center,
     3. the order (priority #) to be removed, with the smaller number removed first, and
     4. the x, y and z coordinate of the REMOVED vertex.
     5. Record the time required for the simplification process excluding printing to file.
  3. The interface should provide the following:
     1. Specifiy the number of vertices to remove, and generate the simplified mesh.
     2. Display mesh.
     3. Student should be able to regenerate any simplified version during the Demo Session.
  4. Output file format 1 (use space to separate parameters)- Example:
     Vertex 3171
     id radius priority x y z
     0 0.89 27 -0.0312216 0.126304 0.00514924
     1 0.4526 34 0.0447046 0.0927877 0.00507585
     2 0.5629 342 -0.0479133 0.129301 0.0269646
     .
     .
     .
     3170 0.89 1897 -0.0377039 0.167987 -0.0130391
     Faces 7100
     Time (specify seconds or milliseconds)

  5. Output file format 2 - Same as input mesh file format.
     
     1. Make sure that an id in format 1 and format 2 refers to the same vertex.
        
     2. Note that x,y,z in format 1 is the removed vertex, replaced by the id at the beginning of the line.
• PRESENTATION - Discuss the algorithm (pros and cons) you have implemented in a 15 minutes presentation.
• PROJECT REPORT - Study and discuss a "skeletonization" algorithm.
• If you want to implement a technique not in the selected list, obtain approval from Prof. Basu.
• Students can also propose a new algorithm and compare with existing ones.
• Useful information can be obtained by searching http://www.google.com.

List of Papers:

1. W. Schroeder, J. Zarge and W. Lorensen, "Decimation of triangle meshes", Proc. Siggraph 1992 pdf
2. P. Hinker and C. Hansen, "Geometric optimization," Proc. Visualization 1993 pdf
3. T. He, Li Hong, A. Kaufman, A. Varshney and S. Wang, "Voxel based object simplification," IEEE Int'l Conf. on Visualization 1995 pdf
4. J. Cohen, A. Varshney, D. Manocha, G. Turk and H. Weber, "Simplification envelopes", Proc. Siggraph 1996 pdf
5. H. Hoppe, "Progressive meshes" Proc. SIGGRAPH 1996 pdf
6. M. Garland and P. Heckbert, "Simplification using quadric error metrics," Proc. Siggraph 1997 pdf
7. K-L. Low and T. S. Tan, "Model simplification using vertex clustering," Proc. 1997 Symp. Interactive 3D Graphics pdf

(Optional) Further Reading:

1. P. S. Heckbert, M. Garland, "Survey of polygonal surface simplification algorithms", Multiresolution Surface Modeling Course SIGGRAH 1997 pdf
2. D. P. Luebke, "A Developer's survey of polygonal simplification algorithms", IEEE Computer Graphics and Applications, May/June pdf
3. J. Foley, A. Dam, S. Feiner and J. Hughes, "Computer Graphics Principles and Practice 2nd Edition", Addison-Wesley.
4. M. Berg, M. Kreveld, M. Overmars and O. Schwarzkopf, "Computational Geometry Algorithms and Applications 2nd Edition", Springer.