Research

Processing Massive Meshes

Polygonal meshes are a very flexible and useful method for representing geometric data. They find application in fields as diverse as the visual arts and scientific computation. Advances in geometry acquisition technology, specifically laser range scanning, along with commensurate progress in disk storage technology has made it possible to create and store meshes of incredible detail and size. The Digital Michelangelo Project has generated surface scans of large statues sampled at a  resolution of  1/4 mm. Complex mechanical systems, such as the Boeing 777, are now designed digitally. These multi-gigabyte models contain hundreds of millions, sometimes billions, of polygons. Efficiently processing meshes of this size requires fundamentally new algorithms and data structures.

My work with Michael Garland includes the creation of algorithms for simplification of massive meshes. These algorithms have in-core storage requirements that are insensitive to the size of the original mesh. The resulting algorithms can simplify multi-gigabyte meshes on a simple laptop.

• E. Shaffer and M. Garland. Efficient Adaptive Simplification of Massive Meshes. In Proceedings of IEEE Visualization 2001. [PDF]
• M. Garland and E. Shaffer. A Multiphase Approach to Efficient Surface Simplification. In Proceedings of IEEE Visualization 2002, October 2002. [PDF]

We have also developed a new multiresolution surface representation that allows applications to quickly generate suitably-sized approximations at run-time. The data structure is particularly well-suited for applications such as view-dependent rendering which effectively require random access to the mesh.  

• E. Shaffer and M. Garland. A Multiresolution Representation for Massive Meshes. In IEEE Transactions on Visualization and Computer Graphics, To Appear [PDF]
   

Previous Research

Virtue: an Immersive Virtual Reality Environment for Performance Visualization

During my work with the Pablo research group at the University of Illinois at Urbana-Champaign, I was one of the principal designers and developers of Virtue. Virtue is a virtual environment that allows software developers to directly manipulate software components while immersed in scalable, hierarchical representations of software structure and real-time performance data. Virtue consists of over 50,000 lines of C++ code and was the focus of a team of 3 full-time programmers and 3 graduate students.

A Library for Spherical Geometry with Application to Visibility Computations

At the University of Minnesota, I completed an MS project implementing a small library of algorithms for spherical computational geometry. The library was written in C and used GL for graphical display on an SGI workstation. The three basic algorithms included were hemisphericity (finding a bounding hemisphere for a set of points), hemisphere intersection (analogous to half-plane intersection in E²), and spherical convex hull. These algorithms were used in an application that computed directions of visibility for the surfaces of non-convex polyhedra, an operation that is useful in the context of numerically-controlled machining.