JIEZCODE
首页 文章 专题 项目 关于我
JIEZCODE

Rendering Lecture 1：Spatial Acceleration Structures

Jiezcode avatarJiezcode   
         

Course: 渲染基础 Rendering Basics Date: November 29, 2025 10:34 AM (GMT+8)

🎮 Rendering Lecture 1：空间加速结构（Spatial Acceleration Structures）

🏛 1. 渲染核心任务：可见性 + 颜色

🎯 1.1 渲染的两个基础问题

  • 🎨 颜色（Intensity）：光照后像素应显示什么颜色
  • 👁 可见性（Visibility）：哪个物体遮挡哪个物体

可见性必须做到 像素级，否则不可能正确呈现复杂场景。

💻 2. 朴素 Ray Casting 的瓶颈

⚡ 循环结构（伪代码）

for pixel in image:
    shoot ray
    for triangle in scene:
        test intersection
    record nearest hit
  • 每张 4K 图像 ≈ 800 万像素
  • 场景可能有数百万三角形

👉 复杂度 O(pixels × triangles) 👉 轻松达到 万亿级 交点测试

✨ 3. 抗锯齿 & 超采样（Super Sampling）

  • 单一采样 → 像素要么全中，要么全黑 → 锯齿
  • 采用多子像素采样、平均颜色
  • 边缘柔和，但样本数暴涨 → 更需要加速结构

🏗️ 4. 空间加速结构综述

空间加速结构的使命： 让光线“少看三角形”。

主流结构：

结构特点应用
Regular Grid均匀划分空间简单但浪费内存
Quadtree / Octree自适应划分适合不均匀分布
KD-Tree轴向划分静态场景极强
BVH包围盒层级工业界主流（DXR、RTX）

🗂️ 5. Regular Grid（规则网格）

🧩 5.1 概念

将整个场景切成均匀格子，把三角形放入格子中。

⭐ 优点

  • 构建快
  • 简单、直观

⚠️ 缺点

  • 大部分格子为空 → 内存浪费
  • 少数格子包含过多三角形 → 搜索无加速效果

适合均匀点云，不适合复杂场景。

🗂️ 6. Quadtree / Octree（四叉树 / 八叉树）

🧭 6.1 动机

对“高密度区域继续细分”，对“空白区域保持粗粒度”。

🔨 特点

  • 自适应节点大小
  • 可能出现三角形跨多个节点 → 需要复制或切割

🧾 影响

  • 内存可能增大
  • 构建速度仍然较快
  • 比规则网格更好，但仍有限制

📊 7. KD-Tree（轴对齐二叉划分）

🧩 7.1 定义

使用垂直于 X/Y/Z 轴的平面拆分空间。

⭐ 优点

  • 自适应
  • 节点分布紧凑
  • 静态场景表现极佳

⚠️ 缺点

  • 三角形可能被切割
  • 构建代价中等，不适合动态场景

🔗 8. Bounding Volumes（包围体）

📦 8.1 为什么需要它？

用简单体包住复杂几何，让光线“快速拒绝”。

  • 🔵 球体（Sphere）
  • 🟥 AABB（轴对齐包围盒）

AABB 优点：

  • 由两点（min/max）定义
  • 合并简单
  • 光线测试非常快

🌟 9. BVH：光追时代的王牌结构

这是工业界（NVIDIA RTX、DXR、Embree）默认使用的结构。

🧱 9.1 结构

  • 内部节点：只存子节点的 AABB
  • 叶子节点：存三角形
  • 子包围盒必须在父包围盒之内
  • 节点间允许重叠（与 KD-Tree 的关键差异）

🎯 核心优势

  • 不切三角形
  • 节点可以重叠，内存低
  • 动态场景可局部更新
  • 容易 GPU 并行构建和遍历
  • 已被硬件加速（RT Cores）

🏗️ 10. 构建 BVH：三种分裂策略

🔨 10.1 Spatial Median（空间中点）

  • 找最长轴
  • 按空间中心分裂
  • ⚡ 超快
  • ❌ BVH 质量一般

🗂️ 10.2 Object Median（对象数量中点）

  • 按三角形中心排序
  • 前后各一半
  • ⚡ 较快
  • ⭐ 树比较平衡
  • ❌ 未必按照空间分布最优

🌈 10.3 SAH（Surface Area Heuristic）

现代 BVH 的黄金标准

✨ 公式思路

Cost=SA(left)⋅N(left)+SA(right)⋅N(right) \text{Cost} = SA(\text{left}) \cdot N(\text{left}) + SA(\text{right}) \cdot N(\text{right})
  • SA：包围盒表面积 → 被光线击中的概率
  • N：三角形数量 → 遍历代价

目标：找到最小成本的分裂位置。

⭐ 优点

  • 遍历性能最佳
  • 在静态场景可带来数量级加速

⚠️ 缺点

  • 构建成本最高

🧭 11. BVH Traversal（遍历）

📖 遍历规则

  1. 从根节点开始

  2. 若 AABB 与光线不相交 → 剪枝

  3. 若相交：

    • 是内部节点 → 优先遍历更近的子节点
    • 是叶节点 → 遍历其中所有三角形

  4. 使用栈记录将要回溯的节点

👉 快速跳过大批与光线无关的区域。

🧠 12. BVH 构建工程技巧

📁 使用全局 Triangle Array

  • 所有节点引用同一数组
  • split 时只移动元素、交换区间
  • 子节点仅需传入 [begin, end) 范围

⚙️ STL 工具

  • std::sort
  • std::nth_element（适合 Object Median）

⏳ SAH 的优化

预计算 LSA / RSA，减少重复扫描。

🔥 13. 加速结构比较（总览）

类型内存构建遍历速度场景
🟦 Regular Grid中–高快差均匀网格
🟩 Quadtree/Octree中–高快中等稍不均匀场景
🟨 KD-Tree中–高中很好静态场景
🟥 BVH（主流）低低–高优秀动态/静态都适用

🚀 14. 当前 BVH 的发展方向

  • 🔸 多叉 BVH（4-way, 8-way）
  • 🔸 Mixed Nodes（内部节点可同时包含三角形）
  • 🔸 动态场景可局部更新的 BVH
  • 🔸 GPU 上的 LBVH / HL-BVH
  • 🔸 适配动画骨骼的 BVH（Moving BVH）
  • 🔸 RTX / DXR 的硬件 BVH Traversal

🌟 15. 学完本章你应该理解的关键点

  • 光线追踪的瓶颈不是着色，而是“找谁被打到了”
  • 所有加速结构都是为减少交点测试次数
  • BVH 为什么成为现代渲染标准
  • SAH 分裂为何能提供最好的遍历性能
  • BVH 为什么比 KD-Tree 更适合 GPU 和动态场景
 Course Notes
 |