  Computation of bounding boxes is a fundamental problem in high performance
rendering, as it is an input to visibility culling and binning operations. In a
scene description structured as a tree, clip nodes and blend nodes entail
intersection and union of bounding boxes, respectively. These are
straightforward to compute on the CPU using a sequential algorithm, but an
efficient, parallel GPU algorithm is more elusive. This paper presents a fast
and practical solution, with a new algorithm for the classic parentheses
matching problem at its core. The core algorithm is presented abstractly (in
terms of a PRAM abstraction), then with a concrete mapping to the thread,
workgroup, and dispatch levels of real GPU hardware. The algorithm is
implemented portably using compute shaders, and performance results show a
dramatic speedup over a sequential CPU version, and indeed a reasonable
fraction of maximum theoretical throughput of the GPU hardware. The immediate
motivating application is 2D rendering, but the algorithms generalize to other
domains, and the core parentheses matching problem has other applications
including parsing.
