#6832 - Psyk - Tue Jun 03, 2003 9:30 am
I know there is a very simple algorithm for drawing a straight line in any direction in C but i just cant remember what it is! Could someone point me in the right direction plz?
#6833 - joet - Tue Jun 03, 2003 9:49 am
Do a quick Google search for Bresenham ...
#6834 - Quirky - Tue Jun 03, 2003 10:07 am
staring monkey's demo library from the main gbadev page has an implementation of Bresenham in there too, IIRC.
#6837 - Psyk - Tue Jun 03, 2003 10:09 am
arg! I cant find anything simple enough for my puny mind! I'll try looking in some source codes, im bound to find it in there somewhere.
#6839 - pbmtp - Tue Jun 03, 2003 10:29 am
Code: |
#define ClipMinX 0
#define ClipMaxX 240
#define ClipMinY 0
#define ClipMaxY 160
static void BresenhamLine(int x1,int y1,int x2,int y2,uchar color)
{
int i;
int x,y;
int IncX,IncY;
int Dx,Dy;
int Err;
int inc1,inc2;
int offset;
if(x1<ClipMinX && x2<ClipMinX) return;
if(y1<ClipMinY && y2<ClipMinY) return;
x=x1;
y=y1;
if(x1<=x2)
{
IncX=1;
Dx=x2-x1;
}
else
{
IncX=-1;
Dx=x1-x2;
}
if(y1<=y2)
{
IncY=1;
Dy=y2-y1;
}
else
{
IncY=-1;
Dy=y1-y2;
}
if(Dy<Dx)
{
inc1=(Dy-Dx)<<1;
inc2=Dy<<1;
Err=inc2-Dx;
offset=GBA_SCREEN_WIDTH*y+x;
for(i=0;i<Dx;i++)
{
if(x>ClipMinX && x<ClipMaxX && y>ClipMinY && y<ClipMaxY)
Video[offset]=color;
if(Err>0)
{
y+=IncY;
offset+=IncY*GBA_SCREEN_WIDTH;
Err+=inc1;
}
else
Err+=inc2;
x+=IncX;
offset+=IncX;
}
}else
{
inc1=(Dx-Dy)<<1;
inc2=Dx<<1;
Err=inc2-Dy;
offset=GBA_SCREEN_WIDTH*y+x;
for(i=0;i<Dy;i++)
{
if(x>ClipMinX && x<ClipMaxX && y>ClipMinY && y<ClipMaxY)
Video[offset]=color;
if(Err>0)
{
x+=IncX;
offset+=IncX;
Err+=inc1;
}
else
Err+=inc2;
y+=IncY;
offset+=IncY*GBA_SCREEN_WIDTH;
}
}
}
|
Hope it will help
[/code]
#6843 - Psyk - Tue Jun 03, 2003 12:19 pm
that will do nicely
thanks
#6917 - hnager - Wed Jun 04, 2003 3:01 pm
Would that work in MODE 4?
this is what I have:
void BLine(int x0, int y0, int x1, int y1, unsigned char color){
int dx, dy, x_inc, y_inc, error=0, index, x, y;
u16* vidMem;
x = x0;
y = y0;
dx = x1-x0;
dy = y1-y0;
if (dx>0){
x_inc = 1;
}else{
x_inc = -1;
dx = -dx;
}
if (dy>0){
y_inc = 1;
}else{
y_inc = -1;
dy = -dy;
}
if(dx>dy){
for(index=0; index<=dx; index++){
vidMem = &VideoBuffer[ ((y*240) + x)>>1 ];
if(x % 2)
*vidMem = (*vidMem & 0x00FF) | (color<<8);
else
*vidMem = (*vidMem & 0xFF00) | color;
error+=dy;
if(error>dx){
error-=dx;
y+=y_inc;
}
x+=x_inc;
}
} else {
for(index=0; index <=dy; index++){
vidMem = &VideoBuffer[ ((y*240) + x)>>1 ];
if(x % 2)
*vidMem = (*vidMem & 0x00FF) | (color<<8);
else
*vidMem = (*vidMem & 0xFF00) | color;
error+=dx;
if(error>0){
error -= dy;
x+=x_inc;
}
y+=y_inc;
}
}
}
#6939 - philip - Wed Jun 04, 2003 8:06 pm
There's probably room for a little optimisation in Mode 4. When dx>dy, you will sometimes get consecutive pixels on the same scanline. If the first is EVEN and the second is ODD, then these can be drawn in a single operation without wasting time reading the screen memory to retain a pixel we're about to change anyway. So:
Code: |
if thispixel is EVEN
record Y ordinate in lastpixel.Y
else //Pixel ODD
if thispixel.Y=lastpixel.Y
THEN
Write both pixels with one operation :-)
ELSE
Write both separately :-(
|
This is ONLY possible when dx>dy. It becomes more efficient the closer the line is to being flat, because more double pixels exist. When we have pairs of pixels like this, we write them both with just a single memory write, rather than the simplest method which would do two reads and two writes to achive the same effect.
I'm assuming drawing the line from left to right here (in a pixel pair, even pixel will be encountered first), so take into account possibility of going the other way. Personally, I'd just swap the start and end points to ensure drawing in that direction. I THINK these checks are quicker than all the memory access to screen space, because you can store lastpixel.Y in a register and compare it quickly, whereas with single pixel writes, you're guaranteed to have to do nasty bitmasking and memory accessing. Or am I wrong?