Body-and-cad geometric constraint systems

ABSTRACT

Motivated by constraint-based CAD software, we develop the foundation for the rigidity theory of a very general model: the body-and-cad structure, composed of rigid bodies in 3D constrained by pairwise coincidence, angle and distance constraints. We identify 21 relevant geometric constraints and develop the corresponding infinitesimal rigidity theory for these structures. The classical body-and-bar rigidity model can be viewed as a body-and-cad structure that uses only one constraint from this new class.

As a consequence, we identify a new, necessary but not sufficient, counting condition for minimal rigidity of body-and-cad structures: nested sparsity. This is a slight generalization of the well-known sparsity condition of Maxwell.

REFERENCES

• 1: H. Crapo and W. Whiteley. The statics of frameworks and movements of panel structures, a geometric introduction. Structural Topology, 6: 43--82, 1982.
• 2: J. Graver, B. Servatius, and H. Servatius. Combinatorial rigidity. Graduate Studies in Mathematics. American Mathematical Society, 1993.
• 3: G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4: 331--340, 1970.
• 4: A. Lee. Geometric Constraint Systems with Applications in CAD and Biology. PhD thesis, University of Massachusetts Amherst, May 2008.
• 5: A. Lee and I. Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 2007.
• 6: A. Lee, I. Streinu, and L. Theran. Graded sparse graphs and matroids. Journal of Universal Computer Science, 13(11): 1671--1679, 2007. http://arxiv.org/abs/0711.2838.
• 7: Hongbo Li , Yihong Wu, Automated short proof generation for projective geometric theorems with Cayley and bracket algebras: I. incidence geometry, Journal of Symbolic Computation, v.36 n.5, p.717-762, November 2003 [doi>10.1016/S0747-7171(03)00067-1]
• 8: D. Michelucci and P. Schreck. Incidence constraints: a combinatorial approach. International Journal of Computational Geometry Applications, 16(5--6): 443--460, 2006.
• 9: Franco Saliola , Walter Whiteley, Constraining Plane Configurations in CAD: Circles, Lines, and Angles in the Plane, SIAM Journal on Discrete Mathematics, v.18 n.2, p.246-271, 2005 [doi>10.1137/S0895480100374138]
• 10: J. M. Selig, Geometrical Methods in Robotics, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 11: Brigitte Servatius , Walter Whiteley, Constraining Plane Configurations in Computer-Aided Design: Combinatorics of Directions and Lengths, SIAM Journal on Discrete Mathematics, v.12 n.1, p.136-153, Jan. 1999 [doi>10.1137/S0895480196307342]
• 12: I. Streinu and L. Theran. Sparse hypergraphs and pebble game algorithms. European Journal of Combinatorics, to appear. http://arxiv.org/abs/math/0703921.
• 13: T.-S. Tay. Rigidity of multigraphs I: linking rigid bodies in n-space. Journal of Combinatorial Theory Series, B 26: 95--112, 1984.
• 14: N. White. Grassmann-cayley algebra and robotics, 1994.
• 15: Neil L. White, Geometric applications of the Grassmann-Cayley algebra, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 16: Neil White , Walter Whiteley, The algebraic geometry of motions of bar-and-body frameworks, SIAM Journal on Algebraic and Discrete Methods, v.8 n.1, p.1-32, January 2, 1987 [doi>10.1137/0608001]
• 17: W. Whiteley. A matroid on hypergraphs, with applications in scene analysis and geometry. Discrete and Computational Geometry, 4: 75--95, 1989.
• 18: W. Whiteley. Some matroids from discrete applied geometry. In J. Bonin, J. G. Oxley, and B. Servatius, editors, Matroid Theory, volume 197 of Contemporary Mathematics, pages 171--311. American Mathematical Society, 1996.
• 19: Yong Zhou , Meera Sitharam, Combinatorial decomposition, generic independence and algebraic complexity of geometric constraints systems: applications in biology and engineering, University of Florida, Gainesville, FL, 2006

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.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
      G.2.3 Applications

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Keywords:
computer aided design, geometric constraint system, rigidity theory