GPU-based trimming and tessellation of NURBS and T-Spline surfaces

ABSTRACT

As there is no hardware support neither for rendering trimmed NURBS -- the standard surface representation in CAD -- nor for T-Spline surfaces the usability of existing rendering APIs like OpenGL, where a run-time tessellation is performed on the CPU, is limited to simple scenes. Due to the irregular mesh data structures required for trimming no algorithms exists that exploit the GPU for tessellation. Therefore, recent approaches perform a pretessellation and use level-of-detail techniques. In contrast to a simple API these methods require tedious preparation of the models before rendering and hinder interactive editing. Furthermore, due to the tremendous amount of triangle data smooth zoom-ins from long shot to close-up are not possible, In this paper we show how the trimming region can be defined by a trim-texture that is dynamically adapted to the required resolution and allows for an efficient trimming of surfaces on the GPU. Combining this new method with GPU-based tessellation of cubic rational surfaces allows a new rendering algorithm for arbitrary trimmed NURBS and T-Spline surfaces with prescribed error in screen space on the GPU. The performance exceeds current CPU-based techniques by a factor of up to 1000 and makes real-time visualization of real-world trimmed NURBS and T-Spline models possible on consumer-level graphics cards.

REFERENCES

• 1: Abi-Ezzi, S. S., and Subramanian, S. 1994. Fast dynamic tessellation of trimmed nurbs surfaces. Computer Graphics Forum 13, 3, 107--126.
• 2: Balázs, Á., Guthe, M., and Klein, R. 2004. Fat borders: Gap filling for efficient view-dependent lod rendering. Computers & Graphics 28, 1, 79--86.
• 3: Bolz, J., and Schröder, P., 2003. Evaluation of subdivision surfaces on programmable graphics hardware. submitted.
• 4: M. Bóo , M. Amor , M. Doggett , J. Hirche , W. Strasser, Hardware support for adaptive subdivision surface rendering, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.33-40, August 2001, Los Angeles, California, United States [doi>10.1145/383507.383522]
• 5: Jatin Chhugani , Subodh Kumar, View-dependent adaptive tessellation of spline surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.59-62, March 2001 [doi>10.1145/364338.364349]
• 6: Cohen, E., Lyche, T., and Riesenfeld, R. F. 1980. Discrete b-spline and sub-division techniques in computer aided geometric design and computer graphics. Computer Graphics and Image Processing 14, 2, 87--111.
• 7: Paul Debevec, Rendering synthetic objects into real scenes: bridging traditional and image-based graphics with global illumination and high dynamic range photography, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.189-198, July 1998 [doi>10.1145/280814.280864]
• 8: Matthias Eck, Degree reduction of Be´zier curves, Computer Aided Geometric Design, v.10 n.3-4, p.237-251, Aug. 1993
• 9: Daniel Filip , Robert Magedson , Robert Markot, Surface algorithms using bounds on derivatives, Computer Aided Geometric Design, v.3 n.4, p.295-311, 1987 [doi>10.1016/0167-8396(86)90005-1]
• 10: Forrest, A. 1972. Interactive interpolation and approximation by bézier polynomials. The Computer Journal 15, 1, 71--79.
• 11: D. R. Forsey , R. V. Klassen, An adaptive subdivision algorithm for crack prevention in the display of parametric surfaces, Proceedings on Graphics interface '90, p.1-8, June 1990, Halifax, Nova Scotia
• 12: Michael Guthe , Jan Meseth , Reinhard Klein, Fast and Memory Efficient View-Dependent Trimmed NURBS Rendering, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.204, October 09-11, 2002
• 13: Paul Heckbert, Color image quantization for frame buffer display, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.297-307, July 26-30, 1982, Boston, Massachusetts, United States
• 14: Brian Von Herzen , Alan H. Barr, Accurate triangulations of deformed, intersecting surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.103-110, July 1987
• 15: Kanai, T., and Yasui, Y. 2004. Per-pixel evaluation of parametric surfaces on gpu. In ACM Workshop on General Purpose Computing Using Graphics Processors (also at SIGGRAPH 2004 poster session).
• 16: Subodh Kumar , Dinesh Manocha , Hansong Zhang , Kenneth E. Hoff, III, Accelerated walkthrough of large spline models, Proceedings of the 1997 symposium on Interactive 3D graphics, p.91-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253313]
• 17: Tomoyuki Nishita , Thomas W. Sederberg , Masanori Kakimoto, Ray tracing trimmed rational surface patches, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.337-345, Aug. 1990
• 18: Park, Y., and Choi, U. J. 1995. Degree reduction of bézier curves and its error analysis. J. Austral. Math. Soc. Ser. B 36, 399--413.
• 19: Alyn Rockwood , Kurt Heaton , Tom Davis, Real-time rendering of trimmed surfaces, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.107-116, July 1989
• 20: Thomas W. Sederberg , David L. Cardon , G. Thomas Finnigan , Nicholas S. North , Jianmin Zheng , Tom Lyche, T-spline simplification and local refinement, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 21: Micheal Shantz , Sheue-Ling Chang, Rendering trimmed NURBS with adaptive forward differencing, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.189-198, Aug. 1988
• 22: Wimmer, M., Scherzer, D., and Purgathofer, W. 2004. Light space perspective shadow maps. In Rendering Techniques 2004 (Proceedings of Eurographics Symposium on Rendering), A. Keller and H. W. Jensen, Eds. Eurographics Association, June, 143--152.
• 23: Jianmin Zheng , Guozhao Wang, Perturbing Bézier coefficients for best constrained degree reduction in the L2-norm, Graphical Models, v.65 n.6, p.351-368, November 2003 [doi>10.1016/j.gmod.2003.07.001]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

Keywords:
GPU-based algorithms, NURBS and T-Spline surfaces, trimming