4.5mooc光栅扫描算法小结.pdf

光栅扫描算法小结 1、直线段的扫描转换算法 这是一维图形的显示基础 （1）DDA算法主要利用了直线的斜截式方程（y=kx+b）,在 这个算法里引进了增量的思想，结果把一个乘法和加法 变成一个加法 （2）中点法是采用的直线的一般式方程，也采用了增量的 思想，比DDA算法的优点是采用了整数加法 （3）Bresenham算法也采用了增量和整数算法，优点是这个 算法还能用于其它二次曲线 2、多边形的扫描转换和区域填充 如何把边界表示的多边形转换成由像素逐点描述的多边形 这是二维图形显示的基础 有四个步骤：求交、排序、配对、填色。这里引进了一个新 的思想—图形的连贯性。手段就是利用增量算法和特殊的数 据结构（多边形y表、边y表、活化多边形表、活化边表）， 2个指针数组和2个指针链表 3、直线和多边形裁剪 关于裁剪算法主要讲了两个经典算法： cohen-Sutherland算法、梁-barsky算法 cohen-Sutherland算法的核心思想是编码。把屏幕（窗口， 场景空间）分成9个部分，用4位编码来描述这9个区域，通 过4位编码的“与”、“或”运算来判断直线段是否在窗口 内或外 梁算法主要的思想： （1）直线方程用参数方程表示 （2）把被裁剪的直线段看成是一条有方向的线段，把窗口 的四条边分成两类：入边和出边 这也是中国人的算法第一次出现在了所有图形学教科书都 必须提的一个算法。这就叫原始创新！ 4、走样、反走样 因为用离散量表示连续量，有限的表示无限的自然会导致一 些失真，这种现象称为走样 反走样主要有三种方法： 提高分辨率 区域采样 加权区域采样。 提高分辨率无非是把分辨率增加，这样可以提高反走样的效果 ；但这个方法是有物理上的限制的—分辨率不能无限增加 区域采样算法是在关键的直线段、关键的区域上绘制的时候 并非非黑即白，可以把关键部位变得模糊一点，有颜色的过 渡区域，这样会产生一种好的视觉效果 加权区域是不但要考虑区域采样，而且要考虑不同区域的权 重，用积分、滤波等技巧来做 5、消隐 在绘制场景时消除被遮挡的不可见的线或面，称作消除隐藏 线和隐藏面，简称为消隐 消隐算法按消隐空间分类： （1）物体空间 以场景中的物体为处理单元 （2 ）图像空间 以屏幕窗口内的每个像素为处理单元 首先介绍了经典的z-buffer算法。为了避免一个z-buffer二 维数组的开销，引进了单个变量的z-buffer算法，把数组变 成了单个变量 单个变量的z-buffer算法的主要问题是要不断地判一个点 是否在多边形内。为了解决这个问题，又讲了3个算法：即 如何判点在多边形内部，有射线法、代数弧长累加法、以 顶点符号为基础的弧长累加方法。 区间扫描线算法：发现扫描线和多边形的交点把扫描线分成 若干区间，每个区间只有一个多边形可以显示。利用这个特 点可以把逐点处理变成逐段处理，提高了算法效率 Warnock消隐算法：采用了分而治之的思想，利用了堆栈的数 据结构 把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口 内目标足够简单，可以显示为止 核心思想 （1）增量思想：通过增量算法可以减少计算量 （2 ）编码思想 （3）符号判别－ 整数算法 尽可能的提高底层算法的效 率，底层上提高效率才是真正解决问题 核心思想 （4 ）图形连贯性：利用连贯性可以大大减少计算量 （5）分而治之：把一个复杂对象进行分块，分到足够简单 再进行处理