4.1.1 KD树：构建与遍历

文档摘要

4.1.1 KD树：构建与遍历在光线追踪、碰撞检测、点云处理乃至现代神经辐射场（NeRF）的加速采样中，空间索引不是锦上添花的装饰，而是决定帧率能否从1 fps跃升至60 fps的命脉。而在这条命脉之上跳动最有力的一节——正是KD树（K-Dimensional tree）。它不靠玄学优化，不依赖黑盒学习，仅凭对几何本质的冷静拆解与对计算代价的锱铢必较，便在数百万三角形与上亿采样点之间架起一条确定性极强的“最短通路”。但遗憾的是，太多工程师只把它当作一行API调用背后的模糊黑箱：知道它快，却不知为何有时快得惊人，有时又慢得令人抓狂；能调用，却在场景动态变化时束手无策；抄来一段递归建树代码，却在8K分辨率路径追踪中因栈溢出而崩溃。