Contents

Alternatives to Polygonal Models B-Spline Basis Functions Parametric Surfaces What About Surface Normals? Real-Time Optimizations

Real-Time 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 pre-evaluate 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 re-tessellated 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:

1. A single NURBS surface with 100 control points
2. 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:

1. 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 non-uniform, 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.
   
   
2. 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.
   
   
3. 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 plug-and-chug 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.
     
     
4. 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.
   
   
5. Back-surface Culling - Aside from clipping, it is also difficult to easily cull back-facing 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 back-facing portion of the sphere before tessellation, but this is difficult to do.
   
   
6. 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 non-uniform tessellation algorithm.
   
   
7. Non-local 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).
   
   
8. 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: Springer-Verlag, 1996.

Foley, j., van Dam, A., Feiner, S., and Hughes, J. Computer Graphics: Principles and Practice, Reading, MA: Addison-Wesley, 1990.

Dean is a Senior Technical Marketing Engineer with Intel's Developer Relations Division. He is currently researching real-time physics with an emphasis on cloth simulation. He welcomes e-mail regarding NURBS and other parametric surfaces, or anything mathematical and related to real-time 3D graphics. He can be reached at dean.p.macri@intel.com.

[Back to] Alternatives to Polygonal Models