Computation of rotation minimizing frames

ABSTRACT

Due to its minimal twist, the rotation minimizing frame (RMF) is widely used in computer graphics, including sweep or blending surface modeling, motion design and control in computer animation and robotics, streamline visualization, and tool path planning in CAD/CAM. We present a novel simple and efficient method for accurate and stable computation of RMF of a curve in 3D. This method, called the double reflection method, uses two reflections to compute each frame from its preceding one to yield a sequence of frames to approximate an exact RMF. The double reflection method has the fourth order global approximation error, thus it is much more accurate than the two currently prevailing methods with the second order approximation error—the projection method by Klok and the rotation method by Bloomenthal, while all these methods have nearly the same per-frame computational cost. Furthermore, the double reflection method is much simpler and faster than using the standard fourth order Runge-Kutta method to integrate the defining ODE of the RMF, though they have the same accuracy. We also investigate further properties and extensions of the double reflection method, and discuss the variational principles in design moving frames with boundary conditions, based on RMF.

REFERENCES

• 1: David C. Banks , Bart A. Singer, A Predictor-Corrector Technique for Visualizing Unsteady Flow, IEEE Transactions on Visualization and Computer Graphics, v.1 n.2, p.151-163, June 1995 [doi>10.1109/2945.468404]
• 2: Ronen Barzel, Faking Dynamics of Ropes and Springs, IEEE Computer Graphics and Applications, v.17 n.3, p.31-39, May 1997 [doi>10.1109/38.586016]
• 3: Bechmann, D. and Gerber, D. 2003. Arbitrary shaped deformation with dogme. Visual Comput. 19, 2--3, 175--186.
• 4: Bishop, R. L. 1975. There is more than one way to frame a curve. Amer. Math. Monthly 82, 3, 246--251.
• 5: Jules Bloomenthal, Modeling the mighty maple, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.305-311, July 1985
• 6: Jules Bloomenthal, Calculation of reference frames along a space curve, Graphics gems, Academic Press Professional, Inc., San Diego, CA, 1990
• 7: Bloomenthal, M. and Riesenfeld, R. F. 1991. Approximation of sweep surfaces by tensor product NURBS. In SPIE Proceedings Curves and Surfaces in Computer Vision and Graphics II. Vol. 1610. 132--154.
• 8: Willem F. Bronsvoort , Fopke Klok, Ray tracing generalized cylinders, ACM Transactions on Graphics (TOG), v.4 n.4, p.291-303, Oct. 1985 [doi>10.1145/6116.6118]
• 9: Hyeong In Choi , Song-Hwa Kwon , Nam-Sook Wee, Almost rotation-minimizing rational parametrization of canal surfaces, Computer Aided Geometric Design, v.21 n.9, p.859-881, November 2004 [doi>10.1016/j.cagd.2004.07.002]
• 10: Chung, T. L. and Wang, W. 1996. Discrete moving frames for sweep surface modeling. In Proceedings of Pacific Graphics. 159--173.
• 11: Rida T. Farouki, Exact rotation-minimizing frames for spatial Pythagorean-hodograph curves, Graphical Models, v.64 n.6, p.382-395, November 2002 [doi>10.1016/S1524-0703(03)00002-X]
• 12: Rida T. Farouki , Chang Yong Han, Rational approximation schemes for rotation-minimizing frames on Pythagorean-hodograph curves, Computer Aided Geometric Design, v.20 n.7, p.435-454, October 2003 [doi>10.1O16/S0167-8396(03)00095-5]
• 13: Goemans, O. and Overmars, M. 2004. Automatic generation of camera motion to track a moving guide. In Proceedings of Workshop on the Algorithmic Foundations of Robotics. (WAFR) 201--216.
• 14: H. Guggenheimer, Computing frames along a trajectory, Computer Aided Geometric Design, v.6 n.1, p.77-78, February 1989 [doi>10.1016/0167-8396(89)90008-3]
• 15: Andrew J. Hanson, Constrained optimal framings of curves and surfaces using quaternion Gauss maps, Proceedings of the conference on Visualization '98, p.375-382, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 16: Hanson, A. 2005. Visualizing Quaternions. Morgan Kaufmann.
• 17: Andrew J. Hanson , Hanson Hui Ma, Quaternion Frame Approach to Streamline Visualization, IEEE Transactions on Visualization and Computer Graphics, v.1 n.2, p.164-174, June 1995 [doi>10.1109/2945.468403]
• 18: Jüttler, B. 1998. Rotational minimizing spherical motions. In Advacnes in Robotics: Analysis and Control. Kluwer, 413--422.
• 19: Jüttler, B. 1999. Rational approximation of rotation minimizing frames using Pythagorean-hodograph cubics. J. Geom. Graph. 3, 141--159.
• 20: Jüttler, B. and Mäurer, C. 1999. Cubic Pythagorean hodograph spline curves and applications to sweep surface modeling. Comput.-Aid. Des. 31, 73--83.
• 21: F Klok, Two moving coordinate frames for sweeping along a 3D trajectory, Computer Aided Geometric Design, v.3 n.3, p.217-229, Nov. 1986 [doi>10.1016/0167-8396(86)90039-7]
• 22: Kreyszig, E. 1991. Differential Geometry. Dover.
• 23: Lazarus, F., Coquillart, S., and Jancène, P. 1993. Interactive axial deformations. In Modeling in Computer Graphics. Springer Verlag, 241--254.
• 24: Lazarus, F. and Verroust, A. 1994. Feature-based shape transformation for polyhedral objects. In Proceedings of the 5th Eurographics Workshop on Animation and Simulation. 1--14.
• 25: Lazarus, S. C. and Jancene, P. 1994. Axial deformation: an intuitive technique. Comput.-Aid. Des. 26, 8, 607--613.
• 26: Ignacio Llamas , Alexander Powell , Jarek Rossignac , Chris D. Shaw, Bender: a virtual ribbon for deforming 3D shapes in biomedical and styling applications, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.89-99, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060255]
• 27: Qunsheng Peng , Xiaogang Jin , Jieqing Feng, Arc-Length-Based Axial Deformation and Length Preserved Animation, Proceedings of the Computer Animation, p.86, June 04-07, 1997
• 28: Poston, T., Fang, S., and Lawton, W. 1995. Computing and approximating sweeping surfaces based on rotation minimizing frames. In Proceedings of the 4th International Conference on CAD/CG. Wuhan, China.
• 29: Pottmann, H. and Wagner, M. 1998. Contributions to motion based surface design. Int. J. Shape Model. 4, 3&4, 183--196.
• 30: Semwal, S. K. and Hallauer, J. 1994. Biomedical modeling: implementing line-of-action algorithm for human muscles and bones using generalized cylinders. Comput. Graph. 18, 1, 105--112.
• 31: Shani, U. and Ballard, D. H. 1984. Splines as embeddings for generalized cylinders. Comput. Vision Graph. Image Proces. 27, 129--156.
• 32: Siltanen, P. and Woodward, C. 1992. Normal orientation methods for 3D offset curves, sweep surfaces, skinning. In Proceedings of Eurographics. 449--457.
• 33: Wang, W. and Joe, B. 1997. Robust computation of rotation minimizing frame for sweep surface modeling. Comput.-Aid Des. 29, 379--391.
• 34: Wang, W., Jüttler, B., Zheng, D., and Liu, Y. 2007. Computation of rotation minimizing frame in computer graphics. Tech. rep., TR 2007-07, Department of Computer Science, University of Hong Kong.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Error analysis

General Terms:
Algorithms, Theory

Keywords:
Curve, differential geometry, motion, motion design, rotation minimizing frame, sweep surface