Author Topic: [68k] Flood Fill (Read 4552 times)

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:

Code: [Select]

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.

Lionel Debroux · « **Reply #1 on:** July 30, 2012, 12:55:44 pm »

What, exactly, "doesn't seem to work" ? IOW, how does it fail ?

blue_bear_94 · « **Reply #2 on:** July 30, 2012, 01:45:32 pm »

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.

blue_bear_94 · « **Reply #3 on:** August 23, 2012, 06:48:55 pm »

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!)

Author Topic: [68k] Flood Fill (Read 4552 times)

blue_bear_94

[68k] Flood Fill

Lionel Debroux

Re: [68k] Flood Fill

blue_bear_94

Re: [68k] Flood Fill

blue_bear_94

Re: [68k] Flood Fill