filling triangles with bresenham's line algorithm to implement z-buffer
Author
Hello.
I am writing in C under Visual Studio 6 and Allegro.
I need to add a z-buffer to my work, as i understood i can no longer use the polygon filling function and i need to write one for using Z-Buffer.
I was told that i need to use Bresenham's line algorithm (which i already have) to draw the triangle and fill it all with that algorithm.
If some one could guide me on how to write a fast triangle filling with this algorithm it will help me a lot.
Thanks in advance. [smile]
Bresenham wasn't exactly created with filling polygons in mind,
but I guess you can use it for that too. A scanline based algorithm may be much faster actually, and I seem to remember something like that in an opengl source.
For Bresenham, you basically generate paralel lines, with start and end points also generated by "walking" the converging extra segments of the triangle. I am not sure how fast that would be or how to optimise it.
Depending on what you actually want to achieve, you might find other algos much better at the task at hand. Also, for line drawing there is a faster, yet intense memory consuming algorithm that breaks down the lines into segments that have their x,y increments already buffered. So, instead of computing, you just make 2 variable loads. x += xbuf[Step], y += ybuf[Step]; Step++;
but I guess you can use it for that too. A scanline based algorithm may be much faster actually, and I seem to remember something like that in an opengl source.
For Bresenham, you basically generate paralel lines, with start and end points also generated by "walking" the converging extra segments of the triangle. I am not sure how fast that would be or how to optimise it.
Depending on what you actually want to achieve, you might find other algos much better at the task at hand. Also, for line drawing there is a faster, yet intense memory consuming algorithm that breaks down the lines into segments that have their x,y increments already buffered. So, instead of computing, you just make 2 variable loads. x += xbuf[Step], y += ybuf[Step]; Step++;
Author
Thank you for your reply.
When i used Bresenham's line algorithm i couldn't get the lines go synchronized so i couldn't fill it on-the-fly.
Is there a way to make it go synchronized or should i seek for some other solution?
I need to get a Z-buffer for my work. Speed is a bonus.
It is more important for me to get it simple, rather than fast.
When i used Bresenham's line algorithm i couldn't get the lines go synchronized so i couldn't fill it on-the-fly.
Is there a way to make it go synchronized or should i seek for some other solution?
I need to get a Z-buffer for my work. Speed is a bonus.
It is more important for me to get it simple, rather than fast.
What do you exactly mean by go syncronized?
If you mean that you need the segments to be equal in length (the segments where you have the begining and the end points for the third segment), then
the answer would be to walk on the longer segment, and only increment when needed.
For example:
A. 15 pixels - you choose it as the directly drawn for paralel lines.
B. 8 pixels
C. 5 pixels
Then you would generate start points on the B segment, and figure out which end point it corresponds to on the C segment. This does result in overdraw, but the other way around you can "miss" certain pixels altoghether. You need though to have a simple floating point increment that multiplied with the number of pixels in the B line return the number of pixels in the C line. (R = C / B).
Horizontal scanline techniques should eliminate overdraw, and the amount of computation might be smaller.
I would use the following technique, if you are not limited to the use of Bresenham:
1. Figure out which triangle point is the topmost and leftmost.
2. By walking the 2 segments that start at that point, note down each x1, x2, for the same y coordinate.
3. with a simple for, fill a horizontal line between the x1 and x2 at y height.
4. Proceed until either one of the segments end.
5. Switch the segment that ended with the third one.
Easy.
If you mean that you need the segments to be equal in length (the segments where you have the begining and the end points for the third segment), then
the answer would be to walk on the longer segment, and only increment when needed.
For example:
A. 15 pixels - you choose it as the directly drawn for paralel lines.
B. 8 pixels
C. 5 pixels
Then you would generate start points on the B segment, and figure out which end point it corresponds to on the C segment. This does result in overdraw, but the other way around you can "miss" certain pixels altoghether. You need though to have a simple floating point increment that multiplied with the number of pixels in the B line return the number of pixels in the C line. (R = C / B).
Horizontal scanline techniques should eliminate overdraw, and the amount of computation might be smaller.
I would use the following technique, if you are not limited to the use of Bresenham:
1. Figure out which triangle point is the topmost and leftmost.
2. By walking the 2 segments that start at that point, note down each x1, x2, for the same y coordinate.
3. with a simple for, fill a horizontal line between the x1 and x2 at y height.
4. Proceed until either one of the segments end.
5. Switch the segment that ended with the third one.
Easy.
Author
I was told to use Bresenham's line algorithm because when i used the simple line equation (y=mx+n, where m is dy/dx meaning its a floating point number) the result was extremely slow and i couldn't work with it. Bresenham's line algorithm cancels the use of floating point math, thus increasing the speed.
Could you please explain that?
I meant fast enough to draw many of them on the screen at the same time. [smile]
Quote:2. By walking the 2 segments that start at that point, note down each x1, x2, for the same y coordinate.
3. with a simple for, fill a horizontal line between the x1 and x2 at y height.
Could you please explain that?
Quote:It is more important for me to get it simple, rather than fast.
I meant fast enough to draw many of them on the screen at the same time. [smile]
floating point math is fast on modern processors. you could use bresenham algorithm to determin the start and end points for your triangle, but floating point math for interpolating zbuffer values is unavoidable(unless you have an integer z buffer). as an alternative you can used fixed point math, and if you're using a system with a slow fpu this is probably the way to go. There are many subltities when using the bresenham algorithm with triangles. for example if you're splitting up the triangles into flat top and flat bottom, you have to make sure the error term in the line drawing algorithm is initialized to where it left off from the previous triangle. I'd suggest using fixed point math if speed is your main goal and your system doesn't have good fpu. otherwise, the only slow part in the traditional scan line algorithm is the float to int conversion. so you could use bresenham to trace the sides of the triangles and floating point to interpolate the z value. since the z-value interpolation is strictly floating point operation.
//edit
this isn't used anyway, you want to make it itterative to avoid multiplication like so
y, x = initial y point,x point;
slope = dx/dy;
while(y <= endy){
plot(round(x),y)
x += m
y++
}
the problem is that round in polt, this is where the majority of the speed problems come from. not from the floating point add(note, y can be an integer). so your alternative is to use bresenham(which stinks because of it's special cases(ie pos/negative lines treated different) or easier is to use fixed point math. also, when interpolating z values, there is no float to int conversion so it's not that bad, but it speed is an issue, used fixed point or integer zbuffer. I've never seen a completely bresenham algorithm but it could be done I think it would be a pain compared to the fixed point.
Tim
//edit
Quote:
y=mx+n
this isn't used anyway, you want to make it itterative to avoid multiplication like so
y, x = initial y point,x point;
slope = dx/dy;
while(y <= endy){
plot(round(x),y)
x += m
y++
}
the problem is that round in polt, this is where the majority of the speed problems come from. not from the floating point add(note, y can be an integer). so your alternative is to use bresenham(which stinks because of it's special cases(ie pos/negative lines treated different) or easier is to use fixed point math. also, when interpolating z values, there is no float to int conversion so it's not that bad, but it speed is an issue, used fixed point or integer zbuffer. I've never seen a completely bresenham algorithm but it could be done I think it would be a pain compared to the fixed point.
Tim
Imagine a triangle in 2D.
One way to fill it is to draw horizontal lines from top to bottom.
You start at the "top" of the triangle and end at the "bottom".
So, the main piece of the filling is a simple:
The y coordinate is, at the beginning of the drawing, the coordinate on OY of the topmost pixel, and at the end, the coordinate of the bottommost pixel, x1 is the leftmost pixel and x2 the rightmost.
The way to determine those 3 coordinates is:
1. find out the highest y by comparing the triangle points
2. x1 is the first pixel on the y row, x2 is the last pixel on the y row. They are generated by taking the coordinates of the 2 lines that start at the topmost point and are modified at each step of the Bresenham algo. Basically you "draw" 2 lines using Bresenham in the same direction (from high Y to low Y) and note the coresponding x's for both lines. The smaller X is the starting point, and the bigger x is the end point.
I'm not sure I can explain clearer than that.
[edit] Also, in terms of z-buffer, there is really no way around using floating point, or at least fixed point for the z values. But for rasterizing, the above should suffice.
One way to fill it is to draw horizontal lines from top to bottom.
You start at the "top" of the triangle and end at the "bottom".
So, the main piece of the filling is a simple:
for(i=x1;i<x2;i++){ ColorMePixelPretty(i, y);}//this draws a horizontal lineThe y coordinate is, at the beginning of the drawing, the coordinate on OY of the topmost pixel, and at the end, the coordinate of the bottommost pixel, x1 is the leftmost pixel and x2 the rightmost.
The way to determine those 3 coordinates is:
1. find out the highest y by comparing the triangle points
2. x1 is the first pixel on the y row, x2 is the last pixel on the y row. They are generated by taking the coordinates of the 2 lines that start at the topmost point and are modified at each step of the Bresenham algo. Basically you "draw" 2 lines using Bresenham in the same direction (from high Y to low Y) and note the coresponding x's for both lines. The smaller X is the starting point, and the bigger x is the end point.
I'm not sure I can explain clearer than that.
[edit] Also, in terms of z-buffer, there is really no way around using floating point, or at least fixed point for the z values. But for rasterizing, the above should suffice.
Quote:
Also, in terms of z-buffer, there is really no way around using floating point, or at least fixed point for the z values. But for rasterizing, the above should suffice.
ya, and to make it worse, later you might want prospective correct zbuffers(1/z buffers) in that case you'll need floating/fixed point operations. or texture interpolations.
Tim
Author
after reading your answers and a few google results i came up with this:
is this correct? is this the general idea?
int x0=50;int y0=50;int x1=600;int y1=200;int x2=300;int y2=400;int xleft=x0;int xright=x0;int dxleft = abs(x2-x0)/(y2-y0);int dxright = abs(x1-x0)/(y1-y0);int y,x;for ( y = y0; y <= y1; y++){ for ( x = xleft; x <= xright; x++) {putpixel(bmp,x,y,color);}xleft += dxleft;xright += dxright;}dxright = abs(x2-x1)/(y2-y1);for ( y = y1; y <= y2; y++){ for ( x = xleft; x<= xright; x++) {putpixel(bmp,x,y,color);}xleft += dxleft;xright += dxright;}is this correct? is this the general idea?
Something like that, except using float and calling the values rx not dx.
They are a ratio not a distance. Using ints reduces accuracy and will only work correctly for a couple of cases (45%, maybe 30, 60?, etc).
Now you only need to add the Bresenham algo to your method of finding the left x1 point and the right x2 point. That should be straightforward.
They are a ratio not a distance. Using ints reduces accuracy and will only work correctly for a couple of cases (45%, maybe 30, 60?, etc).
Now you only need to add the Bresenham algo to your method of finding the left x1 point and the right x2 point. That should be straightforward.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
