OpenGL基本图元的绘制.ppt

四川大学计算机学院 6.OpenGL基本图元的绘制 上一章讲述了如何生成点、线和圆等基本几何构造。 本章重点如何在指定的输出设备上构造多边形域、像素数组等高级图元 主要内容 矩形填充 内外测试 多边形扫描转换 区域填充 多边形扫描转换与区域填充的区别 反走样 学习目标 深入认识图形函数包功能，了解函数是如何实现的，从而可改进图形函数以适应某些特殊的应用需求。 开发和改进图形技术，发展网络图形应用，开发更快的实时性更强的图形显示。 掌握多边形生成算法 掌握区域填充算法 了解反走样概念和相应算法 参考资料 孙家广，计算机图形学（第三版） Computer Graphics with OpenGL,3rd Edition, Hearn 5.1 矩形填充 特殊的多边形。在窗口系统中应用很多，在图形软件包中将它单独当作一类图元处理。 矩形扫描转换算法 FillRect(Rect *rect, int color) { int x,y; for (y=rect-ymin;y=rect-ymax,y++) for(x=rect-xmin;x=rect-xmax;x++) setPixel(x,y,color); } 5.2 内外测试 区域填充算法和其它图形处理常需要鉴别对象的内部区域。 在基本几何形体中，多边形通常被定义为不自交的。标准多边形的例子有三角形、四边形、八角形和十角形。这些对象的组成边仅在顶点处连接，在平面内没有其它公共点。鉴别标准多边形的内部区域通常是—个直观过程。 但在大多数图形应用中，我们可以指定填充区域顶点的任何次序，包括有相交的边的次序。如图。对这样的形状，平面上哪个区域是“内部”和那个区域是对象的“外部”并不是一目了然的。 图形软件包通常采用奇-偶规则或非零环绕数规则来鉴别物体的内部区域。 奇偶规则 奇-偶规则，也称奇偶性规则或偶奇规则，它在概念上从任何位置P到对象坐标范围以外远距离画一直线(射线)，并统计沿该射线与各边的交点数目。假如与这条射线相交的多边形边数为奇数，则P是内部点，否则P是外部点。 为了得到精确的边数，必须保证所画射线不与任何多边形顶点相交。 后面所讨论的多边形扫描线填充算法是用奇偶规则的区域填充的一个例子。 非零环绕数规则 非零环绕数规则。它统计有向多边形边环绕某一特定点的次数，这个数称为环绕数。二维物体的内部点被定义为具有环绕数为非0值。判定规则：在对多边形应用非零环绕数规则时，将环绕数初始化为零。从任意位置P画一射线，所选择的射线不能与多边形任何顶点相交。当从P点沿射线方向移动时，对穿过射线的边记数，每当多边形从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。在所有穿过的边都已记数后的环绕数的最后值决定P的相应位置。假如环绕数为非0，则P定义为内部点，否则P是外部点。 对于标准多边形和其它简单形状，奇偶规则和非零环绕数规则会给出相同的结果，但对于复杂形状，两种方法会产生不同的内部和外部区域。 确定有向边与射线相交的方法： 1.将从P点出发的射线向量u与边向量E的叉积u×E，如果叉积的z值大于0则，边从右到左穿过射线，环绕数加1，否则环绕数减1。 2.较简单的算法是用点积代替叉积，为此，我们建立一个垂直u且p沿u方向看是从右到左指向的向量v，例如u的元素是(ux,uy)，则垂直于u的向量v的元素(-uy,ux)，如果v·E0，则从右到左穿越射线，环绕数加1，否则减1 5.3 多边形扫描转换 逐点判断算法 扫描线填充算法 边缘填充算法 5.3.1 逐点判断算法 实现扫描转换多边形最简单的算法是逐点判断，即判断一个像素是否在多边形内部，是则填充颜色，否则放弃 两种常用的判断像素在多边形内部的方法： 射线法—类似奇偶规则 弧长法—类似非0环绕数规则 缺点：速度慢、效率低 5.3.2 扫描线填充算法 本算法适合凸多边形、凹多边形。 影响交点计数的问题发生在？ 观察两个顶点的区别？ 有两种方法能使扫描线与多边形交点个数为偶数。 方法1：如果两条顺序连接的边的端点y坐标单调地增加或减少，那么对于任何该穿过该点的扫描线就必须将该中间顶点计为一个交点。否则，共享的顶点表示多边形边界上的一个局部极值(最大或最小)，两条边与穿过该顶点的扫描线的交点可以添加到相关表中，记为两个交点。 该方法能保证水平扫描线与多边形的交点的个数为偶数。 方法2：将多边形某些边缩短以分离那些应计为1个交点的顶点。 我们可以以指定的顺时针或逆时针方向处理整个多边形边界上的非水平边。在处理每条边时进行检测，确定该边与下一条非水平边是否有单调递增或单调递减的端点y值。假如有，可将较低的一条边缩短以保证对通过连接两条边的公共顶点的扫描线仅有一个交点生成。 填充方法 每次填充都是以画水平线来进行，且每条水平线都是