“Direct trimming of NURBS surfaces on the GPU” by Schollmeyer and Fröhlich

This paper presents a highly efficient direct trimming technique for NURBS surfaces, which is applicable to tessellation-based rendering as well as ray tracing systems. The central idea is to split the trim curves into monotonic segments with respect to the two parameter dimensions of the surface patches. We use an optimized bisection method to classify a point with respect to each monotonic trim curve segment without performing an actual intersection test. Our hierarchical acceleration structure allows the use of a large number of such curve segments and performs the bisection method only for points contained in the bounding boxes of the curve segments.We have integrated our novel point classification scheme into a GPU-based NURBS ray casting system and implemented the entire trimmed NURBS rendering algorithm in a single OpenGL GLSL shader. The shader can handle surfaces and trim curves of arbitrary degrees, which allows the use of original CAD data without incorporating any approximations. Performance data confirms that our trimming approach can deal with hundreds of thousands of trim curves at interactive rates. Our point classification scheme can be applied to other application domains dealing with complex curved regions including flood fills, font rendering and vector graphics mapped on arbitrary surfaces.

1. Balázs, Á., Guthe, M., and Klein, R. 2004. Efficient trimmed nurbs tessellation. Journal of WSCG 12, 1 (Feb.), 27–33.Google Scholar
2. Benthin, C., Wald, I., and Slusallek, P. 2004. Real-time rendering: Interactive ray tracing of free-form surfaces. In AFRIGRAPH ’04: Proceedings of the 3rd International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa, 99–106. Google ScholarDigital Library
3. Collins, G. E., and Loos, R. 1976. Polynomial real root isolation by differentiation. In SYMSAC ’76: Proceedings of the third ACM Symposium on Symbolic and Algebraic Computation, ACM, New York, NY, USA, 15–25. Google ScholarDigital Library
4. Efremov, A., Havran, V., and Seidel, H.-P. 2005. Robust and numerically stable bézier clipping method for ray tracing nurbs surfaces. In SCCG ’05: Proceedings of the 21st Spring Conference on Computer Graphics, ACM, New York, NY, USA, 127–135. Google ScholarDigital Library
5. Farin, G. 1993. Curves and Surfaces for Computer Aided Geometric Design (3rd ed.): A practical guide. Academic Press Professional, Inc., San Diego, CA, USA. Google ScholarDigital Library
6. Farouki, R. T. 1987. Trimmed-surface algorithms for the evaluation and interrogation of solid boundary representations. IBM J. Res. Dev. 31, 3, 314–334. Google ScholarDigital Library
7. Geimer, M., and Abert, O. 2005. Interactive ray tracing of trimmed bicubic bézier surfaces without triangulation. In Proceedings of WSCG, 71–78.Google Scholar
8. Guthe, M., Balázs, A., and Klein, R. 2005. Gpu-based trimming and tessellation of nurbs and t-spline surfaces. In ACM SIGGRAPH 2005 Papers, ACM, New York, NY, USA, 1016–1023. Google ScholarDigital Library
9. Joy, K. I., and Bhetanabhotla, M. N. 1986. Ray tracing parametric surface patches utilizing numerical techniques and ray coherence. In SIGGRAPH ’86: Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, 279–285. Google ScholarDigital Library
10. Kajiya, J. T. 1982. Ray tracing parametric patches. SIGGRAPH Comput. Graph. 16, 3, 245–254. Google ScholarDigital Library
11. Keyser, J., Culver, T., Manocha, D., and Krishnan, S. 1999. Mapc: a library for efficient and exact manipulation of algebraic points and curves. In SCG ’99: Proceedings of the Fifteenth Annual Symposium on Computational Geometry, ACM, New York, NY, USA, 360–369. Google ScholarDigital Library
12. Kumar, S., and Manocha, D. 1995. Efficient rendering of trimmed NURBS surfaces. Computer-Aided Design 27, 7, 509–521.Google ScholarCross Ref
13. Mudur, S., and Koparkar, P. 1984. Interval methods for processing geometric objects. IEEE Comput. Graph. Appl. 4, 2, 7–17. Google ScholarDigital Library
14. Nishita, T., Sederberg, T. W., and Kakimoto, M. 1990. Ray tracing trimmed rational surface patches. In SIGGRAPH ’90: Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, 337–345. Google ScholarDigital Library
15. Pabst, H.-F., Springer, J., Schollmeyer, A., Lenhardt, R., Lessig, C., and Froehlich, B. 2006. Ray casting of trimmed nurbs surfaces on the gpu. Symposium on Interactive Ray Tracing, 151–160.Google Scholar
16. Pavlidis, T. 1982. Algorithms for Graphics and Image Processing. Computer Science Press, Rockville, Maryland. Google ScholarDigital Library
17. Qin, Z., McCool, M. D., and Kaplan, C. 2008. Precise vector textures for real-time 3d rendering. In SI3D ’08: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, ACM, New York, NY, USA, 199–206. Google ScholarDigital Library
18. Rockwood, A., Heaton, K., and Davis, T. 1989. Real-time rendering of trimmed surfaces. In SIGGRAPH ’89: Proceedings of the 16th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, 107–116. Google ScholarDigital Library
19. Sederberg, T. W., and Wang, X. 1987. Rational hodographs. Computer Aided Geometric Design 4, 4 (Dec.), 333–335.Google ScholarDigital Library
20. Sederberg, T. W. 1995. Point and tangent computation of tensor product rational bézier surfaces. Computer Aided Geometric Design 12, 1, 103–106. Google ScholarDigital Library
21. Song, X., Sederberg, T. W., Zheng, J., Farouki, R. T., and Hass, J. 2004. Linear perturbation methods for topologically consistent representations of free-form surface intersections. Computer Aided Geometric Design 21, 3, 303–319. Google ScholarDigital Library
22. Toth, D. L. 1985. On ray tracing parametric surfaces. SIGGRAPH Computer Graphics 19, 3, 171–179. Google ScholarDigital Library
23. Wang, S.-W., Shih, Z.-C., and Chang, R.-C. 2000. An improved rendering technique for ray tracing bézier and b-spline surfaces. The Journal of Visualization and Computer Animation 11, 4 (Sept.), 209–219.Google ScholarCross Ref