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. ALFELD, P., NEAMTU, M., AND SHUMAKER, L. L. 1996. Bernstein-Bezier polynomials on spheres and sphere-like surfaces. Comput. Aided. Geom. Des. 13, 333-349.
2. ARVO, J. 1995. Startified sampling of spherical triangles. In Proceedings of SIGGRAPH'95. ACM, New York, pp. 437-438.
3. BARONTI, M., CASINI, E., AND PAPINI, P. L. 1997. Centroids, centers and medians: What is the difference? Geometriae Dedicata 68, 157-168.
4. BARR, A. H., CURRIN, B., GABRIEL,S.,AND HUGHES, J. 1992. Smooth interpolation of orientations with angular velocity constraints using quaternions. In Computer Graphics: SIGGRAPH'92 Conference Proceedings. ACM, NewYork, pp. 313-320.
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. FARIN, G. 1993. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. 3rd ed. (contains chapters by P. Bezier and W. Boehm), Academic Press, Boston, Mass.
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. HART,J.C.,FRANCIS,G.K.,AND KAUFFMAN, L. H. 1994. Visualizing quaternion rotation. ACM Trans. Graph. 13, 256-276.
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. KIM, M.-J., KIM, M.-S., AND SHIN, S. Y. 1995. A general construction scheme for unit quaternion curves with simple high order derivatives. In Comput. Graph. SIGGRAPH'95 Conference Proceedings, 369-376.
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. PARK,F.C.AND RAVANI, B. 1997. Smooth invariant interpolation of rotations. ACM Trans. Graph. 16, 227-295.
25. PARKER,R.L.AND DENHAM, C. F. 1979. Interpolation of unit vectors. Geophys. J. Roy. Astronom. Soc. 58, 685-687.
26. POLAK, E. 1997. Optimization: Algorithms and Consistent Approximations. In Applied Mathematical Sciences No. 124. Springer-Verlag, New York.
27. RAMAMOORTHI,R.AND BARR, A. H. 1997. Fast constuction of quaternion splines. In Computer Graphics: SIGGRAPH'97 Conference Proceedings, 287-292.
28. RAMAMOORTHI, R., BALL,C.,AND BARR, A. H. 1997. Dynamic splines with constraints for animation. Tech. Rep. CS-TR-97-03, Dept. of Computer Science, CalTech, Pasalena Calif.
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. SHOEMAKE, K. 1985. Animating rotation with quaternion curves. In Proceedings of SIGGRAPH'85. ACM, New York, pp. 245-254.
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. WATT,A.AND WATT, M. 1992. Advanced Animation and Rendering Techniques. Addison-Wesley, Reading, Mass.
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

• Computing methodologies

  • Computer graphics

    • Image manipulation

    • Shape modeling

      • Parametric curve and surface models

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Interpolation

  • Probability and statistics

    • Probabilistic representations

      • Nonparametric representations

        • Spline models