引言你可能曾对着课本里枯燥的矩阵乘法昏昏欲睡你可能在学习解析几何时被复杂的二次曲面方程绕得头晕目眩你也一定曾为了调通一个二叉树的递归指针而熬过大夜。那时候你或许会问“学这些到底有什么用”直到有一天你打开了一款3A游戏大作看到物理引擎里成千上万个刚体激烈碰撞却丝滑流畅又或者看到光线追踪Ray Tracing渲染出足以乱真的水面反光。你突然发现构成这个绚丽3D数字世界的最底层基石正是你当初死磕过的那些公式与指针。当数学的语言遇上计算机的算法一个迷人且硬核的领域大门向你敞开了——几何体数据结构Geometric Data Structures。第一幕空间的语言 —— 数学的子弹已上膛在计算机里世界是一片虚无。是线性代数和空间解析几何赋予了它形状和规则。向量与点积/叉积它们不是纸上的箭头而是游戏角色的视线是判断敌人是否在背后的雷达是计算风吹过树叶时的受力方向。点积告诉你两个方向有多一致叉积告诉你一个面朝向哪里。矩阵变换4×44 \times 44×4的齐次变换矩阵就是数字世界的乾坤大挪移。一个矩阵乘法就能让一架宇宙飞船在星际坐标系中完成平移、旋转和缩放。矩阵的前三列是物体在空间中的三个正交基向量——它的上、“右和前”——第四列是它的位置。直线与平面方程当你从屏幕中央开出一枪在数学上这就是一条参数化的空间直线方程P(t)OtD⃗P(t) O t\vec{D}P(t)OtD。子弹能不能打中墙壁本质上就是求这条直线方程与墙壁的平面方程的联立解。但是如果场景里有100万个多边形你开一枪难道要把直线方程和这100万个多边形方程全部联立算一遍吗如果这么做你的CPU会瞬间融化游戏帧率会跌到每秒0.001帧。这时候数学的蛮力已经到了极限。我们需要算法来救场。第二幕秩序的建立 —— 数据结构的降维打击为了打破暴力遍历O(N)O(N)O(N)的诅咒树形数据结构和分治思想Divide Conquer闪亮登场。我们不再傻傻地遍历所有物体而是用树把空间或物体框起来、切开来。通过将查询复杂度从O(N)O(N)O(N)降到O(logN)O(\log N)O(logN)理想情况下我们赋予了计算机在庞大世界中瞬息万变的能力。这就是几何体数据结构的几大核心流派1. 四叉树 / 八叉树 (Quadtree / Octree) —— 空间的绝对割裂原理拿刀把空间从几何中心十字切开2D变4份3D变8份如果哪份里面东西多就继续切递归执行直到每份只剩几个物体或达到最大深度。完美邂逅递归数据结构 AABB轴向包围盒解析几何。这是最符合直觉的空间划分方式常用于大世界地图的多细节层次加载LOD和基础碰撞检测。它的规则简单粗暴不管你的数据长什么样我都从正中间一刀一刀等分下去。2. KD树 (K-Dimensional Tree) —— 解析几何的极致刀法原理不再死板地从正中间切。每次选定一个坐标轴X、Y或Z找到数据在该轴上的中位数用一个平行于坐标轴的平面把空间一分为二。下一层换一个轴再切如此交替递归。完美邂逅二叉搜索树BST的多维升级版 平面方程。它曾是光线追踪领域的早期霸主也是搜索最近邻点KNN的绝对神器。当你需要在一堆三维点云里找到离目标最近的那个点时KD树能让你免于遍历整个宇宙。3. BSP树 (Binary Space Partitioning Tree) —— 经典FPS神话的缔造者原理KD树只能用平行于坐标轴的平面来切而BSP树允许用任意角度和位置的平面来切分空间这赋予了它极大的灵活性可以沿着场景中多边形本身的朝向来划分空间。完美邂逅解析几何中一般平面方程AxByCzD0Ax By Cz D 0AxByCzD0在这里大放异彩。上世纪90年代著名的第一人称射击游戏正是靠BSP树在没有3D图形加速卡的年代用CPU高效地解决了复杂室内场景的渲染排序问题决定哪面墙先画、哪面墙后画让玩家流畅地穿越迷宫开创了一个游戏时代。4. BVH (层次包围盒 Bounding Volume Hierarchy) —— 现代引擎的终极答案原理前面三种结构都在切分空间。BVH的哲学完全不同——它不切分空间而是划分物体集合。把相近的物体用一个紧凑的盒子包围盒罩起来再把相邻的几个盒子用一个更大的盒子罩起来层层往上形成一棵层级分明的树。完美邂逅现代物理引擎和实时光线追踪如NVIDIA RTX的绝对核心。当你发射一条射线如果它连外面的大盒子都没碰到里面成千上万的小盒子和几万个三角形就全部被跳过一次比较就淘汰了半棵树的计算量。而且由于BVH划分的是物体而非空间当物体移动时只需要局部更新包围盒而不需要像八叉树那样重建整棵树这使它成为了动态场景的首选。第三幕包围盒 —— 几何世界的第一道防线在深入任何空间树之前你必须先认识它们最基本的砖块——包围盒Bounding Volume。包围盒的本质是用一个简单、廉价的几何体把一个复杂、昂贵的几何体罩起来。如果连简单的盒子都没被碰到那里面复杂的模型就根本不用检测。AABB轴对齐包围盒 Axis-Aligned Bounding Box定义一个六个面都严格平行于坐标轴的长方体。在内存里只需要存两个三维向量最小角点(minx,miny,minz)(\text{min}_x, \text{min}_y, \text{min}_z)(minx,miny,minz)和最大角点(maxx,maxy,maxz)(\text{max}_x, \text{max}_y, \text{max}_z)(maxx,maxy,maxz)。优点相交测试极其便宜。判断两个AABB是否重叠只需要在三个轴上分别比较区间是否有交集——六次比较零次乘法。判断一个点是否在AABB内部只需要六次大小比较。缺点当物体是一根斜着的长棍时AABB会产生大量的空白浪费空间导致误报明明没碰到物体却碰到了盒子。数学本质这就是解析几何中坐标区间的直接应用——把三维空间中的一个区域用三个独立的一维区间[xmin,xmax]×[ymin,ymax]×[zmin,zmax][x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}] \times [z_{\min}, z_{\max}][xmin,xmax]×[ymin,ymax]×[zmin,zmax]来表达。OBB有向包围盒 Oriented Bounding Box定义一个可以任意旋转的长方体。在内存里需要存中心点、三个互相垂直的局部坐标轴正交基向量、以及沿这三个轴的半长。优点比AABB更紧凑地贴合物体。对于旋转过的狭长物体OBB的浪费空间远小于AABB。缺点相交测试的代价陡然上升。判断两个OBB是否相交需要使用分离轴定理SAT在最多15条候选分离轴上做投影和区间比较。数学本质OBB的三个局部坐标轴就是线性代数中正交基Orthonormal Basis的直接体现。而SAT中的投影操作本质上就是向量的点积——把一个顶点投影到某条轴上得到一个标量坐标。包围球Bounding Sphere定义用一个球心和一个半径来定义。优点旋转不变性无论物体怎么旋转包围球的形状和大小都不会改变。而且两个包围球的相交测试极其简单算两个球心的距离和两个半径之和比大小一次比较就完事。缺点对于扁平或狭长的物体包围球的浪费空间是所有包围体中最大的。数学本质这就是解析几何中球面方程(x−cx)2(y−cy)2(z−cz)2r2(x - c_x)^2 (y - c_y)^2 (z - c_z)^2 r^2(x−cx)2(y−cy)2(z−cz)2r2的直接应用。而射线与球体的求交就是把直线参数方程代入球面方程解一个一元二次方程at2btc0at^2 bt c 0at2btc0判别式Δb2−4ac\Delta b^2 - 4acΔb2−4ac大于零就是相交。第四幕相交测试 —— 空间数据结构的心脏空间数据结构本身只是一个索引。它的价值完全取决于你在遍历这棵树的每一个节点时能不能快速、准确地做出一个判断“我关心的东西射线、点、区域和这个节点代表的空间区域有没有交集”这个判断过程就是相交测试Intersection Test。它是整个体系跳动的心脏。射线与AABB相交Slab算法这是光线追踪和BVH遍历中执行频率最高的操作没有之一。核心思想一个AABB可以被看作三对平行平面的交集X轴方向一对、Y轴方向一对、Z轴方向一对。一条射线穿过一对平行平面时会产生一个进入时间tmint_{\min}tmin和一个离开时间tmaxt_{\max}tmax。如果射线同时穿过了三对平面那么三个进入时间中最大的那个和三个离开时间中最小的那个如果满足tenter≤texitt_{\text{enter}} \le t_{\text{exit}}tenter≤texit且texit≥0t_{\text{exit}} \ge 0texit≥0那射线就击中了这个盒子。数学映射射线方程P(t)OtD⃗P(t) O t\vec{D}P(t)OtD解析几何空间直线参数方程求射线与某个面xxminx x_{\min}xxmin的交点txmin−OxDxt \frac{x_{\min} - O_x}{D_x}tDxxmin−Ox解析几何直线与平面联立最终判断max(txmin,tymin,tzmin)≤min(txmax,tymax,tzmax)\max(t_{x_{\min}}, t_{y_{\min}}, t_{z_{\min}}) \le \min(t_{x_{\max}}, t_{y_{\max}}, t_{z_{\max}})max(txmin,tymin,tzmin)≤min(txmax,tymax,tzmax)整个过程没有三角函数没有开方只有加减乘除和比较。这就是为什么AABB Slab算法能在GPU上以数十亿次每秒的速度执行。射线与三角形相交Möller-Trumbore算法当射线穿过了BVH的层层包围盒最终到达叶子节点它必须和叶子里存储的三角形做最终的精确相交判定。核心思想三角形上的任意一点都可以用它的三个顶点V0,V1,V2V_0, V_1, V_2V0,V1,V2和两个参数u,vu, vu,v重心坐标来表示P(1−u−v)V0uV1vV2P (1 - u - v)V_0 uV_1 vV_2P(1−u−v)V0uV1vV2。把射线方程和这个参数方程联立就变成了一个三元一次方程组。用克莱姆法则Cramer’s Rule来解这个方程组——而克莱姆法则的核心操作就是线性代数里的行列式和解析几何里的混合积。数学映射重心坐标解析几何仿射组合联立方程组线性代数AxbAx bAxb克莱姆法则 / 行列式线性代数叉积与混合积空间解析几何向量代数当u≥0u \ge 0u≥0、v≥0v \ge 0v≥0、uv≤1u v \le 1uv≤1且t0t 0t0时射线命中了三角形。你在线性代数课上反复练习的行列式计算在这里成了每一帧画面背后执行数百万次的核心引擎。分离轴定理SAT - Separating Axis Theorem这是判断两个凸多面体如两个OBB是否相交的通用数学武器。核心思想如果两个凸体没有相交那么一定存在一条轴使得两个凸体在这条轴上的投影区间互不重叠。反过来说如果你穷举了所有可能的候选轴在每一条轴上的投影都有重叠那么这两个凸体一定相交。数学映射投影 向量点积线性代数内积的几何意义候选分离轴 两个OBB各自三条局部坐标轴 两两叉积得到的9条轴解析几何叉积区间重叠判断 一维区间比较基础数学两个OBB的SAT需要测试339153 3 9 1533915条候选轴。只要在任何一条轴上发现投影不重叠就可以立刻判定不相交并提前返回。第五幕超越入门 —— 当你想走得更远掌握了上面的核心结构和相交算法之后还有更广阔的天地等着你均匀网格 / 哈希网格 (Uniform Grid / Hash Grid)把空间切成均匀的小格子通过哈希函数直接定位物体所在的格子。在粒子系统和流体模拟中它的简洁和速度无可替代。R树 (R-Tree)BVH在数据库领域的亲兄弟专门为磁盘读写优化是地理信息系统GIS中存储和查询空间数据如查找附近的餐厅的行业标准。表面积启发式 (SAH)构建BVH时不再拍脑袋决定在哪里分裂节点而是通过计算子包围盒表面积的比例来估算一条随机射线击中它的概率从而找到数学上的最优分裂方案。这是概率论与组合优化在图形学中的经典应用。Morton码与线性八叉树通过位交错Bit Interleaving运算将三维坐标(x,y,z)(x, y, z)(x,y,z)编码为一个一维整数。对这些整数排序后你会发现它们天然形成了一棵八叉树的遍历顺序。这是离散数学和位运算在空间索引中的精彩表演。第六幕从理论到引擎 —— 工程的最后一公里数学告诉你怎么算算法告诉你怎么组织但要让代码在真实的CPU和GPU上飞起来你还需要跨越工程的最后一道鸿沟。浮点数的陷阱在纯数学中0.10.20.30.1 0.2 0.30.10.20.3。但在计算机的浮点数世界里0.10.20.300000000000000040.1 0.2 0.300000000000000040.10.20.30000000000000004。当你判断一个点是否精确落在分割平面上时如果用来比较你的程序会以各种诡异的方式崩溃。你必须引入一个极小的容差ϵ\epsilonϵepsilon用abs(a - b) epsilon来做近似相等判断。这一个细节是无数图形学新手踩过的第一个大坑。缓存友好性Cache Locality你在数据结构课上学的二叉树每个节点都是new出来的散落在内存的天涯海角。但在现代引擎中BVH的所有节点通常被压扁存储在一块连续的数组里子节点的索引用数组下标而非指针来表示。这样做的唯一目的是让CPU在遍历树时尽可能地从高速缓存Cache中读取数据而不是等待缓慢的主内存。一次Cache Miss的代价可能比一百次浮点运算还大。SIMD并行化现代CPU支持用一条指令同时处理4个或8个浮点数SSE/AVX指令集。经过精心设计的Slab算法可以用一条SIMD指令同时完成射线在X、Y、Z三个轴上的参数计算。当你的BVH遍历被SIMD优化后性能可以提升数倍。尾声去成为数字世界的造物主你看你曾经以为毫无交集的几门课其实在顶层是紧紧咬合的齿轮线性代数给你提供了描述多维空间和变换的基础组件。空间解析几何教你如何用方程精确表达物体的形状和相交规律。数据结构与算法则为你提供了管理和检索海量几何数据的高效引擎。当你把这三者融会贯通你就拥有了手搓物理引擎、写出光线追踪器、甚至开发下一代空间计算系统的前置底盘。所以别怕那些天书般的数学符号也别怵那些绕来绕去的指针。因为从今天起你学的每一个公式、写的每一行代码都是在为构筑数字宇宙积攒源代码。带上你的线性代数翻开你的解析几何准备好你的编译器。欢迎来到属于勇敢者的几何体数据结构世界。游戏才刚刚开始。
当线性代数与空间解析几何遇上数据结构与算法：欢迎来到几何体数据结构的世界
发布时间：2026/6/9 5:39:42
引言你可能曾对着课本里枯燥的矩阵乘法昏昏欲睡你可能在学习解析几何时被复杂的二次曲面方程绕得头晕目眩你也一定曾为了调通一个二叉树的递归指针而熬过大夜。那时候你或许会问“学这些到底有什么用”直到有一天你打开了一款3A游戏大作看到物理引擎里成千上万个刚体激烈碰撞却丝滑流畅又或者看到光线追踪Ray Tracing渲染出足以乱真的水面反光。你突然发现构成这个绚丽3D数字世界的最底层基石正是你当初死磕过的那些公式与指针。当数学的语言遇上计算机的算法一个迷人且硬核的领域大门向你敞开了——几何体数据结构Geometric Data Structures。第一幕空间的语言 —— 数学的子弹已上膛在计算机里世界是一片虚无。是线性代数和空间解析几何赋予了它形状和规则。向量与点积/叉积它们不是纸上的箭头而是游戏角色的视线是判断敌人是否在背后的雷达是计算风吹过树叶时的受力方向。点积告诉你两个方向有多一致叉积告诉你一个面朝向哪里。矩阵变换4×44 \times 44×4的齐次变换矩阵就是数字世界的乾坤大挪移。一个矩阵乘法就能让一架宇宙飞船在星际坐标系中完成平移、旋转和缩放。矩阵的前三列是物体在空间中的三个正交基向量——它的上、“右和前”——第四列是它的位置。直线与平面方程当你从屏幕中央开出一枪在数学上这就是一条参数化的空间直线方程P(t)OtD⃗P(t) O t\vec{D}P(t)OtD。子弹能不能打中墙壁本质上就是求这条直线方程与墙壁的平面方程的联立解。但是如果场景里有100万个多边形你开一枪难道要把直线方程和这100万个多边形方程全部联立算一遍吗如果这么做你的CPU会瞬间融化游戏帧率会跌到每秒0.001帧。这时候数学的蛮力已经到了极限。我们需要算法来救场。第二幕秩序的建立 —— 数据结构的降维打击为了打破暴力遍历O(N)O(N)O(N)的诅咒树形数据结构和分治思想Divide Conquer闪亮登场。我们不再傻傻地遍历所有物体而是用树把空间或物体框起来、切开来。通过将查询复杂度从O(N)O(N)O(N)降到O(logN)O(\log N)O(logN)理想情况下我们赋予了计算机在庞大世界中瞬息万变的能力。这就是几何体数据结构的几大核心流派1. 四叉树 / 八叉树 (Quadtree / Octree) —— 空间的绝对割裂原理拿刀把空间从几何中心十字切开2D变4份3D变8份如果哪份里面东西多就继续切递归执行直到每份只剩几个物体或达到最大深度。完美邂逅递归数据结构 AABB轴向包围盒解析几何。这是最符合直觉的空间划分方式常用于大世界地图的多细节层次加载LOD和基础碰撞检测。它的规则简单粗暴不管你的数据长什么样我都从正中间一刀一刀等分下去。2. KD树 (K-Dimensional Tree) —— 解析几何的极致刀法原理不再死板地从正中间切。每次选定一个坐标轴X、Y或Z找到数据在该轴上的中位数用一个平行于坐标轴的平面把空间一分为二。下一层换一个轴再切如此交替递归。完美邂逅二叉搜索树BST的多维升级版 平面方程。它曾是光线追踪领域的早期霸主也是搜索最近邻点KNN的绝对神器。当你需要在一堆三维点云里找到离目标最近的那个点时KD树能让你免于遍历整个宇宙。3. BSP树 (Binary Space Partitioning Tree) —— 经典FPS神话的缔造者原理KD树只能用平行于坐标轴的平面来切而BSP树允许用任意角度和位置的平面来切分空间这赋予了它极大的灵活性可以沿着场景中多边形本身的朝向来划分空间。完美邂逅解析几何中一般平面方程AxByCzD0Ax By Cz D 0AxByCzD0在这里大放异彩。上世纪90年代著名的第一人称射击游戏正是靠BSP树在没有3D图形加速卡的年代用CPU高效地解决了复杂室内场景的渲染排序问题决定哪面墙先画、哪面墙后画让玩家流畅地穿越迷宫开创了一个游戏时代。4. BVH (层次包围盒 Bounding Volume Hierarchy) —— 现代引擎的终极答案原理前面三种结构都在切分空间。BVH的哲学完全不同——它不切分空间而是划分物体集合。把相近的物体用一个紧凑的盒子包围盒罩起来再把相邻的几个盒子用一个更大的盒子罩起来层层往上形成一棵层级分明的树。完美邂逅现代物理引擎和实时光线追踪如NVIDIA RTX的绝对核心。当你发射一条射线如果它连外面的大盒子都没碰到里面成千上万的小盒子和几万个三角形就全部被跳过一次比较就淘汰了半棵树的计算量。而且由于BVH划分的是物体而非空间当物体移动时只需要局部更新包围盒而不需要像八叉树那样重建整棵树这使它成为了动态场景的首选。第三幕包围盒 —— 几何世界的第一道防线在深入任何空间树之前你必须先认识它们最基本的砖块——包围盒Bounding Volume。包围盒的本质是用一个简单、廉价的几何体把一个复杂、昂贵的几何体罩起来。如果连简单的盒子都没被碰到那里面复杂的模型就根本不用检测。AABB轴对齐包围盒 Axis-Aligned Bounding Box定义一个六个面都严格平行于坐标轴的长方体。在内存里只需要存两个三维向量最小角点(minx,miny,minz)(\text{min}_x, \text{min}_y, \text{min}_z)(minx,miny,minz)和最大角点(maxx,maxy,maxz)(\text{max}_x, \text{max}_y, \text{max}_z)(maxx,maxy,maxz)。优点相交测试极其便宜。判断两个AABB是否重叠只需要在三个轴上分别比较区间是否有交集——六次比较零次乘法。判断一个点是否在AABB内部只需要六次大小比较。缺点当物体是一根斜着的长棍时AABB会产生大量的空白浪费空间导致误报明明没碰到物体却碰到了盒子。数学本质这就是解析几何中坐标区间的直接应用——把三维空间中的一个区域用三个独立的一维区间[xmin,xmax]×[ymin,ymax]×[zmin,zmax][x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}] \times [z_{\min}, z_{\max}][xmin,xmax]×[ymin,ymax]×[zmin,zmax]来表达。OBB有向包围盒 Oriented Bounding Box定义一个可以任意旋转的长方体。在内存里需要存中心点、三个互相垂直的局部坐标轴正交基向量、以及沿这三个轴的半长。优点比AABB更紧凑地贴合物体。对于旋转过的狭长物体OBB的浪费空间远小于AABB。缺点相交测试的代价陡然上升。判断两个OBB是否相交需要使用分离轴定理SAT在最多15条候选分离轴上做投影和区间比较。数学本质OBB的三个局部坐标轴就是线性代数中正交基Orthonormal Basis的直接体现。而SAT中的投影操作本质上就是向量的点积——把一个顶点投影到某条轴上得到一个标量坐标。包围球Bounding Sphere定义用一个球心和一个半径来定义。优点旋转不变性无论物体怎么旋转包围球的形状和大小都不会改变。而且两个包围球的相交测试极其简单算两个球心的距离和两个半径之和比大小一次比较就完事。缺点对于扁平或狭长的物体包围球的浪费空间是所有包围体中最大的。数学本质这就是解析几何中球面方程(x−cx)2(y−cy)2(z−cz)2r2(x - c_x)^2 (y - c_y)^2 (z - c_z)^2 r^2(x−cx)2(y−cy)2(z−cz)2r2的直接应用。而射线与球体的求交就是把直线参数方程代入球面方程解一个一元二次方程at2btc0at^2 bt c 0at2btc0判别式Δb2−4ac\Delta b^2 - 4acΔb2−4ac大于零就是相交。第四幕相交测试 —— 空间数据结构的心脏空间数据结构本身只是一个索引。它的价值完全取决于你在遍历这棵树的每一个节点时能不能快速、准确地做出一个判断“我关心的东西射线、点、区域和这个节点代表的空间区域有没有交集”这个判断过程就是相交测试Intersection Test。它是整个体系跳动的心脏。射线与AABB相交Slab算法这是光线追踪和BVH遍历中执行频率最高的操作没有之一。核心思想一个AABB可以被看作三对平行平面的交集X轴方向一对、Y轴方向一对、Z轴方向一对。一条射线穿过一对平行平面时会产生一个进入时间tmint_{\min}tmin和一个离开时间tmaxt_{\max}tmax。如果射线同时穿过了三对平面那么三个进入时间中最大的那个和三个离开时间中最小的那个如果满足tenter≤texitt_{\text{enter}} \le t_{\text{exit}}tenter≤texit且texit≥0t_{\text{exit}} \ge 0texit≥0那射线就击中了这个盒子。数学映射射线方程P(t)OtD⃗P(t) O t\vec{D}P(t)OtD解析几何空间直线参数方程求射线与某个面xxminx x_{\min}xxmin的交点txmin−OxDxt \frac{x_{\min} - O_x}{D_x}tDxxmin−Ox解析几何直线与平面联立最终判断max(txmin,tymin,tzmin)≤min(txmax,tymax,tzmax)\max(t_{x_{\min}}, t_{y_{\min}}, t_{z_{\min}}) \le \min(t_{x_{\max}}, t_{y_{\max}}, t_{z_{\max}})max(txmin,tymin,tzmin)≤min(txmax,tymax,tzmax)整个过程没有三角函数没有开方只有加减乘除和比较。这就是为什么AABB Slab算法能在GPU上以数十亿次每秒的速度执行。射线与三角形相交Möller-Trumbore算法当射线穿过了BVH的层层包围盒最终到达叶子节点它必须和叶子里存储的三角形做最终的精确相交判定。核心思想三角形上的任意一点都可以用它的三个顶点V0,V1,V2V_0, V_1, V_2V0,V1,V2和两个参数u,vu, vu,v重心坐标来表示P(1−u−v)V0uV1vV2P (1 - u - v)V_0 uV_1 vV_2P(1−u−v)V0uV1vV2。把射线方程和这个参数方程联立就变成了一个三元一次方程组。用克莱姆法则Cramer’s Rule来解这个方程组——而克莱姆法则的核心操作就是线性代数里的行列式和解析几何里的混合积。数学映射重心坐标解析几何仿射组合联立方程组线性代数AxbAx bAxb克莱姆法则 / 行列式线性代数叉积与混合积空间解析几何向量代数当u≥0u \ge 0u≥0、v≥0v \ge 0v≥0、uv≤1u v \le 1uv≤1且t0t 0t0时射线命中了三角形。你在线性代数课上反复练习的行列式计算在这里成了每一帧画面背后执行数百万次的核心引擎。分离轴定理SAT - Separating Axis Theorem这是判断两个凸多面体如两个OBB是否相交的通用数学武器。核心思想如果两个凸体没有相交那么一定存在一条轴使得两个凸体在这条轴上的投影区间互不重叠。反过来说如果你穷举了所有可能的候选轴在每一条轴上的投影都有重叠那么这两个凸体一定相交。数学映射投影 向量点积线性代数内积的几何意义候选分离轴 两个OBB各自三条局部坐标轴 两两叉积得到的9条轴解析几何叉积区间重叠判断 一维区间比较基础数学两个OBB的SAT需要测试339153 3 9 1533915条候选轴。只要在任何一条轴上发现投影不重叠就可以立刻判定不相交并提前返回。第五幕超越入门 —— 当你想走得更远掌握了上面的核心结构和相交算法之后还有更广阔的天地等着你均匀网格 / 哈希网格 (Uniform Grid / Hash Grid)把空间切成均匀的小格子通过哈希函数直接定位物体所在的格子。在粒子系统和流体模拟中它的简洁和速度无可替代。R树 (R-Tree)BVH在数据库领域的亲兄弟专门为磁盘读写优化是地理信息系统GIS中存储和查询空间数据如查找附近的餐厅的行业标准。表面积启发式 (SAH)构建BVH时不再拍脑袋决定在哪里分裂节点而是通过计算子包围盒表面积的比例来估算一条随机射线击中它的概率从而找到数学上的最优分裂方案。这是概率论与组合优化在图形学中的经典应用。Morton码与线性八叉树通过位交错Bit Interleaving运算将三维坐标(x,y,z)(x, y, z)(x,y,z)编码为一个一维整数。对这些整数排序后你会发现它们天然形成了一棵八叉树的遍历顺序。这是离散数学和位运算在空间索引中的精彩表演。第六幕从理论到引擎 —— 工程的最后一公里数学告诉你怎么算算法告诉你怎么组织但要让代码在真实的CPU和GPU上飞起来你还需要跨越工程的最后一道鸿沟。浮点数的陷阱在纯数学中0.10.20.30.1 0.2 0.30.10.20.3。但在计算机的浮点数世界里0.10.20.300000000000000040.1 0.2 0.300000000000000040.10.20.30000000000000004。当你判断一个点是否精确落在分割平面上时如果用来比较你的程序会以各种诡异的方式崩溃。你必须引入一个极小的容差ϵ\epsilonϵepsilon用abs(a - b) epsilon来做近似相等判断。这一个细节是无数图形学新手踩过的第一个大坑。缓存友好性Cache Locality你在数据结构课上学的二叉树每个节点都是new出来的散落在内存的天涯海角。但在现代引擎中BVH的所有节点通常被压扁存储在一块连续的数组里子节点的索引用数组下标而非指针来表示。这样做的唯一目的是让CPU在遍历树时尽可能地从高速缓存Cache中读取数据而不是等待缓慢的主内存。一次Cache Miss的代价可能比一百次浮点运算还大。SIMD并行化现代CPU支持用一条指令同时处理4个或8个浮点数SSE/AVX指令集。经过精心设计的Slab算法可以用一条SIMD指令同时完成射线在X、Y、Z三个轴上的参数计算。当你的BVH遍历被SIMD优化后性能可以提升数倍。尾声去成为数字世界的造物主你看你曾经以为毫无交集的几门课其实在顶层是紧紧咬合的齿轮线性代数给你提供了描述多维空间和变换的基础组件。空间解析几何教你如何用方程精确表达物体的形状和相交规律。数据结构与算法则为你提供了管理和检索海量几何数据的高效引擎。当你把这三者融会贯通你就拥有了手搓物理引擎、写出光线追踪器、甚至开发下一代空间计算系统的前置底盘。所以别怕那些天书般的数学符号也别怵那些绕来绕去的指针。因为从今天起你学的每一个公式、写的每一行代码都是在为构筑数字宇宙积攒源代码。带上你的线性代数翻开你的解析几何准备好你的编译器。欢迎来到属于勇敢者的几何体数据结构世界。游戏才刚刚开始。
