Saturday, 29 April 2017

ZX Spectrum Scanline Flood Fill

A flood fill is a graphical algorithm to colour an area of screen bounded by pixels of another colour. The scanline technique is a fast, stack-efficient flood fill which can be implemented in 99 bytes of Z80, as demonstrated below:
; scanline fill by John Metcalf
; call with d=x-coord, e=y-coord

; set end marker

fill:
  ld l,255
  push hl

; calculate bit position of pixel

nextrun:
  ld a,d
  and 7
  inc a
  ld b,a
  ld a,1
bitpos:
  rrca
  djnz bitpos
  ld c,b
  ld b,a

; move left until hitting a set pixel or the screen edge

seekleft:
  ld a,d
  or a
  jr z,goright
  dec d
  rlc b
  call scrpos
  jr nz,seekleft

; move right until hitting a set pixel or the screen edge,
; setting pixels as we go. Check rows above and below and
; save their coordinates to fill later if necessary

seekright:  
  rrc b
  inc d
  jr z,rightedge
goright:
  call scrpos
  jr z,rightedge
  ld (hl),a
  inc e
  call checkadj
  dec e
  dec e
  call checkadj
  inc e
  jr seekright

; check to see if there's another row waiting to be filled

rightedge:
  pop de
  ld a,e
  inc a
  jr nz,nextrun
  ret  

; calculate the pixel address and whether or not it's set

scrpos:
  ld a,e
  and 248
  rra
  scf
  rra
  rra
  ld l,a
  xor e
  and 248
  xor e
  ld h,a
  ld a,l
  xor d
  and 7
  xor d
  rrca
  rrca
  rrca
  ld l,a
  ld a,b
  or (hl)
  cp (hl)
  ret

; check and save the coordinates of an adjacent row

checkadj:
  sla c
  ld a,e
  cp 192
  ret nc
  call scrpos+1
  ret z
  inc c
  bit 2,c
  ret nz
  pop hl
  push de
  jp (hl)

8 comments:

  1. Hi John, Just tried this routine and it crashes the Spectrum. I have checked my Z80 a number of times and I cannot see where it differs from the above. I am probably missing something - is the above definately correct? Many thanks. Paddy

    ReplyDelete
  2. My fault John - got an address wrong.

    ReplyDelete
  3. Finding the best biological science paper writing help and Biological Science Writing Services is not easy unless one is keen to establish a reliable biological science research paper provider & biological science coursework writing services.

    ReplyDelete
  4. Fantastic blog! Do you have any tips and hints for aspiring writers? I’m planning to start my own website soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any suggestions? Many thanks! uk flooding

    ReplyDelete
  5. Hi John! I hope you are still around... I ran across you flood fill algorithm and upgraded it a little so it can do colored pattern fills with an arbitrary UDG you select. If you're interested in the approach/source code/demo, just drop me an email at contact2021@bartheld.net. You comment is highly appreciated. Greets, Volker

    ReplyDelete
  6. What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much. Full Spectrum CBD Oil

    ReplyDelete
  7. This surely was a great help to me as well! Thanks to this naming firm,  I was able to monetize my brand name with a variety of merchandise. You should definitely try their new online course CBD OIL TINCTURE

    ReplyDelete
  8. The writing you wrote helped me a lot. 메이저토토사이트 I would like a lot of good articles in the future.

    ReplyDelete