图形学教案ch403pptConvertorWord文件下载.docx
《图形学教案ch403pptConvertorWord文件下载.docx》由会员分享，可在线阅读，更多相关《图形学教案ch403pptConvertorWord文件下载.docx（16页珍藏版）》请在冰点文库上搜索。
下面来求d2的初值。
显然，d2的初值出现在由上半椭圆弧转入下半椭圆弧的时候。
下半椭圆弧的第一个象素就是上半椭圆弧的最后一个象素。
设在上半椭圆弧的最后一个象素是（xp,yp），那么d2的初值为
midpointellipse（a,b,c）
inta,b,c;
{
intx,y;
floatd1,d2;
x=0;
y=b;
d1=b*b+a*a*（-b+0.25）;
putpixel（x,y,c）;
while（b*b*（x+1）<
a*a*（y-0.5））
if（d1<
0）
{d1+=b*b*（2*x+3）;
x++;
}
else{
d1+=b*b*（2*x+3）+a*a*（-2*y+2）;
y--;
putpixel（x,y,c）;
}/*上半椭圆结束*/
d2=b*b*（x+0.5）*（x+0.5）+a*a*（y-1）*（y-1）-a*a*b*b;
while（y>
if（d2<
{
d1+=b*b*（2*x+2）+a*a*（-2*y+3）;
d2+=a*a*（-2*y+3）;
y--;
}
有对称性，不难得出中心在原点的整个椭圆的算法：
putpixel（x,-y,c）;
putpixel（-x,y,c）;
putpixel（-x,-y,c）;
由平移变换，立即得到中心在任意位置（xr,yr）的椭圆的算法：
midpointellipse（xr,yr,a,b,c）
intxr,yr,a,b,c;
putpixel（x+xr,y+yr,c）;
putpixel（x+xr,-y+yr,c）;
putpixel（-x+xr,y+yr,c）;
putpixel（-x+xr,-y+yr,c）;
由平移变换，立即得到中心在任意位置（xr,yr）的椭圆的算法。
d2+=b*b*（2*x+2）+a*a*（-2*y+3）;
主函数如下：
#include<
graphics.h>
math.h>
main（）
intgdriver=DETECT,gmode;
initgraph（&
gdriver,&
gmode,””）;
midpointellipse（150,150,50,40,15）;
4.4区域填充
区域填充的方法主要有：
（多边形域的）扫描线填充算法、（多边形域的）边填充算法、区域的递归填充算法（简单的种子填充算法）、区域的扫描线填充算法（改进的种子填充算法）。
4.4.1区域的递归填充算法（简单的种子填充算法）
和递归填充算法相关的两种区域的表示：
内点表示：
区域内的所有像素着同一颜色，而区域外的所有像素具有另外的颜色；
边界表示：
区域边界上的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定色，而且边界外的像素不能具有与边界相同的颜色。
边界表示的区域的递归填充算法的思想
在给出区域光栅化后的边界位置及边界颜色代码boundary_color后，现在要从多边形内部某一象素（x,y）开始按一定的填充方法对多边形进行填充。
该象素称为种子点。
要求填充的颜色为fill_color。
内点表示的区域的递归填充算法的思想
在给出区域光栅化后的内点的颜色代码oldcolor后，现在要从多边形内部某一象素（x,y）开始按某一种填充方法对多边形进行填充。
要求填充的颜色为newcolor。
两种填充方式
四邻法：
已知象素是区域内的一点，据此向上、下、左、右4个方向测试、填色、扩散。
四邻法
八邻法
八邻法：
已知象素是区域内的一点，据此周围8个方向测试、填色、扩散。
区域的递归填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。
区域按连通情况又可分为四连通区域和八连通区域。
四连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。
八连通区域指的是从区域内每一像素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下移动的组合，在不越出区域的前提下，到达区域内的任意像素。
四连通区域八连通区域
四邻法的缺点：
当用四邻法填充一个八连通区域时，由于它无法填充对角线上的连通象素，因而可能造成某些区域没有被填上。
但是，如果希望两个区域填不同的颜色，用四邻法就比较合适。
八邻法的缺点：
当用八邻法填充一个四连通区域时，由于它填充是按8个方向进行的，因而可能造成从对角线方向越界，造成意想不到的后果。
一般来说，四邻法比八邻法用得更普遍。
因为，填不满比涂出界更容易补救。
边界表示的4连通区域的递归填充算法：
voidseed_filling（x,y,fill_color,boundary_color）
intx,y,fill_color,boundary_color;
intc;
c=getpixel（x,y）;
if（c!
=boundary_color&
&
c!
=fill_color）
putpixel（x,y,fill_color）;
seed_filling（x+1,y,fill_color,boundary_color）;
seed_filling（x-1,y,fill_color,boundary_color）;
seed_filling（x,y+1,fill_color,boundary_color）;
seed_filling（x,y-1,fill_color,boundary_color）;
内点表示的4连通区域的递归填充算法：
voidFloodFill4（intx,inty,intoldcolor,intnewcolor）
{if（getpixel（x,y）==oldcolor）//属于区域内点oldcolor
{putpixel（x,y,newcolor）;
FloodFill4（x,y+1,oldcolor,newcolor）;
FloodFill4（x,y-1,oldcolor,newcolor）;
FloodFill4（x-1,y,oldcolor,newcolor）;
FloodFill4（x+1,y,oldcolor,newcolor）;
4.4.2多边形的扫描线填充算法
简单的种子填充算法中含有4条递归语句，效率太低。
并且当区域过大时会造成堆栈溢出。
解决上述问题的办法是引入扫描线算法，得到了各种改进的算法，即区域的扫描线填充算法。
包括多边形区域的扫描线填充算法、边填充算法、栅栏填充算法、边标志算法和扫描线种子填充算法等。
基本思想：
按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。
对于一条扫描线填充过程可以分为四个步骤：
●求交（点）
●（交点）排序
●交点配对
●（区间）填色
情况1分析扫描线2、7与多边形的相交情况。
通过以上的分析，我们作出第一次修正。
当扫描线与多边形交于上顶点时，交点计数为0。
当扫描线通过多边形的下顶点时，交点计数为2。
当扫描线通过多边形的左右顶点时，交点计数为1。
情况2、上述修正还不能保证填充的正确，因为对边界上象素的取舍不当会出现所谓的“过填”问题。
“过填”造成边长为2个单位的正方形变为边长为3个单位。
避免出现上述“过填”现象，必须要对多边形的边界象素进行取舍。
1）对扫描线与多边形的相交区间取“左闭右开”。
2）对扫描线与多边形的上下顶点相交时，交点的取舍方法为“下闭上开”，即丢弃上方水平边或上顶点。
多边形扫描线填充算法的思想：
将多边形的顶点进行上述处理之后，用（水平）扫描线由下到上扫描多边形，求出每条扫描线与多边形的交点，将这些交点按x坐标进行排序，将排序后的交点成对取出，按照
左闭右开的方式以给定的颜色画线。
多边形被扫描后，填色也就完成了。
如何去求扫描线与多边形的交点？
活性边表法
把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表（或数组）中，称为活性边表（AEL）。
结点内容
x：
当前扫描线与边的交点坐标
△x：
从当前扫描线到下一条扫描线间x的增量，为1/k，其中k为斜率。
ymax：
该边所交的最高扫描线号ymax
扫描线6的活性边表。
假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。
设该边的直线方程为：
ax+by+c=0；
若y＝yi，x=xi；
则当y=yi+1时，
其中
=1/k为常数
当求完当前扫描线与多边形的交点后，应将与下一条扫描线不相交的边从活性边表中删除。
对于那些与下一条扫描线有交点的新边，应及时插入到活性边表中（按x递增排序）。
为了能快速找出与当前扫描线第一次有交点的新边，我们为每一条扫描线建立一个新边表（NEL）
新边表的建立：
先按低端点的y坐标值对所有的边进行分组，若某边的低端点y值为ymin，则该边就放在扫描线y=ymin所对应的表中；
然后用排序方法，按低端点的x坐标值递增的顺序将同一组中的边排列成行。
NEL中的基本元素、结点的构成和AEL相同，每个边结点由以下四个域组成：
其中，各符号的含义为：
⏹ymax：
边的上端点的y坐标
⏹x：
在NEL中表示边的下端点的x坐标，在AEL中表示边与扫描线的交点的x坐标
⏹1/k：
边的斜率的倒数
⏹next：
指向下一条边的指针
上图所示各条扫描线的新边表NEL
当建立了边表NEL后，扫描线多边形填充算法可按如下步骤进行：
（1）初始化AEL，使之为空，取扫描线纵坐标y的初始值为多边形所有顶点中最小的y值。
（2）将NEL中与当前y有关的结点加入至AEL，同时保存AEL中按x值从小到大实现的排序序列。
（3）对于AEL中的扫描线y，在一对交点之间填充所需要的像素值。
（4）从AEL中删掉y>
=ymax的结点。
（5）对于留在AEL中的每个结点，执行xi+1=xi+1/k。
（6）对AEL中的各结点按x值从小到大排序。
（7）y=y+1，成为下一条扫描线的坐标。
（8）若AEL非空，转
（2），否则，停止。
基本原理：
对每一条扫描线，依次求与（经过顶点处理的）多边形各边的交点，将该扫描线上交点右边的所有像素求补。
算法虽然简单易行，但对于复杂图形而言，一些像素的颜色值需反复改变多次，且多边形外的像素处理过多，输入、输出的量比有序边表大的多（可用矩形包围盒提高效率）。
4.4.3边填充算法
栅栏填充算法
对于每条扫描线与多边形的交点，将交点与栅栏之间的扫描线上的像素取补，也就是说，若交点位于栅栏左边，则将交点之右、栅栏之左的所有像素取补；
若交点位于栅栏右边，则将栅栏之右、交点之左的所有像素取补。
多边形外的像素处理大大减少，被重复取补的像素数目也有减少，但仍有一些像素被重复取补。
参见教材图4.3.6
边标志算法：
对多边形边界所在像素置一个特殊标志（对多边形的每条边进行直线扫描转换）；
对于每条与多边形相交的扫描线，从左至右逐个访问该扫描线上的像素。
使用一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。
若点在多边形外，则inside为假。
inside的初始值为假，每当当前访问像素为被打上标志的点（即边界点）就把inside取反。
对未打标志的点，inside不变。
若inside为真，则把该像素置为多边形要填充的颜色。
对每个像素只访问一次，硬件执行速度快。
voidedgemark_fill（polydef,color）
多边形定义polydef；
intcolor;
{对多边形polydef每条边进行直线扫描转换；
inside=FALSE;
for（每条与多边形polydef相交的扫描线y）
for（扫描线上每个象素x）
{
if（象素x被打上边标志）
inside=!
（inside）;
if（inside！
=FALSE）
drawpixel（x,y,color）;
elsedrawpixel（x,y,background）;
4.4.4扫描线种子填充算法
算法思想：
在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；
然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。
可以填充有孔区域，对于每一个待填充区段，只需入栈一次，因此提高了区域填充的效率。
（1）初始化：
堆栈置空。
将种子点（x，y）入栈。
（2）出栈：
若栈空则结束。
否则取栈顶元素（x，y），以y作为当前扫描线。
（3）填充并确定种子点所在区段：
从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。
分别标记区段的左、右端点坐标为xl和xr。
（4）并确定新的种子点：
在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。
若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第
（2）步。
上述算法对于每一个待填充区段，只需压栈一次；
因此，扫描线填充算法提高了区域填充的效率。
升级会员 