课程名称：计算机图形学（研究生）
报告主题：不同ZBuffer 算法的实现和效率比较
提交日期：2023 年 1 月 11 日
一、 实现功能及运行说明
因为我个人想借这个项目的机会进行一些底层类的实现，为之后的希望能完成的图形引擎开发工作打一下基础，所以本项目没有依赖除了 C++标准库之外的其他库，一些基础的功能由自己个性化实现，比如说向量 Vector 的管理和计算
（可以管理坐标、颜色、法向等信息），Obj 格式的 Mesh 读入，便于本项目展示的简单的坐标变换（有参考网络上项目的思路），四叉树以及八叉树的建立和管理等。
（一）主要算法实现了以下几种 ZBuffer：
- 普通的Zbufer 算法（Naive ZBuffer）
- 扫描线Zbuffer 算法（ScanLine ZBuffer）
- 简单版本的层次ZBuffer 算法（Naive ZBuffer + Hierarchical ZBuffer）
- 完整版本的层次 Zbuffer 算法（Naive ZBuffer + Hierarchical ZBuffer + Octree Scene）
（二）为了支持效果自己完成的一些功能
- 读入OBJ 格式的 Mesh 文件，且同时支持三角形和四边形面片的读入，并且支持不同格式的 OBJ 文件，比如只包含坐标、包含坐标和纹理坐标和法向等。
- 为了方便展示不同尺度的模型，实现一个基于窗口大小进行的简单的坐标变换，保证任何 Mesh 都能完整展示在窗口中。
- 简单的模型着色功能，支持基于点光源的 Diffuse 和随机面片颜色两种着色方式。
- 实现了四叉树和八叉树的建立和管理，分别用于 Hierarchical 的 ZBuffer和场景面片的管理。
- 简单的向量管理类，支持不同的向量计算。
- 受渲染管线中Fragment Shader 的启发，建立了面向对象的场景面片管理， 包含面片的坐标、Z 值、颜色等信息。
- 在自己思考下加入了ZBuffer 遍历中的提前剪枝。
二、 开发与运行环境
操作系统：Microsoft Windows 10 Pro 64bit CPU：Intel(R) i5-12400F 2.50 GHz
内存：DDR4 8G
IDE：Microsoft Visual Studio 2022
配置平台：Release X64
正常运行效果效果演示：
三、 项目架构及数据面向对象管理
本实验使用 C++面向对象式地进行开发，为了更形象地展示，其中项目各个类之间的依赖关系和组织架构我画了一张图来展示：
得益于面向对象的管理，main 函数的结构非常清晰：
其中各个类实现的功能基本都可以从类名称清晰的看出，源代码的类定义中也有相关注释，在此就不再赘述，需要解释的一点是：我使用了一个 Fragment 类来管理光栅化之后的单个面片，这个面片与 Model 中的 Face 的区别是，Face 包含的是点坐标、法向等信息的索引值，而 Fragment 类中则直接记录的是面片的顶点坐标，并且是光栅化之后的像素坐标，该类同时还支持根据重心坐标对深度值进行插值，从而得到某一个具体像素处的深度值。
四、 实验步骤细节及问题解决
具体的程序实现细节过于复杂，我不会在此一一赘述，但是在这个部分我会把其中几个我认为有价值的点拿出来简单展示一下。
1. 八叉树和层次 ZBuffer 的对应问题
在实现完整版本的层次 ZBuffer 时，需要同时管理场景面片的八叉树，和ZBuffer 的四叉树两个数据结构，并且需要遍历八叉树，使用层次 ZBuffer 进行深度测试，在这里的实现细节时，需要将八叉树的遍历和层次 ZBuffer 的遍历同步进行，为了实现这种遍历，在构建八叉树的时候，我用的是下面这种顺序：
从 Z 轴来看，前面四个子节点索引分别是 0，2，4，6，后面的子节点则是 1， 3，5，7。这样，在遍历的时候，如果需要进入到下一层子节点，就只需要从 0-7 遍历，而层次ZBuffer 对应的子节点下表只需要用八叉树下标/2 做寻址即可。
另外一个细节是，在简单模式下的 ZBuffer，如果只有左右两个像素需要剖分，就只会增加两个子节点，而不是严格意义上的四叉树，这样会减小遍历的压力，但在完整版本下，为了保证和八叉树的同步，我把层次ZBuffer 做成了严格的四叉树，没有子节点的地方使用空指针 NULL 占位。
上图的情况是由于八叉树的子节点索引和层次 ZBuffer 的子节点索引没有在空间上对齐，导致遍历的时候出现整个子节点的面片都通不过深度测试（其实是因为xy 坐标不在范围内被深度测试强行拒绝）。
2. 层次 ZBuffer 绘制单个面片时的提前剪枝
在寻找到层次 ZBuffer 无法拒绝，但是子节点又无法完全包裹面片时，就需要对面片进行绘制，如下图。但是我实现时发现这样非常非常耗时，具体的时间对比在下一部分。因此我加入了一种剪枝方式。层次ZBuffer 结构本身包含的剪枝是如果面片没有通过较大块的深度测试，就直接剪枝这块 Buffer，但是在绘制时，同样需要剪枝。如下图，由于这个面片跨越四个子节点，因此这四个节点都需要对该面片进行绘制，但是再向下一层，就有一些 Buffer 块不包含面片了，我在此时对这些Buffer 块进行剪枝，程序运行的速度大大加快。
具体实现代码：
3. ScanLine 的边界控制问题
因为 ScanLine 在切换下一条扫描线的时候需要使用提前计算好的 dx、dy、dzx、dzy 等递增量进行数据的递增，因此非常受到数据精度的影响，需要使用float 类型储存数据，但是由于光栅化为单个像素，又必须有 dy 等 int 类型的变量，在计算 dy 时，我一开始采用的是 round 函数进行绘制，但是这样可能会导致由于递增量的误差，在最后一条线绘制的时候，左边的 x 值已经超过了右边的x 值导致绘制错误，但是使用 ceil-floor 的方式又可能会在边界处绘制超过的像素部分，因此我最后对上界和下界都使用了floor 取整。
在实践中由于数据精度问题还导致下面这种绘制错误的产生：
这个问题的出现是由于在计算 dx 时，为了保证精度，我首先使用了下图中上面那种方式计算，这样会导致对于某些几乎平行于 x 轴，但是又没有被浮点判断消除掉的线，计算出的 dx 值会非常大，这就导致递增计算时出现很大的误差， 最终我改为了下图中下面那种计算方法。
另外，ScanLine 算法中的边界控制这部分我认为说起来容易但是最容易出错，在实践中也耗费了我很多时间。比如，在判断活化边的结束条件部分我也出现了一些问题，一开始我担心如果用 dy<0 来作为删除活化边的条件，会有一些情况整个三角形太小只占了一个元素，但是思考后认为应该用 dy<0，因为只占一个元素的情况应该初始 dy=0。而当活化边一边 dy=0 的时候，就应该去对应的活化多边形中寻找下一条边替代并更新活化边的 dxl 和 dxr 了，这样才能保证活化边不被删除且下一次绘制时已经使用了新的递增量。
五、 实验结果与效率对比分析
（一） 实验结果展示
在不同着色模型下不同模型的绘制结果展示：
（二） 算法效率对比分析
在 800*600 的分辨率下，分别进行了不同面片数的 Mesh 绘制，并记录下不同算法的耗时（ms）：（为了方便比较这里把所有面片都预先转化成三角形模式，但是四边形也可以绘制）
而在 1600*1200 的分辨率下：
可以看出相比于ScanLine Zbuffer 算法，层次 ZBuffer 在面片较少时是没有太多优势的，但是在面片数逐渐增加时，其优势就逐渐体现出来了，并且，面片越多，完整的层次ZBuffer 相较于没有Octree 的简单版本优势越大。另外，没有额外剪枝的Hierarchical ZBuffer 算法速度非常慢，此处的ZBuffer 不是指的是在遍历过程中，由于面片被较大的ZBuffer 块深度测试拒绝而导致的剪枝，而是在上一部分提出的，遍历时根据 Zbuffer 覆盖范围和面片覆盖范围比较而进行的剪枝。
另外，在实验中，我发现层次ZBuffer 对于普通的Naïve ZBuffer 加速比效果不太理想，即使我同时绘制了五个模型也没有很好的加速效果，我推测可能是由于目前的场景还是不够复杂，没有很多那种被大范围遮挡的情况，而此时不需要遍历复杂的数据结构的Naïve ZBuffer 就稍占据了一些优势。
六、 总结与改进方向
通过本次实验，我对几种基础的 ZBuffer 算法都有了更深入的理解，“纸上得来终觉浅，绝知此事要躬行”。亲自上手编程实现算法和仅仅通过眼睛学习效果是完全不同的，在这次实践中，我也发现自己对于一些编程上的技巧，数据结构的组织等仍有进步的空间，需要继续努力。我也深刻地意识到面向对象的编程的优势，将需要实现的功能拆分成不同模块，能大大提高编程和Debug 的效率。
在具体实践的时候，ScanLine 耗费了我最多的时间和经历，主要因为这个算法个性化的程度比较高，相比于层次ZBuffer 本质上是利用到八叉树和四叉树， 结构比较清晰，ScanLine 算法则需要花费很多精力在控制边界调节、控制浮点数精度等细节上面。另外从我的实验结果来看，ScanLine 算法由于是用递增量去控制的，无论如何都会存在误差的累计，绘制的效果在某些情况下不太理想。
但同时我也发现了很多程序中存在的问题，有一些已经解决了，在上文中也已经说明，但我认为还有一些可以改进的方向，只是由于事件原因没能实践。比如说，可以考虑使用 GPU 硬件加速八叉树和四叉树的结构，比如并行计算同一个八叉树的不同子节点，这样应该会大大加快程序访问八叉树的速度。
另外，使用层次Zbuffer 绘制面片时，如果某个层次Zbuffer 不能拒绝面片， 但是单个子节点又都不能包含整个面片，那就只能从这个节点开始逐级向下绘制这个面片，但是这样可能会导致拒绝较大面片的效率不高，我认为后续可以进行改进的方法是对面片进行切割，因为这个阶段使用到的面片都是已经光栅化之后的屏幕空间的面片了，再进行平行于 xy 轴的面片切割应该不难实现，切割后就可以用切割的面片分别与子节点进行深度测试了。
