Процедура заливки замкнутого контура

[goodboy]

Смысл бага в том, что при некоторых выборах точки заливки, заливалась область снаружи выделения.

в отладчике видно что начинается заливка правильно, а потом происходит сбой.

[Dart Alver]

Как давно это было.

Вложения

FastWell-BehavedPatternFloodFillA.zip (49.4 Кб, Просмотров: 5)

Очень интересное решение, и с заливкой, и шустро, и смотрится забавно и не особо прожорлива. )) Правда не очень понял статус исходника на сайтах ( зарубеж однако, на каждый пук лицензия )) ), вроде как фриваре с копирайтами его типа можно использовать как хочешь, сохраняя копирайты, или х.з. ?

[Shiny]

Правда не очень понял статус исходника на сайтах ( зарубеж однако, на каждый пук лицензия )) ), вроде как фриваре с копирайтами его типа можно использовать как хочешь, сохраняя копирайты, или х.з. ?

Происхождение алгоритма в архиве.

- - - Добавлено - - -

Вот еще находка. Код набирался из книжки "Инфорком" по графике. Кажется, в исходнике была ошибка, но это было так давно, что забылось.

[TomCaT]

Ok ! Вот снап BGE 3.12d с экраном в режиме заливки.
Ткните в любой прямоугольник и будет вам счастье (точнее наоборот) ))

Вложение 81253

- - - Добавлено - - -

Исходники BGE 3.12d : https://disk.yandex.ru/d/l3YDa52I0iMS3Q
Процедура заливки в файле 'Fill3.asm'

Ага. Так... Помозгую

[TomCaT]

Похоже, неправильно вычисляется длина только что заполненной строки, и при обратном проходе влево (в поисках соседних с ней незаполненных участков) - на снапшоте выше вместо 8 пикселов у левого края, например, проходятся 256 пикселов. Ищу далее...


- - - Добавлено - - -

Да, проблема с вычислением начальной длины. Исправляется за счет вставки еще двух байтов и что там +10...12 лишних тактов на каждую строку
Между "ffilns" и "ffilnb" - есть код
...
ld a,d
sub b
ld b,a
sub d
ld e,a
...

на этом участке программы D= const 8. Регистр B - вычисляется № точки в байте от левого края (выитается из 8). Регистр E - будет накапливаться длина строки, это копия B, но из нее сразу вычитается 8 для компенсации прибавки 8 по коду ниже (сразу после атрибутов), при проходе первого частично заполненного байта на левом краю этой строки

и если левый край строки выходит ровно по краю символа, это компенсационное вычитание все портит. Надо его обойти, вставив "jr z,$+3":

...
ld a,d
sub b
ld b,a
jr z,$+3
sub d
ld e,a
...

- - - Добавлено - - -

P.S. По дороге нашел еще один баг, который не вылетал из-за удчаного стечения адреса компиляции

в двух местах переходы "jr ffilns+4" надо заменить на "jr ffilns+5", т.к. там на месте, куда идет переход, рядом лежит вместо JR уже JP с его лишним байтом. И сейчас "jr ffilns+4" попадают на ложную команду, которая случайно только тратит пару лишних тактов, но не мешала выполнению.

- - - Добавлено - - -

Стряхну пыль с темы. ))


Заменял этой процедурой процедуру заливки в BGE 3.12 Demo, поскольку эта меньше по размеру а места катострофически не хватало. И соответственно она перешла по наследству в BGE 4.0 demo где места ещё меньше осталось )) , и вот внезапно спустя 4 года обнаружил что процедура имеет баг.

Судя по тому что о нём никто не упоминал - это показатель использования. )) Глюк наиболее вероятно можно словить при заливке малых областей, а так как заливают чаще крупные, то ,,,
Смысл бага в том, что при некоторых выборах точки заливки, заливалась область снаружи выделения.

По факту я даже не сразу заподозрил процедуру заливки, думал в коде выбора точки ошибка. Но в конце концов условия срабатывания бага удалось выявить.

Итак условия проявления бага (должены быть соблюдены все):

...

3) В байте слева до курсора не должно быть пикселей, т.е. все пиксели в байте должны быть справа за курсором.

4) Либо байт на который попадает курсор должен быть в крайнем слева знакоместе экрана, либо же в байте предыдущего знакоместа должен быть выставлен в 1 - bit0 (т.е. крайняя правая точка в той же линии предыдущего знакоместа)

Вопрос: может ли автор или кто-либо разобраться и как-то исправить баг в самой процедуре ?

...

Автор смог. Спасибо за тестирование

подробности по глюку чуть выше.

А тут прилагаю текст поправленного кода, который по ходу поиска бага немного дополнил комментариями.

- - - Добавлено - - -

Как давно это было.

Отличная статья. И пример очень быстрый. А по размеру код где-то 0,5кБ, так понимаю по дебаггеру?

Правда, буфер вместо очереди стеком сделан, видимо. Задал ей картинку с огромным количеством ответвлений (чередующиеся по вертикали байты 0xAA / 0x00). Залила секунд за 5, но насорила в стеке больше, чем на 20кБ

Переделать ее на очередь - может стать еще лучше.

[Dart Alver]

Отличная статья. И пример очень быстрый. А по размеру код где-то 0,5кБ, так понимаю по дебаггеру?

Правда, буфер вместо очереди стеком сделан, видимо. Задал ей картинку с огромным количеством ответвлений (чередующиеся по вертикали байты 0xAA / 0x00). Залила секунд за 5, но насорила в стеке больше, чем на 20кБ

Переделать ее на очередь - может стать еще лучше.

Там в статье несколько процедур, самая первая самая быстрая и самая прожорливая по памяти больше 30 k жрать может вроде, две последних жрут вполне экономно, плюс есть ограничитель по заполнению стека.

Самая последняя ( с заливкой текстурой ) по описанию автора для заливки любого уровня сложности требует не более 930 или 950 байт на стеке, я чуть больше задал, встроил её на пробу в BGE (адаптировал под текстуру 16x16 - стала помедленнее теперь )) работает вполне ничего так ). Сама процедура стала 511 байт, плюс чуток обвязки для смены адреса стека на буфер. Если бы мусорила бы на 20k, BGE бы затирал данные или даже вылетел, но глюков пока не наблюдаю. )

И да, в этих процедурах самым медленным и затратным происходит заполнение пустого экрана, если на экране чтото есть, пусть даже с дофига ветвлениями, процесс идёт быстрее ))

[TomCaT]

То есть, если на экране текстура из точек потеснее, то это потом для заливки проще, чем пустой экран? По скорости, так понял, проще, а по расходу стека?

Если буфер перед вызовом в дебагере почистить нулями, то интересно, сколько потратится на стеке на пустом экране, и сколько на испещренном точками.

[Dart Alver]

Попробовал, забивает абсолютно одинаково для пустого экрана и для точек, 1088 байт вроде вышло.

[Shiny]

Я где-то пропустил требования к стеку?
Гляньте на такой вариант:
http://www.retroprogramming.com/2017...lood-fill.html

[Dart Alver]

Я где-то пропустил требования к стеку?

Особых не было. В BGE под временный буфер можно выделить максимум 2560 байт. А уж переместить сюда временно стек или так адресовать - не суть. Процедура TomCatа вполне подходила пока не нашёлся глюк.
Процедура от Альвина Альбрехта, которую ты подсказал, с текстурной заливкой ещё более интересна в этом плане. Хотя и стала медленнее после моих манипуляций. Ведь теперь обрабатывается текстура 16x16 и окраска атрибутами.
Если глюков не обнаружется, останется она.
Ну а эксперименты по заполнению буфера это сугубо ради научного интереса ))

Гляньте на такой вариант:

Ну тут автор не указал сколько нужно оставить места на стек, но чтото мне подсказывает что мнооого )) Впрочем проверять лень. )