CMPT 888 Course Projects (Fall 2004)

Partial Active Region of Horse Compression

Partial Active Region of Bunny Compression

Angle-Analyzer: A Mesh Compression Algorithm by Jeff Sember

Abstract: Angle-Analzyer is a triangle mesh compression algorithm. The performance of the algorithm is investigated, in terms of both mesh connectivity and geometry. Three techniques of encoding the vertices of the mesh are compared, including a novel angle + aspect ratio method, which is shown to consistently outperform the method of the original algorithm. Issues concerning the entropy encoding of the connectivity and geometry are also discussed.


  • H. Lee, P. Alliez, and M. Desbrun, "Angle-Analyzer: A Triangle-Quad Mesh Codec," Vol. 21, No. 3, Computer Graphics Forum, 2002.
  • J. Rossignac, "Edgebreaker: Connectivity Compression for Triangle Meshes", IEEE Transactions on Visualization and Computer Graphics, 5(1), pp. 47-61, 1998.
  • C. Touma and C. Gotsman, "Triangle Mesh Compression", Proc. Graphics Interface, pp. 26ĘC34, 1998.
  • I. Witten, R. Neal, and J. Cleary, "Arithmetic Coding for Data Compression", Communications of the ACM, 30(6), pp. 520ĘC440.

Original Lion

Reconstructed with 50 control points

Reconstructed with 300 control points

Least-Squares Meshes by John Li

Abstract: This project provides a mean of reconstructing a smooth mesh using a connectivity graph and a set of points. The resulting mesh satisfies the least-squares constraint. That is, each vertex lies in the centroid of its immediate neighbours. The geometry of the resulting mesh is obtained by solving a sparse linear system. As it will be discussed later in this document, LS-mesh can be very helpful in aiding many areas of computer graphics.


  • O. Sorkine and D. Cohen-Or, "Least-Squares Meshes," SMI 2004.
  • M. Isenburg, S. Gumhold, and C. Gotsman, "Connectivity shapes", Proceedings of IEEE Visualization, pp. 135-142, 2001.
  • M. S. Floater, "Parametrization and smooth approximation of surface triangulations", Computer Aided Geometric Design, 14(3), pp. 231-250, 1997.
  • R. L. Burden and J. D. Faires, Numerical Analysis, 2001.


Picky ICP

Spectral Correspondence

Affine Point Matching

Point Matching Methods: Survey and Comparison by Varun Jain and Xiaoxing Li

Abstract: Point/feature matching in 2D images has been well studied in the computer vision community. With the huge advancement in shape scanning and acquisition technology, feature matching has recently found usefulness in 3D shape matching and searching. We study the general problem of feature correspondence in 3D shapes represented by triangular meshes. This project is a survey and comparison of extending various 2D point matching algorithms to 3D data sets. Finally, we suggest several potential ways to extend these techniques for solving the general problem of feature correspondence in 3D shapes.

Selected reference:

  • P. J. Besl and N. D. Mckay, "A Method for Registration of 3D Shapes", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, Issue 2, 1992.
  • T. Zinber, J. Schmidt and H. Niemann, "A Refined ICP Algorithm For Robust 3D Correspondence Estimation", IEEE International Conference on Image Processing, 2003.
  • L. S. Shapiro and J. M. Brady, "Feature Based Correspondence: An Eigenvector Approach", Image and Vision Computing, Vol. 10, Issue 5, 1992.
  • M.-K. Hu, "Visual pattern recognition by moment invariants". IRE Trans. Inf. Theory, Vol. 8, pp. 179-187, February 1962.
  • K. Voss, H. Sube, C. Brauer-Burchardt, "Affine Point Pattern Matching", Pattern Recognition, Lecture Notes in Computer Science 2191, Springer 2001, pp. 155-162.
  • Andrew D. J. Cross and Edwin R. Hancock, "Recovering Perspective Pose with a Dual Step EM Algorithm". Eighteenth Annual Conference on Neural Information Processing Systems, 1997.
  • Marco Carcassoni and Edwin R. Hancock, "Point Pattern Matching with Robust Spectral Correspondence", Computer Vision and Pattern Recognition 2000, pp. 1649-1655.

Subsampled image

Interpolated image

Seabed Surface Reconstruction by Vidya Kotamraju

Abstract: The objective of the project is to obtain an impression of the three dimensional seabed structure. The input is an ASCII representation of sonar data which is subject to interpolation before visualization. The implementation of the project is based on the quadtree guided interpolation which uses a two dimensional quadtree of the ping map in order to guide the three dimensional interpolation process. The algorithm used is taken from [1] and results are shown for both two dimensional and three dimensional data.


Last modified: January 2, 2005