Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
Вид для печати
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
Смотря как ты его задаешь.Цитата:
Сообщение от jim
если выпуклый - идёшь от верхней точки к нижней и рисуешь горизонтальные линии. см. dd3dfaq, его недавно даже на Speccy перенесли ;)Цитата:
Сообщение от jim
Спасибо.
А все-таки существует ли более или менее универсальная процедура заливки замкнутого контура, при этом не очень тормозная, для Спектрума.
Всё таки, ты бы привёл конкретные спецификации, потому что ты выдвигаешь к процедуре обработки противоречивые требования: УНИВЕРСАЛИЗМ и ВЫСОКАЯ СКОРОСТЬ, это в принципе противоречивые требования. Если нужна классическая процедура заливки - то бери zx-review'93 в оглавлении сразу найдёшь - это классический пример процедуры заливки, но быстрой её точно не назовёшь, хотя универсальной - да.Цитата:
Сообщение от jim
Противоречивые требования, по моему, это ПАМЯТЬ и СКОРОСТЬ.Цитата:
Сообщение от GriV
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).
ps: Скачал 2 номера zx-review'93 с Virtual TR-DOS, ничего не нашел по заливке. А в каком номере это было?
ну так же и объём потребляемой памяти и скорость тоже противоречивые.Цитата:
Сообщение от jim
Не могу всопмнить конкретный номер, потому что у меня они в сборнике за 1993 год, там номера как таковые не разделялись - качай сборник и там ищи.
Вроде как там был разбор пакета 20 SuperRoutines, именно туда эта утилита входила.
А что мешает любую фигуру разбить на треугольники. Требугольник же,Цитата:
Сообщение от jim
как выпуклая фигура, заливается опиванным методом -- тривиально.
Ну если для тебя приемлем такой тормоз, то бери ревюшную процедуру.Цитата:
Сообщение от jim
Я ее видел в ZX-Forum (единственный номер в электронном виде).
А разбивать на треугольники? Мгновенно чтоли?:)Цитата:
Сообщение от fk0
Зато разбивка невыпуклого полигона на выпуклые нетривиальна.
Тем более что для разбиения на треугольники необходимо представить фигуру в виде отрезков.
а jim-у я понимаю надо заливка аля в графическом редакторе.
Не знаю, по моему достаточно быстро заливает. (см аттач)Цитата:
Сообщение от newart
Абсолютно верно!Цитата:
Сообщение от Sinus
Вот, когда то накропал. Gens-овский файл, но можно и как текст открыть и разобраться. Универсально заливает, но память кушает на сильно разветвлённых фигурах (проверяется на экране, испещрённом точками пиксел через пиксел - с таким и The Artist, и Art Studio не ладят). В принципе, доработать до неиспользования медленной процедуры ПЗУ для точки - и будет неплохо.Цитата:
Сообщение от jim
Спасибо.
Попробую поразбираться.
Если изначально предпологать, что все будет из треугольников - то тривиально =)Цитата:
Сообщение от Dexus
Изобретен какой-то алгоритм хитрый, который бы на спекруме не тормозил, например разбитие хитроформенного лабиринта 463-угольника? Даже самый шустрый ear-cutting алгоритм на спектруме безбожно тормозит.Цитата:
Сообщение от acidrain
Это не по теме вообще. Пиксельная заливка же обсуждается :)
Процедура заливки области на экране была в газете Impulse 1, я её даже пару раз заюзал, работает не слишком быстро, но по крайней мере быстрее чем в ArtStudio.
Насколько я помню самая быстрая заливка была в Artist II.
Hемедленно нажми на RESET, Dratov Denis!
On Wed, 28 Sep 05 00:15:54 +0400, Dratov Denis wrote:
Да какая разница что заливать? По сути один алгоритм, ресурсивный,Цитата:
DD> Изобретен какой-то алгоритм хитрый, который бы на спекруме не тормозил,
DD> например разбитие хитроформенного лабиринта 463-угольника? Даже самый шустрый
DD> ear-cutting алгоритм на спектруме безбожно тормозит.
DD> Это не по теме вообще. Пиксельная заливка же обсуждается :)
в разных формах выраженный получается. Понятно, что разные варианты
могут быть в разных случаях быстрей. Hо для практического применения,
вывода графики, пиксельная заливка только в арт-студио и нужна...
вот именно, лучше б не парились по мелочам, а сделали б че полезное для спека. посчитать скоко времени мы тут потратили на обсуждение такого простого вопроса, что мона было основу для игры наклепать. =) не партесь... купите чип и думайте, как его впихнуть в спек - он быстренько зальет вашу область ;)Цитата:
Сообщение от Kirill Frolov (500:812/1.507)
Вот тут-то вы и не правы. А что, если графика типа Micronaut One? Как, по-вашему, там изображают хотя бы купол Jelly Fly?Цитата:
Сообщение от Kirill Frolov (500:812/1.507)
Ты еще Gyron вспомни
не надо путать заливку замкнутого контура и рисование закрашенных примитивов
а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой графикой.Цитата:
Сообщение от jerri
3Д весьма концептуальноеЦитата:
Сообщение от TomCaT
Извините, я пошутил неудачно. Конечно же, я знаю и видел эту игру. Мне просто показалось, что Вы считаете Gyron плохим примером. :) Больше, надеюсь, не повторится.Цитата:
Сообщение от jerri
я не собираюсь путать. Я привоже пример. Хорошая процедура заливки и в игре м/б пригодится. Пусть это хоть текстовая адвенчура - большая часть времени там как раз на заливку уходила. А ещё на дуги и окружности, но это в плохих квестах и с использованием ПЗУ (Urban Upstart)Цитата:
Сообщение от jerri
Кстати, родилась бешеная идея оптимизации процедуры заливки. Если все получится, то заливать будет не точками -- байтами, но при этом без ошибок, именно замкнутый контур. Из за неперерасчета координат и практически восьмикратного увеличения темпов должно получиться весело!
А потом надо бы ее встроить в Asterix & Obelix, а то игра красивая (хоть и простенькая сюжетно), но заливка там достает неимоверно!
Заливка нужна узором или нет?
Если первое - то сложнее. Обычно делается сначала заливка без узора, а потом по вычисленной маске заполняется узором. Тогда память будет отжираться помимо рекурсивных нужд алгоритма еще и на хранение маски.
А вообще да, байтами можно. Как раз как-то давно я делал именно алгоритм, который заливал байтами, соотв. смещение по x - это инкремент/декремент, а по y понятно, что сложнее, но не на много.
Увы, исходников не осталось, но кое-какие воспоминания есть... может попробую восстановить.
Да с узором потом уж как-то разбираться... Пока ускорить бы 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 пары и оба аккумулятора.
Зачем так сложно? Это же простое текстурирование, сиречь перевод координат X,Y в U,V. Т.е. заливать не волновым алгоритмом (вроде как самый распространёный?), а просто переводить координаты и читать из куска памяти с текстурой цвет точки. Проблема только в умножении.Цитата:
Сообщение от maximk
Ну, поставили мы очередную точку, а перейдя к следующей откуда известно - это незалитая точка или черная точка узора?Цитата:
Сообщение от icebear
А, понял, понял. Ну, перевод координат - задача не для z80, имхо...
Да, заливка с маской была в каком-то редакторе для спека, но я не помню в каком, я его почти не юзал. Так, просто осмотрел.
А для кого в этом случае?Цитата:
Сообщение от maximk
Ай-яй-яй :) классику забываем. В ArtStudio есть. И называется кстати вполне виндовым термином - brush.Цитата:
Сообщение от maximk
Блин :) Я имел ввиду, что не вижу пока оснований, полагать, что заливка с преобразованием координат будет быстрее, чем solid fill, да еще и байтами. Т.е. если ее реализовать на z80 то (скорее всего) результат будет неудовлетворительным по скорости. Но, это я так понимаю, может какой-нибудь мега-кодер покажет мастер класс и заставит меня еще раз засомневаться :)Цитата:
Сообщение от icebear
Дык, виноват :) , но я не художник ни разу и даже не тянет. Поэтому прога впечатлила возможностями, но я реально не использовал.Цитата:
Сообщение от icebear
Тут, как говорится, "палка на двух концах" :) Либо делать топорно но быстро, либо красиво но медленно. С текстурами больше возможностей по "раскраске". Тольк вот как сделать такое на Спектруме не спрашивай, я уже 12 лет на ассемблере Z80 ничего не делал.Цитата:
Сообщение от maximk
Ну нарисовать свой шрифт в АртСтудио обязаность каждого спектрумиста. :)Цитата:
Сообщение от maximk
Поддерживаю. Именно так! Не даром дядька Кнут говорил:Цитата:
Сообщение от icebear
иЦитата:
Premature optimization is the root of all evil
Но, на спеке ввиду скромных (по современным мерками) вычислительных возможностей, вопрос этой самой оптимизации стоит остро. С другой стороны, есть некое удовлетворение, когда ты закодил нечто, что эффектно крутится даже не 3.5МГц, хотя внутри черт голову сломит :)Цитата:
If you optimize everything, you will always be unhappy.
Зато если сделать быстрое текстурирование (даже с ограничениями) - это было бы революцией на Спектруме.Цитата:
Сообщение от maximk
Рекоменую посмотреть вот это http://zxaaa.untergrund.net/DEMO/35mhz.zip - часть из IRIS Ultrademo by Flash Inc.
да, это настоящий шедевр кода. было-бы здорово получить исходники, а еще лучше статью на эту тему.
Исходники есть на zxopensource.Цитата:
Сообщение от elfh
В 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.
спасибо.