计算机图形学上机作业日期:2014.04.04
扫描线Z-Buffer算法
姓名: 学号:
日期:2014/04/04 邮箱:
作业描述
实现扫描线Z-Buffer算法
开发环境
硬件环境:Intel(R) Core(TM) i7-4770 CPU@3.40GHz,RAM 8.00GB 操作系统:Window7专业版 64位 Sp1 集成开发环境:Visual Studio2010中文版(C++)
数据结构
1.主要数据结构
\头文件里定义了活化边表结构,实现活化边表及其相关操作; \头文件里定义了分类边表结构;
\头文件里定义了分类多边形表结构,同时也充当了程序运行中活化多边形表的角色,因为这两种结构存储信息相同(除dy外);
\头文件定义三角形结构,并保存三角形面片的颜色,为了简化问题,读入的obj文件只包括三角形面片;
\头文件定义了一个三角形组结构,存储多个三角形;
2. 辅助类
\头文件定义了一个image类,即存储图像所有像素颜色信息; \头文件定义了一个向量类,用于表示三维向量或点;
1 / 5
计算机图形学上机作业日期:2014.04.04
3. 初始化数据结构
\头文件中定义了一个初始化类,用于读取obj文件,并构造分类多边形表和分类边表,除此之外,还初始化了图像像素信息;
4. main函数
main函数首先调用scene_parser初始化,然后执行主要的扫描线z-buffer算法。
算法优化及加速说明
1.主要数据结构用STL中的vector容器替代了传统的链表结构: a. 节省了链表带来的大量额外空间开销,并简化操作; 2.边排序预处理:
b. 对分类边表中的边进行了预先排序,大大提高后续活化边表中寻找配对边的效率,由于排序采用的是vector现成的sort函数,操作简单并且有天然的速度优势。 3.去除后向面处理:
c. 一般几何体是连续的,如果视线方向与面片法向量夹角小于90度,该面片为后向面,可以直接被排除,夹角的大小只需要通过计算向量的点积,这是相当容易的,于是在进行z-buffer算法前,去除后向面处理可直接“过滤”大约一半的面——空间复杂度和时间复杂度均降为1/2!!!
程序说明
1.程序运行采用命令行方式,命令行格式如下:
Z-buffer.exe -input cube.obj -width 400 -height 400 -output cube_z.tga -scale 150 -normal
其中,cube.obj为输入文件名,cube_z.tga为输出的图像名,width和height分别表示输出图像的宽和高,-scale表示输入的obj几何体需要扩大scale倍来fit像素空间大小,-normal表示是否运用上面的第3条“去除后向面处理”,如果运用该加速方法,则命令行后面加-normal,这样处理之后,输出的图像名会自动在前面加\,即自动变成normal_cube_z.tga。
2.本程序对面片着色采用两种方法:rand_color和normal_color rand_color表示面片读入时对其随机着色;
2 / 5
计算机图形学上机作业日期:2014.04.04
normal_color表示面片的颜色值等于该面片单位法向量的绝对值(这样,每个面片的颜色都是固定的,且与其法向相关,这样做的目的是验证“算法优化的第3条处理方法”删除的是否是后向面)。
为了简化程序,我就没有再在命令行里设置了,请直接定位到scene_parser.cpp文件的第108至115行自行处理(那里有注释说明),对应的代码段截图如下:
3.关于本程序读入obj文件的说明
由于没必要花太多精力在完善C++读obj文件信息的程序上,所以本程序输入的obj文件中请务必只包含点(v)和面(f)信息,其它信息均为多余,包括注释段也为多余;另外请在maya或3dmax中将obj文件转为“全为三角形”输出。 其它一些obj文件的格式处理都与本程序无关。
结果测试
本程序附带了6个obj测试文件,所有的输出图像结果及文件均包含在\目录下,其中包含三个文件夹:
1. “opengl下的模型图”:保存了在opengl或光线追踪算法或3dmax中得到的模型图; 2.“Z-buffer图_随机color”:采用随机着色得到的12幅图像,包含“去除后向面处理”的6张图(图像名前面有normal_)及未处理的6张图;
3.“Z-buffer图_normal_color”:与第2个文件夹类似,只是采用的是normal_color。
下表中列出了一些数据,表明在运用“去除后向面处理”法后,减少处理面片的数量,间接验证了空间复杂度和时间复杂度均可减半的结论。 Obj文件名 模型内容 总面片数 去除后向面后,实际面片比 处理的面片数 3 / 5