Sign in to follow this  

Bresenham Line, Triangle Filling (2d help needed)

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by oggialli
just filling horizontal lines

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Boder
How 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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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

Sign in to follow this