排序模块架构

GPURSSorter 实现了一个四阶段的 GPU 基数排序 (Radix Sort)，完全在 GPU 上对深度键 (depth keys) 和负载索引 (payload indices) 进行重新排序。本文档重点介绍 TypeScript 包装器、缓冲布局和 WGSL 着色器如何在多模型渲染路径中协同工作。

高层管线

preprocess.wgsl  -- 写入 深度键 + 负载索引 + 计数器 --> sorter_bg_pre
radix sort pass 0 -- zero_histograms      (间接或固定调度)
radix sort pass 1 -- calculate_histogram
radix sort pass 2 -- prefix_histogram
radix sort pass 3 -- scatter_even 和 scatter_odd (乒乓缓冲)
renderer          -- 通过 sorter_render_bg 读取 payload_a -> 间接绘制

每个 GPUDevice 只需要一个排序器实例。渲染器为每个点云（或每个全局缓冲）缓存一个 PointCloudSortStuff，以便可以在帧之间重用缓冲。

绑定组布局

GPURSSorter 创建三种布局：

1. 排序管线布局 (私有): 包含六个存储缓冲的绑定组
   • binding 0: sorter_uni (GeneralInfo)
   • binding 1: internal_mem (直方图 + 分区)
   • bindings 2/3: key_a / key_b
   • bindings 4/5: payload_a / payload_b
2. 渲染布局 (createRenderBindGroupLayout)
   • binding 0: sorter_uni (只读)
   • binding 4: payload_a (保存最终顺序的缓冲) 渲染器在绘制 Pass 中将其绑定为 @group(1)。
3. 预处理布局 (createPreprocessBindGroupLayout)
   • binding 0: sorter_uni
   • binding 1: key_a
   • binding 2: payload_a
   • binding 3: sorter_dis (间接调度缓冲) 预处理将其绑定为 @group(2)，以便直接写入键、负载和原子计数器。

缓冲布局

名称	描述
key_a, key_b	乒乓键缓冲 (32位浮点数重新解释为 u32)。Scatter Pass 在每个基数 Pass 中交替读写。
payload_a, payload_b	乒乓负载缓冲。payload_a 成为渲染器绑定的最终排序索引缓冲。
internal_mem	包含所有 Pass 的直方图、共享内存分区和工作组回溯 (lookback) 数据的暂存缓冲。大小随填充后的键数量增长。
sorter_uni	GeneralInfo 结构体 (5 x u32) 打包为 { keys_size, padded_size, passes, even_pass, odd_pass }。预处理每帧更新 keys_size。
sorter_dis	IndirectDispatch 结构体 (dispatch_x, dispatch_y, dispatch_z)。预处理存储所需的直方图/Scatter 工作组数量，以便排序器可以使用 dispatchWorkgroupsIndirect。

填充 (Padding)

键被填充至 keys_per_workgroup = HISTOGRAM_WG_SIZE * RS_HISTOGRAM_BLOCK_ROWS = 256 * 15 = 3840 的倍数。createKeyvalBuffers 在分配缓冲时将请求的点数向上取整到此倍数，且 GeneralInfo.padded_size 存储填充后的值。当可见 Splat 较少时，预处理负责将额外的槽位填充为零。

计算通道 (Compute passes)

1. zero_histograms

• 工作组大小: 256
• 清除 internal_mem 中的直方图和分区元数据。
• 当使用间接模式时，调度计数从 sorter_dis.dispatch_x 读取（这是预处理在发射 Splat 时设置的）。

2. calculate_histogram

• 工作组大小: 256，每线程 15 行，每工作组 3840 个键。
• 每个线程加载多个深度键，提取所有四个基数 Pass 的数字位 (digit)，在共享内存中累积计数，然后原子地加到全局直方图中。
• histogram_sg_size 和 rs_histogram_block_rows 等常量由 processShaderTemplate 注入，因此 WGSL 和 TypeScript 推导出的内存大小一致。

3. prefix_histogram

• 工作组大小: 128。
• 对共享内存中的每 256 个条目的直方图执行独占扫描 (exclusive scan)（上扫 + 下扫）。
• 结果写回 internal_mem 的直方图部分，以便 Scatter Pass 可以查找每个数字位/每个 Pass 的全局偏移量。

4. scatter_even 和 scatter_odd

• 工作组大小: 256。
• scatter_even 处理 Pass 0 和 2（从 key_a 读，写到 key_b），scatter_odd 处理 Pass 1 和 3（从 key_b 读，写到 key_a）。同样的逻辑适用于负载缓冲。
• 每个线程计算其数字位的局部排名 (local rank)，加上直方图前缀和中的全局偏移，并将键/负载写入计算出的目标索引。
• 在第四个 Pass 结束时，key_a 和 payload_a 包含最终的排序顺序。

间接调度 vs 固定调度

• recordSort (固定) 使用从 numPoints 派生的显式工作组计数调用 zero -> histogram -> prefix -> scatter。
• recordSortIndirect 使用 sorter_dis 中存储的计数和 dispatchWorkgroupsIndirect 构建每个计算 Pass。这是渲染器使用的路径，因为预处理每帧计算实际可见的 Splat 数量。
• recordResetIndirectBuffer 将 dispatch_x 和 keys_size 重置为零，以便预处理可以原子地增加它们。

与预处理集成

预处理绑定 sorter_bg_pre 并执行三个关键任务：

1. 将深度键（打包的浮点数）写入 key_a，并将负载索引写入 payload_a，偏移量与其写入 2D Splat 的位置相同。
2. 使用 sorter_uni.keys_size 上的原子操作来跟踪可见 Splat 的数量，并使用 sorter_dis.dispatch_x 上的原子操作来跟踪需要多少个直方图工作组（每 256 * 15 个 Splat 增加一次）。
3. 将任何未使用的槽位填充零直到 padded_size，以保持 Scatter Pass 在边界内。

预处理完成后，渲染器使用相同的 PointCloudSortStuff 调用 recordSortIndirect。不需要 CPU 回读，因为键计数和调度计数已经存在于 sorter_uni 和 sorter_dis 中。

与渲染器集成

• PointCloudSortStuff.sorter_render_bg 在渲染管线的 @group(1) 处绑定，提供 sorter_uni（用于实例计数）和 payload_a（排序后的索引）。
• 排序后，渲染器将 sorter_uni.keys_size 复制到绘制间接缓冲 (draw indirect buffer)，以便 Splat 管线知道要绘制多少个实例。
• 在多模型路径中，单个 recordSortIndirect 和单个绘制调用覆盖每个模型，因为预处理将每个模型写入全局 Splat 缓冲和负载缓冲的唯一范围内。

初始化和验证

GPURSSorter.create(device, queue) 是异步的，因为它：

1. 遍历候选子组大小 (16, 32, 16, 8, 1) 并为每次试验构建管线。
2. 调用 testSort（排序 8192 个浮点数）以确保所选配置在当前适配器上工作。
3. 仅当配置成功时才返回排序器实例；否则抛出异常。

调试提示

• 预处理后验证 sorter_uni.keys_size，以确认原子计数器与预期的可见 Splat 计数匹配。
• 在调用 recordSortIndirect 之前，确保 dispatch_x 等于 ceil(keys_size / (256 * 15))。
• 请记住，经过四个 Pass 后，排序数据驻留在 payload_a 中。如果渲染器看到陈旧的结果，通常意味着缺少乒乓交换 (ping pong flip) 或预处理写入了错误的缓冲。