• 08/10/13 02:14 AM
    Sign in to follow this  

    Practical Guide to B-Splines, Part 1: A Graphical Approach

    General and Gameplay Programming

    cadjunkie

    If you're already familiar with the Bezier formulation of curves, then you shouldn't feel overwhelmed by the topics presented here. If you're not, read the previous article "The Practical Guide to Bezier Curves". This article is a primer for the next article in this series. I believe this article and its companions to be essential to understanding a very common and powerful set of curves and surfaces.

    Disclaimer

    The information presented here might seem new to anyone familiar with traditional B-spline formulations. It's not meant as a replacement to the mathematical methods, which are almost certainly more efficient. This article is meant, however, to introduce the concepts behind B-splines in a more intuitive manner than simply deciphering things through equations. This graphical approach is mathematically equivalent to the traditional definitions of B-splines with full generality preserved.

    What is a B-spline?

    You can think of a B-spline as just a series of Bezier curves joined together with a certain degree of continuity. What determines how these curves are joined? The answer is the knot vector. For example, the knot vector or a degree-3 B-spline \( U = \{ 0,0,0,0,1,2,2,2,2 \} \) says that this B-spline consists of 2 Bezier curves with parameter domains \([0,1]\) and \([1,2]\), they have Bezier end conditions (meaning that the control points at the ends of the curve are on the curve), and that the continuity of the curves at u=1 is \(C^2\). How did we know all that just from the knot vector? To understand this, we have to introduce a notation invented by Dr. Lyle Ramshaw called polar form.

    Polar Form

    Polar form is a kind of notation that allows us to associate the values in the knot vector to specific control points. This allows us to perform mathematical operations on the B-spline using graphical techniques. There are 4 rules that summarize how to use polar form.

    1. For a degree-n Bezier curve defined on a parameter interval [a,b], the control points of the curve are labeled as \( P_i = P(u_1,u_2,\cdots,u_n)\), where \( u_j = \begin{cases}a,& j \leq n-i \\ b,& otherwise \end{cases} \).
    2. For a degree-n B-spline with a knot vector \( \{ t_1,t_2,t_3,t_4,\cdots \} \), the polar form of each control point is a group of n adjacent knots. In polar form, the first and last knot values give us no information, so we leave them off. For example, a "regular" degree-3 B-spline would have a knot vector like \( U = \{ 0,0,0,0,1,2,2,2,2 \} \), but in polar form we would see the knot vector as \( U = \{ 0,0,0,1,2,2,2 \} \). For this example, the control points would be labeled as: \( P_0 = P(0,0,0)\),\( P_1 = P(0,0,1)\),\( P_2 = P(0,1,2)\),\( P_3 = P(1,2,2)\),\( P_4 = P(2,2,2) \).
    3. All combinations of the polar values are equivalent. For example, \( P(1,0,0,2) = P(0,1,0,2) = P(0,0,1,2) = P(2,1,0,0) = \cdots \) and so on.
    4. Given 2 polar values that only differ by one value, such as \( P_1 = P(u_1,u_2,u_3,\cdots,a) \) and \( P_2 = P(u_1,u_2,u_3,\cdots,b) \), we can find a value \( P_3 = P(u_1,u_2,u_3,\cdots,c) \) by linear interpolation: \( P_3 = \frac{(b-c)P_1+(c-a)P_2}{b-a} \).

    de Casteljau using Polar Form

    In an attempt to show how polar form is equivalent to mathematical methods, we'll use it to perform the de Casteljau algorithm. Starting with a cubic Bezier curve, the polar form of the curve using Rule 1 is: \[ P_0 = P(0,0,0), P_1 = P(0,0,1), P_2 = P(0,1,1), P_3 = P(1,1,1) \] The de Casteljau algorithm divides a Bezier curve on the interval [0,1] at a parameter t. We can use Rule 4 of our polar form iteratively to accomplish the same task: \[ P(0,0,t) = (1-t)P(0,0,0) + tP(0,0,1) \]

    Conclusion

    References

    A lot of the information here was taught to me by Dr. Thomas Sederberg (associate dean at Brigham Young University, inventor of the T-splines technology, and recipient of the 2006 ACM SIGGRAPH Computer Graphics Achievement Award). The rest came from my own study of relevant literature.

    Article Update Log

    09 Aug 2013: Initial release



      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.