An algorithm with linear complexity for interactive, physically-based modeling of large proteins
Mark C. Surles · 1992
Physically-based modeling applications usually require batch processing for each frame of an animation or simulation.This paper describes a graphics modeling system, called Sculpr, that maintains physically-valid protein properties while a user interactively moves atoms.Sculpt models stiff properties such as bond lengths and angles as rigid constraints and models weak properties such as non-bonded interactions as potential energies.Sculpr continually satisfies the constraints and maintains a local energy minimum throughout user interaction.On a Silicon Graphics 240-GTX, Sculpt maintains 1,9 updates per second on a molecular model with 355 atoms ( 1065 variables, 1027 constraints, and 3465 potential energies).Performance decreases /r'nearly with increased problem size.This paper presents a Lagrange multiplier method with linear computational complexity that finds a constrained minimum for articulated figures with many more joints in their spines than in any limb (e.g.reptiles, mammals, and proteins).The method computes the Jacobian matrix of the constraints and solves a system of linear equations that results from muhiplying the Jacobian by its transpose.The paper proves that a sort of the Jacobian yields a band-diagonal pattern of nonzeros.The pattern does not change during a modeling session, so the sort can run during a pre-processing step.Multiplication and solution of band-diagonal matrices require computation that increases linearly with problem size.Previous applications of Lagrange multipliers to constrained, physically-based modeling did not take advantage of the constraint connectivity in the spine.They either required many iterations of a linear algorithm or few iterations of a quadratic algorithm for each frame of a simulation.This application finds a constrained minimum with a linear algorithm in a few iterations.Additionally, most of the algorithm's steps execute in parallel for increased performance, CR