计算机图形学2010_02基本图形生成

计算机图形学 教案 第二章 基本图形生成1 第二章第二章 基本图形生成基本图形生成 所谓基本图形生成就是 将用参数定义的平面图形元素转换为点阵 确定出图形元素在点阵 平面上对应的所有点 平面上的图形元素分为三类 点 线 面 点无需生成 可以直接按坐标值输出到图形设备上 点的输出也是任何点阵图形设备必须具 备的基本功能 其是其它图形元素输出的基础 线主要包括 直线 圆周线 椭圆周线 二次曲线 三次曲线 面主要包括 多边形 圆 椭圆及任意封闭区域 第一节第一节 直线的生成直线的生成 一 问题 在一个矩形的均匀点阵平面中 给定两个整数点 x1 y1 x2 y2 确定该两点的连线在点阵平 面中所经过的所有点 在点阵平面中点的坐标值只能取整数 二 直线方程法 1 求直线方程求直线方程 由给定的两点 x1 y1 x2 y2 可得到一个直线方程 y kx b k 和 b 为方程中的两个参数 分别为斜率和截距 可由给定的两点计算得到 如下 k y2 y1 x2 x1 b y1 kx1 该方程表示的是一个无限直线 作为直线段还需要加上 x 的值域 x1 x2 由此得到两点之间 直线段的方程表示如下 y kx b x x1 x2 例例 1 给定两点 1 1 9 6 求其方程 k 6 1 9 1 5 8 0 625 b 1 0 625 1 0 375 x 的值域为 1 9 得 y 0 625x 0 375 x 1 9 2 点阵生成点阵生成 生成方法 在 x 的值域范围内取出所有的 x 整数值 逐一带入直线方程计算得到相应的 y 值 并取整 即得到直线段上所有的像素点的坐标值 例例 2 生成上例中两点之间的像素点 y 1 0 625 1 0 375 1 得 1 1 y 2 0 625 2 0 375 1 625 2 得 2 2 y 3 0 625 3 0 375 2 25 2 得 3 2 y 4 0 625 4 0 375 2 875 3 得 4 3 y 5 0 625 5 0 375 3 5 4 得 5 4 y 6 0 625 6 0 375 4 125 4 得 6 4 计算机图形学 教案 第二章 基本图形生成2 y 7 0 625 7 0 375 4 75 5 得 7 5 y 8 0 625 8 0 375 5 375 5 得 8 5 y 9 0 625 9 0 375 6 得 9 6 将计算结果绘入点阵平面中 如下 10 2510 7 5 1 0 01346789 9 8 6 4 3 2 3 存在的问题存在的问题 例例 3 生成 1 1 6 9 之间的直线 1 求直线方程 k 9 1 6 1 8 5 1 6 b 1 1 6 1 0 6 得 y 1 6x 0 6 x 1 6 2 生成点阵 x 值域范围内的整数值 1 2 3 4 5 6 计算各点的 y 值 y 1 1 6 1 0 6 1 得 1 1 y 2 1 6 2 0 6 2 6 3 得 2 3 y 3 1 6 3 0 6 4 2 4 得 3 4 y 4 1 6 4 0 6 5 8 6 得 4 6 y 5 1 6 5 0 6 7 4 7 得 5 7 y 6 1 6 6 0 6 9 得 6 9 将计算结果绘入点阵平面中 如下 计算机图形学 教案 第二章 基本图形生成3 10 2510 7 5 1 0 01346789 9 8 6 4 3 2 直线出现了间断 问题在于 x 的值域范围比 y 的值域范围要小 按 x 的值域取出的点 无法完整覆盖 y 的值域 因此直线出现间断 4 解决的方法解决的方法 当 y 的值域大于 x 的值域时 即 y2 y1 x2 x1 时 将 x 与 y 对调 求得如下形式的直线方 程 x ky b y y1 y2 其中 k x2 x1 y2 y1 b x1 ky1 然后从 y 的值域中取出整数值 代入方程计算出各点的 x 坐标 三 数值微分法 1 对直线方程法的分析对直线方程法的分析 对直线方程法的求解过程进行一下观察 可以看到 相邻两个点取整前的 y 值之差总是等于 直线的斜率 k 这是因为相邻两点的 x 值总是相差 1 根据直线方程的形式可以证明两点的 y 值必 然相差 k 设第 i 点的 x 值为 xi 第 i 1 点为 xi 1 有 xi 1 xi 1 这两点的 y 值分别为 yi kxi b yi 1 kxi 1 b k xi 1 b kxi k b 所以 yk 1 yk k 根据这一规律 就可以将直线方程法的计算过程进行简化 各点的 y 值可以在上一个点 y 值 的基础上加上 k 得到 而不需代入直线方程计算 下面就由这一思路构造出算法的计算步骤 2 计算步骤计算步骤 计算机图形学 教案 第二章 基本图形生成4 对给定的两个直线端点 x1 y1 x2 y2 有 x2 x1 x2 x1 y2 y1 1 求得两点连线的斜率 k y2 y1 x2 x1 2 px1 x1 py1 y1 得直线上的点 px1 py1 令 i 1 3 若 pxi x2 则计算结束 否则 继续 4 pxi 1 pxi 1 pyi 1 pyi k 得直线上的点 pxi 1 int py i 1 0 5 5 令 i i 1 转到 3 int 为向下取整函数 例 4 用数值微分法生成 2 3 8 7 间的连线 解 k 7 3 8 2 2 3 px1 2 py1 3 得点 2 3 px2 px1 1 2 1 3 py2 py1 k 3 2 3 3 2 3 得点 3 4 px3 px2 1 3 1 4 py3 py2 k 3 2 3 2 3 4 1 3 得点 4 4 px4 px3 1 4 1 5 py4 py3 k 4 1 3 2 3 5 得点 5 5 px5 px4 1 5 1 6 py5 py4 k 5 2 3 5 2 3 得点 6 6 px6 px5 1 6 1 7 py6 py5 k 5 2 3 2 3 6 1 3 得点 7 6 px7 px6 1 7 1 8 py7 py6 k 6 1 3 2 3 7 得点 8 7 有 px7 x2 结束 10 2510 7 5 1 0 01346789 9 8 6 4 3 2 作业 1 用直线方程法生成 1 3 4 9 之间的直线 写出计算过程并画出点阵图 2 用数值微分法生成 2 3 9 7 之间的直线 写出计算过程并画出点阵图 3 写出 y2 y1 y2 y1 x2 x1 的情况下 数值微分法的计算步骤 计算机图形学 教案 第二章 基本图形生成5 计算机图形学 教案 第二章 基本图形生成6 四 Bresenham 算法 1 算法原理算法原理 这里只针对直线的斜率的情况进行讨论 当 k 为其它情况时 可通过一定的变换进10 k 行处理 其是一种递推算法 在上一点的基础上求下一点 当直线的斜率时 下一点只可能取两个点之一 一是当前点的正右侧点 二是当前10 k 点的右上侧点 如下图 该算法构造一个决策变量 通过该变量的值来确定下一点的位置 其构造方式如下 记当前点的坐标为 xk yk 下一点的 x 值为 xk 1 下一点两个候选点的 y 值分别为 yk和 yk 1 设下一点 y 的理想值 取整前的值 为 y0 有 y0 k xk 1 b 计算下一点 y 的理想值与两个候选点的差值 d1 d2 d1 y0 yk k xk 1 b yk d2 yk 1 y0 yk 1 k xk 1 b 其含义如下图 计算机图形学 教案 第二章 基本图形生成7 d1 d2 将两个差值相减 有 d1 d2 2k xk 1 2yk 2b 1 这样就可根据的 d1 d2值来确定取哪一个点 但这样在计算量上并不能获得好处 因而还需 作进一步的处理 设 y y2 y1 x x2 x1 则 k y x 代入上式可得 cyxxyddx kk 22 21 其中 是一个与当前点的位置无关的常数 12 2 bxyc 令 即 21 ddxdk cyxxyd kkk 22 则 dk就作为递推过程中第 k 步的决策参数 若 则取右上方点 xk 1 yk 1 若 则取正右方点 xk 1 yk 0 k d0 k d dk的计算采用递推方法 cyxxyd kkk 111 22 则 22 2 2 1 111 kk kkkkkk yyxy yyxxxydd 得 22 11kkkk yyxydd 若 取右上方点 有 则 0 k d1 1 kk yy xydd kk 22 1 若 取正右侧点 有 则 0 k d0 1 kk yy ydd kk 2 1 第 1 点 dk值的计算 计算机图形学 教案 第二章 基本图形生成8 xy xyxxxyxy xxbyxbxxkxy bxybkxxxy bxyyxxyd 2 2 22 22222 12 2 22 12 222 11 11 11 111 2 计算步骤计算步骤 给定直线的两个端点 x1 y1 x2 y2 有 x2 x1 y2 y1 x2 x1 y2 y1 1 求得 x x2 x1 y y2 y1 c1 2 y 2 x c2 2 y 2 取 px1 x1 py1 y1 得点 px1 py1 求得 d1 2 y x 令 k 1 3 若 pxk x2 结束 否则 继续 4 取 pxk 1 pxk 1 若 dk 0 则 pyk 1 pyk 1 dk 1 dk c1 否则 pyk 1 pyk dk 1 dk c2 得点 pxk 1 pyk 1 5 令 k k 1 转到 3 例 用 Bresenham 算法生成 2 3 8 7 间的连线 解 8422 4624222 4 6 2 1 1212 yc xyc yyyxxx px1 2 py1 3 得点 2 3 26422 1 xyd 则 0 1 d 242 4131 31 112 12 12 cdd pypy pxpx 得点 3 4 则 0 2 d 682 4 41 223 23 23 cdd pypy pxpx 得点 4 4 则 0 3 d 2410 5141 51 134 34 34 cdd pypy pxpx 计算机图形学 教案 第二章 基本图形生成9 得点 5 5 则 0 4 d 242 6151 61 155 45 45 cdd pypy pxpx 得点 6 6 则 0 5 d 682 6 71 256 56 56 cdd pypy pxpx 得点 7 6 则 0 6 d 246 7161 81 167 67 67 cdd pypy pxpx 得点 8 7 有 结束 27 xpx 10 2510 7 5 1 0 01346789 9 8 6 4 3 2 数值微分法 每步进行一次浮点加法运算 计算机图形学 教案 第二章 基本图形生成10 Bresenham 算法每步进行一次整数加法运算 各种基本运算由快到慢有 整数加减法 整数乘法 整数除法 浮点四则运算 其它运算 3 程序程序 在 Bresenham 算法中 直线要分成四种情况分别处理 0 k 1 平缓向上 k 1 陡峭向上 1 k 平缓向下 k 1 陡峭向下 这里仅针对平缓向上的情况 写出 Bresenham 画线算法的程序 void DrawLine1 int x1 int y1 int x2 int y2 int dx x2 x1 dy y2 y1 int c1 2 dy 2 dx c2 2 dy int d 2 dy dx int x x1 y y1 putpixel x y 像素点输出函数 while x 0 y d c1 else d c2 putpixel x y 4 陡峭向上的算法陡峭向上的算法 在这种情况下 有 x2 x1 y2 y1 y2 y1 x2 x1 以平缓向上的算法为基础来进行讨论 构造算法的方式 将原算法中的 x 与 y 对换 1 求得 x x2 x1 y y2 y1 c1 2 x 2 y c2 2 x 对换 2 取 px1 x1 py1 y1 得点 px1 py1 求得 d1 2 x y 令 k 1 3 若 pyk y2 结束 否则 继续 4 取 pyk 1 pyk 1 对换 若 dk 0 则 pxk 1 pxk 1 dk 1 dk c1 对换 否则 pxk 1 pxk dk 1 dk c2 对换 得点 pxk 1 pyk 1 5 令 k k 1 转到 3 例 生成 2 2 5 7 解 计算机图形学 教案 第二章 基本图形生成11 6322 4523222 5 3 2 1 1212 xc yxc yyyxxx px1 2 py1 2 得点 2 2 15322 1 yxd 则 0 1 d 341 3121 31 112 12 12 cdd pxpx pypy 得点 3 3 则 0 2 d 363 3 41 223 23 23 cdd pxpx pypy 得点 3 4 则 0 3 d 143 4131 51 134 34 34 cdd pxpx pypy 得点 4 5 则 0 4 d 561 4 61 245 45 45 cdd pxpx pypy 得点 4 6 则 0 5 d 145 5141 71 156 56 56 cdd pxpx pypy 得点 5 7 结束 26 ypy 点阵图如下 计算机图形学 教案 第二章 基本图形生成12 10 2510 7 5 1 0 01346789 9 8 6 4 3 2 5 平缓向下的算法 平缓向下的算法 有 x2 x1 y1 y2 x2 x1 y1 y2 以平缓向上的算法为基础进行考虑 基本差别 y 值由每步加 1 或不变 变为每步减 1 或不变 算法的变化 1 y 每步减 1 或不变 2 y 的值由 y1减 y2得到 以保持其为正数 6 陡峭向下的算法 陡峭向下的算法 有 x2 x1 y1 y2 y1 y2 x2 x1 以平缓向下的算法为基础进行考虑 变化 1 x 与 y 对换 2 y 每步减 1 x 每步加 1 或不变 或者 以陡峭向上的算法为基础进行考虑 变化 1 y 每步减 1 2 y y1 y2 7 完整的画线程序完整的画线程序 在 4 种情况的画线函数都已有的情况下 写出一个完整的画线函数 能有效画出所有情况下 的直线段 void DrawLine int x1 int y1 int x2 int y2 计算机图形学 教案 第二章 基本图形生成13 if x1 x2 两点对换 int tx x1 ty y1 x1 x2 y1 y2 x2 tx y2 ty if y2 y1 向上 if x2 x1 y2 y1 DrawLine1 x1 y1 x2 y2 平缓向上 else DrawLine2 x1 y1 x2 y2 陡峭向上 else 向下 if x2 x1 y1 y2 DrawLine3 x1 y1 x2 y2 平缓向下 else DrawLine4 x1 y1 x2 y2 陡峭向下 作业 1 用 Bresenham 算法生成 2 4 8 8 之间的直线 写出计算过程并画出点阵图 2 用 Bresenham 算法生成 3 2 7 8 之间的直线 写出计算过程并画出点阵图 3 写出陡峭向上的 Bresenham 算法画线函数 void DrawLine2 4 写出陡峭向下的 Bresenham 画线算法的计算步骤 计算机图形学 教案 第二章 基本图形生成14 第二节第二节 圆的生成圆的生成 圆的生成也有多种算法 这里介绍 Bresenham 算法 其与直线生成的算法类似 一 算法推导 1 基本原理基本原理 针对情况 圆心为原点 圆弧段为 的 1 8 圆弧段 0 r 2 2 rr 该圆弧段上 切线的斜率在 0 到 1 之间 因此 随着 x 值加 1 y 的值要么不变要么减 1 由 这两个候选值与 y 的理想值之差来构造一个决策变量 根据该决策变量的正负来确定下一点 y 的 取值 d2 d1 2 决策变量的计算公式决策变量的计算公式 原理上决策参数为 为便于计算 进行一定的转换 用相邻两点 y 值的平方之差来 21 dd 计算 d1 d2 如下 2 2 02 2 0 2 1 1 k k yyd yyd 圆的方程为 222 ryx 下一点的 x 值为 xk 1 因此 下一点 y 的理想值的平方为 因而有 22 2 0 1 k xry 222 2 22 2 1 1 1 1 kk kk yxrd xryd 则决策参数 22 2 2 21 2 1 1 2ryyxddd kkkk 应有 若 则0 k d kk yy 1 若 则0 k d1 1 kk yy 3 决策变量的递推求解决策变量的递推求解 可得 22 1 2 1 2 11 2 1 1 2ryyxd kkkk 计算机图形学 教案 第二章 基本图形生成15 若 有0 k d kkkk yyxx 11 1 则 即 64 242 882 2 1 1 2 2 1 11 2 222 22 2 222 2 2 1 k kkkk kkkkkkkk x xxxx ryyxryyxdd 64 1 kkk xdd 若 有0 k d1 1 11 kkkk yyxx 则 1044 242 44882 2 1 1 2 2 11 1 11 2 22222 22 2 2 2222 1 kk kkkkkkk kkk kkkkk yx yxxyyxx ryyx ryyxdd 即 1044 1 kkkk yxdd 4 初始点的计算初始点的计算 ryx 11 0 则 r rrrr rrrdk 23 2122 2 1 10 2 222 2222 二 计算步骤 给定圆的半径 r 圆的圆心为原点 生成 1 8 圆弧上的点 1 取 x1 0 y1 r 得点 x1 y1 求得 d1 3 2r 令 k 1 2 若 xk yk 结束 否则 继续 3 取 xk 1 xk 1 若 dk 0 则 yk 1 yk dk 1 dk 4xk 6 否则 yk 1 yk 1 dk 1 dk 4xk 4yk 10 得点 xk 1 yk 1 4 令 k k 1 转到 2 例 生成半径为 5 的 1 8 圆弧点 解 x1 0 y1 5 得点 0 5 75 23 23 1 rd 则 0 1 d 160 476 4 5 11 112 12 12 xdd yy xx 计算机图形学 教案 第二章 基本图形生成16 得点 1 5 则 0 2 d 961 4164 5 21 223 23 23 xdd yy xx 得点 2 5 则 0 3 d 7105 42 491044 4151 31 3334 34 34 yxdd yy xx 得点 3 4 则 0 4 d 13104 43 47 31 41 5 45 45 d yy xx 有 结束 55 yx 5 305 2 0 4 5 5 4 2 11234 4 3 1 1 2 3 三 程序 圆心为原点的 Brenseham1 8 画圆程序 计算机图形学 教案 第二章 基本图形生成17 void DrawCircle08 int r int x 0 y r putpixel x y int d 3 2 r while x y x if d 0 d 4 x 6 else y 1 d 4 x 4 y 10 putpixel x y 四 进一步的问题 1 生成整圆 在求得八分之一圆上的点后 可直接按镜像关系得到其它 7 个点 如 得点 1 5 则对应的 7 个点为 5 1 1 5 5 1 1 5 5 1 1 5 5 1 如下图 5 305 2 0 4 5 5 4 2 11234 4 3 1 1 2 3 第一个点 0 r 则只镜像到另外三个点 r 0 0 r r 0 计算机图形学 教案 第二章 基本图形生成18 上例中通过镜像关系得到的完整的圆如下图所示 5 305 2 0 4 5 5 4 2 11234 4 3 1 1 2 3 2 任意圆心的圆 如 给定圆心的坐标为 3 5 按圆心为原点生成的一个点为 1 8 则该点的实际坐标为 3 1 5 8 即 4 13 按圆心为原点生成点 然后将生成的点的坐标加上圆心的坐标 作业 1 对圆心为原点 半径为 7 的圆 生成其 1 8 圆弧段上的点 2 写出完整的 Bresenham 画圆算法计算步骤 圆心为 x0 y0 半径为 r 生成圆周上的全部点 3 对圆心为 2 5 半径为 6 的圆 生成全部圆周点 4 写出 Bresenham 算法完整的画圆程序 DrawCricle int x0 int y0 int r 计算机图形学 教案 第二章 基本图形生成19 第三节第三节 区域填充区域填充 平面图形元素分为点 线 面三种类型 所谓区域填充讨论的就面图形的生成 其包括 多 边形 含三角形 矩形 圆 椭圆 任意封闭区域 一 多边形填充 边点配对算法 1 生成的结果 区域填充生成的结果有两种 一是 区域中的所有点 二是区域中所有的水平直线段 扫描 线段 某些图形设备能高效率地输出扫描线 如显示系统 在显示卡的帧缓存中 扫描线上各点的 属性值是连续存放的 可以用一条指令完成一条扫描线段的输出 扫描线是指横贯整个图形区域的水平直线 扫描线段则是扫描线上的某一段 一条扫描线段 由三个参数定义 x1 x2 y 2 算法原理 是一种扫描线生成算法 结果是输出多边形内所有的扫描线段 多边形内扫描线段的特性 一条扫描线若通过多边形 则一般情况下将与多边形的边线相交偶数次 将偶数个交点依次 两辆配对即为多边形内的线段 按此特性可形成一种算法 1 依次生成多边形各条边线上的点 2 将各点按 y x 进行排序 3 将各点依次两两配对形成多边形内的所有扫描线段 在该算法中有几个问题需要处理 1 扫描线与边的端点相交 此时上述特性将出现异常 因为每个端点将在相邻的两条边中将各生成一次 这将使两两配 对的规则失效 处理方法 约定各条边线只生成一个端点 这里约定为下端点 2 平缓边线 如果一条边线较平缓 将在某些扫描线上生成多个点 从而是两两配对规则失效 处理方法 总是从 y 方向生成边线的点 此时 对平缓边线 Bresenham 算法将失效 可采用数值微分法 3 水平边线 这也将使两两配对失效 处理方法 水平直线不生成点 计算机图形学 教案 第二章 基本图形生成20 P1 P2 P3 P4 P5 P6 3 程序 按以上算法原理可写出如下多边形填充程序程序 需要由多个函数实现 void FillPolygon int n int xy n 多边形顶点的数量 xy 顺序相连的各顶点坐标 含 2 n 个元素 int dotNum 0 dotXY 1000 边点数量 边点坐标 int i k for i 0 i n 1 i k i 2 FPDrawLine xy k xy k 1 xy k 2 xy k 3 dotNum dotXY k n 1 2 FPDrawLine xy k xy k 1 xy 0 xy 1 dotNum dotXY FPSort dotNum dotXY for i 0 iy2 int tx x1 ty y1 x1 x2 y1 y2 x2 tx y2 ty float d float x2 x1 y2 y1 float fx x1 for int y y1 1 y y2 y fx d dotXY dotNum 2 int fx 0 5 dotXY dotNum 2 1 y dotNum void FPSort int dotNum int dotXY 对所有边点按 y x 由小到大排序 int i ii 1 k flag 1 tx ty While flag flag 0 for i 0 idotXY k 3 dotXY k 1 dotXY k 3 ty dotXY k 1 dotXY k dotXY k 2 dotXY k 1 dotXY k 3 dotXY k 2 tx dotXY k 3 ty flag 1 ii 二 圆填充 处理步骤 1 按 bresenham 算法生成圆周上的所有点 2 确定最小和最大的 y 值 3 对每个 y 值 将 x 值最小和最大的点配对形成区域内的扫描线段 若某个 y 值只有一个点 则直接输出该点 计算机图形学 教案 第二章 基本图形生成22 三 任意封闭区域的填充 种子填充 1 问题及方法 在这种填充问题中是用点阵来定义区域的边界 定义方式 区域边界由一系列相连的点构成 每个点都具有一个特定的颜色值 而区域内的所有点都不 具有该颜色 点之间的连接有四连通和八连通两种规则 四连通 每个点与上 下 左 右四个点相邻接 斜向相邻的点可以对区域形成分割 八连通 每个点与周围八各点相邻接 只有垂直和水平相邻的点才能对区域形成分割 种子填充问题一般是针对于四连通区域 填充条件 已在图形缓冲区中写入所有的边界点 并给定一个区域内的点 称为种子 填充结果 将区域内的所有点写为某种特定的填充色 基本方法 从种子出发 扩散蔓延到区域内的所有点 每处理一个点 首先读取该点的颜色值 如果不等于边界值和填充值 则填充该点 并从该 点继续向外探寻 2 程序 通过递归调用实现 void SeedFill int x int y int fCol int bCol 计算机图形学 教案 第二章 基本图形生成23 x y 种子点的坐标 fCol 填充色 bCol 边界色 int cCol getpixel x y 获取当前点的颜色 if cCol bCOl SeekFill x 1 y fCol bCol SeekFill x 1 y fCol bCol SeekFill x y 1 fCol bCol SeekFill x y 1 fCol bCol 作业 1 对圆心为 2 5 半径为 6 的圆进行填充 首先给出所有的圆周点 然后给出填充圆的所有扫 描线段 2 写出八联通区域种子填充的程序 3 尝试写出圆填充程序 计算机图形学 教案 第二章 基本图形生成24 第四节第四节 裁剪裁剪 问题 用一个区域对图形进行裁剪 显示处于区域内的图形 不显示处于区域外的图形 用 于裁剪的区域通常为矩形 称为窗口 一 点的裁剪 待裁剪的点为 x y 裁剪窗口各边线的坐标值为 上边线 WTop 下边 WBottom 左边 WLeft 右边 WRight 若 WLeft x WRight且 WBottom y WTop 则显示该点 否则不显示 在点阵图形设备中 所有的图形最终都可以转换为一个个的点进行输出 因此可以通过对点 的裁剪来实现对任意图形的裁剪 但这样的效率比较低 二 扫描线裁剪 图形设备的另一种基本输出元素是扫描线 待填充的扫描线为 L x1 x2 y 有 21 xx 填充步骤 若 y WTop 或 y WBottom 则全不显示 结束 若 x2WRight 则全不显示 结束 若 x1 WLeft 且 x2 WRight 则全显示 结束 若 x1WRight 则输出 x1 WRight y 三 直线裁剪 1 直线段裁剪的情况 A B C D 分为四种情况 按直线段的两个端点的状态进行判别 计算机图形学 教案 第二章 基本图形生成25 1 直线段两个端点在窗口内 线段 A 则全显示 2 直线段两个端点在窗口外 且不与窗口相交 线段 B 则全不显示 3 直线段两个端点在窗口外 但与窗口相交 线段 C 则部分显示中间 4 直线段一个端点在窗口内 一个端点在窗口外 线段 E 则部分显示一侧 2 编码裁剪算法 对直线段的两个端点分别进行编码 编码为 4 位 每位对应于窗口的一条边线 对应顺序为上 下 左 右 编码规则 若点处于某条边线 含延长线 之外 则为 1 否则