GP2X Bresenham / Any Line Drawing

[TheMinder]

I have done a bit of searching to see if this has already been covered, but apart from some passing mentions i couldn't find anything (i am very tired and bleary eyed though so apologies if i missed it).

Even though i have other ideas that i could probably pressing on with, i've decided of late to have a look at the demo thread and not using SDL.

Last night i popped a simple bresenham line function into the demo framework, and it worked up to a point (only slopes of 1, but i realise why that is).

I'm just wondering if anyone has done any line drawing and if so have they got any nice quick optimised routines to share ?

(In the first instance i'm talking about normal aliased lines)

 

[YakumoFuji]

Iev only ever used non aliased breshenhams and normalised for when its on the horizontal or vertical. i use it for doing LOS/FOV in my roguelikes.

Im sure you could find a nice arm asm routine for a BL somewhere.

 

[Feeblez]

Here is a slow c version, probably not much help.

void brez_line256( int x1, int y1, int x2, int y2, dword colour, dword* pbuffer )
{
	int i;
	int dx, dy;
	int incx, incy;
	int xerr = 0, yerr = 0;
	int dist;

	dx = x2 - x1;
	dy = y2 - y1;
	if( dx > 0 )
		incx = 1;
	else
		incx = -1;
	if( dy > 0 )
		incy = 1;
	else
		incy = -1;
	dx = abs( dx );
	dy = abs( dy );

	if( dx > dy )
		dist = dx + 1;
	else
		dist = dy + 1;

	for( i = 0; i < dist; ++i )
	{
		pbuffer[ x1 + (y1 << 8) ] = colour;
		xerr += dx;
		if( xerr > dist )
		{
			x1 += incx * (xerr / dist);
			xerr %= dist;
		}
		yerr += dy;
		if( yerr > dist )
		{
			y1 += incy * (yerr / dist);
			yerr %= dist;
		}
	}
}

 

[TheMinder]

Thanks for the reply - i altered a few things in the one i was using and got it working.

The code is unoptimised but i managed to do something for the 2X that is under 3K (2640 bytes at the mo) which i'm happy with as a start.

It's a simple LINES type thing and although not very interesting, it is here for those with too much time on their hands

 

[Daid]

Here is a slow c version, probably not much help.

...

This looks faster to me:

//Bresenham's line algorithm
// Build from the pseudocode on wikipedia
#define Swap(X, Y) {Tmp = X; X = Y; Y = Tmp;}
void DrawLine(SDL_Surface* Surface, int X0, int Y0, int X1, int Y1, int Color)
{
  int Tmp;
  int Steep = abs(Y1 - Y0) > abs(X1 - X0);
  if (Steep)
  {
	Swap(X0, Y0);
	Swap(X1, Y1);
  }
  if (X0 > X1)
  {
	Swap(X0, X1);
	Swap(Y0, Y1);
  }
  int DeltaX = X1 - X0;
  int DeltaY = abs(Y1 - Y0);
  int Error = 0;
  int YStep;
  int Y = Y0;
  if (Y0 < Y1)
	YStep = 1;
  else
	YStep = -1;
  for(int X=X0; X<=X1;X++)
  {
	if (Steep)
	  PutPixel(Surface, Y,X, Color);
	else
	  PutPixel(Surface, X,Y, Color);
	Error += DeltaY;
	if (Error << 1 >= DeltaX)
	{
	  Y += YStep;
	  Error -= DeltaX;
	}
  }
}

 

[Feeblez]

Here is a slow c version, probably not much help.

...

This looks faster to me:

	if (Steep)
	  PutPixel(Surface, Y,X, Color);
	else
	  PutPixel(Surface, X,Y, Color);
	Error += DeltaY;
	if (Error << 1 >= DeltaX)
	{
	  Y += YStep;
	  Error -= DeltaX;
	}

Well PutPixel doesn't look very fast, but the algorithm scould be faster without the multiplies and divides.

There are a lot of ways you can unroll bresenam's, in your example you should move the if (Steep) out of the loop.

 

[YakumoFuji]

Ive added mine, ive replaced code chunks with a //put pixel comment

void line(int xr1, int xc1, int xr2, int xc2)
{
	Sint32 deltaRow, deltaCol;
	Sint32 stepRow, stepCol;
	Sint32 errorRow, errorCol;
	Sint32 detdelta;
	Sint32 count;

	int rr1, rr2, cc1, cc2;

	rr1 = xr1;
	rr2 = xr2;
	cc1 = xc1;
	cc2 = xc2;

	/* horizontal line */
	if(rr1 == rr2)
	{
		if(cc1 > cc2)
			stepCol = -1;
		else
			stepCol = 1;

		for(; cc1 != cc2; cc1 += stepCol)
		{
			// put_pixel
		}

		// put_pixel
		return;
	}


	/* vertical line */
	if(cc1 == cc2)
	{
		if(rr1 > rr2)
			stepRow = -1;
		else
			stepRow = 1;

		for(; rr1 != rr2; rr1 += stepRow)
		{
			// put_pixel
		}

		// put_pixel
		return;
	}


	// put_pixel

	stepCol = 1;
	deltaCol = cc2-cc1;
	if (deltaCol < 0)
	{
		stepCol = -1;
		deltaCol = -deltaCol;
	}

	stepRow = 1;
	deltaRow = rr2 - rr1;
	if (deltaRow < 0)
	{
		stepRow = -1;
		deltaRow = -deltaRow;
	}

	if(deltaCol > deltaRow)
	{
		count=deltaCol;
		detdelta=deltaCol;
		errorRow=deltaCol >> 1;
		errorCol=0;
	}
	else
	{
		count=deltaRow;
		detdelta=deltaRow;
		errorRow=0;
		errorCol=deltaRow >> 1;
	}

	do
	{
		errorCol=(errorCol+deltaCol);
		if(errorCol>=detdelta)
		{
			errorCol-=detdelta;
			cc1 += stepCol;
		}

		errorRow=(errorRow+deltaRow);
		if(errorRow>=detdelta)
		{
			errorRow-=detdelta;
			rr1 += stepRow;
		}

		// put_pixel

		count--;
	} while((Sint32)count>0);

	// put_pixel

	return;
}

*edit :: there is no bounds/clipping/error checking in here

 

[TheMinder]

I adapted (overstating the effort i put in!) this function for the demo-ette above:

void line_fast(int x1, int y1, int x2, int y2, byte color)
{
  int i,dx,dy,sdx,sdy,dxabs,dyabs,x,y,px,py;

  dx=x2-x1;	  /* the horizontal distance of the line */
  dy=y2-y1;	  /* the vertical distance of the line */
  dxabs=abs(dx);
  dyabs=abs(dy);
  sdx=sgn(dx);
  sdy=sgn(dy);
  x=dyabs>>1;
  y=dxabs>>1;
  px=x1;
  py=y1;

  VGA[(py<<8)+(py<<6)+px]=color;

  if (dxabs>=dyabs) /* the line is more horizontal than vertical */
  {
	for(i=0;i<dxabs;i++)
	{
	  y+=dyabs;
	  if (y>=dxabs)
	  {
		y-=dxabs;
		py+=sdy;
	  }
	  px+=sdx;
	  plot_pixel(px,py,color);
	}
  }
  else /* the line is more vertical than horizontal */
  {
	for(i=0;i<dyabs;i++)
	{
	  x+=dxabs;
	  if (x>=dyabs)
	  {
		x-=dyabs;
		px+=sdx;
	  }
	  py+=sdy;
	  plot_pixel(px,py,color);
	}
  }
}

 

[una-i]

About the putpixel speed issue I played arround a bit with TheMinder's routine to get rid of it. The idea is to convert sdx and sdy into pointer offsets instead of coordinate offsets.

btw, its not checked but I supouse it sould work...

void line_fast(int x1, int y1, int x2, int y2, byte color)
{
  int i,dx,dy,sdx,sdy,dxabs,dyabs,x,y,px,py;

  dx=x2-x1;	  /* the horizontal distance of the line */
  dy=y2-y1;	  /* the vertical distance of the line */
  dxabs=abs(dx);
  dyabs=abs(dy);
  sdx=sgn(dx);
  sdy=sgn(dy)*320;
  x=dyabs>>1;
  y=dxabs>>1;

  char* video = VGA[(y1<<8)+(y1<<6)+x1];
  *video = color;

  if (dxabs>=dyabs) /* the line is more horizontal than vertical */
  {
	for(i=0;i<dxabs;i++)
	{
	  y+=dyabs;
	  if (y>=dxabs)
	  {
		y-=dxabs;
		video += sdx;
	  }
	  video += sdx;
	  *video = color;
	}
  }
  else /* the line is more vertical than horizontal */
  {
	for(i=0;i<dyabs;i++)
	{
	  x+=dxabs;
	  if (x>=dyabs)
	  {
		x-=dyabs;
		video += sdx;
	  }
	  video += sdy;
	  *video = color;
	}
  }
}

 

[YakumoFuji]

can you access the gp2x's framebuffer using a char* ? I thought the framebuffer was 16bit internally?

 

[paeryn]

can you access the gp2x's framebuffer using a char* ? I thought the framebuffer was 16bit internally?

You can put the display into 8-bit mode if you want (or 4-bit or even 24-bit). The frame buffer is standard memory - the only limits are what ARM4 imposes and that is generally that 16-bit accesses have to be on even addresses and 32-bit accesses on multiples of 4.
The hardware registers on the other hand have to all be 16-bit (apart from the blitter's which are all 32-bit)

 

[pea]

Hi guys,

Sounds like you are doing ok.

I have some bresenham based line drawing code with antialiasing and clipping. It uses my own graphics canvas objects and alpha look up table as it is part of my peaSDK, but it may be of use?

 

[una-i]

can you access the gp2x's framebuffer using a char* ? I thought the framebuffer was 16bit internally?

I just modified the previous version that used char, I didnt assume any platform, I just wanted to show de idas of modifing the algorith so it uses pointers to avoit the putpixel call.


Unai.

 

[Lazrhog]

What you want is Dzz's nice wuline algorithm from Vektar ! I am assuming wuline obviously .... he may have based it on something else ....

come on Dzz - release the source for the line algo you used - it's lovely and its fast

 

[TheMinder]

Just because I'm getting more interested in this side of things where people do it "small" and ultimately make a demo perhaps, here's a few more.

Very arbitrary this ie done by eye but here's circle routines, filled and empty, that sort of run at the same speed (sort of - ish - very probably not). The code is completely unoptimised (saving that fun for later learning), and the fill routine is full lines (ie not half-line symmetry type of approach).

Empty Circles - this displays 1500 circles at a time of random radius <40 pixels (3244 bytes)

Filled Circles - this displays 300 circles at a time of random radius <40 pixels (3236 bytes)

I would be interested to see the same thing done in (pure) asm just out of curiousity, and maybe i'll learn how to do that myself and repost.

[PS i know this all isn't of much interest, general or otherwise, but that's what you get on open forums ]