本文探讨了线性代数、空间解析几何与数据结构算法在计算机图形学中的结合。介绍了向量、矩阵变换等数学基础，详细讲解了四叉树、八叉树、KD 树、BSP 树及 BVH 等几何数据结构原理。阐述了 AABB、OBB 及包围球等包围盒技术，以及射线与 AABB、三角形相交测试和分离轴定理（SAT）等核心算法。最后讨论了浮点数精度、缓存友好性及 SIMD 并行化等工程实践，旨在帮助读者理解构建物理引擎和光线追踪器的底层逻辑。
你可能曾对着课本里枯燥的矩阵乘法昏昏欲睡；你可能在学习解析几何时，被复杂的二次曲面方程绕得头晕目眩；你也一定曾为了调通一个二叉树的递归指针而熬过大夜。
那时候你或许会问："学这些到底有什么用？"
直到有一天，你打开了一款 3A 游戏大作，看到物理引擎里成千上万个刚体激烈碰撞却丝滑流畅，又或者看到光线追踪（Ray Tracing）渲染出足以乱真的水面反光。
你突然发现，构成这个绚丽 3D 数字世界的最底层基石，正是你当初死磕过的那些公式与指针。
当"数学的语言"遇上"计算机的算法"，一个迷人且硬核的领域大门向你敞开了——几何体数据结构（Geometric Data Structures）。
在计算机里，世界是一片虚无。是线性代数和空间解析几何赋予了它形状和规则。
但是，如果场景里有 100 万个多边形，你开一枪，难道要把直线方程和这 100 万个多边形方程全部联立算一遍吗？
如果这么做，你的 CPU 会瞬间融化，游戏帧率会跌到每秒 0.001 帧。
这时候，数学的蛮力已经到了极限。我们需要算法来救场。
为了打破暴力遍历 O(N) 的诅咒，树形数据结构和分治思想（Divide & Conquer） 闪亮登场。
我们不再傻傻地遍历所有物体，而是用树把空间或物体"框"起来、切开来。通过将查询复杂度从 O(N) 降到 O(log N)（理想情况下），我们赋予了计算机在庞大世界中瞬息万变的能力。
这就是几何体数据结构的几大核心流派：
原理： 拿刀把空间从几何中心十字切开（2D 变 4 份，3D 变 8 份），如果哪份里面东西多，就继续切，递归执行，直到每份只剩几个物体或达到最大深度。
完美邂逅： 递归（数据结构）+ AABB 轴向包围盒（解析几何）。这是最符合直觉的空间划分方式，常用于大世界地图的多细节层次加载（LOD）和基础碰撞检测。它的规则简单粗暴：不管你的数据长什么样，我都从正中间一刀一刀等分下去。
原理： 不再死板地从正中间切。每次选定一个坐标轴（X、Y 或 Z），找到数据在该轴上的中位数，用一个平行于坐标轴的平面把空间一分为二。下一层换一个轴，再切，如此交替递归。
完美邂逅： 二叉搜索树（BST）的多维升级版 + 平面方程。它曾是光线追踪领域的早期霸主，也是搜索最近邻点（KNN）的绝对神器。当你需要在一堆三维点云里找到离目标最近的那个点时，KD 树能让你免于遍历整个宇宙。
原理： KD 树只能用平行于坐标轴的平面来切，而 BSP 树允许用任意角度和位置的平面来切分空间！这赋予了它极大的灵活性，可以沿着场景中多边形本身的朝向来划分空间。
完美邂逅： 解析几何中"一般平面方程" Ax + By + Cz + D = 0 在这里大放异彩。上世纪 90 年代，著名的第一人称射击游戏正是靠 BSP 树，在没有 3D 图形加速卡的年代，用 CPU 高效地解决了复杂室内场景的渲染排序问题（决定哪面墙先画、哪面墙后画），让玩家流畅地穿越迷宫，开创了一个游戏时代。
原理： 前面三种结构都在"切分空间"。BVH 的哲学完全不同——它不切分空间，而是划分物体集合。把相近的物体用一个紧凑的盒子（包围盒）罩起来；再把相邻的几个盒子，用一个更大的盒子罩起来，层层往上，形成一棵层级分明的树。
完美邂逅： 现代物理引擎和实时光线追踪（如 NVIDIA RTX）的绝对核心。当你发射一条射线，如果它连外面的大盒子都没碰到，里面成千上万的小盒子和几万个三角形就全部被跳过，一次比较就淘汰了半棵树的计算量。而且，由于 BVH 划分的是物体而非空间，当物体移动时，只需要局部更新包围盒，而不需要像八叉树那样重建整棵树，这使它成为了动态场景的首选。
在深入任何空间树之前，你必须先认识它们最基本的"砖块"——包围盒（Bounding Volume）。包围盒的本质是用一个简单、廉价的几何体，把一个复杂、昂贵的几何体"罩"起来。如果连简单的盒子都没被碰到，那里面复杂的模型就根本不用检测。
空间数据结构本身只是一个"索引"。它的价值完全取决于你在遍历这棵树的每一个节点时，能不能快速、准确地做出一个判断："我关心的东西（射线、点、区域），和这个节点代表的空间区域有没有交集？"
这个判断过程，就是相交测试（Intersection Test）。它是整个体系跳动的心脏。
这是光线追踪和 BVH 遍历中执行频率最高的操作，没有之一。
核心思想： 一个 AABB 可以被看作三对平行平面的交集（X 轴方向一对、Y 轴方向一对、Z 轴方向一对）。一条射线穿过一对平行平面时，会产生一个进入时间 t_min 和一个离开时间 t_max。如果射线同时穿过了三对平面，那么三个进入时间中最大的那个，和三个离开时间中最小的那个，如果满足 t_enter ≤ t_exit 且 t_exit ≥ 0，那射线就击中了这个盒子。
数学映射：
整个过程没有三角函数，没有开方，只有加减乘除和比较。这就是为什么 AABB + Slab 算法能在 GPU 上以数十亿次每秒的速度执行。
当射线穿过了 BVH 的层层包围盒，最终到达叶子节点，它必须和叶子里存储的三角形做最终的精确相交判定。
核心思想： 三角形上的任意一点，都可以用它的三个顶点 V_0, V_1, V_2 和两个参数 u, v（重心坐标）来表示：P = (1 - u - v)V_0 + uV_1 + vV_2。把射线方程和这个参数方程联立，就变成了一个三元一次方程组。用克莱姆法则（Cramer's Rule） 来解这个方程组——而克莱姆法则的核心操作，就是线性代数里的行列式和解析几何里的混合积。
数学映射：
当 u ≥ 0、v ≥ 0、u + v ≤ 1 且 t > 0 时，射线命中了三角形。你在线性代数课上反复练习的行列式计算，在这里成了每一帧画面背后执行数百万次的核心引擎。
这是判断两个凸多面体（如两个 OBB）是否相交的通用数学武器。
核心思想： 如果两个凸体没有相交，那么一定存在一条轴，使得两个凸体在这条轴上的投影区间互不重叠。反过来说，如果你穷举了所有可能的候选轴，在每一条轴上的投影都有重叠，那么这两个凸体一定相交。
数学映射：
两个 OBB 的 SAT 需要测试 3 + 3 + 9 = 15 条候选轴。只要在任何一条轴上发现投影不重叠，就可以立刻判定"不相交"并提前返回。
掌握了上面的核心结构和相交算法之后，还有更广阔的天地等着你：
数学告诉你"怎么算"，算法告诉你"怎么组织"，但要让代码在真实的 CPU 和 GPU 上飞起来，你还需要跨越工程的最后一道鸿沟。
== 来比较，你的程序会以各种诡异的方式崩溃。你必须引入一个极小的容差 ϵ（epsilon），用 abs(a - b) < epsilon 来做"近似相等"判断。这一个细节，是无数图形学新手踩过的第一个大坑。new 出来的，散落在内存的天涯海角。但在现代引擎中，BVH 的所有节点通常被"压扁"存储在一块连续的数组里，子节点的索引用数组下标而非指针来表示。这样做的唯一目的是让 CPU 在遍历树时，尽可能地从高速缓存（Cache）中读取数据，而不是等待缓慢的主内存。一次 Cache Miss 的代价，可能比一百次浮点运算还大。你看，你曾经以为毫无交集的几门课，其实在顶层是紧紧咬合的齿轮：
当你把这三者融会贯通，你就拥有了手搓物理引擎、写出光线追踪器、甚至开发下一代空间计算系统的前置底盘。
所以，别怕那些天书般的数学符号，也别怵那些绕来绕去的指针。因为从今天起，你学的每一个公式、写的每一行代码，都是在为构筑数字宇宙积攒"源代码"。
带上你的线性代数，翻开你的解析几何，准备好你的编译器。
欢迎来到属于勇敢者的几何体数据结构世界。游戏，才刚刚开始。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online