#### Archived

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

# Drawing a line in steps

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

## 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 on other sites

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 targetvoid 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 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 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 on other sites

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