第12章：空间索引与加速结构
12.1 空间划分
12.1.1 空间划分的目的
在处理大量空间数据时（如碰撞检测、射线追踪），暴力方法的时间复杂度通常是 O(n²) 或 O(n)，难以满足实时性要求。空间划分通过组织空间数据，将复杂度降低到 O(log n) 或更好。
空间划分的应用
1. 碰撞检测
- 快速找到可能碰撞的物体对
- 避免 O(n²) 的两两检测
2. 射线追踪
- 快速找到射线经过的物体
- 加速光线与场景的求交
3. 视锥剔除
- 快速剔除不可见物体
- 减少渲染负担
4. 邻近查询
- 查找某点附近的物体
- K 近邻搜索
无空间划分： 有空间划分：
n 个物体 n 个物体
↓ ↓
O(n²) 检测 O(n log n) 构建
↓ ↓
很慢 O(log n) 查询
↓
非常快12.1.2 空间划分类型
空间划分的分类
┌─────────────────────────────────────────────────────────┐
│ 空间划分结构 │
├─────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ 均匀网格 │ │ 层次结构 │ │
│ │ (Uniform Grid) │ │ │ │
│ └──────────────────┘ └──────────────────┘ │
│ │ │
│ ┌───────────────┼───────────────┐ │
│ │ │ │ │
│ ┌─────┴─────┐ ┌─────┴─────┐ ┌─────┴────┐
│ │ 空间划分 │ │ 对象划分 │ │混合 │
│ └───────────┘ └───────────┘ └──────────┘
│ │ │ │
│ ┌─────┴─────┐ ┌─────┴─────┐ ┌─────┴────┐
│ │四叉树 │ │ BVH │ │KD-Tree │
│ │八叉树 │ │ │ │ │
│ │BSP │ │ │ │ │
│ └───────────┘ └───────────┘ └──────────┘
│ │
└─────────────────────────────────────────────────────────┘
空间划分 vs 对象划分：
空间划分： 对象划分：
先划分空间， 先划分对象，
再将对象放入 再计算空间
┌───┬───┐ ┌─────────────┐
│ ● │ │ │ ┌───┐ │
├───┼───┤ │ │●●●│ │
│ │●● │ │ └───┘ │
└───┴───┘ └─────────────┘
物体可能跨多个格子 每个物体属于唯一节点12.2 四叉树
12.2.1 四叉树原理
四叉树（Quadtree）
将 2D 空间递归地分成 4 个象限。
根节点
┌────────┬────────┐
│ NW │ NE │
│ │ │
├────────┼────────┤
│ SW │ SE │
│ │ │
└────────┴────────┘
递归细分：
Level 0: Level 1: Level 2:
┌────────────────┐ ┌────┬────┐ ┌──┬──┬────┐
│ │ │ │ │ │ │ │ │
│ │ → │ │ │ → ├──┼──┤ │
│ │ ├────┼────┤ │ │ │ │
│ │ │ │ │ ├──┴──┼────┤
└────────────────┘ └────┴────┘ │ │ │
└────┴────┘
只在有多个对象的区域继续细分
终止条件：
1. 节点内对象数 ≤ 阈值
2. 达到最大深度
3. 区域面积太小12.2.2 四叉树实现
javascript
/**
* 四叉树节点
*/
class QuadTreeNode {
constructor(bounds, depth = 0, maxDepth = 8, maxObjects = 10) {
this.bounds = bounds; // { x, y, width, height }
this.depth = depth;
this.maxDepth = maxDepth;
this.maxObjects = maxObjects;
this.objects = []; // 存储的对象
this.children = null; // 四个子节点 [NW, NE, SW, SE]
}
/**
* 细分节点
*/
subdivide() {
const { x, y, width, height } = this.bounds;
const halfW = width / 2;
const halfH = height / 2;
this.children = [
// NW
new QuadTreeNode(
{ x: x, y: y, width: halfW, height: halfH },
this.depth + 1, this.maxDepth, this.maxObjects
),
// NE
new QuadTreeNode(
{ x: x + halfW, y: y, width: halfW, height: halfH },
this.depth + 1, this.maxDepth, this.maxObjects
),
// SW
new QuadTreeNode(
{ x: x, y: y + halfH, width: halfW, height: halfH },
this.depth + 1, this.maxDepth, this.maxObjects
),
// SE
new QuadTreeNode(
{ x: x + halfW, y: y + halfH, width: halfW, height: halfH },
this.depth + 1, this.maxDepth, this.maxObjects
)
];
// 重新分配现有对象
for (const obj of this.objects) {
this.insertIntoChildren(obj);
}
this.objects = [];
}
/**
* 将对象插入合适的子节点
*/
insertIntoChildren(obj) {
for (const child of this.children) {
if (this.objectFitsInBounds(obj, child.bounds)) {
child.insert(obj);
return;
}
}
// 对象跨越边界，保留在当前节点
this.objects.push(obj);
}
/**
* 检查对象是否完全在边界内
*/
objectFitsInBounds(obj, bounds) {
return obj.x >= bounds.x &&
obj.y >= bounds.y &&
obj.x + obj.width <= bounds.x + bounds.width &&
obj.y + obj.height <= bounds.y + bounds.height;
}
/**
* 检查对象是否与边界相交
*/
objectIntersectsBounds(obj, bounds) {
return obj.x < bounds.x + bounds.width &&
obj.x + obj.width > bounds.x &&
obj.y < bounds.y + bounds.height &&
obj.y + obj.height > bounds.y;
}
/**
* 插入对象
*/
insert(obj) {
// 如果有子节点，尝试插入子节点
if (this.children) {
this.insertIntoChildren(obj);
return;
}
// 添加到当前节点
this.objects.push(obj);
// 检查是否需要细分
if (this.objects.length > this.maxObjects && this.depth < this.maxDepth) {
this.subdivide();
}
}
/**
* 查询与给定区域相交的所有对象
*/
query(range, result = []) {
// 检查范围是否与节点相交
if (!this.objectIntersectsBounds(range, this.bounds)) {
return result;
}
// 添加当前节点的对象
for (const obj of this.objects) {
if (this.objectIntersectsBounds(obj, range)) {
result.push(obj);
}
}
// 递归查询子节点
if (this.children) {
for (const child of this.children) {
child.query(range, result);
}
}
return result;
}
/**
* 查询与点最近的对象
*/
queryPoint(x, y, result = []) {
if (x < this.bounds.x || x >= this.bounds.x + this.bounds.width ||
y < this.bounds.y || y >= this.bounds.y + this.bounds.height) {
return result;
}
// 添加当前节点的对象
for (const obj of this.objects) {
if (x >= obj.x && x < obj.x + obj.width &&
y >= obj.y && y < obj.y + obj.height) {
result.push(obj);
}
}
// 递归查询子节点
if (this.children) {
for (const child of this.children) {
child.queryPoint(x, y, result);
}
}
return result;
}
/**
* 移除对象
*/
remove(obj) {
const index = this.objects.indexOf(obj);
if (index !== -1) {
this.objects.splice(index, 1);
return true;
}
if (this.children) {
for (const child of this.children) {
if (child.remove(obj)) return true;
}
}
return false;
}
/**
* 清空树
*/
clear() {
this.objects = [];
if (this.children) {
for (const child of this.children) {
child.clear();
}
this.children = null;
}
}
}
/**
* 四叉树封装类
*/
class QuadTree {
constructor(bounds, maxDepth = 8, maxObjects = 10) {
this.root = new QuadTreeNode(bounds, 0, maxDepth, maxObjects);
}
insert(obj) {
this.root.insert(obj);
}
query(range) {
return this.root.query(range);
}
queryPoint(x, y) {
return this.root.queryPoint(x, y);
}
remove(obj) {
return this.root.remove(obj);
}
clear() {
this.root.clear();
}
}12.3 八叉树
12.3.1 八叉树原理
八叉树（Octree）
将 3D 空间递归地分成 8 个卦限。
根节点
┌────────────────┐
╱ ╱ ╱│
╱ ╱──────────────╱ │
╱ ╱ ╱ │
┌─╱──────────────┐ │
│╱ │ │ │
│ 0 │ 1 │ │
│───────┼────────│ ╱
│ 2 │ 3 │ ╱
└───────┴────────┘╱
正面 4 个（0-3），背面 4 个（4-7）
应用场景：
- 3D 碰撞检测
- 体素渲染
- 点云处理
- 稀疏体积数据12.3.2 八叉树实现
javascript
/**
* 八叉树节点
*/
class OctreeNode {
constructor(bounds, depth = 0, maxDepth = 8, maxObjects = 8) {
this.bounds = bounds; // { x, y, z, size }
this.depth = depth;
this.maxDepth = maxDepth;
this.maxObjects = maxObjects;
this.objects = [];
this.children = null; // 8 个子节点
}
/**
* 细分节点
*/
subdivide() {
const { x, y, z, size } = this.bounds;
const half = size / 2;
this.children = [];
for (let dz = 0; dz < 2; dz++) {
for (let dy = 0; dy < 2; dy++) {
for (let dx = 0; dx < 2; dx++) {
this.children.push(new OctreeNode(
{
x: x + dx * half,
y: y + dy * half,
z: z + dz * half,
size: half
},
this.depth + 1,
this.maxDepth,
this.maxObjects
));
}
}
}
// 重新分配对象
const oldObjects = this.objects;
this.objects = [];
for (const obj of oldObjects) {
this.insertIntoChildren(obj);
}
}
/**
* 获取包含点的子节点索引
*/
getChildIndex(point) {
const { x, y, z, size } = this.bounds;
const half = size / 2;
let index = 0;
if (point.x >= x + half) index |= 1;
if (point.y >= y + half) index |= 2;
if (point.z >= z + half) index |= 4;
return index;
}
/**
* 检查对象是否完全在边界内
*/
containsObject(obj) {
const { x, y, z, size } = this.bounds;
const objBounds = obj.getBounds();
return objBounds.min.x >= x && objBounds.max.x <= x + size &&
objBounds.min.y >= y && objBounds.max.y <= y + size &&
objBounds.min.z >= z && objBounds.max.z <= z + size;
}
/**
* 检查边界是否相交
*/
intersectsBounds(bounds) {
const { x, y, z, size } = this.bounds;
return bounds.max.x >= x && bounds.min.x <= x + size &&
bounds.max.y >= y && bounds.min.y <= y + size &&
bounds.max.z >= z && bounds.min.z <= z + size;
}
insertIntoChildren(obj) {
const objBounds = obj.getBounds();
for (const child of this.children) {
if (child.containsObject(obj)) {
child.insert(obj);
return;
}
}
// 对象跨越边界
this.objects.push(obj);
}
insert(obj) {
if (this.children) {
this.insertIntoChildren(obj);
return;
}
this.objects.push(obj);
if (this.objects.length > this.maxObjects && this.depth < this.maxDepth) {
this.subdivide();
}
}
/**
* 查询与边界相交的对象
*/
query(bounds, result = []) {
if (!this.intersectsBounds(bounds)) {
return result;
}
for (const obj of this.objects) {
const objBounds = obj.getBounds();
if (this.boundsIntersect(objBounds, bounds)) {
result.push(obj);
}
}
if (this.children) {
for (const child of this.children) {
child.query(bounds, result);
}
}
return result;
}
boundsIntersect(a, b) {
return a.max.x >= b.min.x && a.min.x <= b.max.x &&
a.max.y >= b.min.y && a.min.y <= b.max.y &&
a.max.z >= b.min.z && a.min.z <= b.max.z;
}
/**
* 射线查询
*/
raycast(origin, direction, result = []) {
// 射线与节点边界相交测试
if (!this.rayIntersectsBounds(origin, direction)) {
return result;
}
for (const obj of this.objects) {
result.push(obj);
}
if (this.children) {
// 按距离排序子节点（可选优化）
for (const child of this.children) {
child.raycast(origin, direction, result);
}
}
return result;
}
rayIntersectsBounds(origin, direction) {
const { x, y, z, size } = this.bounds;
const min = { x, y, z };
const max = { x: x + size, y: y + size, z: z + size };
let tmin = -Infinity;
let tmax = Infinity;
for (const axis of ['x', 'y', 'z']) {
if (Math.abs(direction[axis]) < 1e-10) {
if (origin[axis] < min[axis] || origin[axis] > max[axis]) {
return false;
}
} else {
let t1 = (min[axis] - origin[axis]) / direction[axis];
let t2 = (max[axis] - origin[axis]) / direction[axis];
if (t1 > t2) [t1, t2] = [t2, t1];
tmin = Math.max(tmin, t1);
tmax = Math.min(tmax, t2);
if (tmin > tmax) return false;
}
}
return true;
}
}12.4 KD 树
12.4.1 KD 树原理
KD 树（K-Dimensional Tree）
按维度交替划分空间的二叉搜索树。
2D KD 树示例：
原始点集： 按 X 划分： 再按 Y 划分：
● ● │ │
│ ● ● │ ●──●
● ● → │ → │
│ ● ● ──┼─●──│──●
● │ │ │
│ ● │ ● │
KD 树结构：
(按X分)
│
┌─────┴─────┐
│ │
(按Y分) (按Y分)
│ │
┌─┴─┐ ┌─┴─┐
│ │ │ │
优点：
- 对点数据非常高效
- K 近邻查询
- 范围查询
缺点：
- 不适合频繁更新
- 高维度效率下降12.4.2 KD 树实现
javascript
/**
* KD 树节点
*/
class KDTreeNode {
constructor(point, axis, left = null, right = null) {
this.point = point; // 分割点
this.axis = axis; // 分割轴 (0, 1, 2 代表 x, y, z)
this.left = left;
this.right = right;
}
}
/**
* KD 树
*/
class KDTree {
constructor(k = 2) {
this.k = k; // 维度
this.root = null;
}
/**
* 从点集构建 KD 树
*/
build(points) {
this.root = this.buildRecursive(points, 0);
return this;
}
buildRecursive(points, depth) {
if (points.length === 0) return null;
const axis = depth % this.k;
// 按当前轴排序
points.sort((a, b) => this.getAxisValue(a, axis) - this.getAxisValue(b, axis));
// 选择中位数作为分割点
const median = Math.floor(points.length / 2);
return new KDTreeNode(
points[median],
axis,
this.buildRecursive(points.slice(0, median), depth + 1),
this.buildRecursive(points.slice(median + 1), depth + 1)
);
}
getAxisValue(point, axis) {
if (axis === 0) return point.x;
if (axis === 1) return point.y;
if (axis === 2) return point.z;
return 0;
}
/**
* 最近邻查询
*/
nearestNeighbor(queryPoint) {
let best = { point: null, distSq: Infinity };
this.nearestNeighborRecursive(this.root, queryPoint, best);
return best.point;
}
nearestNeighborRecursive(node, queryPoint, best) {
if (!node) return;
// 计算到当前点的距离
const distSq = this.distanceSquared(queryPoint, node.point);
if (distSq < best.distSq) {
best.point = node.point;
best.distSq = distSq;
}
// 决定先访问哪个子树
const axis = node.axis;
const queryValue = this.getAxisValue(queryPoint, axis);
const nodeValue = this.getAxisValue(node.point, axis);
const diff = queryValue - nodeValue;
const first = diff < 0 ? node.left : node.right;
const second = diff < 0 ? node.right : node.left;
// 递归搜索近侧子树
this.nearestNeighborRecursive(first, queryPoint, best);
// 检查是否需要搜索远侧子树
if (diff * diff < best.distSq) {
this.nearestNeighborRecursive(second, queryPoint, best);
}
}
/**
* K 近邻查询
*/
kNearestNeighbors(queryPoint, k) {
const heap = new MaxHeap(k);
this.kNNRecursive(this.root, queryPoint, heap, k);
return heap.getAll();
}
kNNRecursive(node, queryPoint, heap, k) {
if (!node) return;
const distSq = this.distanceSquared(queryPoint, node.point);
heap.insert({ point: node.point, distSq });
const axis = node.axis;
const queryValue = this.getAxisValue(queryPoint, axis);
const nodeValue = this.getAxisValue(node.point, axis);
const diff = queryValue - nodeValue;
const first = diff < 0 ? node.left : node.right;
const second = diff < 0 ? node.right : node.left;
this.kNNRecursive(first, queryPoint, heap, k);
// 如果堆未满或者可能有更近的点
if (heap.size() < k || diff * diff < heap.peek().distSq) {
this.kNNRecursive(second, queryPoint, heap, k);
}
}
/**
* 范围查询
*/
rangeQuery(min, max) {
const result = [];
this.rangeQueryRecursive(this.root, min, max, result);
return result;
}
rangeQueryRecursive(node, min, max, result) {
if (!node) return;
// 检查当前点是否在范围内
if (this.pointInRange(node.point, min, max)) {
result.push(node.point);
}
const axis = node.axis;
const nodeValue = this.getAxisValue(node.point, axis);
const minValue = this.getAxisValue(min, axis);
const maxValue = this.getAxisValue(max, axis);
// 检查左子树
if (minValue <= nodeValue) {
this.rangeQueryRecursive(node.left, min, max, result);
}
// 检查右子树
if (maxValue >= nodeValue) {
this.rangeQueryRecursive(node.right, min, max, result);
}
}
pointInRange(point, min, max) {
return point.x >= min.x && point.x <= max.x &&
point.y >= min.y && point.y <= max.y &&
(this.k < 3 || (point.z >= min.z && point.z <= max.z));
}
distanceSquared(a, b) {
const dx = a.x - b.x;
const dy = a.y - b.y;
const dz = (a.z || 0) - (b.z || 0);
return dx * dx + dy * dy + (this.k > 2 ? dz * dz : 0);
}
}
/**
* 最大堆（用于 K 近邻）
*/
class MaxHeap {
constructor(maxSize) {
this.maxSize = maxSize;
this.heap = [];
}
insert(item) {
if (this.heap.length < this.maxSize) {
this.heap.push(item);
this.bubbleUp(this.heap.length - 1);
} else if (item.distSq < this.heap[0].distSq) {
this.heap[0] = item;
this.bubbleDown(0);
}
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
getAll() {
return this.heap.map(item => item.point);
}
bubbleUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.heap[index].distSq <= this.heap[parent].distSq) break;
[this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
index = parent;
}
}
bubbleDown(index) {
while (true) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let largest = index;
if (left < this.heap.length && this.heap[left].distSq > this.heap[largest].distSq) {
largest = left;
}
if (right < this.heap.length && this.heap[right].distSq > this.heap[largest].distSq) {
largest = right;
}
if (largest === index) break;
[this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
index = largest;
}
}
}12.5 BVH
12.5.1 BVH 原理
BVH（Bounding Volume Hierarchy，包围体层次结构）
将对象组织成层次结构，每个节点有一个包含所有子节点的包围体。
根节点
┌────────────────┐
│ 大包围盒 │
│ ┌───┐ ┌───┐ │
│ │ │ │ │ │
│ └───┘ └───┘ │
└────────────────┘
│
┌─────┴─────┐
│ │
┌───────┐ ┌───────┐
│ 左子树 │ │ 右子树 │
│ ┌───┐ │ │ ┌───┐ │
│ │ │ │ │ │ │ │
│ └───┘ │ │ └───┘ │
└───────┘ └───────┘
BVH vs 空间划分：
空间划分（四叉树）： BVH：
┌───┬───┐ ┌─────────────┐
│ ● │ │ 物体可能 │ ┌───┐ │
├───┼───┤ 跨多个格子 │ │●●●│ │
│ │●● │ │ └───┘ │
└───┴───┘ └─────────────┘
每个物体只属于一个节点
优点：
- 对象不会被分割
- 更新相对容易
- 适合动态场景
缺点：
- 包围体可能重叠
- 构建质量影响性能12.5.2 BVH 实现
javascript
/**
* BVH 节点
*/
class BVHNode {
constructor() {
this.bounds = null; // AABB
this.left = null;
this.right = null;
this.object = null; // 叶节点存储对象
}
isLeaf() {
return this.object !== null;
}
}
/**
* BVH 树
*/
class BVH {
constructor() {
this.root = null;
}
/**
* 从对象列表构建 BVH
*/
build(objects) {
if (objects.length === 0) {
this.root = null;
return;
}
this.root = this.buildRecursive(objects);
}
buildRecursive(objects) {
const node = new BVHNode();
// 叶节点
if (objects.length === 1) {
node.object = objects[0];
node.bounds = objects[0].getBounds();
return node;
}
// 计算所有对象的包围盒
node.bounds = this.computeBounds(objects);
// 选择分割轴（最长轴）
const size = {
x: node.bounds.max.x - node.bounds.min.x,
y: node.bounds.max.y - node.bounds.min.y,
z: node.bounds.max.z - node.bounds.min.z
};
let axis = 'x';
if (size.y > size.x && size.y > size.z) axis = 'y';
if (size.z > size.x && size.z > size.y) axis = 'z';
// 按中心点排序
objects.sort((a, b) => {
const boundsA = a.getBounds();
const boundsB = b.getBounds();
const centerA = (boundsA.min[axis] + boundsA.max[axis]) / 2;
const centerB = (boundsB.min[axis] + boundsB.max[axis]) / 2;
return centerA - centerB;
});
// 分割
const mid = Math.floor(objects.length / 2);
node.left = this.buildRecursive(objects.slice(0, mid));
node.right = this.buildRecursive(objects.slice(mid));
return node;
}
/**
* 使用 SAH（Surface Area Heuristic）构建
*/
buildSAH(objects) {
if (objects.length === 0) {
this.root = null;
return;
}
this.root = this.buildSAHRecursive(objects);
}
buildSAHRecursive(objects) {
const node = new BVHNode();
if (objects.length === 1) {
node.object = objects[0];
node.bounds = objects[0].getBounds();
return node;
}
node.bounds = this.computeBounds(objects);
// SAH：尝试所有分割位置，选择代价最小的
let bestCost = Infinity;
let bestAxis = 'x';
let bestSplit = 0;
for (const axis of ['x', 'y', 'z']) {
// 按轴排序
objects.sort((a, b) => {
const boundsA = a.getBounds();
const boundsB = b.getBounds();
return boundsA.min[axis] - boundsB.min[axis];
});
// 尝试不同分割位置
for (let i = 1; i < objects.length; i++) {
const leftObjects = objects.slice(0, i);
const rightObjects = objects.slice(i);
const leftBounds = this.computeBounds(leftObjects);
const rightBounds = this.computeBounds(rightObjects);
const leftArea = this.surfaceArea(leftBounds);
const rightArea = this.surfaceArea(rightBounds);
const parentArea = this.surfaceArea(node.bounds);
// SAH 代价
const cost = 1 + (leftArea / parentArea) * leftObjects.length +
(rightArea / parentArea) * rightObjects.length;
if (cost < bestCost) {
bestCost = cost;
bestAxis = axis;
bestSplit = i;
}
}
}
// 使用最佳分割
objects.sort((a, b) => {
const boundsA = a.getBounds();
const boundsB = b.getBounds();
return boundsA.min[bestAxis] - boundsB.min[bestAxis];
});
node.left = this.buildSAHRecursive(objects.slice(0, bestSplit));
node.right = this.buildSAHRecursive(objects.slice(bestSplit));
return node;
}
computeBounds(objects) {
const min = { x: Infinity, y: Infinity, z: Infinity };
const max = { x: -Infinity, y: -Infinity, z: -Infinity };
for (const obj of objects) {
const bounds = obj.getBounds();
min.x = Math.min(min.x, bounds.min.x);
min.y = Math.min(min.y, bounds.min.y);
min.z = Math.min(min.z, bounds.min.z);
max.x = Math.max(max.x, bounds.max.x);
max.y = Math.max(max.y, bounds.max.y);
max.z = Math.max(max.z, bounds.max.z);
}
return { min, max };
}
surfaceArea(bounds) {
const dx = bounds.max.x - bounds.min.x;
const dy = bounds.max.y - bounds.min.y;
const dz = bounds.max.z - bounds.min.z;
return 2 * (dx * dy + dy * dz + dz * dx);
}
/**
* 射线查询
*/
raycast(origin, direction) {
const results = [];
this.raycastRecursive(this.root, origin, direction, results);
return results;
}
raycastRecursive(node, origin, direction, results) {
if (!node) return;
// 射线与包围盒相交测试
if (!this.rayIntersectsAABB(origin, direction, node.bounds)) {
return;
}
if (node.isLeaf()) {
// 叶节点：精确测试对象
const t = node.object.raycast(origin, direction);
if (t !== null) {
results.push({ object: node.object, t });
}
} else {
// 递归测试子节点
this.raycastRecursive(node.left, origin, direction, results);
this.raycastRecursive(node.right, origin, direction, results);
}
}
rayIntersectsAABB(origin, direction, bounds) {
let tmin = -Infinity;
let tmax = Infinity;
for (const axis of ['x', 'y', 'z']) {
if (Math.abs(direction[axis]) < 1e-10) {
if (origin[axis] < bounds.min[axis] || origin[axis] > bounds.max[axis]) {
return false;
}
} else {
let t1 = (bounds.min[axis] - origin[axis]) / direction[axis];
let t2 = (bounds.max[axis] - origin[axis]) / direction[axis];
if (t1 > t2) [t1, t2] = [t2, t1];
tmin = Math.max(tmin, t1);
tmax = Math.min(tmax, t2);
if (tmin > tmax) return false;
}
}
return tmax >= 0;
}
/**
* 查询与边界相交的对象
*/
query(bounds) {
const results = [];
this.queryRecursive(this.root, bounds, results);
return results;
}
queryRecursive(node, bounds, results) {
if (!node) return;
if (!this.boundsIntersect(node.bounds, bounds)) {
return;
}
if (node.isLeaf()) {
if (this.boundsIntersect(node.object.getBounds(), bounds)) {
results.push(node.object);
}
} else {
this.queryRecursive(node.left, bounds, results);
this.queryRecursive(node.right, bounds, results);
}
}
boundsIntersect(a, b) {
return a.max.x >= b.min.x && a.min.x <= b.max.x &&
a.max.y >= b.min.y && a.min.y <= b.max.y &&
a.max.z >= b.min.z && a.min.z <= b.max.z;
}
}12.6 R 树
12.6.1 R 树简介
R 树（R-Tree）
专门为空间数据设计的平衡树结构，常用于数据库和 GIS。
特点：
- B 树的空间扩展
- 自动平衡
- 支持动态插入删除
- 保证最差情况性能
R 树结构：
根节点
┌────────────────┐
│ R1 ────────────│──┐
│ │ │
│ R2 ─────────│──┼──┐
└────────────────┘ │ │
│ │ │
┌─────┴─────┐ │ │
│ │ │ │
┌───────┐ ┌───────┐ │ │
│ R1 │ │ R2 │ │ │
│ ┌──┐ │ │ ┌──┐ │ │ │
│ │a │ │ │ │c │ │◄─┘ │
│ │b │ │ │ │d │ │ │
│ └──┘ │ │ └──┘ │◄────┘
└───────┘ └───────┘
与 BVH 的区别：
- R 树是平衡的，BVH 可能不平衡
- R 树支持高效的动态更新
- R 树保证填充率（通常 ≥ 40%）12.7 本章小结
空间索引结构对比
| 结构 | 类型 | 维度 | 动态性 | 最佳应用 |
|---|---|---|---|---|
| 四叉树 | 空间划分 | 2D | 中 | 2D 碰撞 |
| 八叉树 | 空间划分 | 3D | 中 | 3D 场景 |
| KD 树 | 混合 | K维 | 差 | 点云、K近邻 |
| BVH | 对象划分 | 任意 | 好 | 光线追踪 |
| R 树 | 对象划分 | K维 | 优秀 | 数据库 |
查询复杂度
| 操作 | 暴力 | 四叉树/八叉树 | KD 树 | BVH |
|---|---|---|---|---|
| 构建 | - | O(n log n) | O(n log n) | O(n log n) |
| 点查询 | O(n) | O(log n) | O(log n) | O(log n) |
| 范围查询 | O(n) | O(√n + k) | O(√n + k) | O(log n + k) |
| K近邻 | O(n) | O(n) | O(log n) | O(n) |
关键要点
- 空间索引将查询复杂度从 O(n) 降到 O(log n)
- 四叉树/八叉树适合均匀分布的数据
- KD 树最适合静态点云和 K 近邻查询
- BVH 是光线追踪的首选，支持动态更新
- SAH 可以构建更高质量的 BVH
下一章预告：在第13章中，我们将学习图像处理基础，包括卷积、滤波和形态学操作。
文档版本：v1.0
字数统计：约 12,000 字