Sliding windows algorithm for B-spline multiplication

ABSTRACT

B-spline multiplication, that is, finding the coefficients of the product B-spline of two given B-splines, is useful as an end result, in addition to being an important prerequisite component to many other symbolic computation operations on B-splines. Algorithms for B-spline multiplication standardly use indirect approaches such as nodal interpolation or computing the product of each set of polynomial pieces using various bases. The original direct approach is complicated. B-spline blossoming provides another direct approach that can be straightforwardly translated from mathematical equation to implementation; however, the algorithm does not scale well with degree or dimension of the subject tensor product B-splines. We present the Sliding Windows Algorithm (SWA), a new blossoming based algorithm for B-spline multiplication that addresses the difficulties mentioned heretofore.

REFERENCES

• 1: Chen, X., Cohen, E., Damon, J., and Cohen, E. 2006. Tracking intersection curves of two deforming surfaces. Springer-Verlag Lecture Notes in Computer Science 4077 (GMP 2006): 101--114.
• 2: Chen, X. 2007. Dynamic geometric computation by singularity detection and shape analysis. Ph.D. Thesis Manuscript.
• 3: Cohen, E., Riesenfeld, R. F., and Elber, G. 2001. Geometeric Modeling with Splines: An Introduction, 1 ed. A K Peters.
• 4: De Boor, C. 1978. A Practical Guide to Splines, 1 ed. Springer-Verlag.
• 5: DeRose, T., and Goldman, R. 1991. A tutorial introduction to blossoming. In Geometric Modeling: Methods and Applications, Springer-Verlag, H. Hagen and D. Roller, Eds., 267--286.
• 6: Tony D. DeRose , Ronald N. Goldman , Hans Hagen , Stephen Mann, Functional composition algorithms via blossoming, ACM Transactions on Graphics (TOG), v.12 n.2, p.113-135, April 1993 [doi>10.1145/151280.151290]
• 7: Gershon Elber , Elaine Cohen, Second-order surface analysis using hybrid symbolic and numeric operators, ACM Transactions on Graphics (TOG), v.12 n.2, p.160-178, April 1993 [doi>10.1145/151280.151283]
• 8: Elber, G., and Cohen, E. 1999. A unified approach to verification in 5-axis freeform milling environments. Computer-Aided Design 31, 13, 795--804.
• 9: Elber, G., and Kim, M.-S. 2000. A computational model for nonrational bisector surfaces: Curve-surface and surface-surface bisectors. GMP, 364--372.
• 10: Gershon Elber , Myung-Soo Kim, Geometric constraint solver using multivariate rational spline functions, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.1-10, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376958]
• 11: Elber, G., Chen, X., and Cohen, E. 2005. Mold accessibility via gauss map analysis. ASME Transactions, Journal of Computing & Information Science in Engineering, June 2005:79--85.
• 12: Gershon Elber, Free form surface analysis using a hybrid of symbolic and numeric computation, University of Utah, Salt Lake City, UT, 1992
• 13: Gerald Farin, Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 14: Jean Gallier, Curves and surfaces in geometric modeling: theory and algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 15: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 16: E. T. Y. Lee, Computing a chain of blossoms, with application to products of splines, Computer Aided Geometric Design, v.11 n.6, p.597-620, Dec. 1994 [doi>10.1016/0167-8396(94)90054-X ]
• 17: Morken, K. M. 1991. Some identities for products and degree raising of splines. Constructive Approximation 7, 195--208.
• 18: Piegl, L. A., and Tiller, W. 1997. Symbolic operators for nurbs. Computer-Aided Design 29, 5, 361--368.
• 19: Ramshaw, L. 1987. Blossoming: A connect-the-dots approach to splines. System Research Center, DEC.
• 20: L. Ramshaw, Blossoms are polar forms, Computer Aided Geometric Design, v.6 n.4, p.323-358, Nov. 1989 [doi>10.1016/0167-8396(89)90032-0 ]
• 21: Hans-Peter Seidel, An Introduction to Polar Forms, IEEE Computer Graphics and Applications, v.13 n.1, p.38-46, January 1993 [doi>10.1109/38.180116 ]
• 22: Seong, J.-K., Elber, G., and Kim, M.-S. 2006. Trimming local and global self-intersections in offset curves/surfaces using distance maps. Computer-Aided Design 38, 3 (March), 183--193.
• 23: Joon-Kyung Seong , Ku-Jin Kim , Myung-Soo Kim , Gershon Elber, Perspective silhouette of a general swept volume, The Visual Computer: International Journal of Computer Graphics, v.22 n.2, p.109-116, February 2006 [doi>10.1007/s00371-006-0371-1]
• 24: Evan C. Sherbrooke , Nicholas M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, v.10 n.5, p.379-405, Oct. 1993 [doi>10.1016/0167-8396(93)90019-Y ]
• 25: Kenji Ueda, Multiplication as a general operation for splines, Proceedings of the international conference on Curves and surfaces in geometric design, p.475-482, November 1994, Chamonix-Mont-Blanc, France

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

Keywords:
NURBS multiplication, blossoming, sliding windows algorithm