Просмотр полной версии : Процедура заливки замкнутого контура
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
Смотря как ты его задаешь.
Поделитесь опытом, как быстро залить многоугольник?
Есть свой вариант, но он не устраивает по скорости.
если выпуклый - идёшь от верхней точки к нижней и рисуешь горизонтальные линии. см. dd3dfaq, его недавно даже на Speccy перенесли ;)
Спасибо.
А все-таки существует ли более или менее универсальная процедура заливки замкнутого контура, при этом не очень тормозная, для Спектрума.
Спасибо.
А все-таки существует ли более или менее универсальная процедура заливки замкнутого контура, при этом не очень тормозная, для Спектрума.
Всё таки, ты бы привёл конкретные спецификации, потому что ты выдвигаешь к процедуре обработки противоречивые требования: УНИВЕРСАЛИЗМ и ВЫСОКАЯ СКОРОСТЬ, это в принципе противоречивые требования. Если нужна классическая процедура заливки - то бери zx-review'93 в оглавлении сразу найдёшь - это классический пример процедуры заливки, но быстрой её точно не назовёшь, хотя универсальной - да.
Всё таки, ты бы привёл конкретные спецификации, потому что ты выдвигаешь к процедуре обработки противоречивые требования: УНИВЕРСАЛИЗМ и ВЫСОКАЯ СКОРОСТЬ, это в принципе противоречивые требования. Если нужна классическая процедура заливки - то бери zx-review'93 в оглавлении сразу найдёшь - это классический пример процедуры заливки, но быстрой её точно не назовёшь, хотя универсальной - да.Противоречивые требования, по моему, это ПАМЯТЬ и СКОРОСТЬ.
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).
ps: Скачал 2 номера zx-review'93 с Virtual TR-DOS, ничего не нашел по заливке. А в каком номере это было?
Противоречивые требования, по моему, это ПАМЯТЬ и СКОРОСТЬ.
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).
ps: Скачал 2 номера zx-review'93 с Virtual TR-DOS, ничего не нашел по заливке. А в каком номере это было?
ну так же и объём потребляемой памяти и скорость тоже противоречивые.
Не могу всопмнить конкретный номер, потому что у меня они в сборнике за 1993 год, там номера как таковые не разделялись - качай сборник и там ищи.
Вроде как там был разбор пакета 20 SuperRoutines, именно туда эта утилита входила.
По поводу конкретной спецификации: нужна именно универсальная процедура (без оптимизации по конкретным фигурам).
А что мешает любую фигуру разбить на треугольники. Требугольник же,
как выпуклая фигура, заливается опиванным методом -- тривиально.
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
Ну если для тебя приемлем такой тормоз, то бери ревюшную процедуру.
Я ее видел в ZX-Forum (единственный номер в электронном виде).
А что мешает любую фигуру разбить на треугольники. Требугольник же,
как выпуклая фигура, заливается опиванным методом -- тривиально.
А разбивать на треугольники? Мгновенно чтоли?:)
Зато разбивка невыпуклого полигона на выпуклые нетривиальна.
Тем более что для разбиения на треугольники необходимо представить фигуру в виде отрезков.
а jim-у я понимаю надо заливка аля в графическом редакторе.
Ну если для тебя приемлем такой тормоз, то бери ревюшную процедуру.
Не знаю, по моему достаточно быстро заливает. (см аттач)
а jim-у я понимаю надо заливка аля в графическом редакторе.
Абсолютно верно!
В том же Beta Basic 4.0 реализована оная функция с вполне приемлемой скоростью.
(Только вот, что она с памятью делает во время исполнения)
Вот бы её оттудова выцарапать.
Вот, когда то накропал. Gens-овский файл, но можно и как текст открыть и разобраться. Универсально заливает, но память кушает на сильно разветвлённых фигурах (проверяется на экране, испещрённом точками пиксел через пиксел - с таким и The Artist, и Art Studio не ладят). В принципе, доработать до неиспользования медленной процедуры ПЗУ для точки - и будет неплохо.
Спасибо.
Попробую поразбираться.
acidrain
27.09.2005, 22:10
А разбивать на треугольники? Мгновенно чтоли?
Если изначально предпологать, что все будет из треугольников - то тривиально =)
Если изначально предпологать, что все будет из треугольников - то тривиально =)
Изобретен какой-то алгоритм хитрый, который бы на спекруме не тормозил, например разбитие хитроформенного лабиринта 463-угольника? Даже самый шустрый ear-cutting алгоритм на спектруме безбожно тормозит.
Это не по теме вообще. Пиксельная заливка же обсуждается :)
Процедура заливки области на экране была в газете Impulse 1, я её даже пару раз заюзал, работает не слишком быстро, но по крайней мере быстрее чем в ArtStudio.
Насколько я помню самая быстрая заливка была в Artist II.
Kirill Frolov (500:812/1.507)
01.10.2005, 21: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, 22:32
пиксельная заливка только в арт-студио и нужна...
вот именно, лучше б не парились по мелочам, а сделали б че полезное для спека. посчитать скоко времени мы тут потратили на обсуждение такого простого вопроса, что мона было основу для игры наклепать. =) не партесь... купите чип и думайте, как его впихнуть в спек - он быстренько зальет вашу область ;)
Да какая разница что заливать? По сути один алгоритм, ресурсивный,
в разных формах выраженный получается. Понятно, что разные варианты
могут быть в разных случаях быстрей. Hо для практического применения,
вывода графики, пиксельная заливка только в арт-студио и нужна...
Вот тут-то вы и не правы. А что, если графика типа Micronaut One? Как, по-вашему, там изображают хотя бы купол Jelly Fly?
Ты еще Gyron вспомни
не надо путать заливку замкнутого контура и рисование закрашенных примитивов
Ты еще Gyron вспомни
а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой графикой.
а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой графикой.
3Д весьма концептуальное
3Д весьма концептуальное
( в сообщении были вложения: GyronAtrium.zip (53.1 Кбайт, 1 просмотров))
Извините, я пошутил неудачно. Конечно же, я знаю и видел эту игру. Мне просто показалось, что Вы считаете Gyron плохим примером. :) Больше, надеюсь, не повторится.
не надо путать заливку замкнутого контура и рисование закрашенных примитивов
я не собираюсь путать. Я привоже пример. Хорошая процедура заливки и в игре м/б пригодится. Пусть это хоть текстовая адвенчура - большая часть времени там как раз на заливку уходила. А ещё на дуги и окружности, но это в плохих квестах и с использованием ПЗУ (Urban Upstart)
Кстати, родилась бешеная идея оптимизации процедуры заливки. Если все получится, то заливать будет не точками -- байтами, но при этом без ошибок, именно замкнутый контур. Из за неперерасчета координат и практически восьмикратного увеличения темпов должно получиться весело!
А потом надо бы ее встроить в 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. Т.е. заливать не волновым алгоритмом (вроде как самый распространёный?), а просто переводить координаты и читать из куска памяти с текстурой цвет точки. Проблема только в умножении.
а просто переводить координаты и читать из куска памяти с текстурой цвет точки. Проблема только в умножении.
Ну, поставили мы очередную точку, а перейдя к следующей откуда известно - это незалитая точка или черная точка узора?
А, понял, понял. Ну, перевод координат - задача не для z80, имхо...
Да, заливка с маской была в каком-то редакторе для спека, но я не помню в каком, я его почти не юзал. Так, просто осмотрел.
Ну, поставили мы очередную точку, а перейдя к следующей откуда известно - это незалитая точка или черная точка узора?
А, понял, понял. Ну, перевод координат - задача не для z80, имхо...
А для кого в этом случае?
Да, заливка с маской была в каком-то редакторе для спека, но я не помню в каком, я его почти не юзал. Так, просто осмотрел.
Ай-яй-яй :) классику забываем. В ArtStudio есть. И называется кстати вполне виндовым термином - brush.
А для кого в этом случае?
Блин :) Я имел ввиду, что не вижу пока оснований, полагать, что заливка с преобразованием координат будет быстрее, чем solid fill, да еще и байтами. Т.е. если ее реализовать на z80 то (скорее всего) результат будет неудовлетворительным по скорости. Но, это я так понимаю, может какой-нибудь мега-кодер покажет мастер класс и заставит меня еще раз засомневаться :)
В ArtStudio есть
Дык, виноват :) , но я не художник ни разу и даже не тянет. Поэтому прога впечатлила возможностями, но я реально не использовал.
Блин :) Я имел ввиду, что не вижу пока оснований, полагать, что заливка с преобразованием координат будет быстрее, чем solid fill, да еще и байтами.
Тут, как говорится, "палка на двух концах" :) Либо делать топорно но быстро, либо красиво но медленно. С текстурами больше возможностей по "раскраске". Тольк вот как сделать такое на Спектруме не спрашивай, я уже 12 лет на ассемблере Z80 ничего не делал.
Дык, виноват :) , но я не художник ни разу и даже не тянет. Поэтому прога впечатлила возможностями, но я реально не использовал.
Ну нарисовать свой шрифт в АртСтудио обязаность каждого спектрумиста. :)
Тут, как говорится, "палка на двух концах" Либо делать топорно но быстро, либо красиво но медленно.
Поддерживаю. Именно так! Не даром дядька Кнут говорил:
Premature optimization is the root of all evil
и
If you optimize everything, you will always be unhappy.
Но, на спеке ввиду скромных (по современным мерками) вычислительных возможностей, вопрос этой самой оптимизации стоит остро. С другой стороны, есть некое удовлетворение, когда ты закодил нечто, что эффектно крутится даже не 3.5МГц, хотя внутри черт голову сломит :)
Но, на спеке ввиду скромных (по современным мерками) вычислительных возможностей, вопрос этой самой оптимизации стоит остро. С другой стороны, есть некое удовлетворение, когда ты закодил нечто, что эффектно крутится даже не 3.5МГц, хотя внутри черт голову сломит :)
Зато если сделать быстрое текстурирование (даже с ограничениями) - это было бы революцией на Спектруме.
Рекоменую посмотреть вот это http://zxaaa.untergrund.net/DEMO/35mhz.zip - часть из IRIS Ultrademo by Flash Inc.
да, это настоящий шедевр кода. было-бы здорово получить исходники, а еще лучше статью на эту тему.
да, это настоящий шедевр кода. было-бы здорово получить исходники, а еще лучше статью на эту тему.
Исходники есть на zxopensource.
В 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.
offtopic: вы вообще очень мощно кодите. я давно поражен тем, как вы реализовывали те или иные вещи. недавно посмотрел процедуру линии by alex raider. тот же принцип применен в процедуре от х-trade, опубликованной в одном из журналов spectrum expert. только там она занимает значительно больше памяти и работает чуть-чуть быстрее, видимо благодаря этому - я не сравнивал алгоритмы. у них по-моему обработка входных параметров оптимальнее сделана.
Ага, не ставилось цели получить worlds fastest line :-)
да и писалось всё в 1996 году :-)
Вернулся из нетворческого отпуска, но там все же дописал эту процедуру. В итоге слишком быстро не получилось. :( :mad: , но зато килобайта буфера(а то, вроде, и меньше) хватает на все задачи. Так что прямое ей место, видимо, в граф. редакторы.
07.09 Ерунду спорол с проверкой на 0 длины линии. Много лишнего, сократилась на 15 байт.
интересно как вот это реализовано? вот бы разобраться..
пример с ftp-шника WOS
называется заливка с затравкой.
в аттачах примеры на си из книги Шикина и Борескова
Зацените игру Hard Driving помоему очень круто для спеки . 89 года. 48к.
И как это всё работает на 3.5 мгц ....
Powered by vBulletin® Version 4.2.5 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot