Jump to content
• ### What is your GameDev Story?

• Advertisement

# Critical analysis of my line algorithm

This topic is 4583 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

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

##### Share on other sites

• Advertisement
• Advertisement
• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• ### Popular Now

• 27
• 16
• 10
• 10
• 11
• Advertisement
• ### Forum Statistics

• Total Topics
634098
• Total Posts
3015525
×

## Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!