222222
1222
1(2, 1.5)(2)( 1.5) (23)(22)p p p p p p d F x y b x a y a b d b x a y '=+-=++--=+++-+
判别式1d 的初始条件确定。椭圆弧起点为(0, b )，第一个中点为(1,b – 0.5)，对应判别式为 上半部分 下半部分 二分量相等的法向量
y x 图1-11 第一象限的椭圆弧
222222210(1,0.5)(0.5)(0.25)d F b b a b a b b a b =-=+--=+-+
在扫描转换椭圆的上半部分时，在每步迭代中需要比较法向量的两个分量来确定核实从上部分转到下半部分。在下半部分算法有些不同，要从正上方和右下方两个像素中选择下一个像素。在从上半部分转到下半部分时，还需要对下半部分的中点判别式进行初始化。即若上半部分所选择的最后一个像素点为(x p , y p )，则下半部分中点判别式应在（x p +0.5, y p –1）的点上计算。其在正下方与右下方的增量计算同上半部分。具体算法的实现请参考下面的程序设计。
程序设计步骤如下。
（1）创建应用程序框架，以上面建立的单文档程序框架为基础。
（2）编辑菜单资源。
在工作区的ResourceView 标签中，单击Menu 项左边“+”，然后双击其子项IDR_MAINFRAME ，并根据表1-5中的定义添加编辑菜单资源。此时建好的菜单如图1-12所示。
图1-12 程序主菜单
（3）添加消息处理函数。
利用ClassWizard （建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName 栏中选择CMyView ，根据表1-6建立如下的消息映射函数，ClassWizard 会自动完成有关的函数声明。
表1-6
菜单项的消息处理函数
（4）程序结构代码如下：
void CMyView:: OnMidpointellispe () //中点算法绘制椭圆，如图1-13所示
{
CDC* pDC=GetDC();
int a=200,b=100,xc=300,yc=200,c=0;
int x,y;
double d1,d2;
x=0;y=b; d1=b*b+a*a*(-b+0.25); 图1-13 中点算法绘制椭圆
pDC->SetPixel(x+300,y+200,c);
pDC->SetPixel(-x+300,y+200,c);
pDC->SetPixel(x+300,-y+200,c);
pDC->SetPixel(-x+300,-y+200,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);
x++;y--;
}
pDC->SetPixel(x+xc,y+yc,c);
pDC->SetPixel(-x+xc,y+yc,c);
pDC->SetPixel(x+xc,-y+yc,c);
pDC->SetPixel(-x+xc,-y+yc,c);
}
d2=sqrt(b*(x+0.5))+a*(y-1)-a*b;
while(y>0)
{
if(d2<0){
d2+=b*b*(2*x+2)+a*a*(-2*y+3);
x++;y--;}
else
{d2+=a*a*(-2*y+3);
y--;}
pDC->SetPixel(x+xc,y+yc,c);
pDC->SetPixel(-x+xc,y+yc,c);
pDC->SetPixel(x+xc,-y+yc,c);
pDC->SetPixel(-x+xc,-y+yc,c);
}
}
1.4 多边形的扫描转换与区域填充
在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示
是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。
1.4.1 多边形的扫描转换
多边形可分为凸多边形、凹多边形、含内环多边形。
（1）凸多边形：任意两顶点间的连线均在多边形内。
（2）凹多边形：任意两顶点间的连线有不在多边形内的部分。
（3）含内环多边形：多边形内包含有封闭多边形。
扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为4个步骤。
（1）求交：计算扫描线与多边形各边的交点。
（2）排序：把所有交点按x 值递增顺序排序。
（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间。
（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。 具体实现方法：为多边形的每一条边建立一边表；为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点递增的顺序存放在一个链表中，称此链表为活性边表。另外使用增量法计算时，需要知道一条边何时不再与下一条扫描线相交，以便及时把它从扫描线循环中删除出去。为了方便活性边表的建立与更新，为每一条扫描线建立一个新边表（NET ），存放在该扫描线第一次出现的边。为使程序简单、易读，这里新边表的结构应保存其对应边如下信息：当前边的边号、边的较低端点（x min ，y min ）与边的较高端点（x max ，y max ）和从当前扫描线到下一条扫描线间x 的增量x 。
相邻扫描线间x 的增量x 的计算，假定当前扫描线与多边形某一条边的交点的X 坐标为x ，则下一条扫描线与该边的交点不要重计算，只要加一个增量x 。设该边的直线方程为ax +by +c =0；若y =y i ，x =x i ；则当y = y i +1时
111()i i i i b x b y c x a a ++=-?-=-
其中/x b a ?=-为常数。
扫描线与多边形顶点相交的处理方法如图1-14所示。
（1）扫描线与多边形相交的边分别处于扫描线的两侧，
则记为一个交点，如点P 5，P 6。
（2）扫描线与多边形相交的边分别处于扫描线同侧，且
y i <y i –1，y i <y i +1，则计两个交点（填色），如P 2，若y i >y i –1，
y i >y i +1，则计0个交点（不填色），如P 1。
（3）扫描线与多边形边界重合（当要区分边界和边界内
图1-14 扫描线与多边形相交，
特殊情况的处理
区域时需特殊处理），则计1个交点。
具体实现时，只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。