Orion_ 1 Report post Posted February 6, 2007 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 ? Quote Share this post Link to post Share on other sites
SebRmv 2 Report post Posted February 6, 2007 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 Quote Share this post Link to post Share on other sites
Orion_ 1 Report post Posted February 6, 2007 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 Quote Share this post Link to post Share on other sites
Azrael 0 Report post Posted February 6, 2007 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... ) Quote Share this post Link to post Share on other sites
SebRmv 2 Report post Posted February 6, 2007 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 Quote Share this post Link to post Share on other sites
Symmetry of TNG 0 Report post Posted February 10, 2007 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 Quote Share this post Link to post Share on other sites