计算机图形学学习笔记(6.1):直线段裁剪

屏幕映射的概念

如下图所示，要将实体显示在2D的屏幕上，需要先将实体在规范化的观察空间中进行投影变换，然后进行裁剪。这个过程就叫屏幕映射。

 

裁剪要处理的问题，就是将在观察窗口内部的图形裁剪出来，进行显示。在观察窗口之外的图形，将不被显示。如下图：

 

首先需要解决的是直线段裁剪问题。下面介绍两个非常著名的算法。

直线段裁剪

Cohen-Sutherland方法

要解决的问题： 对直线段P1 (x1 ,y1 ) -P2 (x2 ,y2)进行裁剪。

Cohen-Sutherland方法：基于编码的裁剪方法

基本思想：对每条直线段P1 (x1 ,y1 )P2 (x2 ,y2)分三种情况处理
(1) 直线段完全可见，“简取”之。
(2) 直线段完全丌可见，“简弃”之。
(3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。

 

 

编码：对于任一端点(x,y)，根据其坐标所在的区域，赋予一个4位的二进制码D3D2D1D0。
编码规则如下：

• 若x<wxl，则D0=1，否则D0=0；

• 若x>wxr，则D1=1，否则D1=0；

• 若y<wyb，则D2=1，否则D2=0；

• 若y>wyt，则D3=1，否则D3=0.

如下图：

 

裁剪一条线段时，先求出端点p1和p2的编码 code1和code2，然后：

(1)若code1|code2=0，对直线段应简取之。

(2)若code1&code2≠0，对直线段可简弃之。

(3)若上述两条件均丌成立。则需求出直线段不窗口边界的交点。在交点处把线段一分为二， 其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。

情况(3)具体做法：按左、下、右、上的顺序求出直线段与窗口边界的交点，分段处理。下图是一个例子：

对于情况(3)，还有另一种方法：二分法。即当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。

Liang-Barsky算法

该算法由梁友栋、Barsky分别独立发明，是目前最高效的直线段裁剪算法。

基本思想：把直线看成是一条有方向的线段，把窗口的四条边及其延长线分成两类：入边和出边

入边：左边界和下边界------从裁剪框外向裁剪框内

出边：右边界和上边界------从裁剪框内向裁剪框外

任意直线段I(x1,y1）J(x2,y2 )的参数方程：

                                                  ,其中0<=u<=1.

给定裁剪窗口：

 

如果任一点在窗口内, 则有：

                                                 

上述关系可用4个不等式表达：

                                                                

 

简记为：,其中：

                                                                

几点说明：

• 取“=”时求得的u对应的是直线不窗口边界的交点
• 1、2、3、4分别对应左、右、下、上边界
• u=0和1时分别对应直线的起点和终点

那么，裁剪后的两端点是哪些点？

 

Uone> Utwo表明：没有线段在矩形内。

下图说明了，当PK为0时的特殊情况处理：

以下是Liang-Barsky算法代码的一个C++示例：

// Liang--Barsky line-clipping algorithm
#include<iostream>
#include<graphics.h>
#include<math.h>
using namespace std;
// this function gives the maximum
float maxi(float arr[],int n) {
  float m = 0;
  for (int i = 0; i < n; ++i)
    if (m < arr[i])
      m = arr[i];
  return m;
}
// this function gives the minimum
float mini(float arr[], int n) {
  float m = 1;
  for (int i = 0; i < n; ++i)
    if (m > arr[i])
      m = arr[i];
  return m;
}


void liang_barsky_clipper(float xmin, float ymin, float xmax, float ymax,
                          float x1, float y1, float x2, float y2) {
  // defining variables
  float p1 = -(x2 - x1);
  float p2 = -p1;
  float p3 = -(y2 - y1);
  float p4 = -p3;
  float q1 = x1 - xmin;
  float q2 = xmax - x1;
  float q3 = y1 - ymin;
  float q4 = ymax - y1;
  float posarr[5], negarr[5];
  int posind = 1, negind = 1;
  posarr[0] = 1;
  negarr[0] = 0;
  rectangle(xmin, 467 - ymin, xmax, 467 - ymax); // drawing the clipping window
  if ((p1 == 0 && q1 < 0) || (p3 == 0 && q3 < 0)) {
      outtextxy(80, 80, "Line is parallel to clipping window!");
      return;
  }
  if (p1 != 0) {
    float r1 = q1 / p1;
    float r2 = q2 / p2;
    if (p1 < 0) {
      negarr[negind++] = r1; // for negative p1, add it to negative array
      posarr[posind++] = r2; // and add p2 to positive array
    } else {
      negarr[negind++] = r2;
      posarr[posind++] = r1;
    }
  }
  if (p3 != 0) {
    float r3 = q3 / p3;
    float r4 = q4 / p4;
    if (p3 < 0) {
      negarr[negind++] = r3;
      posarr[posind++] = r4;
    } else {
      negarr[negind++] = r4;
      posarr[posind++] = r3;
    }
  }
  float xn1, yn1, xn2, yn2;
  float rn1, rn2;
  rn1 = maxi(negarr, negind); // maximum of negative array
  rn2 = mini(posarr, posind); // minimum of positive array
  xn1 = x1 + p2 * rn1;
  yn1 = y1 + p4 * rn1; // computing new points
  xn2 = x1 + p2 * rn2;
  yn2 = y1 + p4 * rn2;
  setcolor(CYAN);
  line(xn1, 467 - yn1, xn2, 467 - yn2); // the drawing the new line
  setlinestyle(1, 1, 0);
  line(x1, 467 - y1, xn1, 467 - yn1);
  line(x2, 467 - y2, xn2, 467 - yn2);
}


int main() {
  cout << "\nLiang-barsky line clipping";
  cout << "\nThe system window outlay is: (0,0) at bottom left and (631, 467) at top right";
  cout << "\nEnter the co-ordinates of the window(wxmin, wxmax, wymin, wymax):";
  float xmin, xmax, ymin, ymax;
  cin >> xmin >> ymin >> xmax >> ymax;
  cout << "\nEnter the end points of the line (x1, y1) and (x2, y2):";
  float x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int gd = DETECT, gm;
  // using the winbgim library for C++, initializing the graphics mode
  initgraph(&gd, &gm, "");
  liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);
  getch();
  closegraph();
}