# Bresenham Line, Triangle Filling (2d help needed)

## Recommended Posts

Hi, I am currently using Bresenham's line algorithm to draw lines:
inline void drawline (unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, DWORD Color, DWORD* pData)
{
int dy = y1 - y0;
int dx = x1 - x0;
int stepx, stepy;

if (dy < 0)
{
dy = -dy;
stepy = -g_DeviceWidth;
}
else
stepy = g_DeviceWidth;
if (dx < 0)
{
dx = -dx;
stepx = -1;
}
else
stepx = 1;

dy <<= 1;
dx <<= 1;

y0 *= g_DeviceWidth;
y1 *= g_DeviceWidth;
pData[x0+y0] = Color;

if (dx > dy)
{
int fraction = dy - (dx >> 1);

while (x0 != x1)
{
if (fraction >= 0)
{
y0 += stepy;
fraction -= dx;
}
x0 += stepx;
fraction += dy;
pData[x0+y0] = Color;
}
}
else
{
int fraction = dx - (dy >> 1);

while (y0 != y1)
{
if (fraction >= 0)
{
x0 += stepx;
fraction -= dy;
}
y0 += stepy;
fraction += dx;
pData[x0+y0] = Color;
}
}
}


The problem is, I do not understand how the algorithm works. A conceptual explanation would help me out a lot. The function is quite fast in drawing lines, and what I want to do is draw triangles using the same algorithm, and maybe even quads. I know making a triangle or quad drawing function should not take many modifications of the core line drawing algorithm since everything is linearly processed. Some help regarding this 2d dilemma would be nice. I would like to get on to the fun 3d stuff ;O). 2d is necessary though. I am setting pixels with one large array btw. To give you an idea, here's my drawpixel function:
inline void drawpixel (unsigned int x, unsigned int y, DWORD Color, DWORD* pData)
{
pData [g_DeviceWidth * y + x] = Color;
}


Thanks a lot for any feedback.

##### Share on other sites
Wikipedia offers a nice concise explanation at http://en.wikipedia.org/wiki/Bresenham's_line_algorithm . If there are any parts of this explanation you find hard to understand, please yell :)

##### Share on other sites
Not using bresenham at all in favor of just filling horizontal lines is faster for a poly filler though.

##### Share on other sites
Quote:
 Original post by oggiallijust filling horizontal lines

...which uses Bresenham's algorithm to determine the extents of the scanlines.

##### Share on other sites
Yes, but still the final lines between the extents the bresenham on the triangle edges gives should be horizontal. True, the OP will still need to understand how Bresenham works, but I was barely commenting on his overall trifiller implementation ;)

##### Share on other sites
How much faster are integer operations compared to floating point operations on today's processors?

##### Share on other sites
To use Bresenham for triangle filling you do exactly what Sneftel says, trace the edges with Bresenham and draw the straight lines between them.

I remember doing this many years ago, and after a few seconds of digging I found an old tutorial I had written, which happens to discuss exactly what you are currently doing. I've uploaded it here if you're interested.

Re-reading it just now I noticed immediately that I did something very silly towards the end that made the algorithm a lot more complex than it needed to be, but I'll leave it to you, or someone else, to spot it (it's in the last paragraph). I can't believe I made it so hard for myself. [lol]

##### Share on other sites
Quote:
 Original post by BoderHow much faster are integer operations compared to floating point operations on today's processors?

Much faster. It doesn't matter if you're talking about processors ten years ago, today, or ten years from now (probably); FP operations are simply much more complicated than integer operations.

##### Share on other sites
Well, not actually universally true. Especially FP multiplication is nowadays a lot faster than integer multiplication.

In the question of drawing lines however, it is a lot faster to use fixed than FP math. This is because what's calculated, either in fixed or floating, is the coordinates to which to plot pixels to form the line. Then these coordinates are used to address memory to write the pixel value to. Memory addressing is done using integers. Now if we used integers for the coordinates too, assuming we weren't dumb, we can just use the coord values for the address. In the other hand if we used FP math, we would be screwed - we would have to convert the floating-point coords to integer addresses first. Now as everyone knows, "ftoi is dead slow". SSE and cvtss2si and cvtsd2si help this A LOT but it's still nothing needed to be done vs. a conversion.

Most of the speed benefit from filling only horizontal lines is from the fact that then you are writing linearly to memory and you don't have that nasty fraction cjump there for every pixel - which is sure to be a lot faster.

##### Share on other sites
Thanks a lot for all of the replies. I just got back from a quick 2-day trip so I will look through them all and perhaps give another post in a bit if I need any more help. I appreciate it.

##### Share on other sites
Thanks a lot for all of the replies. I just got back from a quick 2-day trip so I will look through them all and perhaps give another post in a bit if I need any more help. I appreciate it.

EDIT: Please ignore the above anonymous post. Oops.

## 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

• ### Forum Statistics

• Total Topics
627735
• Total Posts
2978851

• 10
• 10
• 21
• 14
• 12