修正剪线算法的代码
Fixing the code for Line Clipping Algorithm
Midpoint subdivision algorithm [page-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;
}
您只需细分任何不完全在矩形内部或外部的线段。
我不明白这个算法有什么用。至少看看你的代码，只计算与矩形的交点会快得多。
从事几何建模多年，一直都是递归实现所有的细分算法。它的编码和理解要简单得多，而且我很确定它不会比迭代解决方案慢。
一般情况
如果剪裁是凹的，那么答案可能由任意多个片段组成。在这种情况下，您需要一个堆栈（从递归中替换代码堆栈）。下面是一个实现示例：
vector<Line> result; //ordered array of line segments = clipping result
stack<Line> pieces; //stack of pieces that are not processed yet
pieces.push(inputLine);
while (!pieces.empty()) {
auto curr = pieces.top();
pieces.pop();
if (GetLength(curr) < eps) //hard stop criterion
continue;
auto relative = GetSegmentPositionRelativeToRegion(curr, clippingRegion);
if (relative == FULLY_INSIDE)
result.push_back(curr);
else if (relative == INTERSECTS) { //not fully inside, not fully outside
Line left, right; //halves of the curr line segment
SplitAtMiddle(curr, left, right);
pieces.push(left);
pieces.push(right);
}
}
凸包
如果你的裁剪区域保证是凸的，那么结果中正好有一个线段。在这种情况下，细分过程的结构非常简单。假设输入段不完全在剪辑区域内部或外部（即它 相交 ）。
首先，您将线段细分，这样一半在外部，另一半相交并进行剪裁。这意味着你永远只能记住一个工作线段。
某时这个规则被打破，之后又出现了两个细分分支。左边的分支可能有两种分段细分的情况：(intersects + inside) or (outside + 相交)。在右侧反映：(inside + intersects) or (intersects + 外面)。在所有情况下，只有一个子段 相交 ，因此只剩下一个工作段。您可以为循环中的每个分支编写单独的代码。
P.S。当然，当裁剪区域恰好通过中点时，此描述忽略了奇异情况。对于我来说，实现这个算法是不值得的。
你问的完全正确。 Explanations of midpoint subdivision have arisen that are very sloppy or just wrong。看起来您的代码是基于这些不良来源之一。
M-S 仅用于查找交叉点 当您已经知道一个线段跨越剪裁边界（每侧一个端点） 时，它通常用整数实现。它最初用作 Cohen 和 Sutherland 的完整裁剪算法变体中的子例程。
如果您不熟悉 C-S，请参阅 the Wikipedia article。 "out codes" 引导对包含视口边界的无限线进行连续裁剪。在那里的伪代码中，您将用 M-S 替换浮点数学。
假设您在 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 个较小的变化。
终止条件很棘手。在 x0 = C-1 和 tx1 = C: (C + C - 1 + 1) >> 1 == C 的情况下，+ 1 是避免永远循环所必需的，因此下一次迭代将终止。
话虽如此，中点细分已经过时了。它对只有整数运算的处理器很有用（至少在 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 相比如何会很有趣。
我认为这是硬件实现的原因。不要将其视为剪辑。将其视为关于如何将线（或后来投影的三角形）排序为四叉树的练习。最后，您可以继续裁剪到半个节点细分，直到每个节点只有一个像素宽。不要将您的外部零件视为特殊零件。它们只是非常大的四边形。
Midpoint subdivision algorithm [page-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;
}
您只需细分任何不完全在矩形内部或外部的线段。
我不明白这个算法有什么用。至少看看你的代码，只计算与矩形的交点会快得多。
从事几何建模多年，一直都是递归实现所有的细分算法。它的编码和理解要简单得多，而且我很确定它不会比迭代解决方案慢。
一般情况
如果剪裁是凹的，那么答案可能由任意多个片段组成。在这种情况下，您需要一个堆栈（从递归中替换代码堆栈）。下面是一个实现示例：
vector<Line> result; //ordered array of line segments = clipping result
stack<Line> pieces; //stack of pieces that are not processed yet
pieces.push(inputLine);
while (!pieces.empty()) {
auto curr = pieces.top();
pieces.pop();
if (GetLength(curr) < eps) //hard stop criterion
continue;
auto relative = GetSegmentPositionRelativeToRegion(curr, clippingRegion);
if (relative == FULLY_INSIDE)
result.push_back(curr);
else if (relative == INTERSECTS) { //not fully inside, not fully outside
Line left, right; //halves of the curr line segment
SplitAtMiddle(curr, left, right);
pieces.push(left);
pieces.push(right);
}
}
凸包
如果你的裁剪区域保证是凸的，那么结果中正好有一个线段。在这种情况下，细分过程的结构非常简单。假设输入段不完全在剪辑区域内部或外部（即它 相交 ）。
首先，您将线段细分，这样一半在外部，另一半相交并进行剪裁。这意味着你永远只能记住一个工作线段。
某时这个规则被打破，之后又出现了两个细分分支。左边的分支可能有两种分段细分的情况：(intersects + inside) or (outside + 相交)。在右侧反映：(inside + intersects) or (intersects + 外面)。在所有情况下，只有一个子段 相交 ，因此只剩下一个工作段。您可以为循环中的每个分支编写单独的代码。
P.S。当然，当裁剪区域恰好通过中点时，此描述忽略了奇异情况。对于我来说，实现这个算法是不值得的。
你问的完全正确。 Explanations of midpoint subdivision have arisen that are very sloppy or just wrong。看起来您的代码是基于这些不良来源之一。
M-S 仅用于查找交叉点 当您已经知道一个线段跨越剪裁边界（每侧一个端点） 时，它通常用整数实现。它最初用作 Cohen 和 Sutherland 的完整裁剪算法变体中的子例程。
如果您不熟悉 C-S，请参阅 the Wikipedia article。 "out codes" 引导对包含视口边界的无限线进行连续裁剪。在那里的伪代码中，您将用 M-S 替换浮点数学。
假设您在 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 个较小的变化。
终止条件很棘手。在 x0 = C-1 和 tx1 = C: (C + C - 1 + 1) >> 1 == C 的情况下，+ 1 是避免永远循环所必需的，因此下一次迭代将终止。
话虽如此，中点细分已经过时了。它对只有整数运算的处理器很有用（至少在 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 相比如何会很有趣。
我认为这是硬件实现的原因。不要将其视为剪辑。将其视为关于如何将线（或后来投影的三角形）排序为四叉树的练习。最后，您可以继续裁剪到半个节点细分，直到每个节点只有一个像素宽。不要将您的外部零件视为特殊零件。它们只是非常大的四边形。