讲稿-3 北航6系计算机图形学课件.ppt

3平面图形的生成算法 杨钦 博士 副教授电话 82316283Email yangqin 助教 施勇 硕士研究生 Email Sy0106257 2003年2月10 平面图形生成技术 3平面图形的生成算法 3 1线画元素的生成方法3 2填充图形的生成方法3 3反混淆算法 返回 2003年2月10 平面图形生成技术 作业 1编制一个用中点法画线的程序2调用WindowsAPI绘制一些不同形状 不同颜色的点 线和多边形 填充 3用OpenGL绘制一些不同形状 不同颜色的点 线和多边形 填充 4作业用VC6 0完成 可以参考例子程序 2003年2月10 平面图形生成技术 3 1线画元素的生成方法 3 1扫描转换直线段DDA算法中点算法3 2扫描转换圆弧细分成小直线段中点算法3 2图元属性的控制方法 返回 2003年2月10 平面图形生成技术 待扫描转换的直线段 斜率 直线方程 直接求交算法 划分区间 x0 x1 计算纵坐标 取整 3 1 1DDA算法 2003年2月10 平面图形生成技术 3 1 1DDA算法 复杂度 乘法 加法 取整DDA算法 增量算法 复杂度 加法 取整 2003年2月10 平面图形生成技术 3 1 2中点算法 目标 消除DDA算法中的浮点运算 浮点数取整运算 不利于硬件实现 DDA算法 效率低 条件 同DDA算法斜率 直线段的隐式方程 x0 y0 x1 y1 两端点 F x y ax by c 0式中 a y0 y1 b x1 x0 c X0Y1 X1Y0 2003年2月10 平面图形生成技术 直线的正负划分性 直线上方点 F X Y 0直线下方的点F X Y 0 2003年2月10 平面图形生成技术 问题 判断距直线最近的下一个象素点构造判别式 d F M F Xp 1 Yp 0 5 由d 0 0可判定下一个象素 P P2 P1 2003年2月10 平面图形生成技术 要判定再下一个象素 分两种情形考虑 1 若d 0 取正右方象素P1 再下一个象素判定 由 d1 F Xp 2 Yp 0 5 a Xp 2 b Yp 0 5 c d a d的增量是a2 若d 0 取右上方象素P2 再下一个象素 由 d2 F Xp 2 Yp 1 5 d a bd的增量为a b P2 P P1 2003年2月10 平面图形生成技术 d的初始值d0 F X0 1 Y0 0 5 F X0 Y0 a 0 5b因 X0 Y0 在直线上 F X0 Y0 0 所以 d0 a 0 5bd的增量都是整数 只有初始值包含小数 可以用2d代替d 2a改写成a a 算法中只有整数变量 不含乘除法 可用硬件实现 2003年2月10 平面图形生成技术 程序Midpointline intx0 inty0 intx1 inty1 intcolor inta b d1 d2 2 x y a y0 y1 b x1 x0 d 2 a b d1 2 a d2 2 a b x x0 y y0 PutPixel x y color while x x1 if d 0 x y d d2 else x d d1 PutPixel x y color 2003年2月10 平面图形生成技术 线宽控制像素复制方法优点 实现简单缺点 线段两端要么为水平的 要么是竖直的折线顶点处有缺口 2003年2月10 平面图形生成技术 图元的宽度不均匀产生宽度为偶数像素的图元效果不好 2003年2月10 平面图形生成技术 移动刷子 2003年2月10 平面图形生成技术 利用填充图元优点 生成的图形质量高缺点计算量大有些图形的等距线难以获得 例1 PaintBrush 例2 PhotoShop 返回 2003年2月10 平面图形生成技术 3 2填充图形的生成方法 扫描转换多边形逐点判别法扫描线方法区域填充 种子填充法 递归填充算法扫描线填充算法 返回 2003年2月10 平面图形生成技术 多边形的表示方法顶点表示点阵表示扫描转换多边形 将顶点表示形式转换成点阵表示形式 2003年2月10 平面图形生成技术 逐点判断 逐个判断绘图窗口内的像素 如何判断点在多边形的内外关系 1 射线法 2 累计角度法 2003年2月10 平面图形生成技术 基本原理一条扫描线与多边形的边有偶数个交点步骤 对于每一条扫描线 1 求交点 2 交点排序 3 交点配对 填充区段 返回 2003年2月10 平面图形生成技术 3 3反混淆方法 混淆现象锯齿现象细节失真现象反混淆方法提高分辨率的方法非加权区域采样加权区域采样 返回 2003年2月10 平面图形生成技术 不光滑 阶梯状 的图形边界 例子 PaintBrush 2003年2月10 平面图形生成技术 图形细节失真 2003年2月10 平面图形生成技术 狭小图形的遗失与动态图形的闪烁 2003年2月10 平面图形生成技术 提高分辨率的反混淆方法 方法简单 但代价非常大 显示器的水平 竖直分辩率各提高一倍 则显示器的点距减少一倍 帧缓存容量则增加到原来的4倍 而扫描转换同样大小的图元却要花4倍时间 2003年2月10 平面图形生成技术 方法由来两点假设1 象素是数学上抽象的点 它的面积为0 它的亮度由覆盖该点的图形的亮度所决定 2 直线段是数学上抽象直线段 它的宽度为0 现实像素的面积不为0 直线段的宽度至少为1个像素 假设与现实的矛盾是导致混淆出现的原因之一 2003年2月10 平面图形生成技术 解决方法 改变直线段模型 由此产生算法方法步骤 1 将直线段看作具有一定宽度的狭长矩形 2 当直线段与某象素有交时 求出两者相交区域的面积 3 根据相交区域的面积 确定该象素的亮度值 2003年2