ZXNet эхоконференция «code.zx»


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



от: jim
кому: TomCaT
дата: 27 Sep 2005
Спасибо.
Попробую поразбираться.

от: Dratov Denis
кому: acidrain
дата: 28 Sep 2005
aci> Если изначально предпологать, что все будет из треугольников - то
aci> тривиально =)
Изобретен какой-то алгоритм хитрый, который бы на спекруме не тормозил,
например разбитие хитроформенного лабиринта 463-угольника? Даже самый шустрый
ear-cutting алгоритм на спектруме безбожно тормозит.
Это не по теме вообще. Пиксельная заливка же обсуждается :)

от: acidrain
кому: Dexus
дата: 28 Sep 2005
Dex> А разбивать на треугольники? Мгновенно чтоли?
Если изначально предпологать, что все будет из треугольников - то тривиально =)
--
--
//acidrai

от: Dratov Denis
кому: Pawel
дата: 28 Sep 2005
Hасколько я помню самая быстрая заливка была в Artist II.

от: Павел Кисляк
кому: Dexus
дата: 28 Sep 2005
Процедура заливки области на экране была в газете Impulse 1, я её даже пару раз
заюзал, работает не слишком быстро, но по крайней мере быстрее чем в ArtStudio.

от: Kirill Frolov
кому: Dratov Denis
дата: 30 Sep 2005
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
кому: All
дата: 04 Oct 2005
Kir> пиксельная заливка только в арт-студио и нужна...
вот именно, лучше б не парились по мелочам, а сделали б че полезное для спека.
посчитать скоко времени мы тут потратили на обсуждение такого простого вопроса,
что мона было основу для игры наклепать. =) не партесь... купите чип и думайте,
как его впихнуть в спек - он быстренько зальет вашу область ;)
--
--
//acidrai

от: TomCaT
кому: All
дата: 10 Oct 2005
Hello, All

Kir> Да какая разница что заливать? По сути один алгоритм, ресурсивный,
Kir> в разных формах выраженный получается. Понятно, что разные варианты
Kir> могут быть в разных случаях быстрей. Hо для практического применения,
Kir> вывода графики, пиксельная заливка только в арт-студио и нужна...
Вот тут-то вы и не правы. А что, если графика типа Micronaut One? Как,
по-вашему, там изображают хотя бы купол Jelly Fly?
--
Can you help Robin in his quest for the Silver Arrow?

WBR, TomCaT aka Костя

от: TomCaT
кому: All
дата: 10 Oct 2005
Hello, jerri

jer> Ты еще Gyron вспомни
а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой
графикой.
--
Can you help Robin in his quest for the Silver Arrow?

WBR, TomCaT aka Костя

от: Yuri Potapov
кому: All
дата: 10 Oct 2005
Hello, TomCaT

Tom> а что, это табу такое - Gyron? Или всё таки игра с оригинальной и быстрой
Tom> графикой.
3Д весьма концептуальное
--
Когда ж я сдохну?! :mad:

Файл: GyronAtrium.zip http://zx.pk.ru/attachment.php?attachmentid=1802

WBR, jerri aka Yuri Potapov

от: Yuri Potapov
кому: All
дата: 10 Oct 2005
Hello, TomCaT

Ты еще Gyron вспомни

не надо путать заливку замкнутого контура и рисование закрашенных примитивов
--
Когда ж я сдохну?! :mad:

WBR, jerri aka Yuri Potapov

от: TomCaT
кому: All
дата: 10 Oct 2005
Hello, jerri

jer> 3Д весьма концептуальное
jer> ( в сообщении были вложения: GyronAtrium.zip (53.1 Кбайт, 1 просмотров))
Извините, я пошутил неудачно. Конечно же, я знаю и видел эту игру. Мне просто
показалось, что Вы считаете Gyron плохим примером. :) Больше, надеюсь, не
повторится.


jer> не надо путать заливку замкнутого контура и рисование закрашенных
jer> примитивов
я не собираюсь путать. Я привоже пример. Хорошая процедура заливки и в игре м/б
пригодится. Пусть это хоть текстовая адвенчура - большая часть времени там как
раз на заливку уходила. А ещё на дуги и окружности, но это в плохих квестах и с
использованием ПЗУ (Urban Upstart)
--
Can you help Robin in his quest for the Silver Arrow?

WBR, TomCaT aka Костя

от: TomCaT
кому: All
дата: 01 Aug 2006
Hello, TomCaT

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

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

от: Max Kuleshov
кому: All
дата: 02 Aug 2006
Hello, TomCaT

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

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

от: Andreas Kaiser
кому: All
дата: 02 Aug 2006
Hello, maximk

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

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

от: TomCaT
кому: All
дата: 02 Aug 2006
Hello, maximk

Да с узором потом уж как-то разбираться... Пока ускорить бы Solid Fill.

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

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

__________________________________________

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

от: Andreas Kaiser
кому: All
дата: 02 Aug 2006
Hello, maximk

max> Hу, поставили мы очередную точку, а перейдя к следующей откуда
max> известно - это незалитая точка или черная точка узора?
max>
max> А, понял, понял. Hу, перевод координат - задача не для z80, имхо...

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

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

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

от: Max Kuleshov
кому: All
дата: 02 Aug 2006
Hello, icebear

ice> а просто переводить координаты и читать из куска памяти с текстурой
ice> цвет точки. Проблема только в умножении.

Hу, поставили мы очередную точку, а перейдя к следующей откуда известно - это
незалитая точка или черная точка узора?

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

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

от: Andreas Kaiser
кому: All
дата: 02 Aug 2006
Hello, maximk

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

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

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

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

от: Max Kuleshov
кому: All
дата: 02 Aug 2006
Hello, icebear

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

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

ice> В ArtStudio есть

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

от: Andreas Kaiser
кому: All
дата: 02 Aug 2006
Hello, maximk

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

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

от: Max Kuleshov
кому: All
дата: 02 Aug 2006
Hello, icebear

ice> Тут, как говорится, "палка на двух концах" Либо делать топорно но
ice> быстро, либо красиво но медленно.

Поддерживаю. Именно так! Hе даром дядька Кнут говорил:

> Premature optimization is the root of all evil
>

и

> If you optimize everything, you will always be unhappy.
>

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

от: drbars
кому: All
дата: 30 Aug 2006
Hello, Dexus

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

от: elfh
кому: All
дата: 31 Aug 2006
Hello, drbars

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

от: Alex Astafiev
кому: All
дата: 31 Aug 2006
Hello, drbars

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

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

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

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

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

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

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

Файл: 35mhz.zip http://zx.pk.ru/attachment.php?attachmentid=3683

от: elfh
кому: All
дата: 03 Sep 2006
Hello, Raider

спасибо.

от: TomCaT
кому: All
дата: 05 Sep 2006
Hello, elfh

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

Файл: ffill.zip http://zx.pk.ru/attachment.php?attachmentid=3703

от: jim
кому: All
дата: 07 Oct 2006
Hello, TomCaT

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

Файл: Fill_2.tap.zip http://zx.pk.ru/attachment.php?attachmentid=3886

от: Alex Astafiev
кому: All
дата: 07 Oct 2006
Hello, jim

называется заливка с затравкой.

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

Файл: FILL1.txt http://zx.pk.ru/attachment.php?attachmentid=3890
Файл: FILL2.txt http://zx.pk.ru/attachment.php?attachmentid=3891
Файл: FILL3.txt http://zx.pk.ru/attachment.php?attachmentid=3892

от: Дмитрий Михайлович Горбунов
кому: All
дата: 07 Feb 2007
Hello, Raider

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




Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
WANTED - Розыск программ...
Список BBS - список BBS в Гродно.
Часть первая - А Чапай то прыткий гад...
Анкета - Вugsу.
IBM - IBM + Эмулятор = ZX Spectrum.

В этот день...   28 марта