HackerPapers

arXiv:2205.11659cs.GR

Fast GPU bounding boxes on tree-structured scenes

Raph Levien

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.GRGraphics

On Hacker News

Linked by 3 identifiable commenters in 9 comments across 7 threads, from Jun 2022 to Jun 2026. Found in 1 HN submission from Nov 2025 to Nov 2025. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments7 threads

  1. Parallel Parentheses Matching 1 comment

    • Also see Fast GPU bounding boxes on tree-structured scenes[1] (unpublished paper) and notes toward a blog post[2]. This is a highly tuned GPU implementation of parentheses matching. It's actually used in Vello (the classic version in which we offload basically all the work to…

      raphlinusView on HNParent context

  2. SIMD < SIMT < SMT: Parallelism in Nvidia GPUs (2011) 2 comments

    • I'm not aware of any similarly mature GPU-based JSON parser, but I believe such a thing is possible. My stack monoid work [1] contains a bunch of ideas that may be helpful for building one. I've thought about pursuing that, but have kept focus on 2D graphics as it's clearer how…

      raphlinusView on HNParent context

    • There's a bit more information at [1], but I think the details are not public. The hardware is tracking a separate program counter (and call stack) for each thread. So in the CAS example, one thread wins and continues making progress, while the other threads loop. There seems to…

      raphlinusView on HNParent context

  3. The stack monoid revisited 1 comment

    • Not sure why this is popping up now, but people should know there's been quite a bit of followup work. One is a draft paper (not yet polished for publication), on arXiv[1]. I have an issue on my blog[2], and one of these days I intend to get back to it. It's also in use in Vello…

      raphlinusView on HNParent context

  4. PyTorch for WebGPU 1 comment

    • It is possible but you have to do things very differently, for example use monoids. There are a few compilers implemented on GPU, including Aaron Hsu's co-dfns and Voetter's compiler project[1]. The parentheses matching problem itself (the core of parsing) has long known…

      raphlinusView on HNParent context

  5. Introduction to Homotopy Type Theory 1 comment

    • Do not nerd snipe me! There's tons of juice left on the CPU side. Again I recommend Metamath Zero (which is somewhat of an opposite direction as HoTT), as it's able to check the entire Metamath proof database in a few hundred milliseconds. This is orders of magnitude faster than…

      raphlinusView on HNParent context

  6. The culture of rejection in computer science publications 2 comments

    • I found myself in a somewhat similar situation. I learned to thing long-term: (1) Publish initial ideas not in top conferences, but in second rate venues. Most publications in top conferences are, clearly, refinements of ideas that were first presented in inchoate form, in less…

      YorkshireSeasonView on HNParent context

    • > PS, is your monoid work online, is it this https://arxiv.org/abs/2205.11659 ? I'm interested in monoids on GPUs. Yes, that's the draft on arXiv, and I have a blog post in the pipeline[1] explaining it to a more general audience. And thanks for the other advice, I'll consider…

      raphlinusView on HNParent context

  7. Vectorized and performance-portable Quicksort 1 comment

    • Another one if you enjoy this sort of thing like me is Raph Levien's work on the stack monoid; this [1] blog post and this [2] ArXiV paper are great places to look. [1]: https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html [2]: https://arxiv.org/abs/2205.11659

      singhracView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.