Jump to content
  • Advertisement
Sign in to follow this  
dawidjoubert

Critical analysis of my line algorithm

This topic is 4401 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, this is my first attempt at writing a Robust line rendering algorithm using purely screen blits. Please criticize it and remember i appreciate speed/performace critics most. I can post the horiz/verticl line functions if you want, I understand for best performance i should actually include them in the same function?
// This is a modified put line version but the idea here is to use algebra to first
// simplify the line such as clipping it and setting it up from the right side
void putLine(int x1,int y1,int x2,int y2,int color)
{
	int t;
	// First make sure that x1 < x2
	if (x1 > x2) 
	{
		// Standard lame swapping!
		t = x2;
		x2 = x1;
		x1 = t;
		t=y2;
		y2=y1;
		y1=t;
	}

	// Early out total occlusion
	if ((x1 >= g_iWidth) || (x2 < 0)) return;	// Since x1 < x2 if x1 > widht or x2 < 0 then the entire line is offscreen
	if (	(
				(y1 <= y2) && ((y1 >= g_iHeight) || (y2 < 0))
			)  
			||  // Else
			(
				(y2 <= y1) && ((y2 >= g_iHeight) || (y1 < 0))
			)) return;



	// Find change in X and change in Y
	int deltaX = x2-x1;
	int deltaY = y2-y1;

	// Catch devision by zero problems and replace them with horiz/vertical lines
	if (deltaY == 0)
	{
		// Clip x and y
		if (x1 < 0) x1 = 0;
		if (x2 >= g_iWidth) x2 = g_iWidth-1;
		putHorizLine_nochk(x1,x2,y1,color);
		return;
	}
	if (deltaX == 0)
	{
		if (y1 > y2)
		{
			if (y1 >= g_iHeight) y1 = g_iHeight-1;
			if (y2 < 0) y2 = 0;
			putVerticLine_nochk(y2,y1,x1,color);
		}
		else if (y1 < y2)
		{
			if (y2 >= g_iHeight) y2 = g_iHeight-1;
			if (y1 < 0) y1 = 0;
			putVerticLine_nochk(y1,y2,x1,color);
		}
		return;
	}

	// The line equation is y = mx+c or
	// y = m1/m2 *x + c, now multiply m2 out
	// m2y = m1x + m2c
	// c = (m2y - m1x) / m2c
	// m1 = dy and m2 = dx

	// Find the C-Cut
	int cTimesDeltaX = (deltaX * y1 - deltaY * x1);
	//int c = (deltaX * y1 - deltaY * x1)/deltaX;

	// CLIP the line using the two x axeses
	int sx = x1;
	int ex = x2;
	if (sx < 0) sx = 0;
	if (ex >= g_iWidth) ex = g_iWidth-1;
	// Now we must find the corrosponding y values
	// y = mx+c	  = X*deltaY/DeltaX + c = (deltaY * X + c * DeltaX) / DeltaX
	int sy = (deltaY * sx + cTimesDeltaX)/deltaX;
	int ey = (deltaY * ex + cTimesDeltaX)/deltaX;
	

	// CLIP the line using the y axeses
	if (sy < ey)
	{
		if (sy < 0) sy = 0;
			else if (sy >= g_iHeight) return;
		if (ey >= g_iHeight) ey = g_iHeight-1;
			else if (ey < 0) return;
		}
	else
	{
		if (ey < 0) ey = 0;
			else if (ey >= g_iHeight) return;
		if (sy >= g_iHeight) sy = g_iHeight-1;
			else if (sy < 0) return;
	}

	// Now find corrosponding x values
	//x = (y - c)/m
	sx = (sy*deltaX - cTimesDeltaX)/deltaY;
	ex = (ey*deltaX - cTimesDeltaX)/deltaY;

	// Once again do a standard swap, checking that x1 < x2
	if (sx > ex)
	{
		t = sx;
		sx = ex;
		ex = t;
		t = sy;
		sy = ey;
		ey = t;
	}


	// DEBUGGING
	assert((sx >= 0) && (ex < g_iWidth) && (sy >= 0) && (sy < g_iHeight) && (ey >= 0) && (ey < g_iHeight) && (sx < g_iWidth) && (ex >= 0));
	assert(x1 < x2);	// Make Sure x1 is always smaller than x2

	// GREAT OUR LINE IS NOW CLIPPED
	int error = 0;
	deltaX = abs(deltaX);
	deltaY = abs(deltaY);
	if (deltaX <= deltaY)
	{
		// Steep, gradient is > 1
		int di2;
		// Find the direction of the y, increasing or decreasing
		if (sy > ey) 
		{
			di2 = -1;
		deltaY = abs(deltaY);1;
		}
		else 
		{
			di2= +1;
		}

		for (int y=sy;y != ey;y += di2) // Loop through Y Values
		{
			assert((y < g_iHeight) && (y >= 0));
			g_puiScreen[y * g_iScreenMultiple+sx] = color;

			error+= deltaX;
			if ((error << 1) >= deltaY)
			{
				error -= deltaY;
				sx++;  // Increase the X Offset
			}
		}
	}
	else
	{
		int di;
		// Solve the direction y is going (up or down)
		if (sy > ey)di = -g_iScreenMultiple;
		else di = +g_iScreenMultiple;

		unsigned int start=(sy * g_iScreenMultiple);	// Find our starting position for rendering

		for (unsigned int x=sx;x != ex;x++) // Loop through X Values
		{
			g_puiScreen[start + x] = color;
			error+= deltaY;
			if ((error << 1) >= deltaX)
			{
				error -= deltaX;
				start+=di;
			}
		}
	}
};


CREDIT GOES TO ORIGINAL PIONEER OF THIS INTEGER METHOD OF RENDERING:http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Share this post


Link to post
Share on other sites
Advertisement
One thing I would do at the begging to find your smaller X value.


//I would rename the input x values
void putLine(int inputx1,int y1,int inputx2,int y2,int color)
{

// First make sure that x1 < x2
int x1, x2; //this is where x1 and x2 are defined

if (inputx1 > inputx2)
{
x1 = inputx2;
x2 = inputx1;
}
else
{
x1 = inputx1;
x2 = inputx2;
}

//rest of your code...


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!