计算机图形学实验二交互式绘制多边形

一、实验目的

1. 掌握双缓冲绘图技术。

（2）掌握人机交互技术。

（3）掌握填充动态多边形的有效边表算法。

二、实验步骤

（1）在VS2017环境下创建MFC应用程序工程（单文档）

（2）添加命令消息处理函数、双缓冲技术函数

（3）定义边节点类、桶节点类、填充多边形类

（3）添加成员函数及成员变量

（4）编写函数内容

（4）绘制与填充多边形

三、实验结果

 

 

四、实验体会

通过本次实验，我掌握了双缓冲绘图技术、人机交互技术、填充动态多边形的有效边表算法，加深了对算法的理解。通过亲自动手将理论运用于实践，加强了动手能力，对MFC应用程序工程的编写更为熟悉了，对于实际的操作有了质的飞跃，整体对计算机图形学的理解有了不少提高。

附录：源代码

类视图

class CBucket  //桶节点类
{
public:
	CBucket();
	virtual ~CBucket();
public:
	int     ScanLine;//扫描线
	CAET    *pET;    //边表
	CBucket *next;
};

class CAET   //边节点类  
{ 
public: 
  CAET(); 
 virtual ~CAET(); 
public: 
  double        x;     //当前扫描线与有效边的交点的 x 坐标
   int           yMax; //边的最大 y 值
  double        k;        //斜率的倒数(x 的增量) 
  CAET            *next; 
}; 
填充多边形类
CFill::CFill()
{
	PNum=0;
	P=NULL;
	pEdge=NULL;
	pHeadB=NULL;
	pHeadE=NULL;
}

CFill::~CFill()
{
	if(P!=NULL)
	{
		delete[] P;
		P=NULL;
	}
	ClearMemory();
}

void CFill::SetPoint(CPoint p[],int m)//动态创建多边形顶点数组
{
	P=new CPoint[m];
    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;//pHeadB 为 CBucket 的头结点
			pCurrentB = pHeadB;//CurrentB 为 CBucket 当前结点
			pCurrentB->ScanLine = yMin;
			pCurrentB->pET = NULL;//没有链接边表
			pCurrentB->next = NULL;
		}
		else//建立桶的其它结点
		{
			pCurrentB->next = new CBucket;
			pCurrentB = pCurrentB->next;
			pCurrentB->ScanLine = y;
				pCurrentB->pET = NULL;
			pCurrentB->next = NULL;
		}
	}
}


void CFill::CreateEdge()//创建边表
{
	for (int i = 0; i < PNum; i++)
	{
		pCurrentB = pHeadB;
		int j = (i + 1) % PNum;//边的第二个顶点，P[i]和 P[j]构成边
		if (P[i].y < P[j].y)//边的起点比终点低
		{
			pEdge = new CAET;
			pEdge->x = P[i].x;//计算 ET 表的值
			pEdge->yMax = P[j].y;
			pEdge->k = (double)(P[j].x-P[i].x) / ((double)(P[j].y-P[i].y));//代表 1/k 
			pEdge->next = NULL;
			while (pCurrentB->ScanLine != P[i].y)//在桶内寻找该边的 yMin 
			{
				pCurrentB = pCurrentB->next;//移到 yMin 所在的桶结点
			}
		}
		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->next = NULL;
			while (pCurrentB->ScanLine != P[j].y)
			{
				pCurrentB = pCurrentB->next;
			}
		}
		if ((P[j].y) != P[i].y)
		{
			pCurrentE = pCurrentB->pET;
			if (pCurrentE == NULL)
			{
				pCurrentE = pEdge;
				pCurrentB->pET = pCurrentE;
			}
			else
			{
				while (NULL != pCurrentE->next)
				{
					pCurrentE = pCurrentE->next;
				}
				pCurrentE->next = pEdge;
			}
		}
	}
}

void CFill::AddEt(CAET *pNewEdge)//合并ET表
{
	CAET *pCE=pHeadE;
	if(pCE==NULL)
	{
		pHeadE=pNewEdge;
		pCE=pHeadE;
	}
	else
	{
		while(pCE->next!=NULL)
		{
			pCE=pCE->next;
		}
		pCE->next=pNewEdge;
	}
}

void CFill::EtOrder()//边表的冒泡排序算法
{
	CAET *pT1 = NULL, *pT2 = NULL;
	int Count = 1;
	pT1 = pHeadE;
	if (NULL == pT1)
	{
		return;
	}
	if (NULL == pT1->next)
	{
		return;
	}
	while (NULL != pT1->next)
	{
		Count++;
		pT1 = pT1->next;
	}
	for (int i = 1; i < Count; i++)
	{
		pT1 = pHeadE;
		if (pT1->x > pT1->next->x)
		{
			pT2 = pT1->next;
			pT1->next = pT1->next->next;
			pT2->next = pT1;
			pHeadE = pT2;
		}
		else
		{
			if (pT1->x == pT1->next->x)
			{
				if (pT1->k > pT1->next->k)
				{
					pT2 = pT1->next;
					pT1->next = pT1->next->next;
					pT2->next = pT1;
					pHeadE = pT2;
				}
			}
		}
		pT1 = pHeadE;
		while (pT1->next->next != NULL)
		{
			pT2 = pT1;
			pT1 = pT1->next;
			if (pT1->x > pT1->next->x)
			{
				pT2->next = pT1->next;
				pT1->next = pT1->next->next;
				pT2->next->next = pT1;
				pT1 = pT2->next;
			}
			else
			{
				if (pT1->x == pT1->next->x)
				{
					if (pT1->k > pT1->next->k)
					{
						pT2->next = pT1->next;
						pT1->next = pT1->next->next;
						pT2->next->next = pT1;
						pT1 = pT2->next;
					}
				}
			}
		}
	}
}

void CFill::FillPolygon(CDC *pDC)//填充多边形
{
	CAET *pT1 = NULL, *pT2 = NULL;
	pHeadE = NULL;
	for (pCurrentB = pHeadB; pCurrentB != NULL; pCurrentB = pCurrentB->next)
	{
		for (pCurrentE = pCurrentB->pET; pCurrentE != NULL; pCurrentE = pCurrentE->next)
		{
			pEdge = new CAET;
			pEdge->x = pCurrentE->x;
			pEdge->yMax = pCurrentE->yMax;
			pEdge->k = pCurrentE->k;
			pEdge->next = NULL;
			AddEt(pEdge);
		}
		EtOrder();
		pT1 = pHeadE;
		if (pT1 == NULL)
		{
			return;
		}
		while (pCurrentB->ScanLine >= pT1->yMax)//下闭上开
		{
			CAET * pAETTEmp = pT1;
			pT1 = pT1->next;
			delete pAETTEmp;
			pHeadE = pT1;
			if (pHeadE == NULL)
				return;
		}
		if (pT1->next != NULL)
		{
			pT2 = pT1;
			pT1 = pT2->next;
		}
		while (pT1 != NULL)
		
		{
		  if (pCurrentB->ScanLine >= pT1->yMax)//下闭上开
		  {
			CAET* pAETTemp = pT1;
			pT2->next = pT1->next;
			pT1 = pT2->next;
			delete pAETTemp;
		  }
		  else
		  {
			pT2 = pT1;
			pT1 = pT2->next;
		  }
		}
		BOOL In = FALSE;//设置一个 BOOL 变量 In，初始值为假
		int xb, xe;//扫描线的起点和终点
		for (pT1 = pHeadE; pT1 != NULL; pT1 = pT1->next)//填充扫描线和多边形相交的区间
		{
			if (FALSE == In)
			{
				xb = (int)pT1->x;
				In = TRUE;//每访问一个结点,把 In 值取反一次
			}
			else//如果 In 值为真，则填充从当前结点的 x 值开始到下一结点的 x 值结束的区间
			{
				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->next)//边连贯性
		{
			pT1->x = pT1->x + pT1->k;//x=x+1/k           
		}
	}
	
}

void CFill::ClearMemory()//安全删除所有桶和桶上面的边
{
	DeleteAETChain(pHeadE);
	CBucket *pBucket=pHeadB;
	while (pBucket != NULL)// 针对每一个桶
	{
		CBucket * pBucketTemp=pBucket->next;
		DeleteAETChain(pBucket->pET);
		delete pBucket;
		pBucket=pBucketTemp;
	}
	pHeadB=NULL;
	pHeadE=NULL;
}
直线函数
void CLine::LineTo(CDC *pDC,CPoint p1)
{
	P1=p1;
	CPoint p,t;
	COLORREF clr=RGB(0,0,0);//像素点颜色
	if(abs(P0.x-P1.x)<0)//绘制垂线
	{
		if(P0.y>P1.y)//交换顶点,使得起始点低于终点顶点
		{
			t=P0;P0=P1;P1=t;
		}
		for(p=P0;p.y<P1.y;p.y++)
		{
			pDC->SetPixel(p,clr);	
		}
	}
	else
	{
		double k,d;
		k=(double)(P1.y-P0.y)/(double)(P1.x-P0.x);
		if(k>1.0)//绘制k>1
		{
			if(P0.y>P1.y)
			{
				t=P0;P0=P1;P1=t;
			}
			d=1-0.5*k;
			for(p=P0;p.y<P1.y;p.y++)
			{
				pDC->SetPixel(p,clr);
                if(d>=0)
				{
					p.x++;
					d+=1-k;
				}
				else 
                    d+=1;       
			}
		}
		if(0.0<=k && k<=1.0)//绘制0<=k<=1
		{
			if(P0.x>P1.x)
			{
				t=P0;P0=P1;P1=t;
			}
			d=0.5-k; 
			for(p=P0;p.x<P1.x;p.x++)
			{
				pDC->SetPixel(p,clr);
                if(d<0)
				{
					p.y++;
					d+=1-k;
				}
				else 
					d-=k;		
			}
		}		
		if(k>=-1.0 && k<0.0)//绘制-1<=k<0
		{
			if(P0.x>P1.x)
			{
				t=P0;P0=P1;P1=t;
			}
			d=-0.5-k;
            for(p=P0;p.x<P1.x;p.x++)
			{
				pDC->SetPixel(p,clr);
                if(d>0)
				{
					p.y--;
					d-=1+k;
				}
				else 
					d-=k;		
			}
		}
		if(k<-1.0)//绘制k<-1 
		{
			if(P0.y<P1.y)
			{
				t=P0;P0=P1;P1=t;
			}
			d=-1-0.5*k;
			for(p=P0;p.y>P1.y;p.y--)
			{
				pDC->SetPixel(p,clr);
                if(d<0)
				{
					p.x++;
					d-=1+k;
				}
				else 
					d-=1;           
			}
		}
	}
	P0=p1;
}
消息处理函数
void CTestView::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if(m_Arrow)
		::SetCursor(AfxGetApp()->LoadStandardCursor(IDC_ARROW));
	else
		::SetCursor(AfxGetApp()->LoadStandardCursor(IDC_CROSS));
	CString strx,stry;//状态栏显示鼠标位置
	CMainFrame *pFrame=(CMainFrame*)AfxGetApp()->m_pMainWnd;//要求包含MainFrm.h头文件
	CStatusBar *pStatus=&pFrame->m_wndStatusBar;//需要将m_wndStatusBar属性修改为公有
	if(pStatus)
	{
		strx.Format("x=%d",point.x);
		stry.Format("y=%d",point.y);
		CDC *pDC=GetDC();
		CSize sizex=pDC->GetTextExtent(strx);
		CSize sizey=pDC->GetTextExtent(stry);
		pStatus->SetPaneInfo(1,ID_INDICATOR_X,SBPS_NORMAL,sizex.cx);//改变状态栏风格
		pStatus->SetPaneText(1,strx);
		pStatus->SetPaneInfo(2,ID_INDICATOR_Y,SBPS_NORMAL,sizey.cx);//改变状态栏风格
		pStatus->SetPaneText(2,stry);
		ReleaseDC(pDC);
	}
	int index=m_ptrarray.GetSize()-1;
	if(m_LBDown)
	{
		if(!m_IsInsert)//如果是第一次移动，则插入新的顶点
		{
			CPointArray *pPointArray=new CPointArray(point);
			m_ptrarray.Add(pPointArray);
			m_IsInsert=TRUE;
		}
		else//修改上次插入的顶点数据
		{  			
			((CPointArray *)m_ptrarray.GetAt(index))->pt=point;			
		}		
	}
	if(m_LBDown)
	{
		if(MK_SHIFT==nFlags)//约束:测试按下了Shift键
		{
			CPoint* pt1=&(((CPointArray *)m_ptrarray.GetAt(index))->pt);
			CPoint* pt2=&(((CPointArray *)m_ptrarray.GetAt(index-1))->pt);
			if(abs(pt1->x-pt2->x)>=abs(pt1->y-pt2->y))
			{
				pt1->y=pt2->y;//x方向的垂线
			}
			else
			{
				pt1->x=pt2->x;//y方向的垂线
			}
		}
	}
	if(index>3)
	{
		CPoint pt=((CPointArray*)m_ptrarray.GetAt(0))->pt;
		if((abs(point.x-pt.x)<=5) && (abs(point.y-pt.y)<=5))//引力域:边长为10的正方形
		{
			((CPointArray *)m_ptrarray.GetAt(index))->pt=pt;//修改数据
			m_Arrow=TRUE;
			m_LBDown=FALSE;
			m_MState=TRUE;
			m_Flag=FALSE;
		}
	}
	Invalidate(FALSE);
	CView::OnMouseMove(nFlags, point);
}
双缓冲技术函数
void CTestView::DoubleBuffer()//双缓冲
{
	CRect rect;//定义客户区
	GetClientRect(&rect);//获得客户区的大小
	CDC* pDC=GetDC();
	CDC MemDC;//内存设备上下文
	CBitmap NewBitmap,*pOldBitmap;//内存中承载图像的临时位图
	MemDC.CreateCompatibleDC(pDC);//建立与屏幕pDC兼容的MemDC 
	NewBitmap.CreateCompatibleBitmap(pDC,rect.Width(),rect.Height());//创建兼容位图 
	pOldBitmap=MemDC.SelectObject(&NewBitmap); //将兼容位图选入MemDC 
	MemDC.FillSolidRect(rect,pDC->GetBkColor());//按原来背景填充客户区，否则是黑色 
	DrawObject(&MemDC);
	pDC->BitBlt(0,0,rect.Width(),rect.Height(),&MemDC,0,0,SRCCOPY);//将内存位图拷贝到屏幕
	MemDC.SelectObject(pOldBitmap);//恢复位图
	NewBitmap.DeleteObject();//删除位图
	MemDC.DeleteDC();//删除MemDC
	ReleaseDC(pDC);//释放DC
}
 绘制多边形
void CTestView::DrawObject(CDC *pDC)//绘制多边形
{
	int index=m_ptrarray.GetSize();
	CLine *line=new CLine;
	if(index)
	{		
		line->MoveTo(pDC,((CPointArray*)m_ptrarray.GetAt(0))->pt);
		for(int i=1;i<index;i++)
		{
			line->LineTo(pDC,((CPointArray*)m_ptrarray.GetAt(i))->pt);		
		}
		if(FALSE==m_Flag)//线段闭合，填充图形
		{
			FillPolygon(pDC);	
		}
	}
	delete line;
}
多边形填充

void CTestView::FillPolygon(CDC *pDC) 
{
	// TODO: Add your command handler code here
    int size=m_ptrarray.GetSize();
	CPoint *p=new CPoint[size];//分配内存空间
	for(int i=0;i<size;i++)//拷贝数据到一个静态数组
	{
		p[i]=((CPointArray *)m_ptrarray.GetAt(i))->pt;
	}
	CFill *fill=new CFill;//动态分配内存
	fill->SetPoint(p,size);//设置多边形顶点数组
	fill->CreateBucket();//建立桶表
	fill->CreateEdge();//建立边表
	fill->FillPolygon(pDC);//填充多边形
	delete fill;//释放内存
	delete []p;	
}