扫描线z缓存算法
Stephenxjc-千年一笑 2011年1月22日星期六
在附件中附有word的文档,其格式清晰,比较易于阅读。
1.1 基本思想
扫描线z缓存算法的思想是:在某个方向如y上扫描,每条扫描线需要一个z缓存和一个帧缓存,通过对比z缓存中的z与实际z的值,如果实际z大于z缓存中的值,则更新相应位置的帧缓存。
1.2 数据结构
1.2.1 边对
(其中点(a,b,c)为该边对所在三角形的法向量,k为相应边的斜率,sizey为整个场景的高度值,sizex为整个场景的x宽度值,height为图片y方向的像素数,width为图片x方向的像素数)
xl:左边对的x值
dxl:每个y方向的像素,左边x的变化量,公式dxl=-1/k*sizey/height
xr: 右边对的值
dxr:每个y方向的像素,右边x的变化量,公式dxr=-1/k*sizey/height
dy:扫描线行数,为边对总共跨越的扫描线数
zl:左边的z值
dzx:单位x长度,z上的变化量,公式dzx=-a/c
dzy:y方向,每个像素的z上的变化量,公式dzy=b/c*sizey/height
如附件中图一所示,以三角形ABC为例,可以建立两个边对
AB-AC一组:xl=A.x,dxl=(-1/AB的斜率)*sizey/height,rl=A.x,dxr=(-1/AC的斜率)*sizey/height,dy=(A.y-B.y)/height*sizey,zl=A.z,dzx=-a/c,dzy=b/c*sizey/height。注:求三角形的法向量,因为三角形是逆时针存储三点,所以,AB向量X AC向量,可以得到向量。
BC-AC一组:xl=B.x,dxl=(-1/BC的斜率)*sizey/height,rl=D.x,dxr=(-1/AC的斜率)*sizey/height,dy=(B.y-C.y)/height*sizey,zl=B.z,dzx=-a/c,dzy=b/c*sizey/height。 next:在边对中,为了后续采用链表,所以该结构中需要有一个指向下一个节点的指针
1.2.2 边对表
由边对构成,主要是存储边对,根据边对中的y最大值决定插入到哪一行中,如AB-AC边对,通过(A.y-ymin)*height/sizey。(其中ymin是整个场景中y的最小值),之后将AB-AC对添加到计算得到的下标所在队列中。如附件中图二所示.
1.2.3 活化边对队列
为动态的队列。针对它的操作主要是:
- 每条扫描线,需要将边对表中对应行的队列添加到活化队列中。
- 在扫描下一条扫描线时,需要将活化队列中的所有边对更新(包括边对中的xl,xr,dy,zl;更新的公式为xl+=dxl,xr+=dxr,dy--,zl+=dzx*dxl+dzy)。
- 需要将队列中结束的边对从活化队列中删除(结束状态的判断取决于dy,如果dy小于0,则结束)
1.3 算法
1. 遍历整个场景,将所有三角形转化为边对(在1.2.1边对中介绍),将边对添加到边表
2. Y方向上,按从大到小,对场景扫描
a) 查看当前y像素值所在边对表是否有队列,如果有,需要将该队列添加到活化边对队列中
b) 将z缓存中的所有数值为最小值
c) 遍历活化边对队列
i. 当前边对,x方向上从xl到xr
1. 计算z的值,如果z值比z缓存中的大,则更新z缓存中的z值和相应的帧缓存中的颜色数值
2. z+=dzx*sizex/width
d) 遍历活化边对队列
i. 更新值,xl+=dxl,xr+=dxr,dy--,zl+=dzx*dxl+dzy
ii. 如果dy<0,则将其从边对队列中删除
- 大小: 31.7 KB
- 大小: 36.7 KB
分享到:
相关推荐
图形学Z-buffer扫描线算法,输入为OBJ文件
矢量线的栅格化,矢量多边形的区域填充,画点,线,面,款选点,选择点线面,及栅格化,输出位图,曲线填充,缓冲区
15-内点表示的泛填充算法 16-扫描线种子填充算法 17-二维图形几何变换算法 18-Cohen-Sutherland裁剪算法 19-中点分割裁剪算法 20-Liang-Barsky算法 21-Sutherland-Hodgman裁剪算法 22-三维几何变换算法 23-三视图...
10.4线缓冲区边界生成算法 10.5面缓冲区边界生成算法 10.6多目标缓冲区合并算法 思考题 第11章网络分析算法 11.1概述 11.2网络数据模型 11.3路径分析算法 11.3.1单源点的最短路径 11.3.2单目标最短路径...
3.3仿射变换3.4地图投影变换3.4.1概述3.4.2地球椭球体的相关公式...Z曲线和Hibert曲线算法思考题第8章空间数据内插算法8.1概述8.1.1几何方法8.1.2统计方法8.1.3空间统计方法8.1.4函数方法8.1.5随机...
//z缓冲区算法的一个简化的用于演示的程序 //检查点(xp,yp)在直线 (x0,y0)->(x1,y1)那一侧? //画一个四边形,顶点坐标在x,y数组 //画互相垂直的十字线 //正方形绕自己中心旋转角度α,同时放大cosα+sinα //给出画...
实现 Z 缓冲区算法以去除一组立方体的隐藏表面。 ###指示 每个文件夹都有两个子文件夹——Given——教授提供的原始源代码。 -工作- 最终的工作代码。 给定的代码仅适用于 Windows,因为它依赖于 Windows API。...
多线程版本的 RAR 压缩算法提高了在有数个 CPU、多核心 CPU 和使用超线 程技术的处理器的计算机上的压缩速度。多线程默认被启用,但是你可以在 “设置”对话框的“常规”部分中禁用它。 在命令行...
A、音箱 B、绘图仪 C、打印机 D、扫描仪 31.启动Windows98中文版后,下列中___C___的图标不是常见的图标。 A、我的电脑 B、回收站 C、资源管理器 D、收件箱 32.多媒体电脑是指 __B___ 。 A、专供家庭娱乐用的电脑 B...
--horiz-scan* --verti-scan 点阵字符扫描模式; --h-to-l* --l-to-h 点阵字符在字节的存储方式; --font-high=[font_h] 点阵字符的高与宽(应当相等)。 注:* 是默认项。 例子:font /my.hex font --bin --...