Nathan Hurst
ABSTRACT
Current constraint solving techniques for interactive graphical applications cannot satisfactorily handle constraints such as non-overlap, or containment within non-convex shapes or shapes with smooth edges. We present a generic new technique for efficiently handling such kinds of constraints based on trust regions and linear arithmetic constraint solving. Our approach is to model these more complex constraints by a dynamically changing conjunction of linear constraints. At each stage, these give a local approximation to the complex constraints. During direct manipulation, linear constraints in the current local approximation can become active indicating that the current solution is on the boundary of the trust region for the approximation. The associated complex constraint is notified and it may choose to modify the current linear approximation. Empirical evaluation demonstrates that it is possible to (re-)solve systems of linear constraints that are dynamically approximating complex constraints such as non-overlap sufficiently quickly to support direct manipulation in interactive graphical applications.
- D. Baraff. Fast contact force computation for nonpenetrating rigid bodies. In SIGGRAPH '94 Conference Proceedings, pages 23-32, 1994. ACM.]] Google Scholar
Digital Library
- A. Borning, B. Benson, and M. Wilson. Constraint hierarchies. Lisp and Symbolic Computation, 5(3):223-270, September 1992.]] Google ScholarDigital Library
- A. Borning, K. Marriott, P. Stuckey, and Yi Xiao. Solving linear arithmetic constraints for user interface applications. In Proceedings of the 1997 ACM Symposium on User Interface Software and Technology, New York, October 1997. ACM.]] Google ScholarDigital Library
- R. Fletcher. Practical Methods of Optimization. John Wiley & Sons, 1987.]] Google ScholarDigital Library
- I. Fudos. Geometric Constraint Solving. PhD thesis, Purdue University, Dept. of Computer Sciences, 1995.]]Google Scholar
- M. Harada, A. Witkin, and D. Baraff. Interactive physically-based manipulation of discrete/continuous models. In SIGGRAPH '95 Conference Proceedings, pages 199-208, Los Angeles, August 1995. ACM.]] Google ScholarDigital Library
- A. Heydon and G. Nelson. The Juno-2 constraint-based drawing editor. Technical Report 131a, DEC Systems Research Center, Palo Alto, CA, 1994.]]Google Scholar
- H. Hosobe. A modular geometric constraint solver for user interface applications. In Proceedings of the 1999 ACM Conference on User Interface Software and Technology, New York, November 2001. ACM.]] Google ScholarDigital Library
- G. Kramer. A geometric constraint engine. Artificial Intelligence, 58(1-3):327-360, December 1992.]] Google ScholarDigital Library
- M. Lin and S. Gottschalk. Collision detection between geometric models: A survey. In IMA Conference on Mathematics of Surfaces, 1998.]]Google Scholar
- K. Marriott, S.S. Chok, and A. Finlay. A tableau based constraint solving toolkit for interactive graphical applications. In International Conference on Principles and Practice of Constraint Programming (CP98), pages 340-354, 1998.]] Google ScholarDigital Library
- K. Marriott, P. Moulder, P. Stuckey, and A. Borning. Solving disjunctive constraints for interactive graphical applications. In International Conference on Principles and Practice of Constraint Programming (CP01), 2001.]] Google ScholarDigital Library
- K. Marriott and P. Stuckey. Programming with Constraints: An Introduction. MIT Press, 1998.]]Google ScholarCross Ref
- G. Nelson. Juno, a constraint-based graphics system. In SIGGRAPH '85 Conference Proceedings, pages 235-243, San Francisco, July 1985. ACM.]] Google ScholarDigital Library
- H. Samet. Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods. Addison Wesley, 1989.]]Google Scholar
- M. Sannella, J. Maloney, B. Freeman-Benson, and A. Borning. Multi-way versus one-way constraints in user interfaces: Experience with the DeltaBlue algorithm. Software---Practice and Experience, 23(5):529-566, May 1993.]] Google ScholarDigital Library
- I. Sutherland. Sketchpad: A Man-Machine Graphical Communication System. PhD thesis, Dept. of Electrical Engineering, MIT, January 1963.]]Google Scholar
- B. Vander Zanden. An incremental algorithm for satisfying hierarchies of multi-way dataflow constraints. ACM Transactions on Programming Languages and Systems, 18(1):30-72, January 1996.]] Google ScholarDigital Library
Index Terms
- Dynamic approximation of complex graphical constraints by linear constraints
Recommendations
On tree-preserving constraints
The study of tractable subclasses of constraint satisfaction problems is a central topic in constraint solving. Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex ...
Conic approximation to quadratic optimization with linear complementarity constraints
This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same ...
Constraints for Interactive Graphical Applications
CP '02: Proceedings of the 6th International Conference on Principles and Practice of Constraint ProgrammingConstraints have been used in interactive graphical applications since Sketchpad in the early 60's [8]. Constraints in this domain, as in others, provide a declarative way for the user to specify what is desired rather than how to achieve it. Two ...
Comments