计算机图形学第章初步.ppt

简单 速度太慢 由于该算法割断了各像素之间的联系，孤立地考察各像素与多边形的内外关系，使得几十万甚至几百万个像素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。 4舍？还是5入? 当交点的 x 坐标值是小数时需进行舍入运算。 4连通区域也可理解成8连通区域，但是两者的边界不尽相同 边界表示的四连通区域种子填充算法 内点表示的四连通区域种子填充算法 边界表示的八连通区域种子填充算法 内点表示的八连通区域种子填充算法 void floodFill4(int x,int y,int newColor,int oldColor) { if (getpixel(x,y)==oldColor) { drawpixel(x,y,newColor) floodFill4(x+1,y, newColor,oldColor); floodFill4(x-1,y, newColor,oldColor); floodFill4(x,y+1, newColor,oldColor); floodFill4(x,y-1, newColor,oldColor); } } 在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。 初始化：堆栈置空。将种子点（x，y）入栈 出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线 填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr 确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右（左）像素作为种子点压入堆栈，返回第（2）步 （3）像素着色模式 透明 当图案表的对应位置为1时，用前景色写像素，否则，不改变该像素的值 不透明 当图案表的对应位置为1时，用前景色写像素，否则，用背景色（图案背景色）写像素 本质：规定前景色与背景色的组合规则，如前景色优先、背景色优先、前景色与背景色的加权组合、或各种规则的组合。 假设 整型坐标系，直线段斜率0m1 对m＞1，x、y互换 基本原理 确定最佳逼近于该直线的一组像素 按扫描线顺序，对这些像素进行写操作 使用最广泛 由误差项符号决定下一个象素取正右方像素还是右上方像素 基本思想 x方向递增一个单位 比较从理想直线到位于直线上方的像素的距离d2和相邻的位于直线下方的像素的距离d1 根据距离误差项的符号确定与理想直线最近的像素 y方向走步与否取决于d1-d2的值 取决于误差e值的大小 误差判断 当e≥0.5时，最接近P2(xi+1,yi+1), y方向走一步 当e0.5时，最接近 P1(xi+1,yi),y方向不走步 初值：e0= ?y/?x 为方便与0比较，设e=e-0.5 当e≥0时，最接近P2(xi+1,yi+1), y方向走一步 当e0时，最接近P1(xi+1,yi), y 方向不走步 e0= ?y/?x-0.5 设e=e×2?x，不影响判断的准确性 当e≥0时，最接近P2(xi+1,yi+1), y方向走一步 当e0时，最接近P1(xi+1,yi), y 方向不走步 e0=2?y - ?x 下一步误差的计算 当e≥0时，y方向走一步 e’=2?y/?x - 1 e’=e + 2?y - 2?x 当e0时，y方向不走步 e’=2?y/?x e’=e + 2?y 优点 整数运算，速度快 精度高 乘2运算可用移位实现，适于硬件实现 走样 用离散量(像素)表示连续的量(图形)而引起的失真，叫走样或混淆(aliasing) 光栅图形混淆现象 阶梯状边界； 图形细节失真； 狭小图形遗失： 实时动画时隐时现，产生闪烁 用于减少或消除走样现象的技术称为反走样 提高分辨率 区域取样 方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。 而且它也只能减轻而不能消除锯齿问题 在确定像素的亮度等级时，既考虑子像素的多少，还应该考虑子像素的位置分布。 通常会给接近于像素区域中心的子像素更大的权。 因为这些子像素在确定像素的整体亮度中起更重要的作用。 图中示出了对3×3像素分割所采用的加权方案： 中心子像素的加权是角子像素的4倍，是其它像素的2倍； 对九个子像素的每个网格所计算出的亮