“Interactive physically-based manipulation of discrete/continuous models” by Harada, Witkin and Baraff

Physically-based modeling has been used in the past to support a variety of interactive modeling tasks including free-form surface design, mechanism design, constrained drawing, and interactive camera control. In these systems, the user interacts with the model by exerting virtual forces, to which the system responds subject to the active constraints. In the past, this kind of interaction has been applicable only to models that are governed by continuous parameters. In this paper we present an extension to mixed continuous/discrete models, emphasizing constrained layout problems that arise in architecture and other domains. When the object being dragged is blocked from further motion by geometric constraints, a local discrete search is triggered, during which transformations such as swapping of adjacent objects may be performed. The result of the search is a “nearby” state in which the target object has been moved in the indicated direction and in which all constraints are satisfied. The transition to this state is portrayed using simple but effective animated visual effects. Following the transition, continuous dragging is resumed. The resulting seamless transitions between discrete and continuous manipulation allow the user to easily explore the mixed design space just by dragging objects. We demonstrate the method in application to architectural floor plan design, circuit board layout, art analysis, and page layout.

1. David Baraff. Analytical methods for dynamic simulation of non-penetrating rigid bodies. Computer Graphics (Proc. SIG- GRAPH), 23:223-232, 1989.]]
2. David Baraff. Fast contact force computation for nonpenetrating rigid bodies. Computer Graphics (Proc. SIGGRAPH), 28:23-34, 1994.]]
3. David Baraff. Interactive simulation of solid rigid bodies. IEEE Computer Graphics and Applications, 15:63-75, 1995.]]
4. Christopher Carlson. Structure grammars and their application to design. Technical Report EDRC-01-09-89, Engineering Design Research Center, Carnegie Mellon University, Pittsburgh, PA, 1989.]]
5. George Celniker and Dave Gossard. Deformable curve and surface finite-elements for free-form shape design. Computer Graphics, 25(4), July 1991. Proceedings SIGGRAPH ’91.]]
6. Ulrich Flemming. Wall representations of rectangular dissections and their use in automated space allocation. Environment and Planning B: Planning and Design, 5:215-232, 1978.]]
7. Ulrich Flemming. More than the sum of parts: the grammar of Queen Anne houses. Environment and Planning B: Planning and Design, 14:323-350, 1987.]]
8. Ulrich Flemming and Robert F. Coyne. A design system with multiple abstraction capabilities. InAvignon ’90: Tools, Techniques & Applications, volume 1, pages 107-122. EC2, 1990.]]
9. Philip E. Gill, Walter Murray, Michael A. Saunders, and Margaret H. Wright. User’s guide for NPSOL (version 4.0): A fortran package for nonlinear programming. Technical Report SOL 86-2, Stanford University, Stanford, California, 1986.]]
10. Michael Gleicher and Andrew Witkin. Through-the-lens camera control. Computer Graphics, 26, 1992. Proc. Siggraph ’92.]]
11. Michael Gleicher and Andrew Witkin. Drawing with constraints. The Visual Computer, 1994.]]
12. John Grason. Methods for the computer-implemented solution of a class of “floorplan”. PhD thesis, Department of Electrical Engineering, Carnegie Mellon University, 1970.]]
13. Jeff Heisserman. Generative geometric design and boundary solid grammars. PhD thesis, Department of Architecture, Carnegie Mellon University, 1991.]]
14. Michael Kass, Andrew Witkin, and Demetri Terzopoulos. Snakes: Active contour models. Int. J. of Computer Vision, 1(4), 1987.]]
15. Terry W. Knight. Designing with grammars. In Gerhard N. Schmitt, editor, CAAD Futures ’91 Proceedings, pages 19-34, 1991.]]
16. T.W. Knight. Transformations of De Stijl art: the paintings of Georges Vantongerloo and Fritz Glarner. Environment and Planning B: Planning and Design, 16:51-98, 1989.]]
17. H. Koning and J. Eizenberg. The language of the prairie: Frank Lloyd Wright’s prairie houses. Environment and Planning B: Planning and Design, 8:295-323, 1981.]]
18. Sukhamay Kundu. The equivalence of the subregion representation and the wall representation for a certain class of rectangular dissections. Communications of the ACM, 31(6):752- 763, 1988.]]
19. Cornelius Lanczos. The Variational Principles of Mechanics. Dover Publications, Inc., 1970.]]
20. David E LaPotin. Mason: A global floor-planning approach for VLSI design. Technical Report IBMC-11657, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, January 1986.]]
21. William J. Mitchell, Robin S. Ligget, Spiro N. Pollalis, and Milton Tan. Integrating shape grammars and design analysis. In CAAD futures ’91 proceedings, pages 1-18, 1991.]]
22. W.J. Mitchell, J.E Steadman, and Robin S. Ligget. Synthesis and optimization of small rectangular floor plans. Environment and Planning B: Planning and Design, 3(1):37-70, 1976.]]
23. Herbert A. Simon. Style in design. In Charles M. Eastman, editor, Spatial Synthesis in Computer-Aided Building Design, chapter 9, pages 287-309. Applied Science Publishers LTD, Ripple Road, Barking, Essex, England, 1975.]]
24. G. Stiny. Introduction to shape and shape grammars. Environment and Planning B: Planning and Design, 7(3):343-351, 1980.]]
25. G. Stiny and J. Gips. Shape grammars and the generative specification of painting and sculpture. Information Processing, pages 1460-1465, 1972.]]
26. G. Stiny and W.J. Mitchell. The Palladian grammar. Environmerit and Planning B: Planning and Design, 5(1):5-18, 1978.]]
27. Mark C. Surles. An algorithm with linear complexity for interactive, physically-based modeling of large proteins. In Edwin E. Catmull, editor, Computer Graphics (SIGGRAPH ’92 Proceedings), volume 26, pages 221-230, July 1992.]]
28. Demetri Terzopoulos, Andrew Witkin, and Michael Kass. Energy constraints on deformable models: recovering shape and non-rigid motion. In Proc. AAAI-87, Seattle, 1987.]]
29. Demetri Terzopoulos, Andrew Witkin, and Michael Kass. Symmetry-seeking models for 3D object reconstruction. International Journal of Computer Vision, 3(1), 1987.]]
30. Jeffrey A. Thingvold and Elaine Cohen. Physical modeling with B-spline surfaces for interactive design and animation. Computer Graphics, 24(2):129-138, March 1990.]]
31. William Welch and Andrew Witkin. Variational surface modeling. Computer Graphics, 26, 1992. Proc. Siggraph ’92.]]
32. Andrew Witkin, Michael Gleicher, and William Welch. Interactive dynamics. Computer Graphics, 24(2):11-21, March 1990. Proc. 1990 Symposium on 3-D Interactive Graphics.]]
33. Andrew Witkin and William Welch. Fast animation and control of non-rigid structures. Computer Graphics, 24(4):243- 252, July 1990. Proc. Siggraph ’90.]]
34. D.F. Wong, H.W. Leong, and C.L. Liu. Simulated Annealing for VLSI Design. Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell, Massachusetts 02061, 1988.]]
35. Lin S. Woo, C.K. Wong, and D.T. Tang. Pioneer: a macrobased floor-planning design system. VLSI System Design, pages 32-43, August 1986.]]