Как я почти рейтрейсил в реальном времени в 1997 году

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

    Предыстория


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

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

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


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

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

    $\vec x=k(x_s, y_s, z_0)=k\vec S$

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

    $(\vec n,\vec x) = D$

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

    $k=\frac{D}{(\vec n,\vec s)}$


    Ну как легко, пожалуйте в царство боли делений. Компьютер хорошо складывает, сносно умножает (это ведь не более чем сложения и сдвиги), но деление… Деление на моем 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-буфер.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      +19
      Ожидал лампового скриншота
        +4

        Или хотя бы студенческой ламповой фото из этого университета

        +3
        Вечер воспоминаний объявляется открытым!

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

        Z-buffer ответа не даст. Про нелинейность читать тут. А вообще лучше читать с самого начала. Кстати, рейтрейсинг — это совсем не z-buffer, за этим сюда.
          0
          1) совет запоздал на 21 год, сейчас мне все понятно и про нелинейность и про Z-буфер. Да и читать про нелинейность не надо, ее видно в любой комнате — достаточно подойти к стене и взглянуть вдоль нее.

          2) зачаточный рейтрейсинг тут есть — выпускание луча из камеры через экранный пиксель. полноценный бы получился, если бы он отразился от грани
            +1
            А, вы про нелинейности, вызванные неидеальностью вашей оптики? Ну так z-buffer тоже в этом не поможет.
              0
              нет, нелинейность вызвана тем банальным фактом, что перспективная проекция нелинейна
                +2
                Уф. Вы уж больно туманны в ваших определениях.

                Perspective projection is a linear projection where three dimensional objects are projected on a picture plane.
                  0
                  в математике понятие линейность определено достаточно строго. перспективная проекция не является линейным преобразованием (любое линейное преобразование равные отрезки на одной прямой всегда преобразует в равные отрезки на одной прямой)
                  первая же формула в википедии нам намекает:
                  en.wikipedia.org/wiki/Camera_matrix
                    +3
                    Не является линейным преобразованием координат точек (кстати, в однородных координатах-таки является), зато переводит прямые в прямые и является линейной проекцией. Потому и говорю, что вы туманны в определениях.
                      0
                      ну если буквоедствовать, то линейные преобразования возможны только над векторным пространством, а однородные координаты им не являются :)

                      я очень последователен в определениях, и линейность понимаю так, как ее определяет математика (хотя внутри тусовки может использоваться самый лютый фольклор). применительно к рендерингду это имеет самй прострой смылс — если некая величина U вычисленная для текущего пикселя, то в следующем пикселе строки ее значении будет U+deltaU, причем deltaU постоянно для всей грани. Для исходной геометрической координаты Z это неверно в силу приведенной формулы. Для 1/z — верно
                        0
                        я почитал текст, вы Z-буфер зачем-то дали до перспективного преобразования, это как бы очень странно, гораздо лучше объяснять наоборот
            0
            напишите про обработку звука
              0
              Можно PlaySound вызывать, а можно и DirectSound использовать. У Андре Ламота это есть в его книжках.
              А своё микширование ещё со времён Doom делалось легко. Помнится, там просто сложение было с обрезанием по разрядности результата. Хотя уже не помнится — 20 лет прошло. :)
              0
              P.S. Реальные текстурные координаты изменяются нелинейно, для скорости их заменяют линейными. Но что происходит с Z-координатой и зачем при преобразовании Z переворачивают? Ответ на этот вопрос и дает Z-буфер


              Что вы имеете в виду? Реальные текстурные координаты изменяются линейно в плоскости экрана как 1/z. Поэтому z-буфер надо делать буфером 1/z, а не z.
                0
                Реальные текстурные координаты изменяются в грани совершенно нелинейно, из приведенной формулы это видно. Можно представить себе очень длинную стену, с челнобелыми полосами равной ширины, смотрите вдоль нее. При линейном изменении текстурных координат мы видели бы полосы равной ширины, в реальности — ближние полосы широкие, дальние — узкие.

                Для ускорения расчетов реальные текстурные координаты никто не считает, считают их линейную интерполяцию, а ошибку легко контролировать, разбивая большие грани на маленькие. С 1/z координатой ситуация другая, она реально линейна, потому «1/z» буфер работает железобетонно и никакой коррекции не требует
                  0
                  Для ускорения расчетов реальные текстурные координаты никто не считает, считают их линейную интерполяцию,


                  Считают линейную интерполяцию U/Z и V/Z. И получают значение текстуры совершенно точно в любой точке экрана. Для ускорения же линейно или квадратично интерполируют через ряд точек, как это сделано в Quake. Но в узлах вычисляют точно.
                    0
                    не может линейная интерполяция быть совершенно точная в любой точке экрана, иначе бы она не называлась «интерполяция». Она может быть достаточно точна, достаточность обеспечивается разбиением грани на маленькие части (или как вы пишете — узлы). С 1/z ситуация проще — она линейная, потому точна и ничего разбивать не надо
                      0
                      Интерполяция не означает, что значения функции в промежутке отличаются от реальных. Попробуйте линейную интерполяцию для линейной же функции. А так как 1/z меняется линейно, то все точки получаются точно.
                      Когда вы сделали проекцию грани, вы получили координаты (x,y) для экрана. Для концов этой грани известны точно значения z и (u,v). Дальше вы линейно интерполируете по экрану 1/z, u/z и v/z и вычисляете для любой точки экрана в промежутке значения u и v из этой троицы. Получаете точное значение (u,v) для любой точки экрана в промежутке. Точное. Но так как делить на 1/z долго, часто точные значения вычисляют с некоторым экранным шагом, а между ними делают интерполяцию. Но никто так делать не заставляет.
                      Вот пример моей работающей библиотеки (ещё, правда, не доделанной до вида библиотеки) с элементами OpenGL:
                        0
                        «Интерполяция не означает, что значения функции в промежутке отличаются от реальных. » по определению — означает. вопрос — насколько сильно. все ухищрения с линеаризацией — чтобы не сильно. впрочем, ошибку довольно легко контролировать

                        если Z — это геометрическая величина координата, которую не перевернули матрицей проективного преобразования, то:
                        • 1/Z
                        • u, v
                        • u/Z

                        потому я совершенно не понимаю, зачем вам u/Z линейно-интерполировать, когда можно это сделать с u. Точное значение u и v там не вычисляется, они очевидно линейны по точке пересечения экранного луча с гранью и не линейны относительно экранных координат.
                          0
                          потому я совершенно не понимаю, зачем вам u/Z линейно-интерполировать


                          Потому что это простой и естественный способ текстурирования в пространстве экрана.
                            0
                            а чем оно лучше, чем u?
                              0
                              А тем, что нет искажений. Этот метод стандартный.
                              Посмотрите Шикин, Боресов «Компьютерная графика. Полигональные модели».
                                0
                                я не могу понять ваш текст.
                                «Дальше вы линейно интерполируете по экрану 1/z, u/z и v/z и вычисляете для любой точки экрана в промежутке значения u и v из этой троицы. Получаете точное значение (u,v) для любой точки экрана в промежутке. Точное.»
                                Допустим у меня 1/z точное, u/z я линейно интерполировал, как мне без деления получить u?
                                  0
                                  Без деления — никак. Если у вас скорости хватает, то вы можете делить для каждой точки и получать точную текстуру. Если не хватает (как в Quake), тогда вы вычисляете точные значения текстуры, например, для каждых 16 точек экрана, а в промежутке делаете линейную интерполяцию (как вы в своём проекте и делали, разбивая грани, и как делает моя программа выше без разбиения граней). Кстати, с цветом так не заморачиваются и интерполируют линейно в плоскости экрана — в отличие от текстуры там такая точность не нужна.
                                  Вот тут я ещё писал немного про текстурирование в Doom.
                                    0
                                    тогда все ясно — никакой особой разницы нет, просто одна запись более компактна.
                                      0
                                      почитал, очень здорово, я тогда текстурирование пола сделать не смог
                                      0
                                      1/z, кстати, вы тоже интерполируете линейно в плоскости экрана.

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

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