欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算机图形学----直线与多边形的裁剪

程序员文章站 2022-07-14 09:59:28
...

                                                                                  计算机图形学----直线与多边形的裁剪
        裁剪算法详解:在使用计算机处理图形信息时,计算机内部存储的图形往往比较大,而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内,哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后,再判断各点是否在窗内。但那样太费时,一般不可取。这是因为有些图形组成部分全部在窗口外,可以完全排除,不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。

一、直线段编码裁剪算法(Cohen-Sutherland算法)

        假设窗口是标准矩形,即边与坐标轴平行的矩形,由上(y=wyt)、下(y=wyb)、左(x=wxl)、右(x=wxr)四条边描述。

算法基本思想:

对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理:

(1) 直线段完全可见,“简取”之。

(2) 直线段完全不可见,“简弃”之。

(3) 直线段既不满足“简取”的条件,又不满足“简弃”的条件,需要对直线段按交点进行分段,分段后重复上述处理。

原理:将裁剪窗口各边延长,形成9个区域,最中间的框便是裁剪窗口,编码0000,其他的区域都有一个各自的编码,使得任意落在该平面的直线端点都会有各自的编码,直接通过编码运算(与、异或运算),算出完全可见和完全不可见的。

 计算机图形学----直线与多边形的裁剪

        裁剪一条线段时,先求出P1P2所在的区号code1,code2。若code1=0,且code2=0,则线段P1P2在窗口内,应取之。若按位与运算code1&code2≠0,则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外,可弃之。否则,按第三种情况处理。求出线段与窗口某边的交点,在交点处把线段一分为二,其中必有一段在窗口外,可弃之。在对另一段重复上述处理。在实现本算法时,不必把线段与每条窗口边界依次求交,只要按顺序检测到端点的编码不为0,才把线段与对应的窗口边界求交。

程序实现:

#defineLEFT 1
#defineRIGHT 2
#defineBOTTOM 4
#defineTOP 8
 
intCMy1_1View::C_S_Line(CDC *pDC, int x1, int y1, int x2, int y2)
{
   int code1,code2,code,x,y;
   encode(x1,y1,&code1); //(x1,y1)处的编码
   encode(x2,y2,&code2); //(x2,y2)处的编码
   while (code1!=0||code2!=0)   //当 code1 不等于0 或code2 不等于0
   {
      if ((code1&code2)!=0) return 0;  //当 code1 与code2 不等于0,在同侧;
      code=code1;
      if (code1==0)  code=code2;
      if ((LEFT&code)!=0)   //求交点
      {
         x=WL;
         y=y1+(y2-y1)*(WL-x1)/(x2-x1);
      }
      else if ((RIGHT&code)!=0)
      {
         x=WR;
         y=y1+(y2-y1)*(WR-x1)/(x2-x1);
      }
      else if ((BOTTOM&code)!=0)
      {
         y=WB;
         x=x1+(x2-x1)*(WB-y1)/(y2-y1);
      }
      else if ((TOP&code)!=0)
      {
         y=WT;
         x=x1+(x2-x1)*(WT-y1)/(y2-y1);
      }
      if (code==code1)
      {
         x1=x;y1=y;
         encode(x,y,&code1);
      }
      else
      {
         x2=x;y2=y;
         encode(x,y,&code2);
      }
   }
   //end while,表示code1,code2 都为0,其中的线段为可视部分
   pDC->MoveTo(x1+350,y1);
   pDC->LineTo(x2+350,y2);
}
//对坐标点(x,y)编码
void CMy1_1View::encode(int x, int y, int*code)
{
  int c=0;
   if(x<WL)  c=c|LEFT;
  else if (x>WR) c=c|RIGHT;
   if(y<WB)  c=c|BOTTOM;
  else if (y>WT) c=c|TOP;
  *code=c;
}

程序运行效果(后附文档,有详细操作):

计算机图形学----直线与多边形的裁剪

直线与多边形的裁剪.docx

二、多边形裁剪

        对于一个多边形,可以把它分解为边界的线段逐段进行裁剪。但这样做会使原来封闭的多边形变成不封闭的或者一些离散的线段。当多边形作为实区域考虑时,封闭的多边形裁剪后仍应当是封闭的多边形,以便进行填充。为此,可以使用Sutherland-Hodgman算法。该算法的基本思想是一次用窗口的一条边裁剪多边形。

        算法的每一步,考虑窗口的一条边以及延长线构成的裁剪线。该线把平面分成两个部分:一部分包含窗口,称为可见一侧;另一部分称为不可见一侧。依序考虑多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种。

(1)S,P均在可见一侧

(2)S,P均在不可见一侧

(3)S可见,P不可见

(4)S不可见,P可见。

计算机图形学----直线与多边形的裁剪

上述算法仅用一条裁剪边对多边形进行裁剪,得到一个顶点序列,作为下一条裁剪边处理过程的输入。对于每一条裁剪边,算法框图一样,知识判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。

基于divide and conquer策略的Sutherland-Hodgman算法

typedef struct
{ float x; float y; }Vertex;
typedef Vertex Edge[2];
typedef Vertex VertexArray[MAX];
void SutherlandHodgmanClip(VertexArray InVertexArray, VertexArray
OutVertexArray, edge ClipBoundary, int &Inlength, int &Outlength) {      Vertex s, p, ip;
int j;
    Outlength = 0;
    S = InVertexArray [InLength -1];
   for (j = 0; j < Inlength; j++)
   {
        P = InVertexArray [j];
       if(Inside (P, ClipBoundary))
       { if(Inside (S, ClipBoundary)) //SP在窗口内,情况1
        Output(p, OutLength, OutVertex Array)
       else{ //S在窗口外, 情况4
           Intersect (S, P, ClipBoundary, &ip);
           Output (ip, OutLength, OutVertexArray);
           Output (P, OutLength, OutVertexArray);
        }
    }
   else if (Inside (S, WindowsBoundary))
   { //S在窗口内,P在窗口外,情况3
      Intersect (S, P, ClipBoundary, &ip);
      Output (ip, OutLength, OutVertexArray);
   } //情况2没有输出
   S = P;
   }
}

//判点在窗口内
bool Inside (Vertex &TestPt, Edge ClipBoundary)
{ if(ClipBoundary[1].x> ClipBoundary[0].x)//裁剪边为窗口下边 
    if(testpt.y>=ClipBoundary[0].y)
    return TRUE;
else if(ClipBoundary[1].x< ClipBoundary[0].x) //裁剪边为窗口上边 
    if(testpt.y<= ClipBoundary[0].y)
    return TRUE;
else if(ClipBoundary[1].y> ClipBoundary[0].y) //裁剪边为窗口右边 
    if(testpt.x<= ClipBoundary[0].x)
    return TRUE;
else if(ClipBoundary[1].y< ClipBoundary[0].y) //裁剪边为窗口左边 
if(testpt.x>= ClipBoundary[0].x)
    return TRUE;
   return FALSE;
}

//直线段SP和窗口边界求交,返回交点;
void Intersect (Vertex&S,Vertex &P,Edge ClipBoundary,Vertex& IntersectPt)
{ 
    if(ClipBoundary[0].y== ClipBoundary[1].y)//水平裁剪边
    { IntersectPt.y = ClipBoundary[0].y;
     IntersectPt.x = S.x+( ClipBoundary[0].y -s.y)*(p.x - s.x) / (p.y - s.y);
    }
    else //垂直裁剪边
   { Intersect.x = ClipBoundary[0].x;
     Intersect.y = s.y + (ClipBoundary[0].x - s.x)*(p.y - s.y) / (p.x. - s.x);
    }
}

http://www.doc88.com/p-3681059225014.html

相关标签: 计算机 图形