3D线裁剪的实现（Cohen-Sutherland裁剪算法）-陷入无限循环

问题描述 投票：0回答：1

我按照 Cohen–Sutherland 算法 的说明来实现这一点。 通常裁剪算法工作得很好。但有时在剪辑对象时它会陷入无限循环中。 例如，它陷入了无限循环，这两个点组成了一条线。

P1 = (1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544)
P2 = (0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)

如您所见，P1 在 TOP 之外。因为，P1.y > P1.w.

因此发生了剪辑。

After clipping: P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623)

但剪裁后，P1.x > P1.w 并且从右往外。 所以剪辑再次发生。

After clipping: P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546)

但再次剪辑后，我的 P1 位于 TOP 之外，因为 P1.y > P1.w 从而陷入无限循环。 我不知道我应该寻找什么，因为我不确定出了什么问题。可能是我的裁剪算法或其他实现有问题。

这是我的代码：

# Constants for outcodes
LEFT   = 0b000001  # x < -w
RIGHT  = 0b000010  # x > +w
BOTTOM = 0b000100  # y < -w
TOP    = 0b001000  # y > +w
NEAR   = 0b010000  # z < -w
FAR    = 0b100000  # z > +w

# Function to compute the outcode for a point
def compute_outcode(x, y, z, w, P):
    outcode = 0
    if x < -w:
        outcode |= LEFT
        print(f"{P}{x, y, z, w} Left Out")
    elif x > w:
        outcode |= RIGHT
        print(f"{P}{x, y, z, w} Right Out")
    if y < -w:
        outcode |= BOTTOM
        print(f"{P}{x, y, z, w} Bottom Out")
    elif y > w:
        outcode |= TOP
        print(f"{P}{x, y, z, w} Top Out")
    if z < -w:
        outcode |= NEAR
        print(f"{P}{x, y, z, w} Near Out")
    elif z > w:
        outcode |= FAR
        print(f"{P}{x, y, z, w} Far Out")
    return outcode

# Cohen-Sutherland 3D line clipping algorithm
def cohen_sutherland_clip(P1, P2):
    x1, y1, z1, w1 = P1
    x2, y2, z2, w2 = P2
    # Compute outcodes for both points
    outcode1 = compute_outcode(x1, y1, z1, w1, "P1")
    outcode2 = compute_outcode(x2, y2, z2, w2, "P2")

    while True:
        # Trivial acceptance (both outcodes are zero)
        if outcode1 == 0 and outcode2 == 0:
            # print("Done Clipping")
            return ((x1, y1, z1, w1), (x2, y2, z2, w2))
        
        # Trivial rejection (logical AND is not zero)
        if (outcode1 & outcode2) != 0:
            return None
        
        # Choose one point outside the clipping region
        if outcode1 != 0:
            outcode_out = outcode1
        else:
            outcode_out = outcode2

        x, y, z, w = 0, 0, 0, 0
        
        print("-----------")
        # Clip point against the appropriate plane
        if outcode_out & LEFT:  # Clip against left plane (x = -w)
            t = (-w1 - x1) / ((x2 - x1) + (w2 - w1))
            y = y1 + t * (y2 - y1)
            z = z1 + t * (z2 - z1)
            w = w1 + t * (w2 - w1)
            x = -w

        elif outcode_out & RIGHT:  # Clip against right plane (x = w)
            t = (w1 - x1) / ((x2 - x1) - (w2 - w1))
            y = y1 + t * (y2 - y1)
            z =  z1 + t * (z2 - z1)
            w = w1 + t * (w2 - w1)
            x = w

        elif outcode_out & BOTTOM:  # Clip against bottom plane (y = -w)
            t = (-w1 - y1) / ((y2 - y1) + (w2 - w1))
            x = x1 + t * (x2 - x1)
            z = z1 + t * (z2 - z1)
            w = w1 + t * (w2 - w1)
            y = -w

        elif outcode_out & TOP:  # Clip against top plane (y = w)
            t = (w1 - y1) / ((y2 - y1) - (w2 - w1))
            x = x1 + t * (x2 - x1)
            z = z1 + t * (z2 - z1)
            w = w1 + t * (w2 - w1)
            y = w

        elif outcode_out & NEAR:  # Clip against near plane (z = -w)
            t = (-w1 - z1) / ((z2 - z1) + (w2 - w1))
            x  =x1 + t * (x2 - x1)
            y = y1 + t * (y2 - y1)
            w = w1 + t * (w2 - w1)
            z = -w

        elif outcode_out & FAR:  # Clip against far plane (z = w)
            t = (w1 - z1) / ((z2 - z1) - (w2 - w1))
            x = x1 + t * (x2 - x1)
            y = y1 + t * (y2 - y1)
            w = w1 + t * (w2 - w1)
            z = w
        
        # Update the point that was outside and recalculate the outcode
        if outcode_out == outcode1:
            x1, y1, z1, w1 = x, y, z, w
            print("Clipped P1")
            print(f"P1({x1}, {y1}, {z1}, {w1})")
            print(f"P2({x2}, {y2}, {z2}, {w2})")
            print("-----------\n")
            outcode1 = compute_outcode(x1, y1, z1, w1, "P1")
        else:
            x2, y2, z2, w2 = x, y, z, w
            print("Clipped P2")
            print(f"P1({x1}, {y1}, {z1}, {w1})")
            print(f"P2({x2}, {y2}, {z2}, {w2})")
            print("-----------\n")
            outcode2 = compute_outcode(x2, y2, z2, w2, "P2")

P1 = (1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544)
P2 = (0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
print(cohen_sutherland_clip(P1, P2))

前 10 次迭代的输出：

P1(1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544) Top Out
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024) Left Out
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024) Bottom Out
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024) Near Out
-----------
Clipped P1
P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623) Right Out
-----------
Clipped P1
P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546) Top Out
-----------
Clipped P1
P1(1.0624131887954296, 0.08964176964697579, 0.08962177323224663, 0.08964176964697579)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.0624131887954296, 0.08964176964697579, 0.08962177323224663, 0.08964176964697579) Right Out
-----------
Clipped P1
P1(1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544) Top Out
-----------
Clipped P1
P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623) Right Out
-----------
Clipped P1
P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546) Top Out
-----------
Clipped P1
P1(1.0624131887954296, 0.08964176964697579, 0.08962177323224663, 0.08964176964697579)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.0624131887954296, 0.08964176964697579, 0.08962177323224663, 0.08964176964697579) Right Out
-----------
Clipped P1
P1(1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.8855625490365544, 2.159434556152527, 1.8855426244586575, 1.8855625490365544) Top Out
-----------
Clipped P1
P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.0624131887954298, 0.08964176964697623, 0.08962177323224707, 0.08964176964697623) Right Out
-----------
Clipped P1
P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546)
P2(0.29644864320281183, -1.8363609313964844, -1.5815350850164043, -1.5815150217554024)
-----------

P1(1.8855625490365546, 2.159434556152527, 1.8855426244586577, 1.8855625490365546) Top Out

有人可以帮我解决这个问题吗？ 谢谢！

3d line clipping
1个回答
0
投票
/* if you follow this algorithm exactly(at least for c#), then you will fall into an infinite loop 
            in case a line crosses more than two segments. to avoid that problem, leave out the last else
            if(outcodeOut & LEFT) and just make it else*/

参考https://github.com/akmaier/CONRAD/blob/master/src/edu/stanford/rsl/tutorial/cone/ConeBeamProjector.cl#L217

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.