RealTime
Optimizations
We already
talked about some optimizations that can be done to evaluate NURBS surfaces
more quickly. The first, which is used by the sample code, is to use
uniform tessellation and preevaluate the basis functions and their
derivatives at the tessellation points. We also mentioned the possibility
of transforming surface control points into projected space and doing
our surface tessellation in that space. While this works, lighting can
be difficult (or impossible) if you use anything other than directional
lights because distance is not preserved in perspective projected space.
If you're using light maps in your engine I would highly recommend transforming
control points and generating vertices in projected space. You can modify
TessellateSurface() to do the divide by homogeneous w and viewport
scaling to generate vertices in screen space.
To keep memory requirements minimal, we render the surface by generating
two rows of surface points and then passing a triangle strip to the
API (Direct3D* in our case). If a surface didn't need to be retessellated
at every frame, then we could generate all the surface points and store
these in an array. Depending on the application, it may still be quicker
to tessellate the surface at every frame rather than having to fetch
the generated vertices from memory (with corresponding cache misses).
You'll need to experiment with your particular application to see what
works best.
Aside
from the algorithmic optimizations just discussed, we can achieve better
performance by using the new Streaming SIMD Extensions supported by
Intel's Pentium III processor. These extensions allow us to do mathematical
operations on four floating point values at one time (for more information
on the Streaming SIMD Extensions of the Intel Pentium III processor,
visit http://developer.intel.com/design/pentiumiii/).
Since for NURBS surfaces we're dealing with four coordinates (x,
y, z, and w) we can do the same operations to all four at
once. TessellateSurfaceSSE() uses intrinsic functions provided by the
Intel C/C++ Compiler version 4.0 to evaluate all four coordinates of
a NURBS surface point at once.
Other
optimizations are possible depending on the quality vs. speed tradeoffs
acceptable by a particular application. For example, one could choose
to generate normals only every other surface point (or less frequently)
and then linearly interpolate normals in between.
More
Notes on the Sample Code
I should
mention a few last things about the sample code
contained in the download. The sample requires the Microsoft DirectX
7 SDK to build or run and was written using C++ and built using Microsoft
Visual C++ 6.0. If you don't have the Intel C/C++ compiler version 4.0
included with version 4 of the Intel VTune product, you'll need to change
a line in DRGNURBSSurface.h. The line reads "#define SUPPORT_PENTIUM_III
1" and should be changed to "#define SUPPORT_PENTIUM_III 0".
You can then rebuild everything using the Microsoft compiler (or other
C++ compiler) and get to see the code working. You won't be able to
enable the tessellation routine that uses the Streaming SIMD Extensions
of the Intel Pentium III processor, though.
While
running the application, pressing 'H' will bring up a help screen of
available keys. Most are self explanatory. One worth mentioning is the
'M' key that causes the display to switch between two different "Objects".
The objects are either:
 A single
NURBS surface with 100 control points
 Nine
NURBS surfaces with 16 control points each
You'll
notice when viewing the nine surfaces that there are hard creases between
the surfaces. This doesn't happen with the single surface. When changing
the tessellation level, for the single NURBS surface, there are actually
9 times as many points generated as what the number indicates. This
is done to keep a somewhat consistent look between the shapes of the
two different "Objects".
Additional
Details and Potential Pitfalls
I've discussed
the math behind parametric surfaces and the basics of rendering them
and hopefully made them seem appealing as an alternative to polygonal
models. What I haven't addressed are some of the problems that are unique
to parametric surfaces and some of the trickier aspects of using parametric
surfaces in place of polygonal models.
Some of
the more common issues with parametric surfaces are:
 Texture
mapping  A simple approach to texture mapping a parametric surface
is to use the u and v parameter values as texture coordinates
(scaled appropriately to the 0 to 1 range). This works fine in some
cases (and is what the sample code does), but there may be cases that
this won't work for (if the knot vector is very nonuniform, then
the texture will be stretched and squashed). To fix this problem,
a second parametric surface can be used to generate texture coordinates.
This increases overhead substantially, but may be the only solution
(and it provides the most flexibility). Many rendering packages allow
artists to apply textures to a parametric surface by using a second
surface to map the texture coordinates. Keep this in mind as you use
parametric surfaces for your applications.
 Cracking
 When two parametric surfaces meet at an edge (or one parametric
surface meets a polygonal surface) it's possible for a crack to appear
between the surfaces if their degrees of tessellation differ (or it
they're just different sizes). This problem can be solved on a per
application basis by adding connectivity information to the surfaces.
It's not trivial to fix, but it's not impossible.
 Collision
detection  If you're doing collision detection in your application,
you have several choices with parametric surfaces:
 Do
collision detection on the mesh of control points by treating
the mesh as a polygonal mesh  this is approximate and may be
too course in some instances.

Store all the generated triangles and do collision detection on
these  while more accurate, it's more memory intensive as well
as computationally intensive
 Depending
on what types of objects may be colliding, you can solve the parametric
surface equations with equations representing the other objects
(even lines are difficult, though) and then just plugandchug
to find collision points
 Use
a combination of (a) and (b) by starting with (a) and then refining
the surface to triangles to determine an exact hit.
 Clipping
 For surfaces that are partially within the viewing frustum, it can
be difficult to clip prior to generating triangles. The problem is
that you can't just clip control points because doing so would make
the tessellation of the surface difficult to impossible. The easiest
solution is to just generate triangles and then clip the triangles
 the downside to this is the possibility of generating many more
triangles than needed.
 Backsurface
Culling  Aside from clipping, it is also difficult to easily
cull backfacing surfaces or portions of surfaces for similar reasons
to the clipping problem. For example, a sphere can be defined with
one surface but only half of the sphere is ever visible at one time.
It would be nice to be able to cull the backfacing portion of the
sphere before tessellation, but this is difficult to do.
 Tessellation
 Although a uniform tessellation algorithm is easy to implement and
can run fast, in some instances other algorithms may provide better
performance/quality. Surfaces that have very curvy areas as well as
very flat areas may be better tessellated with a nonuniform tessellation
algorithm.
 Nonlocal
refinement not supported  When refining a surface (i.e. adding
detail), you must add control points in complete rows and columns
so the control mesh remains a regular grid of points. This causes
excessive control points to be added just to add detail in a small,
localized region of a surface. Note that this is not an implementation
issue, but rather an issue with NURBS surfaces (and other parametric
surfaces).
 Degenerate
Normals  Because it's possible to have control points that are
at the same location, it's possible for the derivatives of the surface
to vanish (i.e. go to zero). This causes the calculation of surface
normals to fail. To solve this, it is necessary to look at surrounding
points and derivatives if one of the tangents gets too close to zero.
Conclusion
We've
covered a lot of information in this article. We've been introduced
to parametric curves and surfaces and should have a decent understanding
of the concepts behind them. We've learned what's involved in rendering
parametric surfaces and can see how the data requirements are smaller
than the polygonal models that can be generated. And we should now have
an idea how to implement some of the creative types of 3D content we
talked about in the introduction.
Given
that the field of study of parametric surfaces is enormous, we've only
lightly touched the surface (no pun intended) of what's possible. Experimenting
with parametric surfaces is exciting. I encourage you to check out the
sample code and get a feel for how you can incorporate NURBS surface
rendering into your 3D engine today.
References
and Further Reading
Piegl,
Les and Tiller, Wayne. The NURBS Book, 2nd Edition, Berlin, Germany:
SpringerVerlag, 1996.
Foley, j., van Dam, A., Feiner, S., and Hughes, J. Computer Graphics:
Principles and Practice, Reading, MA: AddisonWesley, 1990.
Dean
is a Senior Technical Marketing Engineer with Intel's Developer Relations
Division. He is currently researching realtime physics with an emphasis
on cloth simulation. He welcomes email regarding NURBS and other parametric
surfaces, or anything mathematical and related to realtime 3D graphics.
He can be reached at [email protected].