“An interactive tool for placing curved surfaces without interpenetration” by Snyder

We present a surface representation and a set of algorithms that allow interactive placement of curved parametric objects without interpenetration. Using these algorithms, a modeler can place an object within or on top of other objects, find a stable placement for it, and slide it into new stable placements. Novel algorithms are presented to track points of contact between bodies, detect new points of contact, and delete vanishing contacts. Interactive speeds are maintained even when the moving body touches several bodies at many contact points. We describe a new algorithm that quickly brings a body into a stable configuration with respect to a set of external forces, subject to the constraint that it not penetrate a set of fixed bodies. This algorithm is made possible by sacrificing the requirement that a body behave physically over time. Intuitive control is still achieved by making incremental, “pseudo-physical” changes to the body’s placement, while enforcing the non-interpenetration constraint after each change.

1. Baraff, David, “Curved Surfaces and Coherence for Non-penetrating Rigid Body Simulation,” Computer Graphics, 24(4), pp. 19-28, August 1990.
2. Baraff, David, “Coping with Friction for Non-penetrating Rigid Body Simulation,” Computer Graphics, 25(4), pp. 31-39, July 1991.
3. Baraff, David, “Fast Contact Force Computation for Nonpenetrating Rigid Bodies,” Computer Graphics, 28(2), pp. 23-42, July 1994.
4. Barzel, Ronen, and A. Barr, “A Modeling System Based On Dynamic Constraints,” Computer Graphics, 22(4), pp. 179-188, August 1988.
5. Garcia-Alonso, Alejandro, N. Serrano, and J. Flaquer, “Solving the Collision Detection Problem,” IEEE Computer Graphics and Applications, pp. 36-43, May 1994.
6. Kay, Tim, and K. Kajiya, “Ray Tracing Complex Scenes,” Computer Graphics, 20(4), pp. 269-278, August 1986.
7. Gleicher, Michael, and A. Witkin, “Through-the-Lens Camera Control,” Computer Graphics, 26(2), pp. 331-340, July 1992.
8. Metaxas, Dimitri, and D. Terzopoulos, “Dynamic Deformation of Solid Primitives with Constraints,” Computer Graphics, 26(2), pp. 309-312, July 1992.
9. Moore, M. and Wilhelms, J., “Collision Detection and Response for Computer Animation,” Computer Graphics, 22(4), pp. 289-298, August 1988.
10. Press, W. H., B. R Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes, Cambridge University Press, Cambridge, England, 1986.
11. Sclaroff, Stan, and A. Pentland, “Generalized Implicit Functions for Computer Graphics,” Computer Graphics, 25(4), pp. 247-250, July 1991.
12. Snyder, John, and J. Kajiya, “Generative Modeling: A Symbolic System for Geometric Modeling,” Computer Graphics, 26(2), pp. 369-378, July 1992.
13. Snyder, John, A. Woodbury, K. Fleischer, B. Currin, and A. Barr, “Interval Methods for Multi-point Collisions between Time-Dependent Curved Surfaces”, Computer Graphics, 27(2), pp. 321-334, Aug. 1993.
14. Witkin, Andrew, K. Fleischer, and A. Barr, “Energy Constraints on Parameterized Models,” Computer Graphics, 21 (4), pp. 225-232, July 1987.