1、计通学院 计算机科学系计算机图形学第 4章 二维填充图元的生成1本章目标l 掌握如何绘制填充图元（矩形、多边形等）n 扫面转换算法（扫描线算法）n 填充算法l 学会使用 OpenGL的绘制函数2主要内容l 填充图元l 扫描转换矩形l 扫描转换多边形l 扫描转换扇形区域l 区域填充l 以图像填充区域l 字符的表示与输出l OpenGL相关函数34.1 填充图元l 填充（ Filling）n 矩形 (Rectangle)n 多边形 (Polygon)n 扇形 (Ellipse Arc)l 步骤n 确定那些像素位于填充图元的内部n 用指定颜色绘制这些像素l 两类方法n 扫描转换（ Scan Conv
2、erting） : 参数 点阵n 填充（ Filling） : 点阵 点阵44.2 扫描转换矩形l 含义n 用指定颜色填充矩形内部区域l 定义矩形的参数n 左下角坐标 (xmin, ymin)n 右上角坐标 (xmax, ymax)void FillRectangle(Rectangle *rect,int color) int x,y;for(y = rect-ymin; y ymax; y+)for(x = rect-xmin; x xmax; x+) SetPixel(x, y, color);/*end of FillRectangle() */(xmin, ymin)(xmax, y
3、max)54.2 扫描转换矩形l 问题n 矩形是简单的多边形，那么为什么要单独处理矩形？u比一般多边形可简化计算u应用非常多，如窗口系统n 共享边界如何处理？ u原则：左闭右开，下闭上开属于谁？64.3 扫描 转换 多边形l 多边形的表示方法n 顶点表示顶点序列 P0P1P2 Pnn 点阵表示n 扫描转换多边形：将顶点表示形式转换成点阵表示形式n 三种方法： 逐点判断法；扫描线算法；边缘填充法l 多边形分类（只考虑：简单多边形，即多边形边不自相交）n 凸多边形 (convex)：内角小于 180度n 凹多边形 (concave)：存在内角大于 180度74.3 扫描 转换 多边形如何识别多边形
4、的凸凹性方法 1：观察多边形边的延长线是否划分顶点在两侧方法 2：向量的叉积每条边建立一个向量，测试相邻边的叉积 z坐标的正负（ 1）如果叉积同号，那么是凸多边形（ 2）如果叉积不同号，那么是凹多边形(E1E2 )z 0(E2E3 )z 0(E3E4 )z 0(E5E6 )z 0(E6E1 )z 084.3 扫描 转换 多边形向量叉积（ Cross Product of Two Vector）当 a与 b为二维向量时， ab 矢量中 x， y 分量为 094.3.1 逐点判断法l 基本原理n 判断绘图窗口内的像素是否位于多边形内，若是，则用指定颜色绘制该像素l 问题n 如何判断点在多边形的内外关系？u射线法u累计角度法 *u编码法 *P1P2(xmin, ymin)(xmax, ymax)10
