Omnimaga
Calculator Community => TI Calculators => Calculator C => Topic started by: blue_bear_94 on July 29, 2012, 09:12:42 pm
-
I was trying to implement flood filling with the right-hand algorithm (http://en.wikipedia.org/wiki/Flood_fill#Fixed_memory_method_.28right-hand_fill_method.29), but it don't seem to work. Here's the code specific to the flood filling:
typedef struct {
int x,y,dir;
} pt;
enum {LEFT,UP,RIGHT,DOWN};
#define DEF_DIR DOWN
#define PT_NULL (pt){-20,-20,0}
#define pteq(pt1,pt2) (pt1.x==pt2.x)&&(pt1.y==pt2.y)&&(pt1.dir==pt2.dir)
#define pteqc(pt1,pt2) (pt1.x==pt2.x)&&(pt1.y==pt2.y)
#define ptcolor(Pt) (Pt.x>=0&&Pt.x<whole_scn->xy.x1&&Pt.y>=0&&Pt.y<whole_scn->xy.y1)?GetGPix(Pt.x,Pt.y):mf
#define nextdir(Dir) (Dir+1)%4
#define prevdir(Dir) (Dir+3)%4
#define oppdir(Dir) (Dir+2)%4
int mf=3;
void FillPt(pt Pt,int col)
{
int w=whole_scn->xy.x1;
int h=whole_scn->xy.y1;
if (Pt.x>=0&&Pt.x<w&&Pt.y>=0&&Pt.y<h)
DrawGPix(Pt.x,Pt.y,col,GA_DRAW);
}
pt ptDir(pt Pt,int Dir)
{
switch (Dir)
{
case LEFT:
Pt.x--;
break;
case RIGHT:
Pt.x++;
break;
case UP:
Pt.y--;
break;
case DOWN:
Pt.y++;
break;
}
return Pt;
}
#define ptdir ptDir
pt inFront(pt Pt)
{
return ptDir(Pt,Pt.dir);
}
void FloodFill(short x,short y,short tcol, short rcol)
{
mf=rcol;
pt cur={x,y,DEF_DIR};
pt mark=PT_NULL;
pt mark2=PT_NULL;
//save marks
pt md=PT_NULL;
pt md2=PT_NULL;
int backtrack=0;
int findloop=0;
int count=0;
int temp;
//while front pixel is empty.........move forward
while (ptcolor(inFront(cur))==tcol) cur=inFront(cur);
goto START;
MAIN://MAIN LOOP!
cur=inFront(cur);//move forward
//if right pixel is empty
if (ptcolor(ptDir(cur,nextdir(cur.dir)))==tcol)
{
//if backtrack is true and findloop is false
//and either front pixel or left pixel is empty
//set findloop to true
if (backtrack && !findloop && ((ptcolor(inFront(cur))==tcol)||(ptcolor(ptDir(cur,prevdir(cur.dir)))==tcol))) findloop=1;
//turn right
cur.dir=nextdir(cur.dir);
PAINT:
//move forward
//FillPt(cur,rcol);
cur=inFront(cur);
}
START:
//set count to # of nondiagonally adjacent pixels filled
count=(ptcolor(inFront(cur))!=tcol)+(ptcolor(ptDir(cur,prevdir(cur.dir)))!=tcol)+(ptcolor(ptDir(cur,nextdir(cur.dir)))!=tcol)+(ptcolor(ptDir(cur,oppdir(cur.dir)))!=tcol);
if (count!=4)
{
do {
cur.dir=nextdir(cur.dir);//turn right
} while(ptcolor(inFront(cur))==tcol);//front pixel is empty
do {
cur.dir=prevdir(cur.dir);//turn left
} while(ptcolor(inFront(cur))!=tcol);//front pixel is filled
}
switch (count)
{
case 1:
if (backtrack) findloop=1;
else if (findloop)
{
//if mark is null........restore mark
if (pteq(mark,PT_NULL)) mark=md;
}
else if ((ptcolor(ptdir(inFront(cur),prevdir(cur.dir)))==tcol)&&(ptcolor(ptdir(ptdir(cur,oppdir(cur.dir)),prevdir(cur.dir)))==tcol))
{//front left pixel and back left pixel are both empty
md=mark;//save mark
mark=PT_NULL;//clear mark
cur.dir=prevdir(cur.dir);//turn left
FillPt(cur,rcol);//fill cur
goto PAINT;
}
break;
case 2:
//if back pixel is filled
if (ptcolor(ptdir(cur,oppdir(cur.dir)))!=tcol)
{
//if front left pixel is not filled
if (ptcolor(ptdir(inFront(cur),prevdir(cur.dir)))==tcol)
{
//save mark
md=mark;
//clear mark
mark=PT_NULL;
//turn around
cur.dir=oppdir(cur.dir);
//fill cur
FillPt(cur,rcol);
goto PAINT;
}
}
else if (pteq(mark,PT_NULL))//mark is not set
{
mark=cur;//set mark to cur
md2=mark2;
mark2=PT_NULL;//clear mark2
findloop=0;
backtrack=0;
}
else
{
if (pteq(mark2,PT_NULL))//if mark2 is not set
{
if (pteqc(cur,mark))//if cur is at mark
{
if (cur.dir==mark.dir)//if cur-dir==mark-dir
{
md=mark;
mark=PT_NULL;//clear mark
cur.dir=oppdir(mark.dir);//turn around
goto PAINT;
}
else
{
backtrack=1;
findloop=0;
cur.dir=mark.dir;
}
}
else if (findloop)
{
mark2=cur;//set mark2 to cur, set mark2-dir to cur-dir
}
}
else
{
if (pteqc(cur,mark))//if cur is at mark
{
cur=mark2;//set cur to mark2, set cur-dir to mark2-dir
md=mark;
md2=mark2;
mark=PT_NULL;
mark2=PT_NULL;//clear mark and mark2
backtrack=0;
cur.dir=oppdir(cur.dir);//turn around
FillPt(cur,rcol);//fill cur
goto PAINT;
}
else if (pteqc(cur,mark2))//if cur is at mark2
{
temp=mark.dir;//set mark to cur
mark=cur;
mark.dir=temp;
cur.dir=mark2.dir;//set cur-dir and mark-dir to
mark.dir=mark2.dir;//mark2-dir
md2=mark2;
mark2=PT_NULL;//clear mark2
}
}
}
break;
case 3:
md=mark;
mark=PT_NULL;//clear mark
cur.dir=prevdir(cur.dir);//fill cur
FillPt(cur,rcol);
goto PAINT;
break;
case 4:
FillPt(cur,rcol);//fill cur
return;//done
break;
}
goto MAIN;
}
#define Fill(x,y,col) FloodFill(x,y,GetGPix(x,y),col)Is there anything I did wrong? (The full source is attached.) Thanks for helping me.
-
What, exactly, "doesn't seem to work" ? IOW, how does it fail ? :)
-
It fills a few pixels then hangs; try it on TIEmu to see how (New>OK>Fill).
Edit: Binary.
Edit 2: Here is documentation for GetGPix and DrawGPix.
GetGPix(int x, int y) returns the color of the pixel at the point (x,y). 0 is white, and 3 is black.
SetGPix(int x, int y, int color, int attr) draws a pixel at the point (x,y) using the color specified. The attr argument means:
GA_DRAW: Replaces the color.
GA_ROTATE: Rotates the color.
GA_FLIP: Inverts. The color is disregarded in this drawing mode.
-
I came up with an alternate solution which is easier and still works on the TI-89 without running out of memory (on a 64x64, at least):
[attached]
Now if only I can figure out why the keyboard input sometimes screws up while using the pencil tool and can't be fixed even with a RAM clear... I think it has to do with not putting enough delay between the ticks.
(edit: yet another bug, reattaching)
(yet another edit: flood fill works even for an image the size of the TI-89 screen!)