← 全部标签
# 场景图
2 篇页面
页面
图形学空间数据结构Spatial Data Structures空间数据结构把几何体按 n 维空间组织起来，通常是层次化的树，使"几何体是否重叠"一类查询从 O(n) 降到大约 O(\log n)。常见类型有包围体层次 (BVH)、BSP 树（轴对齐的 k-d 树与多边形对齐两种）、四叉树/八叉树（含松散八叉树），以及更偏向组织模型关系的场景图。它们是剔除、光线求交、碰撞检测等加速算法的基础。游戏开发脏标记Dirty Flag脏标记 (Dirty Flag) 用一个布尔标记记录“派生数据是否已经过时”：原始数据变化时置位；需要派生数据时，如果标记已置位就重新计算并清除标记，否则直接用缓存的结果。场景图里由局部变换求世界变换是经典例子。它只在原始数据变化比派生数据被使用更频繁、而且难以增量更新时才划算，最大的风险是漏置标记导致使用过时数据。