c++ - 修正剪线算法的代码

Question

Midpoint subdivision algorithm [page-93(104)]的工作原理是将一条线分成更小的段，并测试每个段以发现它们是否在裁剪区域的可见边界内。

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

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

我正在使用迭代方法。但是，以下代码不起作用:

    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

你问的很对。 Explanations of midpoint subdivision have arisen that are very sloppy or just wrong .看起来您的代码是基于这些不良来源之一。

M-S 仅在您已经知道线段横跨裁剪边界(每侧一个端点)时才可用于查找交点，并且它通常用整数实现。它最初用作 Cohen 和 Sutherland 的完整裁剪算法变体中的子例程。

参见 the Wikipedia article如果你不熟悉 C-S。 “输出代码”指导对包含视口(viewport)边界的无限线进行连续裁剪。在那里的伪代码中，您将用 M-S 替换 float 学。

假设您在 x=C 处对左边界进行剪裁，并且横跨它的线段是 P0(x0,y0)---P1(x1,y1) .也说x0<C<=x1 , 所以 P0已知在边界之外。那么M-S算法就是:

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 个较小的变化。

终止条件很棘手。 + 1 s 是避免在 x0 = C-1 情况下永远循环的必要条件。和 tx1 = C : (C + C - 1 + 1) >> 1 == C ，所以下一次迭代将终止。

话虽如此，中点 segmentation 几乎已经过时了。它对只有整数运算的处理器很有用(至少在 90 年代中期之前都是这种情况；我在 1984 年用 8088 汇编语言实现了它)。找到中点只需要除以 2，即整数右移，因此可以对最大大小为 n 的坐标进行不超过 ceiling(log_2 n) 次快速迭代的裁剪。如今，随着浮点单元以 gigaflop 的速率运行，用浮点进行裁剪可能会更快，当然也更容易。

添加只是为了好玩，用 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 亿个片段。看看这与浮点 C-S 相比如何会很有趣。