Sign in to follow this  
someuser77

filling triangles with bresenham's line algorithm to implement z-buffer

Recommended Posts

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]

Share this post


Link to post
Share on other sites
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++;

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.
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]

Share this post


Link to post
Share on other sites
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
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

Share this post


Link to post
Share on other sites
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:

for(i=x1;i<x2;i++)
{
ColorMePixelPretty(i, y);
}
//this draws a horizontal line




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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
after reading your answers and a few google results i came up with this:

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
I guess I'm curious why you can't just draw it into the depth buffer by disabling the color buffer when you draw the triangle. If you are manually implementing a depth buffer then that isn't an option, but if it does apply then it seems worthwhile to state the simple solution.

Share this post


Link to post
Share on other sites
I dont understand your code. what if the slope is not an integer value? you cant use integers for your slopes. unless you impliment an error term to keep track how far off the line you are(like bresenham/midpoint method).

Tim

Share this post


Link to post
Share on other sites
@JohnBSmall's post

There are many ways to rasterize a triangle, it may be worth to check out
the DirectX rules for that (the SDK will have that at "Triangle Rasterization Rules".

Also, indeed, why is the normal Z-buffer not allowed in your project?
All but the oldest cards support z-buffer, and I do mean OLD.

Share this post


Link to post
Share on other sites
Quote:
I dont understand your code. what if the slope is not an integer value?

int x0=50;
int y0=50;

int x1=600;
int y1=200;

int x2=300;
int y2=400;

float xleft=x0;
float xright=x0;

float dxleft = abs(x2-x0)/(y2-y0);
float 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;
}

}



Quote:
Also, indeed, why is the normal Z-buffer not allowed in your project?

It is allowed, thats what i'm trying to do.

Is there a point in putting the the x,y value of each point of the segmant in an array and then drawing it?

Share this post


Link to post
Share on other sites
Now this is cool.

If you want to draw textured triangles with z-buffer and using directx you DO NOT NEED to put pixels yourself. Just use Direct3D and the simplest DirectX tutorial that comes with the DirectX SDK.

On the other hand, if you are writing your own renderer (for use on systems that don't have a 3D video card, for example), then you need a custom Z-Buffer, hand written.

Now, back to the important question, what are the exact terms of your project/assigment?

Share this post


Link to post
Share on other sites
Use a variation of the Bresenham algorithm that does dz/dx in addition to dy/dx, keeping in mind that the triangle exists in 3D. For any pixel (x,y), you do a depth check and if the new pixel is closer than the old pixel you write the color to the frame buffer and the z-value to the depth buffer.

Share this post


Link to post
Share on other sites
@zipster

I don't think it's such a great idea to use integer steps...

Overlapping triangles, z-buffer and integers don't really mix.
For z axis he should really use floating/fixed point interpolation.

Share this post


Link to post
Share on other sites
1. don't use integers unless you have enough bits to do decent fixed point (16.16)
2. don't use gouraud like interpolation, instead for triangle find A,B,C for equation Z=Ax+By+C and use it do do all calculation

if you will use gouraud , integer and stuff like that you will get a big mess.

Share this post


Link to post
Share on other sites
Quote:

don't use gouraud like interpolation

why? it's just another lerp, the same code as calculating the zbuffer value. linear interpolation across a triangle is completely equivilent to the weighted average barycentric approach and thus exactly the same as gouraud shading and the way it should be implimented. this isn't true for a quad for example. I can't see how doing that is gonna do anything for you. it just looks like a plane formula to me, are you suggesting computing barycentric coordinates explicitly? what exactly are you suggesting? if you're suggesting computing the barycentric coordiantes explicitly, well that's gonna take a long time lol. linear intrpolation(gouraud) is a incremental way to do the same thing, and is much quicker.

Tim

Share this post


Link to post
Share on other sites
well.. if you do gouraud like shading you will have to fight with errors..
the cause is lack of subpixel accuracy.
it is possible to make gouraud interpolation subpixel correct, but the cost is much larger than simple precalculation of interpolation coefficients.
so best way is..

1. solve simple set of equations like
z1=Ax1+By1+C
z2=Ax2+By2+C
z3=Ax3+By3+C

find A,B,C

scanconvert your triangle using any subpixel correct algorithm
and at beginning of each span find Z=Ax+By+C
and when moving to next pixel on the right calc Z=Z+A

if you are trying to make whole 3d pipeline in software you can do even better
and calculate A,B,C from vertex coordinates BEFORE homogenous clipping, so your clipping routine will only have to interpolate/clip 3d coordinates of triangle.
and A,B,C will be correct even if triangle is clipped to some N-gon.
also you can use it for interpolation textures and colors, they only need to be linear in screen space (so 1/Z instead of Z , hyperbolic textures .. )

Share this post


Link to post
Share on other sites
the function now looks like this:
int x0=50;
int y0=50;

int x1=600;
int y1=200;

int x2=300;
int y2=400;

float xleft=x0;
float xright=x0;

float dxleft = (float)abs(x2-x0)/(y2-y0);
float dxright = (float)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 = (float)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;
}

}


but the result is too slow for me so i should rewrite it using Bresenham's line algorithm. correct?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this