Diagonal Intercept Based Line Clipping - How?
BKK
While looking for efficient line clipping algorithms I stumbled upon
this: http://www.waset.org/pwaset/v23/v23-57.pdf
It seems interesting - but the paper doesn't show any example code or
pseudo-code. Does anyone know how to implement this algorithm, as the
paper isn't too clear. For example, it states:
"4. Else If the line has a positive slope then the point
of intersection the negative slope diagonal and the
line is found with optimized code as (x,y)."
Yes - but how?!?!?!?
Has anyone implemented this algorithm, and if so is there example code
out there anywhere? Google didn't help - and Wikipedia is almost a re-
publication of the original paper. :(
shreya...@gmail.com
Hi there,
Thanks for your interest in the diagonal intercept line
clipping algorithm. I am one of the authors of this algorithm.
I can send you the code for both the "diagonal intercept algorithm"
and our implementation of the Cohen Sutherland algorithm (which we
used to get those comparison figures). However, the code was done in a
hurry and right npw isn't in a very reader friendly state. The
variables will have to be renamed etc. Give me a few days, and you
will have the code. It should be up on wikipedia. The other author and
I are currently working on our undergraduate projects. This is almost
a full time job, and hence we are hard pressed for time at the
moment.
Do you have any deadline etc to meet, by which you need the code?
Thanks,
Shreyas Joshi
Jerzie.K...@gmail.com
that one should consider when reading this thread and the
mentioned paper:
1. WASET - World Academy of Science, this is another one of
those made up groups where people that have had their paper(s)
rejected from every other reputable conference head over to
and and submit.
2. The paper describes a process of "line clipping", lines can
be clipped by the result always is either a line segment or a
segment never a line, the authors of this paper don't seem to
have understood the difference.
3. There is a table that compares the Cohen-Sutherland clipping
algorithm to theirs with differences in running time of over 100%.
To think that an algorithm invented such a long-time ago and used
so heavily in computing has not seen a competitor with such a jump
in efficiency.
4. It is obvious from the quality of the text that the authors of
the paper have very little understanding of workings of Cohen-
Sutherland
algorithm let alone coming up with something better than it, in
short if it was so good, why not submit it to SIG Graph? I'm sure
if it was real it would have been accepted.
5. The request for "code" and the "oh so coincidental" fact that one
of the authors of the paper just so happens to be on /or monitoring
this group, smells of someone trying to sell themselves and their
idea.
6. The authors of the paper have also tried to get their "crap"
onto wikipedia I suggest all peoples on this list vote for the
immediate deletion of the article in question as it is of no value.
http://en.wikipedia.org/wiki/Diagonal_intercept_clipping
The authors of the paper are:
Shabib Mohammed Rafiq
Shreyas Shrikant Joshi
shreya...@gmail.com
I'm guessing you put up the deletion request. Thanks.
First, this algorithm is very real. It does exist. Those
numbers are not made up. The paper explains how we got those numbers.
If it flies in the face of established computer-graphics theory, so be
it.
you say:
" There is a table that compares the Cohen-Sutherland clipping
algorithm to theirs with differences in running time of over 100%"
well could you please clarify what differences you are referring to
here? The maximum difference mentioned in the table is 81-82%. This
difference % was calculated as follows:
(time taken by cohen-sutherland - time taken by diagonal intercept
clipping)/100
Explain how you arrived at the "100%" figure.
Also, getting that 81-82% improvement was not tough. The first thing
that the Cohen-Sutherland algorithm does, is to calculate the region
codes. Well, I'm sure you know how those lines can be trivially
rejected w/o calculating those codes, which is majorly responsible for
the large gain.
Do post your comments, specially the "over 100%" on wikipedia, as it
has specially intrigued me.
Shreyas Joshi
Also on the behalf of Shabib M Rafiq
Nils
The idea to use the diagonal is not bad per se. It reject some lines
quickly that the Cohen-Sutherland algorithm does not detect as trivial
rejects. This is a fine property.
That saves some needless line intersection calculations in some cases.
Otoh the paper gets around calculating the intersection with the end of
the line by exploiting a feature of the bresenham line algorithm. I
think they simply limit the loop-iterations to make sure they don't
render past the end of the valid clip-region
Unfortunately this only works with bresenham and similar algorithms. For
all those who draw lines using hardware or choose a different
line-rendering algorithm it's of no good. In these cases you still have
to calculate the intersections and not much is saved.
For a fair comparison of Cohen-Sutherland clipping against the proposed
algorithm the Cohen-Sutherland clipping has to be adapted to this trick
as well (e.g just clipping the start of the line).
I also have doubts about the performance improvments because calculating
the Cohen-Sutherland region-codes is so dead simple that it takes nearly
no time.
For the case of a line against a rectangle it can be done in about 20
simple CPU instructions (branchless). Any super-scalar CPU will execute
most of them in parallel. It's hard to see how such a short piece of
code can't be bound by the memory-latency on any CPU that has been used
for graphics over the last 10 years.
It's very well possible that I simply haven't understood the novel trick
of the algorithm though. The part with the screen diagonal is essential
for the understanding of the algorithm, but not well explained in the
paper.
That said - I'd like to see the code as well. I encourage the writers to
publish it. If they need web-space for it let me know.
I always like to put something new into my bag of tricks. Maybe there is
a case where this clipping algorithm outperforms the good and trusted
Cohen-Sutherland, or someone comes up with something cool based on the idea.
And now I'm back to work on my polygon triangulation,
Nils
Kenneth Sloan
>
> That said - I'd like to see the code as well. I encourage the writers to
> publish it. If they need web-space for it let me know.
I would be more interested in seeing the authors' code for
Cohen-Sutherland. I suspect that the reasons for the speed improvement
might be found *there*.
--
Kenneth Sloan Kennet...@gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
shreyasjosh...@gmail.com
Nils,
We do the following for trivial rejection:
if (the x-coordinates of both lines are above/below the clipping
window)
reject
if (the y-coordinates of both lines are to the left /right of the
clipping window)
reject
Don't you think this is faster than calculating region codes? (which
needs more if statements and more memory accesses to store the
calculated region code bit, than 2 simple if statements?)
Shreyas
Nils
> Don't you think this is faster than calculating region codes? (which
> needs more if statements and more memory accesses to store the
> calculated region code bit, than 2 simple if statements?)
No. I don't think so.
You need exactly as much compares as Cohen-Sutherland clipcodes. Your
version can "early-out" if it detects a trivial reject early while the
Cohen-Sutherland has to evaluate all the compares first and then does a
final decission.
Which approach is faster depends highly on the architecture, especially
on the smartness of the branch prediction and the predictability of your
test-data.
You need if-statements in your case. For Cohen-Sutherland you can either
use compares or some bit-twiddeling to get the result.
If you subtract instead of compare, the clipcodes end up in the sign-bit
of the result. All you have to do is to mask them out and shift them
into the correct position. This is faster for CPUs without conditional sets.
For all current CPU's the compiler will fold the if-version into
brachless code if you write the code in a way that this is possible
(e.g. you don't imply a control-flow in the if-statements).
I post some untested versions for a single clipcode calculation in c and
some asm-variants at the end of the post.
With register renaming and out of order execution functions like this
take nearly no time. It's hard to believe that such a code can make a
difference.
I'm still a bit puzzled about the trivial reject via the
cliprect-diagonal. Can you explain a bit how this works? I can see that
a infinite line must pass the finite cliprect-diagonal if it's visible,
but how does this works for non infinite lines, and how do you calculate
the intersection without divisions?
-----------
Reference C-Code:
clipcode = ((x < left)<<4)|
((x > right)<<3)|
((y < top)<<2)
((y > bottom));
On MIPS the clipcode for a single point might look like this:
XOR result, result, result ; result = 0
SLT result, x, left ; temp = (x < left) ? 1 : 0
SLT temp, right, x ; temp = (right < x) ? 1 : 0
ADD result, result, result ; result *= 2
OR result, result, temp ; result |= temp;
SLT temp, y, top ; temp = (x < left) ? 1 : 0
ADD result, result, result ; result *= 2
OR result, result, temp ; result |= temp
SLT temp, bottom, y ; temp = (right < x) ? 1 : 0
ADD result, result, result ; result *= 2
OR result, result, temp ; result |= temp;
x86 is a bit more difficult to read but basically the same:
mov ebx, [x] ; load x
mov ecx, [y] ; load y
xor eax, eax ; clear result
xor edx, edx ; clear temp
cmp ebx, [left] ; test x against left
setl al ; get clipcode in result
cmp ebx, [right] ; test x against right
setg dl ; get clipcode in temp
add al, al ; result *= 2
or al, dl ; result |= temp
cmp ecx, [top] ; test y against top
setl dl ; get clipcode in temp
add al, al ; result *= 2
or al, dl ; result |= temp
cmp ecx, [bottom] ; test y against top
setg dl ; get clipcode in temp
add al, al ; result *= 2
or al, dl ; result |= temp
; result in al or eax
ARM-Code is *very* short due to predicated instructions:
sub result, result, result
cmp x, left
addlt result, result, #8
cmp x, right
addgt result, result, #4
cmp y, top
addlt result, result, #2
cmp y, bottom
addgt result, result, #1
Anyone in he mood to contribute a SH4 version? *g*
Nils
Jerzie.K...@gmail.com
No problem - my pleasure, and just to let you know I will personally
persist the deletion process of this article on wikipedia until it has
been deleted, I will even go as far as not allowing the paper itself
be referenced on any of the clipping pages or any other pages on
wikipedia. I have had enough of nobodys like you coming and ruining
sites like that with their trash.
> First, this algorithm is very real. It does exist. Those
> numbers are not made up. The paper explains how we got those numbers.
> If it flies in the face of established computer-graphics theory, so be
> it.
>
Cohen-Sutherland is one of the most widely used CG algorithms known.
It is very simple and many pairs of eyes have looked into it. That
said in this entire time no one seems to have encountered the insight
you two idiots seems to have stumbled across. I'm not saying in
science there has never been a case where someone has obtained insight
and made leaps and bounds over what was commonly known - in fact
science is full of such situations, its just that I truly believe you
and your partner in this situation have not made such a discovery and
your pure ignorance to the topic at hand just goes to prove my point.
> you say:
> " There is a table that compares the Cohen-Sutherland clipping
> algorithm to theirs with differences in running time of over 100%"
> well could you please clarify what differences you are referring to
> here? The maximum difference mentioned in the table is 81-82%. This
> difference % was calculated as follows:
>
> (time taken by cohen-sutherland - time taken by diagonal intercept
> clipping)/100
> Explain how you arrived at the "100%" figure.
From the table in your article:
1 and 9 48.37 18.79 61.15
If we were to take _your_ time as the basis, then one could infer that
it takes Cohen-Sutherland 257% more time to compute said problem. I
chose 1-9 as it seems the most logical/useful example the other were
total nonsense.
> Also, getting that 81-82% improvement was not tough. The first thing
> that the Cohen-Sutherland algorithm does, is to calculate the region
> codes. Well, I'm sure you know how those lines can be trivially
> rejected w/o calculating those codes, which is majorly responsible for
> the large gain.
>
The ONLY way you can top Cohen-Sutherland is by reducing the number of
division operations you do.
That said remarks by Nils and Kenneth also suggest other faults in
your process.
1. Why are you comparing this to Cohen-Sutherland? your method
"supposedly" only supports a subset of the result i don't even believe
it supports the bresenham line segments properly.
2. Your results do not relate to reality, the best way to test your
method would have been with a set of randomly select line segments.
why haven't you done that test?
3. Have you actually read any of the seminal papers on line-segment
clipping? If you have you will have noticed that all of them go into
detail of their algorithms and provide code or at least a very well
thought out pseudo code for their algorithm, where is your?
4. Just looking at the references in your paper it is clear that you
have NOT read and/or related any of then contents in your paper to the
more widely accepted results from the past eg: Cohen-Sutherland,
Cyrus-Beck, Nicholl-Lee-Nicholl, Fast-Clipping
The SIMPLEST thing you could have done was to just paste your code for
Cohen-Sutherland and your routine on this list. As you can see every
second post on this group has some kind of code be it real or pseudo,
members of this list are not adverse.
It is obvious by looking at your wiki edit history that you have more
than enough time to go around editing that trash piece, why not paste
your code? oh and when the fake OP from the start of this thread asked
for code, why not just paste it here on the list why go into this "I
have to rename variables" crap? I mean come on how long does it take
to cleanup 20-30 lines of code?
If your work was of any value you would have submitted it to SIG Graph
and presented there and not on some boggy no-name conference that no
one has heard of. It seems you are either trying to make a name for
yourself or are attempting to pad your resume in either case you made
the wrong choice in continuing this thread, usenet postings remain
cached for a very long time.
Again I would like to request people on this list to request an
immediate deletion of the Wikipedia article in mention:
http://en.wikipedia.org/wiki/Diagonal_intercept_clipping
The 2 incompetent authors are:
Shabib Mohammed Rafiq
Shreyas Shrikant Joshi
The incompetent advisor that let this paper go through:
E. Poovammal