按年被提到
20222022 · 4 次2026
算法与数据结构›经典算法与数据结构·arXiv:2205.11659 · cs.GR

Fast GPU bounding boxes on tree-structured scenes

树状场景上的快速 GPU 包围盒计算
Raph Levien · 2022

用括号匹配新算法在 GPU 上并行计算树状场景的包围盒

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 4 人首次 2022-06-04 · 最近 2026-06-25
4不同的人
8活跃月份
8讨论串
0被引(OpenAlex)

针对 2D 渲染中树状场景描述里剪裁节点与混合节点分别要求包围盒求交与求并的问题,提出快速而实用的 GPU 并行算法,核心是经典括号匹配问题的一个新算法。算法先在 PRAM 抽象下给出,再映射到线程、工作组和调度三个层次,用 compute shader 可移植地实现;性能结果显示相对串行 CPU 版本有大幅加速,并达到 GPU 理论吞吐的相当一部分。

HN 为什么提它

在讨论如何在 GPU 上处理树、解析器和渲染时,评论者(包括作者本人)反复提起 Raph Levien 的 stack monoid 工作,认为可以作为相关设计的基础。

方法难度 4 / 5约 50 分钟经得起时间
读之前最好知道
1GPU 并行计算与 compute shader
2并行算法(PRAM 模型)
3括号匹配与幺半群(monoid)
42D 渲染管线(剪裁与混合)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐singhrac · 2022-06

“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.”

推荐 Raph Levien 的 stack monoid 工作及这篇 arXiv 论文
Vectorized and performance-portable Quicksort原评论 ↗
推荐raphlinus · 2026-06

“Earlier versions of the work were featured on HN [3][4], but this is much more sophisticated.”

指出早期版本曾上过 HN,这篇要复杂得多
Parallel Parentheses Matching原评论 ↗
引用YorkshireSeason · 2022-08

“PS, is your monoid work online, is it this Fast GPU bounding boxes on tree-structured scenes ?”

询问对方的 monoid 工作是否就是这篇论文
The culture of rejection in computer science publications原评论 ↗
引用raphlinus · 2022-08

“Yes, that's the draft on arXiv”

确认这就是 arXiv 上的那份草稿
The culture of rejection in computer science publications原评论 ↗
引用raphlinus · 2022-12

“If you did want to manipulate trees on the GPU, then my stack monoid work[1] might be a good basis for it.”

建议在 GPU 上处理树时,可以以自己的 stack monoid 工作为基础
Introduction to Homotopy Type Theory原评论 ↗
引用raphlinus · 2023-05

“those have been ported to compute shaders[2] (disclosure: blatant self-promotion).”

说明这些思路已移植到 compute shader,并坦言是自我宣传
PyTorch Primitives in WebGPU for the Browser原评论 ↗
看全部 9 条 →
引用raphlinus · 2023-09

“One is a draft paper (not yet polished for publication), on arXiv[1].”

指出其一是 arXiv 上尚未打磨的草稿论文
The Stack Monoid Revisited原评论 ↗
引用raphlinus · 2024-06

“My stack monoid work [1] contains a bunch of ideas that may be helpful for building one.”

指出自己的 stack monoid 工作里的想法可能有助于构建 GPU JSON 解析器
SIMD < SIMT < SMT: Parallelism in Nvidia GPUs (2011)原评论 ↗
引用raphlinus · 2024-06

“There's a bit more information at [1], but I think the details are not public.”

补充说明有更多信息,但细节似乎并未公开
SIMD < SIMT < SMT: Parallelism in Nvidia GPUs (2011)原评论 ↗
被提交为 story · 1 次