精华内容
下载资源
问答
  • 有效边表填充算法

    千次阅读 2018-06-18 16:31:47
    有效边表填充算法通过维护边表和有效边表,避开了扫描线与多边形所有边求交的复杂运算。填充原理是按照扫描线从小到大的移动顺序,计算当前扫描线与有效边的交点,然后把这些交点按x值递增的顺序进行排序、配对,以...

    填充原理

    有效边表填充算法通过维护边表和有效边表,避开了扫描线与多边形所有边求交的复杂运算。填充原理是按照扫描线从小到大的移动顺序,计算当前扫描线与有效边的交点,然后把这些交点按x值递增的顺序进行排序、配对,以确定填充区间,最后用指定颜色填充区间内的所有像素,即完成填充工作。有效边表填充算法已成为目前最为有效的多边形填充算法之一。

    边界像素处理原则

    填充左下角为(1,1),右上角为(3,3)的正方形时,若将边界上的所有像素全部填充,就得到图示的结果。
    这里写图片描述
    在多边形填充过程中,常采用“左闭右开”和“下闭上开”的原则对边界像素进行处理。

    这里写图片描述
    局部最高点P1、P6和P4,共享顶点的两条边落在扫描线的下方;普通连接点P2,共享顶点的两条边分别落在扫描线两侧;局部最低点P0、P3和P5,共享顶点的两条边落在扫描线的上方。常根据共享顶点的两条边的另一端的y值大于扫描线y值的个数来将交点个数取为0、1和2。事实上,有效边表算法能自动处理这三类顶点。

    有效边与有效边表

    有效边

    多边形与当前扫描线相交的边称为有效边(active edge)。在处理一条扫描线时仅对有效边进行求交运算,可以避免与多边形的所有边求交,提高了算法效率。有效边上的扫描线由起点到终点每次加1,即像素点的y坐标为y=y+1,x坐标的变化可以按如下方法推导。
    这里写图片描述

    有效边表

    这里写图片描述

    桶表与边表

    从有效边表的建立过程可以看出,有效边表给出了扫描线与有效边交点坐标的计算方法,但是并没有给出新边出现的位置坐标。为了确定在哪条扫描线上插入了新边,就需要构造一个边表(edge table,ET),用以存放扫描线上多边形各条边出现的信息。因为水平边的1/k为∞,并且水平边本身就是扫描线,在建立边表时可以不予考虑。

    桶表和边表的表示法

    桶表是按照扫描线顺序管理边出现情况的一个数据结构。首先,构造一个纵向扫描线链表,链表的长度为多边形所占有的最大扫描线数,链表的每个结点称为桶(bucket),对应多边形覆盖的每一条扫描线。
    将每条边的信息链入与该边最小y坐标(ymin)相对应的桶处。也就是说,若某边的较低端点为ymin,则该边就存放在相应的扫描线桶中。
    对于每一条扫描线,如果新增多条边,则按x|ymin坐标递增的顺序存放在一个链表中,若x|ymin 相等,则按照1/k由小到大排序,这样就形成边表。
    这里写图片描述

    桶表与边表示例

    这里写图片描述
    这里写图片描述

    展开全文
  • 实验二 有效边表填充算法 实验题目 有效边表填充算法 姓名 指导老师 学号 班级 完成日期 1.实验目的 设计有效边表结点和边表结点数据结构 设计有效边表填充算法 编程实现有效边表填充算法 2.实验描述 下图 1 所示...
  • 多边形有效边表填充算法。计算机图形学基础教程。vc6.0
  • 大学计算机图形学课程作业代码,完美实现多边形有效边表填充算法,自用,具体代码完整。打包下载,可直接运行。c/c++语言MFC实现。支持vs。
  • 有效边表填充算法的实现

    千次阅读 多人点赞 2018-03-08 17:43:46
    有效边表填充算法实现1. 在当前项目中创建有效边结点类AET和边表中桶结点类Bucket,注意AET中的k代表的是边斜率的倒数(1/K) 2. 在视图类中增加属性Point[7],是个点数组,用来存储待填充多边形的顶点,同时在...

    有效边表填充算法实现

    1. 在当前项目中创建有效边结点类AET和边表中桶结点类Bucket,注意AET中的k代表的是边斜率的倒数(1/K

         

    2. 在视图类中增加属性Point[7],是个点数组,用来存储待填充多边形的顶点,同时在视图类的构造函数中为Point[7]赋值

                                                         

     

     

    3. 在视图类的ondraw中,绘制待填充多边形

     

     

    4. 在视图类中增加两个属性HeadB和CurrentB,表示指向第一个桶结点指针、指向当前桶结点指针

     

    5. 在视图类中增加自定义函数CreatBucket(),建立桶结点


     

    6. 在视图类中增加如下图所示属性

     

     

    7. 在视图类中增加自定义函数Et(),把待填充七边形放入边表中,定义Number=7

     

     

    8. 在视图类中增加自定义函数AddEdge(AET *NewEdge);和自定义函数EdgeOrder()

     

     


     

     

     

    9. 在视图类中增加有效边表填充算法,名称为自定义函数PolygonFill()

     

     

     


     

     

     

     

    10. “填充”菜单响应函数中

     

     

    运行效果

    打开项目


     

    点击菜单项后

     

    按下调色板的确定键后,从上往下填充选定颜色

     






    注意:未经允许不可转载,经允许转载要标明出处!

    展开全文
  • 对一个用鼠标左击形成的多边形,画一个最小的矩形,在这个矩形内用有效边表填充算法对多边形填充。 建议 请用VS2008运行。
  • 有效边表填充算法 前言 算法的填充原理 边界像素处理原则 1.考虑像素面积大小的影响问题 2.考虑边界像素的影响问题 不同点的处理原则 1.普通连接点的处理原则 2.局部最低点的处理原则 3.局部最高点的处理原则 有效边...


    前言

    因为计算机图形学真的要挂科了,所以强行复习一下,潜水了这么久,这竟然就是第一篇博客了


    不会写,东西也不太懂

    算法的填充原理

    按照扫描线从小到大的移动顺序,计算当前扫描线与有效边的交点,然后把这些交点按x值递增的顺序进行排序、配对,以确定填充区间,最后用指定颜色填充区间内的所有像素,最终完成填充工作

    边界像素处理原则

    如图所示的例子(从书上找的)

    1.考虑像素面积大小的影响问题

    如果将边界上的所有像素填充,就得到了左边的结果,正方形所填像素覆盖的面积为3×3个单位,但事实上的正方形并没有这么大,只有2×2个单位。
    啊这

    2.考虑边界像素的影响问题

    对于相邻多边形的公共边,如果不做处理,可能把公共边上的像素先设置为一个多边形的颜色,然后又设置为了一个多边形的颜色,一条边界绘制两次会导致混乱的视觉效果

    所以,在多边形填充过程中,常采用“左闭右开”和“上闭下开”的原则对边界像素进行处理。(上课的时候听的一脸懵逼)

    不同点的处理原则

    在这里插入图片描述

    1.普通连接点的处理原则

    对于上图中p2点,他是p2p3边的终点,同时也是p2p1边的起点,属于普通连接点的顶点个数计数为1。按照“下闭上开”的原则,p2点作为终点不填充,但作为起点时被填充

    2.局部最低点的处理原则

    p0,p3,p5为局部最低点,如果处理不当,扫描线y=1会填充区间[3,8],结果填充了p3,p5之间的像素。将局部最低点的个数计数为2。y=1的扫描线填充时,共享顶点p3的两条边会被分别计入有效边表,所以会被填充两次,同理,p5也会被填充两次

    3.局部最高点的处理原则

    局部最高点的顶点个数计数为0,扫描线会自动填充p4点,根据“下闭上开”原则会自动放弃p1,p4和p6。p1与p6点将不再填充,p4点会被经过p2p3边和p5p6边的第5条扫描线填充。

    有效边与有效边表

    1.有效边

    多边形与当前扫描线相交的边即为有效边。有效边上的扫描线由起点到终点每次加1,即像素点的y坐标是y=y+1,x的坐标变化可以由如下方法推导。

    设有效边的斜率为k。假定有效边与当前扫描线的交点为(xi,yi)则有效边与下一条扫描线yi+1的交点为(xi+1,yi+1),其中xi+1=xi+△x/△y,如图所示
    在这里插入图片描述

    2.有效边表

    把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中,称为有效边表。
    在这里插入图片描述


    因为考试不考编程,桶表不想看了。。。
    展开全文
  • 图形学篇:多边形有效边表填充算法

    千次阅读 多人点赞 2019-04-19 21:11:09
    点阵表示法:使用大量的点进行描述,描述完成之后,得到的就是完整形态的多边形,内部已被填充,可直接针对点来进行上色 多边形的扫描转换就是从顶点表示法转换到点阵表示法的过程。 基础的填充多边形方式: 检查...

    什么是多边形?

    • 多边形是由折线段组成的封闭图形

    多边形的表示方法有哪些?

    • 顶点表示法:使用顶点进行描述,但此时多边形仅仅是一些封闭线段,内部是空的,且不能直接进行填充上色
    • 点阵表示法:使用大量的点进行描述,描述完成之后,得到的就是完整形态的多边形,内部已被填充,可直接针对点来进行上色

    多边形的扫描转换就是从顶点表示法转换到点阵表示法的过程。

    基础的填充多边形方式:

    • 检查光栅上的每一个像素是否位于多边形内

    光栅究竟是什么?

    • 由大量等宽等间距的平行狭缝构成的光学器件称为光栅,这是专业且准确的方法,然而明显不是给人看的(观众:???)
    • 光栅是连接帧缓冲和具体的电脑屏幕的桥梁(这是很老的大头显示器上的,现在的液晶显示器不存在光栅,它的成像依靠的是电场,液晶,滤光膜等,所以我们暂且把这里说的的光栅理解为像素

    光栅化究竟是什么?

    有效边表填充算法:

    • 基本原理:按照扫描线从小到大的移动顺序,计算当前扫描线与有效边的交点,然后把这些交点按x的值递增顺序进行排序,配对,以确定填充去间,最后用指定颜色填充区间内的所有像素,即完成填充工作
    • 优势:通过维护边表和有效边表,避开了扫描线与多边形所有边求交的复杂运算,性能提升巨大
    • 边界像素处理原则:对于边界像素,采用“左闭右开”和“下闭上开”的原则
    • 有效边:多边形与当前扫描线相交的边
    • 有效边表:把有效边按照与扫描线交点x坐标递增的顺序存放在一个链表中,称为有效边表
    • 桶表:按照扫描线顺序管理边的数据结构

    算法实现:

    将VC 6.0 调整到ClassView视图

    创建有效边表和桶表类

    将VC 6.0调整到FileView视图,对两个类进行定义

    AET.h

    class CAET  
    {
    public:
    	CAET();
    	virtual ~CAET();
    public:
    	double  x;//当前扫描线与有效边交点的x坐标
    	int     yMax;//边的最大y值
    	double  k;//斜率的倒数(x的增量)
    	CAET   *pNext;
    };
    

    Bucket.h

    #include "AET.h"
    #include "Bucket.h"
    
    class CBucket  
    {
    public:
    	CBucket();
    	virtual ~CBucket();
    public:
    	int     ScanLine;     //扫描线
    	CAET    *pET;         //桶上的边表指针
    	CBucket *pNext;
    };

    回到ClassView视图,像之前那样创建CFill类,再回到FileView视图,对CFill类进行定义

    Fill.h

    #include "AET.h"
    #include "Bucket.h"
    
    class CFill  
    {
    public:
    	CFill();
    	virtual ~CFill();
    	void SetPoint(CPoint *p,int);//初始化顶点和顶点数目
    	void CreateBucket();//创建桶
    	void CreateEdge();//边表
    	void AddET(CAET *);//合并ET表
    	void ETOrder();//ET表排序
    	void Gouraud(CDC *);//填充多边形
     	void ClearMemory();//清理内存
    	void DeleteAETChain(CAET* pAET);//删除边表
    protected:
    	int     PNum;//顶点个数
    	CPoint    *P;//顶点坐标动态数组
    	CAET    *pHeadE,*pCurrentE,*pEdge; //有效边表结点指针
    	CBucket *pHeadB,*pCurrentB;        //桶表结点指针
    };

    Fill.cpp

    // Fill.cpp: implementation of the CFill class.
    //
    //
    
    #include "stdafx.h"
    #include "Study3.h"
    #include "Fill.h"
    #include "AET.h"
    #include "Bucket.h"
    
    #ifdef _DEBUG
    #undef THIS_FILE
    static char THIS_FILE[]=__FILE__;
    #define new DEBUG_NEW
    #endif
    
    //
    // Construction/Destruction
    //
    CFill::CFill()
    {
    	PNum=0;
    	P=NULL;
    	pEdge=NULL;
    	pHeadB=NULL;
    	pHeadE=NULL;
    	pCurrentB = NULL;
    	pCurrentE = NULL;
    }
    
    CFill::~CFill()
    {
    	if(P!=NULL)
    	{
    		delete[] P;
    		P=NULL;
    	}
    	ClearMemory();
    }
    
    void CFill::SetPoint(CPoint *p,int m)初始化顶点和顶点数目
    {
    	P=new CPoint[m];//创建一维动态数组,转储CTestView类中P数组中的顶点
    	for(int i=0;i<m;i++)
    	{
    		P[i]=p[i];	
    	}
    	PNum=m;//记录顶点数量
    }
    
    void CFill::CreateBucket()//创建桶表
    {
    	int yMin,yMax;
    	yMin = yMax = P[0].y;
    	for(int i = 0;i<PNum;i++)
    	{
    		if(P[i].y<yMin)
    		{
    			yMin = P[i].y;
    
    		}
    		if(P[i].y>yMax)
    		{
    			yMax = P[i].y;
    		}
    	}
    
    	for(int y = yMin;y<=yMax;y++)
    	{
    		if(yMin == y)
    		{
    			pHeadB = new CBucket;
    			pCurrentB = pHeadB;
    			pCurrentB->ScanLine = yMin;
    			pCurrentB->pET = NULL;
    			pCurrentB->pNext = NULL;
    		}
    		else
    		{
    			pCurrentB->pNext = new CBucket;
    			pCurrentB=pCurrentB->pNext;
    			pCurrentB->ScanLine = y;
    			pCurrentB->pET=NULL;
    			pCurrentB->pNext=NULL;
    		}
    	}
    }
    
    void CFill::CreateEdge()//创建边表,即将各边链入到相应的桶节点
    {
    	for(int i = 0;i<PNum;i++)
    	{
    		pCurrentB=pHeadB;
    		int j = (i+1)%PNum;
    		if(P[i].y<P[j].y)
    		{
    			pEdge = new CAET;
    			pEdge->x=P[i].x;
    			pEdge->yMax=P[j].y;
    			pEdge->k = (double)(P[j].x-P[i].x)/((double)(P[j].y-P[i].y));
    
    			pEdge->pNext = NULL;
    			while(pCurrentB->ScanLine!=P[i].y)
    			{
    				pCurrentB=pCurrentB->pNext;
    			}
    		}
    
    		if(P[j].y<P[i].y)
    		{
    			pEdge=new CAET;
    			pEdge->x=P[j].x;
    			pEdge->yMax=P[i].y;
    			pEdge->k = (double)(P[i].x-P[j].x)/((double)(P[i].y-P[j].y));
    			pEdge->pNext = NULL;
    			while(pCurrentB->ScanLine!=P[j].y)
    			{
    				pCurrentB=pCurrentB->pNext;
    			}
    		}
    
    		if(P[j].y!=P[i].y)
    		{
    			pCurrentE=pCurrentB->pET;
    			if(pCurrentE==NULL)
    			{
    				pCurrentE=pEdge;
    				pCurrentB->pET=pCurrentE;
    			}
    			else
    			{
    				while(NULL!=pCurrentE->pNext)
    				{
    					pCurrentE=pCurrentE->pNext;
    				}
    				pCurrentE->pNext=pEdge;
    			}
    		}
    	}
    }
    void CFill::AddET(CAET *pNewEdge)//合并ET表
    {
    	CAET *pCE=pHeadE;//边表头结点
    	if(pCE==NULL)//若边表为空,则pNewEdge作为边表头结点
    	{
    		pHeadE=pNewEdge;
    		pCE=pHeadE;
    	}
    	else//将pNewEdge链接到边表末尾(未排序)
    	{
    		while(pCE->pNext!=NULL)
    		{
    			pCE=pCE->pNext;
    		}
    		pCE->pNext=pNewEdge;
    	}
    }
    
    void CFill::ETOrder()//边表的冒泡排序算法
    {
    	CAET *pT1,*pT2;
    	int Count=1;
    	pT1=pHeadE;
    	if(pT1==NULL)//没有边,不需要排序
    	{
    		return;
    	}
    	if(pT1->pNext==NULL)//如果该ET表没有再连ET表
    	{
    		return;//只有一条边,不需要排序
    	}
    	while(pT1->pNext!=NULL)//统计边结点的个数
    	{
    		Count++;
    		pT1=pT1->pNext;
    	}
    	for(int i=0;i<Count-1;i++)//冒泡排序
    	{
    		CAET **pPre=&pHeadE;//pPre记录当面两个节点的前面一个节点,第一次为头节点
    		pT1=pHeadE;
    		for (int j=0;j<Count-1-i;j++)
    		{
    			pT2=pT1->pNext;
    			
    			if ((pT1->x>pT2->x)||((pT1->x==pT2->x)&&(pT1->k>pT2->k)))//满足条件,则交换当前两个边结点的位置
    			{
    				pT1->pNext=pT2->pNext;
    				pT2->pNext=pT1;
    				*pPre=pT2;
    				pPre=&(pT2->pNext);//调整位置为下次遍历准备
    			}
    			else//不交换当前两个边结点的位置,更新pPre和pT1
    			{
    				pPre=&(pT1->pNext);
    				pT1=pT1->pNext;
    			}
    		}
    	}
    }
    
    void CFill::Gouraud(CDC *pDC)//填充多边形
    {
    	CAET *pT1=NULL,*pT2=NULL;
    	pHeadE=NULL;
    	for(pCurrentB=pHeadB;pCurrentB!=NULL;pCurrentB=pCurrentB->pNext)
    	{
    		for(pCurrentE=pCurrentB->pET;pCurrentE!=NULL;pCurrentE=pCurrentE->pNext)
    		{
    			pEdge=new CAET;
    			pEdge->x=pCurrentE->x;
    			pEdge->yMax=pCurrentE->yMax;
    			pEdge->k=pCurrentE->k;
    			pEdge->pNext=NULL;
    			AddET(pEdge);
    		}
    
    		ETOrder();
    		pT1=pHeadE;
    		if(pT1==NULL)
    		{
    			return ;
    		}
    		while(pCurrentB->ScanLine>=pT1->yMax)
    		{
    			CAET *pAETTEmp = pT1;
    			pT1=pT1->pNext;
    			delete pAETTEmp;
    			pHeadE=pT1;
    			if(pHeadE==NULL)
    			{
    				return;
    			}
    
    		}
    		if(pT1->pNext!=NULL)
    		{
    			pT2=pT1;
    			pT1=pT2->pNext;
    		}
    
    		while(pT1!=NULL)
    		{
    			if(pCurrentB->ScanLine>=pT1->yMax)
    			{
    				CAET *pAETTemp=pT1;
    				pT2->pNext=pT1->pNext;
    				pT1=pT2->pNext;
    				delete pAETTemp;
    			}
    			else
    			{
    				pT2=pT1;
    				pT1=pT2->pNext;
    			}
    		}
    		BOOL In = FALSE;
    		int xb,xe;
    		for(pT1=pHeadE;pT1!=NULL;pT1=pT1->pNext)
    		{
    			if(FALSE==In)
    			{
    				xb = (int)pT1->x;
    				In=TRUE;
    			}
    			else
    			{
    				xe = (int)pT1->x;
    				for(int x = xb;x<xe;x++)
    				{
    					pDC->SetPixel(x,pCurrentB->ScanLine,RGB(0,0,255));
    				}
    				In = FALSE;
    
    			}
    		}
    		for(pT1=pHeadE;pT1!=NULL;pT1=pT1->pNext)
    		{
    			pT1->x=pT1->x+pT1->k;
    		}
    	}
    }
    
    
    void CFill::ClearMemory()//安全删除所有桶与桶上连接的边
    {
    	DeleteAETChain(pHeadE);//删除边表
    	CBucket *pBucket=pHeadB;
    	while (pBucket!=NULL)//针对每一个桶
    	{
    		CBucket *pBucketTemp=pBucket->pNext;
    		DeleteAETChain(pBucket->pET);//删除桶上面的边
    		delete pBucket;
    		pBucket=pBucketTemp;
    	}
    	pHeadB=NULL;
    	pHeadE=NULL;
    }
    
    void CFill::DeleteAETChain(CAET *pAET)//删除边表
    {
    	while (pAET!=NULL)
    	{
    		CAET *pAETTemp=pAET->pNext;
    		delete pAET;
    		pAET=pAETTemp;
    	}
    }

    一切准备就绪,进入CXXXView.cpp(“XXX”为你项目名称)

    给OnDraw函数添加以下语句

    	CRect rect;
    	GetClientRect(&rect);
    	pDC->SetMapMode(MM_ANISOTROPIC);
    	pDC->SetWindowExt(rect.Width(),rect.Height());
    	pDC->SetViewportExt(rect.Width(),-rect.Height());
    	pDC->SetViewportOrg(rect.Width()/2,rect.Height()/2);
    	rect.OffsetRect(-rect.Width()/2,-rect.Height()/2);
    
    	//声明Fill类
    	CFill *cFill = new CFill;
    
    	//声明多边形的七个顶点
    	CPoint points[7] = {CPoint(50,70),CPoint(-150,270),CPoint(-250,20),CPoint(-150,-280),CPoint(0,-80),CPoint(100,-280),CPoint(300,120)};
    
    	//设置顶点
    	cFill->SetPoint(points,7);
    
    	//创建桶表
    	cFill->CreateBucket();
    
    	//创建边表
    	cFill->CreateEdge();
    
    	//填充多边形
    	cFill->Gouraud(pDC);

    运行结果

    大家对于填充算法要多看看,很重要

    展开全文
  • 与孔令德的教材是配套的 大家参考一下 谢谢
  • 正方形四等分,使用红,绿,黄,蓝4种颜色填充,使用的是有效边表算法,下载请慎重。
  • 为提高区域填充效率,对三种常见的区域填充算法进行了介绍和分析,并对其中优势较为明显的活性边表区域填充算法进行了进一步改进。改进算法针对原始算法的不足,充分利用多边形顶点信息,建立了活性边动态发现机制,...
  • 改进的有效边表算法(y-x算法)。可实现opengl环境下的多点间空白填充
  • 1.有效边表填充算法 1.1.有效边表填充算法分为如下几个步骤: 1.1.1.将多边形所有的边分别与扫描线1计算交点,得到交点集,与扫描线计算的边没有顺序要求。 1.1.2.将点集按标x的大小递增排序,得到有序点集。 1.1.3....
  • 一 DDA算法 (一) 原理:DDA算法跟在坐标系中画直线类似函数y=0.5*x+1x123456y1.522.5 33.54在坐标系中描绘这六个点,用线连接起来,就是函数的直线 DDA算法简单来说寻找合适的进度(例如,x方向,从起点x=1到x...
  • 用VS2013,OPENGL环境实现多边形的扫描转换和区域填充,附上OPENGL配置文件。多边形的扫描转换:有效边表算法,多边形的区域填充:边界填充算法
  • 有效边表填充算法通过填充凸、凹多边形和环,已成为目前最为有效的多边形填充算法。 Southerland-Hodgman 多边形裁减算法的基本思想就是逐边进行裁减;首先将多边形对于巨型窗口的裁剪分解为对窗口四边形所在直线的...
  • 计算机图形学实践教程实例源程序,包含直线中点Bresenham算法,圆中点Bresenham算法,椭圆中点Bresenham算法,直线反走样Wu算法,多边形有效边表填充算法,多边形边缘填充算法等案例。
  • 计算机图形学基础教程案例源码,例如:中点Bresenham算法、多边形有效边表填充算法、梁友栋-Barsky直线裁剪算法、Bezier曲线算法等40多个案例源码。
  • 图形学综合大作业

    2014-07-04 14:48:49
    将一学期重要算法和知识用自己写的案例来实现了一下,里面的所有类都是自己重新设计编写,包括了Bresenham Wu反走样算法,分形几何,二维动画,三维建模,有效边表填充算法,Bezier线条反走样。计算机 图形学 大作业...

空空如也

空空如也

1 2 3
收藏数 44
精华内容 17
关键字:

有效边表填充算法