Создание 3D Engine. Часть 1.

11 Октября, 2012 Dunadan KSMПросмотров: 17394

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

3d_engine3d_engine

В цикле статей я приведу несколько старых алгоритмов для отрисовки сцен, подходя к самому движку, будут выложены исходные тексты программ и версий движка, а так же сам текст дипломной работы. До теперешних 3Д сцен далеко конечно, но более 10 лет назад это было вполне приемлемо и конкурентно способно. Хватит отступлений и перейдем к делу.

Алгоритм определения видимых поверхностей  путём трассировки лучей.

Это один из самых первых алгоритмов  создания игр, поэтому рассмотрим как работает алгоритм на примере устройства классической игры Wolfenstein 3D фирмы IDSoftware. 

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

3d_engine pics

Кроме того, в игре приняты следующие допущения. Стены могут быть только вертикальные и горизонтальные. Расстояние между потолком и полом и высота "глаз" над уровнем пола везде одинаковы. Еще немного упростим модель и будем рассматривать матрицу, элементами которой являются числа, полностью определяющие игровое поле, положение игрока и противников, а также все предметы.
Теперь рассмотрим способы отображения игрового поля. Для этого нам понадобиться алгоритм трассировки лучей (ray casting), а точнее его двумерная интерпретация. Вот зачем он нужен. Рано или поздно при отрисовки некоторого числа поверхностей возникает вопрос о том, а действительно ли необходимо выводить на экран все из них. Оказывается, что нет. Некоторые стены можно выводить не до конца, т.к. они перекрываются другими, некоторые вообще не видны. Как же проверить, видно стену или нет. Для этого есть множество способов, но сначала определим одно важное понятие. 
Под камерой будем понимать объект, который имеет вектор направления (ракурс, угол зрения и т.д.) и размерами этого объекта можно пренебречь. Можно также считать, что вместо камеры сидит наблюдатель и смотрит в сторону, заданную вектором направления. Посмотрим и мы на то, что видит этот наблюдатель. Заметим, что на экран как раз это и нужно выводить. Есть метод вывода на экран путем построчного сканирования. (вывод по строкам) В данной конкретной ситуации удобнее будет вывод на экран по столбцам. 
Пока что попробуем свести задачу определения ближайших граней а пространстве, к аналогичной задаче на плоскости. Посмотрим на игровое поле сверху. Получилась задача на плоскости 0XY. 
3d_engine pics
Двумерная интерпретация алгоритма трассировки лучей заключается в следующем. Из точки, где находиться наблюдатель, выпускается пучок лучей. Далее для каждого луча находиться его ближайшее (первое) пересечение с другими объектами (в нашем случае со стенами). Но это еще не все. Просто алгоритм, где проверяются все стены на пересечение с лучом малоэффективен. Приятнее воспользоваться тем, что стены являются сегментами линий сетки. Для этого пересекаемые лучом клетки отслеживаются в порядке распространения от начала до того, пока не будет встречена непустая клетка. 
3d_engine pics

Реализуем все это следующим образом. Проверим на пересечение с лучом сначала вертикальные, а потом горизонтальные стены. Далее выберем ближайшее пересечение.

Пусть наблюдатель находиться в точке с координатами (x*,y*), а угол между лучом

и положительным направлением оси 0X равен alpha. Будем считать, что клетка, содержащая игрока, имеет индекс (i*,j*), а шаг сетки равен h. Найдем точки пересечения луча с вертикальными линиями x=ih. Если направляющий вектор луча имеет положительную х-составляющую (cos(alpha)>0 => alpha от -pi/2 до pi/2), то ближайшая точка будет иметь координаты x1=(i*+1)h, y1=y*+(h-(x*-i*h))tan(alpha)=y*+(x1-x*)tan(alpha). При этом эта точка лежит на границе клетки (i*+1,[y1/h]). Если эта клетка занята стеной, то пересечение сразу получается в точке (x1,y1). При этом расстояние до точки пересечения будет равно d=(x1-x*)/cos(alpha). Если же эта клетка пуста, то проверяем следующие точки: Xi+1=Xi+h, Yi+1=Yi+htan(alpha). Здесь i-ая точка соответствует клетке (i*+i,[Yi/h]). Проверка происходит до тех пор, пока мы либо не наткнемся на занятую клетку, либо не выйдем за пределы лабиринта.

Если клетка, соответствующая точке пересечения (Xi,Yi), занята, то расстояние до этой точки будет d=(Xi-x*)/cos(alpha).

Теперь рассмотрим случай, когда cos(alpha)<0 (alpha то pi/2 до 3pi/2). Ближайшая точка пересечения луча с линией вида x=ih описывается формулами: x1=i*h, y1=y*-(x*- 1)tan(alpha)=y*+(x1-x*)tan(alpha). Первой проверяется клетка (i*-1,[y1/h]). Если она занята, то пересечение найдено и расстояние до точки пересечения равно d=(x1-x*)/cos(alpha). Иначе необходимо проверить остальные точки пересечения: Xi+1=Xi-h, Yi+1=Yi-htan(alpha). Для точки (Xi,Yi) следует проверить клетку (i*-i,[Yi/h]). Если она занята, то расстояние до точки пересечения составит d=(Xi-x*)/cos(alpha).

       Получаем следующий код

float  checkVWalls ( float angle )

{

        int  xTile = (int) locX;     //cell indices

        int  yTile = (int) locY;

        float xIntercept;            // intercept point

        float    yIntercept;

        float        xStep;         // intercept steps

        float        yStep;

        int        dxTile;

        if (fabs ( cos ( angle ) ) < 1e-7 )

                return 10000.0;

        if (angle >= ANGLE_270 || angle <= ANGLE_90 )

        {

                xTile ++;

                xStep      = 1;

                yStep      = tan ( angle );

                xIntercept = xTile;

                dxTile     = 1;

        }

        else

        {

                xTile --;

                xStep      = -1;

                yStep      = -tan ( angle );

                xIntercept = xTile + 1;

                dxTile     = -1;

        }

                      //find interception point

        yIntercept = locY + (xIntercept - locX)* tan ( angle );

        for ( ;; )

        {

                yTile = yIntercept;

                if ( xTile < 0 || xTile > 52 || yTile < 0 || yTile > 9 )

                        return 10000.0;

        if ( worldMap [yTile][xTile] != ' ' )

            return ( xIntercept - locX ) / cos ( angle );

                xIntercept += xStep;

                yIntercept += yStep;

                xTile      += dxTile;

        }

}

Точно так же находится ближайшая точка пересечения луча с горизонтальными линиями сетки y=ih. 

      При alpha от 0 до pi: x1=x*+(y1-y*)ctg(alpha), y1=(j*+1)h, Xi+1=Xi+hctg(alpha), Yi+1=Yi+h. При alpha от pi до 2pi x1=x*+(y1-y*)ctg(alpha), y1=(j*-1)h, Xi+1=Xi-hctg(alpha), Yi+1=Yi-h. 

      Код для горизонтальной проверки выглядит так. 

float        checkHWalls ( float angle )

{

        int        xTile = (int) locX;

        int        yTile = (int) locY;

        float        xIntercept;

        float        yIntercept;

        float        xStep;

        float        yStep;

        int        dyTile;

        if (fabs ( sin ( angle ) ) < 1e-7 )

                return 10000.0;

        if ( angle <= ANGLE_180 )

        {

                yTile ++;

                xStep = 1 / tan ( angle );

                yStep = 1;

                yIntercept = yTile;

                dyTile = 1;

        }

        else

        {

                yTile --;

                yStep = -1;

                xStep = -1 / tan ( angle );

                yIntercept = yTile + 1;

                dyTile = -1;

        }

        xIntercept = locX + (yIntercept - locY) / tan ( angle );

        for ( ; ; )

        {

                xTile = xIntercept;

                if ( xTile < 0 || xTile > 52 || yTile < 0 || yTile > 9 )

                        return 10000.0;

                if ( worldMap [yTile][xTile] != ' ' )

                        return ( yIntercept - locY ) / sin ( angle );

                xIntercept += xStep;

                yIntercept += yStep;

                yTile      += dyTile;

        }

}

      После того, как найдены ближайшие точки пересечения луча как с вертикальными, так и с горизонтальными стенами, среди них выбирается наименее удаленная от игрока. 
      Теперь нужно понять, как по найденному расстоянию d строиться столбец пикселей. Для этого нам нужно ввести расстояние f до картинной плоскости. 
3d_engine pics
      Найдем величины отрезков AB, BC и CD через f и d. Условимся, что камера находиться посередине между потолком и полом. Т.е. AB=CD. Тогда BC=(SCREEN_HEIGHT*f)/d, AB= SCREEN_HEIGHT-BC)/2. 
      Реализация этого в коде ниже. 
 

void        drawView ()

{

        float        phi;

        float        distance;

        totalFrames++;

        for ( int col = 0; col < 320; col++ )

        {

                phi = angle + rayAngle [col];

                if ( phi < 0 )

                        phi += 2 * M_PI;

                else

                if ( phi >= 2 * M_PI )

                        phi -= 2 * M_PI;

                float        d1 = checkVWalls ( phi );

                float        d2 = checkHWalls ( phi );

                distance = d1;

                if ( d2 < distance )

                        distance = d2;

                distance *= cos ( phi - angle );        //adjustment for fish-eye

                drawSpan ( distance, WALL_COLOR, col );

        }

}

Для задания углов лучей здесь используется массив rayAngle - для каждого луча указан угол между направлением луча и направлением взгляда игрока. Наиболее простым способом описания этого массива является задание углов с постоянным шагом, но, т.к. этот способ вызывает некоторые искажения, применим следующий алгоритм: 

      reyAngle[i]=arctg(tg(VIEW_ANGLE/2)*(1+i/(SCREEN_WIDTH-1))) 
3d_engine pics
 

twitter.com facebook.com vkontakte.ru odnoklassniki.ru mail.ru ya.ru rutvit.ru myspace.com technorati.com digg.com friendfeed.com pikabu.ru blogger.com liveinternet.ru livejournal.ru memori.ru google.com bobrdobr.ru mister-wong.ru yahoo.com yandex.ru del.icio.us

Оставьте комментарий

аноним

совет Используйте нормальные имена. Ваш комментарий будет опубликован после проверки.

комментатор / стать им

как?Укажите свой действующий email и пароль. При регистрации на указанный адрес придет письмо с кодом активации и ссылкой на ваш персональный аккаунт, где вы сможете изменить свои данные включая адрес сайта, ник, описание, контакты и т.д.

grin LOL cheese smile wink smirk rolleyes confused surprised big surprise tongue laugh tongue rolleye tongue wink raspberry blank stare long face ohh grrr gulp oh oh downer red face sick shut eye hmmm mad angry zipper kiss shock cool smile cool smirk cool grin cool hmm cool mad cool cheese vampire snake excaim question

(обязательно)