Floodfill — различия между версиями

Материал из SpeccyWiki
Перейти к: навигация, поиск
(Содержимое страницы заменено на «Статья удаленна из-за самоуправства рязанского пидора Димачки Быстров…»)
(Отмена правки 35915, сделанной участником Goblinish (обс.) причина:наличие личных оскорблений в нецензурной форме)
 
Строка 1: Строка 1:
−
Статья удаленна из-за самоуправства рязанского пидора Димачки Быстрова.Сдохни с туберкулеза гнида
+
Алгоритм основан на коде(Basic):
 +
<code><pre>
 +
5 REM AUTHOR UNKNOWN
 +
10 CIRCLE 128,88,80
 +
20 LET x=100 : LET y = 100 : REM START POINT
 +
30 GO SUB 1000 : STOP
 +
 
 +
1000 PLOT x,y
 +
1010 IF NOT POINT(x+1,y) THEN LET x=x+1 : GO SUB 1000 : LET x=x-1
 +
1020 IF NOT POINT(x-1,y) THEN LET x=x-1 : GO SUB 1000 : LET x=x+1
 +
1030 IF NOT POINT(x,y+1) THEN LET y=y+1 : GO SUB 1000 : LET y=y-1
 +
1040 IF NOT POINT(x,y-1) THEN LET y=y-1 : GO SUB 1000 : LET y=y+1
 +
1050 RETURN
 +
</pre></code>
 +
 
 +
Alvin Albrecht в статье "A Fast Well-Behaved Pattern Flood Fill" предложил ускоренный вариант, теперь в экранной области не сканируется каждая точка, а заполняется значением #ff, если байт нулевой. исходники в статье содержат неточности, поэтому приводится дизассемблированный текст.
 +
 
 +
Входные параметры: hl=YX координаты точки заливки области.
 +
 
 +
<code><pre>
 +
fill:
 +
ld bc, 64h
 +
call sub_800B
 +
ret
 +
; =============== S U B R O U T I N E =======================================
 +
sub_800B:
 +
ld a, h
 +
cp 0C0h
 +
ret nc
 +
dec bc
 +
push bc
 +
call sub_80F9
 +
ex de, hl
 +
call sub_814B
 +
jr c, loc_801C
 +
pop bc
 +
ret
 +
loc_801C:
 +
ld ix, 0FFFFh
 +
add ix, sp
 +
push hl
 +
push bc
 +
inc sp
 +
xor a
 +
push af
 +
dec sp
 +
ld c, (ix+1)
 +
ld b, (ix+2)
 +
inc bc
 +
ld l, c
 +
ld h, b
 +
add hl, bc
 +
add hl, bc
 +
ld c, l
 +
ld b, h
 +
ld h, a
 +
ld l, a
 +
sbc hl, bc
 +
add hl, sp
 +
ld (hl), a
 +
ld sp, hl
 +
ld a, 80h
 +
push af
 +
inc sp
 +
ld e, l
 +
ld d, h
 +
inc de
 +
dec bc
 +
ldir
 +
push ix
 +
pop bc
 +
ld hl, 0FFFAh
 +
add hl, bc
 +
ex de, hl
 +
ld l, c
 +
ld h, b
 +
loc_8050:
 +
ld a, (hl)
 +
cp 80h
 +
jr c, loc_8059
 +
push ix
 +
pop hl
 +
ld a, (hl)
 +
loc_8059:
 +
cp 40h
 +
jr c, loc_80B8
 +
ld b, a
 +
dec hl
 +
ld c, (hl)
 +
dec hl
 +
ld a, (hl)
 +
dec hl
 +
inc (ix+1)
 +
jr nz, loc_806B
 +
inc (ix+2)
 +
loc_806B:
 +
push hl
 +
ld l, c
 +
ld h, b
 +
ld b, a
 +
push hl
 +
call sub_8120
 +
jr c, loc_807D
 +
push bc
 +
call sub_814B
 +
call c, sub_80D3
 +
pop bc
 +
loc_807D:
 +
pop hl
 +
push hl
 +
call sub_8135
 +
jr c, loc_808C
 +
push bc
 +
call sub_814B
 +
call c, sub_80D3
 +
pop bc
 +
loc_808C:
 +
pop hl
 +
bit 7, b
 +
jr z, loc_80A3
 +
push hl
 +
ld a, l
 +
dec l
 +
and 1Fh
 +
jr z, loc_80A2
 +
push bc
 +
ld b, 1
 +
call sub_814B
 +
call c, sub_80D3
 +
pop bc
 +
loc_80A2:
 +
pop hl
 +
loc_80A3:
 +
bit 0, b
 +
jr z, loc_80B5
 +
inc l
 +
ld a, l
 +
and 1Fh
 +
jr z, loc_80B5
 +
ld b, 80h
 +
call sub_814B
 +
call c, sub_80D3
 +
loc_80B5:
 +
pop hl
 +
jr loc_8050
 +
loc_80B8:
 +
dec hl
 +
dec hl
 +
dec hl
 +
ld a, (de)
 +
cp 80h
 +
jr c, loc_80C3
 +
push ix
 +
pop de
 +
loc_80C3:
 +
xor a
 +
ld (de), a
 +
dec de
 +
dec de
 +
dec de
 +
ld a, (hl)
 +
cp 40h
 +
jr nc, loc_8050
 +
ld sp, ix
 +
inc sp
 +
inc sp
 +
inc sp
 +
ret
 +
; =============== S U B R O U T I N E =======================================
 +
sub_80D3:
 +
push hl
 +
ld l, (ix+1)
 +
ld h, (ix+2)
 +
ld a, h
 +
or l
 +
jr nz, loc_80E0
 +
pop hl
 +
ret
 +
loc_80E0:
 +
dec hl
 +
ld (ix+1), l
 +
ld (ix+2), h
 +
pop hl
 +
ld a, (de)
 +
cp 80h
 +
jr c, loc_80F0
 +
push ix
 +
pop de
 +
loc_80F0:
 +
ex de, hl
 +
ld (hl), d
 +
dec hl
 +
ld (hl), e
 +
dec hl
 +
ld (hl), b
 +
dec hl
 +
ex de, hl
 +
ret
 +
; =============== S U B R O U T I N E =======================================
 +
sub_80F9:
 +
and 7
 +
or 40h
 +
ld d, a
 +
ld a, h
 +
rra
 +
rra
 +
rra
 +
and 18h
 +
or d
 +
ld d, a
 +
ld a, l
 +
and 7
 +
ld b, a
 +
ld a, 80h
 +
jr z, loc_8111
 +
loc_810E:
 +
rra
 +
djnz loc_810E
 +
loc_8111:
 +
ld b, a
 +
srl l
 +
srl l
 +
srl l
 +
ld a, h
 +
rla
 +
rla
 +
and 0E0h
 +
or l
 +
ld e, a
 +
ret
 +
; =============== S U B R O U T I N E =======================================
 +
sub_8120:
 +
ld a, h
 +
dec h
 +
and 7
 +
ret nz
 +
ld a, 8
 +
add a, h
 +
ld h, a
 +
ld a, l
 +
sub 20h
 +
ld l, a
 +
ret nc
 +
ld a, h
 +
sub 8
 +
ld h, a
 +
cp 40h
 +
ret
 +
; =============== S U B R O U T I N E =======================================
 +
sub_8135:
 +
inc h
 +
ld a, h
 +
and 7
 +
ret nz
 +
ld a, h
 +
sub 8
 +
ld h, a
 +
ld a, l
 +
add a, 20h
 +
ld l, a
 +
ret nc
 +
ld a, h
 +
add a, 8
 +
ld h, a
 +
cp 58h
 +
ccf
 +
ret
 +
; =============== S U B R O U T I N E =======================================
 +
sub_814B:
 +
ld a, b
 +
xor (hl)
 +
and b
 +
ret z
 +
ld b, a
 +
loc_8150:
 +
rra
 +
ld c, a
 +
ld a, b
 +
add a, a
 +
or c
 +
or b
 +
ld c, a
 +
xor (hl)
 +
and c
 +
cp b
 +
ld b, a
 +
jp nz, loc_8150
 +
or (hl)
 +
ld (hl), a
 +
scf
 +
ret
 +
 
 +
</pre></code>
 +
ссылки:
 +
http://en.wikipedia.org/wiki/Flood_fill
 +
 
 +
http://wos.meulie.net/pub/spectrum/games-info/f/FastWell-BehavedPatternFloodFillA.doc
 +
(статья содержит подробную статью о структуре экранной области, приведены исходные тексты Basic.)
 +
http://www.timexsinclair.org/alvin/tidbits/fillprogs.zip
 +
(.TAP-файлы пример программ на Basic, статья ссылается на архив)
 +
[[Категория:Программирование графики]]

Текущая версия на 01:12, 8 августа 2017

Алгоритм основан на коде(Basic): 

5 REM AUTHOR UNKNOWN
10 CIRCLE 128,88,80
20 LET x=100 : LET y = 100 : REM START POINT
30 GO SUB 1000 : STOP

1000 PLOT x,y
1010 IF NOT POINT(x+1,y) THEN LET x=x+1 : GO SUB 1000 : LET x=x-1
1020 IF NOT POINT(x-1,y) THEN LET x=x-1 : GO SUB 1000 : LET x=x+1
1030 IF NOT POINT(x,y+1) THEN LET y=y+1 : GO SUB 1000 : LET y=y-1
1040 IF NOT POINT(x,y-1) THEN LET y=y-1 : GO SUB 1000 : LET y=y+1
1050 RETURN

Alvin Albrecht в статье "A Fast Well-Behaved Pattern Flood Fill" предложил ускоренный вариант, теперь в экранной области не сканируется каждая точка, а заполняется значением #ff, если байт нулевой. исходники в статье содержат неточности, поэтому приводится дизассемблированный текст.

Входные параметры: hl=YX координаты точки заливки области. 

fill:
		ld	bc, 64h
		call	sub_800B
		ret
; =============== S U B	R O U T	I N E =======================================
sub_800B:
		ld	a, h
		cp	0C0h
		ret	nc
		dec	bc
		push	bc
		call	sub_80F9
		ex	de, hl
		call	sub_814B
		jr	c, loc_801C
		pop	bc
		ret
loc_801C:
		ld	ix, 0FFFFh
		add	ix, sp
		push	hl
		push	bc
		inc	sp
		xor	a
		push	af
		dec	sp
		ld	c, (ix+1)
		ld	b, (ix+2)
		inc	bc
		ld	l, c
		ld	h, b
		add	hl, bc
		add	hl, bc
		ld	c, l
		ld	b, h
		ld	h, a
		ld	l, a
		sbc	hl, bc
		add	hl, sp
		ld	(hl), a
		ld	sp, hl
		ld	a, 80h
		push	af
		inc	sp
		ld	e, l
		ld	d, h
		inc	de
		dec	bc
		ldir
		push	ix
		pop	bc
		ld	hl, 0FFFAh
		add	hl, bc
		ex	de, hl
		ld	l, c
		ld	h, b
loc_8050:
		ld	a, (hl)
		cp	80h
		jr	c, loc_8059
		push	ix
		pop	hl
		ld	a, (hl)
loc_8059:
		cp	40h
		jr	c, loc_80B8
		ld	b, a
		dec	hl
		ld	c, (hl)
		dec	hl
		ld	a, (hl)
		dec	hl
		inc	(ix+1)
		jr	nz, loc_806B
		inc	(ix+2)
loc_806B:
		push	hl
		ld	l, c
		ld	h, b
		ld	b, a
		push	hl
		call	sub_8120
		jr	c, loc_807D
		push	bc
		call	sub_814B
		call	c, sub_80D3
		pop	bc
loc_807D:
		pop	hl
		push	hl
		call	sub_8135
		jr	c, loc_808C
		push	bc
		call	sub_814B
		call	c, sub_80D3
		pop	bc
loc_808C:
		pop	hl
		bit	7, b
		jr	z, loc_80A3
		push	hl
		ld	a, l
		dec	l
		and	1Fh
		jr	z, loc_80A2
		push	bc
		ld	b, 1
		call	sub_814B
		call	c, sub_80D3
		pop	bc
loc_80A2:
		pop	hl
loc_80A3:
		bit	0, b
		jr	z, loc_80B5
		inc	l
		ld	a, l
		and	1Fh
		jr	z, loc_80B5
		ld	b, 80h
		call	sub_814B
		call	c, sub_80D3
loc_80B5:
		pop	hl
		jr	loc_8050
loc_80B8:
		dec	hl
		dec	hl
		dec	hl
		ld	a, (de)
		cp	80h
		jr	c, loc_80C3
		push	ix
		pop	de
loc_80C3:
		xor	a
		ld	(de), a
		dec	de
		dec	de
		dec	de
		ld	a, (hl)
		cp	40h
		jr	nc, loc_8050
		ld	sp, ix
		inc	sp
		inc	sp
		inc	sp
		ret
; =============== S U B	R O U T	I N E =======================================
sub_80D3:
		push	hl
		ld	l, (ix+1)
		ld	h, (ix+2)
		ld	a, h
		or	l
		jr	nz, loc_80E0
		pop	hl
		ret
loc_80E0:
		dec	hl
		ld	(ix+1),	l
		ld	(ix+2),	h
		pop	hl
		ld	a, (de)
		cp	80h
		jr	c, loc_80F0
		push	ix
		pop	de
loc_80F0:
		ex	de, hl
		ld	(hl), d
		dec	hl
		ld	(hl), e
		dec	hl
		ld	(hl), b
		dec	hl
		ex	de, hl
		ret
; =============== S U B	R O U T	I N E =======================================
sub_80F9:
		and	7
		or	40h
		ld	d, a
		ld	a, h
		rra
		rra
		rra
		and	18h
		or	d
		ld	d, a
		ld	a, l
		and	7
		ld	b, a
		ld	a, 80h
		jr	z, loc_8111
loc_810E:
		rra
		djnz	loc_810E
loc_8111:
		ld	b, a
		srl	l
		srl	l
		srl	l
		ld	a, h
		rla
		rla
		and	0E0h
		or	l
		ld	e, a
		ret
; =============== S U B	R O U T	I N E =======================================
sub_8120:
		ld	a, h
		dec	h
		and	7
		ret	nz
		ld	a, 8
		add	a, h
		ld	h, a
		ld	a, l
		sub	20h
		ld	l, a
		ret	nc
		ld	a, h
		sub	8
		ld	h, a
		cp	40h
		ret
; =============== S U B	R O U T	I N E =======================================
sub_8135:
		inc	h
		ld	a, h
		and	7
		ret	nz
		ld	a, h
		sub	8
		ld	h, a
		ld	a, l
		add	a, 20h
		ld	l, a
		ret	nc
		ld	a, h
		add	a, 8
		ld	h, a
		cp	58h
		ccf
		ret
; =============== S U B	R O U T	I N E =======================================
sub_814B:
		ld	a, b
		xor	(hl)
		and	b
		ret	z
		ld	b, a
loc_8150:
		rra
		ld	c, a
		ld	a, b
		add	a, a
		or	c
		or	b
		ld	c, a
		xor	(hl)
		and	c
		cp	b
		ld	b, a
		jp	nz, loc_8150
		or	(hl)
		ld	(hl), a
		scf
		ret

ссылки: http://en.wikipedia.org/wiki/Flood_fill

http://wos.meulie.net/pub/spectrum/games-info/f/FastWell-BehavedPatternFloodFillA.doc (статья содержит подробную статью о структуре экранной области, приведены исходные тексты Basic.) http://www.timexsinclair.org/alvin/tidbits/fillprogs.zip (.TAP-файлы пример программ на Basic, статья ссылается на архив)

Источник — «https://speccy.info/w/index.php?title=Floodfill&oldid=37159»