Combining symbolic and numerical solvers to simplify indecomposable systems solving

ABSTRACT

In Computer-Aided Design, solvers always attempt to decompose geometric constraint systems into smaller ones in order to make faster the resolution. However, this scheme often fails in the case of 3D geometric constraint systems since they are hardly decomposable. We have studied a new method which uses jointly two solvers, a symbolic one and a numerical one, in order to solve a system S: system S is transformed into a parametric system S' "almost" equivalent to S and such that system S" is symbolically solvable and the numerical solver computes solutions of S from solutions of S".

REFERENCES

• 1: B. Aldefeld, H. Malberg, H. Richter, and K. Voss. Rule-based variational geometry in computer-aided design, pages 27--46. (D. T. Pham ed.), Springer-Verlag, 1992.
• 2: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry, Springer-Verlag, New York, 1998.
• 3: Jean-François Dufourd , Pascal Mathis , Pascal Schreck, Geometric construction by assembling solved subfigures, Artificial Intelligence, v.99 n.1, p.73-119, Feb. 1998 [doi>10.1016/S0004-3702(97)00070-2]
• 4: Ioannis Fudos , Christoph M. Hoffmann, A graph-constructive approach to solving systems of geometric constraints, ACM Transactions on Graphics (TOG), v.16 n.2, p.179-216, April 1997 [doi>10.1145/248210.248223]
• 5: Xiao-Shan Gao , Christoph M. Hoffmann , Wei-Qiang Yang, Solving spatial basic geometric constraint configurations with locus intersection, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566299]
• 6: X.-S, Gao, C. M. Hoffmann, and W.-Q. Yang. Solving spatial basic geometric constraint configurations with locus intersection. Computer-Aided Design, 36:111--122, 2004.
• 7: Decomposition plans for geometric constraint systems, part I: performance measures for CAD, Journal of Symbolic Computation, v.31 n.4, p.367-408, April 1, 2001 [doi>10.1006/jsco.2000.0402]
• 8: R. Joan-Arinyo , A. Soto-Riera, Combining constructive and equational geometric constraint-solving techniques, ACM Transactions on Graphics (TOG), v.18 n.1, p.35-55, Jan. 1999 [doi>10.1145/300776.300780]
• 9: H. Lamure and D. Michelucci. Qualitative study of geometric constraints. In Geometric Constraint Solving and Applications, pages 234--258. Springer, 1998.
• 10: V. C. Lin , D. C. Gossard , R. A. Light, Variational geometry in computer-aided design, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.171-177, August 1981
• 11: D. Michelucci and S. Foufou. The witness configuration method. Computer-Aided Design, 38(4):284--299, 2006.
• 12: 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]
• 13: P. Schreck, J.-F. Dufourd, and P. Mathis. Using a numerical tool in a formal construction method with decomposition. In Proceedings of 2th International Conference on Computer Graphics and Artificial Intelligence, Limoges, France, 1998.
• 14: G. Sunde. Specification of shape by dimensions and other geometric constraints. In Proceedings of the Eurographics Workshop on Intelligent CAD systems, Noordwisjkeroul, 1987.
• 15: W. Wu. Basic principles of mechanical theorem proving in elementary geometries. Journal of Symbolic Computation, 4:207--235, 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Keywords:
algebraic specification, geometric constraint systems description, geometric universe, software engineering