R.Wieser
2020-10-08 16:37:11 UTC
Hello all,
I need someone to eyeball what I think I've found, and tell me where I went
hopelesly off-track. At least, I think I must have, as several
implementations and/or examples of the Cohen-Sutherland algoritm all seem to
do the exact same thing - which is different from what I ended up with.
The Cohen-Sutherland algorithm is explained here :
http://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/mm.html
with its pseudo-code(?) implementation here :
https://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/code1.html
While implementing it for a 16-bit DOS environment (and having problems
understanding what exactly should be happening in the
"CohenSutherlandLineClipAndDraw"s "main" block) I suddenly realized that the
"CompOutCode" function (to determine the "zone" a coordinate is in) gets
called each time a lines clipping is actually done - which can happen upto
four times.
Like when a line is drawn from the lower part of the top-left zone to the
upper part of the bottom-right zone (it would pass, in order, the top, left,
bottom and right boundaries)
Loading Image...
Thats 16 comparisions and associated bitmask settings - which I think are
unnneeded.
Replacing a line like "if TOP in outcodeOut then" with a simple
coordinate-against-boundary check (like "if y1 < TOP then") does away with
having to call "CompOutCode".
Also, I do not see any reason to loop thru those checks until a zero "zone"
mask is generated - a simple checking for all four boundaries in (no
particular) order looks to be enough ...
IOW, my current program first does an "if (x1 <left and x2 < left) or (..."
check to determine a "trivial discarding" of a line, and if not continues to
clip the first coordinate against all boundaries in succession ( "if x1 <
left {update x1,y1}; if x1 > right {update x1,y1}; if y1 < bottom {update
x1,y1}; if y1 > top {update x1,y1};" ), than swaps the coordinates and does
it again so the enpoint is clipped too.
tl;dr:
Can someone explain to me how the Cohen-Sutherland algoritm speeds up and/or
simplifies basic line clipping ?
Regards,
Rudy Wieser
P.s.
A few of the webpages effectivily all doing the same thing :
https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
https://www.geeksforgeeks.org/line-clipping-set-1-cohen-sutherland-algorithm/
https://iq.opengenus.org/cohen-sutherland-line-clipping-algorithm/
https://sighack.com/post/cohen-sutherland-line-clipping-algorithm
I need someone to eyeball what I think I've found, and tell me where I went
hopelesly off-track. At least, I think I must have, as several
implementations and/or examples of the Cohen-Sutherland algoritm all seem to
do the exact same thing - which is different from what I ended up with.
The Cohen-Sutherland algorithm is explained here :
http://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/mm.html
with its pseudo-code(?) implementation here :
https://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/code1.html
While implementing it for a 16-bit DOS environment (and having problems
understanding what exactly should be happening in the
"CohenSutherlandLineClipAndDraw"s "main" block) I suddenly realized that the
"CompOutCode" function (to determine the "zone" a coordinate is in) gets
called each time a lines clipping is actually done - which can happen upto
four times.
Like when a line is drawn from the lower part of the top-left zone to the
upper part of the bottom-right zone (it would pass, in order, the top, left,
bottom and right boundaries)
Loading Image...
Thats 16 comparisions and associated bitmask settings - which I think are
unnneeded.
Replacing a line like "if TOP in outcodeOut then" with a simple
coordinate-against-boundary check (like "if y1 < TOP then") does away with
having to call "CompOutCode".
Also, I do not see any reason to loop thru those checks until a zero "zone"
mask is generated - a simple checking for all four boundaries in (no
particular) order looks to be enough ...
IOW, my current program first does an "if (x1 <left and x2 < left) or (..."
check to determine a "trivial discarding" of a line, and if not continues to
clip the first coordinate against all boundaries in succession ( "if x1 <
left {update x1,y1}; if x1 > right {update x1,y1}; if y1 < bottom {update
x1,y1}; if y1 > top {update x1,y1};" ), than swaps the coordinates and does
it again so the enpoint is clipped too.
tl;dr:
Can someone explain to me how the Cohen-Sutherland algoritm speeds up and/or
simplifies basic line clipping ?
Regards,
Rudy Wieser
P.s.
A few of the webpages effectivily all doing the same thing :
https://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland_algorithm
https://www.geeksforgeeks.org/line-clipping-set-1-cohen-sutherland-algorithm/
https://iq.opengenus.org/cohen-sutherland-line-clipping-algorithm/
https://sighack.com/post/cohen-sutherland-line-clipping-algorithm