Monday, January 19, 2015

What's a NURBS? (Part 1)


You may or may not know that NURDS, name of my Meetup group (and this blog), is a very nerdy pun on the graphics term NURBS. Though it's not one that I can claim credit (blame?) for, as the group was called that when I took it over.

What's a NURBS, you may ask? It's an acronym for: Non Uniform Rational Bezier Spline. Personally I don't think this collection of apparently meaningless words explains very much at all. But their back story is pretty interesting (in my opinion at least), so I'll try explain it a little in this post. Note that many of the historical details I mention below come from Alastair Townsend's excellent webpage on the subject.

Splines

In the 3D graphics world splines are considered a mathematical concept, that only exists in software. In fact splines are a real physical thing.  Splines have been used to model curved surfaces for centuries before the invention of the modern computer. As far back as the 18th Century European shipbuilders modeled the curve of a ship's hull using a flexible piece of wood, called a spline. Wooden splines can be bent to produce the curves required to design different parts of ship's hull. By tracing along the curve of the spline, a free-form curve that would incredibly hard to draw accurately by hand can be committed to paper. Splines of this kind are used by yacht designers to this day.
An actual real life spline

Bezier Curves

Computers do not enter in the story until the 1950s. In this era Computer Numerical Control (CNC) machines were starting to become common in the car industry. These early computer controlled machine tools automatically produced components, such as car body panels, according to a instructions fed in on punched paper tape.

These machines could represent simple shapes like lines and circles easily, but producing the spline curves that designers were used to was a much harder problem. Two Frenchmen, Paul de Faget de Casteljau and Pierre B├ęzier working for French car makers Citroen and Renault respectively, were attempting to crack this puzzle.

The result was what is now know as Bezier splines. These are based on the concept of a Bezier curve. A Bezier curve is formed by a parameteric function that takes four 3D points (in its most common, cubic, form) and produces a point on the curve for a given value of the parameter t:
\[ P(t) = (1-t)^3P_0 + 3t(1-t)^2P_1 + 3t^2(1-t)P_2 + t^3 P_3 \]

As t varies between 0.0 and 1.0 the curve's shape is traced out by the function. The four points, known as control points, define the shape of the curve.  It will pass through the first point (when t is 0.0) and the last point (when t is 1.0).  While the other two points influence the shape of the curve, it does not pass through them.  This way, just as with physical wooden splines, a complicated free-form curve can be created by placing the four control points.
Bezier curve (shown in green)

From a 3D graphics point of view Bezier curves also have the big advantage that the parametric function can be rearranged into set of simple matrix operations, so can be easily executed on graphics hardware:

\[ \left( \begin{matrix} 1 & t & t^2 & t^3 \end{matrix} \right)   \left(  \begin{matrix} 1 & 0 & 0 & 0 \\ -3 & 3 & 0 & 0 \\ 3 & -6 & 3 & 0 \\ -1 & 3 & -3 & 1 \end{matrix} \right)   \left( \begin{matrix} P_0 \\ P_1 \\ P_2 \\ P_3 \end{matrix} \right) \]

Bezier curves have the big restriction that they can only have exactly four control points (technically they have degree+1 control points, and cubic is another way of saying "has a degree of three"). However multiple Bezier curves can be combined to form a curve with an arbitrary number of points. The problem is that at the point where one curve joins another a discontinuity occurs, as both curves are forced to pass through the same start/end point.
Discontinuity between two Bezier curves



In the next part of this post I'll explain how Bezier curves can be expanded to Bezier splines, and NURBS. Hopefully this post was interesting, feel free to comment if you have feedback of any kind.

1 comment:

  1. Good stuff man, it's cool to learn whats behind all the mouse clicks and renders!

    ReplyDelete