解读论文《A Hierarchical 3D Gaussian Representation for Real-Time Rendering of Very Large Datasets》

一、 图形学相关基础知识

（一）Level of Detail（LOD）的原理

在计算机图形学中，LOD（Level of Detail）技术是一种用于提高图形渲染性能的技术。
核心思想：在渲染三维场景时，根据对象与观察者的距离选择不同的细节层次进行渲染。LOD技术通过使用几何简化和纹理替换等方法来减少远离观察者的对象的计算量，从而提高整体渲染速度和性能，平衡渲染速度和渲染质量。

如图所示，一个三维模型的LOD分为若干个层次，每个层次的模型细节不同，即模型体网格数量不同，对应着不同的距离或缩放级别。在较远的距离或较小的缩放级别下，模型的细节较低，只显示一些简化的几何形状，以达到更高的渲染性能；而在较近的距离或较大的缩放级别下，模型的细节较高，可以显示更加精细的几何细节。

（二）AABB框与BVH树

1. AABB框： axis-aligned bounding box，轴对齐边界框。一个3D的AABB框就是一个六面体，每条边都平行于一个坐标平面。框不一定是一个立方体。如图所示：
2. BVH树： 八叉树（Oct-tree）根据空间来划分三维空间，BVH树通过物体来划分, 即划分的不是空间，是把整个物体分为两个部分。步骤如下：
a. 找到一个bbox包含所有物体；
b.递归地把盒子内所有物体分为两个部分；
c. 重新计算每一部分的bbox；
d. 重复以上过程直到停止。
3. BVH树生成过程：
a. 首先对所有物体找一个盒子把它们全部包围起来，如AABB框，对应于根节点；

b. 把框内的所有物体分成两部分，左边一部分和右边一部分，具体怎么划分可以根据具体任务进行定义，生成两个叶子结点；

c. 对上边划分的两部分的物体，分别重新求它们各自的包围盒（图中灰色部分，仍以AABB框为例）。对每一个部分继续划分；

d. 重复以上过程直到停止（停止条件通常为一个包围盒里最多只有n个物体，n∈R，图中n=5）。

4. BVH树的性质：
a. BVH树中的每个物体只可能出现在一个格子里。
b. 划分速度快。（把物体分成两堆很容易实现，其次，在重新求包围盒时，只需要求每一堆物体的最大最小x，y，z坐标即可）
c. 不同的bbox有可能相交，对空间并不是严格意义上的划分开了。

5. 实际上如何有效划分每个节点？
答：选择一个维度（轴）进行划分。有两种策略：
策略1-平均划分法（mean split)： 每次都在所有物体最长的轴的中间位置进行划分。（适用于所有场景都在一个长条里，划分后可以保证节点均匀分布。）
策略2-中值划分法（median split，最常用)： 对所有物体沿最长轴进行排序，每次选择中间物体的位置进行划分。（适用于所有场景都在一个长条里，且有好多物体都挤在左边，只有一个物体在右边。这样划分后，可以尽量保证两边的物体数量相等，划分后BVH树是一棵平衡二叉树，这样树的最大深度小，平均搜索次数少。）

（三）扫描线（scanline）和天空盒（skybox）

1. 扫描线： 从图形的y最小值到y最大值依次进行y上的遍历，遍历的每个y=c这条直线称为扫描线。换句话说，用一条线从下往上对图形进行扫描，这条线就叫扫描线。

2. 天空盒： 一个包裹整个场景的立方体，由6个图像构成一个环绕的环境，给人一种所在的场景比实际的要大得多的幻觉。

展开形式：

如果把这六个面折叠成一个立方体，就可以模拟一个无限远的场景：

使用天空盒的作用：
a. 模拟无限远场景：无论在场景中怎么移动，背景都不会显得离得更近或更远；
b. 提高渲染效率：与用实际几何体和大量细节来模拟远景相比，使用天空盒可以显著减少计算量，因为只需要绘制几个简单的平面，而不需要处理复杂的三维模型；
c. 无缝衔接的视觉效果：天空盒的六个面上的纹理无缝连接，不会看到明显的边界或接缝。这种无缝连接的视觉效果让人们感觉环境是连续和自然的。
d. 减少资源消耗：天空盒只使用一个立方体，可以显著减少显存和计算资源的使用。

二、算法总览

1. 标定相机

2. 场景分块

3. 块内LOD渲染

4. 层次融合

5. 渲染整个场景

三、LOD的要求

1. 找出候选的3DGS基元，并定义如何将他们合并到中间节点
2. 一种有效的策略，来选择层次，同时兼顾渲染质量和速度
3. 层次结构间的平滑过度策略，不能产生伪影

四、LOD的实现策略（核心）

1. 使用固定数量的，少量3DGS去优化整个场景，生成最初的高斯球

2. 基于树结构，自底向上构建

3. 每个节点代表一个3DGS基元，其中叶子结点是3DGS最初产生的高斯球，内部节点是融合后的3D高斯球

4. 内部节点的要求：
   a. 保持与叶节点相同的快速栅格化流程
   b. 尽可能的描述子节点的外观

5. 内部节点融合（μ、∑、α、SH）：
   a. 均值μ和协方差∑，最小化加权3D KL散度（合并后的节点和其子节点之间）
   
   其中wi是归一化后的权重，归一化前的原始权重wi’与每个子节点对其创建的父节点的贡献成正比。

   b. 计算原始权重wi’（即每个高斯球的贡献）
   i. 考虑一个独立的高斯球gi，它对一个像素位置（x,y）的贡献(contribution)为：
   
   其中：
   
   则gi对整张图像的贡献为：
   
   这里利用高斯函数性质：
   
   
   

ii. 简化高斯球，假设他们都是各向同性的，且几乎没有重叠。在这种情况下，要确保父节点的高斯对于整张图的贡献，等于他的两个子节点的高斯贡献之和。即：Cp=C1+C2。利用以上计算结果和简化结果，忽略与权重无关的常量和颜色，可以得到权重为：

iii. 在实际计算中不使用协方差的行列式，使用高斯球的尺度S进行计算：Wi’=OiSi
(从权重的表达式可以看出，一个高斯球对于整张图片的贡献与它的透明度α和尺度S成正比。这里可以利用极限的思想，考虑两个高斯球，其中一个透明度几乎为1，另一个几乎为0，那么最终看到的图像肯定是透明度接近于1的那个高斯球占据主导。再比如两个高斯球透明度一样的情况下，尺度或者表面积大的那个高斯球，投影后对整张图的影响更大。)

iv. 同理，将SH系数合并：

v. 同理，将不透明度合并，这里需要注意，加权平均的合并策略会改变不透明度的语义，如下图所示：

红色和蓝色是两个叶子结点，他两个的单独的不透明度如d所示，α-belnding后©如e所示，使用上述方式合并后(g)如(f)所示。这里超过1的部分就当做是1。
到此为止，中间节点的合并策略有了。

五、构建3DGS的LOD结构

1. 对块内所有高斯球使用AABB框，以中值划分法构建BVH树；
2. 从叶子结点开始，自底向上融合高斯球；
3. 根据LOD实现策略，计算中间节点高斯球的属性。

到此为止，每个块内都生成了一个LOD结构。

六、cut选择和level转换

（一）cut选择

1. 定义：给定某一视图V 时，选择树结构中的哪些节点进行渲染，这些被选择的节点的集合成为一个cut。
   请注意，一个cut内的节点不一定都在同一个level，也就是树的同一层。
2. 选择策略：给定一个视图V，选择那些保持渲染质量的同时，渲染速度最快的那些节点。
3. 具体选择过程：
   a. 定义节点n的粒度ε(n):一个节点n的粒度，是它在给定视图V上投影后在屏幕上的大小；
   b. 取出一个节点中包含的所有叶子结点，将它们按照自身bbox的最长轴进行投影，计算投影后的尺寸大小是否小于给定的目标粒度τ_ε；（如 1 pixel）
   c. 如果节点n的粒度小于目标粒度，即ε(n)<τ_ε ，但其父节点的粒度大于目标粒度，那么当前节点n就被选择在cut中，如图绿色轨迹所示。
   

（二）level转换（线性插值）

1. 作用：实现层次间（父节点到子节点）的平滑过度。先生成两个与紫色具有相同属性的高斯球（α除外），然后分别插值到他们各自的属性。
   

2. 如果当前cut的节点不再满足当前视图中目标粒度的要求（比如上一张视图中，根据目标粒度选了一个cut，换到下一张视图中，这个cut内的节点有些不再满足粒度要求），那么就通过插值，生成新的节点。插值是在节点n和其父节点之间。

3. 插值权重：
   

4. 位置、SH系数通过插值计算；

5. 插值协方差前的预处理：
   作者实验发现，分别对S和R插值，效果比直接对协方差矩阵更好。然而，即使两个高斯球的S, R完全不一样，他们的形状也会一样。即：高斯球的旋转轴定义不明确会导致在插值协方差（R\S）时出现不同的结果。如下图所示，两个高斯球的协方差完全一样，但如果对旋转轴定义不明确，会导致在插值时出现完全不一样的结果。
   
   为了解决这个问题，作者在生成细节层次结构（LOD）的时候，从根节点开始，递归地为每个子节点执行了“方向匹配”。
   方向匹配：实现两个3D高斯椭球的方向匹配，从而在空间中对齐它们的方向和位置。
   引用论文里的一句话：It minimizes the relative rotation between the child node and its parent.
   方向匹配的大致流程：
   a) 特征提取：提取3D高斯球的特征（中心位置、主轴方向、各轴方差）
   b) 计算描述符：计算协方差矩阵的特征值和特征向量（特征向量指示高斯球主轴方向，特征值代表每个轴的方差）
   c) 匹配：比较特征向量，计算旋转矩阵，使一个椭球的主轴方向对齐到另一个椭球的主轴方向
   从根节点开始，使得每一个子节点都与其父节点方向匹配，最小化它们的旋转差异。执行完毕后，每一个块内的层次结构中，所有的3DGS球，方向都基本一致。

6. 插值不透明度的预处理：要保证插值后生成的两个高斯球合成的颜色与父节点相同。
   so that the resulting blending of the overlapping Gaussians gives the same result as the parent at the start of the transition.
   必要性：如果插值后两个高斯的叠加颜色，与父节点不同，观察者可能会感到突兀和不自然。
   计算不透明度：
   

左侧：父节点的颜色（贡献）；右侧：两个子节点通过α混合后的（贡献）。

上面公式来自于α-blending：

解得：

其中：αi是两个真是存在的子节点的不透明度，α’是开始转换时生成的两个节点的不透明度，α(t)是中间插值节点的高斯，t是插值权重。

七、LOD结构的优化和压缩

（一）优化

1. 中间节点本身就是一个3DGS球，因此也是可以被优化的，即不能在创建后就固定住。要实现这一点，就需要保证梯度能够回传到中间节点。

2. 图形学中的LOD要根据距离选择细节层次：从远处观看时渲染场景的简化版本。层次结构中的目标颗粒度可以实现这个效果。如下图所示：
   

3. 层次结构的优化：
   a. 随机选择一组图像和一个目标粒度，图像和目标粒度决定了相应的层次结构中的一个cut；
   b. 为实现高质量采样，优化各级层次结构，定义标准随机变量
   

采样的目标粒度用如下公式计算：

c. 在优化过程中，cut的选择策略和插值都会被用到；
为了同时优化父节点和子节点，梯度会同时传递到两层结构。这也就意味着梯度会传递到中间插值的节点以及α’。
这会导致一个问题：在优化高层次LOD时，可能会由于插值导致叶节点的质量降低。因此在优化过程中，不优化叶子结点。

4. 此外，作者在层次结构中使用了Mip-splatting的EWA滤波来抗锯齿。

（二）压缩

为了避免内存开销过大，以及，避免父节点尺寸仅仅比子节点稍微大一点点，这会导致这些节点很难被优化到。为了解决这个问题，作者对生成的树结构进行稀疏化。
1. 将叶节点做标记，防止被删除；
2. 在所有训练图像中，以目标粒度为3像素，寻找所有cut的集合成为cut1；
3. 在集合cut1中找到最底层的节点，产生cut2，cut2中的节点就代表在所选粒度下，细节最丰富的节点；
4. 删除叶节点和cut2节点之间的所有节点；
5. 将目标粒度*2，重复上述过程，直到目标粒度达到一半像素。

八、超大场景训练（稀疏）

首先对所有数据分块：步行捕获的数据，块大小是50*50；骑车：100 *100

（一）粗初始化和块细分

1. 粗初始化：
   a. 对整个数据集所有图像做标定；
   b. 训练整个场景的3DGS，并创建skybox，在10倍场景直径的球体上放置100k个3DGS基元，渲染天空；
   在这个过程中，不使用高斯致密化（克隆、分裂），也不优化位置，因为作者认为SFM的点的位置就已经很好了。
   训练完后得到整个场景的coarse scaffold，粗框架。
2. 块细分：
   在超大场景中，SFM的点会溢出内存，因此粗优化本身也可以分块，中间的部分结果可以输出到磁盘。
   块内相机选择：所有在块边界内的相机，或者是相机在两倍块边界内，并在当前块内有超过50个SFM点的相机。

接下来的内容，都是基于超大场景，即在SFM阶段就开始分块的情形。假设每个块都独立获取了SFM的点。

（二）块内训练：

1. 每个块单独训练coarse scaffold，即粗框架；
2. 基于此创建LOD层次结构；
3. 优化：
   a. 对于块内的训练使用3DGS的策略+Mip-splatting；
   b. 对于块外的内容（即其他块的粗糙3DGS和skybox），进行一个小的临时优化，只优化α和SH；
4. 在致密化时，不使用原始3DGS的平均梯度，而用最大梯度，原因有如下两点：
   a. 无界场景下，使用平均梯度将使3DGS不停分裂，不管它是否对细节建模得足够精细；
   b. 数据的稀疏，相机的分散会导致致密化时不会考虑全局；
   

（三）合并

由于在块细分的时候，块内的相机会看到相邻块的，粗框架的点，因此在合并时，当前块内的层次结构，可能在其他块里。
1. Root：在合并时，为全局创建一个根节点；
2. Update：通过目标颗粒度，来选择cut，并渲染（间隔2帧）；
3. Cleanup：如果一个高斯球与块