Real-time graphics hardware continues to offer improved resources for programmable vertex and fragment shaders. However, shader programmers continue to write shaders that require more resources than are available in the hardware. One way to virtualize the resources necessary to run complex shaders is to partition the shaders into multiple rendering passes. This problem, called the ``Multi-Pass Partitioning Problem'' (MPP), and a solution for the problem, Recursive Dominator Split (RDS), have been presented by Eric Chan et al. The O(n^3) RDS algorithm and its heuristic-based O(n^2) cousin, RDSh, are robust in that they can efficiently partition shaders for many architectures with varying resources. However, RDS's high runtime cost and inability to handle multiple outputs per pass make it less desirable for real-time use on today's latest graphics hardware. This paper redefines the MPP as a scheduling problem and uses scheduling algorithms that allow incremental resource estimation and pass computation in O(n log n) time. Our scheduling algorithm, Mio, is experimentally compared to RDS and shown to have better run-time scaling and produce comparable partitions for emerging hardware architectures.

In computer cinematography, the process of lighting design involves placing and configuring lights to define the visual appearance of environments and to enhance story elements. This process is labor intensive and time consuming, primarily because lighting artists receive poor feedback from existing tools: interactive previews have very poor quality, while final-quality images often take hours to render. This paper presents an interactive cinematic lighting system used in the production of computer-animated feature films containing environments of very high complexity, in which surface and light appearances are described using procedural RenderMan shaders. Our system provides lighting artists with high-quality previews at interactive framerates with only small approximations compared to the final rendered images. This is accomplished by combining numerical estimation of surface response, image-space caching, deferred shading, and the computational power of modern graphics hardware. Our system has been successfully used in the production of two feature-length animated films, dramatically accelerating lighting tasks. In our experience interactivity fundamentally changes an artist's workflow, improving both productivity and artistic expressiveness.