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