Трехмерный рендер - финал (надеюсь)

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

Меня давно, практически с самого начала работы, беспокоила мысль о том, что игра жрет слишком много памяти под текстуры.
Было устроено все просто — все текстуры хранятся в одном большом атласе 2048*4096 в ARGB формате (просто большой вектор, который получается путем вызова bitmapdata.getVector()).
Текстуры хранились уже с наложенными лайтмапами, что заставляло копировать текстуры по нескольку раз (если у меня 10 ящиков с одинаковой текстурой, но разным освещением, хранилось 10 копий текстуры).
Зачитал инт из текстуры. Записал на экран. Молодец, свободен.
Все это изначально было сделано для скорости рендера, поэтому собирался с этим смириться.

Вот посмотрел я на текущую демку и подумал «А почему это уровень висит в пустоте? Непорядок, надо добавить стенки.»
Начал добавлять стенки и понял, что с трудом влезаю в атлас, а делать 2 атласа совсем не хотелось.
Что тут началось!!1 Истерика! Молодые годы потрачены впустую! Как жить дальше?!?!

Немного успокоившись (порубался несколько дней в QuakeII и Fallout:New Vegas) начал искать выход из ситуации.
Решение, собственно, простое. Разделить текстуры и лайтмапы в разные картинки и смешивать их при рендере.
Текстуры повторяются, а лайтмапы можно хранить в меньшем разрешении.
Раньше я такую штуку тоже пробовал, но смешивать для каждого пикселя три компоненты оказалось слишком медленно.

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

Итак, возникло решение проблемы.

Все текстуры уровня переводятся в индексированный 8-битный цвет и хранятся в тайлах 64*64 пиксела.
Все лайтмапы рендерятся в маленькое разрешение, тоже переводятся в 8-битный цвет, но со своей палитрой.
По двум палитрам считаем табличку 256*256 и рендер сокращается до 3 вычиток на пиксел (код цвета, код лайтмапа, значение из таблицы).
Лайтмапы еще дизерятся, чтобы хоть как-то сгладить низкое разрешение и маленькое количество цветов.

Попутно пришлось написать свой экспортер для статической геометрии тоже.
Потому что .obj не позволяет сохранять 2 текстурных канала, а .3ds (насколько я помню) экспортирует геометрию только в виде треугольников, что сильно ударило бы по производительности (если не писать свою объединялку треугольников во многоугольники).

Добавил стенки, оказалось, что камера постоянно в них упирается, пришлось добавить отступы и, чтобы было интересней, отступы заполнил «водой».
С водой тоже получилось интересно.
Тут долго рассказывать, но смысл в том, что воды нет :) Ложки нет, Нео.
Я имею ввиду, что она не рисуется отдельным проходом или чем-то подобным. Просто некоторые (подводные) полигоны рендерятся особо хитрым образом, так что наличие воды практически не повлияло на общую производительность.

После того, как определился со статикой, начал думать, как бы освещать пацанов.
Проблема в том, что если марин скрыт от лампочки за стенкой, на него не должен падать свет от этой самой лампочки.
Еще хотелось каким-то образом ускорить вычисление освещения, которое хоть и считается повершинно, но все же может подтормаживать, если лампочек много. 200 вершин на объект и 10 источников освещения дадут о себе знать.
Вот тут, кстати, камрады сетуют в комментах, что мои ковыряния после выхода молехилла окажутся ненужными. Совершенно согласен по части рендера, но если вы думаете, что молехилл будет решать за вас, когда и какие источники света включать/выключать, то вы заблуждаетесь. Все это придется делать самим :)

Надо считать Lighting Grid для уровня.

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

Поэтому для каждой клетки уровня я считаю просто коэффициент освещенности для каждого источника света с учетом удаленности и затененности.

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

Чтобы все было гладко и мягко, для каждой клетки (уровень 18*18 клеток) для каждого источника света (их 15 штук) считается 3375 лучей.

Считается все просто:
0. Цикл по всем источникам света.
1. Цикл по всем клеткам (cx, cz).
2. Запускаем 3 вложенных цикла по 15 повторений (dz, dy, dx).
3. Получаем точку внутри клетки (x = cx*64+32+(dx*4), y=...) и так далее.
4. Проверяем дальность от точки до источника света.
5. Если далеко — выходим, иначе бросаем луч от точки до источника через геометрию уровня.
6. Если не было пересечений — добавляем вклад с учетом освещенности от этого источника в текущую клетку.
7. Усредняем.

Сначала сделал все это на AS3, но когда за полчаса посчиталось только ~10% от общего объема, начал искать другие решения.

Вспомнил, что haxe может компилироваться в нативный бинарник.
Полгода назад смотрел эту фичу, показалось прикольной, но ненужной. Сейчас вот пригодилось.
Быстренько переписал все на haxe.
Пришлось поковыряться с настройкой ( blog.touchmypixel.com/2009/04/our-possible-haxe-c-plans/ ), попутно нашел глюк в АПИ (отписал багрепорт) и снова поупражнялся в написании кода без отладчика (кажется я уже привык к этому).
В итоге за 15 минут все просчитывается, причем с тупым брутфорсным перебором.
Надо будет, конечно, добавить дерево, чтобы не проверять лишние треугольники, но это потом.

Дальше все просто.
По координатам объекта определяем клетку. Делаем билинейную интерполяцию коэффициентов (чтобы при переходе из клетки в клетку освещение изменялось мягко), если коэффициент больше нуля, добавляем в список источников, которые действуют на данный объект.
В среднем на объект действуют 2-3 источника, так что расчет происходит довольно быстро.

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

Демка тут: megaswf.com/serve/102077/, наверное, получилась слишком темная, но это поправимо.
Может глючить, если вылететь за стенки или сильно задрать камеру.
Кстати, отпишитесь про fps, пожалуйста. У меня ~38-45.