Solved

Scan line algorithm

Posted on 1997-04-12
3
1,117 Views
Last Modified: 2012-06-22
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
0
Comment
Question by:oren020997
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 

Expert Comment

by:yangjun
ID: 1162685
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.
0
 
LVL 4

Expert Comment

by:marko020397
ID: 1162686
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

0
 

Accepted Solution

by:
aleroy earned 100 total points
ID: 1162687
The book Computer Graphics from Folley/Vandam is indeed
an excellent book ! If you are interessed in the subject, buy it !
In fact in this book, you will find everything you want to know
in section 3.5 (page 94 in the french version) about polygon filling.

Please fell free to reject the answer if you prefer an algorithm.
I don't have enough time to extract one from the book
(it is quite complex but very fast).


0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question