Описание идеи тайлового 3д рендера
Как и обещал в твиттере, пишу небольшой отчет про очередную попытку сделать софтварный рендер.
Вообще, подход не идеальный, но я давно хотел его попробовать и для одного конкретного проекта, который я сейчас делаю, более-менее подходит.
Чтобы начать, вкратце рассмотрим как работает «обычный» сканлайн-рендер с z-буфером:
0. Выделяем кусок памяти размером с экран (один раз, при инициализации)
1. Чистим z-буфер и экран каким-то образом. Или не чистим, но это уже оптимизации.
2. Идем по полигонам.
3. Каждый видимый полигон рисуем на экран одновременно обновляя z-буфер.
Как выглядит самый внутренний цикл отрисовки (полупсевдокод):
1. Чтение z-буфера
2. Запись z-буфера, если прошли z-test
3. Чтение текстуры
4. Запись цвета во фреймбуфер (на экран), если прошли z-test
У данного подхода есть следующий недостаток — даже если мы рисуем один выпуклый объект (convex), например, куб или сферу, приходится читать и писать z-буфер. Хотя понятно, что тест всегда будет проходить, а записываемые данные никогда не будут прочитаны.
Вот, собственно, с данным недостатком я и решил побороться. Пока еще на стадии proof-of-concept, но все-таки.
Идея заключается в следующем:
1. Разбиваем экран на полоски 16*1 пикселей (такой размер выбран, чтобы совпадал с периодом перспективной коррекции. Она тоже у меня делается каждые 16 пикселей).
2. В каждой полоске храним список всех полигонов, которые хоть одним пикселем в нее попадают. Это определяется на этапе растеризации. То есть при отрисовке полигона определяются полоски, в которые он попадает и в каждую добавляется «ссылка» на полигон. Чтобы было ясно — на экран пока ничего не записываем.
3. Растеризуем каждую полоску, примерно так, как обычно.
В чем профит?
Казалось бы, рендер просто делает лишнюю работу, но тут есть нюанс :)
Картинка для привлечения внимания:
На это картинке зеленым подсвечены области экрана где z-буфер не нужен. Соответственно, красным — где нужен.
Как это определяется?
Определяется это элементарно — если на полоску претендует только один полигон — z-буфер не нужен, и, соответственно, количество операций во внутреннем цикле (см. выше) сокращается вдвое.
Вот эта оптимизация это только половина метода.
Самое интересное это «красные» области.
Здесь надо сделать замечание, что не все операции в виртуальной машине одинаковы по скорости. Конкретно операции с памятью (даже быстрой) намного(!) медленнее, чем операции с регистрами (их обычно называют локальными переменными, но это не совсем верно). Причем локальный массив еще более тормозная штука, чем быстрая память.
Ну так вот, когда рендер приходит на красную полоску ему в любом случае нужен z-буфер. Можно, конечно, каким-то образом разрезать полоски геометрически, но этим я пока не занимался.
Итак, идея номер два — хранить z-буфер полоски в регистрах.
Поскольку рендер обрабатывает полоски последовательно, размер z-буфера константный и равен 16 регистрам (интов или флоатов).
Соответственно, алгоритм такой:
1. Приходим на красную полоску
2. Зачищаем 16 регистров
3. Рендерим все кусочки полигонов, которые входят в эту полоску, в качестве z-буфера используя регистры. Запись на экран прямая, не увидел пока смысла буферизовать еще и фреймбуфер.
Вот тут есть одна засада. Фактически, z-буфер представляет собой 16 локальных переменных, который начинает с адреса кратного 16:
К сожалению, индексный доступ к регистрам в опкодах виртуальной машины не предусмотрен, но делать что-то надо. И решение классическое — codegen.
Всего у нас получается 16 возможных смещений и 16 длин, что дает 256 вариантов минус невозможные. Насколько я помню, вроде 136 вариантов, но могу ошибаться.
Вот, если интересно, небольшой кусочек сгенерированного кода: gist.github.com/ryzed/5193061
Это на самом деле небольшой кусочек, полный файл содержит примерно 6000 строк. Хоть код и кажется ужасным и громоздким, но все работает вполне быстро.
Недостатки
Очевидно, что не все так гладко, как хотелось бы. Беда пришла откуда не ждал.
Полосок на экране много, в каждой полоске может быть много ссылок на полигоны и чтобы нарисовать кусок полигона в полоске — надо из ссылки на полигон выдернуть градиенты (z и текстурные). Даже если вытаскивать только этот необходимый минимум — для каждой ссылки в каждой полоске надо вычитывать 9 флоатов из памяти, что, фактически, убивает большую часть профита.
Пока эта проблема решается кэшированием последних прочитанных градиентов, но думаю тут можно найти более интересное решение.
Вроде все.
Ссылка вот: gametrax.eu/game/8ef478c4f5
Летать как обычно (стрелки и мышь), если потыкать мышью в колонны — они разваливаются, backspace — рестарт.
Вообще, подход не идеальный, но я давно хотел его попробовать и для одного конкретного проекта, который я сейчас делаю, более-менее подходит.
Чтобы начать, вкратце рассмотрим как работает «обычный» сканлайн-рендер с z-буфером:
0. Выделяем кусок памяти размером с экран (один раз, при инициализации)
1. Чистим z-буфер и экран каким-то образом. Или не чистим, но это уже оптимизации.
2. Идем по полигонам.
3. Каждый видимый полигон рисуем на экран одновременно обновляя z-буфер.
Как выглядит самый внутренний цикл отрисовки (полупсевдокод):
while (adr < eadr)
{
if (Memory.getI32(adr) < z)
{
Memory.setI32(adr, z);
// тут читаем текстуру и определяем цвет
// тут кидаем на экран
}
// шагаем на следующий пиксел
u += du; v += dv; z += dz; adr += 4;
}
1. Чтение z-буфера
2. Запись z-буфера, если прошли z-test
3. Чтение текстуры
4. Запись цвета во фреймбуфер (на экран), если прошли z-test
У данного подхода есть следующий недостаток — даже если мы рисуем один выпуклый объект (convex), например, куб или сферу, приходится читать и писать z-буфер. Хотя понятно, что тест всегда будет проходить, а записываемые данные никогда не будут прочитаны.
Вот, собственно, с данным недостатком я и решил побороться. Пока еще на стадии proof-of-concept, но все-таки.
Идея заключается в следующем:
1. Разбиваем экран на полоски 16*1 пикселей (такой размер выбран, чтобы совпадал с периодом перспективной коррекции. Она тоже у меня делается каждые 16 пикселей).
2. В каждой полоске храним список всех полигонов, которые хоть одним пикселем в нее попадают. Это определяется на этапе растеризации. То есть при отрисовке полигона определяются полоски, в которые он попадает и в каждую добавляется «ссылка» на полигон. Чтобы было ясно — на экран пока ничего не записываем.
3. Растеризуем каждую полоску, примерно так, как обычно.
В чем профит?
Казалось бы, рендер просто делает лишнюю работу, но тут есть нюанс :)
Картинка для привлечения внимания:
На это картинке зеленым подсвечены области экрана где z-буфер не нужен. Соответственно, красным — где нужен.
Как это определяется?
Определяется это элементарно — если на полоску претендует только один полигон — z-буфер не нужен, и, соответственно, количество операций во внутреннем цикле (см. выше) сокращается вдвое.
Вот эта оптимизация это только половина метода.
Самое интересное это «красные» области.
Здесь надо сделать замечание, что не все операции в виртуальной машине одинаковы по скорости. Конкретно операции с памятью (даже быстрой) намного(!) медленнее, чем операции с регистрами (их обычно называют локальными переменными, но это не совсем верно). Причем локальный массив еще более тормозная штука, чем быстрая память.
Ну так вот, когда рендер приходит на красную полоску ему в любом случае нужен z-буфер. Можно, конечно, каким-то образом разрезать полоски геометрически, но этим я пока не занимался.
Итак, идея номер два — хранить z-буфер полоски в регистрах.
Поскольку рендер обрабатывает полоски последовательно, размер z-буфера константный и равен 16 регистрам (интов или флоатов).
Соответственно, алгоритм такой:
1. Приходим на красную полоску
2. Зачищаем 16 регистров
3. Рендерим все кусочки полигонов, которые входят в эту полоску, в качестве z-буфера используя регистры. Запись на экран прямая, не увидел пока смысла буферизовать еще и фреймбуфер.
Вот тут есть одна засада. Фактически, z-буфер представляет собой 16 локальных переменных, который начинает с адреса кратного 16:
// clear zbuf
var z0:Int = 0; var z1:Int = 0; var z2:Int = 0; var z3:Int = 0;
var z4:Int = 0; var z5:Int = 0; var z6:Int = 0; var z7:Int = 0;
var z8:Int = 0; var z9:Int = 0; var z10:Int = 0; var z11:Int = 0;
var z12:Int = 0; var z13:Int = 0; var z14:Int = 0; var z15:Int = 0;
К сожалению, индексный доступ к регистрам в опкодах виртуальной машины не предусмотрен, но делать что-то надо. И решение классическое — codegen.
Всего у нас получается 16 возможных смещений и 16 длин, что дает 256 вариантов минус невозможные. Насколько я помню, вроде 136 вариантов, но могу ошибаться.
Вот, если интересно, небольшой кусочек сгенерированного кода: gist.github.com/ryzed/5193061
Это на самом деле небольшой кусочек, полный файл содержит примерно 6000 строк. Хоть код и кажется ужасным и громоздким, но все работает вполне быстро.
Недостатки
Очевидно, что не все так гладко, как хотелось бы. Беда пришла откуда не ждал.
Полосок на экране много, в каждой полоске может быть много ссылок на полигоны и чтобы нарисовать кусок полигона в полоске — надо из ссылки на полигон выдернуть градиенты (z и текстурные). Даже если вытаскивать только этот необходимый минимум — для каждой ссылки в каждой полоске надо вычитывать 9 флоатов из памяти, что, фактически, убивает большую часть профита.
Пока эта проблема решается кэшированием последних прочитанных градиентов, но думаю тут можно найти более интересное решение.
Вроде все.
Ссылка вот: gametrax.eu/game/8ef478c4f5
Летать как обычно (стрелки и мышь), если потыкать мышью в колонны — они разваливаются, backspace — рестарт.
- +10
- ryzed
Комментарии (2)