使用递归Flood Fill算法时如何避免屏幕闪烁
汇编实现Flood Fill的问题与分析
维基百科中关于Flood Fill的条目描述了如下递归算法:
Flood-fill (node):
- 若节点不在区域内则返回。
- 设置该节点。
- 对节点南侧的位置执行Flood-fill。
- 对节点北侧的位置执行Flood-fill。
- 对节点西侧的位置执行Flood-fill。
- 对节点东侧的位置执行Flood-fill。
- 返回。
网上能找到的汇编实现Flood Fill的示例不多,我自行用FASM写了个还算不错的版本,Stack Overflow上还有两个更差的递归实现!
从性能角度看,邻域像素的遍历顺序影响不大,不一定非要按南→北→西→东的顺序。24种排列随便用哪种都行,但千万别选方向和其相反方向不紧邻的顺序——这会让栈使用量直接翻倍!合适的顺序包括SNWE、NSWE、SNEW、NSEW、WESN、EWSN、WENS和EWNS。
这个程序能正常运行,但屏幕会出现闪烁(flicker)。会不会是递归实现Flood Fill导致的?真的是这个原因吗?
; ------------------------------ ; BL is OldColor ; BH is NewColor ; CX is X ; DX is Y ; IN (bx,cx,dx) FloodWhile: pusha mov al, bl ; NewColor mov ah, 0Ch mov si, ax ; CONST shr bx, 8 ; -> BL is OldColor, BH=0 is DisplayPage cmp al, bl ; NewColor must be different from OldColor je .z mov ah, 0Dh ; BIOS.ReadPixel int 10h ; -> AL cmp al, bl ; First pixel must have OldColor jne .z call .Flood ; -> (AX) .z: popa ret ; - - - - - - - - - - - - - - - ; IN (bx,cx,dx,si) OUT () MOD (ax) .Flood: push di mov di, 12 mov ax, si ; -> AL is NewColor, AH=0Ch is FunctionID int 10h ; BIOS.WritePixel .a: add cx, [.c+di] ; Try a neighboring pixel (SNWE) cmp cx, 320 jnb .b add dx, [.c+di+2] cmp dx, 200 jnb .b mov ah, 0Dh ; BIOS.ReadPixel int 10h ; -> AL cmp al, bl jne .b call .Flood .b: sub di, 4 jns .a dec cx ; X-- Return from East pop di ret ; East West North South <-- SNWE .c: dw +2,0, -1,+1, 0,-2, 0,+1 ; ------------------------------
内容的提问来源于stack exchange,提问作者Sep Roland
相关产品推荐
相关产品推荐

