M.Sc Thesis

M.Sc StudentBen-Chen Mirela
SubjectOn the Optimality of Spectreal Mesh Compression
DepartmentDepartment of Computer Science
Supervisor PROF. Chaim Craig Gotsman


Spectral compression of triangle meshes has shown good results in practice, but there is little or no theoretical support for the optimality of this compression. We show that for certain classes of geometric mesh models, spectral decomposition using the eigenvectors of the symmetric Laplacian of the connectivity graph, is equivalent to principal component analysis. Hence spectral compression is optimal in the MSE sense.

We prove this result for one dimensional and two-dimensional meshes, and show a few three dimensional extensions. To prove this, we assume a natural distribution on the space of meshes, and show that for this distribution, the Laplacian matrix is identical, up to a constant factor, to the inverse covariance matrix of the distribution. Since principal component analysis is based on decomposition using the eigenvectors of the covariance matrix, and since the covariance matrix and the Laplacian share the same eigenvectors, this implies that the spectral decomposition - which is based on the eigenvectors of the Laplacian - is optimal.

In the one-dimensional case, we assume that the valid geometries are distributed like uniform order statistics. The resulting covariance matrix is indeed the inverse matrix of the Laplacian up to a constant. In the two-dimensional case, we define the distribution on a barycentric coordinates matrix, and show that the resulting geometries’ distribution is approximately multivariate normal. Then we use the properties of the inverse of the covariance matrix for the multivariate normal distribution to show that the inverse covariance is identical to the Laplacian up to a constant.