Discussion:
Line clipping w. Cohen-Sutherland - causes more work & time instead of less ?
(too old to reply)
R.Wieser
2020-10-08 16:37:11 UTC
Permalink
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
Terje Mathisen
2020-10-08 19:52:47 UTC
Permalink
I never studied or read up on any textbook algorithms for line clipping
against a frustrum, but in my own code I had the special case that
frustrum would always be rectangular with aligned vertical/horizontal
edges, so the code was simple enough:

Check left vertical edge, if the x coordinates cross it, clip
Check right vertical edge, ditto
Check bottom horizontal edge, clip if needed
Check top edge, ditto.

An alternative is to classify each coordinate into one of 9 bins, and
then use the resulting product for classify(x0,y0)*classify(x1,y1) to
very quickly detect both all inside and most of the discard cases, i.e.
both end points either above or below, left or right of the clipping
(visible) area.

For the remaining cases apply the parts of the first algorithm that
makes sense for each case, i.e. only the full diagonals (from 0 to 8 or
2 to 6) need all the clipping operations, and at that point there is no
need to re-calculate the bin number.

Terje
Post by R.Wieser
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.
http://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/mm.html
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)
https://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/pic1.gif
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.
Can someone explain to me how the Cohen-Sutherland algoritm speeds up and/or
simplifies basic line clipping ?
Regards,
Rudy Wieser
P.s.
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
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
R.Wieser
2020-10-09 07:53:33 UTC
Permalink
Terje,
but in my own code I had the special case that frustrum would always be
rectangular
Thats what I'm having.
[snip]

Which is pretty-much what I ended up with too.
An alternative is to classify each coordinate into one of 9 bins,
And thats pretty-much the problem : what does it give that a simple "if (x1
< Left and x2 < Left) or (x1 > Right and ....") comparision doesn't provide.
For the remaining cases apply the parts of the first algorithm that makes
sense for each case, i.e. only the full diagonals (from 0 to 8 or 2 to 6)
need all the clipping operations
So, trying to skip certain checks depending on which zones the start and
endpoints are in ? AFAICS that won't work, as the exact clipping action is
dependant on where, in those corner zones, the start and endpoints are.

Assuming a diagonal line than if it starts above the clipwindow diagonal the
top-boundary clip should be taken. If it starts below the diagonal the
left-boundary should be taken. It gets complicated when a line is not at
a diagonal angle, or when only the start or endpoints are in those corner
zones ...

I have got zero proof, but somehow I get the feeling that such checks could
easily become more expensive than a duplicated clipping or two.


tl;dr:
The thing is that the Cohen-Sutherland algorithm seems to make the whole
thing more complicated (and costly in the sense of total instructions - even
in pseudo-code) than what you and I ended up with. And that does not make
any sense. As such I came to the conclusion I must be missing something in
that algorithm. The question is, what ?

Regards,
Rudy Wieser
wolfgang kern
2020-10-09 10:34:51 UTC
Permalink
On 09.10.2020 09:53, R.Wieser wrote:
[...]
Post by R.Wieser
The thing is that the Cohen-Sutherland algorithm seems to make the whole
thing more complicated (and costly in the sense of total instructions - even
in pseudo-code) than what you and I ended up with. And that does not make
any sense. As such I came to the conclusion I must be missing something in
that algorithm. The question is, what ?
cannot see any sense in it either, perhaps just to explain what clipping
is to non-aware folks.
my clip is in the final dot-drawer, so what's outside become ignored but
may delay the whole story.
__
wolfgang
R.Wieser
2020-10-09 11:16:12 UTC
Permalink
Wolfgang,
Post by wolfgang kern
cannot see any sense in it either, perhaps just to explain what clipping
is to non-aware folks.
Understanding what clipping is was the easy part.
Post by wolfgang kern
my clip is in the final dot-drawer, so what's outside become ignored but
may delay the whole story.
Thats what I've beein doing too. But at some point I saw sense in not
going thru slews of dots that are not going to be displayed anyway, likely
speeding up the drawing process itself. Especially as I wanted to be able
to draw in a full 16-bit signed int range, while only actually viewing a
small part of it.

Regards,
Rudy Wieser
wolfgang kern
2020-10-10 10:16:35 UTC
Permalink
Post by R.Wieser
Wolfgang,
Post by wolfgang kern
cannot see any sense in it either, perhaps just to explain what clipping
is to non-aware folks.
Understanding what clipping is was the easy part.
Post by wolfgang kern
my clip is in the final dot-drawer, so what's outside become ignored but
may delay the whole story.
Thats what I've beein doing too. But at some point I saw sense in not
going thru slews of dots that are not going to be displayed anyway, likely
speeding up the drawing process itself. Especially as I wanted to be able
to draw in a full 16-bit signed int range, while only actually viewing a
small part of it.
Yes, me too once tried to gain speed by clipping before the draw, but
the additional checks took more time than a few not written dots.
My draw functions use 16 bit unsigned (left,top screen == 0,0).
__
wolfgang
R.Wieser
2020-10-10 14:47:01 UTC
Permalink
Wolfgang,
Post by wolfgang kern
My draw functions use 16 bit unsigned (left,top screen == 0,0).
In hindsight I should maybe have done that too, as mixing signed and
unsigned values together (coordinates and distances between them) (while
staying within the 16-bit realm of instructions) took me a while to wrap my
head round.

Regards,
Rudy Wieser

Terje Mathisen
2020-10-09 13:01:10 UTC
Permalink
Post by R.Wieser
Terje,
but in my own code I had the special case that frustrum would always be
rectangular
Thats what I'm having.
[snip]
Which is pretty-much what I ended up with too.
An alternative is to classify each coordinate into one of 9 bins,
And thats pretty-much the problem : what does it give that a simple "if (x1
< Left and x2 < Left) or (x1 > Right and ....") comparision doesn't provide.
One key issue is that you can generate all those classifications in
parallel, so it could all be done in a cycle or two, replacing a bunch
of distributed/replicated if (a <= b) tests.
Post by R.Wieser
For the remaining cases apply the parts of the first algorithm that makes
sense for each case, i.e. only the full diagonals (from 0 to 8 or 2 to 6)
need all the clipping operations
So, trying to skip certain checks depending on which zones the start and
endpoints are in ? AFAICS that won't work, as the exact clipping action is
dependant on where, in those corner zones, the start and endpoints are.
Absolutely right, but it still helps: If we number the zones from 0 to
8, top left to bottom right, and neither end point is in the first
(0..2) row, then we can skip all clip tests against the top of the
frustrum. Similarly with any other side of the target zone.

When both end points are in the same row or column we get to either
trivially discard, or limit clipping to one dimension.
Post by R.Wieser
Assuming a diagonal line than if it starts above the clipwindow diagonal the
top-boundary clip should be taken. If it starts below the diagonal the
left-boundary should be taken. It gets complicated when a line is not at
a diagonal angle, or when only the start or endpoints are in those corner
zones ...
I believe my own code ignores the order clips should occur in, i.e. a
diagonal line passing the top and right boundaries can be clipped
against those two lines in arbitrary order and still come out correct,
we don't need to figure out up front if anything will be visible or not.
Post by R.Wieser
I have got zero proof, but somehow I get the feeling that such checks could
easily become more expensive than a duplicated clipping or two.
I agree.
Post by R.Wieser
The thing is that the Cohen-Sutherland algorithm seems to make the whole
thing more complicated (and costly in the sense of total instructions - even
in pseudo-code) than what you and I ended up with. And that does not make
any sense. As such I came to the conclusion I must be missing something in
that algorithm. The question is, what ?
I'm assuming this was intended for HW implementation where it is easy to
have enough parallel resources to perform all those operations more or
less at the same time.

With modern SIMD hardware we also want as many of the comparisons to
happen at the same time as we can manage.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
R.Wieser
2020-10-09 16:36:33 UTC
Permalink
Terje,
Post by Terje Mathisen
One key issue is that you can generate all those classifications in
parallel, so it could all be done in a cycle or two, replacing a bunch of
distributed/replicated if (a <= b) tests.
I did not think of that, but that is indeed a case in which it could/would
matter (clipping both endpoints in parallel would than be another big
speed-up).

I do not see anything in/to the algorithm about such an intention though.
Also, AFAIC most environments upto rather recently where single-core (and
the algorithm was created back in 1967).
Post by Terje Mathisen
Absolutely right, but it still helps: If we number the zones from 0 to 8,
top left to bottom right, and neither end point is in the first (0..2)
row, then we can skip all clip tests against the top of the frustrum.
Yes, thats the method used in the pseudo-code. I don't think that that
bit-test will be much, if any shorter than the comparision of two values
though (assuming that the coordinates fit in the processors registers) .

In short, only the first creation of that zone bitmask (instead of four
times two coordinate-against-boundary comparisions) seem to weigh positivily
against the total time spend. In the other cases a comparision of two
values could well be shorter than a regeneration of that zone bitmask and
the subsequently needed bit-test.

Hmm... Just thought of using the gathered zone bits as an index in a
jumptable to different boundary-compare sequences. As you said, a line which
starts in zone 0 (and is not trivially rejected) only needs to compare with
the top and left boundaries. On the other hand, thats a lot of
duplicated code just to remove (the opposite) two boundary checks ....
Post by Terje Mathisen
I believe my own code ignores the order clips should occur in
So does mine. And as you said, it works ok that way (test have not shown
any glaring problems with it).
Post by Terje Mathisen
I'm assuming this was intended for HW implementation where it is easy to
have enough parallel resources to perform all those operations more or
less at the same time.
Yes, thats is an explanation that makes sense. Thanks for that. I thought
I was going mad here. :-|
Post by Terje Mathisen
With modern SIMD hardware we also want as many of the
comparisons to happen at the same time as we can manage.
With modern hardware there is a good chance I can just tell the GPU what I
want to have happen and than leave the rest upto it. :-)

Regards,
Rudy Wieser
Loading...