Lode 的计算机图形学教程

Cohen-Sutherland 裁剪

简介

在屏幕上绘制 2D 直线时，可能出现一个或两个端点在屏幕外，而直线的一部分仍应可见的情况。此时需要一个高效的算法来找到两个位于屏幕边缘的新端点，从而绘制出可见部分。这样，直线在屏幕外的所有点都被裁剪掉，无需浪费任何执行时间。

Cohen-Sutherland 算法是一种优秀的裁剪算法。包含该算法的函数已内置于 QuickCG 的 QuickCG.cpp 文件中，名为 clipLine。调用时传入旧直线的坐标，以及通过引用传入的新直线坐标，函数通过修改这些参数来返回新直线的坐标。

裁剪是 3D 图形学中非常重要的环节，因此在 3D 直线教程中会经常用到这个 2D 裁剪函数。

Cohen-Sutherland 裁剪算法

绘制 2D 直线时，若直线一个端点在屏幕外、另一个在屏幕内，则需裁剪直线，使屏幕内的部分保留下来。即使两个端点都在屏幕外，直线的一部分仍可能可见。裁剪算法需要找到新的端点，使其位于屏幕内部或边缘上。下面是几种情况，黑色矩形代表屏幕，红色为原端点，蓝色为裁剪后的端点：

情况 A：两个端点都在屏幕内，无需裁剪。
情况 B：一个端点在屏幕外，需裁剪该端点。
情况 C：两个端点都在屏幕外，且直线没有可见部分，不绘制。
情况 D：两个端点都在屏幕外，但直线有可见部分，裁剪两个端点后绘制。

存在大量不同情况：每个端点可能在屏幕内、左侧、右侧、上方、下方等。Cohen-Sutherland 裁剪算法能高效识别这些情况并完成裁剪。该算法将 2D 空间划分为 9 个区域：

中心区域是屏幕，其他 8 个区域位于屏幕外的不同方向。每个区域被赋予一个二进制数，称为"区域码"（outcode）。编码规则如下：

若区域在屏幕上方，第 1 位为 1
若区域在屏幕下方，第 2 位为 1
若区域在屏幕右侧，第 3 位为 1
若区域在屏幕左侧，第 4 位为 1

显然，一个区域不可能同时在左侧和右侧，也不可能同时在上方和下方，因此第 3 位和第 4 位不能同时为 1，第 1 位和第 2 位也不能同时为 1。屏幕本身的 4 位全为 0。

直线的两个端点可以位于这 9 个区域中的任意一个，存在几种平凡情况：

若两个端点都在屏幕内部或边缘上，则直线在屏幕内，可以绘制。这种情况称为平凡接受。
若两个端点在屏幕的同一侧（例如，两个端点都在屏幕上方），则直线肯定没有可见部分。这种情况称为平凡拒绝，无需绘制。

利用区域码可以轻松检测这两种情况：

平凡接受：两个端点都必须在编码为 0000 的区域内，因此只有当 code1 | code2 == 0 时才发生平凡接受，其中 code1 和 code2 是直线两端点的编码，'|' 是二进制 OR 运算符，只有当两个编码都为 0 时结果才为 0。
平凡拒绝：由于区域编码的选取方式，只有当直线两端点在区域同一侧时，两个编码才会有对应位同时为 1。例如，只有当两个端点都在屏幕左侧时，两个编码的第 4 位才都为 1。因此，平凡拒绝的检测条件为 code1 & code2 != 0，其中 & 是二进制 AND 运算，只有当两个对应位都为 1 时才返回非零结果。

所有其他情况（即既非平凡拒绝也非平凡接受）都需要通过一次裁剪操作转化为平凡情况。Cohen-Sutherland 算法是一个循环，每次只执行一次裁剪操作。它每次只裁剪直线的一个端点，且只裁剪到垂直或水平的区域边界。在许多情况下，需要多次裁剪才能最终判断直线是接受还是拒绝，但裁剪次数不超过约 4 次，因此速度相当快。

使用 Cohen-Sutherland 裁剪算法的函数是 QuickCG 中的 clipLine 函数，位于 QuickCG.cpp 文件中。它使用一个辅助函数 findRegion，返回给定端点所在区域的二进制编码。例如，要将第 2 位设为 1，需要将编码与 4 进行"或"运算（第 1 位代表 8，第 2 位代表 4，第 3 位代表 2，第 4 位（主位）代表 1）。

int findRegion(int x, int y)
{
  int code=0;
  if(y >= h)
  code |= 1; //top
  else if(y < 0)
  code |= 2; //bottom
  if(x >= w)
  code |= 4; //right
  else if (x < 0)
  code |= 8; //left
  return(code);
}

clipLine 函数的循环首先检测是否存在平凡情况：

bool clipLine(int x1, int y1, int x2, int y2, int & x3, int & y3, int & x4, int & y4)
{
  int code1, code2, codeout;
  bool accept = 0, done=0;
  code1 = findRegion(x1, y1); //the region outcodes for the endpoints
  code2 = findRegion(x2, y2);
  do //In theory, this can never end up in an infinite loop, it'll always come in one of the trivial cases eventually
  {
    if(!(code1 | code2)) accept = done = 1;  //accept because both endpoints are in screen or on the border, trivial accept
    else if(code1 & code2) done = 1; //the line isn't visible on screen, trivial reject

若未检测到平凡情况，则需对直线进行裁剪。每次只执行 4 种可能的裁剪操作之一。裁剪时，将某个端点的一个坐标设置为区域边界（也是屏幕边界）的坐标，然后根据直线方程重新计算该点的另一个坐标。为确定需要执行哪种裁剪操作，需要选择一个不在屏幕内的端点。该端点的编码称为 codeout，根据 code1 或 code2 中哪个不为零来设置。

    else  //if no trivial reject or accept, continue the loop
    {
      int x, y;
      codeout = code1 ? code1 : code2;
      if(codeout & 1) //top
      {
        x = x1 + (x2 - x1) * (h - y1) / (y2 - y1);
        y = h - 1;
      }
      else if(codeout & 2) //bottom
      {
        x = x1 + (x2 - x1) * -y1 / (y2 - y1);
        y = 0;
      }
      else if(codeout & 4) //right
      {
        y = y1 + (y2 - y1) * (w - x1) / (x2 - x1);
        x = w - 1;
      }
      else //left
      {
        y = y1 + (y2 - y1) * -x1 / (x2 - x1);
        x = 0;
      }

上面的代码计算了裁剪点的新坐标，现在需要根据 codeout 代表哪个端点，将坐标设置给 endpoint1 或 endpoint2。这也是循环的末尾，之后直线要么进入平凡情况，要么仍非平凡情况，循环继续执行更多裁剪。

      if(codeout == code1) //first endpoint was clipped
      {
        x1 = x; y1 = y;
        code1 = findRegion(x1, y1);
      }
      else //second endpoint was clipped
      {
        x2 = x; y2 = y;
        code2 = findRegion(x2, y2);
      }
    }
  }
  while(done == 0);

循环及裁剪完成后，函数设置新直线的 4 个坐标（通过引用传入），并返回是平凡接受还是平凡拒绝。

  if(accept)
  {
    x3 = x1;
    x4 = x2;
    y3 = y1;
    y4 = y2;
    return 1;
  }
  else
  {
    x3 = x4 = y3 = y4 = 0;
    return 0;
  }
}

Lode 的计算机图形学教程

Cohen-Sutherland 裁剪

目录

简介

Cohen-Sutherland 裁剪算法