Software render на Rust: переходим в 3d

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



Совсем простое и почти чисто прикладное описание можно найти тут, прочитав которое становится понятно что такое матрицы proj, view, world и зачем они нужны, а так же становится понятно как подвигать камеру или объекты на сцене. Подробнее про матрицы и вектора вообще рассказывает вот эта статья. Её стоит почитать хотя бы из тех соображений, что углубляться дальше не вспомнив что такое векторное и скалярное умножение векторов - не реально. Для тех, кто хочет понять почему матрицы проецирования именно такие, зачем нужны однородные координаты и почему вводят дополнительную координату w - расширенное чтиво.

Резюмирую описанное по ссылкам выше, обычно для проецирования треугольника используют 3 матрицы:

• mat_world - позиционирует объект на сцене
• mat_view - перемещает всю сцену так, что бы камера оказалась в начале координат
• mat_proj - выполняет проекцию точек, в рамках данной статьи - перспективную проекцию

В итоге после перемножения mat_proj * mat_view * mat_world на вершину треугольника (x,y,z,1) мы получим набор координат (x, y, z, w), причём такие, что для видимой на экране вершины будут выполнятся неравенства:
-1 < x/w < 1
-1 < y/w < 1
-1 < z/w < 1
соответственно (x/w, y/w) это экранные координаты вершины, если их масштабировать до размера экрана получим следующие неравенства:
0 < (x/w + 1) * screen_size_x * 0.5 < screen_size_x
0 < (y/w + 1) * screen_size_y * 0.5 < screen_size_y

Вот собственно и всё, получаем экранные координаты для всех 3 точек треугольника и рисуем как в предыдущей статье. Последнее неравенство с z по хорошему нужно использовать что бы отсечь треугольники и их части которые ближе near plane или дальше far plane, оставим это на потом, т.к. там есть нетривиальные моменты.

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

Таким образом для каждого рисуемого пикселя нужно знать его z координату. Просто взять и линейно интерполировать z координату получившуюся выше после умножения матриц на вершину - нельзя, а вот 1/w - можно, более того 1/w будет обратно пропорционален настоящей z координате пикселя. Т.е. фактически мы будем делать inverse-w-buffer. Подробнее про w координату, её смысл и что можно, а что нельзя интерполировать можно почитать тут.

Что бы от теории перейти к практике, нужна библиотека для работы с матрицами и векторами. Создание таковой несомненно полезная для общего развития работа и я её в своё время проводил. Но повторять ещё раз пожалуй не буду, т.к. полноценная реализация и тестирование это несколько полных дней, а хитрые и неочевидные баги будут вылезать ещё несколько недель, тем более разработка на малознакомом языке оставляет весьма мало шансов на то, что бы сделать код быстрым и качественным. Поэтому я решил довериться чужой разработке, а именно cgmath, тем более она судя по всему неплохо сделана и оттестирована кучей народа. А вот интерполяцию z координаты для буфера глубины делать пришлось, надеюсь получился понятный код.

Задавать координаты треугольников вручную, что бы нарисовать что-то осмысленное на экране - дело не благодарное, поэтому пришлось ещё делать загрузчик моделей. В качестве формата был выбран 3ds, он правда довольно устаревший и несовершенный, но очень широко распространён и поддерживается всеми основными 3d редакторами. Информации по тому, как он устроен, в сети великое множество, в качестве базы можно посмотреть на это (читать примерно с середины, пункт "7.5. Формат 3DS-файла") и это. Так же неплохо помогли исходники импорта и экспорта из blender, они на python и читаются замечательно. Более подробное описание интересующих чанков, легко находится в google по chunk id. Моя реализация сейчас поддерживает только часть спецификации, по мере необходимости я её буду расширять.

Одним из недостатков формата 3ds, является отсутствие там явного упоминания нормалей, но восстановить их не сложно, достаточно посчитать векторное произведение для каждого из треугольников. Вершины каждого треугольника при экспорте задаются таким образом, что cross product даёт нам всегда верное направление нормали (вот моя реализация).

Ещё пару слов о нормалях: их так же нужно умножать на матрицы преобразования, только в данном случае нам достаточно лишь mat_world умножить на нормаль, т.к. освещённость (для которой собственно нормаль в основном считается) от позиции камеры никак не зависит. И тут есть такой нюанс, если вершину мы дополняли 4-й компонентой = 1.0, то нормаль дополняется нулём, т.к. она является вектором и трансформации в виде перемещения к ней не применимы, напомню что подробнее про w компоненту, можно почитать по ссылкам, что я давал в начале статьи.

Имея нормали к треугольнику можно посчитать освещённость. Обычно оперируют 4 её компонентами: фоновой (ambient), диффузной (diffuse), зеркальный (specular) и исходящий (emission). Если фоновый цвет это обычно константа для модели, то для расчёта диффузной составляющей - уже применяют различные математические модели, простейшую и наиболее распространённую называют освещением по Ламберту. Отмечу, что косинус фигурирующий в формуле по ссылке, можно получить как скалярное произведение нормализованного вектора нормали и вектора направленного от освещаемой точки к источнику света. Если результат получился отрицательным то считаем что свет в эту точку не попадает и диффузный цвет в этой точке считаем равным нулю. Вот моя реализация вершинного и пиксельного шейдера по этой модели (да и если понятие шейдера вам незнакомо, вам сюда).

В результате получается следующее:

На этой низкополигональной модели отчётливо видны треугольники, т.к. цвет рассчитывался для каждого треугольника целиком, без каких-либо интерполяций. Однако если взять модель с примерно миллионом треугольников все будет довольно качественным:

И напоследок расскажу про несложную в реализации оптимизацию, позволяющую не рисовать лишний раз большую часть треугольников - это отброс нелицевых граней, на буржуйском называется "Back-face culling". Т.к. по хорошему растеризатор не должен знать ничего о нормали и о векторе камеры, то мы воспользуемся способом отличным от представленного в википедии. Будем считать, что камера находится в начале координат и направлена вдоль оси z, а спроецированные на экран вершины треугольника находятся на плоскости с координатой z = 1, хотя расстояние в принципе не важно, главное что бы не нулевое. Тогда мы можем составить матрицу из векторов направленных от камеры к точкам спроецированного треугольника: [[sx0, sy0, 1], [sx1, sy1, 1], [sx2, sy2, 1]], где sx и sy - это экранные координаты треугольника. Тогда определитель этой матрицы даст нам смешанное произведение этих трёх векторов, а его знак укажет на то является ли эта тройка векторов правой или левой. Практический смысл - находим определитель указанной матрицы и в зависимости от его знака рисуем или нет треугольник. Замечу, что этот метод работает только если вершины треугольников были экспортированы с одинаковым направлением обхода (в формате 3ds как раз это правило соблюдается). Получилось немного сумбурно, но к сожалению не нашёл подходящую ссылку с описанием.

Да и ещё немного впечатлений о rust:

• Я постоянно делаю какие-то оптимизации в движке, которые часто требуют например преобразовать массив одних типов в другой и т.п. вещи. На C++ подобные операции с указателями и приведениями типов делают элементарно, в Rust хоть и есть возможность сделать подобное, но нужные функции обычно глубоко спрятаны и плохо описаны. С одной стороны я понимаю почему так, а с другой сильно не хватает низкоуровневых возможностей.
• Система владения и время жизни объектов зачастую взрывает мозг. Хоть авторы и обещают, что через какое-то время программисты привыкают и чуть ли не удовольствие от этого получают. Но по началу очень сложно понять чего же от тебя хочет компилятор. Зачастую во вполне очевидных случаях требуется явно ограничивать области видимости, а то и вообще переписывать функции, что бы не было двойных изменяемых ссылок и т.п. вещей. Но как результат - вернуть ссылку на объект на стеке, который будет уничтожен - компилятор не даст и как следствие куча случайных ошибок подобного рода не возникают.
• Некоторые подсистемы явно сырые, например при чтении из файла фактически можно прочитать только массив из байтов, а дальше крутись как хочешь. И судя по всему вполне нормальным считается подход, когда потом из этого массива читают по 4 байта, с помощью сдвигов и сложений, с поправкой на big/little endian получают н-р 32-х битное число и конвертируют его во float например. В подсистеме буферизированного чтения вообще натолкнулся на явный баг, когда большие файлы не читаются до конца, а просто с какой-то позиции выдают мусор и пока не натолкнулся на issue искал ошибку у себя в коде. Что интересно ошибку закрыли, мол файлы больше 64К через этот класс читать не нужно. Хоть бы в документацию добавили упоминание!

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

Продолжение следует