"This presentation is a follow-up of our HPG paper that we presented just a couple of days ago. The paper is called “Concurrent Binary Trees for Large-Scale Game Components”..."
- CBT 是一个能同时回答「还剩多少」和「第 k 个是谁」的结构：一棵满二叉树（除了叶子，每个节点恰好有两个孩子）＝ 树最底层一个位域（叶子只存二值）＋ 对位域的一棵求和归约树（其余节点存对应子树里绿位的个数，讲义 slide 32–35）。由此，根给出绿位总数，也能遍历并不连续的绿位。
- 它能当内存池，因为容量就等于位域的容量：绿位记已分配、红位记可用，于是根就给出还剩多少（slide 36）；分配＝置一并更新归约树，回收＝置零再更新（slide 38–39）。讲者把这一层收成一句可搬走的话 —— CBT 提供的是「分配、释放、并遍历内存池里所有元素」的办法（slide 51）。
- 一条硬约束逼出整套表示：128k 的 CBT 节点数是位域大小的两倍（
2 × (128 × 1024) = 262144），朴素约 1 MB，而 DX12 组共享内存上限是 32 KB（slide 54–55）；于是树被按访问约束拆成原子友好子树、线程子树、虚拟层级、原始位域四类，本体落到约 3 KB（slide 56–67）。 - 网格侧把「任意多边形网格」翻译成「一堆可分配的槽位」：输入半边界网格，输出每条半边界一个三角形（slide 41–42）；翻译的代价是必须自带邻接 —— 朴素二分会出 T 形接缝，最终表面上出现裂缝（slide 45–50）。
- 一帧跑十二段管线，多数是间接派发（slide 89–93）：Classify 把每条平分线判成 Keep、Merge 或 Split（slide 96–101）；Split 先算这次分裂最坏情况要预留多少内存，拿不到就不做，否则会破坏 LEB 机制（slide 102–109）。
- 最实在的优化在 Evaluate LEB：最终位置由 heapID 位串经一串矩阵乘法给出，每一位对应两个矩阵之一（slide 139）。乘法必须在 double 空间做，最多 64 次 3×3；先拆成两段各 32 次 float 夹一次 double（仍然不够好），再用深度 5 的矩阵缓存降到两组各 6 次 float 加一次 double（slide 140–143）。
- 性能口径先钉死，而整套东西是开源的：1920×1080、CBT 128K，三张卡（Arc 770、AMD 6650 XT「大致相当于 PS5」、Nvidia 4090）；讲者点名的结论是始终在合理成本内、在相当于 PS5 的硬件上低于 0.2 毫秒（slide 151–154）。demo 完整代码开源于 slide 158 给出的地址。
1这类组件有多大：从地形、海洋到整颗行星
这类组件有多大：从地形、海洋到整颗行星
这一篇讲的是把一棵并发二叉树（concurrent binary tree / CBT）当成 GPU 上可分配的内存池、用它驱动任意多边形网格自适应二分三角化的整套做法。开场先把来路交代清楚。按讲义 slide 1 的讲稿，这一场是几天前一场 HPG 论文报告的后续场次，论文题为《Concurrent Binary Trees for Large-Scale Game Components》，论文里的主要内容这一场都会讲到（讲义 slide 1、2）。其中有一批实现细节在讲义里被标成红色，讲者把这批单独提出来，理由是论文写成至今的半年里，Anis 把实现重做了一遍、让它更快，于是论文里描述的东西如今多少已经过时（讲义 slide 3、4）。这一场给的是这份新实现的细节，前半先由一位把论文 recap 一遍，实现细节留给 Anis（讲义 slide 5、31）。
对象是什么，讲义先给一句界定：一个大规模游戏组件（large-scale game component）通常就是让你的游戏世界看起来「大」的那个东西（讲义 slide 7）。这句界定出自同页讲稿，该页的文字层是空的。
界定的下一段是例子，讲义用三款作品把这件事落到具体物件上（讲义 slide 8、9、10）。Red Dead Redemption 2（Rockstar）对应地形，Assassin's Creed Origins（Ubisoft）对应海洋，Star Citizen（Cloud Imperium Games）对应整颗行星。三页是逐页累加的，地形先单独出现，海洋在第二页并排进来，行星到第三页才补齐，页末把它归成一个词 planets。
讲者在这组画面下面把范围说全：这些截图里除了前景的角色，几乎所有东西都是用一个专门系统渲染的，这个专门系统就是他们说的「大规模游戏组件」（讲义 slide 10 讲稿）。这句说明解释了上面三件看上去相隔很远的物件为什么能放在一起讲，它们的共同点是都被同一个独立系统接管。
为什么要给这一类单独做一套算法，讲稿把理由落在像素上：这类组件往往占了大量像素，所以需要一整套高效算法尽快把它们画出来，论文的目标就是给这套算法添一块（讲义 slide 11）。页内把这层意思压成一句短语 one component, lots of pixels。
规模感在演示里给了一次具体读数（讲义 slide 17）。讲者在这一页放了一段视频，记录他们方法的结果；按同页讲稿，在他们的方法下、全高清分辨率、PS5 级别的硬件上跑到 250+ FPS。这一页页内只有一个项目符号，读数由讲稿给出，口径是全高清与 PS5 级别的硬件，他没有宣称它在别的分辨率或别的硬件档位上也成立。
本章可核对的结论有三条。这一场是 HPG 那篇论文的后续场次，论文里那 4 页实现细节在讲义里标红，讲者明说它们如今多少已经过时，这一场讲的是重做过的新实现（讲义 slide 1、3、4、5）。一个大规模游戏组件通常就是让游戏世界看起来「大」的那个东西，三件例子是 Red Dead Redemption 2 的地形、Assassin's Creed Origins 的海洋与 Star Citizen 的整颗行星，这些画面里除前景角色外几乎都由一个专门系统渲染（讲义 slide 7、8、9、10）。给它单独做算法的理由是它占大量像素，页内短句为 one component, lots of pixels，演示读数是全高清、PS5 级别硬件上的 250+ FPS（讲义 slide 11、17）。下一章看这一族问题怎么被分成两个子问题。
2两个子问题，以及这一篇只做哪一个
上一章把对象与理由摆完，这一章看这一族问题内部怎么分（讲义 slide 12）。页内把这一族问题标成 2 sub-problems，讲稿说它们通常可以分作两类（讲义 slide 12）。页内这一行只占版面顶端，下面才是那串参考出处与本篇的贡献行（讲义 slide 12）。
第一类是数据生成（data generation），处理的是纹理、精灵、实例等等怎么生成（讲义 slide 13 讲稿）。
第二类是三角化与渲染（triangulation / rendering），处理的是这些数据怎么画出来（讲义 slide 14 讲稿）。页内在第二类旁边记的名字是 rendering，讲稿把它展开成 triangulation 与 rendering 这一支。两类旁边并排列着一串参考出处（讲义 slide 13、14）：《Rendering Water in Horizon Forbidden West》（SG'22）、《Large Scale terrain rendering in Call of Duty》（SG'23）、《Simulating Tropical Weather in Farcry 6》（GDC'22），以及《Concurrent Binary Trees for Large-scale Terrain Rendering》（SG'21）。这些是讲义页内给出的参考出处，本篇照抄作品名与场次，不引它们的正文内容，也不替它们下评判；其中《Concurrent Binary Trees for Large-scale Terrain Rendering》（SG'21）那一栏与本篇的关系下一段就会说到。
这四栏是逐页累加出来的，前一页并排的只有水面与地形两场（讲义 slide 13），后一页才添上天气与这套树方法两栏（讲义 slide 14）。页内把它们摆在两类子问题的旁边，用途是交代这一族的来路，正文只照抄页内给出的作品名与场次。
这两类的分法是讲义给出的一个归纳，页内在同一版上把它们与几处参考出处摆在一起（讲义 slide 12、13、14）。本篇落脚的这一类在页内排在第二位，编号是 2。页内把两类的说明写得很短，一类只占一行，展开成完整的话由讲稿补出（讲义 slide 13、14）。两类的编号在页内固定下来，本篇的贡献行挂在编号 2 下面（讲义 slide 14、16）。
本篇的范围在下一页被写死（讲义 slide 15）。页内在 rendering 那一支下面添了 our contribution 一行，讲稿把话说得很直：论文只给后者做贡献，所以这一场不谈数据生成；给出来的东西是一个能在任意尺度上探索超大环境的三角化方法。这条边界要记牢，本篇只做三角化与渲染那一侧，数据生成明确不在范围内。讲者在同一页把这项工作的能力也交代了，它要处理的是非常大的环境，而且这些环境要能在任意不同的尺度上被探索（讲义 slide 15）。
而且这一套是对已有工作的改进（讲义 slide 16）。讲稿说它是对「Concurrent Binary Trees」（CBTs）的改进，那套是他们三年前在同一门课上讲过的；讲者喜欢把这个改进叫「CBT version 2」，或者简称 CBT-V2。页内在 our contribution 后面直接标了 CBT-V2。命名的用法这里要留意：本场题目用的是 CBTS，讲者口头上用 CBT-V2，两处都按讲义照写，不替他把名字统一起来。讲者在同一页还说，CBT 到底是什么他马上会讲，这句话把读者送到第 4 章。
本章可核对的结论有三条。这一族问题被分成两类，数据生成管纹理、精灵、实例等等怎么生成，三角化与渲染管这些数据怎么画出来（讲义 slide 12、13、14）。页内并列的参考出处是 Rendering Water in Horizon Forbidden West（SG'22）、Large Scale terrain rendering in Call of Duty（SG'23）、Simulating Tropical Weather in Farcry 6（GDC'22）与 Concurrent Binary Trees for Large-scale Terrain Rendering（SG'21）。本篇只给三角化与渲染那一支做贡献，数据生成不在这一场的范围里（讲义 slide 15）；它同时是三年前同一门课上那套 CBT 的改进，讲者叫它 CBT version 2 或 CBT-V2（讲义 slide 16）。下一章看动机里那个装不进硬盘的数字，以及它堵死了哪两条现成的路。
3全分辨率要 exabytes，而现成的 LOD 用不上
上一章把范围收在三角化与渲染这一支，这一章交代为什么现成的细节层级（level-of-detail / LOD）顶不住这件事（讲义 slide 28）。讲义先给一个数量级判断：他们那颗地球模型的全分辨率网格，也就是不做任何 LOD 的网格，需要 exabytes 的数据；页内在括注里写明 1 exabyte = 1,000,000 terabytes。讲者把这句判断补完，这样连一块大 SSD 都放不下。这里说的全分辨率，指的是完全不引入 LOD 的那一份网格。这句判断在紧接着的几页里一直留在版面上，讲到哪一条路都把它带在头上（讲义 slide 29、30）。两条被否掉的路面对的是同一个数量级，页内没有给出别的口径来解释它们为什么用不上。
第一条被堵死的路跟在下一页（讲义 slide 29）。这个量级直接挡住了 Nanite 那类 LOD 系统，按讲稿的说法，它们要求把全分辨率网格作为输入。页内把这类做法标成 Geometry Clusters + DAG，并引了 SG'21 的《A Deep Dive into Nanite Virtualized》作来路，DAG 这个缩写页内没有展开。输入本身就是一个放不进硬盘的量，这一类做法在这套场景里就用不上，页内把这层结论收在一句 … so we can't use this 里。这里只按讲义页内与讲稿的原话说这一类做法对输入的要求，不与它做优劣比较。这两条路在页内各留了一处来路，两处都只用来指认这类做法的出处，正文不给它们添别的话（讲义 slide 29、30）。
第二条路在再下一页（讲义 slide 30）。讲义补了一句：在 UE5.3 里其实还有一条路，用它自己的大规模游戏组件，做法是把两套表示耦合起来，一套管近处、一套管远处。页内把这行标成 alternative in UE 5.3，并引了 Unreal Engine 5.3 Water Documentation。讲者的让步这里要照写：混合表示很难用，尤其是自由飞行的相机，因为两套表示之间那个过渡位置很难定。讲者在这两页的措辞是留有余地的，他先说这一类 LOD 系统用不上、UE5.3 里还有一条替代路线，随后才指出替代路线自己的难处（讲义 slide 29、30）。
这三页在版面上是层层叠下来的，数量级那句判断放在最上面一层，下面依次挂着第一类做法的说明与 UE5.3 的替代路线（讲义 slide 28、29、30）。读的时候从最上面那层往下看，两条路都属于对同一句话的不同反应。
他们方法的优点在页末一句带过（讲义 slide 30）。按讲稿，他们这套只依赖一套表示，所以不必操心过渡位置这件事。这一句是本章的落点：绕开过渡问题的办法，是把表示收成一份。页内把这条优点写在一句话里，没有再给对照数据或额外论证（讲义 slide 30）。
本章可核对的结论有三条。他们那颗地球模型的全分辨率网格需要 exabytes 的数据，页内注明 1 exabyte = 1,000,000 terabytes，讲者补一句这样连一块大 SSD 都放不下（讲义 slide 28）。这个量级直接挡住了 Nanite 那类 LOD 系统，因为讲稿说它们要求把全分辨率网格作为输入，页内把这类做法标成 Geometry Clusters + DAG 并引 SG'21 的《A Deep Dive into Nanite Virtualized》（讲义 slide 29）。在 UE5.3 里另有一条路，用它自己的大规模游戏组件把近处与远处两套表示耦合起来，页内标成 alternative in UE 5.3；讲者指出混合表示很难用、尤其自由飞行的相机，因为两套表示之间的过渡位置很难定，而他们这套只依赖一套表示（讲义 slide 30）。本章的三页只给判断与两条路，没有给任何耗时或占用数字（讲义 slide 28、29、30）。下一章看他们自己那棵树长什么样。
4CBT 是什么：位域加一棵求和归约树
上一章说明现成的两条路都走不通，这一章回到他们自己那件东西（讲义 slide 31、32）。讲者在进入定义前先把后面的分工交代了：他先快速解释什么是并发二叉树、以及他们的方法怎么和它配合，实现细节接下来交给 Anis（讲义 slide 31）。定义一句话给足：一个并发二叉树（concurrent binary tree / CBT）是一棵满二叉树（full binary tree），也就是除了叶子、每个节点恰好有两个孩子；这棵树由两大部分组成（讲义 slide 32 讲稿）。这棵树是定形的，父子关系固定下来，层与层的边界也就跟着定了，后面凡说到某一层、某棵子树，指的都是这张固定形状上的位置（讲义 slide 32）。
第一部分是树最底层的一个位域（bitfield）（讲义 slide 33）。叶子节点只存二值，最低这一排位置每一位只取零与一两种取值。这一部分占的是树的最底一层，位数就是最底层节点的个数，底部这一层只回答开与关两件事。这一页页内只给了 bitfield 一个词，其余细节由讲稿补出。
第二部分是对这个位域做的一棵求和归约树（sum-reduction tree）（讲义 slide 34）。其余每个节点存它对应子树里绿位（green bits）的个数，绿位就是置为一的那些位。这一层的读法是自下而上累加的，每个内部节点只回答一个问题，它下面那片叶子里有多少位被置成一。这一部分覆盖的是树里除叶子之外的所有节点，每个节点只保存它下面那一小片子树的一份计数，越往上覆盖的范围越大。页内这一页把 bitfield 与 sum-reduction tree 两个词上下并排摆在同一版面上。
定义这一段的页内文字都很薄，树的形状那页文字层是空的，最底层那页只有一个词，求和归约树那页两个词上下并排（讲义 slide 32、33、34）。这些页的读法因此要靠讲稿，页内给出的只是每一部分的名称，转入这一段的那页页内也没有文字（讲义 slide 31）。
两条由此而来的能力在同一页的讲稿里说全（讲义 slide 35）。其一，根节点给出绿位的总数，取一次根就等于知道整棵树里被置成一的位置共有多少。其二，求和归约树让这件事成为可能，可以遍历绿位，哪怕这些绿位在位域里并不连续。第二点是这棵树后面所有用途的关键，遍历要能在稀疏的置位里找出下一个位置，而这件事靠的就是每个节点存的那份计数。这两条能力在定义的最后一页给出，后面几章把它们接到具体的用途上（讲义 slide 35）。根上的那份总数是一次读就能拿到的量，遍历则是顺着计数一层层往下走的量，两者合起来，一棵只存零与一的树就能当一份可以逐项点名的名单。
位域那一层排在树的最下面，求和归约树从它上面一层层长起来，两部分合起来才是完整的一棵树（讲义 slide 33、34）。页内在这几页没有给数值示例，树的规模与层数留到实现那一段再谈（讲义 slide 32、33、34、35）。
本章可核对的结论有三条。一棵 CBT 是一棵满二叉树，除叶子外每个节点恰好有两个孩子，它由两大部分组成（讲义 slide 32）。第一部分是树最底层的位域，叶子节点只存二值；第二部分是对这个位域做的求和归约树，其余每个节点存它对应子树里绿位的个数，绿位是置为一的位（讲义 slide 33、34）。由此得到两条能力，根节点给出绿位的总数，求和归约树让人可以遍历绿位，哪怕这些绿位在位域里并不连续（讲义 slide 35）。这两条能力是下一章把它当内存池用的前提。
5能当内存池用，是因为它有这三条性质
上一章落在两条能力上，根节点给出绿位的总数，求和归约树让人可以遍历绿位，哪怕这些绿位在位域里并不连续。这一章看这两条能力怎么被接到用途上（讲义 slide 36）。
讲义在这一页先把结论说了：上面那些性质让 CBT 可以当一个内存池管理器用，追踪已分配与可用的内存。讲者随后把内存池（memory pool）本身说清，内存池就是一个存你想存的任何数据的数组，他们把它的容量设成位域的容量。已分配的条目用绿位追踪，可用的内存用红位追踪，于是 CBT 的根就给出还有多少内存可用、多少已分配。页内把这两问写成两个函数签名，uint32_t available_memory(); 与 uint32_t allocated_memory();。同一页把位域、求和归约树与内存池三层并排画在一起，池那一列里既有真实的数值，也有若干空出来的 null 槽位。
这三条性质可以按提问的方式摆开。第一问是池里还剩多少，答在根上，读一次根节点就有结果，因为求和归约树的根存着整棵子树里绿位的个数，而池的容量等于位域容量，绿位全部落在这个位域里。第二问是下一个空位在哪，答在一趟遍历里，沿求和归约树往下走就能定位，绿位在位域里连不连续都不妨碍这件事。第三问是谁被占了，同样是这趟遍历给出的名册，把绿位逐个列出来，得到的就是已分配项的清单。三问共用一份数据，池的容量、剩余量与已分配项的分布都从同一棵树读出，不必再另维护一份索引。
池那一列里数值与 null 交错排列，可用位置并不都连在一起，遍历绿位因此是必需的。讲义 slide 40 讲者用一句话把话题从结构转向三角化，说接下来要讲的是他们为三角化做的事。池的容量等于位域容量，所以这一档的池也是 128k 宽，池里装的就是后面几章要讲的那批三角形数据。
分配与回收（allocation 与 de-allocation）各是一句就能说完的操作（讲义 slide 37 至 39）。分配是把某一位置一，并更新求和归约树。回收是把某一位置零，再更新求和归约树。讲义 slide 37 把四个函数名并排给出，除前面两个查询函数之外还有 uint32_t atomic_allocation(); 与 uint32_t atomic_deallocation();，名字里的 atomic 指向多个线程同时改写同一棵树这件事；原子冲突在这两页里没有展开，讲义只说这两页要各做哪一件事。
这一步的收尾在 slide 51。讲者把前面几页压成一句可以搬走的话，CBT 提供的是一种分配、释放、并遍历内存池里所有元素的办法，而且这套东西可以在 GPU 上高效地做完。这一页也是前半场 overview 的收尾，讲者说完就把话筒交给 Anis，由他来讲实现细节（讲义 slide 51）。同一页还给出一处规模读数，他们 demo 用的内存池是 128k 宽，总共需要 7 MB 内存。这个 128k 是这一场演示所选的那一档，讲义在前面明确说过规模可以按应用的需要调高或调低，demo 里提供的是 128k 这一档的布局。
本章可核对的结论有三条。这些性质让 CBT 可以充当内存池管理器，追踪已分配与可用内存，而内存池就是一个存你想存的任何数据的数组，容量等于位域容量，已分配项用绿位追踪、可用内存用红位追踪，根给出还有多少可用与已分配（讲义 slide 36）。分配是把某一位置一并更新求和归约树，回收是把某一位置零再更新求和归约树，页内给出的函数是 atomic_allocation() 与 atomic_deallocation()（讲义 slide 37 至 39）。讲者的收尾口径是 CBT 提供分配、释放与遍历内存池里所有元素的办法，且可以在 GPU 上高效完成；demo 的内存池为 128k 宽、共 7 MB，这一档可按应用需要调高或调低（讲义 slide 51）。下一章看网格侧怎么把一半边翻译成一个三角形。
6网格侧：一半边一个三角形，再把它压进槽位
上一章的内存池能分配、能回收、能遍历，但它还只是一个池子。这一章看池子里装的是什么，以及这件事为什么需要额外的邻接信息（讲义 slide 41 至 42）。
方法的两端在这两页交代清楚。输入是一个半边界网格（halfedge mesh），输出是每条半边界一个三角形。讲者的原话是方法以一个半边界网格为输入，并为每条半边界产出一个三角形，他还提醒听众可以在这两页之间来回看，一页是接口，一页是映射之后的结果。页内沿用前面那四个函数签名，available_memory()、allocated_memory()、atomic_allocation() 与 atomic_deallocation()，并把它们与位域、求和归约树、内存池三层示意摆在同一张图上，池那一列的槽位序列与上一章的形状一致。
压进槽位的做法在 slide 43 讲清。他们把每个三角形的三个顶点压成一个整数，这个整数叫 heapID（堆编号），存进内存池的一个专用条目里。页内的例子有 12 个三角形，于是需要 12 个槽位。这一步把几何问题翻译成槽位问题，三角形本身不再单独占结构，它退进那一个整数里，槽位只是池中一个可分配的位置。
slide 44 继续用三角形 23 走了一遍。它存在槽位 7，除 heapID 之外，这一条还存了用指针表示的邻接信息。
邻接信息的展开占了下几页。从三角形 23 出发，它的邻居有三角形 24，落在槽位 8；三角形 27，落在槽位 11；还有三角形 17，落在槽位 1（讲义 slide 45 至 47）。slide 48 补一句，每个三角形都要这样做。这句话把邻接从个别三角形的装饰变回整张网格的共同约定，之所以要逐条存下来，是因为后面的细分只认这些指针。
为什么要存这些信息，讲义用病灶来回答（讲义 slide 49）。他们实现的是一套二分（bisection）细分方案，能把一个三角形分裂成两个新的。讲者在这里给了一句让步，朴素地二分一个三角形会产生 T 形接缝（T-junction），而 T 形接缝会让最终表面上出现裂缝（crack）。这两个词在页内与讲稿里是绑在一起的，T 形接缝是中间状态，裂缝是它落到表面上的后果；这条链是朴素做法会付的代价，他们的方案要处理的就是它。
治病的办法也在这条线上（讲义 slide 50）。靠邻接信息，他们才能把二分传播到相邻的多个三角形上，从而保证表面无裂缝。这一句把前面几页的邻接铺陈收成一条规则，凡是分裂一条边，就要沿邻接把这次二分继续往下传，直到接口两边一致。
网格用的内存池规模另有一页（讲义 slide 51）。页内是池的布局与大小，讲者在同一页给出 demo 的读数，内存池 128k 宽，总共需要 7 MB 内存。这一页与本章开头的映射相呼应，池的容量由位域容量决定，池里装的就是这一批压缩后的整数；128k 仍是这一场演示所选的那一档，讲义明说可以按应用需要调高或调低。
本章可核对的结论有四条。方法以半边界网格为输入，为每条半边界产出一个三角形，页内给出的接口是 available_memory()、allocated_memory()、atomic_allocation() 与 atomic_deallocation()（讲义 slide 42）。每个三角形的三个顶点压成一个 heapID 存进池里一个专用条目，示例里 12 个三角形需要 12 个槽位，三角形 23 落在槽位 7，并带指针形式的邻接信息（讲义 slide 43 至 44）。三角形 23 的邻居包括槽位 8 的三角形 24、槽位 11 的三角形 27 与槽位 1 的三角形 17，每个三角形都按同一套办法存邻接（讲义 slide 45 至 48）。存邻接的理由是这套方案用二分细分，朴素二分一个三角形会产生 T 形接缝，最终表面上会出现裂缝，靠邻接才能把二分传播到多个三角形上，保证表面无裂缝（讲义 slide 49 至 50）；demo 的内存池为 128k 宽、共 7 MB（讲义 slide 51）。下一章进入并行更新例程，看这棵 CBT 怎么被压进组共享内存。
7并行更新例程：把约 1 MB 压到约 3 KB
上一章把网格压成了一池整数，池子背后的那棵树还没讲怎么在 GPU 上被并行改写。这一章进入实现细节（讲义 slide 52）。讲者在这一页先把范围定下，因时间有限不会去讲代码细节，完整源码已经发布，可以自己拿去探索和试。这句限定整章都要带着，下面的做法都停在讲义与讲稿明说的那一层。
为什么要放在组共享内存里，讲义 slide 53 给了理由，为了读写更高效。他们想把 CBT 存进组共享内存（group shared memory），示例统一用 128k 的 CBT，并说明可以按应用需要调高或调低。这棵树要能被工作线程读写，所以他们本来想用 uint32_t 来表示节点，以便吃上原子内置函数（atomic intrinsic），但页内紧接着标出这里有个问题。
问题有多大，下两页给出算术（讲义 slide 54 至 55）。节点的数目是位域大小的两倍，页内写出 const uint32_t cbt_num_nodes = 2 * (128 * 1024); // 262144，接着一行 groupshared uint32_t gs_cbt[cbt_num_nodes]; // 1 MB，讲者补一句，这样朴素地存下来大约要 1 MB。下一页在同样两行下面压上一行红字，DX12 上组共享内存限制在 32 KB。约 1 MB 与 32 KB 的上限正面相撞，讲义的结论很直接，需要一种更好的表示。
怎么拆，讲义先从一层说起（讲义 slide 56）。树的每一层由四样东西定义，该层的节点数、每个节点能表示的数值范围、表示这个范围所需的最小位数、以及最终用来表示它的位数。页内把这条定义写成一行模板 Level X: [Range] x Num Values, Min size, Actual Size。按这四样，他们把树分解成若干部分。
第一类是原子友好子树（atomic-friendly subtree），slide 57 把它标成红色。节点按 uint32_t 对齐、放在组共享内存里。讲者给的理由是修改期间所有线程都可以安全地写树的任意节点，节点用 uint32_t 表示以吃上原子内置函数；它覆盖第 0 层到第 6 层。
第二类是线程子树（thread subtree），slide 58 把它标成绿色。规则是每棵子树在同一时刻只被一个线程修改，节点尺寸向上取到最近的 2 的幂，同样放在组共享内存里；页内把第 7 层到第 10 层划给它。第三类是虚拟层级（virtual level），slide 59 明说它不被显式表示，讲者说这些层级可以从最后一层推出来，页内把第 11 层到第 16 层标成 Virtual。第四类是原始位域（raw bitfield），slide 61 标成蓝色，约束是 uint64_t 与结构化缓冲（structured buffer）。它用 uint64_t 表示以吃上一些内置函数，存放在组共享内存之外的结构化缓冲里，页内写成第 17 层 Raw 64 bits representation。
落地成几个缓冲在 slide 63 至 67 交代。页内先给一行注释 // Graphics Buffers that hold the CBT，然后是两行声明，RWStructuredBuffer<uint32_t> _TreeBufferRW: register(CBT_BUFFER0_BINDING_SLOT); // RED + GREEN 与 RWStructuredBuffer<uint64_t> _BitfieldBufferRW: register(CBT_BUFFER1_BINDING_SLOT); // BLUE。第一个缓冲装树里红色与绿色那两部分，第二个装位域。slide 65 再加第三个缓冲 RWStructuredBuffer<uint32_t> _AllocationBufferRW，讲者说这是分配缓冲。slide 66 用内存占用表推出树占的槽数，页内写成 const uint32_t tree_num_slots = (1 * 32 + 2 * 32 + ... + 1024 * 8) / 32;；slide 67 在它下面给出组共享内存里的那一份 groupshared uint32_t gs_cbtTree[tree_num_slots]; // ~3KB，讲者的结论是这一档的 CBT 本体现在约占 3 KB，这个量级可以接受。相对约 1 MB 的朴素表示，账目落到了 KB 量级。
每帧怎么用这棵树，在 slide 68 至 76 讲完。步骤分三段，页内把它们写成 Book & Allocate & Cancel，先预订最坏情况下需要的内存，再按这次处理的细分情形分配若干个位，最后把没用掉的空间还给内存管理器。函数名逐页给出，void cbt_new_frame();、void book_memory_space(uint32_t numSlots);、void cancel_memory_booking(uint32_t numSlots);，分配用 uint32_t allocate_next_available_slot(uint32_t bisectorID);。接着是 Decode Bit(s)，用 void load_buffer_to_shared_memory(uint32_t groupIndex); 把树缓冲按工作组拷进组共享内存，再用 uint32_t decode_bit_complement(uint32_t index); 做树下降，讲者说这份内存布局让树下降显著加速。然后是 Set Bit(s) Atomic，用 void set_bit_atomic(uint32_t bitID, bool state); 把分配的位置一、回收的位置零；最后是 Sum Reduction，用 void reduce(...); 做一次求和归约，让树回到合法状态。slide 76 压上一行 Repeat Each Frame，讲者说这套操作每帧重复一遍。
本章可核对的结论有五条。他们把 CBT 放进组共享内存以求读写更高效，示例用 128k 的 CBT 并明说可以按应用需要调高或调低；朴素表示下节点数是位域大小的两倍，2 × (128 × 1024) = 262144，约 1 MB，而 DX12 的组共享内存上限是 32 KB，于是必须换一种表示（讲义 slide 53 至 55）。每一层由节点数、数值范围、最小位数与实际位数四样定义，树按不同约束拆成原子友好子树、线程子树、虚拟层级与原始位域四类结构（讲义 slide 56 至 62）。落地是两个结构化缓冲加一个分配缓冲，_TreeBufferRW 装红绿两部分、_BitfieldBufferRW 装位域、_AllocationBufferRW 供分配用，CBT 本体现在约占 3 KB（讲义 slide 63 至 67）。每帧的用法是先预订最坏情况、再按情形分配若干位、最后把没用掉的还回去，配套动作是把树缓冲拷进组共享内存、做树下降、原子置位或置零、再做一次求和归约，每帧重复（讲义 slide 68 至 76）。下一章把环绕这些缓冲的更新管线一段段摊开。
8十二段更新管线
上一章把 CBT 侧讲到约 3 KB 的规模，这一章换到内存池一侧，把环绕它的缓冲与整条更新管线摊开（讲义 slide 77 至 78）。
内存池侧先要两个缓冲。页内注释写成 // Graphics Buffers that hold the Memory pool，下面两行是 RWStructuredBuffer<uint64_t> _HeapIDBufferRW: register(POOL_BUFFER0_BINDING_SLOT); 与 RWStructuredBuffer<uint3> _NeighborsBufferRW: register(POOL_BUFFER1_BINDING_SLOT);。第一个装 heapID，第二个装邻接。讲者在这一页说，前面提过的 HeapID 与 Neighbor 各需要一个缓冲，页内在两行声明下面还画出了池里的槽位序列。
位置信息在 slide 79 至 80 加进来。页内第三行是 RWStructuredBuffer<float3> _PositionRWSBufferRW: register(POOL_BUFFER2_BINDING_SLOT);，讲者说他们还要能存相机相对（camera-relative）位置，先是三角形三个顶点各一个位置。下一页补上第四个位置，页内写明 4 positions per bisector，讲者解释这个位置用来重建父三角形，分裂与合并的判定要用到它。
临时数据在 slide 81 单独占一处。页内写成 RWStructuredBuffer<UpdateData> _UpdateDataBuffer: register(POOL_BUFFER3_BINDING_SLOT);，配一个同名结构体，讲者把这份数据叫 update data，并说明它是临时性质的一层。
分裂状态在 slide 82 至 85 编成位。在每个更新循环里，一条平分线可以处在五种状态之一，不变、单次分裂、两次分裂（有两种情形）、或三次分裂。他们把这种分裂状态编成三位，存在一个 uint32_t 里，以便吃上原子内置函数，这个字段在结构体里叫 subdivPattern。页内把几种模式的取值列成 0x0、0x1、0x3、0x5、0x7，并在旁边标注 One Alloc、Two Allocs、Two Allocs、Three Allocs。按分裂情形最多需要三个新槽位，讲者说明实现里为了性能与紧凑，总是复用当前平分线所在的槽位，页内相应给出 Previous Slot、First Alloc、Second Alloc、Third Alloc 这四个位置，那一行 uint3 allocations 的初值写成三个 UINT32_MAX。
邻接怎么预测也在这一段（讲义 slide 86 至 88）。讲者强调索引的分配方式必须一致，这样在两个平分线的接口上，无论出现哪一种分裂组合，都能只用当前与邻居平分线的 update 与 neighbor 数据预测出邻居数据，他把这一步称为无同步并行实现的基石。slide 88 再补一个数组，用来存额外的标志与邻居传播数据，页内写出 uint32_t flags; 与 uint2 propagation;。
整条管线在 slide 89 一页展开。页内把十二段的名字竖排列出，Reset（重置）、Classify（分类）、Split（分裂）、Decode（解码）、Bisect（二分）、Propagate Bisect（传播二分）、Prepare Simplify（准备简化）、Simplify（简化）、Propagate Simplify（传播简化）、Reduction（归约）、Evaluate LEB（求值 LEB）、Deformation（形变）。这十二段是本章的骨架，后面几章按同一顺序逐段展开。
派发方式在 slide 90 至 93 说明。页内先给一句，给定一个三角化就对应一个内存池，接着把间接派发（indirect dispatch）标在管线上。讲者说多数 pass（趟）会是基于某一组平分线的间接派发。平分线的集合会随 pass 变化，每一步要处理的子集由那一步自己指定。这几句合起来，管线的形状就是十二段串联，每一段只处理上一段筛出来的那一小撮平分线，页内用一次次改变线程数的示意把这件事画出来。
第一段在 slide 94 至 95 交代。Reset 是一个单线程派发，页内写成 m_cmdBuffer->dispatch(1, 1, 1); // One thread，同一页在派发那一行旁标 CPU，在两个 CBT 函数旁标 GPU。这一段的动作有两个，cbt_new_frame(); 为这一帧准备分配，reset_queues(); 重置用于间接派发的平分线队列。讲者的原话是这一趟为这一帧准备分配，并重置供间接派发用的平分线队列。
本章可核对的结论有五条。内存池侧需要两个缓冲分装 HeapID 与 Neighbor，相机相对位置则要三角形三个顶点各一个加一个用来重建父三角形的第四点，分裂与合并的判定要用到它（讲义 slide 78 至 80）。每条平分线在每次更新循环里可处在五种分裂状态之一，这种状态编成三位存在 uint32_t 里以吃原子内置函数，按情形最多需要三个新槽位，实现里总是复用当前平分线的槽位（讲义 slide 82 至 85）。索引分配方式必须一致，这样任意分裂组合下都能只用当前与邻居平分线的数据预测邻居数据，这是无同步并行实现的基石，另有 flags 与 propagation 存标志与传播数据（讲义 slide 86 至 88）。整条管线的十二段是 Reset、Classify、Split、Decode、Bisect、Propagate Bisect、Prepare Simplify、Simplify、Propagate Simplify、Reduction、Evaluate LEB 与 Deformation，多数是间接派发，平分线集合随 pass 变化，子集由每一步自己指定（讲义 slide 89 至 93）。Reset 是单线程派发，为这一帧准备分配并重置供间接派发用的平分线队列（讲义 slide 94 至 95）。
9Classify 与 Split：先判定谁要细分，再算最坏情况要预留多少
管线的第二段是 Classify。上一段的 Reset 只做两件事，为这一帧准备分配、重置用于间接派发的平分线队列；判定与分裂这两段从本章展开（讲义 slide 96）。
Classify 跑在一次间接派发上，页内写成 m_cmdBuffer->dispatch_indirect(ACTIVE_BISECTORS);，同一行注释列出这一批平分线的 HeapID，从 16、18、19 一直排到 48、49（讲义 slide 96）。讲者备注给了这一段的分工，每个线程负责一条活跃的平分线（讲义 slide 96）。判定把每条平分线归到三种状态里的一种，页内列作 Keep、Merge 与 Split，也就是保留、合并与分裂；讲者说这三种操作各自的判据随目标而变，demo 用的是下面几条（讲义 slide 97）。
判据按先后排。先做 NdotV 测试，页内写成 if (NdotV < 0.0) return MERGE;，注释问的是当前平分线是否可见，不通过就标为合并（讲义 slide 98）。接着与一个或多个视锥（frustum）求交，页内写成 if (not intersect_frustum(...)) return MERGE;，与任何一个视锥都不相交同样标为合并（讲义 slide 99）。再往下把四个顶点投影下来，页内声明 float currentArea, parentArea; 并调 project_bisector(...)，备注说这一步要算出三角形与父三角形各自的投影面积（讲义 slide 100）。最后拿这两个面积与应用定义的一个三角形尺寸比较，页内三段依次是当前投影面积大于 TRIANGLE_SIZE 就返回 Split、父三角形的投影面积小于 TRIANGLE_SIZE 就返回 Merge、两者都不满足则返回 Keep（讲义 slide 101）。
页内那张表把这一批平分线的判定结果一并列出，16、34、18、19、20 是 Keep，42 是 Merge，46 是 Split，其后的 48、43、49 是 Merge，余下的仍是 Keep（讲义 slide 96–101）。判定是逐条独立做出的，同一批里可以同时出现三种状态，而下一步只挑走其中被标为需要分裂的那一部分。
判定之后是 Split，它只跑在标为需要分裂的平分线上（讲义 slide 102）。派发参数随之换成 m_cmdBuffer->dispatch_indirect(SPLIT_BISECTORS);，后面注释指明这一批只有 HeapID 46（讲义 slide 102）。讲者把这次分裂的第一件事说得很硬，要算出为保证分裂被传播下去、最坏情况需要预留多少内存（讲义 slide 103）。页内写成 uint32_t maxMemory = eval_max_memory(...);，紧随两行注释点明朴素解是 2 × 深度 − 1、不可行、需要做更好（讲义 slide 103）。讲者补了朴素解为什么不可行，它在高速移动时会欠细分（讲义 slide 104）。更好的估算讲者没有在演讲里展开，他明说做法不在这里细讲、细节在他们分享的源码里（讲义 slide 105）。
估算拿到之后从 CBT 里预订这么多内存，页内写成 if (not book_memory(maxMemory)) return;。讲者给这一步配了一条硬约束，如果拿不到所需的空间，这次分裂就不能进行，否则会破坏 LEB 这套机制（讲义 slide 103）；预订失败的情形他在后面又重述一遍，同样不做（讲义 slide 105）。
预订成功之后，传播算法从递归改成 while 循环（讲义 slide 106）。页内先设 uint32_t usedMemory = 1;，循环体分两支：当前深度与孪生面深度相等、或孪生面已经分裂，就用 InterlockedOr 把细分模式置上 0x1、已用内存加一、分配下一个可用槽位、结束循环；否则按 rightSuddiv ? 0x3 : 0x5 置位、已用内存加二、连着分配两个槽位、再用 move_to_twin() 走到孪生面（讲义 slide 106）。这一例中途遇到了 T 形接缝，于是继续往下走（讲义 slide 107），再接两次分配就收尾（讲义 slide 108）。循环结束后页内调 cancel_memory_booking(maxMemory - usedMemory);，把没分配掉的空间还给 CBT（讲义 slide 109）。
本章可核对的结论有三条。Classify 每个线程管一条活跃平分线，把它判成 Keep、Merge 与 Split 之一，demo 的判据依次是 NdotV 测试、与一个或多个视锥求交、投影四个顶点并比较三角形与父三角形的投影面积、再与应用定义的三角形尺寸比较，任一前置条件不通过即标为合并（讲义 slide 96–101）。Split 只跑在标为需要分裂的平分线上，先估最坏情况要预留多少，估算的朴素解 2 × 深度 − 1 会欠细分、不可行，替代做法按讲者所说明留在源码里，预订失败则这次分裂不做，以免破坏 LEB（讲义 slide 102–105）。预订成功后传播改成 while 循环，逐个三角形分裂、按情形分配一或两个槽位、把细分传给孪生面，遇 T 形接缝继续走，最后把没用掉的空间还回去（讲义 slide 106–109）。下一章接着走分裂侧剩下的两段，再转到合并侧。
10Bisect 与 Prepare Simplify
上一章把分裂的内存预订好、把细分传播到孪生面并退还余量；这一章走完分裂侧剩下的两段，再转到合并侧（讲义 slide 110）。
第一段是 Decode，跑在被标为需要细分的平分线上，页内派发注释给这一批的 HeapID 是 46 与 27；讲者说这一步要把每个已分配的槽位与 CBT 里的一个空位对应起来（讲义 slide 110）。页内分三步，先把 CBT 载入组共享内存，写成 load_buffer_to_shared_memory(...);；再数出细分模式里置一的位数，写成 uint32_t numAllocations = countbits(updateData.subdivPattern);；最后按这个数逐个解码，写成 updateData.allocations[allocIdx] = decode_bit_complement(...);（讲义 slide 111）。细分模式里置一的位数就是要做几次解码，结果存进临时数据（讲义 slide 111）。
下一段 Bisect 跑在与 Decode 同一批平分线上，派发注释同样是 46 与 27（讲义 slide 112）。页内给出修补函数 void update_bisectors(uint32_t ID0, uint32_t ID1, …)，注释说它按当前平分线与邻居的模式改邻居、改 heapID，并标出哪些细分需要传播，随后按细分模式分三支调用（讲义 slide 113）。讲者在这一步给了两条限定，它只是部分更新了邻居，仍然留下有问题的接口，页内用红色标出、留到下一步解决；这一步产出的是三角化的新状态（讲义 slide 113、114）。段末还要回写 CBT 的位，按这次分裂所需的分配数逐个原子置位，写成 set_bit_atomic(upData.allocation[allocIdx], true);（讲义 slide 115）。
第三段 Propagate Bisect 专门处理那些有问题的接口，必要时改邻居，派发注释给它的 HeapID 是 93（讲义 slide 116）。页内先问邻居是否被分裂过，是的话按邻居的细分模式调整，否则直接调 adjust_neighbors(neighborID, currentID);（讲义 slide 117）。讲者把判据说全，修补例程要考虑邻居是否被分裂、以及它是怎么分裂的，一次、两次还是三次（讲义 slide 117）。分裂侧到此收住，他顺带交代合并侧，思路大致相同，但更简单，因为没有传播要管（讲义 slide 117）。
合并侧第一段是 Prepare Simplify，派发注释列出这一批四个 HeapID，42、43、48、49（讲义 slide 118）。为避免同步与竞态，由这四条里 heapID 最小的那条负责检查并登记这次简化，例子里是 42，用深度与 heapID 就能认出是哪一条（讲义 slide 119、120）。页内先做两道门槛，heapID 是奇数、或配对深度与当前深度不等，就直接返回；孪生面的判据与此类似（讲义 slide 120）。过了门槛，页内逐条确认四条都要求合并，任何一条不满足就返回，全都满足才把当前平分线入队，写成 enqueue_for_simplify(currentID);（讲义 slide 121）。讲者还交代了一处取舍，实践中为了优化，不把奇数 heapID 的平分线放进合并队列（讲义 slide 119）。
下一段 Simplify 在例子里只跑 42 这一条（讲义 slide 122）。页内四行动作依次是更新当前平分线、释放它的配对、更新孪生面、释放孪生面的配对（讲义 slide 123）。讲者把留下的与释放的分开说，留下的是每组里 heapID 最小的一条，也就是 42 与 48，释放的是另外两条，43 与 49（讲义 slide 123）。与分裂侧一样，这一步更新 heapID、只部分更新邻居（讲义 slide 124）。最后把 CBT 里不再使用的槽位置零，落在配对与孪生面的配对上（讲义 slide 125）。
合并侧最后一段 Propagate Simplify 派发到那些让邻居产生不一致的平分线上，这一批的 HeapID 是 21 与 24（讲义 slide 126）。页内按邻居是否被合并分两支，被合并过时再看它是否已被删除，被删除就调整邻居的配对，没被删除就调整邻居本身；没有被合并则直接调整邻居（讲义 slide 127）。讲者收尾一句，把分裂与合并两类请求都处理完，就得到一致、而且与 LEB 兼容的三角化（讲义 slide 128）。
本章可核对的结论有三条。Decode 先载入 CBT，再按细分模式里置一的位数做同样多次解码；Bisect 与它同批，改 heapID 与邻居指针、只部分更新，并按分配数原子回写位（讲义 slide 110–115）。Propagate Bisect 补掉那些接口，判别邻居是否被分裂以及分裂了几次；合并侧由四条里 heapID 最小的一条登记，实践中不把奇数 heapID 放进合并队列（讲义 slide 116–121）。Simplify 更新留下的、释放另外的、把不用的槽位置零，Propagate Simplify 再按邻居是否被合并、当前是否被删除分别修补，最终得到一致且与 LEB 兼容的三角化（讲义 slide 122–128）。下一章看位域改完之后如何把树对齐。
11Evaluate LEB：最终位置由一条链给出
前几段改了位域，树已经和位域对不上，所以在位域这一步之后要先对 CBT 的树做一次求和归约（sum-reduction），把两者重新对齐（讲义 slide 129）。讲者拿 128k 的 CBT 举例（讲义 slide 130）。页内把树的层级按区间与条数列开，Level 0 是 [0, 131072] 一条，Level 1 是 [0, 65536] 两条，逐级往下到 Level 10 的 [0, 128] 一千零二十四条，另有一行记着 Level 17 是原始 64 位表示（讲义 slide 130）。归约分三趟，第一趟 dispatch(1024 / 4 / 64) 标为 REDUCE_PREPASS，把位域归约到树上第一个显式存储的层级；第二趟 dispatch(512 / 64) 标为 REDUCE_FIRST_PASS，在树的每线程原子那一段里过一次；第三趟 dispatch(1) 标为 REDUCE_SECOND_PASS，由一个单独的工作组对原子友好树做完整的求和归约（讲义 slide 131–133）。讲者认为这样能把整棵树在合理成本内更新完（讲义 slide 133），并在下一页给出 demo 各档 CBT 规模在三张卡上的归约耗时表，三张卡是 Intel Arc 770、AMD 6650 XT 与 Nvidia 4090（讲义 slide 134）。这张表的分行分列未经人工核对，正文不逐行抄。
归约之后是 Evaluate LEB，它对被修改过的平分线派发，页内写成 dispatch_indirect(MODIFIED_BISECTORS);，用来保证位置是最新的（讲义 slide 135）。几何信息用 heapID 编码，写成二进制就是一串位，页内给的样子是 HeapID = 0 0 1 0 … 0 1（讲义 slide 136）。最终位置由一串矩阵乘法给出，heapID 的每一位对应两个矩阵之一，页内画出第 i 位为 0 与第 i 位为 1 两支，并注明这两个矩阵就是 demo 用的那两个（讲义 slide 137–138）。
这一步有两个麻烦（讲义 slide 139）。即使输出位置用单精度、而且是相机相对（camera-relative）的，乘法也必须在 double 空间里做，否则会因为方法本身的精度问题把浮点搞坏。另一处是按细分层级不同，最多要做 64 次 3×3 矩阵乘法，页内标为 Up to 64 3x3 double matmul，讲者的评价是这很多。
优化分三级。第一级把这一串乘法拆成两段各 32 次 3×3 float 乘法、中间夹一次 3×3 double 乘法，页内标为 32 3x3 float matmul X2 + 1 3x3 double matmul，讲者说这样能降低 ALU 消耗、更好地利用显卡的浮点吞吐，但仍然不够好（讲义 slide 140）。第二级把 heapID 切成若干等长的位段，页内给的位段样子是 00000、00001、00010、00011 一直到 11111（讲义 slide 141）；再对若干层内所有组合预先乘出乘积，做成一张矩阵缓存（matrix cache），页内标为 Matrix cache to speed up the evaluation (Depth 5)（讲义 slide 142）。讲者说实测深度取 5 是加速比与体积的最佳折中，代价是这张缓存要放进组共享内存，因为访问太频繁（讲义 slide 142）。这样一做，乘法降到最多两组各 6 次 3×3 float 乘法加一次 3×3 double 乘法，页内标为 6 3x3 float matmul X2 + 1 3x3 double matmul（讲义 slide 143）。讲者补了一句限定，这个着色器只对被修改过的平分线执行，那只占全部平分线的一小部分（讲义 slide 143）。
使用方式在页内分三步。先把矩阵缓存载入组共享内存，写成 load_leb_matrix_cache_to_shared_memory(...);（讲义 slide 144）。再把 heapID 展平成四个位置，页内声明 double3 bisectorPos[4]; 并调 evaluate_positions(heapID);，讲者说这四个位置里三个给当前平分线、一个给父三角形（讲义 slide 145）。最后做一次变换，把结果映射到球形行星上、并转到相对世界空间，页内是四次 to_rws_planet_coord(...) 写进位置缓冲（讲义 slide 146）。
管线最后一段是 Deformation，它对所有已有位置施加相应的形变（讲义 slide 147）。地球是一堆 FFT 的结果，月球用 NASA 网站提供的高度位移图，再加一堆噪声函数补高频细节（讲义 slide 147）。这些位置既供本帧渲染，光栅化或光追都行，也供下一帧做分类判定，页内把分类那段代码又摆了一遍（讲义 slide 148–149）。
本章可核对的结论有三条。位域改过之后先做一次求和归约把树对齐，分预趟、首趟与次趟三趟，最后一趟由一个单独工作组完成，demo 另给各档 CBT 规模在三张卡上的耗时表（讲义 slide 129–134）。Evaluate LEB 只对修改过的平分线派发，几何信息编码在 heapID 的位里，每位对应两个矩阵之一，最终位置由一串矩阵乘法给出；乘法必须在 double 空间做，按层级最多 64 次，经三级优化降到最多两组各 6 次 float 加一次 double，而这段着色器只作用于一小部分平分线（讲义 slide 135–146）。Deformation 给已有位置施加形变，地球来自 FFT、月球来自 NASA 位移图与噪声，结果既供本帧渲染也供下一帧分类（讲义 slide 147–149）。下一章看性能口径与那份开源实现。
12性能表、结语与那份开源实现
讲者把性能放在最后几页讲，先做的一件事是把口径钉死。截图是 demo 在地球表面跑出来的（讲义 slide 151），他关心的是表里用红色标出的那一段（讲义 slide 152）。渲染分辨率是 1920×1080、CBT 规模是 128K（讲义 slide 153）。profiling 放在三张 GPU 上做，Intel Arc 770、AMD 6650 XT，页内说它大致相当于一台 PS5，以及更高端的 Nvidia 4090（讲义 slide 153）。三张卡连成一条从主流到高端的区间，讲者口中「相当于 PS5」的那一句落在 6650 XT 上。这张表里的 6650 XT 是那把标尺，另外两张分别给出这一档上下的参照。他先在整张 capture 里框出与更新管线有关的那一段，再逐段读它的耗时。页内那张表把前面讲过的每一段都逐段列了进去，是讲者为整条更新管线做的一次汇总（讲义 slide 153）。这张表的分行分列未经人工核对，正文不逐行抄，只引讲者点名的结论。
讲者点名的结论是，他们始终能保持在合理的成本内，而且在相当于 PS5 的硬件上低于 0.2 毫秒（讲义 slide 154）。他给这句话的定位是，相对于这套方法所达成的效果，这个成本已经很合理。这条读数覆盖的是前面讲过的整条更新管线，十二段都在其中，他把这条线当成整场性能部分的落点。
限定有两处，讲者都主动摆了出来。后段的渲染管线取决于实际使用的形变与管线的整体结构，demo 里用的是可见性缓冲（visibility buffer）加一个材质 pass（material pass），这一段的成本没有固定值（讲义 slide 155）。这些数字是在 AMD 6650 XT 上得到的，而且很依赖你怎么生成表面数据（讲义 slide 156）。两处限定合起来说明，表里的数字对应的是 demo 那一套形变与那一套后段管线。
另有一段与光追有关。方法兼容实时硬件光追，因为图元数量保持在相当低的水平，即使每帧完整重建 TLAS 与 BLAS（顶层／底层加速结构）也能拿到不错的结果（讲义 slide 157）。这一条讲的是加速结构重建这一笔开销，讲者把它作为额外的补充给出，用来说明方法与光追并行不冲突，也说明两套用法各有各的账。
收尾一页讲者把 demo 的完整代码开放出来，地址印在页内 https://github.com/AnisB/large_cbt，他另请听众去看论文，说更详细的方法说明在那里（讲义 slide 158）。这一页同时收住了两条线索，demo 给出可运行的实现，论文给出更细的方法说明，讲者把这两样材料一起交给听众，并留在现场接受提问。
边界 1： 本篇只做三角化与渲染那一侧，数据生成明确不在范围内。讲义 slide 15 把这一类大规模组件的问题分成数据生成与三角化渲染两个子问题，本篇只贡献给后者；纹理、精灵、实例这些数据怎么生成，那一条线不复述，也不替它补内容。
边界 2： 这是一套「半年前论文加半年后新实现」的组合。讲义 slide 3–4 明说论文里那 4 页实现细节如今多少已经过时，因为实现在这半年里被重做过一遍；因此叙事以新实现为准，部分细节只存在于源码里，slide 105 明说 Split 的最坏情况估算不在演讲里展开，正文照此如实标注、不替讲者补。
边界 3： 本场所有实现与性能数字都是 128k 那一档的 CBT。讲者明说规模可按应用需要调高或调低，demo 里提供的是 128k 的布局；不得把 128k 当成这套方法的固有上限，它只是这一场取的一个档位。
边界 4： 性能读数的口径是钉死的，1920×1080、CBT 128K，三张卡分别是 Arc 770、AMD 6650 XT（大致相当于 PS5）与 Nvidia 4090；讲者点名的结论是始终在合理成本内、在相当于 PS5 的硬件上低于 0.2 毫秒。口语里的这个 0.2 毫秒按页内数值写，不四舍五入到别的位数。表的分行分列未经人工核对，正文不逐行抄。
边界 5： 数据侧的数字依赖表面数据的生成方式（slide 156 明说），后段渲染管线也取决于实际使用的形变与管线结构，demo 用的是可见性缓冲加材质 pass（slide 155）；这两处限定都要跟着读数一起读。
边界 6： 讲义 slide 20–27 是八页纯截图，无文字层、无讲稿描述，本篇未取图，也不描述画面。
边界 7： 许可方面，讲义幻灯区内逐页印着同一行保留所有权利的版权行，159 页全部命中，按非 CC 口径逐件登记、逐图署名并标注残留风险。讲义 slide 158 另给了 demo 的开源地址，那是这套实现的代码出处，与讲义及页内画面的许可要分开写，不得据此推断讲义或画面可转载。
边界 8： 命名沿用讲者口径。他把这次改进叫 CBT version 2 或简称 CBT-V2（slide 16），而本场题目用的是 CBTS，正文照讲义写、不替他统一命名；缩写 LEB 讲义没有展开，不猜它的全称。
13贡献块
可搬走的四条与站内互读
这一场能留下的东西，集中在「把一个有硬上限的资源当成一等约束」这一类：组共享内存 32 KB、每帧的射线与 pass 预算、以及「分裂一旦开始就必须做完」这条隐含要求。讲者在 slide 3 至 4 还交代了一层来路：论文里那 4 页实现细节如今多少已经过时，因为 Anis 在这半年里把实现重做了一遍。本章收的四条，没有一条是「设计了一套新方案」，全部是「在一处硬约束上换了做法、换到了多少」。
贡献 1：把「表示」按访问约束分层拆开。 冲突是直接的：128k 的 CBT 节点数是位域大小的两倍（2 × (128 × 1024) = 262144），朴素表示约 1 MB，而 DX12 的组共享内存上限是 32 KB（slide 54–55）。他们的手法不是压缩，而是先问「谁在什么时候能写谁」：修改期间所有线程都可以安全写任意节点的部分，每个节点用 uint32_t 以吃原子指令，放进组共享内存（原子友好子树）；每棵子树同一时刻只被一个线程修改的部分，节点尺寸向上取到最近的 2 的幂（线程子树）；不需要显式表示、可以从最后一层推出来的部分干脆不存（虚拟层级）；要 uint64_t 内置函数、又不必进组共享内存的部分留在 structured buffer 里（原始位域）。四类结构合起来，CBT 本体现在约占 3 KB（slide 56–67）。可搬走的顺序是先按访问约束分类，再定每类的宽度与住处；反过来做，就会一直在那 32 KB 上做大扫除。
贡献 2：把「预留最坏情况」放在分裂之前，并且允许这一次不做。 Split 的第一件事不是分裂，而是算出要保证这次分裂被传播下去、最坏情况要预留多少内存（slide 102–109）。如果拿不到所需的空间，这次分裂就不能进行，否则会破坏 LEB 这套机制；拿到估算后从 CBT 里预订这么多内存，失败同样不做。讲者还顺带交代了一条被否掉的朴素解：2 × 深度 − 1 在高速移动时会欠细分，所以不可行（slide 104），更好的做法不在演讲里展开、见他们分享的源码。可搬走的是这种全有或全无的写法：先算上界、再在上界内一次分配、拿不到就整体放弃，它把「做了一半」这个最难回滚的中间态从设计里删掉了。
贡献 3：把几何编码进位串，再为这条链造一张深度 5 的矩阵缓存。 最终位置由一串矩阵乘法给出，heapID 的每一位对应两个矩阵之一；两个麻烦是乘法必须在 double 空间里做，否则会因为方法本身的精度问题把浮点搞坏，以及按细分层级不同最多要做 64 次 3×3 矩阵乘法（slide 139）。第一级优化把这条乘法拆成两段各 32 次 3×3 float、中间夹一次 3×3 double —— 讲者自己说仍然不够好（slide 140）；第二级才把 heapID 切成若干等长的位段，预先乘出「若干层内所有组合」的乘积做成矩阵缓存，实测深度取 5 是加速比与体积的最佳折中，而且因为访问太频繁必须放进组共享内存（slide 142），于是降到最多两组各 6 次 3×3 float 乘法加一次 3×3 double（slide 143）。可搬走的是先拆、再缓存的次序：拆段只把 ALU 压力摊开，真正把次数打下去的是「把重复的组合预先算好」。讲者同时给了限定：这个着色器只对被修改过的平分线执行，那只占全部平分线的一小部分（slide 143）。
贡献 4：用「让组里身份最靠前的那条负责登记」避开竞态。 合并侧要在四条平分线之间协调，Prepare Simplify 的做法是由这四条里 heapID 最小的那条负责检查并登记这次简化（slide 118–121），用深度与 heapID 可以很容易认出是哪一条；页内另注明实践中为了优化，不把奇数 heapID 的平分线放进合并队列。可搬走的是这条低成本纪律：当一组对象要共同决定一件事、又不想上锁时，用「谁的身份最靠前谁负责」把裁决收成单点，其余成员等结果。它与分裂侧的 Propagate Bisect 构成一对：那边派发到那些让邻居产生了不一致的平分线上、按邻居是否被分裂与分裂了几次分别处理（slide 116–117），把不一致收敛掉；这边靠事先指定负责人，把不一致挡在门外。
站在站内看，这一篇接在一条已有的几何轴上，但它接的位置和这条轴上已有的两篇不同。
篇目 35（NanoMesh）与本篇是同一句话的两种答案。 那篇要把 8000 万三角形搬上手机，做法是「离线写 cluster 层级、运行时按距离选」—— 把 mesh 切成 cluster 后连续重组成更粗层级，每个 cluster 上限 128 个三角形，运行时先做 instance 级的 HZB 快剔，再叠加视锥、遮挡与法锥剔除来挑 cluster；它要绕开的是移动端缺 mesh shader 与 bindless 的约束。而本篇讲者在 slide 29 明确说：Nanite 那一类做法（页内标成 Geometry Clusters + DAG）要求把全分辨率网格作为输入，所以对他们这种以 exabytes 计的组件用不上。两篇因此落在同一句话的两侧：一边是「离线写好层级、运行时只做挑选」，一边是「不预先写层级、用一个可分配的内存池让网格自己二分」。两篇的平台与规模口径几乎没有交集（一边是手机，一边是 1920×1080 与三张桌面卡），读数不可横比，但连读能把「自适应 LOD 的层级究竟从哪来」这个问题问清。
篇目 30（Adaptive Tessellation and Subdivision）与本篇共用一个词，落点并不重合。 那篇在补丁细分因子上做文章：DX11 的分数细分因子分得均匀却收不住，讲者先夹紧平行四边形把整块图案换掉，再把它搬上 compute 做自适应。本篇的自适应落在另一层 —— 「谁被细分了、被细分到哪一层」这件事怎么被记录、怎么被分配：三角化状态全部装在一棵可分配的树里，最终位置再由 heapID 的位串推出来。两篇可以并读成「细分图案」与「细分状态的记账」两层。
篇目 39（Frostbite 的动态漫反射 GI）与本篇不同轴：一个管光照、一个管几何与三角化，两篇没有可横比的读数，只在「把一条已经跑得动的管线再压一档」这件事上取向一致。本篇末尾那段形变与渲染（地球是一堆 FFT 的结果，月球用 NASA 网站提供的高度位移图再加一堆噪声函数补高频细节，这些位置既供本帧渲染、也供下一帧做分类判定，slide 147–149），讲者只给了做法与用途，站内没有同源篇目可对照，正文按讲义口径收住。本篇讲义给出的开源材料只有 slide 158 那一处 demo 仓库地址，没有别的代码仓库或开源链接。
14原文出处块
原文出处与引用口径
出处：SIGGRAPH 2024 · Advances in Real-Time Rendering in Games course · 2024-08 · 讲者 Anis Benyoub 与 Jonathan Dupuy（Intel Corporation）· 官方讲义《Achieving Scalable Performances for Large Scale Game Components with CBTs》，159 页，540×720 pt，来源 PDF 2024-siggraph-advances-cbt.pdf。讲义文本层没有印讲者全名 —— 页内只给出场的先后（slide 31 讲稿 then Anis will dive into the details、slide 51 讲稿 Your turn Anis!）与 slide 158 的仓库地址 github.com/AnisB/large_cbt；姓名与单位据 HPG 2024 会议程序与该论文页面（《Concurrent Binary Trees for Large-Scale Game Components》，arXiv:2407.02215）与 Intel 的公开说明补齐，只用于署名。
材料：官方讲义 159 页 —— 幻灯区内有实时文字层（159/159 页），区内文字合计 93,970 字符（含每页底部重复的那行版权行与论文标题）；幻灯片下方是一条讲稿带，合计 22,456 字符（均 141 字/页）。讲稿稀疏是本篇最重要的一条材料事实：页内只给标签、讲稿也没解释的地方，正文只写「讲义该页标注了 X」，不替讲者延伸。p20–p27 是八页纯截图（无文字层、无讲稿描述）⇒ 未取图、也不描述画面。页码为 PDF 页序（从 0 起），引用写作「讲义 slide N」。
许可：讲义幻灯区内 159/159 页都印着同一行保留所有权利的版权行（© 2024 SIGGRAPH ADVANCES IN REAL-TIME RENDERING IN GAMES course. ALL RIGHTS RESERVED.），并在幻灯区底部另印一行论文标题（"Concurrent Binary Trees for Large-Scale Game Components" HPG24）。取图走整页渲染，这两行会进入每一张图；处置是原样保留、不裁切、不改像素 —— 裁掉等于把版权行从图里抹掉，对署名诚实性不利，也违反「未修改引用」口径。逐页检索 Copyright、Creative Commons、CC BY、CC0、License、licensed、Images ©、with permission、courtesy of、许可，除上面那行之外全部无命中；页内没有素材单独署名，也没有 CC 素材。故按分区非 CC 口径处理：逐件登记、逐图署名（图号 + slide 号 + 出处 + 「未修改引用」）+ 标注残留风险（讲义未授权转载，条款以官方发布为准）。有一处必须与许可分开写：讲者在 slide 158 给出了 demo 的开源地址 https://github.com/AnisB/large_cbt —— 那是这套实现的代码出处，不是讲义的许可，不得据此推断讲义或页内画面可转载。
引用口径：页内数值按讲义原值写，不改写、不改位数、不四舍五入到别的位数 —— 250+ FPS（全高清、PS5 级别硬件，slide 17）；exabytes 与 1 exabyte = 1,000,000 terabytes（slide 28）；demo 的内存池 128k 宽、共 7 MB（slide 51）；2 × (128 × 1024) = 262144 个节点、朴素表示约 1 MB（slide 54）；DX12 组共享内存 32 KB 上限（slide 55）；CBT 本体约 3 KB（slide 67）；五种分裂状态（slide 82）、编成三位（slide 83）、最多三个新槽位（slide 84）；三种分类状态 Keep／Merge／Split（slide 97）；朴素解 2 × 深度 − 1（slide 104）；最多 64 次 3×3 double 矩阵乘法（slide 139）；两段各 32 次 3×3 float 加中间一次 3×3 double（slide 140）；矩阵缓存深度 5（slide 142）；两组各 6 次 3×3 float 加一次 3×3 double（slide 143）；1920×1080、CBT 128K、Intel Arc 770／AMD 6650 XT／Nvidia 4090（slide 153）；低于 0.2 毫秒（slide 154）。三处「讲者明说不在演讲里展开」照标注、不代为补内容：Split 最坏情况估算的更好做法请看他们分享的源码（slide 105）；因时间有限不讲代码细节，完整源码已发布（slide 52）；更详细的方法说明见论文（slide 158）。讲者的让步与限定一并保留：论文里那 4 页实现细节如今多少已经过时（slide 3–4）；混合表示很难用，尤其是自由飞行的相机（slide 30）；朴素二分会产生 T 形接缝、最终表面上会出现裂缝（slide 49）；原想用 uint32_t 吃原子指令但有麻烦（slide 53）；拿不到内存这次分裂就不做，否则破坏 LEB 这套机制（slide 103）；朴素解在高速移动时会欠细分（slide 104）；Bisect 只部分更新了邻居，仍然留下有问题的接口（slide 113–114）；乘法必须在 double 空间做，否则精度会坏、最多 64 次矩阵乘法，这很多（slide 139）；拆成两段后仍然不够好（slide 140）；这个着色器只对被修改过的平分线执行，只占一小部分（slide 143）；后段的渲染管线取决于实际使用的形变与管线结构（slide 155）；这些数字是在 AMD 6650 XT 上得到的，而且很依赖你怎么生成表面数据（slide 156）。页内表格不逐行抄：p153–p157 的逐段耗时表、p59 与 p63 的两张结构表、p64–p67 的缓冲构成表、p130–p134 的归约耗时表，正文只写结构与用途与讲者点名的结论（表的分行分列未经人工核对）。不与任何商用方案横比：Nanite（要求把全分辨率网格作为输入）与 UE5.3（把近处一套与远处一套耦合起来）只按讲义原话写，不做优劣评判；页内所有对照都是同一套实现内部的对照（朴素表示与分拆表示、朴素解与更好的估算、三级矩阵优化）。规模口径钉住：本场所有实现与性能数字都是128k 那一档的 CBT，讲者明说可以按应用需要调高或调低，不得把 128k 当成方法的固有上限。范围写死：本篇只做三角化与渲染那一侧，数据生成明确不在范围内（slide 15）。LEB 这个缩写讲义没有展开，正文只照写、不猜全称。命名沿用讲者口径：他把这次改进叫「CBT version 2」或简称 CBT-V2（slide 16），而本场题目用的是 CBTS，正文照讲义各处写，不替他统一命名。篇幅说明：正文按 15,000–20,000 汉字写，事实全部来自幻灯区文字层与讲稿带；slide 1–6 的来路只作定位；slide 13 与 14 里并列的那几场讲座只作参考出处（作品名与场次照页内抄）；slide 158 的仓库地址照写。