计算机图形学——区域填充的扫描线算法
一．实验名称：
区域填充的扫描线算法
二．实验目的：
1、理解区域填充扫描线算法的原理；
2、实现区域填充的扫描线算法并测试；
三．算法原理：
算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。
借助于栈结构，区域填充的扫描线算法之步骤如下：
Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈；
Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点；
Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。分别以xl 和xr 表示该填充区段两端点的横坐标；
Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条
扫描线上位于区段[xl, xr] 内的区域内的区段。若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。
四．原程序代码：
/*****************************************/
/*4-ScanLineFill 区域填充的扫描线算法实现*/
/*****************************************/
#include
#include
#include
#include
#define Stack_Size 100 //栈的大小常量
//定义结构体,记录种子点
typedef struct{
int x;
int y;
}Seed;
//定义顺序栈(种子点)
typedef struct
{
Seed Point[Stack_Size];
int top;
}SeqStack;
//初始化栈操作
void InitStack(SeqStack *&S)
{
S=(SeqStack *)malloc(sizeof(SeqStack));
S->top=-1;
}
//种子点栈置空；
void setstackempty (SeqStack *S)
{
S->top==-1;
}
//种子点栈状态检测函数
int isstackempty (SeqStack *S)
{
if(S->top==-1)
return true; //空栈返回true
else
return false; //非空栈返回false
}
//种子点入栈；
int stackpush (SeqStack *&S,Seed point)
{
if(S->top==Stack_Size-1)//栈已满，返回false return false;
S->top++;//栈未满，栈顶元素加1
S->Point[S->top]= point;
return true;
}
//取栈顶元素；
int stackpop (SeqStack *&S,Seed &point)
{
if(S->top==-1)//栈为空，返回false
return false;
point=S->Point[S->top];
S->top --;//栈未空，top减1
return true;
}
//画圆
void CirclePoints (int xc, int yc, int x, int y, int Color) {
putpixel (xc + x, yc + y, Color);
putpixel (xc + x, yc - y, Color);
putpixel (xc - x, yc + y, Color);
putpixel (xc - x, yc - y, Color);
putpixel (xc + y, yc + x, Color);
putpixel (xc + y, yc - x, Color);
putpixel (xc - y, yc + x, Color);
putpixel (xc - y, yc - x, Color); }
//中点画圆算法
void MidpointCircle(int radius, int Color) {
int x, y;
float d;
x=0;
y=radius;
d=5.0/4-radius;
CirclePoints(250,250,x,y,Color);
while(x { if (d<0) { d+=x*2.0+3; } else { d+=(x-y)*2.0+5; y--; } x++; CirclePoints(250,250,x,y,Color); } } //四连通扫描线算法 void ScanLineFill4(int x, int y, int oldcolor, int newcolor) { int xl, xr, i; bool SpanNeedFill; Seed pt;//种子点 SeqStack *S;//定义顺序栈 InitStack(S);//定义了栈之后必须把栈先初始化 setstackempty(S);//种子点栈置空； pt.x = x; pt.y = y; stackpush (S,pt); // 种子点(x, y)入栈 while (!isstackempty(S)) { stackpop (S,pt);//取种子点 y = pt.y; x = pt.x; while (getpixel (x,y)==oldcolor) {// 从种子点开始向右填充putpixel (x, y, newcolor); x++; } xr = x -1; x = pt.x -1; while (getpixel (x,y)==oldcolor) { // 从种子点开始向左填充putpixel (x, y, newcolor); x--; } xl = x + 1; x = xl; y = y +1; // 处理上面一条扫描线while (x < xr) { SpanNeedFill = false; while (getpixel (x, y)==oldcolor) { SpanNeedFill = true; x++ ; } // 待填充区段搜索完毕 if (SpanNeedFill) {// 将右端点作为种子点入栈 pt.x = x - 1; pt.y = y; stackpush (S,pt); SpanNeedFill = false; } //继续向右检查以防遗漏 while ((getpixel (x, y)!=oldcolor) && (x< xr)) x++; } //上一条扫描线上检查完毕 x = xl; y=y-2; // 处理下面一条扫描线 while (x < xr) { SpanNeedFill = false; while (getpixel (x, y)==oldcolor) { SpanNeedFill=true; x++ ; } if (SpanNeedFill) { pt.x= x - 1; pt.y = y; stackpush (S,pt); SpanNeedFill=false; } while ((getpixel (x, y)!=oldcolor) && (x < xr)) x++; } } } //主函数检测 void main() { int radius,color; int x,y;//种子点 int oldcolor,newcolor;//原色与填充色 //输入参数值 printf("input radius and color:\n");//画圆参数 scanf("%d,%d",&radius,&color); printf("input x and y:\n"); //读入内点 scanf("%d,%d", &x, &y); printf("input oldcolor and newcolor:\n"); //读入原色与填充色scanf("%d,%d", &oldcolor, &newcolor); int gdriver = DETECT,gmode; initgraph(&gdriver, &gmode, "c:\\tc"); // 用背景色清空屏幕 cleardevice(); // 设置绘图色为红色 setcolor(RED); MidpointCircle(radius,color);//用中点画圆算法画圆 rectangle(150, 150, 350, 350);//再画一个矩形区域 ScanLineFill4 (x,y,oldcolor,newcolor);//扫描线区域填充 getch(); closegraph(); } 五．运行结果与讨论： 测试结果1： 测试结果2： 六．实验分析与讨论： 1.通过借助栈这一数据结构，完成了区域填充的扫描线算法的实现，并利用以前所学的画圆等算法，进行综合运用，在此基础上进行扩充，设计多种图案，进行扫描线填充算法的检测，都得到了理想的结果，体现了算法的有效性； 2.栈的数据结构给种子点的操作带来了极大的方便，为算法的实现提供了便利，同时还提高了算法的复用性和可靠性； 3.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。 13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。 解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表： 6-10 5 4 3 2 1 该多边形的AET指针的内容为： 1 AET为空 2 3 4 1 2 3 4 5 6 7 8 9 10 01234567891011121314 1516 5 6 7 8 9 10 具体编程实现如下： 第1步：(1) 根据输入的五个顶点坐标找到y 值最小的点(例如点D ，此时y=2)，并找到与D 有边关系的两个顶点(此时为E 和C)，在y=2处建立ET 边表记录(ymax 、xi 和m 值均可通过顶点坐标间的计算得到，例如DE 边的建立，特别注意：当D 点和E 点y 坐标值相同时，也即是DE 与x 轴平行，该边不能计入ET 边表)，之后标记D 点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET 表建立完善。 [注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y 坐标值，ET 边表采用邻接表的数据结构 第2步：根据ET 表构建AET 表，并逐行完成多边形填充，具体的C++代码如下： (1) 建立头文件base_class.h ，主要是边表结点结构体和ET 边表类的实现 enum ResultCode{Success, Failure}; template 实验四区域填充算法的实现 班级 08信计2班学号 20080502088 姓名许延恒分数 一、实验目的和要求： 1、理解区域的表示和类型。 2、能正确区分四连通和八连通的区域 3、了解区域填充的实验原理。 4、利用C++实现区域填充的递归算法。 二、实验内容： 1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。 2 取（x，y）为种子点将整个区域填充为新的颜色。 3 进行递归填充。 三、实验结果分析 区域填充属性包括填充样式，填充颜色和填充图案的类型。C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充 . 程序代码 #include 扫描线算法（S c a n-L i n e F i l l i n g） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指 定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种常用算法》 一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以 判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是 只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法效率问题之外，还 存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就 有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此， 适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相 连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照 x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。 多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步 继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的 特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。 对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效 率底下，如图（6）所示： 图（6）多边形与扫描线示意图 实验四区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0（及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include 实验报告 一、实验目的 1、掌握有序边表算法填充多边形区域； 2、理解多边形填充算法的意义； 3、增强C语言编程能力。 二、算法原理介绍 根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容 1.x -当前扫描线与这条边交点的x坐标； 2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量； 3.ymax -该边最高顶点相交的扫描线号。 每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。 当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。 当多边形新边表ET构成后，按下列步骤进行： ①对每一条扫描线i，初始化ET表的表头指针ET[i]； ②将ymax = i的边放入ET[i]中； ③使y =多边形最低的扫描线号； ④初始化活性边表AET为空； ⑤循环，直到AET和ET为空。 ●将新边表ET中对应y值的新边节点插入到AET表。 ●遍历AET表，将两两配对的交点之间填充给定颜色值。 ●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增Δx；并重新排序。 ●y增加1。 三、程序源代码 #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h" #include "dos.h" #include "conio.h" typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */ 任意封闭多边形的扫描线填充算法类收藏 这个代码不是我写的，但是我肯定这代码是一个牛人写的，放在这里供大家学习和使用啦！感谢原作者！ 我在这里做了些改进： 1 去除了绘制多边形的函数，使其成为了一个纯的填充算法模块 2 改进了其成员变量，使其更容易让大多数人所使用 3 改进了填充，使其“看”（代码上）起来更像用扫描线在填充 改进后的扫描线算法类如下： //扫描线填充算法类 class CPFill { public: CPoint *Point; //指向点坐标的指针 int Count; //多边形点的个数 public: CPFill(int,int[],int[]);//构造函数 bool FillPolygon(CDC*);//填充多边形 bool CrossJudge(CPoint,CPoint,CPoint,CPoint,CPoint&);//判断两条线段是否相交 int GetAi(int);//获取下一个点的索引号 int GetBi(int);//获取前一个点的索引号 bool Sort(int*,int);//冒泡排序 ~CPFill();//析构函数 }; //构造函数（模块入口，koradji 注，合理的设计这个地方，就可以完全不用改动其他的地方就可以使用这个类） CPFill::CPFill(){ } //获取前一个点的索引号 int CPFill::GetBi(int i) { return (i==0)? Count-1:i-1; } //获取下一个点的索引号 int CPFill::GetAi(int i) { return (i==Count-1)?0:i+1; } //在指定的pDC设备中，填充多边形 bool CPFill::FillPolygon(CDC* pDC) { //获取多边形中所有坐标点的最大值和最小值，作为扫描线循环的范围 int minX=Point[0].x , minY=Point[0].y; int maxX=Point[0].x , maxY=Point[0].y; for(int i=1;i Phong Lighting 该模型计算效率高、与物理事实足够接近。Phong模型利用4个向量计算表面任一点的颜色值，考虑了光线和材质之间的三种相互作用：环境光反射、漫反射和镜面反射。Phong模型使用公式：I s=K s L s cosαΦα：高光系数。计算方面的优势：把r和v归一化为单位向量，利用点积计算镜面反射分量：I s=K s L s max((r，v)α，0)，还可增加距离衰减因子。 在Gouraud着色这种明暗绘制方法中，对公用一个顶点的多边形的法向量取平均值，把归一化的平均值定义为该顶点的法向量，Gouraud着色对顶点的明暗值进行插值。Phong着色是在多边形内对法向量进行插值。Phong着色要求把光照模型应用到每个片元上，也被称为片元的着色。 颜色模型RGB XYZ HSV RGB:RGB颜色模式已经成为现代图形系统的标准，使用RGB加色模型的RGB三原色系统中，红绿蓝图像在概念上有各自的缓存，每个像素都分别有三个分量。任意色光F都可表示为F＝r [ R ] + g [ G ] + b [ B ]。RGB颜色立方体中沿着一个坐标轴方向的距离代表了颜色中相应原色的分量，原点(黑)到体对角线顶点(白)为不同亮度的灰色 XYZ:在RGB 系统基础上，改用三个假想的原色X、Y、Z建立了一个新的色度系统, 将它匹配等能光谱的三刺激值,该系统称为视场XYZ色度系统，在XYZ空间中不能直观地评价颜色。 HSV是一种将RGB中的点在圆柱坐标系中的表示法，H色相S饱和度V明度，中心轴为灰色底黑顶白，绕轴角度为H，到该轴距离为S，沿轴高度为S。 RGB优点:笛卡尔坐标系，线性，基于硬件(易转换)，基于三刺激值，缺点:难以指定命名颜色，不能覆盖所有颜色范围，不一致。 HSV优点:易于转换成RGB，直观指定颜色，’缺点:非线性，不能覆盖所有颜色范围，不一致 XYZ:覆盖所有颜色范围，基于人眼的三刺激值，线性，包含所有空间，缺点:不一致 交互式计算机程序员模型 (应用模型<->应用程序<->图形库)->(图形系统<->显示屏).应用程序和图形系统之间的接口可以通过图形库的一组函数来指定，这和接口的规范称为应用程序编程人员接口(API)，软件驱动程序负责解释API的输出并把这些数据转换为能被特定硬件识别的形式。API提供的功能应该同程序员用来确定图像的概念模型相匹配。建立复杂的交互式模型，首先要从基本对象开始。良好的交互式程序需包含下述特性：平滑的显示效果。使用交互设备控制屏幕上图像的显示。能使用各种方法输入信息和显示信息。界面友好易于使用和学习。对用户的操作具有反馈功能。对用户的误操作具有容忍性。Opengl并不直接支持交互，窗口和输入函数并没有包含在API中。 简单光线跟踪、迭代光线跟踪 光线跟踪是一种真实感地显示物体的方法，该方法由Appel在1968年提出。光线跟踪方法沿着到达视点的光线的相反方向跟踪，经过屏幕上每一象素，找出与视线所交的物体表面点P0，并继续跟踪，找出影响P0点光强的所有的光源，从而算出P0点上精确的光照强度。光线跟踪器最适合于绘制具有高反射属性表面的场景。优缺点：原理简单，便于实现，能生成各种逼真的视觉效果，但计算量开销大，终止条件：光线与光源相交光线超出视线范围，达到最大递归层次。一般有三种：1)相交表面为理想漫射面，跟踪结束。2)相交表面为理想镜面，光线沿镜面反射方向继续跟踪。3)相交表面为规则透射面，光线沿规则透射方向继续跟踪。 描述光线跟踪简单方法是递归，即通过一个递归函数跟踪一条光线，其反射光想和折射光线再调用此函数本身，递归函数用来跟踪一条光线，该光线由一个点和一个方向确定，函数返回与光线相交的第一个对象表面的明暗值。递归函数会调用函数计算指定的光线与最近对象表面的交点位置。 图形学算法加速技术BVH, GRID, BSP, OCTree 加速技术：判定光线与场景中景物表面的相对位置关系，避免光线与实际不相交的景物表面的求交运算。加速器技术分为以下两种：Bounding Volume Hierarchy 简写BVH，即包围盒层次技术，是一种基于“物体”的场景管理技术，广泛应用于碰撞检测、射线相交测试之类的场合。BVH的数据结构其实就是一棵二叉树（Binary Tree）。它有两种节点（Node）类型：Interior Node 和Leaf Node。前者也是非叶子节点，即如果一个Node不是Leaf Node，它必定是Interior Node。Leaf Node 是最终存放物体/们的地方，而Interior Node存放着代表该划分（Partition）的包围盒信息，下面还有两个子树有待遍历。使用BVH需要考虑两个阶段的工作：构建（Build）和遍历（Traversal）。另一种是景物空间分割技术，包括BSP tree，KD tree Octree Grid BSP:二叉空间区分树 OCTree:划分二维平面空间无限四等分 Z-buffer算法 算法描述：1、帧缓冲器中的颜色设置为背景颜色2、z缓冲器中的z值设置成最小值（离视点最远）3、以任意顺序扫描各多边形a) 对于多边形中的每一个采样点，计算其深度值z(x,y) b) 比较z(x, y)与z缓冲器中已有的值zbuffer(x,y)如果z(x, y) >zbuffer(x, y)，那么计算该像素(x, y)的光亮值属性并写入帧缓冲器更新z缓冲器zbuffer(x, y)＝z(x, y) Z-buffer算法是使用广泛的隐藏面消除算法思想为保留每条投影线从COP到已绘制最近点距离，在投影后绘制多边形时更新这个信息。存储必要的深度信息放在Z缓存中，深度大于Z缓存中已有的深度值，对应投影线上已绘制的多边形距离观察者更近，故忽略该当前多边形颜色，深度小于Z缓存中的已有深度值，用这个多边形的颜色替换缓存中的颜色，并更新Z缓存的深度值。 void zBuffer() {int x, y; for (y = 0; y < YMAX; y++) for (x = 0; x < XMAX; x++) { WritePixel (x, y, BACKGROUND_VALUE); WriteZ (x, y, 1);} for each polygon { for each pixel in polygon’s projection { //plane equation doubl pz = Z-value at pixel (x, y); if (pz < ReadZ (x, y)) { // New point is closer to front of view WritePixel (x, y, color at pixel (x, y)) WriteZ (x, y, pz);}}}} 优点：算法复杂度只会随着场景的复杂度线性增加、无须排序、适合于并行实现 缺点：z缓冲器需要占用大量存储单元、深度采样与量化带来走样现象、难以处理透明物体 着色器编程方法vert. frag 着色器初始化：1、将着色器读入内存2、创建一个程序对象3、创建着色器对象4、把着色器对象绑定到程序对象5、编译着色器6、将所有的程序连接起来7、选择当前的程序对象8、把应用程序和着色器之间的uniform变量及attribute变量关联起来。 Vertex Shader：实现了一种通用的可编程方法操作顶点，输入主要有：1、属性、2、使用的常量数据3、被Uniforms使用的特殊类型4、顶点着色器编程源码。输入叫做varying变量。被使用在传统的基于顶点的操作，例如位移矩阵、计算光照方程、产生贴图坐标等。Fragment shader：计算每个像素的颜色和其他属性，实现了一种作用于片段的通用可编程方法，对光栅化阶段产生的每个片段进行操作。输入：Varying 变量、Uniforms-用于片元着色器的常量，Samples-用于呈现纹理、编程代码。输出：内建变量。 观察变换 建模变换是把对象从对象标架变换到世界标架 观察变换把世界坐标变换成照相机坐标。VC是与物理设备无关的，用于设置观察窗口观察和描述用户感兴趣的区域内部分对象，观察坐标系采用左手直角坐标系，可在用户坐标系中的任何位置、任何方向定义。其中有一坐标轴与观察方向重合同向并与观察平面垂直。观察变换是指将对象描述从世界坐标系变换到观察坐标系的过程。（1）：平移观察坐标系的坐标原点，与世界坐标系的原点重合，（2）：将x e，y e轴分别旋转（-θ）角与x w、y w轴重合。 规范化设备坐标系 规范化设备坐标系是与具体的物理设备无关的一种坐标系，用于定义视区，描述来自世界坐标系窗口内对象的图形。 光线与隐式表面求交 将一个对象表面定义为f(x,y,z)=f(p)=0,来自P0，方向为d的光线用参数的形式表示为P(t)=P0+td. 交点位置处参数t的值满足：f(P0+td)=0,若f是一个代数曲面，则f是形式为X i Y j Z k的多项式之和，求交就转化为寻求多项式所有根的问题，满足的情况一：二次曲面，情况二：品面求交，将光线方程带入平面方程：p*n+c=0可得到一个只需做一次除法的标量方程p=p0+td。可通过计算得到交点的参数t的值：t=(p0*n+c)/(n*d). 几何变换T R S矩阵表示 三维平移T 三维缩放S旋转绕z轴Rz( ) 100dx 010dy 001dz 0001 Sx000 0Sy00 00Sz0 0001 cos-sin00 sin cos00 0010 0001 θθ θθ 旋转绕x轴Rx(θ) 旋转绕y轴Ry(θ) 1000 0cos-sin0 0sin cos0 0001 θθ θθ cos0sin0 0100 -sin0cos0 0001 θθ θθ 曲线曲面 Bezier曲线性质：Bezier曲线的起点和终点分别是特征多边形的第一个顶点和最后一个顶点。曲线在起点和终点处的切线分别是特征多边形的第一条边和最后一条边，且切矢的模长分别为相应边长的n倍；（2）凸包性；（3）几何不变性（4）变差缩减性。端点插值。 均匀B样条曲线的性质包括：凸包性、局部性、B样条混合函数的权性、连续性、B样条多项式的次数不取决于控制函数。 G连续C连续 C0连续满足：C1连续满足： (1)(0) p(1)=(1)(0)(0) (1)(0) px qx py q qy pz qz == ???? ???? ???? ???? (1)(0) p'(1)=(1)'(0)(0) (1)(0) p x q x p y q q y p z q z == ???? ???? ???? ???? C0(G0)连续:曲线的三个分量在连接点必须对应相等 C1连续:参数方程和一阶导数都对应相等 G1连续:两曲线的切线向量成比例 三维空间中，曲线上某点的导数即是该点的切线，只要求两个曲线段连接点的导数成比例，不需要导 数相等，即p’(1)=aq’(0) 称为G1几何连续性。将该思想推广到高阶导数，就可得到C n和G n连续性。 课程设计报告 课程名称计算机图形学 课题名称多边形裁剪与填充 专业计算机科学与技术 班级计算机0902 学号 姓名 指导教师刘长松曹燚 2012年10 月9 日 湖南工程学院 课程设计任务书 课程名称计算机图形学课题多边形裁剪与填充 专业班级计算机0902 学生姓名 学号 指导老师刘长松曹燚 审批 任务书下达日期2012年9月15 日 任务完成日期2012 年10月9 日 一、设计内容与设计要求 1．设计内容： 交互式地实现多边形的裁剪和填充。。 2．设计要求： 1）窗口功能设计。 2）实现鼠标画多边形与数据存储功能。 3）实现鼠标剪裁窗口选择功能。 4）实现多边形裁剪和填充功能。 3.算法提示： 多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。 多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。 二、进度安排 第 3 周星期一8：00——12：00 星期二8：00——12：00 星期三8：00——12：00 星期四8：00——12：00 星期五8：00——12：00 第 4 周星期一8：00——12：00 附： 课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大小的图纸及程序清单）、评分。正文的格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。 扫描线算法（Scan-Line F illing） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏 和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种 常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断 算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但 是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交 算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之 间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这 个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能 是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由 多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列 交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个 端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤： （1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进 行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然 后转第1步继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是 线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出 显示。 实验三多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤（程序实现）。 1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2)对临时AET表排序，按照x递增的顺序存放。 3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline 4)扫描AET表，填充扫描线和多边形相交的区间。 计算机图形学——区域填充的扫描线算法 一．实验名称： 区域填充的扫描线算法 二．实验目的： 1、理解区域填充扫描线算法的原理； 2、实现区域填充的扫描线算法并测试； 三．算法原理： 算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 借助于栈结构，区域填充的扫描线算法之步骤如下： Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈； Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点； Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。分别以xl 和xr 表示该填充区段两端点的横坐标； Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条 扫描线上位于区段[xl, xr] 内的区域内的区段。若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。 四．原程序代码： /*****************************************/ /*4-ScanLineFill 区域填充的扫描线算法实现*/ /*****************************************/ #include 实验六扫描线填充算法 一、实验目的 编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。 二、实验任务（2学时） 编写多边形的扫描线填充算法程序，利用数组实现AET，考虑与链表实现程序的不同。 三、实验内容 1、算法 对一条扫描线的填充一般分为以下4个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把扫描线上所有交点按递增顺序进行排序； （3）配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。 （4）着色：把区间内的像素置为填充色。 2、成员函数的关系 主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共c ount个）的x和y坐标。它调用8个子程序，彼此之间的调用关系图1所示为： 图1 fill_area的程序结构 3、算法的程序设计 步骤1：创建“S_L_Fill”工程文件； 步骤2：创建类class：“EACH_ENTRY”。 在工作区“S_L_Fill classes”单击右键-→“new class”-→选择类型“Generic Class”名称为“EACH_ENTRY”，添加成员变量（添加至“class EACH_ENTRY { public:”之内）：int y_top; float x_int; int delta_y; float x_change_per_scan; 步骤3：包含头文件，同时初始化定义多边形顶点数目。在“class CS_L_FillView : public Cview……”之前添加代码“#include EACH_ENTRY.h”及“#define MAX_POINT 9”。 #define MAX_POINT 9 #include "EACH_ENTRY.h" 步骤4：在类“class CS_L_FillView”中添加成员变量（鼠标双击工作区“CS_L_FillView”，代码添加至“class CS_L_FillView : public Cview {protected: ……public:之后”）：EACH_ENTRY sides[MAX_POINT]; int x[MAX_POINT],y[MAX_POINT]; int side_count,first_s,last_s,scan,bottomscan,x_int_count; 步骤5：利用构造函数“CS_L_FillView::CS_L_FillView()”初始化顶点坐标（鼠标双击工作区“CS_L_FillView”，代码添加至“CS_L_FillView（）之内”）： x[0]=200;y[0]=100; x[1]=240;y[1]=160; x[2]=220;y[2]=340; x[3]=330;y[3]=100; x[4]=400;y[4]=180; x[5]=300;y[5]=400; x[6]=170;y[6]=380; x[7]=120;y[7]=440; x[8]=100;y[8]=220; 步骤6：在“class CS_L_FillView”下添加实现不同功能的成员函数。在工作区“CS_L_FillView”上单击鼠标右键，选择“Add Member Function”，分别完成以下成员函数的添加： （1）void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y) 函数说明：put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，y值较大者，排在活性边表的靠前位置。 void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)// entry为剔除水平边之后的第entry条边，x1, y1,为起点，x2, y2为终点，next_y为终点相邻的下一个顶点y坐标{ int maxy; float x2_temp,x_change_temp; x_change_temp=(float)(x2-x1)/(float)(y2-y1);//计算1/k x2_temp=float(x2); if((y2>y1)&&(y2 实验报告模板 《计算机图形学》实验报告 区域填充算法、裁剪算法 一、实验目的及要求 上机用所学的算法来填充多边形区域，在所给的区域里面剪裁所给出的线段。 二、理论基础 区域填充：区域填充所采用的算法是种子天填充算法。算法的主要思想是在所给定的区域类取一点作为种子，然后向种子坐标的上下左右，或者上下左右，左上，左下，右上，右下八个方向进行填充，从而达到填充整个区域的目地。但是由于在上述的算法中其他的新种子呀进行入栈，就会使得很多用过的种子从新入栈，使效率不高。所以重新设计了一下算法，采用取一点先横向填充，即(x0,y0)y0,不变x0++或者x0--,在所给定的范围之类填充完了之后再采用y+1，y-1.上下两个方向进行填充。 剪裁:选用了Cohe-SutherLand算法，剪裁算法的主体思想是先将整个区域分成9个区域。如图所示 1001 1000 1010 0001 0000 0010 0101 0100 0110 其中0000里面是所需要的剪裁的部分。在一条直线在这个区域里面。它的两个端点将会落在上面的区域中的任何一个区域中。1) 当线段完全在框里面，取这个两个端点；2) 当这条直线明显在区域外面，则抛弃；3) 如果不满足上面的2个条件，则把线段分成两段，其中一段在外面，则放弃，在里面则保留。通过上面的标记来判断端点是否在区域里面。 三、算法设计与分析 剪裁： void COpenglForMFCView::OnAreaCut() { // TODO: Add your command handler code here m_bClip = !m_bClip ; if( !m_bClip ) return ; // 直线端点集合数组一定为端点对偶数个点坐标和裁剪准备时数据一致 int nvLines[8][2] = {{0,0},{100,100},{10,201},{-200,-50},{-50,-140},{-50,140},{-80,10},{240,270}}; // 裁剪窗口边界坐标上下左右 扫描线Z-Buffer算法作业说明 学号20821055 姓名邹松 联系方式zousong@https://www.doczj.com/doc/b714144804.html, 1、SRC目录 src目录为算法源代码，编译环境为microsoft visual c++ 2005 express edition，源码中有主要步骤的注释说明。绘制时用到了OpenGL的glDrawPixels函数，需用到OpenGL库文件和头文件及glut库 2、BIN目录 bin目录为编译好的可执行程序，批处理运行程序，多个测试obj文件。 各个obj文件说明： cube.obj 为立方体模型，8个点，12个面，36条边。 cone.obj为圆台模型，146个点，288个多边形，864条边； sphere.obj为球模型，482个点，960个多边形，2880条边; teapot.obj为茶壶模型，530个点，992个多边形，2976条边; torus.obj为圆环模型，288个点，576个多边形，1728条边; torusknot.obj为环形结模型，1440个点，2880个多边形，8640条边; venusm.obj 为维纳斯像模型，19755个点，43357个多边形，130071个条边。 test.obj为我自己手工建立的obj文件，包含一个五角星和两个三角形，主要测试(凹)多边形(上面几个模型都只有三角形)，及多边形互相贯穿的情况。 可执行程序运行方式: SL_Z_buffer [file] 参数分别为obj文件名 默认分别为test.obj 直接运行run.bat文件即可对以上obj文件分别绘制出对应的图像。 使用的可执行程序为每个面片产生随机颜色 运行SL_Z_buffer可绘制test.obj 对应的图像 什么是计算机图形学? 计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科 计算几何：研究几何模型和数据处理的学 科，探讨几何形体的计算机表示、分析和 综合 计算机图形学研究内容:建模,绘制,动画 图形系统的基本功能 1.计算功能 元素生成、坐标变换、求交、剪裁计算。 2.存储功能 存储数据:形体的集合数据、形体间相互关系、数据的实时检索、保存图形的编辑等信息。 3.输入功能 输入信息: 数据、图形信息、图象信息等输入。 命令关键字、操作信息。 4.输出功能 输出信息: 图形信息、文件信息；静态图形、动态图形。 5.交互功能 人─机交互:拾取对象、输入参数；接受命令、数据等。 显示器种类 阴极射线管、随机扫描、存储管式、光栅扫描、等离子和液晶显 示器 从以下几个方面介绍图形显示设备： 图形硬件显示原理 CRT;CRT是利用电子枪发射电子束来产生图像，容易受电磁波干扰液晶显示器;液晶显示器的工作原理是利用液晶的物理特性，在通电时导通，使液晶排列变得有秩序，使光线容易通过；不通电时，排列则变得混乱，阻止光线通过 未来显示器 光栅显示系统的组成 图形显示方式:随机扫描存储管式扫描光栅扫描 图形显示质量与一帧的画线数量有关:当一帧线条太多，无法维持30～60帧/秒刷新频率，就会出现满屏闪烁 光栅扫描显示器的常用概念:行频、帧频（图像刷新率） 水平扫描频率为行频。垂直扫描频率为帧频。 隔行扫描、逐行扫描 隔行扫描方式是先扫偶数行扫描线，再扫奇数行扫描线。像素 屏幕被扫描线分成n 行，每行有m 个点，每个点为一个象素。整个屏幕有m ×n 个象素。具有灰度和颜色信息 分辨率 指CRT单位长度上能分辨出的最大光点(象素)数。分为水平分辨率和垂直分辨率。多边形区域填充算法
计算机图形学 区域填充算法的实现
扫描线填充算法讲解
区域填充算法的实现
《计算机图形学》有序边表填充算法
扫描线填充算法
计算机图形学必考知识点
计算机图形学 多边形裁剪与填充 计算机图形学课程设计
扫描线填充算法讲解
多边形的有效边表填充算法-
计算机图形学-区域填充的扫描线算法
实验六 扫描线填充算法
《计算机图形学》实验报告——区域填充和剪裁
扫描线Z-Buffer算法作业说明-Read
什么是计算机图形学
相关主题
文本预览