Scanline Rasterizer

[Betanumerical]

As suggested, I'm starting a thread instead of continuing the OT discussion in the maths thread.

Hmm - I wanted to hint, sorry if I'm not being clear.

Console output - that's basic in any language, should be one of the first tutorials in whichever you choose. Write a program that fills the console with #'s. From there you know a line number and a character position (since you're the one creating it) - why not try to figure out how to make this appear next?

   ##
  ##
 ########
 ########
  ##
   ##

Iterate over each line you want to output, and choose the number of spaces and #'s to appear, and where, and output them.

You may wish to create another thread to ask specific questions in so we don't continue going OT with this one.

#include <iostream>
#include <conio>

using namespace std;

int main () {

cout << " " << " " << "#" << "#" << endl;
cout << " " << "#" << "#" << endl;
cout << "#" << "#" << "#" << "#" << "#" << "#" << "#" << endl;
cout << "#" << "#" << "#" << "#" << "#" << "#" << "#" << endl;
cout << " " << "#" << "#" << endl;
cout << " " << " " << "#" << "#" << endl;

getch();

}

Well I banged this up quickly in c++ but I don't know if its what you mean.

 

[MrGaribaldi]

I think what he meant was that you should create a function that would fill the console with #, and then modify it to output a shape (ie. take 3 points of a triangle and output # if it is within the triangle)... Then do a rectangle, and then combine the two for an arrow...
Then you can extend it to do polygons, without the need for simplification to other shapes..

 

[Betanumerical]

I think what he meant was that you should create a function that would fill the console with #, and then modify it to output a shape (ie. take 3 points of a triangle and output # if it is within the triangle)... Then do a rectangle, and then combine the two for an arrow...
Then you can extend it to do polygons, without the need for simplification to other shapes..

Oh I see, I feel really stupid right now.

 

[MrGaribaldi]

Don't worry about it. IMO it's better to ask more questions than fewer, and if one or two of them sometimes feels a bit dumb afterwards who cares...

 

[catisfit]

Maybe this will help.

The idea of a scanline rasteriser is to draw a shape on a horizontal line by line basis, so to start off with, imagine your screen is, let's say 10x10 pixels:

   0123456789
0  ##########
1  ##########
2  ##########
3  ##########
4  ##########
5  ##########
6  ##########
7  ##########
8  ##########
9  ##########

And you have a triangle (I'd start with triangles as a rectangle is just two triangles next to each other ) which you want to draw, which has coordinates (5,1), (2,7) and (8,5) for the three vertices:

   0123456789
0
1       #
2 
3 
4 
5          #
6 
7    #
8 
9

You need to write a function which will end up with something like this shape (I'm just drawing these on to give an idea):

   0123456789
0
1       #
2       #
3      ###
4      ####
5     ######
6     ####
7    ##
8 
9

So what you need to do is, for each row down the screen (scanline), work out at which point on that row you enter the triangle, and which point you leave the triangle, then draw "#" inside these points and " " outside of them. Obviously some lines (like lines 0, 8 and 9 in the example above) may not enter the triangle at all.

Linear interpolation is what you need to look at to find these points on every line.

You will then need to think about what to do if one part of the triangle is off the side of your 10x10 grid and things like that.

I hope this helps to get your mind around what needs to be done

 

[Betanumerical]

Maybe this will help.

The idea of a scanline rasteriser is to draw a shape on a horizontal line by line basis, so to start off with, imagine your screen is, let's say 10x10 pixels:

   0123456789
0  ##########
1  ##########
2  ##########
3  ##########
4  ##########
5  ##########
6  ##########
7  ##########
8  ##########
9  ##########

And you have a triangle (I'd start with triangles as a rectangle is just two triangles next to each other ) which you want to draw, which has coordinates (5,1), (2,7) and (8,5) for the three vertices:

   0123456789
0
1       #
2 
3 
4 
5          #
6 
7    #
8 
9

You need to write a function which will end up with something like this shape (I'm just drawing these on to give an idea):

   0123456789
0
1       #
2       #
3      ###
4      ####
5     ######
6     ####
7    ##
8 
9

So what you need to do is, for each row down the screen (scanline), work out at which point on that row you enter the triangle, and which point you leave the triangle, then draw "#" inside these points and " " outside of them. Obviously some lines (like lines 0, 8 and 9 in the example above) may not enter the triangle at all.

Linear interpolation is what you need to look at to find these points on every line.

You will then need to think about what to do if one part of the trianlge is off the side of your 10x10 grid and things like that.

I hope this helps to get your mind around what needs to be done

Thanks you have been a great help, I bet you the answer to the problem I'm having now is going to have a really simple answer like before, but I can't for the life of me workout how to use linear interpolation to work this out. This is really embarrassing having problems with such simple problems.

EDIT: One way I can think of that might work is to construct a list of all the points along the edges of the triangle and then check if the current point being checked falls within the edges.

 

[Simon F]

Betanumerical,
One thing you should try to handle correctly are the {OpenGL} fill rules - e.g. if you have two abutting polygons with a common edge and a pixel centre that is close to (or exactly on) the shared edge, it must fall into exactly one of the two triangles.

 

[catisfit]

Thanks you have been a great help

No problem

EDIT: One way I can think of that might work is to construct a list of all the points along the edges of the triangle and then check if the current point being checked falls within the edges.

This is how linear interpolation works. Let's say you're on scanline 4 of my earlier diagram. The left edge goes from (5,1) to (2,7) and the right edge goes from (5,1) to (8,5).

For the left edge, you can work out how far "along" the edge you are, using the y coordinates (the second number in each case): The edge goes from 1 to 7, and we are at 4, so we are (4-1)/(7-1) = 0.5 of the way along the edge.

The formula is (currentline - startline) / (endline - startline) = distance along edge.

So to find the X value you need to do that equation in reverse, using the x coordinates and the distance along the edge you just calculated: (x - 5)/(2 - 5) = 0.5 so x = 3.5 (I'll say 4 in this case).

You can do the same with the other edge and get an x value of 7.25 (or 7).

So between the 4 and 7 columns (inclusive) you'd print "#", and for the rest print " ". The result is "____####__" (using underscores to represent " ").

That's scanline 4 done, move on to scanline 5...

There are some caveats here which you'll need to be aware of (like rounding), but start simply as understanding the method is more important than the implementation to start with, once you've got it working you can take account of the edge cases, optimise it etc.

Hope this helps.

 

[zsouthboy]

catisfit is right on the money with what I was trying to get you to do

Simon: Also with that rule, the top left corner point rule (which IIRC D3D and OGL do)

@Beta: seems much less complicated that you probably first though, eh? From filling in an abitrary triangle you can move to multiple triangles, z buffering those triangles, then fun with matrices, etc. Keep asking questions here along the way, others may learn from your experiences

 

[Simon F]

Simon: Also with that rule, the top left corner point rule (which IIRC D3D and OGL do)

IIRC with OpenGl it's not specific which "corner" you choose just as long as it is 100% consistent.

IMHO, this leeway makes sense as (a) it gives the vendor more flexibility and (b) who is going to change the rule if the device can change from landscape to portrait mode?

 

[Betanumerical]

No problem



This is how linear interpolation works. Let's say you're on scanline 4 of my earlier diagram. The left edge goes from (5,1) to (2,7) and the right edge goes from (5,1) to (8,5).

For the left edge, you can work out how far "along" the edge you are, using the y coordinates (the second number in each case): The edge goes from 1 to 7, and we are at 4, so we are (4-1)/(7-1) = 0.5 of the way along the edge.

The formula is (currentline - startline) / (endline - startline) = distance along edge.

So to find the X value you need to do that equation in reverse, using the x coordinates and the distance along the edge you just calculated: (x - 5)/(2 - 5) = 0.5 so x = 3.5 (I'll say 4 in this case).

You can do the same with the other edge and get an x value of 7.25 (or 7).

So between the 4 and 7 columns (inclusive) you'd print "#", and for the rest print " ". The result is "____####__" (using underscores to represent " ").

That's scanline 4 done, move on to scanline 5...

There are some caveats here which you'll need to be aware of (like rounding), but start simply as understanding the method is more important than the implementation to start with, once you've got it working you can take account of the edge cases, optimise it etc.

Hope this helps.

I think I get it (finally) you use The formula (currentline - startline) / (endline - startline) to get one edge, and then you modify the formula to find out where the equivalent point is on the opposite line (x - 5)/(2 - 5) = 0.5 so x = 3.5 and then you draw the #'s in between the two points, you have to do this for each column and row, not just the columns right?. Also what happens when you come to a point that goes from (8,5) to (2,7) ? do you just do the same thing using (8,5) to (2,7) and (5,1) to (2,7)?.

 

[catisfit]

I think I get it (finally) you use The formula (currentline - startline) / (endline - startline) to get one edge, and then you modify the formula to find out where the equivalent point is on the opposite line (x - 5)/(2 - 5) = 0.5 so x = 3.5 and then you draw the #'s in between the two points

Sorry no, that's not quite right, you need to do the whole process twice - once for each edge. I'll quote my post above and add some further explanation:

Let's say we're on scanline 4 of my earlier diagram. The left edge goes from (5,1) to (2,7) and the right edge goes from (5,1) to (8,5).

What we need to find is two points to be able to draw the scanline: the point where the left edge crosses scanline 4, and the point which the right edge crosses scanline 4. Once we have those two points, we can draw scanline 4 by filling in the area between these two points.

So let's look at finding where the left edge crosses scanline 4. This will be a point with (x,y) values. We are given a freebie as we already know the y value (it's the number of the scanline we are on = 4). So all we need to do is find x when y = 4 and we have what we need.

We do this in two steps. First of all, we work out how far "along" the edge we are, using the y coordinates we already know. The edge goes from (5,1) to (2,7), so the y coordinates are 1 and 7. We are on scanline 4, so we use the formula below:

(currentline - startline) / (endline - startline) = distance along edge

Plugging the numbers in, we have (4-1)/(7-1) = 0.5 of the way along the edge. In other words, we have worked out the proportion of the way between 1 and 7 that 4 is, in this case it's exactly halfway.

So now, we know how far along the edge we are (halfway), but we don't know what the x coordinate is at that point. We do know the start and end x values (the start and end coordinates are (5,1) to (2,7), so the x coordinates are 5 and 2). We can rearrange the above equation so that it operates in reverse:

currentline = (distance along edge * (endline - startline)) + startline

Plugging the numbers in again, we have (0.5 * (2 - 5)) + 5 = 3.5. So the actual coordinate of where the left edge crosses scanline 4 is (3.5, 4).
That's the left edge done.

Now we need to do the same for the right edge all over again. I suggest you try yourself, but just to help here are some values you can check against to make sure you're doing it right:

start: (5,1)
end: (8,5)
scanline: 4
distance along edge (using y values) = (4 - 1) / (5 - 1) = 0.75
x value = (0.75 * (8 - 5)) + 5 = 7.25
actual coordinate (7.25, 4)

So now we have the two intersection points. The left edge meets scanline 4 at (3.5,4) and the right edge meets scanline 4 at (7.25,4). All you need to do is use the x values (3.5 and 7.25) to decide where to draw "#" and where to draw " ". In this case you draw "#" from 4 to 7 (as we need to round the x coordinates to integer values), and draw " " everywhere else. So the row looks like "____####__" (using "_" to represent " ").

So that's how you do scanline 4. You just need to do the other 9 and the job is done

Also what happens when you come to a point that goes from (8,5) to (2,7) ? do you just do the same thing using (8,5) to (2,7) and (5,1) to (2,7)?.

Yes.

There are a few things you will eventually have to code for. For example:
- How do you decide which two edges you should look at for each scanline?
- What do you do if the edge is horizontal?
- What do you do on scanline 5, which intersects two edges at the vertex between the two?
- What do you do if the triangle is very small or thin and two or more vertices are on the same pixel?

But get the basics working first