PDA

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



jim
27.08.2005, 22:24
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.

newart
27.08.2005, 23:32
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
Смотря как ты его задаешь.

MadCat!
27.08.2005, 23:44
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
если выпуклый - идёшь от верхней точки к нижней и рисуешь горизонтальные линии. см. dd3dfaq, его недавно даже на Speccy перенесли ;)

jim
27.08.2005, 23:57
Спасибо.
А все-таки существует ли более или менее универсальная процедура заливки замкнутого контура, при этом не очень тормозная, для Спектрума.

GriV
28.08.2005, 06:20
Спасибо.
А все-таки существует ли более или менее универсальная процедура заливки замкнутого контура, при этом не очень тормозная, для Спектрума.

Всё таки, ты бы привёл конкретные спецификации, потому что ты выдвигаешь к процедуре обработки противоречивые требования: УНИВЕРСАЛИЗМ и ВЫСОКАЯ СКОРОСТЬ, это в принципе противоречивые требования. Если нужна классическая процедура заливки - то бери zx-review'93 в оглавлении сразу найдёшь - это классический пример процедуры заливки, но быстрой её точно не назовёшь, хотя универсальной - да.

jim
29.08.2005, 11:20
Всё таки, ты бы привёл конкретные спецификации, потому что ты выдвигаешь к процедуре обработки противоречивые требования: УНИВЕРСАЛИЗМ и ВЫСОКАЯ СКОРОСТЬ, это в принципе противоречивые требования. Если нужна классическая процедура заливки - то бери zx-review'93 в оглавлении сразу найдёшь - это классический пример процедуры заливки, но быстрой её точно не назовёшь, хотя универсальной - да.Противоречивые требования, по моему, это ПАМЯТЬ и СКОРОСТЬ.
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).
ps: Скачал 2 номера zx-review'93 с Virtual TR-DOS, ничего не нашел по заливке. А в каком номере это было?

GriV
05.09.2005, 15:31
Противоречивые требования, по моему, это ПАМЯТЬ и СКОРОСТЬ.
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).
ps: Скачал 2 номера zx-review'93 с Virtual TR-DOS, ничего не нашел по заливке. А в каком номере это было?

ну так же и объём потребляемой памяти и скорость тоже противоречивые.
Не могу всопмнить конкретный номер, потому что у меня они в сборнике за 1993 год, там номера как таковые не разделялись - качай сборник и там ищи.
Вроде как там был разбор пакета 20 SuperRoutines, именно туда эта утилита входила.

fk0
05.09.2005, 16:20
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).

А что мешает любую фигуру разбить на треугольники. Требугольник же,
как выпуклая фигура, заливается опиванным методом -- тривиально.

newart
05.09.2005, 18:01
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
Ну если для тебя приемлем такой тормоз, то бери ревюшную процедуру.
Я ее видел в ZX-Forum (единственный номер в электронном виде).

Dexus
05.09.2005, 18:16
А что мешает любую фигуру разбить на треугольники. Требугольник же,
как выпуклая фигура, заливается опиванным методом -- тривиально.
А разбивать на треугольники? Мгновенно чтоли?:)

Sinus
06.09.2005, 15:16
Зато разбивка невыпуклого полигона на выпуклые нетривиальна.
Тем более что для разбиения на треугольники необходимо представить фигуру в виде отрезков.
а jim-у я понимаю надо заливка аля в графическом редакторе.

jim
06.09.2005, 20:10
Ну если для тебя приемлем такой тормоз, то бери ревюшную процедуру.

Не знаю, по моему достаточно быстро заливает. (см аттач)


а jim-у я понимаю надо заливка аля в графическом редакторе.
Абсолютно верно!

TomCaT
23.09.2005, 16:50
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.

Вот, когда то накропал. Gens-овский файл, но можно и как текст открыть и разобраться. Универсально заливает, но память кушает на сильно разветвлённых фигурах (проверяется на экране, испещрённом точками пиксел через пиксел - с таким и The Artist, и Art Studio не ладят). В принципе, доработать до неиспользования медленной процедуры ПЗУ для точки - и будет неплохо.

jim
27.09.2005, 11:30
Спасибо.
Попробую поразбираться.

acidrain
27.09.2005, 20:10
А разбивать на треугольники? Мгновенно чтоли?
Если изначально предпологать, что все будет из треугольников - то тривиально =)

Dexus
27.09.2005, 21:09
Если изначально предпологать, что все будет из треугольников - то тривиально =)
Изобретен какой-то алгоритм хитрый, который бы на спекруме не тормозил, например разбитие хитроформенного лабиринта 463-угольника? Даже самый шустрый ear-cutting алгоритм на спектруме безбожно тормозит.
Это не по теме вообще. Пиксельная заливка же обсуждается :)

Pawel
28.09.2005, 11:18
Процедура заливки области на экране была в газете Impulse 1, я её даже пару раз заюзал, работает не слишком быстро, но по крайней мере быстрее чем в ArtStudio.

Dexus
28.09.2005, 14:27
Насколько я помню самая быстрая заливка была в Artist II.

Kirill Frolov (500:812/1.507)
01.10.2005, 19:52
Hемедленно нажми на RESET, Dratov Denis!

On Wed, 28 Sep 05 00:15:54 +0400, Dratov Denis wrote:


DD> Изобретен какой-то алгоритм хитрый, который бы на спекруме не тормозил,
DD> например разбитие хитроформенного лабиринта 463-угольника? Даже самый шустрый
DD> ear-cutting алгоритм на спектруме безбожно тормозит.
DD> Это не по теме вообще. Пиксельная заливка же обсуждается :)

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

acidrain
03.10.2005, 20:32
пиксельная заливка только в арт-студио и нужна...
вот именно, лучше б не парились по мелочам, а сделали б че полезное для спека. посчитать скоко времени мы тут потратили на обсуждение такого простого вопроса, что мона было основу для игры наклепать. =) не партесь... купите чип и думайте, как его впихнуть в спек - он быстренько зальет вашу область ;)

TomCaT
10.10.2005, 08:27
Да какая разница что заливать? По сути один алгоритм, ресурсивный,
в разных формах выраженный получается. Понятно, что разные варианты
могут быть в разных случаях быстрей. Hо для практического применения,
вывода графики, пиксельная заливка только в арт-студио и нужна...

Вот тут-то вы и не правы. А что, если графика типа Micronaut One? Как, по-вашему, там изображают хотя бы купол Jelly Fly?

jerri
10.10.2005, 14:12
Ты еще Gyron вспомни

не надо путать заливку замкнутого контура и рисование закрашенных примитивов

TomCaT
10.10.2005, 14:32
Ты еще Gyron вспомни

а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой графикой.

jerri
10.10.2005, 14:35
а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой графикой.

3Д весьма концептуальное

TomCaT
10.10.2005, 15:57
3Д весьма концептуальное
( в сообщении были вложения: GyronAtrium.zip (53.1 Кбайт, 1 просмотров))

Извините, я пошутил неудачно. Конечно же, я знаю и видел эту игру. Мне просто показалось, что Вы считаете Gyron плохим примером. :) Больше, надеюсь, не повторится.


не надо путать заливку замкнутого контура и рисование закрашенных примитивов

я не собираюсь путать. Я привоже пример. Хорошая процедура заливки и в игре м/б пригодится. Пусть это хоть текстовая адвенчура - большая часть времени там как раз на заливку уходила. А ещё на дуги и окружности, но это в плохих квестах и с использованием ПЗУ (Urban Upstart)

TomCaT
01.08.2006, 19:10
Кстати, родилась бешеная идея оптимизации процедуры заливки. Если все получится, то заливать будет не точками -- байтами, но при этом без ошибок, именно замкнутый контур. Из за неперерасчета координат и практически восьмикратного увеличения темпов должно получиться весело!

А потом надо бы ее встроить в Asterix & Obelix, а то игра красивая (хоть и простенькая сюжетно), но заливка там достает неимоверно!

maximk
01.08.2006, 20:56
Заливка нужна узором или нет?
Если первое - то сложнее. Обычно делается сначала заливка без узора, а потом по вычисленной маске заполняется узором. Тогда память будет отжираться помимо рекурсивных нужд алгоритма еще и на хранение маски.

А вообще да, байтами можно. Как раз как-то давно я делал именно алгоритм, который заливал байтами, соотв. смещение по x - это инкремент/декремент, а по y понятно, что сложнее, но не на много.
Увы, исходников не осталось, но кое-какие воспоминания есть... может попробую восстановить.

TomCaT
02.08.2006, 06:39
Да с узором потом уж как-то разбираться... Пока ускорить бы Solid Fill.

Я уже половину написал, все должно работать (как всегда, ДОЛЖНО, но... :). Но если исходников нет, может, есть какие идеи по оптимизации?.. Я, к сожалению, пока распланировал неплохо, даже стек -- только для сохранения ответвлений, никаких лишних операций с памятью, но -- жрет альтернативные. Случайно нет таких команд: EX DE,IX / EX DE,IY? Поиск в инете говорит, что вроде нет :( :/.

В частности, нужно быстро переходить из адреса видеобуфера на соседнюю строку вверх и вниз. Можно использовать аккумулятор и одну какую то пару, DE например. Я пока догадался только, что если неприятные переходы и преобразования адреса ждут сверху, то внизу их точно нет, и vice versa... Еще можно сделать табличку из 192 адресов левого края строк, а один 8-битный рег использовать для хранения номера строки, изменяя параллельно с адресом и рассчитывая заново после снятия адреса со стека.

__________________________________________

Еще вот похожие на рабочие варианты: так как всегда заняты A, HL для операций с очередным байтом и BC, для хранения и отсчета текущего бита, A' -- разные флаги, то IY мог бы хранить старый стек (с IY на его вершине -- используется только в начале и конце работы), а IX и DE -- два адресов соседних строк. Но уже тут проблемы с хранением маски. Так что, если нет команды обмена последних, стоит отказаться от одного адреса (он и так легко получается INC/DEC HL), введя одним флагом признак "стороны" той строки, что сейчас в DE. А еще в E хранить маску, а в D -- биты старшие 4-0, младшие 7-5 адреса соседней строки, по которым из HL также недолго (AND, OR, пара AND A, SCF, 6 сдвигов A и 3 -- другого регистра) получить адрес второй строки-соседки. Старый стек тогда в IX. Итого занято 4 пары и оба аккумулятора.

icebear
02.08.2006, 08:59
Заливка нужна узором или нет?
Если первое - то сложнее. Обычно делается сначала заливка без узора, а потом по вычисленной маске заполняется узором. Тогда память будет отжираться помимо рекурсивных нужд алгоритма еще и на хранение маски.

Зачем так сложно? Это же простое текстурирование, сиречь перевод координат X,Y в U,V. Т.е. заливать не волновым алгоритмом (вроде как самый распространёный?), а просто переводить координаты и читать из куска памяти с текстурой цвет точки. Проблема только в умножении.

maximk
02.08.2006, 10:14
а просто переводить координаты и читать из куска памяти с текстурой цвет точки. Проблема только в умножении.
Ну, поставили мы очередную точку, а перейдя к следующей откуда известно - это незалитая точка или черная точка узора?

А, понял, понял. Ну, перевод координат - задача не для z80, имхо...

Да, заливка с маской была в каком-то редакторе для спека, но я не помню в каком, я его почти не юзал. Так, просто осмотрел.

icebear
02.08.2006, 10:27
Ну, поставили мы очередную точку, а перейдя к следующей откуда известно - это незалитая точка или черная точка узора?

А, понял, понял. Ну, перевод координат - задача не для z80, имхо...

А для кого в этом случае?


Да, заливка с маской была в каком-то редакторе для спека, но я не помню в каком, я его почти не юзал. Так, просто осмотрел.

Ай-яй-яй :) классику забываем. В ArtStudio есть. И называется кстати вполне виндовым термином - brush.

maximk
02.08.2006, 12:15
А для кого в этом случае?

Блин :) Я имел ввиду, что не вижу пока оснований, полагать, что заливка с преобразованием координат будет быстрее, чем solid fill, да еще и байтами. Т.е. если ее реализовать на z80 то (скорее всего) результат будет неудовлетворительным по скорости. Но, это я так понимаю, может какой-нибудь мега-кодер покажет мастер класс и заставит меня еще раз засомневаться :)


В ArtStudio есть
Дык, виноват :) , но я не художник ни разу и даже не тянет. Поэтому прога впечатлила возможностями, но я реально не использовал.

icebear
02.08.2006, 13:50
Блин :) Я имел ввиду, что не вижу пока оснований, полагать, что заливка с преобразованием координат будет быстрее, чем solid fill, да еще и байтами.

Тут, как говорится, "палка на двух концах" :) Либо делать топорно но быстро, либо красиво но медленно. С текстурами больше возможностей по "раскраске". Тольк вот как сделать такое на Спектруме не спрашивай, я уже 12 лет на ассемблере Z80 ничего не делал.


Дык, виноват :) , но я не художник ни разу и даже не тянет. Поэтому прога впечатлила возможностями, но я реально не использовал.

Ну нарисовать свой шрифт в АртСтудио обязаность каждого спектрумиста. :)

maximk
02.08.2006, 14:37
Тут, как говорится, "палка на двух концах" Либо делать топорно но быстро, либо красиво но медленно.
Поддерживаю. Именно так! Не даром дядька Кнут говорил:


Premature optimization is the root of all evil

и


If you optimize everything, you will always be unhappy.


Но, на спеке ввиду скромных (по современным мерками) вычислительных возможностей, вопрос этой самой оптимизации стоит остро. С другой стороны, есть некое удовлетворение, когда ты закодил нечто, что эффектно крутится даже не 3.5МГц, хотя внутри черт голову сломит :)

icebear
02.08.2006, 14:43
Но, на спеке ввиду скромных (по современным мерками) вычислительных возможностей, вопрос этой самой оптимизации стоит остро. С другой стороны, есть некое удовлетворение, когда ты закодил нечто, что эффектно крутится даже не 3.5МГц, хотя внутри черт голову сломит :)

Зато если сделать быстрое текстурирование (даже с ограничениями) - это было бы революцией на Спектруме.

drbars
30.08.2006, 18:39
Рекоменую посмотреть вот это http://zxaaa.untergrund.net/DEMO/35mhz.zip - часть из IRIS Ultrademo by Flash Inc.

elfh
31.08.2006, 00:24
да, это настоящий шедевр кода. было-бы здорово получить исходники, а еще лучше статью на эту тему.

drbars
31.08.2006, 12:06
да, это настоящий шедевр кода. было-бы здорово получить исходники, а еще лучше статью на эту тему.

Исходники есть на zxopensource.

Raider
31.08.2006, 18:38
В IRIS (и в остальных вещах) делается довольно просто - рисуются многоугольные полигоны. Это не заливка через затравку (растеканием),
это отрисовка полигона по-линиям, сверху-вниз, между левой и правой стороной.

Текстурный паттерн не сдвигается побитно. Он "стоит" на экране. Благодаря этому при заливке полигона переносятся просто-напросто байты текстурного паттерна. Единственное только, это на ребрах откусываются байты паттерна по and-маске.

Текстуру и не надо двигать при заливке, иначе у ребер получится некрасиво.

Алгоритм очень прост.
Для того чтобы он работал, должны выполняться два условия - рисуемый многоугольник обязательно должен быть выпуклым.
(Кстати любые выпуклые геометрические тела дают выпуклую проекцию грани, т.е. при проекции многоугольник на экране будет заведомо выпуклым - это теорема геометрии)
И второе условие - вершины должны обходится по порядку, либо все по часовой стрелке, либо все против часовой стрелки.

Есть два буфера сторон. Для левой стороны многоугольника, и для правой стороны многоугольника. Они содержат X-координаты. Длина буферов нужна не менее высоты экрана.
Ищется самая верхняя вершина (min Y).
Ищется самая нижняя вершина (max Y).
Начиная от самой верхней найденной вершины, по-порядку, каждое ребро посылается в процедуру ScanConvert(x1, x2, y1, y2).
Итого - для треугольника будет три ребра и три раза будет вызываться ScanConvert. Для четырехугольника - четыре, и так далее...
Далее все просто - ScanConvert определяет левое это ребро или правое (правый буфер заполнять или левый) и шагая сверху-вниз по выбранному буферу (получается что как бы по "развертке" ребра на ось Y) пошагово вносит в буфер X-координаты ребра. Для этого я для каждого шага находил делением дельту. Вы можете составить более быстрый алгоритм. Как определить правое или левое это ребро легко догадаться, ибо сверху заданы два условия. Вырожденные ребра (чисто горизонтальные) не вносятся.
А дальше, когда буферы заполнены от самой верхней найденной Y-вершины и до самой нижней Y-вершины рисуем линии. Каждая линия от X-координаты левого буфера до X-координаты правого.

p.s.
сорцы Iris много лет уже можно взять на
http://opensourcezx.narod.ru

можете втч. ими воспользоваться.
смотреть нужно функции POLY3 или POLY4.

elfh
02.09.2006, 21:13
спасибо.

elfh
03.09.2006, 15:10
offtopic: вы вообще очень мощно кодите. я давно поражен тем, как вы реализовывали те или иные вещи. недавно посмотрел процедуру линии by alex raider. тот же принцип применен в процедуре от х-trade, опубликованной в одном из журналов spectrum expert. только там она занимает значительно больше памяти и работает чуть-чуть быстрее, видимо благодаря этому - я не сравнивал алгоритмы. у них по-моему обработка входных параметров оптимальнее сделана.

Raider
03.09.2006, 16:59
Ага, не ставилось цели получить worlds fastest line :-)
да и писалось всё в 1996 году :-)

TomCaT
04.09.2006, 19:59
Вернулся из нетворческого отпуска, но там все же дописал эту процедуру. В итоге слишком быстро не получилось. :( :mad: , но зато килобайта буфера(а то, вроде, и меньше) хватает на все задачи. Так что прямое ей место, видимо, в граф. редакторы.

07.09 Ерунду спорол с проверкой на 0 длины линии. Много лишнего, сократилась на 15 байт.

jim
06.10.2006, 22:12
интересно как вот это реализовано? вот бы разобраться..
пример с ftp-шника WOS

Raider
07.10.2006, 17:20
называется заливка с затравкой.

в аттачах примеры на си из книги Шикина и Борескова

DIMA 1
07.02.2007, 17:50
Зацените игру Hard Driving помоему очень круто для спеки . 89 года. 48к.
И как это всё работает на 3.5 мгц ....