Archived

This topic is now archived and is closed to further replies.

SMurf7

Drawing a line in steps

Recommended Posts

Hi, I''m trying to draw a line 1 pixel per game cycle, using a modified Bresenham algorithm (very loosely penned ). The problem is, the resultant line will only draw in 45-degree angles. My code is thus:-
  
void CMissile::Create(int x, int y, int xd, int yd)
{
	xpos = origx = x;
	ypos = origy = y;
	pos = x + y*iPitch;
	dx = xd - x;
	dy = yd - y;
	if (dx>=0)
	{
		x_inc = 1;
	} // end if line is moving right

	else
	{
		x_inc = -1;
		dx = -dx;  // need absolute value

	} // end else moving left


	if (dy>=0)
	{
		y_inc = iPitch;
	} // end if line is moving down

	else
	{
		y_inc = -iPitch;
		dy = -dy;  // need absolute value

	} // end else moving up


	// compute (dx,dy) * 2

	dx2 = dx << 1;
	dy2 = dy << 1;
	active = true;
}

void CMissile::Move(void)
{
	if (active)
	{
		// now based on which delta is greater we can draw the line

		if (dx > dy)
		{
			// initialize error term

			error = dy2 - dx;

			// test if error has overflowed

			if (error >= 0) 
			{
				error-=dx2;

				// move to next line

				pos+=y_inc;
			} // end if error overflowed


			// adjust the error term

			error+=dy2;

			// move to the next pixel

			pos+=x_inc;
		} // end if |slope| <= 1

		else
		{
			// initialize error term

			error = dx2 - dy; 

			// test if error overflowed

			if (error >= 0)
			{
				error-=dy2;

				// move to next line

				pos+=x_inc;
			} // end if error overflowed


			// adjust the error term

			error+=dx2;

			// move to the next pixel

			pos+=y_inc;
		} // end else |slope| > 1

		xpos = pos % iPitch;
		ypos = (pos - xpos) / iPitch;
		Draw_Line(origx, origy, xpos, ypos, 4, buffer, iPitch);
	}
}
  
Essentially, the xpos and ypos values should be updated with the location of the next pixel, and a line is drawn from the original coordinates (origx, origy) to it. The move code is called every game cycle. Any ideas?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

You are drawing at 45 degree angles because you can only have 8 possibilities for dx and dy:



dx | dy
-1 | -1
-1 | 0
-1 | +1
0 | -1
0 | +1
+1 | -1
+1 | 0
+1 | +1



There is no provision for fractional dx or dy.

May I suggest an alternate method?

Since you are drawing the line one pixel per frame, you could do it like so, using fixed point numbers.

  

// x0, y0 is missile origin, xf, yf is missile target

void Missile::create(int x0, int y0, int xf, xf)
{
int len = sqrt((xf-x0)*(xf-x0)+(yf-y0)*(yf-y0));

dx = ((xf-x0)<<16)/len; // fixed point representation

dy = ((yf-y0)<<16)/len; // fixed point representation


xpos = x0<<16; // fixed point

ypos = y0<<16; // fixed point

}

void Missile::move(void)
{
if(active)
{
xpos += dx;
ypos += dy;

Draw_Line(x0, y0, xpos>>16, ypos>>16, 4, buffer, iPitch);
}
}



This seems much easier to me.

Share this post


Link to post
Share on other sites
AP - um.. no. What you cited is standard DDA and there are plenty of problems with it (besides the fact that it's slow as hell, it also leaves gaps between pixels). Try to read the code before replying. Also, your code involves a call to Draw_Line() or whatever, which is exactly what he's trying to code.

SMurf7 - You're not updating your dx/dy, so the error term is always exactly the same.

-goltrpoat


--
Float like a butterfly, bite like a crocodile.



Edited by - goltrpoat on August 3, 2001 6:47:05 PM

Share this post


Link to post
Share on other sites
Hmm, what I had essentially done was take the original Bresenham algorithm (in Andre LaMothe format):-
  
int Draw_Line(int x0, int y0, // starting position

int x1, int y1, // ending position

UCHAR color, // color index

UCHAR *vb_start, int lpitch) // video buffer and memory pitch

{
// this function draws a line from xo,yo to x1,y1 using differential error

// terms (based on Bresenahams work)


int dx, // difference in x''s

dy, // difference in y''s

dx2, // dx,dy * 2

dy2,
x_inc, // amount in pixel space to move during drawing

y_inc, // amount in pixel space to move during drawing

error, // the discriminant i.e. error i.e. decision variable

index; // used for looping


// pre-compute first pixel address in video buffer

vb_start = vb_start + x0 + y0*lpitch;

// compute horizontal and vertical deltas

dx = x1-x0;
dy = y1-y0;

// test which direction the line is going in i.e. slope angle

if (dx>=0)
{
x_inc = 1;
} // end if line is moving right

else
{
x_inc = -1;
dx = -dx; // need absolute value

} // end else moving left


// test y component of slope


if (dy>=0)
{
y_inc = lpitch;
} // end if line is moving down

else
{
y_inc = -lpitch;
dy = -dy; // need absolute value

} // end else moving up


// compute (dx,dy) * 2

dx2 = dx << 1;
dy2 = dy << 1;

// now based on which delta is greater we can draw the line

if (dx > dy)
{
// initialize error term

error = dy2 - dx;

// draw the line

for (index=0; index <= dx; index++)
{
// set the pixel

*vb_start = color;

// test if error has overflowed

if (error >= 0)
{
error-=dx2;

// move to next line

vb_start+=y_inc;
} // end if error overflowed


// adjust the error term

error+=dy2;

// move to the next pixel

vb_start+=x_inc;
} // end for


} // end if |slope| <= 1

else
{
// initialize error term

error = dx2 - dy;

// draw the line

for (index=0; index <= dy; index++)
{
// set the pixel

*vb_start = color;

// test if error overflowed

if (error >= 0)
{
error-=dy2;

// move to next line

vb_start+=x_inc;
} // end if error overflowed


// adjust the error term

error+=dx2;

// move to the next pixel

vb_start+=y_inc;
} // end for


} // end else |slope| > 1


// return success

return(1);
} // end Draw_Line



And I put all of the non-looped stuff in the Create code, all of the looped stuff (where the entire line is drawn) in the Move code and replaced the buffer pointer with a long (pos). It doesn''t appear that the error term is updated in any way different to how I''m doing it...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

Standard DDA? Ok, if you say so. I just came up with that off the top of my head, I didn''t know it was a some standard line drawing technique.

I can see how the missile creation function is slow (due to the sqrt and two divides) but I assume missiles will not be created every frame, probably once every few hundred frames, so I think it is negligible.

As for missing pixels, OK, maybe it would if we were using it to draw a line, but he is drawing a line from the missile origin to the new missile position, so as long as Draw_Line() is a good line drawing algo, this is also not a problem.

Also, please explain to me how two adds and two shifts (my method) are slower than at least two "if" tests, two comparisons, four additions, a modulus operation, and a divide (his method).


Share this post


Link to post
Share on other sites
Your method is 2 adds, 2 shifts and one multiply (to get the screen buffer address, he doesn''t need the extra multiply since he calculates the screen buffer address implicitely). His method *should be* 2 two conditional near branches and 4 adds. I didn''t say his code was optimized .


-goltrpoat


--
Float like a butterfly, bite like a crocodile.

Share this post


Link to post
Share on other sites