“Real-time GPU rendering of piecewise algebraic surfaces” by Loop and Blinn

We consider the problem of real-time GPU rendering of algebraic surfaces defined by Bézier tetrahedra. These surfaces are rendered directly in terms of their polynomial representations, as opposed to a collection of approximating triangles, thereby eliminating tessellation artifacts and reducing memory usage. A key step in such algorithms is the computation of univariate polynomial coefficients at each pixel; real roots of this polynomial correspond to possibly visible points on the surface. Our approach leverages the strengths of GPU computation and is highly efficient. Furthermore, we compute these coefficients in Bernstein form to maximize the stability of root finding, and to provide shader instances with an early exit test based on the sign of these coefficients. Solving for roots is done using analytic techniques that map well to a SIMD architecture, but limits us to fourth order algebraic surfaces. The general framework could be extended to higher order with numerical root finding.

1. Bajaj, C. 1997. Implicit surface patches. In Introduction to Implicit Surfaces, Morgan Kaufman, J. Bloomenthal, Ed., 98–125.Google Scholar
2. Bangert, C., and Prautzsch, H. 1999. Quadric splines. Computer Aided Geometric Design 16, 6, 497–525.Google ScholarCross Ref
3. Blinn, J. 2003. Jim Blinn’s Corner Notation, notation, notation. Morgan Kaufmann. Google ScholarDigital Library
4. Blinn, J. 2005. How to solve a quadratic equation. IEEE CG & A 25, 6 (November/December), 76. Google ScholarDigital Library
5. Blinn, J. 2006. Jim Blinn’s Corner. IEEE CG & A.Google Scholar
6. Blythe, D. 2006. The Direct3D 10 System. ACM Transactions on Graphics. Siggraph Conference Proceedings. Google ScholarDigital Library
7. Dahman, W. 1989. Smooth peicewise quadric surfaces. In Mathmatical Methods in Computer Aided Geometric Design, Acadmemic Press, T. Lyche and L. Schumaker, Eds., 181–194. Google ScholarDigital Library
8. de Boor, C. 1987. B-form basics. In Geometric Modeling: Algorithms and New Trends, G. Farin, Ed. SIAM, 131–148.Google Scholar
9. Farouki, R. T., and Rajan, V. T. 1987. On the numerical condition of polynomials in bernstein form. Computer Aided Geometric Design 4, 191–216. Google ScholarDigital Library
10. Farouki, R. T., and Rajan, V. T. 1988. Algorithms for polynomials in bernstein form. Computer Aided Geometric Design 5, 1–26. Google ScholarDigital Library
11. Gray, K. 2003. The Microsoft DirectX 9 Programmable Graphics Pipeline. Microsoft Press. Google ScholarDigital Library
12. Guo, B. 1995. Quadric and cubic bitetrahedral patches. The Visual Computer 11, 5, 253–262.Google ScholarCross Ref
13. Hadwiger, M., Sigg, C., Scharsach, H., Bühler, K., and Gross, M. 2005. Real-time ray-casting and advanced shading of discrete isosurfaces. In Eurographics, Blackwell Publishing, M. Alexa and J. Marks, Eds., vol. 24.Google Scholar
14. Heckbert, P. 1984. The mathematics of quadric surface rendering and soid. Tech. Rep. 3-D Technical Memo 4, New York Institute of Technology. available from: www-2.cs.cmu.edu/~ph.Google Scholar
15. Herbison-Evans, D. 1995. Solving quartics and cubics for graphics. In Graphics Gems V., AP Professional, Chestnut Hill MA.Google Scholar
16. Hoschek, J., and Lasser, D. 1989. Fundamentals of Computer Aided Geometric Design. A K Peters. English translation by L Schumaker, 1993. Google ScholarDigital Library
17. Loop, C., and Blinn, J. 2005. Resolution independent curve rendering using programmable graphics hardware. ACM Transactions on Graphics 24, 3, 1000–1009. Siggraph Conference Proceedings. Google ScholarDigital Library
18. Mahl, R. 1972. Visible surface algorithms for quadric patches. IEEE Trans. Computers (Jan.), 1–4.Google ScholarDigital Library
19. Microsoft Corp. 2006. Direct3d 9 reference. In In Direct3D 9 graphics. http://msdn.microsoft.com/directx.Google Scholar
20. Ramshaw, L. 1989. Blossoms are polar forms. Computer Aided Geometric Design 6, 4 (November), 323–358. Google ScholarDigital Library
21. Sederberg, T. W., and Zundel, A. K. 1989. Scan line display of algebraic surfaces. Siggraph 1998 Conference Proceeding 23, 3. Google ScholarDigital Library
22. Sederberg, T. 1985. Piecewise algebraic surface patches. Computer Aided Geometric Design 2, 1–3, 53–60.Google ScholarDigital Library
23. Shirley, P., and Tuchman, A. A. 1990. Polygonal approximation to direct scalar volume rendering. In Proceedings San Diego Workshop on Volume Visualization, Computer Graphics, vol. 24, 63–70. Google ScholarDigital Library