--> [68k] Flood Fill --> -->

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

0 Members and 1 Guest are viewing this topic.

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
[68k] Flood Fill
« 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.
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: [68k] Flood Fill
« Reply #1 on: July 30, 2012, 12:55:44 pm »
What, exactly, "doesn't seem to work" ? IOW, how does it fail ? :)
« Last Edit: July 30, 2012, 12:55:59 pm by Lionel Debroux »
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: [68k] Flood Fill
« 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.
« Last Edit: August 07, 2012, 05:21:46 pm by blue_bear_94 »
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: [68k] Flood Fill
« 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!)
« Last Edit: August 23, 2012, 07:01:14 pm by blue_bear_94 »
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

 

\n\t\t\t\t\t\t\t\t\t
<' + '/div>\n\t\t\t\t\t\t\t\t\t