Performing efficient NURBS modeling operations on the GPU

ABSTRACT

We present algorithms for evaluating and performing modeling operatyons on NURBS surfaces using the programmable fragment processor on the Graphics Processing Unit (GPU). We extend our GPU-based NURBS evaluator that evaluates NURBS surfaces to compute exact normals for either standard or rational B-spline surfaces for use in rendering and geometric modeling. We build on these calculations in our new GPU algorithms to perform standard modeling operations such as inverse evaluations, ray intersections, and surface-surface intersections on the GPU. Our modeling algorithms run in real time, enabling the user to sketch on the actual surface to create new features. In addition, the designer can edit the surface by interactively trimming it without the need for re-tessellation. We also present a GPU-accelerated algorithm to perform surface-surface intersection operations with NURBS surfaces that can output intersection curves in the model space as well as in the parametric spaces of both the intersecting surfaces at interactive rates.

REFERENCES

• 1: S. S. Abi-Ezzi , M. J. Wozny, Factoring a homogeneous transformation for a more efficient graphics pipeline, Computer Graphics Forum, v.9 n.3, p.245-255, September 1990 [doi>10.1111/j.1467-8659.1990.tb00401.x]
• 2: R. E. Barnhill , S. N. Kersey, A marching method for parametric surface/surface intersection, Computer Aided Geometric Design, v.7 n.1-4, p.257-280, Jun. 1990 [doi>10.1016/0167-8396(90)90035-P]
• 3: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 4: Nathan A. Carr , Jared Hoberock , Keenan Crane , John C. Hart, Fast GPU ray tracing of dynamic meshes using geometry images, Proceedings of Graphics Interface 2006, June 07-09, 2006, Quebec, Canada
• 5: Corney, J., and Lim, T. 2001. 3D Modeling with ACIS. Saxe-Coburg.
• 6: De Boor, C. 1978. A practical guide to splines. Springer-Verlag.
• 7: Gershon Elber , Myung-Soo Kim, Geometric constraint solver using multivariate rational spline functions, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.1-10, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376958]
• 8: 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]
• 9: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 10: Gress, A., Guthe, M., and Klein, R. 2006. GPU-based collision detection for deformable parameterized surfaces. Computer Graphics Forum 25, 3, 497--506.
• 11: Michael Guthe , Aákos Balázs , Reinhard Klein, GPU-based trimming and tessellation of NURBS and T-Spline surfaces, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 12: Guthe, M., Balázs, A., and Klein, R. 2006. GPU-based appearance preserving trimmed NURBS rendering. Journal of WSCG 14.
• 13: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 14: Matt Pharr , Randima Fernando, GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation (Gpu Gems), Addison-Wesley Professional, 2005
• 15: Kanai, T. 2007. Fragment-based evaluation of Non-Uniform B-spline surfaces on GPUs. Computer-Aided Design and Applications 4, 3, 287--294.
• 16: Peter Kipfer , Mark Segal , Rüdiger Westermann, UberFlow: a GPU-based particle engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058146]
• 17: A. Kolb , L. Latta , C. Rezk-Salama, Hardware-based simulation and collision detection for large particle systems, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058147]
• 18: G. A. Kriezis , P. V. Prakash , N. M. Patrikalakis, A method for intersecting algebraic surfaces with rational polynomial patches in presented, Computer-Aided Design, v.22 n.10, p.645-654, Dec. 1990 [doi>10.1016/0010-4485(90)90011-Z]
• 19: Adarsh Krishnamurthy , Rahul Khardekar , Sara McMains, Direct evaluation of NURBS curves and surfaces on the GPU, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236293]
• 20: Shankar Krishnan , Dinesh Manocha, An efficient surface intersection algorithm based on lower-dimensional formulation, ACM Transactions on Graphics (TOG), v.16 n.1, p.74-106, Jan. 1997 [doi>10.1145/237748.237751]
• 21: Charles Loop , Jim Blinn, Resolution independent curve rendering using programmable graphics hardware, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 22: William Martin , Elaine Cohen , Russell Fish , Peter Shirley, Practical ray tracing of trimmed NURBS surfaces, Journal of Graphics Tools, v.5 n.1, p.27-52, Sept. 2000
• 23: Tomoyuki Nishita , Thomas W. Sederberg , Masanori Kakimoto, Ray tracing trimmed rational surface patches, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.337-345, September 1990, Dallas, TX, USA
• 24: Nicholas M. Patrikalakis, Surface-to-Surface Intersections, IEEE Computer Graphics and Applications, v.13 n.1, p.89-95, January 1993 [doi>10.1109/38.180122]
• 25: Les Piegl , Wayne Tiller, The NURBS book, Springer-Verlag, London, 1995
• 26: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 27: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 28: Aristides A. G. Requicha , Jarek R. Rossignac, Solid Modeling and Beyond, IEEE Computer Graphics and Applications, v.12 n.5, p.31-44, September 1992 [doi>10.1109/38.156011]
• 29: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 30: Thompson, T., and Cohen, E. 1999. Direct haptic rendering of complex trimmed NURBS models. In 8th Annual Symp. Haptic Interfaces for Virtual Environment and Teleoperator Systems.
• 31: Daniel L. Toth, On ray tracing parametric surfaces, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.171-179, July 1985

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

Keywords:
GPU, NURBS, interactive trimming, intersection curves, inverse evaluation, prefix sum, sketching