第二章 光栅图形学.ppt

计算机图形学翁彬 第2章光栅图形学 什么是光栅图形学 光栅显示器 图形光栅化 光栅化图形的处理 光栅图形学的研究内容2 1直线段的扫描转换算法2 2圆弧的扫描转换算法2 3多边形的扫描转换与区域填充2 4字符2 5裁剪2 6反走样2 7消隐 2 1直线段的扫描转换算法 直线的扫描转换 确定最佳逼近于该直线的一组象素 并且按扫描线顺序 对这些象素进行写操作 三个常用算法 数值微分法 DDA 中点画线法Bresenham算法 2 1 1数值微分 DDA 法 基本思想已知过端点的直线段L 直线斜率为从的左端点开始 向右端点步进 步长 1 个象素 计算相应的y坐标 取象素点 x round y 作为当前点的坐标 这种方法直观 但效率太低 因为每一步需要一次浮点乘法 一次加法和一次舍入运算 2 1 1数值微分 DDA 法 作为最底层的光栅图形算法 在通常的CAD 图形系统中 会被大量应用 因此 哪怕节约一个加法或减法 也是很了不起的改进 由此出发点 导致增量算法的思想 增量算法 在一个迭代算法中 如果每一步的x y值是用前一步的值加上一个增量来获得 则称为增量算法 2 1 1数值微分 DDA 法 计算当时 即 当x每递增1 y递增k 即直线斜率 2 1 1数值微分 DDA 法 例 画直线段k 0 4xyint y 0 5 y 0 50000注 网格点表示象素 2 1 1数值微分 DDA 法 例 画直线段xint y 0 5 y 0 5000100 4 0 5210 8 0 5311 2 0 5421 6 0 5522 0 0 5注 网格点表示象素 2 1 1数值微分 DDA 法 voidDDALine intx0 inty0 intx1 inty1 intcolor intx floatdx dy y k dx x1 x0 dy y1 y0 k dy dx y y0 for x x0 x x1 x drawpixel x int y 0 5 color y y k 2 1 1数值微分 DDA 法 注意上述分析的算法仅适用于 k 1的情形 在这种情况下 x每增加1 y最多增加1 问题 当 k 1时 会如何 答案见下页 k 1示意图 2 1 1数值微分 DDA 法 当 k 1时 必须把x y地位互换 y每增加1 x相应增加1 k 2 1 1数值微分 DDA 法 缺点 在此算法中 y k必须是float 且每一步都必须对y进行舍入取整 不利于硬件实现 DDA算法小结 直线的显式方程 两点式 象素是整数的 x每次增加1 取象素点 x round y 最简单算法效率低改进为增量算法 当x每递增1 y递增k 采用增量思想的DDA算法 每计算一个象素 只需计算一个加法 是否最优 如非最优 如何改进 目标 进一步将一个加法改为一个整数加法 新思路 DDA算法采用两点式 可否采用其他的直线表示方式 2 1 2中点画线法 基本思想当前象素点为 xp yp 下一个象素点为P1或P2 设M xp 1 yp 0 5 为p1与p2之中点 Q为理想直线与x xp 1垂线的交点 将Q与M的y坐标进行比较 当M在Q的下方 P2离直线更近更近 取P2 M在Q的上方 P1离直线更近更近 取P1M与Q重合 P1 P2任取一点 2 1 2中点画线法 问题 如何判断M与Q点的关系 2 1 2中点画线法 假设直线方程为 F x y ax by c 0其中a y0 y1 b x1 x0 c x0y1 x1y0由常识知 欲判断M点是在Q点上方还是在Q点下方 只需把M代入F x y 并检查它的符号 2 1 2中点画线法 构造判别式 d F M F xp 1 yp 0 5 a xp 1 b yp 0 5 c其中a y0 y1 b x1 x0 c x0y1 x1y0当d0 M在L Q点 上方 取右方P1为下一个象素 当d 0 选P1或P2均可 约定取P1为下一个象素 2 1 2中点画线法 但这样做 每一个象素的计算量是4个加法 两个乘法 d a xp 1 b yp 0 5 c 2 1 2中点画线法 如果也采用增量算法呢 2 1 2中点画线法 d是xp yp的线性函数 因此可采用增量计算 提高运算效率 d a xp 1 b yp 0 5 c 2 1 2中点画线法 若当前象素处于d 0情况 则取正右方象素P1 xp 1 yp 要判下一个象素位置 应计算d1 F xp 2 yp 0 5 a xp 2 b yp 0 5 c d a 增量为ad a xp 1 b yp 0 5 c 2 1 2中点画线法 若d 0时 则取右上方象素P2 xp 1 yp 1 要判断再下一象素 则要计算d2 F xp 2 yp 1 5 a xp 2 b yp 1 5 c d a b 增量为a bd a xp 1 b yp 0 5 c 2 1 2中点画线法 至此 至少新算法可以和DDA算法一样好 能否再做改进 2 1 2中点画线法 能否实现整数运算 2 1 2中点画线法 画线从 x0 y0 开始 d的初值d0 F x0 1 y0 0 5 a x0 1 b y0 0 5 c F x0 y0 a 0 5b a 0 5b 由于只用d的符号作判断 为了只包含整数运算 可以用2d代替d来摆脱小数 提高效率 令d0 2a b d1 2a d2 2a 2b 我们有如下算法 2 1 2中点画线法 voidMidpointLine intx0 inty0 intx1 inty1 intcolor inta b d1 d2 d x y a y0 y1 b x1 x0 d 2 a b d1 2 a d2 2 a b x x0 y y0 drawpixel x y color while x x1 if d 0 x y d d2 else x d d1 drawpixel x y color while midPointLine 2 1 2中点画线法 例 用中点画线法ixiyid1001210 33213431 15425 中点画线法小结 中点与交点位置来判断象素选取引入直接的隐式方程F x y ax by c 0但计算量大 故又改进为增量算法 此处 增量分两种情况 为进一步提高效率 修改为全是整数计算的算法 2d代替d 同时增量也做相应调整 2 1 2中点画线法 思考题 P552 2用中点画线法扫描转换从点 1 0 到 4 7 经过的直线段 并给出每一步的判别值 DDA算法采用点斜式 中点法采用隐式表示 中点法可以有整数算法 其他表示可以推出整数算法吗 2 1 3Bresenham算法 基本思想过各行各列象素中心构造一组虚拟网格线 按直线从起点到终点的顺序计算直线与各垂直网格线的交点 然后根据误差项的符号确定该列象素中与此交点最近的象素 2 1 3Bresenham算法 设直线方程为 其中k dy dx 因为直线的起始点在象素中心 所以误差项d的初值d0 0 X下标每增加1 d的值相应递增直线的斜率值k 即d d k 当d 0 5时 选择当前象素的右上方象素 修改比较的基点为改点 即将d 1而当d 0 5时 选择当前象素的右方象素 此时不改变基点为方便计算 令e d 0 5 e的初值为 0 5 增量为k 当e 0时 取当前象素 xi yi 的右上方象素 而当e 0时 更接近于右方象素 2 1 3Bresenham算法 例 Line P0 0 0 P1 5 2 k dy dx 0 4xye00 0 510 0 1210 331 0 3420 152 0 5e每次加k 若e大于零则y加1且e减1 若e小于零则不变 2 1 3Bresenham算法 voidBresenhamline intx0 inty0 intx1 inty1 intcolor intx y dx dy floatk e dx x1 x0 dy y1 y0 k dy dx e 0 5 x x0 y y0 for i 0 i dx i drawpixel x y color x x 1 e e k if e 0 y e e 1 2 1 3Bresenham算法 可以改用整数以避免除法 由于算法中只用到误差项的符号 因此可作如下替换 2 1 3Bresenham算法 voidBresenhamline intx0 inty0 intx1 inty1 intcolor intx y dx dy e dx x1 x0 dy y1 y0 e dx x x0 y y0 for i 0 i dx i drawpixel x y color x x 1 e e 2 dy if e 0 y e e 2 dx intx y dx dy floatk e dx x1 x0 dy y1 y0 k dy dx e 0 5 x x0 y y0 for i 0 i dx i drawpixel x y color x x 1 e e k if e 0 y e e 1 2 1 3Bresenham算法 y每次增k 误差项每次也增k 同DDA算法 通过交点与基点的距离d来判断为了用正负号判断 e d 0 5为了变为整数算法最终 Bresenham算法也是每个象素 需一个整数算法 其优点是可以用于其他二次曲线 2 2圆弧的扫描转换算法 圆的特征 八对称性 只要扫描转换八分之一圆弧 就可以求出整个圆弧的象素集中点画圆法考虑中心在原点 半径为R的第二个8分圆 构造判别式 圆方程 2 2圆弧的扫描转换算法 若d 0 则应取P2为下一象素 而且下一象素的判别式为第一个象素是 0 R 判别式d的初始值为 2 2圆弧的扫描转换算法 MidPointCircle intrintcolor intx y floatd x 0 y r d 1 25 r circlepoints x y color 显示圆弧上的八个对称点while x y if d 0 d 2 x 3 else d 2 x y 5 y x circlepoints x y color 2 2圆弧的扫描转换算法 为了进一步提高算法的效率 可以将上面的算法中的浮点数改写成整数 将乘法运算改成加法运算 即仅用整数实现中点画圆法 如何改 2 2圆弧的扫描转换算法 使用e d 0 25代替de0 1 R 圆弧的中点扫描转换算法 利用圆八对称性类似于直线的中点法使用了圆的隐式方程两种不同的增量 0时 0时 为了改为整数算法e d 0 25代替d 小结 2 1直线段的扫描转换算法2 1 1数值微分 DDA 法2 1 2中点画线法2 1 3Bresenham算法2 2圆弧的扫描转换算法 2 3多边形的扫描转换与区域填充 多边形的表示方法顶点表示点阵表示顶点表示 用多边形顶点的序列来刻划多边形 直观 几何意义强 占内存少 不能直接用于面着色 点阵表示 用位于多边形内的象素的集合来刻划多边形 失去了许多重要的几何信息 便于运用帧缓冲存储器表示图形 易于面着色 2 3多边形的扫描转换与区域填充 多边形的扫描转换 把多边形的顶点表示转换为点阵表示 也就是从多边形的给定边界出发 求出位于其内部的各个象素 并给帧缓冲器内的各个对应元素设置相应的灰度和颜色 通常称这种转换为多边形的扫描转换 2 3多边形的扫描转换与区域填充 区域指已经表示成点阵形式的填充图形 它是象素的集合 区域填充指先将区域的一点赋予指定的颜色 然后将该颜色扩展到整个区域的过程 区域填充算法要求区域是连通的 2 3多边形的扫描转换与区域填充 区域表示方法 内点表示 边界表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色 多边形分为凸多边形 凹多边形 含内环的多边形 逐点判断算法 逐点判断算法 逐个像素判别其是否位于多边形内部判断一个点是否位于多边形内部 射线法从当前像素发射一条射线 计算射线与多边形的交点个数内部 奇数个交点外部 偶数个交点 逐点判断算法 判断一点是否位于多边形内部 逐点判断算法 算法描述for y 0 y y resolution y for x 0 x x resolution x if inside polygon x y setpixel framebuffer x y polygon color elsesetpixel framebuffer x y background color 逐点判断算法的不足 速度慢 几十万甚是几百万像素的多边形内外判断 大量的求交 乘除运算没有考虑像素之间的联系结论 逐点判断算法不可取 2 3 1 1扫描线算法 一个多边形与若干扫描线 2 3 1多边形的扫描转换 2 3 1 1扫描线算法基本思想 按扫描线顺序 计算扫描线与多边形的相交区间 再用要求的颜色显示这些区间的象素 即完成填充工作 对于一条扫描线填充过程可以分为四个步骤 求交排序配对填色 多边形扫描转换算法 P0 P1 P2 P3 P4 P5 P6 P7 扫描转换示意图 相邻像素之间的连贯性 扫描线算法充分利用了相邻像素之间的连贯性 避免了对像素的逐点判断和求交运算 提高了算法效率各种连贯性的定义区域连贯性扫描线连贯性边的连贯性 区域连贯性 区域的连贯性是指多边形定义的区域内部相邻的像素具有相同的性质 例如具有相同的颜色 区域的连贯性 区域连贯性 两条扫描线之间的长方形区域被所处理的多边形分割成若干梯形 三角形可以看作退化梯形 梯形的底边为扫描线 梯形的腰为多边形的边或窗口边缘 区域的连贯性 区域连贯性 梯形分为两类 多边形内部和多边形外部两类梯形在多边形内部相间排列 相邻的两个梯形必然有一个位于多边形内部 有一个在多边形外部 区域的连贯性 区域连贯性 推论 如果上述梯形属于多边形内 外 那么该梯形内所有点的均属于多边形内 外 效率提高的根源 逐点判断 区域判断 扫描线连贯性 区域连贯性在一条扫描线上的反映 扫描线的连贯性 扫描线连贯性 交点序列 扫描线与多边形的交点个数为偶数 1 2 3 4 5 6 红色区间 1 2 3 4 5 6 位于多边形内部其余绿色区间位于多边形外部两类区间相间排列 扫描线的连贯性 扫描线连贯性 推论 如果上述交点区间属于多边形内 外 那么该区间内所有点均属于多边形内 外 效率提高的根源 逐点判断 区间判断 边的连贯性 边的连贯性 直线的线性性质在光栅上的表现 边的连贯性 1 x1 y1 2 x2 y2 11 x11 y11 22 x22 y22 扫描线与边的交点 边的连贯性 相邻扫描线 y1 y11 1 与多边形的同一条边的交点存在如下关系 当知道扫描线与一条边的一个交点之后 通过上述公式可以通过增量算法迅速求出其他交点 边的连贯性 边的连贯性 推论 边的连贯性是连接区域连贯性和扫描线连贯性的纽带 扫描线连贯性 边连贯性 区域连贯性 2 3 1 1扫描线算法 扫描线与多边形的顶点或边界相交时 必须进行正确的交点取舍 只需检查顶点的两条边的另外两个端点的y值 按这两个y值中大于交点y值的个数是0 1 2来决定 2 3 1 1扫描线算法 数据结构结点内容x 当前扫描线与边的交点坐标 x 从当前扫描线到下一条扫描线间x的增量ymax 该边所交的最高扫描线号ymax 2 3 1 1扫描线算法 数据结构新边表 NET 存放在该扫描线第一次出现的边 若某边的较低端点为ymin 则该边就放在扫描线ymin的新边表中上图所示各条扫描线的新边表NET 2 3 1 1扫描线算法 数据结构活性边表 AET 把与当前扫描线相交的边称为活性边 并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中 2 3 1 1扫描线算法 假定当前扫描线与多边形某一条边的交点的x坐标为x 则下一条扫描线与该边的交点不要重计算 只要加一个增量 x 设该边的直线方程为 ax by c 0 若y yi x xi 则当y yi 1时 其中为常数 并约定a 0时 算法过程 voidpolyfill polygon color intcolor 多边形polygon for 各条扫描线i 初始化新边表头指针NET i 把ymin i的边放进边表NET i y 最低扫描线号 初始化活性边表AET为空 for 各条扫描线i 算法过程 把新边表NET i 中的边结点用插入排序法插入AET表 使之按x坐标递增顺序排列 遍历AET表 把配对交点区间 左闭右开 上的象素 x y 用drawpixel x y color 改写象素颜色值 i 遍历AET表 把ymax i的结点从AET表中删除 并把ymax i结点的x值递增 x polyfill 思考题 已知多边形P P0P1P2P3P4P5P6P0 其各边坐标分别为 2 5 2 10 9 6 16 11 16 4 12 2 7 2 建立其新边表和活性边表 新边表 y 3 y 8 活动边表的例子 扫描线算法小结 建立新边表按照扫描线顺序处理每条扫描线构造活性边表 x递增插入排序 中间考虑交点取舍根据当前活性边表选取像素进行填充 x方向 从活性边表中删除ymax i的结点 2 3 1 2边界标志算法 基本思想 帧缓冲器中对多边形的每条边进行直线扫描转换 亦即对多边形边界所经过的象素打上标志 填充 对每条与多边形相交的扫描线 按从左到右的顺序 逐个访问该扫描线上的象素 取一个布尔变量inside来指示当前点的状态 若点在多边形内 则inside为真 若点在多边形外 则inside为假 Inside的初始值为假 每当当前访问象素为被打上标志的点 就把inside取反 对未打标志的点 inside不变 边标志算法 例子 多边形P0P1P2P3P4顶点坐标为 2 1 2 7 8 5 8 1 6 4 以扫描线Y 3为例说明填充过程 开始时inside 0 1 对于X 0 该像素未置成边界值 inside 0 该点为背景色 2 对于X 1 同上 3 对于X 2 该像素已置成边界色 inside取反后为1 该点被置成多边形颜色 4 对于X 3 4 像素未置成边界色 由于inside 1 所以点被置成多边形颜色 5 对于X 5 像素被置成边界色 inside取反后为0 该点被置成背景色 6 对于X 6 像素未置成边界色 由于inside 0 所以点被置成背景色 7 对于X 7 像素被置成边界色 inside取反后为1 该点被置成多边形颜色 8 对于X 8 像素被置成边界色 inside取反后为0 该点被置成背景色 算法过程 voidedgemark fill polydef color 多边形定义polydef intcolor 对多边形polydef每条边进行直线扫描转换 for 每条与多边形polydef相交的扫描线y inside FALSE for 扫描线上每个象素x if 象素x被打上边标志 inside inside if inside FALSE drawpixel x y color elsedrawpixel x y background 2 3 1 2边界标志算法 用软件实现时 扫描线算法与边界标志算法的执行速度几乎相同 但由于边界标志算法不必建立维护边表以及对它进行排序 所以边界标志算法更适合硬件实现 这时它的执行速度比有序边表算法快一至两个数量级 2 3 2区域填充算法 区域指已经表示成点阵形式的填充图形 它是象素的集合 区域填充指先将区域的一点赋予指定的颜色 然后将该颜色扩展到整个区域的过程 区域填充算法要求区域是连通的 2 3 2区域填充算法 区域表示方法 内点表示 边界表示内点表示枚举出区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色 2 3 2区域填充算法 区域填充要求区域是连通的连通性 4连通 8连通4连通 8连通 2 3 2区域填充算法 4连通与8连通区域的区别连通性 4连通可看作8连通区域 但对边界有要求对边界的要求 A 适合于内点表示区域的填充算法设G为一内点表示的区域 x y 为区域内一点 oldcolor为G的原色 现取 x y 为种子点对区域G进行填充 即先置像素 x y 的颜色为newcolor 然后逐步将整个区域G都置为同样的颜色 步骤如下 种子象素入栈 当栈非空时 执行如下三步操作 1 栈顶象素出栈 2 将出栈象素置成多边形色 3 按上 下 左 右的顺序检查与出栈象素相邻的四个象素 若其中某个象素不在边界上且未置成多边形色 则把该象素入栈 2 3 2 1区域填充的递归算法 种子填充算法 种子填充算法 例子 多边形由P0P1P2P3P4构成 P0 1 5 P1 5 5 P2 7 3 P3 7 1 P4 1 1 设种子点为 3 3 搜索的方向是上 下 左 右 依此类推 最后像素被选中并填充的次序如图中箭头所示 2 3 2 1区域填充的递归算法 内点表示的4连通区域的递归填充算法 voidFloodFill4 intx inty intoldcolor intnewcolor if getpixel x y oldcolor 属于区域内点oldcolor drawpixel x y newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x y 1 oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor FloodFill4 x 1 y oldcolor newcolor 2 3 2 1区域填充的递归算法 边界表示的4连通区域的递归填充算法 voidBoundaryFill4 intx inty intboundarycolor intnewcolor intcolor getpixel x y if color newcolor 该算法也可以填充有孔区域 缺点 1 有些象素会入栈多次 降低算法效率 栈结构占空间 2 递归执行 算法简单 但效率不高 区域内每一象素都引起一次递归 进 出栈 费时费内存 改进算法 减少递归次数 提高效率 解决方法是用扫描线填充算法 2 3 2 1区域填充的递归算法 2 3 2 2区域填充的扫描线算法 目标 减少递归层次适用于内点表示的4连通区域算法步骤 首先填充种子点所在扫描线上的位于给定区域的一个区段然后确定与这一区段相连通的上 下两条扫描线上位于给定区域内的区段 并依次保存下来 反复这个过程 直到填充结束 2 3 2 2区域填充的扫描线算法 1 初始化 堆栈置空 将种子点 x y 入栈 2 出栈 若栈空则结束 否则取栈顶元素 x y 以y作为当前扫描线 3 填充并确定种子点所在区段 从种子点 x y 出发 沿当前扫描线向左 右两个方向填充 直到边界 分别标记区段的左 右端点坐标为xl和xr 4 并确定新的种子点 在区间 xl xr 中检查与当前扫描线y上 下相邻的两条扫描线上的象素 若存在非边界 未填充的象素 则把每一区间的最右象素作为种子点压入堆栈 返回第 2 步 上述算法对于每一个待填充区段 只需压栈一次 因此 扫描线填充算法提高了区域填充的效率 扫描线算法分析 举例分析 该算法也可以填充有孔区域 像素中的序号标指它所在区段位于堆栈中的位置 扫描线算法分析 举例分析 扫描线算法分析 举例分析 扫描线算法分析 举例分析 多边形扫描转换与区域填充方法比较 联系 都是光栅图形面着色 用于真实感图形显示 可相互转换 多边形的扫描转换转化为区域填充问题 当给定多边形内一点为种子点 并用Bresenham或DDA算法将多边形的边界表示成八连通区域后 则多边形的扫描转换转化为区域填充 区域填充转化为多边形的扫描转换 若已知给定多边形的顶点 则区域填充转化为多边形的扫描转换 多边形扫描转换与区域填充方法比较 不同点 1 基本思想不同 前者是顶点表示转换成点阵表示 后者只改变区域内填充颜色 没有改变表示方法 2 对边界的要求不同前者只要求扫描线与多边形边界交点个数为偶数 后者 区域封闭 防止递归填充跨界 3 基本的条件不同前者 从边界顶点信息出发 后者 区域内种子点 第二章光栅图形学 2 1直线段的扫描转换算法2 2圆弧的扫描转换算法2 3多边形的扫描转换与区域填充2 4字符2 5裁剪2 6反走样2 7消隐 2 4字符 字符指数字 字母 汉字等符号 计算机中字符由一个数字编码唯一标识 国际上最流行的字符集 美国信息交换用标准代码集 简称ASCII码 它是用7位二进制数进行编码表示128个字符 包括字母 标点 运算符以及一些特殊符号 汉字编码的国家标准字符集 GB2312 80 该字符集分为94个区 94个位 每个符号由一个区码和一个位码共同标识 区码和位码各用一个字节表示 为了能够区分ASCII码与汉字编码 采用字节的最高位来标识 最高位为0表示ASCII码 最高位为1表示表示汉字编码 字库 为了在显示器等输出设备上输出字符 系统中必须装备有相应的字库 字库中存储了每个字符的形状信息 字库分为矢量型和点阵型两种 点阵字符 每个字符由一个位图表示 该位为1表示字符的笔画经过此位 对应于此位的象素应置为字符颜色 该位为0表示字符的笔画不经过此位 对应于此位的象素应置为背景颜色 点阵字符点阵字库中的位图表示 在实际应用中 有多种字体 如宋体 楷体等 每种字体又有多种大小型号 因此字库的存储空间是很庞大的 解决这个问题一般采用压缩技术 点阵字符的显示分为两步 首先从字库中将它的位图检索出来 然后将检索到的位图写到帧缓冲器中 矢量字符 记录字符的笔画信息 而不是整个位图 具有存储空间小 美观 变换方便等优点 对于字符的旋转 缩放等变换 点阵字符的变换需要对表示字符位图中的每一象素进行 矢量字符的变换只要对其笔画端点进行变换就可以了 矢量字符的显示也分为两步 显示 首先从字库中将它的字符信息 然后取出端点坐标 对其进行适当的几何变换 再根据各端点的标志显示出字符 点阵字符点阵字库中的位图表示矢量轮廓字符 特点 点阵字符 存储量大 易于显示矢量字符 存储量小 美观 变换方便 但需要光栅化后才能显示 字符属性 字体宋体仿宋体楷体黑体隶书字高宋体宋体宋体宋体字宽字倾斜角倾斜倾斜对齐 左对齐 中心对齐 右对齐 字色红色 绿色 蓝色 2 5裁剪 裁剪 确定图形中哪些部分落在显示区之内 哪些落在显示区之外 以便只显示落在显示区内的那部分图形 这个选择过程称为裁剪 在使用计算机处理图形信息时 计算机内部存储的图形往往比较大 而屏幕显示的只是图的一部分 问 为什么要裁减 直接处理呢 即 在绘制 写帧缓存时 再处理 最简单的裁剪方法是把各种图形扫描转换为点之后 再判断各点是否在窗内 但那样太费时 一般不可取 这是因为有些图形组成部分全部在窗口外 可以完全排除 不必进行扫描转换 所以一般采用先裁剪再扫描转换的方法 2 5 1直线段裁剪 直线段裁剪算法是复杂图元裁剪的基础 复杂的曲线可以通过折线段来近似 从而裁剪问题也可以化为直线段的裁剪问题 2 5 1 1Cohen Sutherland2 5 1 2中点分割算法2 5 1 3梁友栋 Barskey算法 2 5 1 1Cohen Sutherland裁剪 基本思想 对于每条线段P1P2分为三种情况处理分为三种情况处理 1 若P1P2完全在窗口内 则显示该线段P1P2简称 取 之 2 若P1P2明显在窗口外 则丢弃该线段 简称 弃 之 3 若线段不满足 取 或 弃 的条件 则在交点处把线段分为两段 其中一段完全在窗口外 可弃之 然后对另一段重复上述处理 为快速判断 采用如下编码方法 每个区域赋予4位编码 编码线段裁剪 若P1P2完全在窗口内code1 0 且code2 0 则 取 若P1P2明显在窗口外 code1 code2 0 则 弃 在交点处把线段分为两段 其中一段完全在窗口外 可弃之 然后对另一段重复上述处理 计算线段P1 x1 y1 P2 x2 y2 与窗口边界的交点if LEFT 示例 编码的思想在图形学中非常重要 Sutherland Coons奖 图灵奖 IEEE计算机先驱奖 2 5 1 2中点分割裁剪算法 基本思想 与前一种Cohen Sutherland算法一样首先对线段端点进行编码 并把线段与窗口的关系分为三种情况 全在 完全不在和线段和窗口有交 对前两种情况 进行一样的处理 对于第三种情况 用中点分割的方法求出线段与窗口的交点 求线段与窗口的交点 A B分别为距P0 P1最近的可见点 Pm为P0P1中点 从出发找最近可见点的方法先求出的中点若不是显然不可见的 并且在窗口中有可见部分 则距最近的可见点一定落在上 所以用代替 否则取代替再对新的求中点 重复上述过程 直到长度小于给定的控制常数为止 此时收敛于交点 从出发找最近可见点采用上面类似方法 问 算法为什么可行 会不会无限循环 不断二分 2 5 1 3梁友栋 Barsky算法 梁 Barsky算法的几何含义 入边 出边与端点 写入图形学教科书的唯一中国人的算法 CommunicationofACM的论文梁有栋教授的二三事Liang Barsky算法几何连续理论 叶 马 郑从几何学与纤维缠绕理论到基因工程 参数化形式写出裁剪条件 可以统一表示为形式 入边出边 0且 0 则线段完全在边界外 0 则该线段平行于裁剪边界并且在窗口内 当 0 当0 线段从裁剪边界延长线的内部延伸到外部 对于每条直线 可以计算出参数u1和u2 它们定义了在裁剪矩形内的线段部分u1的值由线段从外到内遇到的矩形边界所决定 p0 对这些边界计算rk qk pk u2取1和各个rk值之中的最小值 如果u1 u2 则线段完全落在裁剪窗口之外 被舍弃 否则裁剪线段由参数u的两个值u1 u2计算出来 voidLB LineClip x1 y1 x2 y2 XL XR YB YT floatx1 y1 x2 y2 XL XR YB YT floatdx dy u1 u2 u1 0 u2 1 dx x2 x1 dy y2 y1 if ClipT dx x1 XL boolClipT p q u1 u2 floatp q u1 u2 floatr if p u2 returnFALSE elseif r u1 u1 r returnTRUE 下页 elseif p 0 r p q if r u1 returnFALSE elseif r u2 u2 r returnTRUE elseif q 0 returnFALSE returnTRUE 裁减的插曲 汪嘉业的快速算法80年代的裁减热 应道宁 工程图学研究所 汪国昭 图形图像研究所 对三种算法比较 Cohen Sutherland与中点法在区域码测试阶段能以位运算方式高效率地进行 因而当大多数线段能够简单的取舍时 效率较好 梁友栋 Barskey算法只能应用于矩形窗口的情形 但其效率比前两者要高 这是因为运算只涉及到参数 仅到必要时才进行坐标计算 2 5 2多边形裁剪 基本思想是一次用窗口的一条边裁剪多边形 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分 可见一侧 不可见一侧 多边形的各条边的两端点S P 它们与裁剪线的位置关系只有四种 对于情况 1 仅输出顶点P 情况 2 输出0个顶点 情况 3 输出线段SP与裁剪线的交点I 情况 4 输出线段SP与裁剪线的交点I和终点P 上述算法仅用一条裁剪边对多边形进行裁剪 得到一个顶点序列 作为下一条裁剪边处理过程的输入 对于每