Three Applications of Optimization in Computer Graphics

Jeffrey Smith
doctoral dissertation, tech. report CMU-RI-TR-03-15, Robotics Institute, Carnegie Mellon University, May, 2003

  • Adobe portable document format (pdf) (5MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

This thesis addresses the application of nonlinear optimization to three different problems in computer graphics: the generation of gait cycles for legged creatures, the generation of models of truss structures, and the generation of models of constant mean curvature structures.

We first present work on the automatic motion generation for legged creatures. Our technique is a reformulation of spacetime optimization, which has been used in the past to semi-automatically generate realistic, physically-based motion of simple articulated characters. Our approach poses the task of motion sythesis as the process of solving a large, constrained nonlinear optimization problem. The objective function of these problems is a measure of consumed energy, and the constraints are a combination of the laws of physics and a high-level description of the motion we wish to see. Our technique replaces the Newtonian constraints that previous techniques have used to enforce physical realism with a dynamic simulation, which makes the spacetime constraints framework more flexible and potentially more powerful.

We then present a method for designing truss structures, a common and complex category of buildings, using non-linear optimization. Truss structures are ubiquitous in the industrialized world, appearing as bridges, towers, roof supports and building exoskeletons, yet are complex enough that modeling them by hand is time consuming and tedious. We represent trusses as a set of rigid bars connected by pin joints, which may change location during optimization. By including the location of the joints as well as the strength of individual beams in our design variables, we can simultaneously optimize the geometry and the mass of structures.

In the third section of this thesis, we present a method for creating models of surface-area minimizing, constant mean curvature objects. Constant mean curvature objects, which include such diverse natural and man-made structures as thin-film membranes, sails, pneumatic structures, and soap bubbles and films, are both common and often difficult to create by hand. Using techniques of constrained non-linear optimization, we can automatically generate models of these structures, typically minimizing surface area while maintaining a constant mean curvature over the whole surface in addition to volume or other geometric constraints.

We conclude this thesis with a discussion of the advantages and shortcomings of optimization as a technique for solving modeling and animation problems in computer graphics.


Text Reference
Jeffrey Smith, "Three Applications of Optimization in Computer Graphics," doctoral dissertation, tech. report CMU-RI-TR-03-15, Robotics Institute, Carnegie Mellon University, May, 2003

BibTeX Reference
   author = "Jeffrey Smith",
   title = "Three Applications of Optimization in Computer Graphics",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "May",
   year = "2003",
   number= "CMU-RI-TR-03-15",
   address= "Pittsburgh, PA",