| blob | b8d1bb480cf40289294e0d180443a8cac203b19c |
1 ; Patterned Flood Fill
2 ; Alvin Albrecht 2002
3 ;
4 ;
5 ; This subroutine does a byte-at-a-time breadth-first patterned flood fill.
6 ; It works by allocating a circular queue on the stack, with the size of the
7 ; queue determined by an input parameter. The queue is divided into three
8 ; contiguous blocks: the pattern block, the investigate block and the new block.
9 ; The queue contains 3-byte structures (described below) with a special structure
10 ; delimiting each block. The physical end of the queue is marked with a special
11 ; byte. The contents of the queue grow down in memory.
12 ;
13 ; The pattern block holds pixels that have been blackened on screen and are
14 ; only waiting to have the pattern applied to them before they are removed
15 ; from the queue.
16 ;
17 ; The investigate block holds pixels that have been blackened on screen and
18 ; are waiting to be investigated before they become part of the pattern
19 ; block. 'Investigating' a pixel means trying to expand the fill in all
20 ; four directions. Any successful expansion causes the new pixel to be
21 ; added to the new block.
22 ;
23 ; The new block holds pixels that have been blackened on screen and are
24 ; waiting to become part of the investigate block. The new block expands
25 ; as the investigate block is investigated.
26 ;
27 ; The pattern fill algorithm follows these steps:
28 ; 1. Examine the investigate block. Add new pixels to the new block if an
29 ; expansion is possible.
30 ; 2. Pattern the pattern block. All pixels waiting to be patterned are
31 ; patterned on screen.
32 ; 3. The investigate block becomes the pattern block.
33 ; The new block becomes the investigate block.
34 ; 4. Repeat until the investigate block is empty.
35 ;
36 ; The algorithm may bail out prematurely if the queue fills up. Bailing
37 ; out causes any pending pixels in the queue to be patterned before the
38 ; subroutine exits. If PFILL would continue to run by refusing to enter
39 ; new pixels when the queue is full, there would be no guarantee that
40 ; the subroutine would ever return.
41 ;
42 ; In English, the idea behind the patterned flood fill is simple. The
43 ; start pixel grows out in a circular shape (actually a diamond). A
44 ; fill boundary two pixels thick is maintained in that circular shape.
45 ; The outermost boundary is the frontier, and is where the flood fill
46 ; is growing from (ie the investigate block). The inner boundary is
47 ; the pattern block, waiting to be patterned. A solid inner boundary
48 ; is necessary to prevent the flood-fill frontier pixels from growing
49 ; back toward the starting pixel through holes in the pattern. Once
50 ; the frontier pixels are investigated, the innermost boundary is
51 ; patterned. The newly investigated pixels become the outermost
52 ; boundary (the investigate block) and the old investigate block becomes
53 ; the new pattern block.
54 ;
55 ; Each entry in the queue is a 3-byte struct that grows down in memory:
56 ; screen address (2-bytes, MSB first)
57 ; fill byte (1-byte)
58 ; A screen address with MSB < 0x40 is used to indicate the end of a block.
59 ; A screen address with MSB >= 0x80 is used to mark the physical end of the Q.
60 ;
61 ; The fill pattern is a typical 8x8 pixel character, stored in 8 bytes.
63 ; enter: h = y coord, l = x coord, bc = max stack depth, de = address of fill pattern
64 ; In hi-res mode, carry flag is most significant bit of x coord
65 ; used : ix, af, bc, de, hl
66 ; exit : no carry = success, carry = had to bail queue was too small
67 ; stack: 3*bc+30 bytes, not including the call to PFILL or interrupts
69 SPPFill:
70 push de ; save (pattern pointer) variable
71 dec bc ; we will start with one struct in the queue
72 push bc ; save max stack depth variable
73 ld a,h
74 call SPGetScrnAddr ; de = screen address, b = pixel byte
75 ex de,hl ; hl = screen address
76 call .bytefill ; b = fill byte
77 jr c,.viable
78 pop bc
79 pop de
80 ret
82 .viable:
83 ex de,hl ; de = screen address, b = fill byte
84 ld hl,-7
85 add hl,sp
86 push hl ; create pattern block pointer = top of queue
87 push hl
88 pop ix ; ix = top of queue
89 dec hl
90 dec hl
91 dec hl
92 push hl ; create investigate block pointer
93 ld hl,-12
94 add hl,sp
95 push hl ; create new block pointer
97 xor a
98 push af
99 dec sp ; mark end of pattern block
100 push de ; screen address and fill byte are
101 push bc ; first struct in investigate block
102 inc sp
103 push af
104 dec sp ; mark end of investigate block
106 ld c,(ix+7)
107 ld b,(ix+8) ; bc = max stack depth - 1
108 inc bc
109 ld l,c
110 ld h,b
111 add hl,bc ; space required = 3*BC (max depth) + 10
112 add hl,bc ; but have already taken 9 bytes
113 ld c,l
114 ld b,h ; bc = # uninitialized bytes in queue
115 ld hl,0
116 sbc hl,bc ; negate hl, additions above will not set carry
117 add hl,sp
118 ld (hl),0 ; zero last byte in queue
119 ld sp,hl ; move stack below queue
120 ld a,$80
121 push af ; mark end of queue with $80 byte
122 inc sp
123 ld e,l
124 ld d,h
125 inc de
126 dec bc
127 ldir ; zero the uninitialized bytes in queue
129 ; NOTE: Must move the stack before clearing the queue, otherwise if an interrupt
130 ; occurred, garbage could overwrite portions of the (just cleared) queue.
132 ; ix = top of queue, bottom of queue marked with 0x80 byte
134 ; Variables indexed by ix, LSB first:
135 ; ix + 11/12 return address
136 ; ix + 09/10 fill pattern pointer
137 ; ix + 07/08 max stack depth
138 ; ix + 05/06 pattern block pointer
139 ; ix + 03/04 investigate block pointer
140 ; ix + 01/02 new block pointer
142 ; A picture of memory at this point:
143 ;
144 ;+-----------------------+ higher addresses
145 ;| | |
146 ;|- return address -| \|/
147 ;| | V
148 ;+-----------------------+ lower addresses
149 ;| fill |
150 ;|- pattern pointer -|
151 ;| |
152 ;+-----------------------+
153 ;| |
154 ;|- max stack depth -|
155 ;| |
156 ;+-----------------------+
157 ;| |
158 ;|- pattern block -|
159 ;| |
160 ;+-----------------------+
161 ;| |
162 ;|- investigate block -|
163 ;| |
164 ;+-----------------------+
165 ;| |
166 ;|- new block -|
167 ;| |
168 ;+-----------------------+
169 ;| end of block marker | <- ix = pattern block = top of queue
170 ;| ? |
171 ;| ? |
172 ;+-----------------------+
173 ;| screen address MSB | <- investigate block
174 ;| screen address LSB |
175 ;| fill byte |
176 ;+-----------------------+
177 ;| end of block marker |
178 ;| ? |
179 ;| ? |
180 ;+-----------------------+
181 ;| 0 | <- new block
182 ;| 0 |
183 ;| 0 |
184 ;+-----------------------+
185 ;| |
186 ;| ...... | size is a multiple of 3 bytes
187 ;| rest of queue |
188 ;| all zeroed |
189 ;| ...... |
190 ;| |
191 ;+-----------------------+
192 ;| 0x80 | <- sp, special byte marks end of queue
193 ;+-----------------------+
195 .pfloop:
196 ld l,(ix+3)
197 ld h,(ix+4) ; hl = investigate block
198 ld e,(ix+1)
199 ld d,(ix+2) ; de = new block
200 call .investigate
201 ld (ix+1),e
202 ld (ix+2),d ; save new block
203 ld (ix+3),l
204 ld (ix+4),h ; save investigate block
206 ld l,(ix+5)
207 ld h,(ix+6) ; hl = pattern block
208 ld c,(ix+7)
209 ld b,(ix+8) ; bc = max stack depth (available space)
210 call .applypattern
211 ld (ix+7),c
212 ld (ix+8),b ; save stack depth
213 ld (ix+5),l
214 ld (ix+6),h ; save pattern block
216 ld a,(hl) ; done if the investigate block was empty
217 cp 0x40
218 jr nc,.pfloop
220 .endpfill:
221 ld de,11 ; return address is at ix+11
222 add ix,de
223 ld sp,ix
224 or a ; make sure carry is clear, indicating success
225 ret
227 ; IN/OUT: hl = investigate block, de = new block
228 .investigate:
229 ld a,(hl)
230 cp 0x80 ; bit 15 of screen addr set if time to wrap
231 jr c,.inowrap
232 push ix
233 pop hl ; hl = ix = top of queue
234 ld a,(hl)
236 .inowrap:
237 cp 0x40 ; screen address < 0x4000 marks end of block
238 jr c,.endinv ; are we done yet?
239 ld b,a
240 dec hl
241 ld c,(hl) ; bc = screen address
242 dec hl
243 ld a,(hl) ; a = fill byte
244 dec hl
245 push hl ; save spot in investigate block
246 ld l,c
247 ld h,b ; hl = screen address
248 ld b,a ; b = fill byte
250 .goup:
251 push hl ; save screen address
252 call SPPixelUp ; move screen address up one pixel
253 jr c,.updeadend ; if went off-screen
254 push bc ; save fill byte
255 call .bytefill
256 call c,.addnew ; if up is not dead end, add this to new block
257 pop bc ; restore fill byte
259 .updeadend:
260 pop hl ; restore screen address
262 .godown:
263 push hl ; save screen address
264 call SPPixelDown ; move screen address down one pixel
265 jr c,.downdeadend
266 push bc ; save fill byte
267 call .bytefill
268 call c,.addnew ; if down is not dead end, add this to new block
269 pop bc ; restore fill byte
271 .downdeadend:
272 pop hl ; restore screen address
274 .goleft:
275 bit 7,b ; can only move left if leftmost bit of fill byte set
276 jr z,.goright
277 ld a,l
278 and 31
279 jr nz,.okleft
280 bit 5,h ; for hi-res mode: column = 1 if l=0 and bit 5 of h is set
281 jr z,.goright
283 .okleft:
284 push hl ; save screen address
285 call SPCharLeft
286 push bc ; save fill byte
287 ld b,0x01 ; set rightmost pixel for incoming byte
288 call .bytefill
289 call c,.addnew ; if left is not dead end, add this to new block
290 pop bc ; restore fill byte
291 pop hl ; restore screen address
293 .goright:
294 bit 0,b ; can only move right if rightmost bit of fill byte set
295 jr z,.nextinv
296 or a ; clear carry
297 call SPCharRight
298 jr c,.nextinv ; went off screen
299 ld a,l
300 and 31
301 jr z,.nextinv ; wrapped around line
302 ld b,0x80 ; set leftmost pixel for incoming byte
303 call .bytefill
304 call c,.addnew ; if right is not dead end, add this to new block
306 .nextinv:
307 pop hl ; hl = spot in investigate block
308 jr .investigate
310 .endinv
311 dec hl
312 dec hl
313 dec hl ; investigate block now points at new block
315 ld a,(de) ; check if new block is at end of queue
316 cp 0x80
317 jr c,.nowrapnew
318 ld e,lx
319 ld d,hx ; de = ix = top of queue
321 .nowrapnew:
322 xor a
323 ld (de),a ; store end marker for new block
324 dec de
325 dec de
326 dec de
327 ret
329 ; enter b = incoming byte, hl = screen address
330 ; exit b = fill byte, screen blackened with fill byte
331 .bytefill:
332 ld a,b
333 xor (hl) ; zero out incoming pixels that
334 and b ; run into set pixels in display
335 ret z
337 .bfloop:
338 ld b,a
339 rra ; expand incoming pixels
340 ld c,a ; to the right and left
341 ld a,b ; within byte
342 add a,a
343 or c
344 or b
345 ld c,a
346 xor (hl) ; zero out pixels that run into
347 and c ; set pixels on display
348 cp b
349 jr nz,.bfloop ; keep going until incoming byte does not change
351 or (hl)
352 ld (hl),a ; fill byte on screen
353 scf ; indicate that this was a viable step
354 ret
356 ; add incoming fill byte and screen address to new block
357 ; enter b = incoming byte, hl = screen address, de = new block
358 .addnew:
359 push hl ; save screen address
360 ld l,(ix+7)
361 ld h,(ix+8) ; hl = max stack depth
362 ld a,h
363 or l
364 jr z,.bail ; no space in queue so bail!
365 dec hl ; available queue space decreases by one struct
366 ld (ix+7),l
367 ld (ix+8),h
368 pop hl ; hl = screen address
370 ld a,(de) ; check if new block is at end of queue
371 cp 0x80
372 jr c,.annowrap
373 ld e,lx
374 ld d,hx ; de = ix = top of queue
376 .annowrap:
377 ex de,hl
378 ld (hl),d ; make struct, store screen address (2 bytes)
379 dec hl
380 ld (hl),e
381 dec hl
382 ld (hl),b ; store fill byte (1 byte)
383 dec hl
384 ex de,hl
385 ret
387 ; if the queue filled up, we need to bail. Bailing means patterning any set pixels
388 ; which may still be on the display. If we didnt bail and tried to trudge along,
389 ; there is no guarantee the fill would ever return.
390 .bail:
391 pop hl ; hl = screen address, b = fill byte
392 ld a,b
393 xor (hl)
394 ld (hl),a ; clear this byte on screen
395 xor a
396 ld (de),a ; mark end of new block
397 ld l,(ix+5)
398 ld h,(ix+6) ; hl = pattern block
399 call .applypattern ; for pattern block
400 call .applypattern ; for investigate block
401 call .applypattern ; for new block
402 ld de,11 ; return address is at ix+11
403 add ix,de
404 ld sp,ix
405 scf ; indicate we had to bail
406 ret
408 ; hl = pattern block, bc = max stack depth (available space)
409 .applypattern:
410 ld a,(hl)
411 cp 0x80 ; bit 15 of screen addr set if time to wrap
412 jr c,.apnowrap
413 push ix
414 pop hl ; hl = ix = top of queue
415 ld a,(hl)
416 .apnowrap:
417 cp 0x40 ; screen address < 0x4000 marks end of block
418 jr c,.endapply ; are we done yet?
419 and 0x07 ; use scan line 0..7 to index pattern
420 add a,(ix+9)
421 ld e,a
422 ld a,0
423 adc a,(ix+10)
424 ld d,a ; de points into fill pattern
425 ld a,(de) ; a = pattern
426 ld d,(hl)
427 dec hl
428 ld e,(hl) ; de = screen address
429 dec hl
430 and (hl) ; and pattern with fill byte
431 sub (hl) ; or in complement of fill byte
432 dec a
433 ex de,hl
434 and (hl) ; apply pattern to screen
435 ld (hl),a
436 ex de,hl
437 dec hl
438 inc bc ; increase available queue space
439 jr .applypattern
441 .endapply:
442 dec hl
443 dec hl
444 dec hl ; pattern block now pts at investigate block
445 ret
448 ; Get Screen Address
449 ;
450 ; Returns the screen address and pixel mask corresponding
451 ; to a given pixel coordinate.
452 ;
453 ; enter: a = h = y coord
454 ; l = x coord
455 ; exit : de = screen address, b = pixel mask
456 ; uses : af, b, de, hl
457 SPGetScrnAddr:
458 and #07 ; A = 00000SSS
459 or #40 ; A = 01000SSS
460 ld d,a ; D = 01000SSS
461 ld a,h ; A = Y coord = BBLLLSSS
462 rra
463 rra
464 rra ; A = ???BBLLL
465 and #18 ; A = 000BB000
466 or d ; A = 010BBSSS
467 ld d,a ; D = 010BBSSS top 8 bits of address done
468 ld a,l ; A = X coord = CCCCCTTT
469 and #07 ; A = 00000TTT
470 ld b,a ; B = 00000TTT = which pixel?
471 ld a,#80 ; A = 10000000
472 jr z,.norotate ; if B=0, A is the right pixel so skip
473 .rotloop
474 rra ; rotate the pixel right one place B times
475 djnz .rotloop
476 .norotate
477 ld b,a ; B = pixel mask
478 srl l
479 srl l
480 srl l ; L = 000CCCCC
481 ld a,h ; A = Y coord = BBLLLSSS
482 rla
483 rla ; A = LLLSSS??
484 and #E0 ; A = LLL00000
485 or l ; A = LLLCCCCC
486 ld e,a ; E = LLLCCCCC
487 ret ; DE = 010BBSS LLLCCCCC, the screen address!
490 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
491 ;; IN:
492 ;; HL: scraddr
493 ;; OUT:
494 ;; HL: scraddrnext -- prev y line
495 ;; AF: dead
496 SPPixelUp:
497 ld a,h
498 dec h
499 and #07
500 ret nz
501 ld a,l
502 add a,#E0
503 ld l,a
504 sbc a,a
505 and #08
506 add a,h
507 ld h,a
508 cp #40
509 ret
512 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
513 ;; IN:
514 ;; HL: scraddr
515 ;; OUT:
516 ;; HL: scraddrnext -- next y line
517 ;; AF: dead
518 SPPixelDown:
519 inc h
520 ld a,h
521 and #07
522 ret nz
523 ld a,l
524 sub #E0
525 ld l,a
526 sbc a,a
527 and #F8
528 add a,h
529 ld h,a
530 cp #58
531 ccf
532 ret
535 SPCharRight:
536 inc l
537 ret nz
538 ld a,#08
539 add a,h
540 ld h,a
541 cp a,#58
542 ccf
543 ret
546 SPCharLeft:
547 ld a,l
548 dec l
549 or a,a
550 ret nz
551 ld a,h
552 sub a,#08
553 ld h,a
554 cp a,#40
555 ret