Solution space navigation for geometric constraint systems

Abstract

We study the well documented problem of systematically navigating the potentially exponentially many roots or realizations of well-constrained, variational geometric constraint systems. We give a scalable method called the Equation and Solution Manager (ESM) that can be used both for automatic searches and visual, user-driven searches for desired realizations. The method incrementally assembles the desired solution of the entire system and avoids combinatorial explosion by offering the user a visual walk-through of the solutions to recursively constructed subsystems and by permitting the user to make gradual, adaptive solution choices.We isolate requirements on companion methods that are essential and desirable for efficient, meaningful solution space navigation. Specifically, they permit (a) incorporation of many existing approaches to solution space steering or navigation into the ESM; and (b) integration of the ESM into a standard geometric constraint solver architecture. We address the latter challenge and explain how the integration is achieved. Additionally, we sketch the ESM implementation as part of an opensource, 2D and 3D geometric constraint solver, FRONTIER.

References

1. Bettig, B. and Shah, A. 2003. Solution selectors: A user oriented answer to the multiple solution problem in constraint solving. J. Mechan. Design 125, 3, 445--451.]]
2. Bjorner, A., Vergnas, M. L., Sturmfels, B., White, N., and Ziegler, G. 1993. Oriented Matroids. Encyclopaedia of Mathematics. vol. 46. G-C. Rota, Ed. Cambridge University Press.]]
3. Bouma, W., Fudos, I., Hoffmann, C. M., Cai, J., and Paige, R. 1995. A geometric constraint solver. Comput. Aided Design 27, 487--501.]]
4. Bruderlin, B. 1986. Constructing three-dimensional geometric object defined by constraints. In ACM SIGGRAPH. Chapel Hill, NC.]]
5. Crapo, H. 1979. Structural rigidity. Structural Topology 1, 26--45.]]
6. Crapo, H. 1982. The tetrahedral-octahedral truss. Structural Topology 7, 52--61.]]
7. Fudos, I. 1995. Constraint solving for computer aided design. Ph.D. thesis, Department of Computer Sciences, Purdue University.]]
8. Fudos, I. and Hoffmann, C. M. 1996. Correctness proof of a geometric constraint solver. J. Comp. Geomet. Appl. 6, 405--420.]]
9. Fudos, I. and Hoffmann, C. M. 1997. A graph-constructive approach to solving systems of geometric constraints. ACM Trans. Graph. 10, 2, 179--216.]]
10. Gaukel, J. 2003. Effiziente losung polynomialer und nichtpolynomialer gleichungssysteme mit hilfe von subdivisionsalgorithmen. Ph.D. thesis, Department of Mathematics, Technical University of Darmstadt, Germany.]]
11. Graver, J. E., Servatius, B., and Servatius, H. 1993. Combinatorial Rigidity. American Mathematical Society.]]
12. Hendrickson, B. 1992. Conditions for unique graph realizations. SIAM J. Comput. 21, 65--84.]]
13. Hoffmann, C., Sitharam, M., and Yuan, B. 2004. Making constraint solvers more useable: the overconstraint problem. Comput. Aided Design, to appear.]]
14. Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 1997. Finding solvable subsets of constraint graphs. In Lecture Notes in Computer Science, vol. 1330, 463--477.]]
15. Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 1998a. Geometric constraint decomposition. In Geometric Constraint Solving, B. Bruderlin and D. Roller, Eds. Springer-Verlag.]]
16. Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 1998b. Geometric constraint decomposition. In Geometric Constraint Solving, B. Bruderlin and D. Roller Eds, Springer Verlag. Eds. 170--195.]]
17. Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 1999. Planning geometric constraint decompositions via graph transformations. In Lecture Notes in Computer Science, vol. 1779. Springer Verlag, 309--324.]]
18. Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 2001a. Decomposition of geometric constraints systems, part i: Performance measures. J. Symb. Comput. 31, 4.]]
19. Hoffmann, C. M., Lomonosov, A., and Sitharam, M. 2001b. Decomposition of geometric constraints systems, part ii: New algorithms. J. Symb. Comput. 31, 4.]]
20. Joan-Arinyo, R., Luzon, M., and Soto, A. 2003. Genetic algorithms for root multiselection in geometric constraint solving. Comput. Graph. 27, 1, 51--60.]]
21. Kohareswaran, N. 2003. Design of a 3d graphical user interface for frontier, a geometric constraint solver graphs. M. thesis. University of Florida, Department of Computer and Information Science, Gainesville, FL.]]
22. Kramer, G. 1992. Solving Geometric Constraint Systems. MIT Press.]]
23. Laman, G. 1970. On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331--340.]]
24. Lomonosov, A. 2004. Graph and Combinatorial Analysis for Geometric Constraint Graphs. Tech. rep., Ph.D thesis, Department of Computer and Information Science, University of Florida, Gainesville, FL.]]
25. Lomonosov, A. and Sitharam, M. 2004. Graph algorithms for geometric constraint solving. Based on Lomonosov's Univ Florida PhD Thesis, 2004. Submitted for publication. Available on request from [email protected].]]
26. Oung, J. J., Sitharam, M., Moro, B., and Arbree, A. 2001. Frontier: Fully enabling geometric constraints for feature based design and assembly. In Proceedings of the ACM Solid Modeling Conference.]]
27. Owen, J. D-cubed commercial geometric constraint solving software. www.d-cubed.co.uk/.]]
28. Sitharam, M. 2004a. Frontier, an opensource 3d geometric constraint solver: algorithms and architecture. Monograph, in preparation. www.cise.ufl.edu/~sitharam/partone.pdf. and /partwo.pdf.]]
29. Sitharam, M. 2004b. Frontier, opensource gnu geometric constraint solver: Version 1 (2001) for general 2d systems; version 2 (2002) for 2d and some 3d systems; version 3 (2003) for general 2d and 3d systems. In http://www.cise.ufl.edu/~sitharam, http://www.gnu.org.]]
30. Sitharam, M. 2004c. Combinatorial approaches to geometric constraint solving: problems, progress and directions. In AMS-DIMACS (volume on Computer Aided Design and Manufacturing), D. Dutta, R. Janardhan, and M. Smid, Eds. vol. 67, 117--163.]]
31. Sitharam, M., Oung, J., Zhou, Y., and Arbree, A. 2006. Geometric constraints within feature hierarchies. J. Comput. Aided Design 38, 1, 22--38.]]
32. Sitharam, M., Peters, J., and Zhou, Y. 2004. Solving minimal, wellconstrained, 3d geometric constraint systems: combinatorial optimization of algebraic complexity.]]
33. Sitharam, M. and Zhou, Y. 2004. A tractable, approximate, combinatorial 3d rigidity characterization. 5th Automated Deduction in Geometry (ADG).]]
34. Sitharam, M. 2006. Characterizing well-formed systems on incidences for resolving collections of rigid bodies. UCGA Geometric Constraints. To appear. www.cise.ufl.edu/~sitharam/overlap-new.pdf.]]
35. Whiteley, W. 1997. Rigidity and scene analysis. In Handbook of Discrete and Computational Geometry. CRC Press, 893 --916.]]

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Engineering

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry