CODEWITHSUNDEEP
3dlineclipping
Shail
Shail

Reputation: 29

Implementation of 3D line clipping (Cohen-Sutherland clipping algorithm) - Stuck in infinite loop

I have followed instructions from Cohen–Sutherland algorithm to implement this. Normally clipping algorithm works just fine. But sometimes it get stuck in infinite loop with some lines while clipping an object. For example., It is stuck in infinite loop with these 2 points which make one line.

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

As you can see that P1 is outside from TOP. Because, P1.y > P1.w.

So clipping happens.

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

But after clipping, P1.x > P1.w and it is outside from right. So clipping happens again.

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

But after clipping again my P1 is outside from TOP because P1.y > P1.w And hence stuck in infinite loop. I don't know what I should be looking for because I'm not sure what is wrong. It might be something wrong with my implementation of clipping algorithm or something else.

Here is my code:

# 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))

OUTPUT of first 10 iterations:

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

Can anyone please help me with this problem? Thanks!

Upvotes: 0

Views: 102

Answers (1)

Night Wolf
Night Wolf

Reputation: 21

/* 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*/

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

Upvotes: 2

Related Questions