article

From curve design algorithms to the design of rigid body motions

Authors:

Helmut Pottmann, and

Bahram RavaniAuthors Info & Claims

The Visual Computer: International Journal of Computer Graphics, Volume 20, Issue 5

Pages 279 - 297

Published: 01 July 2004 Publication History

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.

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

Digital Library

[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

[5]

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

[6]

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

Digital Library

[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

Digital Library

[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

Digital Library

[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

[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

Digital Library

[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

[16]

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

[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

[19]

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

[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

[22]

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

Digital Library

[23]

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

Digital Library

[24]

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

[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

[27]

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

Digital Library

[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

[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

Digital Library

[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

[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

Digital Library

[42]

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

Cited By

Schröcker HWeber M(2014)Guaranteed collision detection with toleranced motionsComputer Aided Geometric Design10.1016/j.cagd.2014.08.00131:7(602-612)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.cagd.2014.08.001
Krajnc MSampoli MSestini AŽagar E(2014)C 1 interpolation by rational biarcs with rational rotation minimizing directed framesComputer Aided Geometric Design10.1016/j.cagd.2014.06.00131:7(427-440)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.cagd.2014.06.001
Cripps RMullineux G(2012)Constructing 3D motions from curvature and torsion profilesComputer-Aided Design10.1016/j.cad.2012.01.00444:5(379-387)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.cad.2012.01.004
Show More Cited By

Index Terms

From curve design algorithms to the design of rigid body motions

Recommendations

Hermite interpolation by rational Gk motions of low degree

Interpolation by rational spline motions is an important issue in robotics and related fields. In this paper a new approach to rational spline motion design is described by using techniques of geometric interpolation. This enables us to reduce the ...
Read More
Geometric design of motions constrained by a contacting surface pair

We discuss the following problem which arises in robot motion planning, NC machining and computer animation: Given are a fixed surface Φ and N positions Φ_i of a moving surface Φ such that the Φ_i are in point contact with Ψ. Compute a smooth and fair ...
Read More
Construction of low degree rational motions

Construction of rational spline motions is an important issue in robotics, animations and related fields. In this paper a geometric approach to interpolate given sequence of rigid body positions is considered, which, in contrast to standard approaches, ...
Read More

Comments

Information & Contributors

Information

Published In

cover image The Visual Computer: International Journal of Computer Graphics

The Visual Computer: International Journal of Computer Graphics Volume 20, Issue 5

July 2004

81 pages

ISSN:0178-2789

Issue’s Table of Contents

Copyright © Copyright © 2004 Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Other Metrics

View Author Metrics

Citations

Cited By

Schröcker HWeber M(2014)Guaranteed collision detection with toleranced motionsComputer Aided Geometric Design10.1016/j.cagd.2014.08.00131:7(602-612)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.cagd.2014.08.001
Krajnc MSampoli MSestini AŽagar E(2014)C 1 interpolation by rational biarcs with rational rotation minimizing directed framesComputer Aided Geometric Design10.1016/j.cagd.2014.06.00131:7(427-440)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.cagd.2014.06.001
Cripps RMullineux G(2012)Constructing 3D motions from curvature and torsion profilesComputer-Aided Design10.1016/j.cad.2012.01.00444:5(379-387)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.cad.2012.01.004
Adams BOvsjanikov MWand MSeidel HGuibas LFiume ETessendorf JGross MJames D(2008)Meshless modeling of deformable shapes and their motionProceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/1632592.1632605(77-86)Online publication date: 7-Jul-2008
https://dl.acm.org/doi/10.5555/1632592.1632605
Nawratil GPottmann H(2008)Subdivision schemes for the fair discretization of the spherical motion groupJournal of Computational and Applied Mathematics10.1016/j.cam.2007.12.004222:2(574-591)Online publication date: 20-Dec-2008
https://dl.acm.org/doi/10.1016/j.cam.2007.12.004
Mitra NGuibas LPauly MLevoy M(2007)SymmetrizationACM SIGGRAPH 2007 papers10.1145/1275808.1276456(63-es)Online publication date: 5-Aug-2007
https://dl.acm.org/doi/10.1145/1275808.1276456
Huang QFlöry SGelfand NHofer MPottmann HFinnegan JDorsey J(2006)Reassembling fractured objects by geometric matchingACM SIGGRAPH 2006 Papers10.1145/1179352.1141925(569-578)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1179352.1141925
Mitra NGuibas LPauly MFinnegan JDorsey J(2006)Partial and approximate symmetry detection for 3D geometryACM SIGGRAPH 2006 Papers10.1145/1179352.1141924(560-568)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1179352.1141924
Huang QFlöry SGelfand NHofer MPottmann H(2006)Reassembling fractured objects by geometric matchingACM Transactions on Graphics10.1145/1141911.114192525:3(569-578)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1145/1141911.1141925
Mitra NGuibas LPauly M(2006)Partial and approximate symmetry detection for 3D geometryACM Transactions on Graphics10.1145/1141911.114192425:3(560-568)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1145/1141911.1141924
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents

-