Blossoms and CAGD Algorithms

Last Updated: October 10, 2012

Blossoming is a technique for analysising polynomial functions. For a degree n, univariate polynomial F, there exists a unique blossom f such that

f is n-variate,
f is multi-affine,
f agrees with F on the diagonal (e.g., f(u,u,u,u) = F(u)).

In short, the blossom allows us the analyse polynomial functions by performing repeated affine combinations.

Although the blossom has primarily been used as a theoretical technique, it can also be used to derive efficient algorithms. The goal of this work is to implement an efficient software library to support the blossom abstraction, and to develop algorithms based on these ideas and on this software package.

As a strong, mathematical base layer of software, we have developed a Euclidean geometry abstract data type, which we have implemented in C, C++, and Java. The key observation here is that the matrix abstraction commonly used in graphics programs provides a linear algebra abstraction. Unfortunately, use of this linear algebra abstraction leads to subtle errors when doing the type of geometric programming commonly found in computer graphics. By providing a geometric abstraction, such program errors are eliminated.

People

The following people are currently working on this project:

Stephen Mann
Nathan Litke
Tony DeRose (Pixar)
Ronen Barzel (Pixar)

Software

So far, two libraries have been implemented:

Coordinate Free Geometry Software
Blossoming Software , a C++ library supporting blossoms.

Papers

Stephen Mann, Nathan Litke, and Tony DeRose, ``A Coordinate Free Geometry ADT,'' Research Report CS-97-15, Computer Science Department, University of Waterloo (June 1997). This technical report describes a software package for a Euclidean geometry ADT.
Wayne Liu and Stephen Mann, ``An Optimal Algorithm for Expanding the Composition of Polynomials,'' ACM TOG, April, 1997. This paper describes an efficient algorithm for polynomial composition that was developed using blossoming ideas.
Stephen Mann, Algorithms from Blossoms, to appear in the Proceedings of the 1996 Conference on Curves and Surfaces, Oct 1996.
An expanded version of this paper is available as a technical report: Stephen Mann, ``Algorithms from Blossoms,'' Research Report CS-96-29, Computer Science Department, University of Waterloo (October 1996).
Wayne Liu and Stephen Mann, ``Programming Support for Blossoming'', in the Graphics Interfaces '96 Conference Proceedings. This paper describes the blossoming software. See also Wayne Liu's Masters Thesis.
Wayne Liu, ``A Simple Efficient Degree-Raising Algorithm for B-spline Curves,'' accepted for publication in CAGD, July 1996. This paper describes a degree-raising algorithm for B-splines derived from blossoming.

Back one level.