Real-time programmable graphics hardware has resource constraints that
prevent complex shaders from rendering in a single pass.  One way to
virtualize these resources is to partition shading computations into
multiple passes, each of which satisfies the given constraints.  Many
such partitions exist for a shader, but it is important to find one
that renders efficiently.  We present Recursive Dominator Split (RDS),
a polynomial-time algorithm that uses a cost model to find
near-optimal partitions of arbitrarily complex shaders.  Using a
simulator, we analyze partitions for architectures with different
resource constraints and show that RDS performs well on different
graphics architectures.  We also demonstrate that shader partitions
computed by RDS can run efficiently on programmable graphics hardware
available today.