Если б тайлы были чуть больше тайлами. Выход за границы наивного представления

    image

    Тот кто когда-нибудь задумывался о том как работает графическая часть 2д ретро ускорителя, примерно представляет как именно она рисует эти пресловутые Tiles, которые к слову из определения не обязаны быть прямоугольными. Тайлинг это про замощение плиткой. Да чаще всего разработчики железного апи понимают это и методы соответственно называют drawRect а не drawTile. Любой прямоугольник действительно может быть тайлом, но обратное не верно! И тут назревает вопрос: Почему 2D ускорители упорно ускоряют только rect… Простой ответ на этот вопрос потому что все остальное слишком сложно для простой железки. Но тут я бы и поспорил. Можно предложить как минимум одно простое, но очень функциональное расширение этой базовой абстракции, следующее.

    Я давно не писал на Хабр. Потому что все время хотелось сделать идеально… есть у меня такая болезнь. Сам Хабр тем временем ощутимо снизил планку, а я все не пишу да не пишу. Поэтому сегодняшняя статья родившаяся без подготовки из просто беседы с другом. Однако есть такие друзья с которыми хочется беседовать глубоко и обстоятельно.

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

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

    Итак начнем…

    Рассмотрим для образца общую функцию копирования произвольной прямоугольной области. Видим что это просто двойной цикл по строкам и по элементам строк:

    image

    Заметим, что этот блок кода обычно тривиально повторяют в х4 комбинациях направлений обхода обоих циклов для реализации Отражений:

    image

    Еще х2 комбинаций дает перестановка порядка на dst[x][y] отражая по оси y=x.
    Попутно эти 8 вариантов отражений являются всеми возможными поворотами кратными 90гр со всеми их зеркальными отражениями слева направо.

    А теперь посмотрим на то, как еще минимальными добавлениями можно было бы сильно видоизменить данный базовый элемент.

    Возможно никому не приходило это в голову, но почему тайл не может быть например параллелепипедом? Забегая вперед скажу, что это расширение носит минимальные накладные расходы, потому что для реализации этого необходимо добавить всего пару инкрементов на строку:

    image

    В результате комбинации с x/y перестановкой мы получим параллелепипед парой сторон всегда ориентированных по одной ортогонали, а две других будут под углом. Что же нам дает эта дешево полученная мелочь? Ну во первых возможность использовать три фиксированные проекции:

    image

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

    image

    Так и для построения стен в пространстве изометрических проекций:

    image

    И помним, что говоря дробные это не означает непременную поддержку float! О чем современный избалованный программист порой начинает забывать. float это дробные с Плавающей точкой, а тут она совершенно не нужна. “Поддержкой” же дробных с фиксированной точкой (fixed point), обладает Аппаратно по сути любой процессор имеющий сдвоенные регистры, где верхний из пары может читаться как отдельное значение. Более того в этом случае НИ одной лишней инструкции не добавиться. (Ну за исключением того что задаваться наклон будет в 256-ых долях) Так что это все бесплатно, берите ребята!

    Еще один аналогичный шаг который попроситься по индукции у внимательного читателя, это повторение этого функционала ко второй границе перебора внутреннего цикла. Мы ведь можем отдельно развязать приращение end. И тогда в общем случае мы сможем рисовать любые лежащие основанием на одной из ортогоналей трапеции (как частный случай треугольники):

    image

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

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

    Было бы здорово иметь для них аппаратную поддержку на ускорителе:

    image

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

    Той же парой вызовов отрисовки можно составить любой не ограниченный частностями треугольник (он просто сечется на два ортогональной линией по средней точке, это очень похоже на его классический алгоритм отрисовки) И из этого уже можно строить построения в перспективе. Кстати из самих трапеций например элементарно дешево получается вертикально фиксированная 3D проекция DOOM1 вида:
    image

    При желании можно пробовать рисовать заливкой даже что-то более менее крупно-воксельное. В зависимости от степеней свободы проекции затрачивая больше или меньше вызовов отрисовки. Первые две перспективные проекции ниже являются фиксированными однако каждая из них имеет 4 симметричных представления — итого 8 углов отображения. Третья является общим случаем и фиксирована только вертикально. Вращаясь вокруг вертикальной оси она будет попеременно переходить то в первую, то во вторую:

    image

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

    Выполнение на бонусном функционале перспективного текстурирования в этих вызовах, возможно, но требует реализации дробного скейлинга и связано с внесением дополнительных коэффициентов расхождения при src, и коэффициентов прореживания, которые пуще того необходимо будет раз это 3D довольно криво рассчитывать в динамике, что не целесообразно для данной простой архитектуры.

    Ну и заканчивая реванш перед Хабром за свой собственный интерес, я все же не удержусь кратко пояснить откуда берется вся эта магия коэффициентов приращения алгебраически. Формула прямой y=kx+b которую учат в школах, передает нам здесь привет сразу дважды. Все коэффициенты пригодились на своих местах:

    image

    Почему же мне не встречались аппаратные 2д ускорители с такой реализацией тайлов, я могу лишь гадать:

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

    Средняя зарплата в IT

    110 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 8 550 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 22

      +3
      Четырёхугольные спрайты-полигоны были реализованы в 3DO, Sega Saturn, в некоторых аркадных автоматах и в видеокарте NVidia NV1.

      Mode7 никакого отношения к перспективе сам по себе не имел, по сути это всего лишь один составной спрайт (тайловая карта), который можно вращать и масштабировать. Его нельзя было наклонять или двигать отдельные углы. Это достигалось уже программно, изменением параметров вращения и масштаба на каждой строке растра таким образом, чтобы в эту строку попала нужным образом повёрнутая и растянутая строка исходного спрайта — как бы построчная растеризация полигона.
        0
        Да я писал его на высоком уровне по приколу. Но на сколько я узнавал исторически. На консолях это был специальный режим рисования спрайта, который аппаратно брал на себя ускорение конкретно афинных преобразований. Этого хватало только для поворота, масштаба и сдвига. Потому оси X и Y вращать было можно, — это есть в афинных. А вот Z нету, и ни как виртаульно она не добавлялась. Впрочем прямого управления ею нет в большинстве 3д игр. Перспектива же добавлялась хаком нарезания полос, но не обязательно только по строкам растра, иногда даже по несколько строк одним ректом, в зависимости от требований скорость/качество. Чем ближе была полоса, тем больше зум. А в консолях шел этот режим за номером семь. Я вспомнил его здесь как пасхалочку для знатоков.

        Нашел сейчас его у себя в загашниках, но версию с классическим MODE7 для поворота/наклона/смещения положенного в перспективу пола деплоить лень (она не тема этой статьи и для интересующих это гуглиться) Зато могу задеплоить бенчмарк, который как раз не тривиально использует наклон:

        codepen.io/impfromliga/full/qBNomVO
        Скрол меняет угол наклона в поверхность.
        Дополнительно колесо мыши меняет «скважность» полос для теста скорость/качество
        Очень наглядно видно насколько большими полосами можно было относительно качественно эту перспективу хакать.
          +2
          А в консолях шел этот режим за номером семь.

          Всё же всего на одной консоли, SNES. Схожий функционал в GBA и Sega CD имеет свои номера (2 на GBA и никакого на Sega CD). Mode 7 просто стало именем нарицательным для перспективной проекции а-ля трасса в F-Zero, это название использовалось в рекламных материалах (на коробке с игрой) и потому ушло в народ, не особо разбирающийся в технических деталях.
            0
            Да я понимаю что нарицательным, сам его так же использую, потому что keyword гуглиться. Просто лично его не застал, не достаточно олд я…
            Хотя при анализе приема, для чего писался бенч, — Возможности этого режима позволят рендерить не только пол/небо, но даже что-то вроде DOOM1 like рейкастинга, теоретически. Только кастить надо будет интеллектуально, что бы получать углы стен.

            — Кстати нужно заметить что HTML5 Canvas окружение без webGL является по сути тем же окружением. Встречал на этом алгоритмы развертки сферической панорамы в проекцию 3д камеры. Что бы сделать как в yandex панорамах. Как один из fallback'ов для неподдерживающих ничегошеньки устройств. Причем на CSS2 то же есть реализации, но суть не меняется — Суметь нарезать кривое на плоское
              0
              Я могу говорить только за реальный Mode 7 и SNES, т.к. знаю, как они работают и что с ними делать. За абстрактный программный Mode 7-подобный рендер сказать ничего не могу, т.к. его можно сделать каким угодно. Оригинальный же Mode 7 позволил бы рендерить стены а-ля Wolf 3D только если положить телевизор на бок, т.к. мы можем менять параметры рендера каждую строку (через HDMA), но никак не можем менять их каждый столбец.
                0
                Ахахах, сразу видно единомышленника…
                — Когда я размышлял как успеть выдать рейкастинг с микроконтроллера софтверно синтезирующего VGA сигнал, при том что памяти на экранный буфер у него нет, но есть на строки, в которых паузы пока возваращается луч в развертке 20% времени… И хотя нужно гораздо больше, можно подготавливать строку отложенно, пока предыдущая подготовленная пуляет копии.

                Но телевизор на бок все таки прийдется положить…
                Человечество просчиталось… развертку надо было делать сначало по строкам.
                Так и горизонтальное разрешение было бы выше — что полезно и для шрифта.
                Хотя сейчас можно найти дисплеи с возможностью поворота изображения на бок.

                — возможно по этим же причинам (ход луча) на SNES апи было горизонтально ориентированным…
        +3

        фиксированная точка => fixed point, а не strict point.

          0
          точно! спасибо
          0
          Можно узнать а зачем вы хотите нарезать квады на трапеции?
            0
            Вроде же в статье обьяснил. Или вам интересно конкретно зачем я хочу их нарезать? Но это тогда не корректный вопрос — Just we can, как говориться. Но могу ответить о практическом применении.

            В действительности статья с практической т.з. слегка запоздала. Лет так на 50, во времена ZX Spectrum, когда набирали популярность видео ускорители. Она больше как «развлекательная математика». Однако, если постараться то практическое применение и кроме «разминки для мозга» этому еще можно найти:
            — ПЛИСы для собственных задач графической отрисовки.
            — Микроконтроллеры БЕЗ графического ускорения.
            0
            Рассмотренные вами варианты сводятся к задаче заливки треугольника или отображения одного треугольника в другой. Но аппаратная реализация этих функций и стала тем, что впоследствии назвали «3D ускоритель».

            Первые 3D-ускорители специализировались именно на маппинге текстур, т.е. отображении текстуры из одних треугольников в другие. Потом уже появились прочие плюшки, такие, как интерполяция, расчёты проективной геометрии, Z-buffer, шейдеры и т.д.

            Мне в своё время пришлось прибегать к средствам 3D-графики для создания двумерных анимаций. Хорошо легли на маппинг текстур такие задачи, как повороты на произвольный угол, изменение масштаба.
              0
              Сейчас ясно что все сводят к треугольникам. Но я тут про 2D ускорители и алгоритмическую сложность. То что задача заливки треугольника сводиться к описанным двум трапециям я упомянул. А не наоборот! Достаточно вспомнить классический алгоритм заливки треугольника. (см. compgraphics.info/2D/triangle_rasterization.php ) Потому более гибким вариантом 2D апи будет, — иметь ускоритель трапеции. Не говоря уже о том, что она рендериться эффективнее.

              А треугольник современный, это вообще другое! Он учитывает перспективу при текстурировнии. Т.е. у его вершин есть глубина! И это сразу привет 4х4 матрицы! Кстати как тут уже обсуждалось, матрицы в 2D таки приходили (см. SNES Mode7), но только Афинные 3х3 (можно и 2х3, норма на плоскости довольно бесполезна).

              И подводя итог про апогей 2D функционала ускорителей:
              — На мой взгляд он почему-то не наступил. Может из-за того, что поддержка более ресурсозатратных треугольников просто пришла раньше.
              0
              Было бы интересно глянуть на софтверный движок, манипулирующий такими тайлами. Нынче развелось много фантазийных консолей, вроде PICO-8, TIC-80 и иже с ними, где эта тема представляет изрядный интерес.
                0
                Да, это тоже применение. Но сам движ консоли не обязательно писать на проце… Его можно просто завернуть в такое апи. С прицелом если такая консоль решиться переезжать в железо, там будет легко это поддержать. Тут в практических целях от барметал практически не отвязаться.
                0
                Все же уточню свой вопрос:
                1. Вся отрисовывемая карта состоит только из паралеллепипедов?
                2. Поворот камеры производится в реальном времени на произвольный угол?
                3. Это будет чистая изометрия или все таки перспективная проекция?
                4. У паралеллепипеда можно наблюдать от одной до трех сторон (горизонтальная, фронтальная, саггитальная). Предположим что для каких то движений камеры рендеринг одной из сторон оптимизировали, что там с оставшимися сторонами? Как их выводить, 3D-полигонами?
                  0
                  1. На скрине из демки? — да. Только там оно не выводиться на процессоре.
                  2. Эта крутиться на 8 углов. (почти точных). Версию с произвольным углом выпилил, там проверялся другой концепт. Если посмотреть, там хитро стоит камера, что 3й этаж совпадает с регулярной сеткой первого. Это что б оно с танцами, но переносилось и на «прямоугольные» ускорители.
                  3. «ЭТО» уже есть. Демка весьма опосредованное отношение имеющая к сути данной статьи.
                  4. Зависит от того что выводить и что доступно для оптимизации. Плоскости с такими названиями у вас сохранятся только в фронтальной перспективной проекции (одноточечьной) поворот камеры у нее будет строго зафиксированным по ортогональным осям. Это как в первых 3D рогалках с поворотом строго на 90гр. Если двухточечную перспективу делать, то фиксированной останется одна ось (обычно вертикальная). А плоскости утратятся: Фронтальная потеряет свойство перпендикулярности камеры и вывести ее только скелингом уже неудастся. Однако вместе с саггитальной они сохранят свойство параллельности вертикали. Это позволяет выводить их методами на подобии mode7. Или если говорить о барметал использовать обрезанные матрицы (с читерской Y составляющей, которая всегда будет равняться 1). Но горизонтальная плоскость потеряет любую параллельность экранным ортогоналям, и выводить ее с текстурированной будет трудно. Mode7 прийдется резать вобще на кубики вместо полосок и это будет еще корявее…

                  Описанное мной в статье НЕ для перспективного текстурирования. А для разного рода текстурированных Изометрий привлекательно. Про полноценность 3D топить не надо. Изометрия это пространство 3х измерений. Просто с отсутствием искажений размеров по Z.
                  Более того она вполне законно существует в реальности — у Снайпера на дальние дистанции практически исчезает перспективный эффект. У фото съемок со спутника тоже практическая изометрия.

                  В принципе если вам очень нужно искажение размеров по Z используйте паралакс, на слоях рисуемой в глубину top-down проекции. Но у нее фиксированый 90гр поворот вертикальной оси. Это то как рисовалась «формулы 1». Но это единственная проекция которую можно вывести с текстурированием и перспективой. Важно указать, что «перспектива» здесь будет только относительно размеров обьектов, но не их граней относительно друг друга. Потому в такой проекции нет особого смысла рисовать грани отдельными вызовами. С трапециями можно было бы пробовать cavalier проекции. слегка в нахлест кубами класть. И скалировать слои в глубину. Если что глядите тут
                  0
                  Для 8 фиксированных углов изометрии целесообразно использовать 8 фиксированных спрайтов на каждую грань. Это увеличит расход ОЗУ в 8 раз.

                  Спрайт можно назвать частным случаем текстуры, когда пиксели копирются на экран один к одному. Если вы собираетесь мапировать текстуру более сложным способом, то в пределах одной строки растра может происходить происходить как масштабирование строки текселей, так и непоследовательное чтение из памяти (UV координаты). И то и другое наводит на мысли о фильтрации: NearestNeigbor, Bilinear и прочие.
                    0
                    — для поверхностей я на них обходился одним! — Для персонажей двумя.
                    поверхности задеплоены — codepen.io/impfromliga/full/pKgwjd
                    — рисовать на процессоре что то перспективное с текстурированием, РЕЗКО увеличивает сложность алгоритма и его ресурсозатратность, потому почти наверняка НЕ рационально.
                    Все это надо делать уже на нормальном GPU.

                    Самый распространенный алгоритм применявшийся для перспективного 3D рендеринга известный мне это т.н. scanline. На нем был Дюк. И это просто верх. Особо много на нем не вытащить даже на нынешних CPU. Есть еще отдельный вид воксельный рейкастинг, самое показательное развитие этого метода — Ace of Spades но он уже без текстур
                      +2
                      На нем был Дюк. И это просто верх. Особо много на нем не вытащить даже на нынешних CPU.

                        0
                        если это без GPU, то оно прекрасно. Но все-таки надо сказать что это не много. Хотя я понимаю на сколько шедеврально оно выжимает!
                    0
                    Вижу несколько варианта спрайтов для стенок. Либо мапирование текстуры по разным осям UV, и в разных направлениях. Кстати, последовательное чтение из памяти на современном железе оптимизировано, происходит гораздо быстрее непоследовательного.
                      0
                      это все спички по сравнению даже с webGL. У CPU есть сильные стороны ввиду возможности реализовывать последовательные прогрессивные алгоритмы, сканлайны, скользяцие окна, но это все очень потно и кастомно, я уже отыгрался. Сейчас относительно 3D интересует как раз таки webGL. Он кстати тоже довольно ограниченный. Но в какой то мере становиться вездесущим графическим окружением. Вместо исчезающих ретро консолей. По части ретро консолей, интересно смотреть в сторону новых разработок. Сказать по честному сейчас на каких-нибудь STM32F7 можно ТАКОЕ сделать, в сравнении с чипами древности… Я жду что явление вируальных консолей кто нибудь разовьет в сторону аля-ардуино (но лучше не оно а STM32 / ESP32)

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

                    Самое читаемое