Computational Geometry Seminar

A promising approach for achieving a better division of labor between user and computer is inverse design: the user states declaratively the criteria for a good graphic or animation, and the computer finds one, usually by means of heuristic optimization. Although this idea has proven very successful for some problems, it is not a panacea. In this talk I will present a selection of design tasks (all with a computational-geometry flavor) to which we have applied the inverse-design approach. These tasks include text placement in maps and diagrams, motion synthesis for articulated-figure and multibody animations, and object-model generation. These examples serve to illustrate why some graphics problems are more amenable to inverse design than others.

I will also describe a general alternative to inverse design that we have developed, called Design Galleries. In this approach, the computer tries to generate an optimal selection of graphics (typically several hundred of them), not just a single optimal graphic as in inverse design. Computational geometry is central to the Design-Gallery concept: the notion of an optimal selection is related to notions of geometric covering in high-dimensional spaces, and the visual organization of hundreds of design alternatives for browsing by the user is facilitated by graph drawing. I will show Design Galleries for several difficult graphics-design problems: light selection and placement for image rendering, transfer-function specification for volume rendering, and motion synthesis for animation. Design Galleries appear to be most useful when the application of inverse design is problematic.

Joint work with B. Andalman, P. Beardsley, J. Christensen, S. Edmondson, D. Feinberg, W. Freeman, S. Gibson, J. Hodgins, T. Kang, B. Mirtich, J.T. Ngo, H. Pfister, W. Ruml, K. Ryall, J. Seims, S. Shieber, M. Sosa, D. Tang.