“Shader algebra” by McCool, Du Toit, Popa, Chan and Moule

  • ©Michael McCool, Stefanus Du Toit, Tiberiu Popa, Bryan Chan, and Kevin Moule




    Shader algebra



    An algebra consists of a set of objects and a set of operators that act on those objects. We treat shader programs as first-class objects and define two operators: connection and combination. Connection is functional composition: the outputs of one shader are fed into the inputs of another. Combination concatenates the input channels, output channels, and computations of two shaders. Similar operators can be used to manipulate streams and apply computational kernels expressed as shaders to streams. Connecting a shader program to a stream applies that program to all elements of the stream; combining streams concatenates the record definitions of those streams.In conjunction with an optimizing compiler, these operators can manipulate shader programs in many useful ways, including specialization, without modifying the original source code. We demonstrate these operators in Sh, a metaprogramming shading language embedded in C++.


    1. ABRAM, G. D., AND WHITTED, T. 1990. Building block shaders. Computer Graphics (Proc. SIGGRAPH) 24, 4 (Aug.), 283–288.]] Google ScholarDigital Library
    2. APODACA, A. A., AND GRITZ, L. 2000. Advanced Render-Man: Creating CGI for Motion Pictures. Morgan Kaufmann.]] Google ScholarDigital Library
    3. BLINN, J. F. 1977. Models of light reflection for computer synthesized pictures. Computer Graphics (Proc. SIGGRAPH) (July), 192–198.]] Google ScholarDigital Library
    4. BOLZ, J., FARMER, I., GRINSPUN, E., ANDSCHRÖDER, P. 2003. Sparse matrix solvers on the GPU: Conjugate gradients and multigrid. ACM Trans. on Graphics (Proc. SIGGRAPH) 22, 3 (July), 917–924.]] Google ScholarDigital Library
    5. BUCK, I., FOLEY, T., HORN, D., SUGERMAN, J., FATAHALIAN, K., HOUSTON, M., AND HANRAHAN, P. 2004. Brook for GPUs: Stream computing on graphics hardware. ACM Trans. on Graphics (Proc. SIGGRAPH) 23, 3 (August).]] Google ScholarDigital Library
    6. BUCK, I. 2003. BrookGPU web site. http://graphics.stanford.edu/projects/brookgpu/.]]Google Scholar
    7. COOK, R. L. 1984. Shade trees. Computer Graphics (Proc. SIGGRAPH) 18, 3 (July), 223–231.]] Google ScholarDigital Library
    8. DAWES, B., AND ABRAHAMS, D. 2003. Boost++ web site. http://www.boost.org.]]Google Scholar
    9. DRAVES, S. 1996. Compiler generation for interactive graphics using intermediate code. In Dagstuhl Seminar on Partial Evaluation, 95–114.]] Google ScholarDigital Library
    10. ELLIOTT, C., FINNE, S., AND DE MOOR, O. 2000. Compiling embedded languages. In SAIG/PLI, 9–27.]] Google ScholarDigital Library
    11. GUENTER, B., KNOBLOCK, T., AND RUF, E., 1995. Specializing shaders. In Proc. SIGGRAPH, 343–350.]] Google ScholarDigital Library
    12. HANRAHAN, P., AND LAWSON, J. 1990. A language for shading and lighting calculations. In Computer Graphics (SIGGRAPH ’90 Proceedings), 289–298.]] Google ScholarDigital Library
    13. HART, J. C., CARR, N., KAMEYA, M., TIBBITTS, S. A., AND COLEMAN, T. J. 1999. Antialiased parameterized solid texturing simplified for consumer-level hardware implementation. In Proc. SIGGRAPH/Eurographics Workshop on Graphics Hardware, ACM Press, 45–53.]] Google ScholarDigital Library
    14. HEDELMAN, H. 1984. A data flow approach to procedural modeling. IEEE CG&A 3, 1 (January), 16–26.]]Google Scholar
    15. HERRINGTON, J. 2003. Code Generation in Action. Manning Publications.]] Google ScholarDigital Library
    16. HILLESLAND, K. E., MOLINOV, S., AND GREZESZCZUK, R. 2003. Nonlinear optimization framework for image-based modeling on programmable graphics hardware. ACM Trans. on Graphics (Proc. SIGGRAPH) 22, 3 (July), 925–934.]] Google ScholarDigital Library
    17. KASS, M. 1992. CONDOR: Constraint-based dataflow. In Proc. SIGGRAPH, 321–330.]] Google ScholarDigital Library
    18. KESSENICH, J., BALDWIN, D., AND ROST, R. 2003. OpenGL 2.0 Shading Language, 1.051 ed., Feb.]]Google Scholar
    19. KRÜGER, J., ANDWESTERMANN, R. 2003. Linear algebra operators for GPU implementation of numerical algorithms. ACM Trans. on Graphics (Proc. SIGGRAPH) 22, 3 (July), 908–916.]] Google ScholarDigital Library
    20. LEE, P., AND LEONE, M. 1996. Optimizing ML with run-time code generation. In SIGPLAN Conference on Programming Language Design and Implementation, 137–148.]] Google ScholarDigital Library
    21. MARK, W. R., AND PROUDFOOT, K. 2001. Compiling to a VLIW fragment pipeline. In Proc. Graphics Hardware, SIGGRAPH/Eurographics.]] Google ScholarDigital Library
    22. MARK, W. R., GLANVILLE, R. S., AKELEY, K., AND KILGARD, M. J. 2003. Cg: A System for programming graphics hardware in a C-like language. ACM Trans. on Graphics (Proc. SIGGRAPH) 22, 3 (July), 896–907.]] Google ScholarDigital Library
    23. MCCOOL, M. D., QIN, Z., AND POPA, T. S. 2002. Shader metaprogramming. In Proc. Graphics Hardware, 57–68.]] Google ScholarDigital Library
    24. OWENS, J. D., DALLY, W. J., KAPASI, U. J., RIXNER, S., MATTSON, P., AND MOWERY, B. 2000. Polygon rendering on a stream architecture. In Proc. Eurographics/SIGGRAPH Workshop on Graphics Hardware, 23–32.]] Google ScholarDigital Library
    25. PEACHEY, D. 1985. Solid texturing of complex surfaces. Computer Graphics (Proc. SIGGRAPH) 19, 3 (July), 279–286.]] Google ScholarDigital Library
    26. PEERCY, M. S., OLANO, M., AIREY, J., AND UNGAR, P. J. 2000. Interactive multi-pass programmable shading. In Proc. SIGGRAPH, 425–432.]] Google ScholarDigital Library
    27. PERLIN, K. 1985. An image synthesizer. Computer Graphics (Proc. SIGGRAPH) 19, 3 (July), 287–296.]] Google ScholarDigital Library
    28. PIXAR. 2000. The RenderMan Interface, version 3.2, July.]]Google Scholar
    29. POLETTO, M., HSIEH, W. C., ENGLER, D. R., AND KAASHOEK, M. F. 1999. ‘C and tcc: a language and compiler for dynamic code generation. ACM Trans. on Programming Languages and Systems 21, 2, 324–369.]] Google ScholarDigital Library
    30. PROUDFOOT, K., MARK, W. R., HANRAHAN, P., AND TZVETKIOV, S. 2001. A real-time procedural shading system for programmable graphics hardware. Computer Graphics (Proc. SIGGRAPH) (Aug.), 159–170.]] Google ScholarDigital Library
    31. ROST, R. J. 2004. OpenGL Shading Language. Addison-Wesley.]] Google ScholarDigital Library
    32. SIMS, K. 1990. Particle animation and rendering using data parallel computation. Computer Graphics (Proc. SIGGRAPH) 24, 4 (August), 405–413.]] Google ScholarDigital Library
    33. SLUSALLEK, P., STAMMINGER, M., HEIDRICH, W., POPP, J.-C., AND SEIDEL, H.-P. 1998. Composite lighting simulations with lighting networks. IEEE CG&A 18, 2 (Mar.), 22–31.]] Google ScholarDigital Library
    34. SNYDER, J. M., AND KAJIYA, J. T. 1992. Generative modeling: A symbolic system for geometric modeling. Computer Graphics (Proc. SIGGRAPH) 26, 2 (July), 369–378.]] Google ScholarDigital Library
    35. SNYDER, J. M. 1992. Interval analysis for computer graphics. Computer Graphics (Proc. SIGGRAPH) 26, 2 (July), 121–130.]] Google ScholarDigital Library
    36. TRENDALL, C., AND STEWART, A. J. 2000. General calculations using graphics hardware, with applications to interactive caustics. In Rendering Techniques ’00 (Proc. Eurographics Workshop on Rendering), Springer, 287–298.]] Google ScholarDigital Library
    37. UPSTILL, S. 1990. The RenderMan Companion: A Programmer’s Guide to Realistic Computer Graphics. Addison-Wesley.]] Google ScholarDigital Library
    38. VELDHUIZEN, T. L. 1999. C++ templates as partial evaluation. In ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation.]]Google Scholar

ACM Digital Library Publication: