[68k] Flood Fill
(1/1)
blue_bear_94:
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 All | Copy To Clipboard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

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)

clip = new ZeroClipboard.Client();clip.setHandCursor( true );clip.glue("a-1");clip.setText(StripHTML("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:
What, exactly, "doesn't seem to work" ? IOW, how does it fail ? :)
blue_bear_94:
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:
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!)
Navigation
Message Index