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