Bresenham My Friend

[Orion_]

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 ?

I hope so ...

 

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

[SebRmv]

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

[Orion_]

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

[Azrael]

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 or I have misunderstood the question... )

[SebRmv]

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

[Symmetry of TNG]

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

 

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