二维图形视见与裁剪

浅浅的花香味﹌ 2022-08-18 14:15 165阅读 0赞

**二维图形视见与裁剪**

# 一．目的： #

1．理解、巩固线段裁剪的含义。

2．掌握Cohen-Sutherland线段裁剪方法。

# 二．要求： #

1．在屏幕上绘制出较简单的几何图形。

2. 用Cohen-Sutherland算法实现线段裁剪，并将裁剪结果在显示窗口显示出来。

3. 用Sutherland-Hodgema算法（多边形裁减算法原理）实现多边形裁剪，并将裁剪结果在显示窗口显示出来。

# 三．原理和关键算法： #

1. Cohen-SutherLand算法（编码算法）

直线算法原理：

对于每条线段P1P2分为三种情况处理:

（1）若P1P2完全在窗口内，则显示该线段P1P2。

（2）若P1P2明显在窗口外，则丢弃该线段。

（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

为快速判断，采用如下编码方法：由窗口四条边所在直线把二维平面分成9个区域(右图)，每个区域赋予一个四位编码：CtCbCrCl（上下右左）；直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。

各位编码含义：

![Center][]

上：if y>ymax，Ct=1，else, 0;

下：if y<ymax，Cb=1，else, 0；

右：if x>xmax，Cr=1，else, 0;

左：if x<xmax，Cl=1，else, 0;

对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右；

‐如果两端点的编码均为0000，表示直线在窗口内。

‐如果两端点的编码相与不为0000，表示直线在窗口外。

‐如果两端点的编码不全为0000，但相与为0000，则该直线部分可见，需计算直线与窗口的交点，确定哪一部分可见。

2.Sutherland-Hodgema算法（多边形裁减算法原理）：

通过对单一边或面的裁剪来实现多边形的裁剪分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。一次用窗口的一条边裁剪多边形。流水线过程(左上右下)：前边的结果是后边的输入。 亦称逐边裁剪算法。

算法的每一次输出（包括中间结果）都是一个多边形的顶点表，且所有顶点均位于相应窗口裁剪边或面的可见一侧。由于多边形的每一条边需要与裁剪边或面分别进行比较，因此只需要讨论单条边和单个裁剪边或面之间可能的位置关系。假设S，P为多边形的两个相邻顶点，且S为该边的起点，P为该边的终点，则变SP与裁剪边或面之间只有4种可能的关系 。

把平面分成两个部分：一部分包含窗口，成为可见一侧；另一部分称为不可见一侧。依序考虑多边形各边的两端点S,P。它们与裁剪线的位置关系只有4中情况。

![Center 1][]

（1）S,P 均在可见一侧，计为P点 （2）S,P均不在可见一侧

![Center 2][]

（3）S可见，P不可见 (4) S不可见，P可见

由上可见，每一次将多边形的边与裁剪边或面比较后，输出一个或两个顶点，也可能无输出点。如果SP边完全可见，则输出P点，不必输出起点S，因为顶点是按顺序处理的，S是作为前一边的终点输出的。如果SP边完全不可见，则无输出。如果SP边部分可见，则SP边可能进入或离开裁剪边或面的可见一侧。 如果SP边离开裁剪边或面的可见一侧，则输出SP与裁剪边或面交点。如果SP边进入裁剪边或面的可见一侧，则输出两点，一个为SP与裁剪边或面的交点，一个是P点。

对于多边形的第一个顶点，只需判断其可见性。如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。

对于最后一条边PnP1，其处理方法是：标志第一顶点为F，这样最后一条边则为PnF，可与其他边作相同的处理。

实现方法：

设置二个表：

输入顶点表：用于存放被裁剪多边形的顶点p1-pm。 

输出顶点表：用于存放裁剪过程中及结果的顶点q1-qn。

输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。

相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。

3.Cohen-Sutherland直线剪裁核心算法：

算法描述：

1）. while 对于每一个窗口边或面  do begin
    2）. if P1在窗口边的可见一侧 then 输出P1
    3）. for i=1 到 n do begin
    4）.        if Pi在窗口边的可见一侧   then
    5）.           if Pi+1在窗口边的可见一侧 then 输出Pi+1
    6）.           else 计算交点并输出交点
    7）.        else if Pi+1在窗口边的可见一侧，then 计算交点并输出交点，同时输出Pi+1 end end
    8）. end of algorithm<span style="font-family: 宋体; background-color: rgb(255, 255, 255);"> </span>

四．关键代码：

1.对区域进行编码：

int CCg_WuPing2DtransView::pCode(int *x, int *y)
    {
    	int code = 0;
    
    	CCg_WuPing2DtransDoc* pDoc = GetDocument();
    	
    	if(*x < pDoc ->m_wndRectangle[0])
    		code = code | LEFT;
    	else if(*x > pDoc ->m_wndRectangle[1])
    			code = code | RIGHT;
            if(*y < pDoc ->m_wndRectangle[3])
    		    code = code | BOTTOM; 
    	else if(*y > pDoc ->m_wndRectangle[2])
    		    code = code | TOP;
    	return code;
    }

2.Cohen-Sutherland直线裁剪：

int CCg_WuPing2DtransView::ClipLine(int *x1, int *y1, int *x2, int *y2)
    {
    	int tempx, tempy;
            CCg_WuPing2DtransDoc* pDoc = GetDocument();
            int pcode1, pcode2, pcode;
            pcode1 = pCode(x1, y1);
    	pcode2 = pCode(x2, y2);
            if(pcode1 == 0  && pcode2 == 0)
    	{
    		return 1;
    	}
            while(pcode1 != 0 || pcode2 != 0)
    	{
    		if((pcode1 & pcode2) != 0)
    		{
    			return 0;
    		}
                    pcode = pcode1;
    		if(pcode1 == 0)
    			pcode = pcode2;
    		if((LEFT & pcode) != 0)
    		{
    			tempx = pDoc ->m_wndRectangle[0];
    			tempy = *y1 + (*y2 - *y1) * (pDoc ->m_wndRectangle[0] - *x1) / (*x2 - *x1);
    		}
    		else if((RIGHT & pcode) != 0)
    		{
    			tempx = pDoc ->m_wndRectangle[1];
    			tempy = *y1 + (*y2 - *y1) * (pDoc ->m_wndRectangle[1] - *x1) / (*x2 - *x1);
    		}
    		else if((TOP & pcode) != 0)
    		{
    			tempy = pDoc ->m_wndRectangle[2];
    			tempx = *x1 + (*x2 - *x1) * (pDoc ->m_wndRectangle[2] - *y1) / (*y2 - *y1) ;
    		}
    
    		else if((BOTTOM & pcode) != 0)
    		{
    			tempy = pDoc ->m_wndRectangle[3];
    			tempx = *x1 + (*x2 - *x1) * (pDoc ->m_wndRectangle[3] - *y1) / (*y2 - *y1) ;
    		｝
    		if(pcode == pcode1)
    		{
    			*x1 = tempx;
    			*y1 = tempy;
    			pcode1 = pCode(x1, y1);
    		}
    	    else if(pcode == pcode2) 
    		{
    			*x2 = tempx;
    			*y2 = tempy;
    		    pcode2 = pCode(x2, y2);
    		}
    	}
    	return 1;
    }

3.判断多边形的每条边是否可见：（以下几个函数都用于实现多边形裁剪）

int CCg_WuPing2DtransView::pVisible(int x, int y, int i)
    {
    	int visible = 0;
    
    	CCg_WuPing2DtransDoc* pDoc = GetDocument();
    
            switch(i)
    	{
    	case 0:
    		if(x >= pDoc ->m_wndRectangle[0])
    			visible = 1;
    		break;
    	case 1:
    		if(x <= pDoc ->m_wndRectangle[1])
    			visible =1;
    		break;
    	case 2:
    		if(y <= pDoc ->m_wndRectangle[2])
    			visible = 1;
    		break;
    	case 3:
    		if(y >= pDoc ->m_wndRectangle[3])
    			visible = 1;
    		break;
    	}
    	return visible;
    }

4.判断是否要求交：

int CCg_WuPing2DtransView::LineCross(int x1, int y1, int x2, int y2, int i)
    {
    	int visible1,visible2;
    
    	visible1 = pVisible(x1, y1, i);
    	visible2 = pVisible(x2, y2, i);
    
    	if(visible1 != visible2)
    		return 1;
    	else
            return 0;
    }

5．求出多边形边与裁剪窗口的交点：

void CCg_WuPing2DtransView::interSect(int Sx, int  Sy, int Px, int Py, int  i, int *ix, int *iy)//求交点
    {
    	CCg_WuPing2DtransDoc* pDoc = GetDocument();
    	switch (i) 
    	{
    	case 0: // Left
    		*ix = pDoc->m_wndRectangle[0];
    		*iy = (float)(Py-Sy)/(Px-Sx) * (pDoc->m_wndRectangle[0] - Sx) + Sy;		
    		break;
    	case 1: // Right
    		*ix = pDoc->m_wndRectangle[1];
    	    *iy = (float)(Py-Sy)/(Px-Sx) * (pDoc->m_wndRectangle[1] - Sx) + Sy;
            break;
    	case 2: // Top
    		*iy = pDoc->m_wndRectangle[2];
    		*ix= (float)(Px-Sx)/(Py-Sy) * (pDoc->m_wndRectangle[2] - Sy) + Sx;		
    		break;
    	case 3: // Bottom
    		*iy = pDoc->m_wndRectangle[3];
    	    *ix = (float)(Px-Sx)/(Py-Sy) * (pDoc->m_wndRectangle[3] - Sy) + Sx;
    		break;
    	}
    }

6.存储多边形输出顶点：

void CCg_WuPing2DtransView::outPut(int x, int y, int *Nout, int *tempX, int *tempY)
    {
    	tempX[*Nout] = x;
    	tempY[*Nout] = y;
    	(*Nout)++;
    }

五．结果：

1.线段裁剪：

![Center 3][]

![Center 4][]

2.多边形裁剪：

![Center 5][]

![Center 6][]

3.裁剪窗口移动裁剪：

![Center 7][]

[Center]: /images/20220731/1fa4c9e1814b4eec949d085212d9512d.png
[Center 1]: /images/20220731/42e8cba694354f57835d09aed83697fc.png
[Center 2]: /images/20220731/aecdb32034ae4a06894c0eb3cda40641.png
[Center 3]: /images/20220731/78bbf7a74cab41029bb10620b7f518c0.png
[Center 4]: /images/20220731/07567625396d4d3f805270451e310617.png
[Center 5]: /images/20220731/b137ba1c1a764c2aba2a23a604db2322.png
[Center 6]: /images/20220731/c0c3dbde696e49fe9eaeeffa9486d468.png
[Center 7]: /images/20220731/a6fdb3e56fc54927a0c18e291231bbb6.png