计算机图形学 16：多个模型怎样组成场景

把两个模型挂到同一个父节点下，旋转父节点后，模型画面跟着转了，碰撞或裁剪使用的包围盒却还停在原处。渲染结果和空间查询各自使用一套变换缓存时，很容易出现这种分歧。

本篇建立一个可从文件导入的三节点场景：一个分组节点与两个共享网格的实例。更换父节点变换后，同时核对世界顶点、实例包围盒与整个子树的包围盒；非法层级与缺失资源也必须明确失败。

资源和实例分别保存什么

第 12 篇的 Mesh 保存模型自身的顶点和三角形连接。把同一个方形放到两处，不需要复制它的顶点数组。两个场景节点只需引用同一个网格编号，各自保存局部变换。

资源表中的网格位于模型空间；场景节点记录“这份资源以什么变换出现在场景里”。改变一个实例的位置，不应改写资源表坐标，否则其他引用者也会改变。当前求值接口把资源表作为常量引用，只输出世界矩阵与包围盒。

分组节点可以没有网格。它仍然定义局部坐标系，其变换影响后代。实验中节点 0 就是这样的分组，节点 1 和 2 都引用资源 0。资源 0 只有四个顶点、两个三角形，但画面里出现两个实例。

节点关系采用森林：每个节点只有一个 parent 整数，−1 表示根。这种数据表示本身不允许同时写两个父节点；若从使用 children 数组的格式转换，需要先检查重复父引用，不能静默覆盖。当前文件并不解析 glTF，也没有声称支持它的完整资源和动画规范。

子节点的世界矩阵怎样得到

沿用列向量约定，局部矩阵 L 将节点坐标变到父坐标，父节点的世界矩阵 Wₚ 再变到世界坐标，因此：

W_c=W_pL_c,\qquad p_w=W_c p_c.

根节点没有父坐标系可继续追溯，它的世界矩阵就是自身局部矩阵。相机观察矩阵 V 和投影 P 在这之后作用，完整提交仍为 PVW₍c₎p，不把相机变换混进场景层级。

取父节点 Wₚ=T(10,0,0)Rz(90°)，子节点 L=T(2,0,0)。子节点原点先到父坐标 (2,0,0)，旋转后为 (0,2,0)，再平移到世界位置 (10,2,0)。若错写 L Wₚ，原点会变成 (12,0,0)，失去围绕父坐标原点旋转的效果。

文件内每个节点的局部变换按 T Rz S 构造，先缩放，再绕 Z 轴旋转，最后平移。角度使用弧度，平移使用本系列模型单位。数据结构中的矩阵按行存储，但数学对象仍作用于列向量；存储顺序不改变乘法含义。

glTF 2.0 §3.5.2 与 §3.5.3 也明确区分层级和局部 TRS，并规定父世界矩阵左乘子局部矩阵。这里借用这些概念核对组合规则，当前文本格式只支持 Z 轴旋转，不提供四元数、皮肤或材质解析。

文件顺序不能决定父子顺序

如果父节点在文件最后，按数组从头到尾直接求世界矩阵，子节点会读到尚未计算的父矩阵。要求父节点必须写在前面可以简化格式，但当前实现没有设置这个限制。

evaluate_scene 先检查所有父索引和网格引用，再建立 children 列表。所有根加入遍历队列；取出父节点后计算自身世界矩阵，并把子节点加入队尾。这样每个子节点求值时，父矩阵已经存在。

遍历结束后，访问数必须等于节点总数。一个没有根可达的环不会进入队列，即使其他分量存在正常根，也能通过总数不等识别。自身作为父节点则在索引检查时立即拒绝，不必等到遍历结束。

当前求值每次从头计算，不保存跨次调用的世界矩阵缓存。对最多 256 节点的实验，这使“修改父变换后忘记标记后代失效”的问题不进入实现。更大场景若引入脏标记，需要把后代矩阵和祖先子树包围盒的失效方向分别处理。

矩阵传播从父到子，子树范围合并却从子到父。求出全部节点世界矩阵后，按遍历顺序逆序合并，每个父节点读取的子树盒就已包含更深后代。两次遍历分别承担不同依赖，不能用一次随意的数组遍历替代。

轴对齐盒为什么需要八个角

AABB 用每一轴的最小、最大值描述范围。它的 low 和 high 是两个对角点，不代表变换后仍分别拥有所有轴的极值。

考虑立方体 [−1,1]³ 绕 Z 轴旋转 45°。旧 low=(−1,−1,−1) 和 high=(1,1,1) 的新 x 都为 0；只变这两点会得到近乎零的 x 宽度。然而另外两个 XY 角点分别到达 x=−√2 与 x=√2，正确宽度为 2√2。

本实验实际算得两角法宽度 2.2204460493×10⁻¹⁶，八角法宽度 2.82842712474619。前一个残差来自浮点三角函数，不是盒子真的还有一条极细宽度。

对仿射变换，输出坐标的每一分量都是输入坐标的线性组合加平移；在线段区间组成的盒子上，极值可以在角点取得。因此逐一变换八个角，再按轴取最小最大，就能包住整个变换后的局部盒：

b'_{\min,j}=\min_{i=0}^{7}(Wc_i)_j,\qquad b'_{\max,j}=\max_{i=0}^{7}(Wc_i)_j.

这套推理依赖仿射变换，没有经过透视除法。不能把包含相机投影的 PVW 直接当作同一种世界包围盒变换；跨越 w=0 的投影范围尤其不能用这个结论处理。

八角法得到的是“变换后的局部 AABB 的世界轴对齐外包盒”，一般不是网格顶点的最紧世界 AABB。局部盒可能包含大量没有几何的空间，旋转之后这些空白仍参与外包。本实验的矩形顶点恰好包含局部盒全部不同角点，所以逐顶点求界与八角法应相同；程序单独检查了这个特殊等价关系。

子树盒只合并同一空间的数据

实例盒先使用完整世界矩阵生成。父节点的子树盒从自己的实例盒开始，再合并全部子树盒。所有输入都处于世界空间，因此合并只需逐轴取最小值和最大值，不再次乘父矩阵。

若把已经变到世界的子盒再乘父矩阵，就会重复旋转或平移。另一种常见错误是把父局部盒和子世界盒直接合并；数值类型相同并不意味着坐标空间相同。

没有网格、也没有带几何后代的节点，其范围用空的 optional 表示。它不贡献范围。不能默认用原点盒代替空盒，否则一个位于 x=100 附近的分组会被无理由扩大到包含世界原点。

当前包围盒用于验收和显示，没有把它用作已实现的视锥剔除或碰撞判定。AABB 相交只说明范围重叠，不保证两个实际网格相交；作为粗筛之后还需与查询目的相符的精确阶段。

一份资源、两种父节点姿态

实验输入 scene-demo.txt 为：

CGSCENE1 3
-1 -1 10 0 0 0 1 1 1
0 0 2 0 0 0 1 1 1
0 0 -2 0 0 0.7853981633974483 0.5 1 1

第一行是版本标记与节点数。之后每条记录为 parent、mesh、tx、ty、tz、绕 Z 角度、sx、sy、sz，节点编号由记录顺序确定。父索引 −1 表示根，网格索引 −1 表示分组。文件不包含网格顶点；资源表由累计工程提供。

第一阶段父节点只平移 (10,0,0)。第二阶段只把父矩阵改成 T(10,0,0)Rz(π/2)，两个孩子的局部数据不变。橙色实例是未缩放方形；蓝色实例先沿 X 缩小为一半，再旋转 π/4、向父坐标负 X 平移 2。

图像由实际 CPU 光栅器生成，两块均为 256×256，相机在 (10,0,12) 看向 (10,0,0)，正交半高 5，近远距离 1、20。白线是实例世界盒，绿线是父子树世界盒；重合线由后绘制的绿色覆盖。这些是计算结果的诊断叠加线，直接使用码值，不参与面颜色的线性照明。

父姿态	橙色原点	蓝色原点	子树 XY 最小值	子树 XY 最大值
仅平移	(12,0)	(8,0)	(6.9393398282,−1.0606601718)	(13,1.0606601718)
平移和旋转	(10,2)	(10,−2)	(8.9393398282,−3.0606601718)	(11.0606601718,3)

所有 z 均为 0，因此这是嵌入三维场景的平面几何，包围盒在 Z 轴可以合法地零厚。蓝色实例沿任一 XY 轴的半范围为 (0.5+1)/√2=1.0606601718；这与程序八角结果独立计算出的表格一致。

检查器还逐顶点比较累计矩阵结果与手写父变换：第一阶段为 (10+x,y,z)，第二阶段为 (10−y,x,z)。两阶段最大误差分别为 8.8817841970×10⁻¹⁶ 和 0。交换记录位置，让父节点排在孩子之后，世界原点仍正确，避免只在恰好按拓扑排列的输入上通过。

导入失败应发生在使用之前

解析器限制 1–256 个节点，所有平移、角度和缩放数值绝对值不超过 1000，缩放分量在 [10⁻⁶,1000]。负缩放、零缩放属于当前格式的拒绝范围，不是仿射数学禁止它们。没有处理镜像绕序与零尺度表面，因此不默默接受再产生不明确结果。

语法读取成功之后还要执行场景求值校验：父索引、资源索引、自引用、环都不是浮点解析器能够判断的。文件末尾额外内容也拒绝，避免拼错字段数量却被静默忽略。返回的节点数组只有在 evaluate_scene 通过之后才进入绘制。

十个实际拒绝样本包括越界父索引、自父节点、环、缺失网格、NaN 矩阵、非仿射矩阵、过大节点数、截断记录、零缩放和额外数据。每个样本核对具体错误类别；帮助命令和缺参数失败另行运行。

内存接口可以接收一般仿射局部矩阵，并不要求每个矩阵可逆；文本解析器的正缩放规则比这个接口更窄。世界矩阵及变换结果另有限值与幅度检查。资源几何合法性依赖 Mesh 构造器，不能先任意修改公开顶点数组，再把先前构造验证当作永久保证。

复跑与练习

1 2	`make -C examples/computer-graphics check examples/computer-graphics/build/scene_check examples/computer-graphics/scene-demo.txt examples/computer-graphics/build`

代码为 scene.hpp 与 scene_check.cpp，结果为 scene-hierarchy.ppm。PNG 由该 PPM 转换；数值记录位于 writing-plans/computer-graphics/evidence/16-cpu.txt。实验不使用随机数、GPU 或性能计时。

练习一：父节点为 T(10,0,0)Rz(90°)，孩子局部平移改成 (3,1,0)，孩子原点的世界位置是多少？如果把平移直接相加会得到什么错误结果？

答案：先旋转 (3,1,0) 得到 (−1,3,0)，再平移得到 (9,3,0)。直接相加会得到 (13,1,0)，遗漏父旋转对局部位移的作用。

练习二：一个分组没有自身网格，只有位于 [99,101]³ 的孩子。把分组初始范围设成原点盒后再合并，得到什么？应怎样表示空范围？

答案：错误结果为 [0,101]³，凭空包含孩子之外的大片区域。应把初始范围表示为空，第一次合并直接取孩子范围，之后才做逐轴并集。

练习三：逐顶点求最紧世界盒比变换局部盒更紧，是否总应该使用前者？

答案：不是。前者每次通常要访问全部顶点，后者只变换八角。应按更新频率、网格规模及粗筛误判成本选择；保守盒可以多保留候选，但不能因求界错误漏掉真实几何。本篇没有性能测量，不能给出未经实验的速度倍数。