修复线裁剪算法的代码

Question

中点细分算法[第93(104)页]的工作原理是将一条线分成更小的段，并测试每个段以查找它们是否在剪切区域的可见边界内。

在二分搜索算法中，我们找到中间元素，然后选择右侧或左侧。

但是，如下图所示，在第一次分割之后，我们发现这两个小节实际上都是有争议的。因此，它们都是进一步细分的候选者。所以，我们不能像二分查找那样进行。

我正在使用迭代方法。但是，下面的代码不起作用：

    Line2d GetClippedLine()
    {
        Line2d clippingCandidate = this->line;

        std::vector<Line2d> lines = clippingCandidate.GetMidpointSubLines();

        while(lines[0] != lines[1])
        {
            lines = clippingCandidate.GetMidpointSubLines();

            Line2d one = lines[0];
            Line2d two = lines[1]; 

            if(one.IsClippingCandidate(rectangle))
            {
                clippingCandidate = one;
            }
            if(two.IsClippingCandidate(rectangle))
            {           
                clippingCandidate = two;
            }

            if(one.IsVisible(rectangle))
            {
                Coordinates2d::Draw(one, Yellow);
            }
            if(two.IsVisible(rectangle))
            {
                Coordinates2d::Draw(two, Yellow);
            }

            clippingCandidate.Show();
            //std::cout<<"++";
            //two.Show();
            std::cout<<"\n";
        }

        return clippingCandidate;
    }

Answer 1

你问得完全正确。对中点细分的解释非常草率或完全错误。看来您的代码基于这些不良来源之一。

仅当您已经知道线段跨越裁剪边界（每一侧一个端点）时， MS 仅适用于查找交点，并且通常使用整数实现。它最初被用作 Cohen 和 Sutherland 完整裁剪算法的变体中的子程序。

如果您不熟悉 CS，请参阅Wikipedia 文章。“输出代码”指导对包含视口边界的无限线进行连续剪切。在伪代码中，您可以用 MS 替换浮点数学。

假设您在 x=C 处对左边界进行裁剪，横跨它的线段是P0(x0,y0)---P1(x1,y1)。说也x0<C<=x1，P0故知为界外。那么MS算法为：

tx1 = x1; // don't modify P1; it's inside the boundary
ty1 = y1;
while (x0 < C) {
  xm = (x0 + tx1 + 1) >> 1;
  ym = (y0 + ty1 + 1) >> 1;
  if (xm <= C) { // the midpoint is on or outside the boundary
    x0 = xm;     //   move P0
    y0 = ym;
  } else {       // the midpoint is strictly inside
    tx1 = xm;    //   move P1 
    ty1 = ym;
  }
}
// The clipped segment is (x0,x1)--(y0,y1).

对于其他 3 个边界，您需要对此进行 3 个其他较小的变化。

终止条件很棘手。s+ 1对于避免在 casex0 = C-1和tx1 = C:中永远循环是必要的(C + C - 1 + 1) >> 1 == C，因此下一次迭代将终止。

话虽如此，中点细分已经过时了。它对于只有整数运算的处理器非常有用（至少在 90 年代中期之前都是这种情况；我在 1984 年用 8088 汇编语言实现了它）。找到中点只需要除以 2，即整数右移，因此可以使用不超过上限（log_2 n）的快速迭代来剪辑最大尺寸 n 的坐标。如今，浮点单元以千兆浮点运算速度运行，它可能会更快，并且更容易使用浮点进行剪辑。

加法 只是为了好玩，用 C 实现：

#include <stdio.h>
#include <stdlib.h>

typedef unsigned OUTCODE;
typedef int COORD;
typedef int BOOL;
#define TRUE 1
#define FALSE 0

#define XMIN 0
#define YMIN 0
#define XMAX 5000
#define YMAX 3000

// Not strictly portable, but usually fine.
#define SIGN_BIT (~(~0u >> 1))

#define LEFT SIGN_BIT
#define TOP (LEFT >> 1)
#define RIGHT (TOP >> 1)
#define BOTTOM (RIGHT >> 1)
#define ALL (LEFT | BOTTOM | RIGHT | TOP)

// Mask the sign bit.
#define M(X) ((X) & SIGN_BIT)

// Shift previous value and mask in the new sign bit.
#define SM(Prev, New) (((OUTCODE)(Prev) >> 1) | M(New))

__inline OUTCODE outcode(COORD x, COORD y) {
  return SM(SM(SM(M(YMAX - y), XMAX - x), y - YMIN), x - XMIN);
}

// In the S-T coordinate system, pO is outside boundary C and will be moved
// to the boundary while pI doesn't move. I is the termination correction.
#define MOVE_TO_BOUNDARY(SO, TO, SI, TI, C, I, IS_OUTSIDE) do { \
  COORD tsi = SI, tti = TI; \
  while (SO IS_OUTSIDE C) { \
    COORD sm = (tsi + SO + I) >> 1; \
    COORD tm = (tti + TO + I) >> 1; \
    if (sm IS_OUTSIDE ## = C) { \
      SO = sm; \
      TO = tm; \
    } else { \
      tsi = sm; \
      tti = tm; \
    } \
  } \
} while (0)

BOOL clip(COORD *x0p, COORD *y0p, COORD *x1p, COORD *y1p) {
  COORD x0 = *x0p, y0 = *y0p, x1 = *x1p, y1 = *y1p;
  OUTCODE code0 = outcode(x0, y0);
  OUTCODE code1 = outcode(x1, y1);
  for (;;) {
    if ((code0 | code1) == 0) {
      *x0p = x0; *y0p = y0; *x1p = x1; *y1p = y1;
      return TRUE;
    } else if (code0 & code1) {
      return FALSE;
    } else if (code0) {
      if (code0 & BOTTOM)     MOVE_TO_BOUNDARY(y0, x0, y1, x1, YMAX, 0, >);
      else if (code0 & RIGHT) MOVE_TO_BOUNDARY(x0, y0, x1, y1, XMAX, 0, >);
      else if (code0 & TOP)   MOVE_TO_BOUNDARY(y0, x0, y1, x1, YMIN, 1, <);
      else /* LEFT */         MOVE_TO_BOUNDARY(x0, y0, x1, y1, XMIN, 1, <);
      code0 = outcode(x0, y0);
    } else {
      if (code1 & BOTTOM)     MOVE_TO_BOUNDARY(y1, x1, y0, x0, YMAX, 0, >);
      else if (code1 & RIGHT) MOVE_TO_BOUNDARY(x1, y1, x0, y0, XMAX, 0, >);
      else if (code1 & TOP)   MOVE_TO_BOUNDARY(y1, x1, y0, x0, YMIN, 1, <);
      else /* LEFT */         MOVE_TO_BOUNDARY(x1, y1, x0, y0, XMIN, 1, <);
      code1 = outcode(x1, y1);
    }
  }
}

int main(void) {
  int n = 0, margin = 2000;
  for (;;) {
    // Generate some random points around the viewport.
    int x0 = rand() % (2 * margin + XMAX - XMIN) - margin;
    int y0 = rand() % (2 * margin + YMAX - YMIN) - margin;
    int x1 = rand() % (2 * margin + XMAX - XMIN) - margin;
    int y1 = rand() % (2 * margin + YMAX - YMIN) - margin;
    printf("a(%d, %d)--(%d, %d) %x--%x\n", x0, y0, x1, y1,
      outcode(x0,y0) >> 28, outcode(x1,y1) >> 28);
    BOOL r = clip(&x0, &y0, &x1, &y1);
    printf("a(%d, %d)--(%d, %d): %d\n", x0, y0, x1, y1, r);
  }
  return 0;
}

在我的 MacBook 上，它可以在 90 秒内剪辑 10 亿个片段。看看它与浮点 CS 相比如何会很有趣。