Skip to main content
SpringerLink
Log in

From curve design algorithms to the design of rigid body motions

  • original article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

We discuss the following problem, which arises in computer animation and robot motion planning: given are N positions or keyframes Σ(ti) of a moving body Σ⊂ℝ3 at time instances ti. Compute a smooth rigid body motion Σ(t) that interpolates or approximates the given positions Σ(ti) such that chosen feature points of the moving system run on smooth paths. We present an algorithm that can be considered as a transfer principle from curve design algorithms to motion design. The algorithm relies on known curve design algorithms and on registration techniques from computer vision. We prove that the motion generated in this way is of the same smoothness as the curve design algorithm employed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arikan O, Forsyth DA (2002) Interactive motion generation from examples. In: Proceedings of SIGGRAPH ’02, San Antonio, TX, 21–26 July 2002, pp 483–490

  2. Barr AH, Currin B, Gabriel S, Hughes JF (1992) Smooth interpolation of orientations with angular velocity constraints using quaternions. In: Proceedings of SIGGRAPH ’92, Computer Graphics, 26:313–320

  3. Bayazit OB, Lien JM, Amato NM (2002) Probabilistic roadmap motion planning for deformable objects. In: Proceedings of the IEEE international conference on robotics and automation (ICRA ’02), Washington DC, 11–15 May 2002, pp 2126–2133

  4. Belta C, Kumar V (2002) An SVD-projection method for interpolation on SE(3). IEEE Trans Robot Automat 18(3):334–345

    Article  Google Scholar 

  5. Bernardini F, Rushmeier H (2002) The 3D model acquisition pipeline. Comput Graph Forum 21(2):149–172

    Article  Google Scholar 

  6. Besl PJ, McKay ND (1992) A method for registration of 3-D shapes. IEEE Trans Patt Anal Mach Intell 14(2):239–256

    Article  Google Scholar 

  7. Blake A, Isard M (1998) Active contours. Springer, Berlin Heidelberg New York

  8. Chen Y, Medioni G (1992) Object modeling by registration of multiple range images. Image Vision Comput 10(3):145–155

    Article  Google Scholar 

  9. Eggert DW, Larusso A, Fisher RB (1997) Estimating 3-D rigid body transformations: a comparison of four major algorithms. Mach Vision Appl 9(5/06):272–290

  10. Fang YC, Hsieh CC, Kim MJ, Chang JJ, Woo TC (1998) Real time motion fairing with unit quaternions. Comput Aided Des 30(3):191–198

    Article  Google Scholar 

  11. Halperin D, Kavraki L, Latombe JC (1997) Robotics. In: Goodman JE, O’Rourke J (eds) Handbook of discrete and computational geometry. CRC Press, Boca Raton, FL, pp 775–778

  12. Hanson AJ (1998) Constrained optimal framings of curves and surfaces using quaternion gauss maps. In: Proceedings of Visualization ’98, Research Triangle Park, NC, 18–23 October 1998. IEEE Press, New York, pp 375–382

  13. Hofer M, Pottmann H, Ravani B (2002) Subdivision algorithms for motion design based on homologous points. In: Lenarcic J, Thomas T (eds) Advances in robot kinematics: theory and applications. Kluwer, Amsterdam, pp 235–244

  14. Hofer M, Pottmann H, Ravani B (2003) Geometric design of motions constrained by a contacting surface pair. Comput Aided Geom Des 20(8–9), 523–547

  15. Horn BKP (1987) Closed form solution of absolute orientation using unit quaternions. J Opt Soc A 4(4):629–642

    Article  Google Scholar 

  16. Hsieh CC, Chang TY (2003) Motion fairing using genetic algorithms. Comput Aided Des 35(8):739–749

    Article  Google Scholar 

  17. Hyun DE, Jüttler B, Kim MS (2001) Minimizing the distortion of affine spline motions. In: Proceedings of Pacific Graphics ’01, Tokyo, 16–18 October 2001. IEEE Press, New York, pp 50–59

  18. Jüttler B (1994) Visualization of moving objects using dual quaternion curves. Comput Graph 18(3):315–326

    Article  Google Scholar 

  19. Jüttler B, Wagner M (1996) Computer aided design with spatial rational B-spline motions. ASME J Mech Des 118(2):193–201

    Article  Google Scholar 

  20. Jüttler B, Wagner M (2002) Kinematics and animation. In: Farin G, Hoschek J, Kim MS (eds) Handbook of computer aided geometric design. Elsevier, Amsterdam, pp 723–748

  21. Kalisiak M, van de Panne M (2001) A grasp-based motion planning algorithm for character animation. J Vis Comput Animat 12(3):117–129

    Article  Google Scholar 

  22. Kobbelt L (1996) A variational approach to subdivision. Comput Aided Geom Des 13(8):743–761

    Article  MathSciNet  Google Scholar 

  23. Kobbelt L, Schröder P (1998) A multiresolution framework for variational subdivision. ACM Trans Graph 17(4):209–237

    Article  Google Scholar 

  24. Latombe JC (1999) Motion planning: a journey of robots, molecules, digital actors, and other artifacts. Int J Robot Res 18(11):1119–1128

    Article  Google Scholar 

  25. Latombe JC (2001) Robot motion planning, 6th edn. Kluwer, Amsterdam

  26. Marchand É, Courty N (2002) Controlling a camera in a virtual environment. Vis Comput 18(1):1–19

    Article  Google Scholar 

  27. Park FC, Ravani B (1997) Smooth invariant interpolation of rotations. ACM Trans Graph 16(3):277–295

    Article  Google Scholar 

  28. Pottmann H, Leopoldseder S, Hofer M (2002a) Simultaneous registration of multiple views of a 3D object. Archives of the photogrammetry, remote sensing and spatial information sciences, vol XXXIV, part 3A, Commission III, pp 265–270

  29. Pottmann H, Leopoldseder S, Hofer M (2002b) Approximation with active B-spline curves and surfaces. In: Proceedings of Pacific Graphics 02, Beijing, 9–11 October 2002. IEEE Press, New York, pp 8–25

  30. Pottmann H, Peternell M (2000) On approximation in spaces of geometric objects. In: Cipolla R, Martin R (eds) The mathematics of surfaces IX. Springer, Berlin Heidelberg New York, pp 438–458

  31. Pottmann H, Wallner J (2001) Computational line geometry. Springer, Berlin Heidelberg New York

  32. Ramamoorthi R, Barr AH (1997) Fast construction of accurate quaternion splines. In Proceedings of SIGGRAPH ’97, Computer Graphics, 31:287–292

  33. Röschel O (1998) Rational motion design — a survey. Comput Aided Des 30(3):169–178

    Article  Google Scholar 

  34. Rusinkiewicz S, Levoy M (2001) Efficient variants of the ICP algorithm. In: Proceedings of the 3rd international conference on 3D digital imaging and modeling, Quebec, 28 May–1 June 2001, pp 145–152

  35. Salomon B, Garber M, Lin MC, Manocha D (2003) Interactive navigation in complex environments using path planning. In: Proceedings of the ACM SIGGRAPH symposium on interactive 3D graphics, Monterey, CA, 28–30 April 2003, pp 41–50

  36. Sharir M (1997) Algorithmic motion planning. In: Goodman JE, O’Rourke J (eds) Handbook of discrete and computational geometry. CRC Press, Boca Raton, FL, pp 733–754

  37. Shoemake K (1985) Animating rotation with quaternion curves. In: Proceedings of SIGGRAPH ’85, Computer Graphics, 19:245–254

  38. Song G, Amato NM (2002) Using motion planning to study protein folding pathways. J Comput Biol 9(2):149–168

    Article  Google Scholar 

  39. Wahba G (1990) Spline models for observational data. SIAM, Philadelphia

  40. Wallner J (2002) L2 Approximation by Euclidean motions. Technical Report No. 93, Institute of Geometry, Vienna University of Technology, Vienna

  41. Wallner J (2004) Gliding spline motions and applications. Comput Aided Geom Des 21(1), 3–21

  42. Warren J, Weimer H (2001) Subdivision methods for geometric design: a constructive approach. Morgan Kaufmann Series in Computer Graphics, Morgan Kaufmann, San Francisco

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Geometric Modeling and Industrial Geometry Group, Vienna University of Technology, Wiedner Hauptstrasse 8–10/104, A-1040, Vienna, Austria

    Michael Hofer & Helmut Pottmann

  2. Department of Mechanical & Aeronautical Engineering, University of California, 1013 Academic Surge, Davis, CA, 95616-5294, USA

    Bahram Ravani

Authors
  1. Michael Hofer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Helmut Pottmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bahram Ravani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Hofer.

Additional information

To the memory of Peter Steiner

Electronic Supplementary Material

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hofer, M., Pottmann, H. & Ravani, B. From curve design algorithms to the design of rigid body motions. Vis Comput 20, 279–297 (2004). https://doi.org/10.1007/s00371-003-0221-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-003-0221-3

Keywords

Search

Navigation