A graph-constructive approach to solving systems of geometric constraints

ABSTRACT

A graph-constructive approach to solving systems of geometric constraints capable of effeciently handling well-constrained, overconstrained, and underconstrained configurations is presented. The geometric constraint solver works in two phases: in the analysis phase the constraint graph is analyzed and a sequence of elementary construction steps is derived, and then in the construction phase the sequence of construction steps in actually carried out. The analysis phase of the algorithm is described in detail, its correctness is proved, and an efficient algorith to realized it is presented. The scope of the graph analysis is then extended by utilizing semantic information in the form of anlge derivations, and by extending the repertoire of the construction steps. Finally, the construction phase is briefly discussed.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: AIT-AOUDIA, S., JEGOU, R., AND MICHELUCCI, D. 1993. Reduction of constraint systems. In Proceedings of Cornpugraphics, (A1vor, Portugal), 83-92.
• 3: B. Aldefeld, Variation of geometrics based on a geometric-reasoning method, Computer-Aided Design, v.20 n.3, p.117-126, April, 1988 [doi>10.1016/0010-4485(88)90019-X]
• 4: BLUM, L., SCHUB, M., AND SMALE, S. 1989. On a theory of computation and complexity over the real numbers: NP-Completeness, recursive functions and universal machines. Bull. Am. Math. Soc. (New Series) 21, 1-46.
• 5: BOUMA, W., FUDOS, I., HOFFMANN, C. M., CAI, J., AND PAIGE, R. 1995. A geometric constraint solver. Cornput. Aided Des. 27, 6 (June), 487-501. Also available through http://www.cs.purdue.edu/people/fudos.
• 6: Beat Brüderlin, Constructing three-dimensional geometric objects defined by constraints, Proceedings of the 1986 workshop on Interactive 3D graphics, p.111-129, January 1987, Chapel Hill, North Carolina, United States [doi>10.1145/319120.319130]
• 7: CRIPPEN, G. M. AND HAVEL, T. F. 1988. Distance Geometry and Molecular Conformation. Research Studies Press, Wiley, New York.
• 8: CUCKER, F. AND MATAMALA, M. 1997. On digital nondeterminism. Preprint.
• 9: Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 10: Andreas W. M. Dress , Timothy F. Havel, Shortest-path problems and molecular conformation, Discrete Applied Mathematics, v.19 n.1-3, p.129-144, March 1988 [doi>10.1016/0166-218X(88)90009-1]
• 11: FUDOS, I. AND HOFFMANN, C.M. 1995. Correctness proof of a geometric constraint solver. Int. J. Cornput. Geom. Appl. Also available through http://www.cs.purdue.edu/people/fudos.
• 12: FUDOS, I. 1993. Editable representations for 2D geometric design. Master's Thesis, Dept. of Computer Sciences, Purdue Univ., Dec. Available through http://www.cs.purdue.edu/people/ fudos.
• 13: Ioannis Fudos , Christoph M. Hoffmann, Constraint solving for computer-aided design, 1995
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: GOSLING, J. 1983. Algebraic constraints. Tech. Rep. CMU-CS-83-132, CMU.
• 16: HILBERT, D. 1956. Grundlagen der Geornetrie. B. G. Teubner, Stuttgart.
• 17: HOFFMANN, C. M. 1993. On the semantics of generative geometry representations. In Proceedings of the 19th ASME Design Automation Conference, Vol. 2, 411-420.
• 18: Christoph M. Hoffmann , Robert Juan, Erep: An editable, high-level representation for geometric design and analysis, Selected and Expanded Papers from the IFIP TC5/WG5.2 Working Conference on Geometric Modeling for Product Realization, p.129-164, September 27-October 01, 1992
• 19: HOPCROFT, J. E. AND TARJAN, R.E. 1973. Dividing a graph into triconnected components. SIAM J. Cornput. 2, 3, 135-158.
• 20: IMAI, H. 1985. On combinatorial structures of line drawings of polyhedra. Discrete Appl. Math. 10, 79.
• 21: ITAI, A. AND RODEH, M. 1978. Finding a minimum circuit in a graph. SIAM J. Cornput. 7, 4, 413-423.
• 22: JUAN-ARINYO, R. AND SOTO, A. 1995. A rule-constructive geometric constraint solver. Tech. Rep. LSI-95-25-R, Univ. Politecnica de Catalunya.
• 23: K_RAMER, G.A. 1992. Solving Geometric Constraints Systems: A Case Study in Kinematics. MIT Press, Cambridge, MA.
• 24: LIGHT, R. AND GOSSARD, D. 1982. Modification of geometric models through variational geometry. Cornput. Aided Des. 14, 4 (July), 209-214.
• 25: MACLANE, S. 1937. A structural characterization of planar combinatorial graphs. Duke Math. J. 3, 460-472.
• 26: MONIEN, B. 1983. The complexity of determining a shortest cycle of even length. Computing 31,355-369.
• 27: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 28: J. C. Owen, Algebraic solution for geometry from dimensional constraints, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.397-407, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112573]
• 29: OWEN, J.C. 1993. Constraints on simple geometry in two and three dimensions. In Third SIAM Conference on Geometric Design, (Nov.). Int. J. Comput. Geom. Appl. (to appear).
• 30: D. Roller , F. Schonek , A. Verroust, Dimension-driven geometry in CAD: a survey, Theory and practice of geometric modeling, Springer-Verlag New York, Inc., New York, NY, 1989
• 31: Barry K. Rosen, Tree-Manipulating Systems and Church-Rosser Theorems, Journal of the ACM (JACM), v.20 n.1, p.160-187, Jan. 1973 [doi>10.1145/321738.321750]
• 32: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 33: SERRANO, D. AND GOSSARD, D. 1986. Combining mathematical models and geometric models in CAE systems. In Proceedings of ASME Computers in Engineering Conference, (Chicago, July), ASME, 277-284.
• 34: SUGIHARA, Z. 1985. Detection of structural inconsistencies in systems of equations with degrees of freedom and its applications. Discrete Appl. Math. 10, 297-312.
• 35: SUNDE, G. 1988. Specification of shape by dimensions and other geometric constraints. In Geometric Modeling for CAD Applications, M. J. Wozny, H. W. McLaughlin, and J. L. Encarnacao, Eds., North Holland, Amsterdam, 199-213.
• 36: SUTHERLAND, I. 1963. Sketchpad, a man-machine graphical communication system. In Proceedings of the Spring Joint Computer Conference, IFIPS, 329-345.
• 37: SUZUKI, H., ANDO, H., AND KIMURA, F. 1990. Variation of geometries based on a geometricreasoning method. Comput. Graph. 14, 2, 211-224.
• 38: TARJAN, R.E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 146-159.
• 39: VERROUST, A., SCHONEK, F., AND ROLLER, D. 1992. Rule-oriented method for parameterized computer-aided design. Comput. Aided Des. 24, 3 (Oct.), 531-540.
• 40: YAMAGUCHI, Y. AND KIMURA, F. 1990. A constraint modeling system for variational geometry. In Geometric Modeling for Product Engineering, M. J. Wozny, J. U. Turner, and K. Preiss, Eds., Elsevier Science (North Holland), Amsterdam, 221-233.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
complexity, constraint solving, geometric constraints, graph-based constraint solvers, underconstrained systems