Interrogating witnesses for geometric constraint solving

ABSTRACT

Classically, geometric constraint solvers use graph-based methods to analyze systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes. This paper details the computation of a basis of the vector space of the free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for detecting all dependencies between constraints: structural dependencies already detectable by graph-based methods, and also non-structural dependencies, due to known or unknown geometric theorems, which are undetectable with graph-based methods. The paper also discusses how to decide about the rigidity of a witness.

REFERENCES

• 1: B. Bruderlin and D. Roller, editors. Geometric Constraint Solving and Applications. Springer-Verlag, 1998.
• 2: K. S. Christos H. Papadimitriou. Combinatorial Optimization, algorithms and Complexity. Dover Publications, 1998.
• 3: S. Foufou, D. Michelucci, and J.-P. Jurzak. Numerical decomposition of geometric constraints. In ACM Symp. on Solid and Physical Modelling, pages 143--151, 2005.
• 4: C. Fuenfzig, D. Michelucci, and S. Foufou. Nonlinear systems solver in floating-point arithmetic using lp reduction. In Proceedings of the 2009 ACM symposium on Solid modeling, 2009.
• 5: X.-S. Gao, C. Hoffmann, and W. Yang. Solving spatial basic geometric constraint configurations with locus intersection. Computer Aided Design, 36(2):111--122, 2004.
• 6: X.-S. Gao and G. Zhang. Geometric constraint solving via c-tree decomposition. In ACM Solid Modelling, pages 45--55. ACM Press, New York, 2003.
• 7: C. Hoffmann, A. Lomonosov, and M. Sitharam. Decomposition plans for geometric constraint problems, Part II: New algorithms. J. Symbolic Computation, 31:409--427, 2001.
• 8: C. Hoffmann, A. Lomonosov, and M. Sitharam. Decomposition plans for geometric constraint systems, Part I: Performance measures for cad. J. Symbolic Computation, 31:367--408, 2001.
• 9: H. S. J. Graver, B. Servatius. Combinatorial Rigidity. Graduate Studies in Mathematics. American Mathematical Society, 1993.
• 10: C. Jermann, B. Neveu, and G. Trombettoni. Algorithms for identifying rigid subsystems in geometric constraint systems. In Int. Joint Conf. in Artificial Intelligence IJCAI-03, pages 233--238, 2003.
• 11: C. Jermann, G. Trombettoni, B. Neveu, and P. Mathis. Decomposition of geometric constraint systems: a survey. Int. J. of Comp. Geometry and App. (IJCGA), 16(5--6):379--414, 2006.
• 12: H. Lamure and D. Michelucci. Solving constraints by homotopy. In Proc. of the Symp. on Solid Modeling Foundations and CAD/CAM Applications, pages 263--269, May 1995.
• 13: D. Michelucci and S. Foufou. Geometric constraint solving: the witness configuration method. Computer Aided Design, 38(4):284--299, 2006.
• 14: J. Owen. Constraint on simple geometry in two and three dimensions. Int. J. Comput. Geometry Appl., 6(4):421--434, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

Keywords:
dependency detection, geometric constraint solving