Numerical decomposition of geometric constraints

ABSTRACT

Geometric constraint solving is a key issue in CAD/CAM. Since Owen's seminal paper, solvers typically use graph based decomposition methods. However, these methods become difficult to implement in 3D and are misled by geometric theorems. We extend the Numerical Probabilistic Method (NPM), well known in rigidity theory, to more general kinds of constraints and show that NPM can also decompose a system into rigid subsystems. Classical NPM studies the structure of the Jacobian at a random (or generic) configuration. The variant we are proposing does not consider a random configuration, but a configuration similar to the unknown one. Similar means the configuration fulfills the same set of incidence constraints, such as collinearities and coplanarities. Jurzak's prover is used to find a similar configuration.

REFERENCES

• 1: Denis Bouhineau, Solving Geometrical Constraint Systems Using CLP Based on Linear Constraint Solver, Proceedings of the International Conference AISMC-3 on Artificial Intelligence and Symbolic Mathematical Computation, p.274-288, September 23-25, 1996
• 2: Brderlin, B., and Roller, D., Eds. 1998. Geometric Constraint Solving & Applications. Springer Verlag, June.
• 3: S.-C. Chou, Mechanical geometry theorem proving, Kluwer Academic Publishers, Norwell, MA, 1987
• 4: Xiao-Shan Gao , Gui-Fang Zhang, Geometric constraint solving via C-tree decomposition, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781617]
• 5: Grünbaum, B. 1967. Convex polytopes. London Interscience.
• 6: Bruce Hendrickson, Conditions for unique graph realizations, SIAM Journal on Computing, v.21 n.1, p.65-84, Feb. 1992 [doi>10.1137/0221008]
• 7: Christoph M. Hoffman , Andrew Lomonosov , Meera Sitharam, Decomposition plans for geometric constraint problems, part II: new algorithms, Journal of Symbolic Computation, v.31 n.4, p.409-427, April 1, 2001 [doi>10.1006/jsco.2000.0403 ]
• 8: 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 ]
• 9: Hoffmann, C., Sitharam, M., and Yuan, B. 2004. Making constraint solvers useable: overconstraints. Comp. Aided Design.
• 10: Jermann, C., Neveu, B., and Trombettoni, G. 2003. Algorithms for identifying rigid subsystems in geometric constraint systems. IJCAI, 233--238.
• 11: R. Joan-Arinyo , A. Soto-Riera , S. Vila-Marta , J. Vilaplana-Pastó, Transforming an under-constrained geometric constraint problem into a well-constrained one, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781616]
• 12: Joan-Arinyo, R., Soto-Riera, A., Vila-Marta, S., and Vilaplana-Pasto, J. 2004. Revisiting decomposition analysis of geometric constraint graphs. Computer-Aided Design 36, 2, 123--140.
• 13: Jurzak, J.-P. 2003. Géométrie vectorielle algorithmique: La góométrie vectorielle par l'ínformatique. Tech. Rep. http://passerelle.u-bourgogne.fr/publications/webgeometrie/Université de Bourgogne, Dijon.
• 14: Kortenkamp, U., and Richter-Gebert, J. 1998. The Interactive Geometry Software Cinderella. Springer-Verlag.
• 15: Kortenkamp, U. 1999. Foundations of Dynamic Geometry. PhD Thesis No 13403, Swiss Federal Institue of Technology, Zurich, Switzerland.
• 16: Laman, G. 1970. On graphs and rigidity of plane skeletal structures. J. Engineering Math. 4, 331--340.
• 17: Lamure, H., and Michelucci, D. 1998. Qualitative study of geometric constraints. In Geometric Constraint Solving and Applications, Springer-Verlag.
• 18: V. C. Lin , D. C. Gossard , R. A. Light, Variational geometry in computer-aided design, Proceedings of the 8th annual conference on Computer graphics and interactive techniques, p.171-177, August 03-07, 1981, Dallas, Texas, United States
• 19: L. Lovasz, Matching Theory (North-Holland mathematics studies), Elsevier Science Ltd, 1986
• 20: Lovasz, L., and Yemini, Y. 1982. On generic rigidity in the plane. SIAM J. Alg. Discr. Meth. 3, 1, 91--98.
• 21: Michelucci, D., and Foufou, S. 2004. Using Cayley-Menger determinants for geometric constraint solving. In ACM Symposium on Solid Modeling.
• 22: Mignotte, M., and Stefanescu, D. 1999. Polynomials: An algorithmic approach. In Discrete Mathematics and Theoretical Computer Science Series, vol. XI. Springer.
• 23: Olano, S., and Brunet, P. 1994. Constructive constraint-based model for parametric cad systems. Computer-Aided Design 26, 8, 614--621.
• 24: 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]
• 25: Owen, J. 1996. Constraints on simple geometry in two and three dimensions. Int. J. of Computational Geometry and Applications 6, 4, 421--434.
• 26: Pouzergues, R. 2002. Les hexamys. Tech. rep., http://hexamys.free.fr/.
• 27: Ashutosh Rege, A complete and practical algorithm for geometric theorem proving (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.277-286, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220309]
• 28: Schramm, E., and Schreck, P. 2003. Solving geometric constraints invariant modulo the similarity group. In Proceedings of Computational Science and Its Applications - ICCSA 2003, International Conference, Part III, Montreal, Canada, May 2003, Springer, vol. 2669 of Lecture Notes in Computer Science, 356--365.
• 29: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 30: Serré, P., Riviere, A., Duong, A., and Ortuzar, A. 2001. Analysis of a geometric specification. In Proceedings of the 27th Design Automation Conference, ASME Design Engineering Technical Conferences.
• 31: Sitharam, M., and Zhou, Y. 2004. A tractable, approximate characterization of combinatorial rigidity in 3D. In Automated Deduction in Geometry.
• 32: Sutherland, I. 1963. Sketchpad- A Man-Machine Graphical Interface. PhD thesis, MIT.
• 33: Yang, L. 2002. Distance coordinates used in geometric constraint solving. Automated Deduction in Geometry, 216--229.

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

Keywords:
constraints decomposition and solving, geometric constraints, geometry provers