Kinematic convexity of spherical displacements and its application to collision prediction

ABSTRACT

In recent years, there has been an increasing interest in developing geometric algorithms for kinematic computations. The aim of this paper is to present the notion of kinematic convexity as a key element for a new framework for spherical kinematic geometry that allows for the development of more elegant and efficient algorithms for geometric computations in kinematic applications. The resulting framework, called computational spherical kinematic geometry, is developed by combining the oriented projective geometry with the kinematic geometry of spherical motions. By extending the idea of convexity in affine geometry to an oriented image space of spherical displacements, the notion of kinematic convexity is proposed. A novel application to the collision prediction problem is presented to illustrate the theory developed.

REFERENCES

• 1: C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
• 2: Blaschke, W. 1960. Kinematik und Quaternionen. Deutscher Verlag der Wissenschaften, Berlin.
• 3: Bottema, O., and Roth, B. 1979. Theoretical Kinematics. North Holland, Amsterdam.
• 4: Samuel R. Buss , Jay P. Fillmore, Spherical averages and applications to spherical splines and interpolation, ACM Transactions on Graphics (TOG), v.20 n.2, p.95-126, April 2001 [doi>10.1145/502122.502124]
• 5: Dooley, J. R., and Ravani, B. 1994. Geometric analysis of spatial rigid body dynamics with multiple frictional contacts. In Advances in Robot Kinematics and Computational Geometry, J. Lenarcic and B. Ravani, Eds. KAP, 71--80.
• 6: Flanders, H. 1989. Differential forms with applications to the physical sciences. Dover Pub., New York.
• 7: Ge, Q. J., and Larochelle, P. M. 1999. Algebraic motion approximation with nurbs motions and its application to spherical mechanism synthesis. ASME Journal of Mechanical Design 121, 4, 529--532.
• 8: Ge, Q. J., and Ravani, B. 1994. Computer-aided geometric design of motion interpolants. ASME Journal of Mechanical Design 116, 3, 756--762.
• 9: Ge, Q. J., and Ravani, B. 1994. Geometric construction of bezier motions. ASME Journal of Mechanical Design 116, 3, 749--755.
• 10: Hunt, K. 1978. Kinematic Geometry of Mechanisms. Oxford University Press.
• 11: Juttler, B., and Wagner, M. G. 1996. Computer-aided design with spatial rational b-spline motions. ASME Journal of Mechanical Design 118, 2, 193--201.
• 12: Kim, M. S., and Nam, K. W. 1995. Interpolating solid orientations with circular blending quaternion curves. Computer-Aided Design 27, 5, 385--398.
• 13: Byungmoon Kim , Jarek Rossignac, Collision prediction for polyhedra under screw motions, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781612]
• 14: Larochelle, P., and McCarthy, J. M. 1994. Design of spatial 4c mechanisms for rigid body guidance. In Proc. 1994 ASME Mechanisms Conference, 135--142.
• 15: Li, S., and Ge, Q. J. 2005. Rational bezier line symmmetric motions. ASME Journal of Mechanical Design 127, 2, 222--226.
• 16: J. M. McCarthy, Introduction to theoretical kinematics, MIT Press, Cambridge, MA, 1990
• 17: Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
• 18: Park, F. C., and Ravani, B. 1995. Bezier curves on riemannianmanifolds and lie-groups with kinematics applications. ASME Journal of Mechanical Design 117, 1, 36--40.
• 19: Purwar, A., and Ge, Q. J. 2005. On the effect of dual weights in computer aided design of rational motions. ASME Journal of Mechanical Design 127, 5, 967--972.
• 20: Ravani, B., and Roth, B. 1983. Motion synthesis using kinematic mappings. Journal of Mechanisms Transmissions and Automation in Design-Transactions of the ASME 105, 3, 460--467.
• 21: Ravani, B., and Roth, B. 1984. Mappings of spatial kinematics. Journal of Mechanisms Transmissions and Automation in Design-Transactions of the ASME 106, 3, 341--347.
• 22: Ken Shoemake, Animating rotation with quaternion curves, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.245-254, July 1985
• 23: Srinivasan, L. N., and Ge, Q. J. 1998. Fine tuning of rational b-spline motions. ASME Journal of Mechanical Design 120, 1, 46--51.
• 24: Jorge Stolfi, Oriented projective geometry, Academic Press Professional, Inc., San Diego, CA, 1991
• 25: Study, E. 1903. Die Geometrie der Dynamen. Verlag Teubner, Leipzig.
• 26: Wagner, M. G. 1994. A Geometric Approach to Motion Design. Ph.d. dissertation, Technische Universitt Wien.
• 27: Woo, T. 1994. Visibility maps and spherical algorithms. Computer-Aided Design 26, 1, 6--16.
• 28: Zefran, M., and Kumar, V. 1998. Interpolation schemes for rigid body motions. Computer-Aided Design 30, 3, 179--189.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Keywords:
collision prediction, convexity, kinematics, motion planning, quaternions