This morning I attended the Ph.D. defense of Pablo Díaz-Gutiérrez, a Ph.D. student here in the computer graphics group who's been doing some interesting work combining geometric models of shapes with theoretical data structures and graph algorithms.

One aspect of Pablo's thesis research concerns triangle strips, branching off from some research his advisor Gopi and I had previously done on generating single-strip triangle meshes. A triangle strip covering all the triangles in a mesh is essentially the same thing as a traveling salesman path in the cubic graph formed by the planar dual graph of the mesh, but the TSP is difficult to solve directly even in these graphs. Gopi and I had observed that the complement of a Hamiltonian path in a cubic graph is a perfect matching, guaranteed to exist by Petersen's matching theorem; we described algorithms that compute a matching and then perform local operations (sometimes if necessary subdividing the mesh) to glue the complementary cycles into a Hamiltonian path. But this was all purely combinatorial. In his own work, Pablo set about putting the geometry of problem to use in controlling the shape of the strips formed in this way. He showed that, by giving higher weight to model edges that form sharper angles and by using a weighted matching algorithm, he could generate strips in which adjacent triangles tended to have the same orientation. By then imposing a segment tree data structure on the strip, in which each tree node stores composite information about the orientation and position of the triangles represented by that node, he was able to perform back-face culling quickly, listing only the contiguous subsequences of the strips that are visible within a given scene. He also showed how to use the same controlled-strip-generation ideas with different weights to provide cache-oblivious memory layouts for geometric models, to compress the combinatorial structure of a mesh to a small number of bits, and to find many independently-performable edge contraction operations that can be used to simplify the non-visible parts of a mesh while still preserving its topology and its strip decomposition. The results Pablo presented in his defense also included some related material on surface simplification (with a similar mix of algorithmic tools and geometric heuristics) in which by finding and removing small topological defects and then using an ε-net on the Gaussian sphere to guide sample vertex selection he was able to quickly find simplified versions of geometric models with high visual quality and few vertices.

There was plenty of good material there and we had no hesitation in passing him. Congratulations, Pablo!