8.2 空间划分与 BVH
上一节对每个盒子做一次 AABB-视锥判定，几百个还行，十万个就是十万次判定。这一节把盒子组织成二叉 BVH：先在根节点上一次性排除掉整片看不到的区域，只有可能可见的分支才继续往下走，平均每个盒子的判定次数降到亚线性。
最长轴中位数分割建树
建树用「最长轴中位数分割」：取一批盒子中心点在最长那根轴上的中位数，切成左右两半，递归下去，直到每片只剩 leafSize 个盒子。节点存成扁平数组，内部节点记左右孩子下标，叶节点记「图元在 order[] 里的起点与个数」；遍历时用显式栈，节点 AABB 判为 outside 就整枝剪掉。L1 模块 src/render/culling/bvh.ts（末尾附自打印 demo，node src/render/culling/bvh.ts 可直跑）：
// file: src/render/culling/bvh.ts
// tier: L1
// verify: npx vitest run src/render/culling/bvh.test.ts
//
// helio 渲染卷 8.2：空间划分与 BVH。用「最长轴中位数分割」把一组 AABB 建成扁平的
// 二叉 BVH，再拿视锥去遍历。目标是把 O(N) 的逐盒剔除换成「先扔大块、再查小块」的层次剔除。
import {
aabbInFrustum, extractFrustumPlanes, lookAt, multiply, perspective,
type Aabb, type Frustum, type Vec3,
} from './frustum.ts';
export interface BvhNode {
readonly min: Vec3; readonly max: Vec3;
/** 叶节点：图元在 order[] 里的起点；内部节点：左孩子下标。 */
readonly left: number;
/** 内部节点：右孩子下标；叶节点恒为 0。 */
readonly right: number;
/** > 0 表示叶节点，值为图元个数。 */
readonly count: number;
}
export interface Bvh {
readonly nodes: readonly BvhNode[];
/** 图元下标的置换：叶节点按 left/count 切它。 */
readonly order: readonly number[];
readonly depth: number;
readonly leafCount: number;
}
const INF = Number.POSITIVE_INFINITY;
const centroid = (a: Aabb): Vec3 => [(a.min[0] + a.max[0]) / 2, (a.min[1] + a.max[1]) / 2, (a.min[2] + a.max[2]) / 2];
const union = (a: Aabb, b: Aabb): Aabb => ({
min: [Math.min(a.min[0], b.min[0]), Math.min(a.min[1], b.min[1]), Math.min(a.min[2], b.min[2])],
max: [Math.max(a.max[0], b.max[0]), Math.max(a.max[1], b.max[1]), Math.max(a.max[2], b.max[2])],
});
/** 最长轴中位数分割建树；叶节点最多 leafSize 个图元。 */
export function buildBvh(boxes: readonly Aabb[], leafSize = 4): Bvh {
if (boxes.length === 0) throw new RangeError('boxes 不能为空');
const order = boxes.map((_, i) => i);
const nodes: BvhNode[] = [];
let depth = 0, leafCount = 0;
const build = (start: number, end: number, d: number): number => {
depth = Math.max(depth, d);
let bb: Aabb = { min: [INF, INF, INF], max: [-INF, -INF, -INF] };
let cmin: Vec3 = [INF, INF, INF], cmax: Vec3 = [-INF, -INF, -INF];
for (let i = start; i < end; i++) {
const b = boxes[order[i]!]!;
bb = union(bb, b);
const c = centroid(b);
cmin = [Math.min(cmin[0], c[0]), Math.min(cmin[1], c[1]), Math.min(cmin[2], c[2])];
cmax = [Math.max(cmax[0], c[0]), Math.max(cmax[1], c[1]), Math.max(cmax[2], c[2])];
}
const idx = nodes.length;
nodes.push({ min: bb.min, max: bb.max, left: 0, right: 0, count: 0 });
const n = end - start;
if (n <= leafSize) {
leafCount++;
nodes[idx] = { min: bb.min, max: bb.max, left: start, right: 0, count: n };
return idx;
}
const ex = [cmax[0] - cmin[0], cmax[1] - cmin[1], cmax[2] - cmin[2]];
const axis = ex[0]! >= ex[1]! && ex[0]! >= ex[2]! ? 0 : ex[1]! >= ex[2]! ? 1 : 2;
const slice = order.slice(start, end).sort((a, b) => centroid(boxes[a]!)[axis]! - centroid(boxes[b]!)[axis]!);
for (let k = 0; k < slice.length; k++) order[start + k] = slice[k]!;
const mid = start + (n >> 1);
const left = build(start, mid, d + 1);
const right = build(mid, end, d + 1);
nodes[idx] = { min: bb.min, max: bb.max, left, right, count: 0 };
return idx;
};
build(0, boxes.length, 0);
return { nodes, order, depth, leafCount };
}
export interface CullTrace {
readonly visible: readonly number[];
/** 访问到的节点数（层次剔除的代价）。 */
readonly nodeTests: number;
/** 真正做 AABB 判定的图元数。 */
readonly leafTests: number;
}
/** 用视锥遍历 BVH，收集可见图元下标（升序）。 */
export function bvhCull(bvh: Bvh, boxes: readonly Aabb[], f: Frustum): CullTrace {
const visible: number[] = [];
let nodeTests = 0, leafTests = 0;
const stack: number[] = [0];
while (stack.length > 0) {
const node = bvh.nodes[stack.pop()!]!;
nodeTests++;
if (aabbInFrustum({ min: node.min, max: node.max }, f) === 'outside') continue;
if (node.count > 0) {
for (let k = 0; k < node.count; k++) {
const pi = bvh.order[node.left + k]!;
leafTests++;
if (aabbInFrustum(boxes[pi]!, f) !== 'outside') visible.push(pi);
}
} else stack.push(node.left, node.right);
}
visible.sort((a, b) => a - b);
return { visible, nodeTests, leafTests };
}
/** 逐个 AABB 的暴力剔除，作为 BVH 的正确性基准。 */
export function bruteCull(boxes: readonly Aabb[], f: Frustum): number[] {
const out: number[] = [];
for (let i = 0; i < boxes.length; i++) if (aabbInFrustum(boxes[i]!, f) !== 'outside') out.push(i);
return out;
}
/** 确定性场景：LCG 在以原点为中心、边长为 extent 的立方体里撒 N 个边长为 size 的盒子。 */
export function scatterScene(n: number, extent: number, size: number, seed = 1): Aabb[] {
let s = seed >>> 0;
const next = (): number => ((s = (Math.imul(s, 1664525) + 1013904223) >>> 0) / 4294967296);
const h = size / 2, out: Aabb[] = [];
for (let i = 0; i < n; i++) {
const x = (next() - 0.5) * extent, y = (next() - 0.5) * extent, z = (next() - 0.5) * extent;
out.push({ min: [x - h, y - h, z - h], max: [x + h, y + h, z + h] });
}
return out;
}
// ---- 直接运行时：10 万盒子下比较暴力剔除与 BVH 剔除（Node 26 import.meta.main）----
if ((import.meta as { main?: boolean }).main) {
const N = 100_000, REPEAT = 20;
const vp = multiply(perspective((60 * Math.PI) / 180, 1, 0.1, 120), lookAt([0, 0, 0], [0, 0, -1], [0, 1, 0]));
const f = extractFrustumPlanes(vp);
const scene = scatterScene(N, 2000, 1, 3);
const bvh = buildBvh(scene, 4);
const t = bvhCull(bvh, scene, f);
const brute = bruteCull(scene, f);
const time = (fn: () => void): number => {
fn();
const t0 = performance.now();
for (let i = 0; i < REPEAT; i++) fn();
return (performance.now() - t0) / REPEAT;
};
const bvhMs = time(() => bvhCull(bvh, scene, f)), bruteMs = time(() => bruteCull(scene, f));
console.log(`scene ${N} boxes visible ${t.visible.length}`);
console.log(`bvh nodes ${bvh.nodes.length} leaves ${bvh.leafCount} depth ${bvh.depth}`);
console.log(`tests bvh node ${t.nodeTests} + leaf ${t.leafTests} = ${t.nodeTests + t.leafTests} vs brute ${N}`);
console.log(`brute visible ${brute.length}（与 BVH 一致：${brute.length === t.visible.length}）`);
console.log(`time bvh ${bvhMs.toFixed(3)}ms brute ${bruteMs.toFixed(3)}ms 比值 ${(bruteMs / bvhMs).toFixed(1)}x`);
}
可运行产物：10 万盒子的层次剔除
node src/render/culling/bvh.ts（本机实测，耗时随机器负载浮动）：
scene 100000 boxes visible 10
bvh nodes 65535 leaves 32768 depth 15
tests bvh node 221 + leaf 36 = 257 vs brute 100000
brute visible 10（与 BVH 一致：true）
time bvh 0.026ms brute 2.819ms 比值 109.4x
10 万个盒子、叶容量 4，建出 65535 个节点、32768 个叶、深度 15。视锥只碰了 221 个节点加 36 个图元，共 257 次判定，而暴力做法是 10 万次；两者可见集合完全一致（都是 10 个）。
可运行产物：把两级剔除搬到 GPU
BVH 遍历本身是串行的，但摊平后可以交给 GPU：上传叶节点 AABB 与全部图元 AABB，用两个 compute 通道做两级剔除——先算「叶可见掩码」，再让每个图元在「自身可见」且「所属叶可见」时置位。着色器 shaders/bvh-cull-mask.wgsl：
// file: shaders/bvh-cull-mask.wgsl
// tier: L2
// verify: node tools/run-l2.mjs src/render/culling/bvh-gpu-cull.ts
//
// 8.2 的 L2 验收：把 BVH 的叶节点 AABB 与全部图元 AABB 上传到 GPU，
// 用两级视锥剔除：先算「叶可见掩码」，再让每个图元在「自身 AABB 可见」且
// 「所属叶可见」时才置位。回读掩码与 CPU 的 BVH 遍历逐位比对。
struct Frame { planes: array<vec4<f32>, 6> };
struct Box { min: vec4<f32>, max: vec4<f32> };
@group(0) @binding(0) var<uniform> frame: Frame;
@group(0) @binding(1) var<storage, read> leafBoxes: array<Box>;
@group(0) @binding(2) var<storage, read> primBoxes: array<Box>;
@group(0) @binding(3) var<storage, read> primLeaf: array<u32>;
@group(0) @binding(4) var<storage, read_write> leafMask: array<u32>;
@group(0) @binding(5) var<storage, read_write> primMask: array<u32>;
// p-vertex / n-vertex：与 CPU 侧 aabbInFrustum 同一套判定，只是搬到 GPU。
fn visible(b: Box) -> u32 {
var vis = 1u;
for (var p = 0u; p < 6u; p = p + 1u) {
let pl = frame.planes[p];
let n = pl.xyz;
let pv = select(b.min.xyz, b.max.xyz, n >= vec3<f32>(0.0));
if (dot(n, pv) + pl.w < 0.0) { vis = 0u; }
}
return vis;
}
@compute @workgroup_size(64)
fn leafMain(@builtin(global_invocation_id) gid: vec3<u32>) {
let i = gid.x;
if (i >= arrayLength(&leafBoxes)) { return; }
leafMask[i] = visible(leafBoxes[i]);
}
@compute @workgroup_size(64)
fn primMain(@builtin(global_invocation_id) gid: vec3<u32>) {
let i = gid.x;
if (i >= arrayLength(&primBoxes)) { return; }
let own = visible(primBoxes[i]);
let leaf = leafMask[primLeaf[i]];
primMask[i] = own * leaf;
}
src/render/culling/bvh-gpu-cull.ts（L2）在 CPU 侧建 BVH 并算出基准掩码，上传后与 GPU 逐位比对：
// file: src/render/culling/bvh-gpu-cull.ts
// tier: L2
// verify: node tools/run-l2.mjs src/render/culling/bvh-gpu-cull.ts
//
// 8.2 的 L2 验收：把 CPU 侧建好的 BVH 摊平上传，用 compute 做两级视锥剔除。
// 第一级按叶节点 AABB 算「叶可见掩码」，第二级让每个图元在「自身 AABB 可见」
// 且「所属叶可见」时置位；回读掩码与 CPU 的 bvhCull 逐位比对。
// 需 headless Chromium + 本地 http 服务，命令行不可复现。
import { extractFrustumPlanes, lookAt, multiply, perspective, type Aabb, type Vec3 } from './frustum.ts';
import { buildBvh, bvhCull, scatterScene } from './bvh.ts';
const N = 65536, LEAF = 8, WORKGROUP = 64;
export interface BvhGpuResult {
readonly prims: number; readonly leaves: number;
readonly cpuVisible: number; readonly gpuVisible: number;
readonly maskDiff: number; readonly leafFalseNegatives: number; readonly wgslErrors: number;
}
function packBoxes(boxes: readonly Aabb[]): Float32Array {
const a = new Float32Array(boxes.length * 8);
boxes.forEach((b, i) => a.set([b.min[0], b.min[1], b.min[2], 0, b.max[0], b.max[1], b.max[2], 0], i * 8));
return a;
}
export async function runL2(): Promise<{ checks: { name: string; ok: boolean; detail: string }[]; data: BvhGpuResult }> {
const adapter = await navigator.gpu.requestAdapter();
if (!adapter) throw new Error('拿不到 WebGPU adapter');
const device = await adapter.requestDevice();
const code = await (await fetch('/shaders/bvh-cull-mask.wgsl')).text();
const module = device.createShaderModule({ code });
const info = await module.getCompilationInfo();
const wgslErrors = info.messages.filter((m) => m.type === 'error').length;
// ---- CPU 侧：撒点、建 BVH、抽出叶节点、算出基准可见集 ----
const scene = scatterScene(N, 2000, 1, 11);
const bvh = buildBvh(scene, LEAF);
const vp = multiply(perspective((60 * Math.PI) / 180, 1, 0.1, 120), lookAt([0, 0, 0], [0, 0, -1], [0, 1, 0]));
const f = extractFrustumPlanes(vp);
const expected = new Uint32Array(N);
for (const i of bvhCull(bvh, scene, f).visible) expected[i] = 1;
const leafNodes = bvh.nodes.filter((nd) => nd.count > 0);
const leafBoxes = leafNodes.map((nd) => ({ min: nd.min, max: nd.max } as Aabb));
const primLeaf = new Uint32Array(N);
leafNodes.forEach((nd, li) => { for (let k = 0; k < nd.count; k++) primLeaf[bvh.order[nd.left + k]!] = li; });
// ---- 上传 ----
const mk = (data: Float32Array | Uint32Array, usage: GPUBufferUsageFlags): GPUBuffer => {
const buf = device.createBuffer({ size: Math.max(4, data.byteLength), usage: usage | GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(buf, 0, data);
return buf;
};
const R = GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC;
const leafBoxBuf = mk(packBoxes(leafBoxes), R);
const primBoxBuf = mk(packBoxes(scene), R);
const primLeafBuf = mk(primLeaf, R);
const leafMaskBuf = mk(new Uint32Array(leafNodes.length), R);
const primMaskBuf = mk(new Uint32Array(N), R);
const ubo = device.createBuffer({ size: 96, usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(ubo, 0, new Float32Array(f.flat()));
const bindLayout = device.createBindGroupLayout({ entries: [
{ binding: 0, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'uniform', minBindingSize: 96 } },
{ binding: 1, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'read-only-storage' } },
{ binding: 2, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'read-only-storage' } },
{ binding: 3, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'read-only-storage' } },
{ binding: 4, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'storage' } },
{ binding: 5, visibility: GPUShaderStage.COMPUTE, buffer: { type: 'storage' } },
] });
const pipelineLayout = device.createPipelineLayout({ bindGroupLayouts: [bindLayout] });
const bind = device.createBindGroup({ layout: bindLayout, entries: [
{ binding: 0, resource: { buffer: ubo } },
{ binding: 1, resource: { buffer: leafBoxBuf } },
{ binding: 2, resource: { buffer: primBoxBuf } },
{ binding: 3, resource: { buffer: primLeafBuf } },
{ binding: 4, resource: { buffer: leafMaskBuf } },
{ binding: 5, resource: { buffer: primMaskBuf } },
] });
const mkPipeline = (entryPoint: string) => device.createComputePipeline({ layout: pipelineLayout, compute: { module, entryPoint } });
const enc = device.createCommandEncoder();
for (const [name, count] of [['leafMain', leafNodes.length], ['primMain', N]] as const) {
const pass = enc.beginComputePass();
pass.setPipeline(mkPipeline(name));
pass.setBindGroup(0, bind);
pass.dispatchWorkgroups(Math.ceil(count / WORKGROUP));
pass.end();
}
const read = (src: GPUBuffer, bytes: number): GPUBuffer => {
const rb = device.createBuffer({ size: bytes, usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ });
enc.copyBufferToBuffer(src, 0, rb, 0, bytes);
return rb;
};
const leafRb = read(leafMaskBuf, leafNodes.length * 4);
const primRb = read(primMaskBuf, N * 4);
device.queue.submit([enc.finish()]);
await Promise.all([leafRb.mapAsync(GPUMapMode.READ), primRb.mapAsync(GPUMapMode.READ)]);
const leafMask = new Uint32Array(leafRb.getMappedRange().slice(0));
const primMask = new Uint32Array(primRb.getMappedRange().slice(0));
leafRb.unmap(); primRb.unmap();
let maskDiff = 0, gpuVisible = 0, leafFalseNegatives = 0;
for (let i = 0; i < N; i++) {
if (primMask[i] !== expected[i]) maskDiff++;
if (primMask[i]! === 1) gpuVisible++;
if (primMask[i]! === 1 && leafMask[primLeaf[i]!]! === 0) leafFalseNegatives++;
}
device.destroy();
const data: BvhGpuResult = {
prims: N, leaves: leafNodes.length,
cpuVisible: expected.reduce((s, v) => s + v, 0), gpuVisible,
maskDiff, leafFalseNegatives, wgslErrors,
};
const checks = [
{ name: 'wgsl.0error', ok: wgslErrors === 0, detail: `errors=${wgslErrors}` },
{ name: 'gpu.mask==cpu', ok: maskDiff === 0, detail: `diff=${maskDiff}` },
{ name: 'gpu.visible==cpu', ok: gpuVisible === data.cpuVisible, detail: `${gpuVisible} vs ${data.cpuVisible}` },
{ name: 'leaf.no.false.negative', ok: leafFalseNegatives === 0, detail: `bad=${leafFalseNegatives}` },
];
return { checks, data };
}
node tools/run-l2.mjs src/render/culling/bvh-gpu-cull.ts（本机实测）：
PASS wgsl.0error errors=0
PASS gpu.mask==cpu diff=0
PASS gpu.visible==cpu 10 vs 10
PASS leaf.no.false.negative bad=0
65536 个图元、叶容量 8，建出 8192 个叶节点。GPU 的两级剔除结果与 CPU 的 bvhCull 逐位一致（diff=0），可见数都是 10，且没有任何图元出现「自身可见却所属叶不可见」的矛盾（bad=0）。
小结
BVH 把逐盒的线性扫描换成「先扔大块」的层次扫描：本机 10 万盒子里只做了 257 次判定。这一节建的树、算的叶掩码，下一节直接拿来当 GPU 驱动的输入——连 CPU 侧的剔除调用都省掉，让 GPU 自己决定画谁、画哪一档 LOD。
阅读导航：上一节：8.1 视锥剔除与包围体 · 下一节：8.3 GPU 驱动剔除与 LOD 协同 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。