Jump to content

Bresenham My Friend


Orion_

Recommended Posts

ok, I'm not really good for doing math/algo stuff, so I will try to explain my problem here

(in english, so prepare for confusing explanation Oo)

 

I understand how work bresenham line drawing algorithm, but my problem is when you try to apply this algorithm to triangle filling algorithm.

the basic implementation of triangle filling is to increment Y each step and fill from x1 to x2

using bresenham with a Y delta larger than a X delta is ok because Y will be incremented each step.

now my problem is when X delta is larger than the Y delta, because, to know the next X position at the next Y step we must do some kind of loop to compute the X (and doing that for each segment of the triangle depending on deltas ...)

does anyone get the idea ? :D

I hope so ...

 

so, do we must compute the X like that .. (quite boring to code :/) or is there another algorithm/tips ?

Link to comment
Share on other sites

I don't really understand your question

 

For polygon filling, I am not sure Bresenham is the right algorithm to use.

(and by the way, I am really surprised by your question since you have already coded a polygon filler but anyway...)

 

Let say you want to fill the triangle A(xa,ya) B(xb,yb) C(xc,yc)

and let say that A is the upper point and that AB is the left side, AC is the right side

 

You keep for one line two variables xleft and xright

and you start filling at line ya

 

until you reach yb or yc

you enter a loop

xleft = xleft + xincleft

xright = xright + xincright

and you fill from xleft to xright

 

then to finish the drawing you recompute xincleft and xincright and then continue to fill until the other point

 

for the first part of the triangle, you have

xincleft = (xb-xa)/(yb-ya)

and xincright = (xc-xa)/(yc-ya)

 

hope this helps (at least, that's the spirit)

 

Seb

Link to comment
Share on other sites

I'm already using this algorithm, but I have "holes" between 2 triangles sometimes, and I think this is because of the imprecision of the increment (24.8 or 16.16 give the same result ...)

so I thought that using bresenham I would have more accurate results :)

Link to comment
Share on other sites

If you really want to use Bresenham with a DeltaX greater than DeltaY you can "outer" the display of the point at each change of Y. But it means that you will pass through all the points of the line, but only diplaying those at the extremities of each horizontal segment.

 

(hopoe it was clear :lol: or I have misunderstood the question... :blink: )

Link to comment
Share on other sites

I'm already using this algorithm, but I have "holes" between 2 triangles sometimes, and I think this is because of the imprecision of the increment (24.8 or 16.16 give the same result ...)

so I thought that using bresenham I would have more accurate results :)

 

ok, I understand better then :)

I guess it is a problem of subpixel accuracy (google is your friend)

I think you should consider all the coordinates to be 16.16 values

Link to comment
Share on other sites

Hmm a 3D related question out in the open.?.. ok fine by me :P

 

One can debate forever if it is worth the HOLE lot of extra trouble it is to get pixel perfect polys and compare that to the extra polycount or framerate you get if you just accept some dropouts..

But i guess for a racing game it doesnt matter that much, but for a "Tomb raider" it might.

(cf Ps1).

 

So.. Bresenham.. when i sat down with it and did some comparisons if a line goes from upper right to down left in a polygon, the polygon that gets below it, its rout will fill over large portions of the already drawn upper poly!... ?... for flat polys this might not matter much, you will never get dropouts for sure, but for example if you use textures, you will loose allot of textures from upper poly when the lower one paints them over.

 

What you need is a "Fill convention" ...you need to descide to have, for example, a "top-left" fill convention, where you "round up" your scanline startingposition on the top & left side of your poly, and round down on bottom& right.

 

check out Chris Heckers article on Perspective Texturemapping at

http://www.d6.com/users/checker/misctech.htm

 

 

Havent realy checked my old rout with a lupe, but i think it looks rather ok (?) ..16.16 math it fits the blitter nicely (with its fractional pixelstart positions). it will automatically deside if the blitter should draw the pixel or not and handle the fraction->screen-integer-pixel-position truncation for you.

 

Perhapps there is an easier way to do this altogether, if someone knows please let me know =)

 

cheers

/Sym

Link to comment
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
×
×
  • Create New...