Zbuffer扫描线算法

计算机图形学上机作业日期: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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4