# Software filled triangles to have the same edges as outlined triangles

This topic is 3077 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm attempting to knock together some code to fill triangles in software. I'd like these filled triangles to have the exactly the same boundary as they would if lines are drawn between the three vertices using Bresenham's line drawing algorithm.

My current code steps through each Y coordinate and traces the edges of the triangle from top to bottom using Bresenham's line algorithm. This works very nicely on steep-sided triangles. This does not, however, work for shallow-sided triangles. I hope this image illustrates my problem:

The blue line shows the edge of the triangle traced by Bresenham's line drawing algorithm. The white dots show my calculated X coordinates. Where there are multiple X coordinates on the line per Y coordinate I'd need to be able to calculate the minimum X coordinate for that Y coordinate (if the edge I was tracing was on the left of the triangle) or the maximum coordinate for the Y coordinate (if the edge I was tracing was on the right of the triangle).

The green circle shows that this simple implementation is occasionally wrong, too; that white dot is one pixel too far left (it lines up with the blue line segment above it when it should have a black pixel above it).

In the past I've set aside a buffer in memory that stores the minimum and maximum X coordinate for each Y coordinate and trace the line "normally" (either stepping in X or stepping in Y depending on whether the line is steep or shallow). This works relatively well in practice but does not seem efficient and I do not have the free RAM on the current hardware to store such a buffer. As far as I can see I am limited to always stepping through Y from top to bottom.

Does anyone have any hints they may offer? I've tried a range of different fudge factors on the original error calculation and offsetting X before tracing the edge but all solutions have been ever so slightly "off" (the occasional incorrect pixel).

##### Share on other sites
So are you saying that using the Bresenham line drawing algorithm you get correct results where as "my calculated X coordinates" are wrong ?

Then you're not calculating the X coordinates in the same way that Bresenham does.

I don't quite understand...

##### Share on other sites

I guess you do something like this (though I may have made a mistake, didn't test it):
int (x0, y0, x1, y1) = ... ;int e = 0;int yd = y1 - y0;int xd = x1 - x0;for(int x=x0,y=y0;x<=x1;++x) {	pixel(x, y);		e += yd;	if(e > xd) {		e -= xd;		++y;	}}

So if you want to know how much to increase X when Y increases by one instead (again untested, but should definitely be determinable with something like this):
int (x0, y0, x1, y1) = ... ;int e = 0;int yd = y1 - y0;int xd = x1 - x0;for(int y=y0,x=x0;y<=y1;++y) {	pixel(x, y);		++y;	e += xd;	x += (e / yd);	e %= yd;}

##### Share on other sites
Quote:
 Original post by GregMichaelThen you're not calculating the X coordinates in the same way that Bresenham does.
That's the problem, I believe. Bresenham's line drawing algorithm steps along the longest axis of the line; for steep lines it will step along the Y axis, for shallow lines it will step along the X axis. As I am filling a triangle from the top down I am always stepping along the Y axis. This produces correct results for steep sides of triangles, incorrect results for shallow sides. Something has been lost in my translation from one type to another.
Quote:
 Original post by Erik RufeltI guess you do something like this (though I may have made a mistake, didn't test it):
Pretty much, just with a while < 0 instead of an if < 0 check:

private void BresenhamYOnly(int x0, int y0, int x1, int y1) {            // Ensure Y0<=Y1.    if (y0 > y1) {        int s;        s = x0; x0 = x1; x1 = s;        s = y0; y0 = y1; y1 = s;    }    int deltay = y1 - y0;    int deltax = x1 - x0;    int xstep;    if (deltax < 0) {        deltax = -deltax;        xstep = -1;    } else {        xstep = +1;    }    bool steep = deltay > deltax;    int error;    if (steep) {        error = deltay / 2;    } else {        error = deltax / 2;    }    // Prevent infinite loops.    if (deltay == 0) deltay = deltax;    for (int x = x0, y = y0; y <= y1; y++) {        if (x >= 0 && y >= 0 && x < renderWidth && y < renderHeight) {            this.renderSurface.SetPixel(x, y, Color.White);        }                        error -= deltax;        while (error < 0) {            error += deltay;            x += xstep;        }    }}

Quote:
 So if you want to know how much to increase X when Y increases by one instead (again untested, but should definitely be determinable with something like this):

Very interesting, that appears to produce much more reliable results (I haven't tested it very thoroughly yet but it's given me something to think about). [smile] Cheers!

##### Share on other sites
Two things, though quite obvious:

1 -- most cononical triangle fillers and line-drawers start "virtually" in the center of the source and target pixel on each edge or line, often with hidden fractional precision, fixed-point bits and/or by pre-stepping the algorithm. You may be doing this in one and not the other, or you may but one may differ from the other.

2 -- obviously the edges are not being calculated the same way. In my system I use the same algorithm for all such interpolations -- lines, edges and even color component interpolation. I factored the algorithm out into a template class so I can specify the number of fractional precision bits in the fixed-point math that's used internally, so all the usual constants and expressions get folded together when optimized, all the stepping functions are small and inline easily. I'm not sure if the "jump-to-step-N" function inlines, it's probably small enough that it does, but it's used rarely enough (and outside of loops, typically) that it doesn't matter.

##### Share on other sites
Thanks for your assistance! I think I've figured it out. My routine for tracing the edges of the triangles always starts from the higher vertex and works down to the lower one. However, my code for plotting lines starts with the higher vertex for steep lines but the leftmost vertex for shallow lines. This means that some lines may end up being drawn bottom to top, and the very slight differences this incurs means that one or two pixels along the line may be plotted incorrectly. I just need to force my line plotting routine to always draw from top to bottom and all should be resolved.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633728
• Total Posts
3013575
×