Spherical averages and applications to spherical splines and interpolation

ABSTRACT

This article introduces a method for computing weighted averages on spheres based on least squares minimization that respects spherical distance. We prove existence and uniqueness properties of the weighted averages, and give fast iterative algorithms with linear and quadratic convergence rates. Our methods are appropriate to problems involving averages of spherical data in meteorological, geophysical, and astronomical applications. One simple application is a method for smooth averaging of quaternions, which generalizes Shoemake's spherical linear interpolation.The weighted averages methods allow a novel method of defining Bézier and spline curves on spheres, which provides direct generalization of Bézier and B-spline curves to spherical spline curves. We present a fast algorithm for spline interpolation on spheres. Our spherical splines allow the use of arbitrary knot positions; potential applications of spherical splines include smooth quaternion curves for applications in graphics, animation, robotics, and motion planning.

REFERENCES

• 1: Peter Alfeld , Marian Neamtu , Larry L. Schumaker, Bernstein-Be´zier polynomials on spheres and sphere-like surfaces, Computer Aided Geometric Design, v.13 n.4, p.333-349, June 1996 [doi>10.1016/0167-8396(95)00030-5]
• 2: James Arvo, Stratified sampling of spherical triangles, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.437-438, September 1995 [doi>10.1145/218380.218500]
• 3: BARONTI, M., CASINI, E., AND PAPINI, P. L. 1997. Centroids, centers and medians: What is the difference? Geometriae Dedicata 68, 157-168.
• 4: Alan H. Barr , Bena Currin , Steven Gabriel , John F. Hughes, Smooth interpolation of orientations with angular velocity constraints using quaternions, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.313-320, July 1992
• 5: BROWN,J.L.AND WORSEY, A. J. 1992. Problems with defining barycentric coordinates for the sphere. Mathematical Modelling and Numerical Analysis (Modelisation mathematique et Analyse numerique) 26, 37-49.
• 6: CLARK,R.M.AND THOMPSON, R. 1984. Statistical comparison of palaeomagnetic directional records from lake sediment. Geophys. J. Roy. Astr. Soc. 76, 337-368.
• 7: COXETER, H. S. M. 1946. Quaternions and reflections. Am. Math. Monthly 53, 136-146.
• 8: DAM, E. B., KOCH, M., AND LILLHOLM, M. 1998. Quaternions, interpolation and animation. Tech. Rep. DIKU 98/5, Institute of Computer Science, University of Copenhagen, Copenhagen Denmark. http://www.diku.dk/students/myth/quat.html.
• 9: DUFF, T. 1986. Splines in animation and modeling. In SIGGRAPH'86 Course Notes on State of the Art in Image Synthesis, July, ACM, New York.
• 10: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 11: FISHER,N.I.AND LEWIS, T. 1985. A note on spherical splines. J. Roy. Stat Soc. B 47, 482- 488.
• 12: GABRIEL,S.AND KAJIYA, K. 1985. Spline interpolation in curved space. In SIGGRAPH'85 Course Notes on State of the Art Image Synthesis, ACM, NewYork, pp. 1-14.
• 13: GE,Q.J.AND RAVANI, B. 1994. Computer aided geometric design of motion interpolants. Trans. ASME: J. Mech. Des, 756-762.
• 14: GROSS, O. 1964. The rondezvous value of a metric space. In Advances in Game Theory, Princeton University Press, Princeton, N. J., 49-53.
• 15: John C. Hart , George K. Francis , Louis H. Kauffman, Visualizing quaternion rotation, ACM Transactions on Graphics (TOG), v.13 n.3, p.256-276, July 1994 [doi>10.1145/195784.197480]
• 16: JUPP, P. E. 1987. Fitting smooth paths to spherical data. Appl. Stat. 36, 34-46.
• 17: JUTTLER, B. 1994. Visualization of moving objects using dual quaternion curves. Comput. Graph. 18, 315-326.
• 18: JUTTLER,B.AND WAGNER, M. G. 1996. Computer-aided design with spatial rational B-spline motions. J. Mech Des. 118, 193-201.
• 19: Myoung-Jun Kim , Myung-Soo Kim , Sung Yong Shin, A general construction scheme for unit quaternion curves with simple high order derivatives, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.369-376, September 1995 [doi>10.1145/218380.218486]
• 20: KIM, M.-S. AND NAM, K.-W. 1995. Interpolating solid orientations with circular blending quaternion curves. Comput. Aided Des. 27, 385-398.
• 21: KIM, M.-S. AND NAM, K.-W. 1996. Hermite interpolation of solid orientations with circular blending quaternion curves. J. Visual. Comput. Anim. 7, 95-110.
• 22: MILNOR, J. W. 1965. Topology from the Differentiable Viewpoint. University Press of Virginia, Charlottesville, Va. (Based on notes by D.W. Weaver.)
• 23: NOAKES, L., HEINZINGER,G.,AND PADEN, B. 1989. Cubic splines on curved surfaces. IMA J. Math. Control In. 6, 465-473.
• 24: F. C. Park , Bahram Ravani, Smooth invariant interpolation of rotations, ACM Transactions on Graphics (TOG), v.16 n.3, p.277-295, July 1997 [doi>10.1145/256157.256160]
• 25: PARKER,R.L.AND DENHAM, C. F. 1979. Interpolation of unit vectors. Geophys. J. Roy. Astronom. Soc. 58, 685-687.
• 26: Elijah Polak, Optimization: algorithms and consistent approximations, Springer-Verlag New York, Inc., New York, NY, 1997
• 27: Ravi Ramamoorthi , Alan H. Barr, Fast construction of accurate quaternion splines, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.287-292, August 1997 [doi>10.1145/258734.258870]
• 28: Ravi Ramamoorthi , Cindy Ball , Alan H. Barr, Dynamic Splines with Constraints for Animation, California Institute of Technology, Pasadena, CA, 1997
• 29: ROBERTS,K.S.,BISHOP,G.,AND GANAPATHY, S. K. 1988. Smooth interpolation of rotational matrices. In Proceedings CVPR'88: Computer Vision and Pattern Recognition, IEEE Computer Science Press, Los Alamitos, Calif., 724-729.
• 30: Ken Shoemake, Animating rotation with quaternion curves, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.245-254, July 1985
• 31: SHOEMAKE, K. 1987. Quaternion calculus and fast animation. In SIGGRAPH'87 Course Notes on State of the Art Image Synthesis. ACM, New York, pp. 101-121.
• 32: SPIVAK, M. 1965. Calculus on Manifolds. Benjamin/Cummings Publishing, Menlo Park, Calif.
• 33: THOMPSON,R.AND CLARK, R. M. 1982. A robust least-squares Gondwanan apparent polar wander path and the question of paleomagnetic assessment of Gondwanan reconstructions. Earth Planetary Sci. Lett. 57, 152-158.
• 34: WAGNER, G. 1990. On means of distances on the surface of a sphere (lower bounds). Pacific J. Math. 144, 389-398.
• 35: WAGNER, G. 1992. On means of distances on the surface of a sphere. II (lower bounds). Pacific J. Mathematics, 154, 381-396.
• 36: WANG,W.AND JOE, B. 1993. Orientation interpolation in quaternion space using spherical biarcs. In Proceedings of Graphics Interface'93. Morgan-Kaufmann, San Francisco Calif. pp. 24-32.
• 37: WATSON, G. S. 1983. Statistics on Spheres. Wiley, New York.
• 38: Alan Watt , Mark Watt, Advanced animation and rendering techniques, ACM Press, New York, NY, 1991
• 39: WOLF, R. 1994. On the average distance property of spheres in Banach spaces. Archives Math. 62, 338-344.
• 40: ZEFRAN,M.AND KUMAR, V. 1996. Planning of smooth motions on SE(3). In Proceedings of the IEEE International Conference on Robotics and Animation. IEEE Computer Society Press, Los Alamitos, Calif., pp. 121-126.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Line and curve generation
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

General Terms:
Algorithms, Theory

Keywords:
Bézier curve, B-spline, barycentric coordinates, least squares minimization, quaternion interpolation, quaternions, spherical average, spherical interpolation, spherical mean, spline curve, spline interpolation