Я хотел бы поделиться воспоминаниями о своих попытках сделать «3D графический движок» «своими руками» практически в до-интернетную эпоху (он как бы уже где-то там конечно был, но у меня его фактически не было). Никакую Америку открыть не удалось, революции тоже не случилось, но было много старания, мучений и фана. С годами память о многих событиях стирается, исчезают детали, тускнеют впечатления — при многочисленных переездах коробка с дискетами были потеряна и никаких артефактов от описываемых событий не осталось.

Предыстория

Последние 4 года школьной учебы прошли в омской физматшколе, где ребенка (кроме физкультуры и матершины), научили языку C, что, наложившись на интерес к графике в играх, позволило писать что-то самому, пробуя реализовать то, что видел в играх того времени. 2D графикой удивить уже было сложно, но вот Wolf 3D поставил меня на некоторое время в тупик. Кто-то из старших товарищей произнес «да там все на столбиках», и это позволило сдвинуться с мертвой точки. Потом я понял, что алгоритм Брезенхема можно применить к масштабированию столбика изображения и какая-то пародия на Wolf3D начала получатся. Я совершенно не стремился создать что-то играбельное (какая пошлость!), мне нравился сам процесс реализации графических алгоритмов, то ощущение, что ты знаешь как это сделано и можешь это сделать. На выпускных экзаменах я выбрал сдавать информатику и представил «теоретическую» часть учителям, сильно удивил их наличием практической. Но за неделю до экзамена я увидел Descent — настоящая трехмерная игра с текстурами. Это было что-то невозможное, я знал что существует 3DS, но там чтобы отрендерить мультик нужна уйма времени, а тут летало прямо на глазах.

На выпускном, вместо того, чтобы бухать, как все нормальные дети, обсуждал с друзьями Duke Nukem (он тоже столбиковый), который мне очень нравился своим юмором и разнообразием. И тут один парень сказал мне «посмотри Quake». Когда я посмотрел кваку, я решил, что хватит это терпеть, так нельзя, это настоящая 3D графика, никакие не столбики — и я совершенно не понимаю как это сделано.

Я умел в геометрию

Сейчас можно найти любую информацию за 5 минут, но что делать тогда? Книжки по 3D графике у меня были, но они не проясняли нужный вопрос нисколько. В «думе» все грани превращаются на экране в трапеции, натягивание текстуры делается растяжением столбиков. Но при этом я упустил из виду, что по горизонтали возникает нелинейность, и на самом деле картинка в думе не полностью реалистична. Так я пропустил мимо главный принцип 3D графики, открытый еще Ньютоном — "линеаризуй это". Что станет источником всех последующих проблем и метаний.

Раз мы уже умеем рисовать трапеции, давайте «нарисуем» на экране каждую треугольную грань. Да, ее нельзя закрасить столбиками, но ведь геометрия — вещь не очень трудная, давайте через каждый ее пиксель экрана пропустим из камеры луч и найдем где он пересекает грань. Это же практически трассировка лучей, только облегченная! Любой студент напишет эту формулу за 5 минут. Уравнение прямой:

$$

где $$, $$ это координаты пикселя на экранной плоскости, $$ это расстояние от камеры до экранной плоскости (камера в нуле системы отсчета), $$ — параметр
Уравнение плоскости:

$$

где n это нормаль, тогда параметр (а значит координаты) легко найти:

$$

Ну как легко, пожалуйте в царство боли делений. Компьютер хорошо складывает, сносно умножает (это ведь не более чем сложения и сдвиги), но деление… Деление на моем Pentium занимало 46 тактов. Даже если 320 на 200, даже если ничего более, то на каждый кадр надо 3 миллиона тактов. А моего пенька их всего 100, значит быстрее 30 фпс не получить в принципе. А если разрешение увеличить в 2 раза? 7 фпс? Но малолетнего энтузиаста это не смутило.

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

1. решить, стоит ли рисовать грань в этом пикселе, или ее перекроет другая грань
2. найти текстурные координаты

Сортируй дерево

Конечно, про Z-буфер я знал. Но поверьте, 99% людей, которые знаю Z-буфер, представляют его себе неверно, точно так же как неверно представлял его себе я (будет пояснение). В любом случае, я хотел избегать лишних вычислений (уж больно тяжелы деления), потому решил применить другую технику, вычитанную в книжке — деревья бинарного разбиение пространства, они же BSP-tree. Я всегда любил деревья, метод сортировки деревом всегда завораживал меня своей магией, а тут была его вариация — я отлаживался 8 часов непрерывно, но смог!

Метод позволил отсортировать грани (при этом некоторые грани разрезались на части) так, что при отображении сначала рисовались «ближние» грани, потом дальние. Потому если при рисовании грани я видел, что пиксель уже занят, то можно смело переходить к следующему пикселю, проблема порядка решена, осталось натянуть текстуры.

Клеим обои текстуры

U,V координаты? Нет, не слышал. Но не стоит осуждать меня, вы ведь, когда клеите обои то же о них не думаете. Вы думаете что вот у вас один край обоев (вектор горизонтали текстуры), вот у вам другой край обоев (вектор вертикали текстуры), вы их накладываете на стену! Так и я, для каждой грани заводил 2 вектора для краев текстуры и зная точку пересечения, находил координаты внутри текстуры.

Нам нужен сюжет и эффекты

Рендеринг заработал, хотя и не быстро, но заработал! Я смог в 3D графику! Но что мы будем рендерить? Нам нужен какой-то сюжет, какие-то модели, нужен какой-то звук.

Ходилка или леталка? Ходилка это пошло и не дает почувствовать всех 3D красоты, однозначно леталка! Будет наш Descent.

Я сделал платформу, поставил на нее несколько зданий, натянул на них текстуры с окнами, сделал фонтанчик из граней (казалось что это круто). Чем мы будем стрелять? В квейке стреляли гвоздями, это было не круто. По какой-то неизвестной культурологам причине в тот момент было популярно слово «болт» (который надо забивать), и я понял, что стрелять мы будем болтами — правда выяснилось, что это были винты — шлицы очень красиво смотрелись на вбитых в здание «болтах».

Враг? Ну я не мог сделать модельки людей, я сделал… летающую машину скорой помощи, практически кубическую, лишь немного наклонил ей лобовое стекло. Зато текстур сэкономил.

Звуки. Звуки выстрелов и взрывов и вопль I got a flying machine я взял из варкрафта, саундтреком пустил акустический The man who sold the world — сам-то я слушал металлику, но пожалел родителей, которым приходилось вечерами слушать одно и тоже, пока я отлаживался.
В Windows 95 звуки не микшировались, но вот она, польза университета, преподаватель рассказал мне о многопоточности и я написал микшер в отдельном потоке — очередной успех (через год выйдет windows 98, где звуки микшируются сами и это тайное умение станет бесполезным).

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

Почти конец истории

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

На втором курсе я пытался все переделать на основе новых знаний, но шел дефолтный 98 год, и я увидел второй квейк на 3D акселераторе — он был сказочно прекрасен. Денег тогда не было от слова совсем, стоил акселератор как космолет, я почему-то решил, что у меня его в ближайшее время не будет. И интерес к программированию графики начал стремительно угасать — зато я загорелся идеей обработки звука. Но это уже другая история

P.S. Реальные текстурные координаты изменяются нелинейно, для скорости их заменяют линейными. Но что происходит с Z-координатой и зачем при преобразовании Z переворачивают? Ответ на этот вопрос и дает Z-буфер.