圆的扫描转换算法

① 直线和圆的显示（在线等答案）

实验2 圆与椭圆
给出圆心坐标(xc, yc)和半径r，逐点画出一个圆周的公式有下列两种。
一 直角坐标法
直角坐标系的圆的方程为

由上式导出：

当x-xc从-r到r做加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，| x-xc | 越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。
二 中点画圆法
如图1所示，函数为F(x, y)=x2+y2-R2的构造圆，圆上的点为F(x, y)=0，圆外的点F(x, y)>0，圆内的点F(x, y)<0，构造判别式：
d=F(M)=F(xp+1, yp-0.5)=(xp+1)2+(yp-0.5)2
若d＜0，则应取P1为下一像素，而且下一像素的判别式为
d=F(xp+2, yp-0.5)= (xp+2)2+(yp-0.5)2-R2=d+2xp+3
若d≥0，则应取P2为下一像素，而且下一像素的判别式为
d=F(xp+2, yp-1.5)= (xp+2)2+(yp-1.5)2-R2=d+2(xp- yp)+5
我们讨论按顺时针方向生成第二个八分圆，则第一个像素是（0, R），判别式d的初始值为
d0=F(1, R-0.5)=1.25-R
三 圆的Bresenham算法
设圆的半径为r，先考虑圆心在(0, 0)，从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束，即有xi+1 = xi + 1；相应的，yi+1则在两种可能中选择：yi+1=yi或者yi+1 = yi - 1。选择的原则是考察精确值y是靠近yi还是靠近yi-1（见图2），计算式为
y2= r2-(xi+1)2
d1 = yi2-y2 = yi2-r2+(xi+1)2
d2 = y2- (yi - 1)2 = r2-(xi+1)2-(yi - 1)2
令pi=d1-d2，并代入d1、d2，则有
pi = 2(xi+1)2 + yi2+ (yi - 1)2 -2r2 （1.6）
pi称为误差。如果pi＜0，则yi+1=yi，否则yi+1=yi - 1。
pi的递归式为
pi+1 = pi + 4xi +6+2(yi2+1- yi2)-2(yi+1-yi) （1.7）
pi的初值由式(1.6)代入xi=0，yi=r，得
p1 = 3-2r （1.8）
根据上面的推导，圆周生成算法思想如下：
（1）求误差初值，p1=3-2r，i=1，画点(0, r)。
（2）求下一个光栅位置，其中xi+1=xi+1，如果pi＜0则yi+1=yi，否则yi+1=yi - 1。
（3）画点(xi+1, yi+1)。
（4）计算下一个误差，如果pi＜0则pi+1=pi+4xi+6，否则pi+1=pi+4(xi - yi)+10。
（5）i=i+1，如果x=y则结束，否则返回步骤（2）。
程序设计步骤如下。
（1）创建应用程序框架，以上面建立的单文档程序框架为基础。
（2）编辑菜单资源。
在工作区的ResourceView标签中，单击Menu项左边"+"，然后双击其子项IDR_MAINFRAME，并根据表1中的定义添加编辑菜单资源。此时建好的菜单如图3所示。
表1 菜单资源表
菜单标题 菜单项标题 标示符ID
圆 中点画圆 ID_MIDPOINTCIRCLE
Bresenham画圆 ID_BRESENHAMCIRCLE
（3）添加消息处理函数。
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表2建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表2 菜单项的消息处理函数
菜单项ID 消 息 消息处理函数
ID_MIDPOINTCIRCLE CONMMAN OnMidpointcircle
ID_BRESENHAMCIRCLE CONMMAN OnBresenhamcircle
（4）程序结构代码，在CMyView.cpp文件中的相应位置添加如下代码。

void CMyView::OnMidpointcircle() //中点算法绘制圆，如图4所示
{
// TODO: Add your command handler code here
CDC* pDC=GetDC();
int xc=300, yc=300, r=50, c=0;
int x,y;
float d;
x=0; y=r; d=1.25-r;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
while(x<=y)
{ if(d<0) d+=2*x+3;
else { d+=2*(x-y)+5; y--;}
x++;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
}
}
void CMyView::OnBresenhamcircle() //// Bresenham算法绘制圆，如图5所示
{
CDC* pDC=GetDC();
int xc=100, yc=100, radius=50, c=0;
int x=0,y=radius,p=3-2*radius;
while(x<y)
{
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
if (p<0)
p=p+4*x+6;
else
{
p=p+4*(x-y)+10;
y-=1;
}
x+=1;
}
if(x==y)
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
}

四 椭圆扫描转换中点算法
下面讨论椭圆的扫描转换中点算法，设椭圆为中心在坐标原点的标准椭圆，其方 程为
F(x, y)=b2x2+a2y2-a2b2=0
（1）对于椭圆上的点，有F(x, y)=0；
（2）对于椭圆外的点，F(x, y)>0；
（3）对于椭圆内的点，F(x, y)<0。
以弧上斜率为-1的点作为分界将第一象限椭圆弧分为上下两部分（如图6所示）。
法向量：

而在下一个点，不等号改变方向，则说明椭圆弧从上部分转入下部分。
与中点绘制圆算法类似，一个像素确定后，在下面两个候选像素点的中点计算一个判别式的值，再根据判别式符号确定离椭圆最近的点。先看椭圆弧的上半部分，具体算法如下：
假设横坐标为xp的像素中与椭圆最近点为（xp, yp），下一对候选像素的中点应为（xp+1，yp-0.5），判别式为

，表明中点在椭圆内，应取正右方像素点，判别式变为

若 ，表明中点在椭圆外，应取右下方像素点，判别式变为

判别式 的初始条件确定。椭圆弧起点为(0, b)，第一个中点为(1,b - 0.5)，对应判别式为

在扫描转换椭圆的上半部分时，在每步迭代中需要比较法向量的两个分量来确定核实从上部分转到下半部分。在下半部分算法有些不同，要从正上方和右下方两个像素中选择下一个像素。在从上半部分转到下半部分时，还需要对下半部分的中点判别式进行初始化。即若上半部分所选择的最后一个像素点为(xp, yp)，则下半部分中点判别式应在（xp+0.5, yp-1）的点上计算。其在正下方与右下方的增量计算同上半部分。具体算法的实现请参考下面的程序设计。
程序设计步骤如下。
（1）创建应用程序框架，以上面建立的单文档程序框架为基础。
（2）编辑菜单资源。
在工作区的ResourceView标签中，单击Menu项左边"+"，然后双击其子项IDR_MAINFRAME，并根据表3中的定义添加编辑菜单资源。此时建好的菜单如图7所示。
表3 菜单资源表
菜单标题 菜单项标题 标示符ID
椭圆 中点画椭圆 ID_MIDPOINTELLISPE

图7 程序主菜单
（3）添加消息处理函数。
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表4建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表4 菜单项的消息处理函数
菜单项ID 消 息 消息处理函数
ID_MIDPOINTELLISPE CONMMAN OnMidpointellispe
（4）程序结构代码如下：

void CMyView:: OnMidpointellispe () //中点算法绘制椭圆，如图8所示
{
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);
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);
}
}

实验一: 直 线
数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。
由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham 算法。
一. DDA（数值微分）算法
DDA算法原理：如图1-1所示，已知过端点 的直线段 ；直线斜率为 ，从 的左端点 开始，向 右端点步进画线，步长=1（个像素），计算相应的 坐标 ；取像素点 [ , round（y）] 作为当前点的坐标。计算 ，当 ，即当x每递增1，y递增k（即直线斜率）。
注意：上述分析的算法仅适用于k1的情形。在这种情况下，x每增加1, y最多增加1。当 时，必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的Visual C++程序）。
二. 生成直线的中点画线法
中点画线法的基本原理如图1-2所示。在画直线段的过程中，当前像素点为P，下一个像素点有两种选择，点P1或P2。M为P1与P2中点，Q为理想直线与X=Xp+1垂线的交点。当M在Q的下方时，则P2应为下一个像素点；当M在Q的上方时，应取P1为下一点。
中点画线法的实现：令直线段为L[ p0(x0,y0), p1(x1, y1)]，其方程式F(x, y)=ax+by+c=0。
其中，a=y0–y1, b=x1–x0, c=x0y1–x1y0；点与L的关系如下。
在直线上，F(x, y)=0；
在直线上方，F(x, y)>0；
在直线下方，F(x, y)<0。
把M代入F（x, y），判断F的符号，可知Q点在中点M的上方还是下方。为此构造判别式d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c。
当d < 0，L(Q点)在M上方，取P2为下一个像素。
当d > 0，L(Q点)在M下方，取P1为下一个像素。
当d=0，选P1或P2均可，取P1为下一个像素。
其中d是xp, yp的线性函数。
三. Bresenham算法
Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。由误差项符号决定下一个像素取右边点还是右上方点。
设直线从起点(x1, y1)到终点(x2, y2)。直线可表示为方程y = mx+b，其中b=y1–mx1， m = (y2–y1)/(x2–x1)=dy/dx；此处的讨论直线方向限于第一象限，如图1-3所示，当直线光栅化时，x每次都增加1个单元，设x像素为(xi，yi)。下一个像素的列坐标为xi+1，行坐标为yi或者递增1为yi+1，由y与yi及yi+1的距离d1及d2的大小而定。计算公式为
y = m(xi + 1) + b （1.1）
d1 = y – yi （1.2）
d2=yi+1–y （1.3）
如果d1–d2>0，则yi+1=yi+1，否则yi+1=yi。
式（1.1）、（1.2）、（1.3）代入d1–d2，再用dx乘等式两边，并以Pi=(d1–d2)，dx代入上述等式，得
Pi = 2xidy–2yidx+2dy+(2b–1)dx （1.4）
d1–d2是用以判断符号的误差。由于在第一象限，dx总大于0，所以Pi仍旧可以用做判断符号的误差。Pi+1为
Pi+1 = Pi+2dy–2(yi+1–yi)dx （1.5）
求误差的初值P1，可将x1、y1和b代入式（1.4）中的xi、yi，而得到
P1 = 2dy–dx
综述上面的推导，第一象限内的直线Bresenham算法思想如下：
（1）画点（x1, y1），dx=x2–x1，dy=y2–y1，计算误差初值P1=2dy–dx，i=1。
（2）求直线的下一点位置xi+1 = xi + 1，如果Pi>0，则yi+1=yi+1，否则yi+1=yi。
（3）画点(xi+1, yi+1)。
（4）求下一个误差Pi+1，如果Pi>0，则Pi+1=Pi+2dy–2dx，否则Pi+1=Pi+2dy。
（5）i=i+1；如果i<dx+1则转步骤（2）；否则结束操作。
四. 程序设计
1 程序设计功能说明
为编程实现上述算法，本程序利用最基本的绘制元素（如点、直线等），绘制图形。如图1-4所示，为程序运行主界面，通过选择菜单及下拉菜单的各功能项分别完成各种对应算法的图形绘制。

图1-4 基本图形生成的程序运行界面
2 创建工程名称为“基本图形的生成”单文档应用程序框架
（1）启动VC，选择“文件”|“新建”菜单命令，并在弹出的新建对话框中单击“工程”标签。
（2）选择MFC AppWizard(exe)，在“工程名称”编辑框中输入 “基本图形的生成”作为工程名称，单击“确定”按钮，出现Step 1对话框。
（3）选择“单个文档”选项，单击“下一个”按钮，出现Step 2对话框。
（4）接受默认选项，单击“下一个”按钮，在出现的Step 3～Step 5对话框中，接受默认选项，单击“下一个”按钮。
（5）在Step 6对话框中单击“完成”按钮，即完成“基本图形的生成”应用程序的所有选项，随后出现工程信息对话框（记录以上步骤各选项选择情况），如图1-5所示，单击“确定”按钮，完成应用程序框架的创建。

图1-5 信息程序基本
3 编辑菜单资源
设计如图1-4所示的菜单项。在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-1中的定义编辑菜单资源。此时VC已自动建好程序框架，如图1-5所示。
表1-1 菜单资源表
菜单标题 菜单项标题 标示符ID
直线 DDA算法生成直线 ID_DDALINE
Bresenham算法生成直线 ID_BRESENHAMLINE
中点算法生成直线 ID_MIDPOINTLINE
4 添加消息处理函数
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-2建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表1-2 菜单项的消息处理函数
菜单项ID 消 息 消息处理函数
ID_DDALINE CONMMAN OnDdaline
ID_MIDPOINTLINE CONMMAN OnMidpointline
ID_BRESENHAMLINE CONMMAN OnBresenhamline
5 程序结构代码，在CMyView.cpp文件中相应位置添加如下代码：
// DDA算法生成直线
void CMyView:: OnDdaline()
{
CDC* pDC=GetDC();//获得设备指针
int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);//定义直线的两端点，直线颜色
int x,y;
float dx, dy, k;
dx=(float)(xb-xa), dy=(float)(yb-ya);
k=dy/dx, y=ya;
if(abs(k)<1)
{
for (x=xa;x<=xb;x++)
{pDC->SetPixel (x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{
for (y=ya;y<=yb;y++)
{pDC->SetPixel (int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC);
}

说明：
（1）以上代码理论上通过定义直线的两端点，可得到任意端点之间的一直线，但由于一般屏幕坐标采用右手系坐标，屏幕上只有正的x, y值，屏幕坐标与窗口坐标之间转换知识请参考第3章。
（2）注意上述程序考虑到当k1的情形x每增加1，y最多增加1；当k>1时，y每增加1，x相应增加1/k。在这个算法中，y与k用浮点数表示，而且每一步都要对y进行四舍五入后取整。

//中点算法生成直线
void CMyView::OnMidpointline()
{
CDC* pDC=GetDC();
int xa=300, ya=200, xb=450, yb=300,c=RGB(0,255,0);
int a, b, d1, d2, d, x, y;
a=ya-yb, b=xb-xa, d=2*a+b;
d1=2*a, d2=2* (a+b);
x=xa, y=ya;
pDC->SetPixel(x, y, c);
while (x<xb)
{ if (d<0) {x++, y++, d+=d2; }
else {x++, d+=d1;}
pDC->SetPixel(x, y, c);
}
ReleaseDC(pDC);
}

说明：
（1）其中d是xp, yp的线性函数。为了提高运算效率，程序中采用增量计算。具体算法如下：若当前像素处于d>0情况，则取正右方像素P1(xp+1, yp)，判断下一个像素点的位置，应计算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；，其中增量为a。若d<0时，则取右上方像素P2（xp+1, yp+1）。再判断下一像素，则要计算d2 = F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5) + c=d+a+b，增量为a+b。
（2） 画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，因F(x0, y0)=0，则d0=a+0.5b。
（3）程序中只利用d的符号，d的增量都是整数，只是初始值包含小数，用2d代替d，使程序中仅包含整数的运算。

//Bresenham算法生成直线
void CMyView::OnBresenhamline()
{
CDC* pDC=GetDC();
int x1=100, y1=200, x2=350, y2=100,c=RGB(0,0,255);
int i,s1,s2,interchange;
float x,y,deltax,deltay,f,temp;
x=x1;
y=y1;
deltax=abs(x2-x1);
deltay=abs(y2-y1);
if(x2-x1>=0) s1=1; else s1=-1;
if(y2-y1>=0) s2=1; else s2=-1;
if(deltay>deltax){
temp=deltax;
deltax=deltay;
deltay=temp;
interchange=1;
}
else interchange=0;
f=2*deltay-deltax;
pDC->SetPixel(x,y,c);
for(i=1;i<=deltax;i++){
if(f>=0){
if(interchange==1) x+=s1;
else y+=s2;
pDC->SetPixel(x,y,c);
f=f-2*deltax;
}
else{
if(interchange==1) y+=s2;
else x+=s1;
f=f+2*deltay;
}
}
}

说明：
（1）以上程序已经考虑到所有象限直线的生成。
（2）Bresenham算法的优点如下：
① 不必计算直线的斜率，因此不做除法。
② 不用浮点数，只用整数。
③ 只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。
④ Bresenham算法的运算速度很快。

② 假设圆的圆心不在原点，试编写算法对整个圆进行扫描转换

扫描转换是啥意思

③ 在opengl应用框架下圆弧的扫描转换算法 怎么点用辅助函数

在平面解析几何中，圆的方程可以描述为(x – x0)2 + (y – y0)2 = R2，其中(x0, y0)是圆心坐标，R是圆的半径，特别的，当(x0, y0)就是坐标中心点时，圆方程可以简化为x2 + y2 = R2。在计算机图形学中，圆和直线一样，也存在在点阵输出设备上显示或输出的问题，因此也需要一套光栅扫描转换算法。为了简化，我们先考虑圆心在原点的圆的生成，对于中心不是原点的圆，可以通过坐标的平移变换获得相应位置的圆。
在进行扫描转换之前，需要了解一个圆的特性，就是圆的八分对成性。

④ 学习计算机图形学的书籍介绍

目录

计算机图形学基础教程（Visual C++版）

第1章 导论1
1.1 计算机图形学的应用领域1
1.1.1 计算机辅助设计1
1.1.2 计算机艺术1
1.1.3 虚拟现实3
1.1.4 计算机辅助教学3
1.2 计算机图形学的概念4
1.3 计算机图形学的相关学科5
1.4 计算机图形学的确立和发展5
1.5 图形显示器的发展及其工作原理7
1.5.1 阴极射线管7
1.5.2 随机扫描显示器8
1.5.3 直视储存管显示器8
1.5.4 光栅扫描显示器9
1.5.5 液晶显示器13
1.5.6 等离子显示器15
1.5.7 三维显示器15
1.6 图形软件标准的形成18
1.7 计算机图形学的最新技术18
1.7.1 交互技术18
1.7.2 造型技术18
1.7.3 真实感图形显示技术19
1.8 小结19
习题119第2章 Visual C++6.0绘图基础21
2.1 面向对象程序设计基础21
2.1.1 类和对象21
2.1.2 构造函数和析构函数22
2.1.3 对象的动态建立和释放24
2.1.4 继承与派生25
2.2 MFC上机操作步骤28
2.3 基本绘图函数31
2.3.1 CDC类结构和GDI对象32
2.3.2 映射模式33
2.3.3 CDC类的主要绘图成员函数34
2.3.4 设备上下文的调用和释放50
2.3.5 VC++绘制图形的几种方法51
2.4 小结52
习题252第3章 基本图形的扫描转换55
3.1 直线的扫描转换55
3.1.1 算法原理56
3.1.2 构造中点偏差判别式56
3.1.3 递推公式57
3.2 圆的扫描转换57
3.2.1 算法原理58
3.2.2 构造中点偏差判别式59
3.2.3 递推公式60
3.3 椭圆的扫描转换60
3.3.1 算法原理61
3.3.2 构造上半部分I中点偏差判别式62
3.3.3 上半部分I的递推公式62
3.3.4 构造下半部分II中点偏差判别式64
3.3.5 下半部分II的递推公式64
3.4 反走样技术66
3.5 直线距离加权反走样算法67
3.5.1 算法原理67
3.5.2 构造距离判别式69
3.5.3 计算机化69
3.6 小结69
习题369第4章 多边形填充72
4.1 实面积图形的概念72
4.1.1 多边形的定义73
4.1.2 多边形的表示73
4.1.3 多边形的填充74
4.1.4 区域填充74
4.2 有效边表填充算法75
4.2.1 填充原理75
4.2.2 边界像素的处理原则75
4.2.3 有效边和有效边表76
4.2.4 边表79
4.3 边缘填充算法80
4.3.1 填充原理80
4.3.2 填充过程80
4.4 区域填充算法82
4.4.1 填充原理82
4.4.2 四邻接点和八邻接点82
4.4.3 四连通域和八连通域83
4.4.4 四邻接点填充算法和八邻接点填充算法84
4.5 小结85
习题485第5章 二维变换和裁剪89
5.1 图形几何变换基础89
5.1.1 规范化齐次坐标89
5.1.2 矩阵相乘89
5.1.3 二维变换矩阵90
5.1.4 二维几何变换90
5.2 二维图形基本几何变换矩阵91
5.2.1 平移变换矩阵91
5.2.2 比例变换矩阵91
5.2.3 旋转变换矩阵92
5.2.4 反射变换矩阵93
5.2.5 错切变换矩阵94
5.3 二维复合变换95
5.3.1 复合变换原理95
5.3.2 相对于任一参考点的二维几何变换95
5.3.3 相对于任意方向的二维几何变换96
5.4 二维图形裁剪98
5.4.1 图形学中常用的坐标系98
5.4.2 窗口和视区及窗视变换99
5.4.3 窗视变换矩阵100
5.5 Cohen-Sutherland直线裁剪算法101
5.5.1 编码原理101
5.5.2 裁剪步骤102
5.5.3 交点计算公式102
5.6 中点分割直线裁剪算法103
5.6.1 中点分割直线裁剪算法原理103
5.6.2 中点计算公式103
5.7 梁友栋-Barsky直线裁剪算法103
5.7.1 梁友栋算法原理103
5.7.2 算法分析104
5.7.3 算法的几何意义104
5.8 小结106
习题5106第6章 三维变换和投影108
6.1 三维几何变换108
6.1.1 三维变换矩阵108
6.1.2 三维几何变换108
6.2 三维基本几何变换矩阵109
6.2.1 平移变换109
6.2.2 比例变换109
6.2.3 旋转变换110
6.2.4 反射变换111
6.2.5 错切变换112
6.3 三维复合变换113
6.4 投影变换115
6.4.1 三视图115
6.4.2 斜等侧图118
6.5 透视变换120
6.5.1 透视变换坐标系120
6.5.2 坐标系变换121
6.5.3 用户坐标系到观察坐标系的变换122
6.5.4 观察坐标系到屏幕坐标系的变换124
6.5.5 透视投影分类125
6.6 小结127
习题6128第7章 自由曲线和曲面130
7.1 基本概念130
7.1.1 样条曲线曲面130
7.1.2 曲线曲面的表示形式130
7.1.3 拟合和逼近131
7.1.4 连续性条件131
7.2 三次参数样条曲线132
7.2.1 参数样条曲线定义132
7.2.2 系数求解133
7.2.3 边界条件133
7.3 Hermite样条曲线135
7.4 Bezier曲线137
7.4.1 Bezier曲线的定义137
7.4.2 Bezier曲线的性质139
7.4.3 Bezier曲线的可分割性139
7.5 Bezier曲面141
7.5.1 Bezier曲面的定义141
7.5.2 双三次Bezier曲面的定义141
7.6 B样条曲线142
7.6.1 B样条曲线的定义143
7.6.2 二次B样条曲线143
7.6.3 三次B样条曲线144
7.6.4 B样条曲线的性质146
7.6.5 构造特殊的三次B样条曲线的技巧148
7.7 B样条曲面149
7.7.1 B样条曲面的定义149
7.7.2 双三次B样条曲面的定义149
7.7.3 双三次B样条曲面的连续性150
7.8 小结152
习题7152第8章 分形几何156
8.1 分形和分维156
8.1.1 分形的诞生156
8.1.2 分形的基本特征157
8.1.3 分形的定义158
8.1.4 分形维数的定义158
8.2 递归模型160
8.2.1 Cantor集160
8.2.2 Koch曲线161
8.2.3 Peano-Hilbert曲线162
8.2.4 Sierpinski垫片、地毯和海绵164
8.2.5 C字曲线168
8.2.6 Caley树168
8.3 L系统模型169
8.3.1 L系统文法169
8.3.2 Koch曲线170
8.3.3 分形草171
8.3.4 Peano-Hilbert曲线171
8.3.5 分形灌木丛173
8.4 IFS迭代函数系统模型174
8.4.1 仿射变换174
8.4.2 IFS175
8.4.3 Koch曲线178
8.4.4 Sierpinski垫片180
8.4.5 枫叶生成182
8.5 小结183
习题8183第9章 动态消隐187
9.1 图形的数据结构187
9.1.1 图形的几何信息和拓扑信息187
9.1.2 基本图形的数据结构187
9.1.3 立体表示模型188
9.2 消隐算法分类190
9.3 隐线算法190
9.3.1 凸多面体消隐算法190
9.3.2 曲面体消隐算法192
9.4 隐面算法194
9.4.1 Z-Buffer算法194
9.4.2 画家算法197
9.5 小结198
习题9198第10章 真实感图形201
10.1 颜色模型201
10.1.1 基本概念201
10.1.2 RGB颜色模型202
10.1.3 Gouraud颜色渐变203
10.2 材质模型和光照模型205
10.2.1 物体的材质205
10.2.2 环境光模型206
10.2.3 漫反射光模型206
10.2.4 镜面反射光模型207
10.2.5 光强的衰减208
10.3 纹理映射209
10.3.1 纹理定义209
10.3.2 纹理映射210
10.4 OpenGL简介210
10.4.1 案例效果210
10.4.2 TestView.h文件210
10.4.3 TestView.cpp文件213
10.4.4 程序说明220
10.5 小结222
习题10222附录A 配套实践教程的案例设置及与本书的对应关系225

⑤ 四道图像图像算法题目

取X=0时，在Y轴上画点1。
取Y=0时，在X轴上画点2。
画直线通过两点。
你画的X=0时，Y是几？自己数手指头去。

⑥ 详细论述直线与圆的扫描转换算法,并写出C++的实现代码。

推荐去CNKI撒，清华搞的撒，那里面是论文数据库，可以随时下载的。你要搞不定的话，去淘宝的///翰林书店///，能下载到论文的

⑦ 计算机图形学 问题 中点圆算法和扫描线算法

写个文档解释一下。

⑧ 跪求一个能画出彩色花朵的计算机图形学课程设计源代码，如图

目前在电子行业使用比较多的产品主要有ASIC和FPGA，在这两者之间FPGA是最具有技术优势的一种产品，并且具有逐渐取代ASIC的趋势。
ASIC是专用集成电路的英文简称。在过去的一段时间中，ASIC设计技术一直是集成电路设计市场的主流。一般说来，ASIC主要针对大批量生产的专用产品，以尽可能的降低生产设计成本。而FPGA由于其良好的可配置特性广泛应用小批量的产品设计中，尤其是在ASIC的原型验证阶段经常使用FPGA来构建硬件平台。但是随着FPGA在性能、密度上的提升，以及芯片制造工艺的改进导致的NRE成本激增，使ASIC的市场逐渐被FPGA所占据。
对于ASIC与没有使用嵌入式硬核基于LUT的FPGA(图1-2)而言，ASIC与FPGA的延迟性能大概相差12～14倍，并且该结果针对0.25um～90nm的CMOS工艺都是基本适用的。不考虑性能的情况下，对于实现相同的逻辑功能而言，没有使用硬核的FPGA比ASIC面积大35倍，动态功耗增加14倍以上。
22fgcfcvg

⑨ 计算机图形学基础教程的目录

第1章 绪论
1.1 计算机图形学的研究内容
1.2 计算机图形学发展的历史回顾
1.3 计算机图形学的应用及研究前沿
1.3.1 计算机辅助设计与制造
1.3.2 可视化
1.3.3 真实感图形实时绘制与自然景物仿真
1.3.4 计算机动画
1.3.5 用户接口
1.3.6 计算机艺术
1.4 图形设备
1.4.1 图形显示设备
1.4.2 图形处理器
1.4.3 图形输入设备
习题
第2章 光栅图形学
2.1 直线段的扫描转换算法
2.1.1 DDA法
2.1.2 中点画线法
2.1.3 Bresenham算法
2.2 圆弧的扫描转换算法
2.2.1 圆的特征
2.2.2 中点画圆法
2.3 多边形的扫描转换与区域填充
2.3.1 多边形的扫描转换
2.3.2 区域填充算法
2.4 字符
2.4.1 点阵字符
2.4.2 矢量字符
2.4.3 字符属性
2.5 裁剪
2.5.1 直线段裁剪
2.5.2 多边形裁剪
2.5.3 字符裁剪
2.6 反走样
2.6.1 提高分辨率
2.6.2 区域采样
2.6.3 加权区域采样
2.7 消隐
2.7.1 消隐的分类
2.7.2 消除隐藏线
2.7.3 消除隐藏面
习题
第3章 几何造型技术
3.1 参数曲线和曲面
3.1.1 曲线曲面的表示
3.1.2 曲线的基本概念
3.1.3 插值、拟合和光顺
3.1.4 参数化
3.1.5 参数曲线的代数和几何形式
3.1.6 连续性
3.1.7 参数曲面的基本概念
3.2 Bezier曲线与曲面
3.2.1 Bezier曲线的定义和性质
3.2.2 Bezier曲线的递推(de Casteljau)算法
3.2.3 Bezier曲线的拼接
3.2.4 Bezier曲线的升阶与降阶
3.2.5 Bezier曲面
3.2.6 三边Bezier曲面片
3.3 B样条曲线与曲面
3.3.1 B样条的递推定义和性质
3.3.2 B样条曲线的性质
3.3.3 de Boor算法
3.3.4 节点插入算法
3.3.5 B样条曲面
3.4 NURBS曲线与曲面
3.4.1 NURBS曲线的定义
3.4.2 齐次坐标表示
3.4.3 权因子的几何表示
3.4.4 圆锥曲线的NURBS表洋
3.4.5 NURBS曲线的修改
3.4.6 非均匀有理B样条（NURBS）曲面
3.5 Coons曲面
3.5.1 基本概念
3.5.2 双线性Coons曲面
3.5.3 双三次Coons曲面
3.6 形体在计算机内的表示
3.6.1 引言
3.6.2 形体表示模型
3.6.3 形体的边界表示模型
3.7 求交分类
3.7.1 求交分类简介
3.7.2 求交分类策略
3.7.3 基本的求交算法
3.8 实体造型系统简介
3.8.1 Parasolid系统
3.8.2 ACIS系统
习题
第4章 真实感图形学
4.1 颜色视觉
4.1.1 基本概念
4.1.2 三色学说
4.1.3 CIE色度图
4.1.4 常用的颜色模型
4.2 简单光照明模型
4.2.1 相关知识
4.2.2 Phong光照明模型
4.2.3 增量式光照明模型
4.2.4 阴影的生成
4.3 局部光照明模型
4.3.1 理论基础
4.3.2 局部光照明模型
4.4 光透射模型
4.4.1 透明效果的简单模拟
4.4.2 Whitted光透射模型
4.4.3 Hall光透射模型
4.4.4 简单反射透射模型
4.5 纹理及纹理映射
4.5.1 纹理概述
4.5.2 二维纹理域的映射
4.5.3 三维纹理域的映射
4.5.4 几何纹理
4.6 整体光照明模型
4.6.1 光线跟踪算法
4.6.2 辐射度方法
4.7 实时真实感图形学技术
4.7.1 层次细节显示和简化
4.7.2 基于图像的绘制技术
习题
第5章 图形标准
5.1 Open GL
5.1.1 Open GL概述
5.1.2 Open GL程序结构
5.1.3 基本几何元素
5.1.4 坐标变换
5.1.5 光照处理
5.2 VRML
5.2.1 VRML简介
5.2.2 线性变换
5.2.3 场景交互
5.2.4 VRML节点
5.2.5 VRML展望
习题
附录A 计算机图形学的数学基础
附录B 图形的几何变换
附录C 形体的投影变换
参考文献