Solving spatial basic geometric constraint configurations with locus intersection

ABSTRACT

A basic idea of geometric constraint solving is to decompose the constraint problem into smaller ones according to some basic configurations. In this paper, we find all spatial basic configurations involving points, lines, and planes containing up to six geometric primitives in an automated way. Many of these basic configurations still resist effective analytical solutions. We propose the locus intersection method for geometric constraint solving, which is used to solve all these basic configurations.

REFERENCES

• 1: Beat Brüderlin, Using geometric rewrite rules for solving geometric problems symbolically, Theoretical Computer Science, v.116 n.2, p.291-303, Aug. 16, 1993 [doi>10.1016/0304-3975(93)90324-M]
• 2: X. Chen and C. Hoffmann, On Editability of Feature Based Design, CAD 27, 905--914, 1995
• 3: Cassiano Durand , Christophe M. Hoffmann, A systematic framework for solving geometric constraints analytically, Journal of Symbolic Computation, v.30 n.5, p.493-519, Nov. 2000 [doi>10.1006/jsco.2000.0392]
• 4: X.-S. Gao and S. C. Chou, Solving Geometric Constraint Systems I. A Global Propagation Approach, Computer Aided Design, 30(1), 47--54, 1998
• 5: X.-S. Gao and S. C. Chou, Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility, Computer-Aided Design, 30(2), 115--122, 1998
• 6: Xiao-Shan Gao , Lei-Dong Huang , Kun Jiang, A Hybrid Method for Solving Geometric Constraint Problems, Revised Papers from the Third International Workshop on Automated Deduction in Geometry, p.16-25, September 25-27, 2000
• 7: X.-S. Gao, K. Jiang, and C.-C. Zhu, Geometric Constraint Solving with Conics and Linkages, accepted by Computer Aided Design
• 8: Ching-Yao Hsu, Graph-based approach for solving geometric constraint problems, University of Utah, Salt Lake City, UT, 1996
• 9: Ching-yao Hsu , Beat Brüderlin, A Hybrid Constraint Solver Using Exact and Iterative Geometric Constructions, CAD Systems Development: Tools and Methods [Dagstuhl Seminar, 1995], p.265-279, January 1997
• 10: R. Joan-Arinyo and A. Soto, A Correct Rule-Based Geometric Constraint Solver, Computers and Graphics, 21(5), 599--609, 1997
• 11: 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]
• 12: Robert Joan-Arinyo , Nuria Mata , Antoni Soto-Riera, A constraint solving-based approach to analyze 2D geometric problems with interval parometers, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.11-17, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376959]
• 13: (MATH) C. Hoffmann and P.J. Vermeer, Geometric Constraint Solving in R2 and R3, in Computing in Euclidean Geometry, D.Z.Du and F.Huang (eds), pp. 266--298, World Scientific, Singapore, 1995
• 14: C. M. Hoffmann, A. Lomonosov and M. Sitharam, Finding Solvable Subsets of Constraint Graphs, in LNCS, NO.1330, pp.163--197, Springer, Berlin Heidelberg, 1997
• 15: Christoph M. Hoffmann , Bo Yuan, On Spatial Constraint Solving Approaches, Revised Papers from the Third International Workshop on Automated Deduction in Geometry, p.1-15, September 25-27, 2000
• 16: G. A. Kramer, Solving Geometric Constraints Systems: A Case Study in Kinematics, MIT Press, Cambridge Massachusetts, 1992
• 17: K. Kondo, Algebraic Method for Manipulation of Dimensional Relationships in Geometric Models, Computer Aided Design, 24(3), 141--147, 1992
• 18: Hervé Lamure , Dominique Michelucci, Solving Geometric Constraints By Homotopy, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.28-34, March 1996 [doi>10.1109/2945.489384]
• 19: R. S. Latham and A. E. Middleditch, Connectivity Analysis: a Tool for Processing Geometric Constraints, Computer Aided Design, 28(11), 917--928, 1994
• 20: J. Y. Lee and K. Kim, Geometric Reasoning for Knowledge-Based Design Using Graph Representation, Computer-Aided Design, 28(10), 831--841, 1998
• 21: 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
• 22: D. Michelucci, Using Cayley-Menger Determinants,undated world-wide-web document, www.emse.fr/~micheluc/MENGER/
• 23: 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]
• 24: G. Sunde, Specification of Shape by Dimension and Other Geometric Constraints, Geometric Modeling for CAD Application, pp.199--213, North-Holland, 1998
• 25: A. Verroust, F. Schonek and D. Roller, Rule-Oriented Method for Parameterized Computer-Aided Design, Computer Aided Design, 24(10), 531--540, 1992
• 26: Wen-tsün Wu, Mechanical theorem proving in geometries, Springer-Verlag New York, Inc., New York, NY, 1994

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
geometric constraint solving, locus intersection, parametric CAD, spatial basic configuration