Numerical constrained optimization is an important tool with extensive applications in computer graphics and many other diverse fields. In computer animation, for example, constrained optimization has been used for finding initial conditions, smoothing or finishing motion paths, interpolating orientations, animating flexible bodies, self-assembly of objects, and finding boundaries. An ideal problem for constrained optimization is one that has a single measure defining the quality of a solution plus some requirements upon that solution that must not be violated. The quality measure is called the objective function; the requirements are called constraints. A constrained optimization solver maximizes (or minimizes) the objective function while satisfying the constraints. In this report, we propose a new method for constraint handling that can be applied to established optimization algorithms and which significantly improves their ability to traverse through constrained space. To make the presentation concrete, we apply the new constraint method to the Nelder and Mead polytope algorithm. The resulting technique, called SPIDER, has shown great initial promise for solving difficult (e.g., nonlinear, nondifferentiable, noisy) constrained problems.
Where: ACM SIGGRAPH
MERL Contacts: Ronald Perry; Jeroen van BaarBrief
Date: August 12, 2001
- The papers "Computing 3D Geometry Directly from Range Images" by Frisken, S.F. and Perry, R.N., "A New Method for Numerical Constrained Optimization" by Perry, R.N., "Dynamic Meshing Using Adaptively Sampled Distance Fields" by Pope, J., Frisken, S.F. and Perry, R.N., "Shadermaps: A Method for Accelerating Procedural Shading" by Jones, T.R., Perry, R.N. and Callahan, M., "A Computationally Efficient Framework for Modeling Soft Body Impact" by Frisken, S.F. and Perry, R.N., "Kizamu: A System for Sculpting Digital Characters" by Perry, R.N. and Frisken, S.F. and "Surface Splatting" by Zwicker, M., Pfister, H., van Baar, J. and Gross, M. were presented at ACM SIGGRAPH.