oren020997
asked on
Scan line algorithm
I think this is really easy, however, since I'm gonna be pretty specific, I'm givin' it 100 pts... ;-)
Anyway.... this is an ALGORITHM question not c++, but I couldn't find a better spot for it (and I'm using c++).
SO: I need an algorithm that will take a CONVEX polygon and convert it to scan lines. The polygon is described by its vertices in CW or CCW order. (This is used in a real-time 3D renderer, so I need speed). I've got a working version, but it's not fast enough.
I've searched all over the net, and even found some AMBIGUOUS pseudocode of the "active-edge" algorithm, but always missing SOME details.
So, all I want is a better (read quicker) algorithm than the one I'm using. If you can give me an algorithm or point me to one which I can use, you win! :-)
Thank you in advance,
--- Oren
Anyway.... this is an ALGORITHM question not c++, but I couldn't find a better spot for it (and I'm using c++).
SO: I need an algorithm that will take a CONVEX polygon and convert it to scan lines. The polygon is described by its vertices in CW or CCW order. (This is used in a real-time 3D renderer, so I need speed). I've got a working version, but it's not fast enough.
I've searched all over the net, and even found some AMBIGUOUS pseudocode of the "active-edge" algorithm, but always missing SOME details.
So, all I want is a better (read quicker) algorithm than the one I'm using. If you can give me an algorithm or point me to one which I can use, you win! :-)
Thank you in advance,
--- Oren
I once programmed the BGI driver for SuperVGA several years ago and came across such problems. I remembered that there was a book discussing this stuff. It gave both C and assembly routines. I forgot the name. I remembered that it talked about graphics programming in EGA and VGA graphics mode.
I have had the similar problem. One of the problems in my case
was determining start and end point of scan line. To determine
these point i used the adjusted algorithms for drawing lines.
These algorithms are very fast. You just have to find them.
As I remember this approach gave me some speed up.
If you are programming 3D or any other computer graphics then
you should read the book "Computer Graphics Principles And
Practice", Addison Wessley, 1990. The authors are: James D.
Foley, Andries van Dam, Steven K. Fenier, John F, Hughes. This
is the best book on computer graphics I have ever seen.
Marko
was determining start and end point of scan line. To determine
these point i used the adjusted algorithms for drawing lines.
These algorithms are very fast. You just have to find them.
As I remember this approach gave me some speed up.
If you are programming 3D or any other computer graphics then
you should read the book "Computer Graphics Principles And
Practice", Addison Wessley, 1990. The authors are: James D.
Foley, Andries van Dam, Steven K. Fenier, John F, Hughes. This
is the best book on computer graphics I have ever seen.
Marko
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.