Среда, 24 Апреля 2024, 11:41

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 2
  • 1
  • 2
  • »
Форум игроделов » Программирование » C/C++ » Оптимизация рейкастинга
Оптимизация рейкастинга
AlkoshaДата: Вторник, 17 Декабря 2013, 10:34 | Сообщение # 1
участник
Сейчас нет на сайте
Шалом...
Попробовал скомпилить этот сорс.
http://lodev.org/cgtutor/raycasting2.html#Howitworks

На фуллскриновом разрешении 640*480 выдаёт 60 кадров в секунду, и это на 2.2 Гигагерцах. Понизил частоту проца до 800 мегагерц ~15 кадров в секунду (иногда и 10). Запустил на пентиуме MMX - 1 кадр в секунду(!). И это при том, что графика-то на уровне вульфа3д, и это без воспроизведения звуков, просчёта AI, дверей, та и размер карты явно меньше.
Тогда как рейкастинговые игры с нормальным алгоритмом для пня - раз плюнуть, на разрешениях 800*600.

Конкретно в данном примере используется SDL, в дополнительном cpp-файле (quickcg.cpp) реализован оптимизированный вывод пикселей на экран, как я понял (ну и заодно рисование графических примитивов, которые в конкретно этом примере не юзаются).
Как можно оптимизировать сам процесс выборки лучей ? Понизить точность просчёта во благо производительности.

Добавлено (17.12.2013, 10:34)
---------------------------------------------
Хм... Ещё одна особенность, на той версии SDL, что предоставлялась с исходником , фреймрейт вдвое шустрее , нежели на той, с которой компилировал я.
У меня версия SDL 2.0.1, кажись.
Но всё равно слишком маленький fps, как для сотен мегагерц.

Там когда вплотную к "стене" прижимаешься, шибко гладкая перспектива. Может из-за этого так медленно рисует ? То что просчитывает столбцы, кратные одному пикселю?


Сообщение отредактировал Alkosha - Вторник, 17 Декабря 2013, 12:45
XakepДата: Вторник, 17 Декабря 2013, 10:50 | Сообщение # 2
めちゃくちゃちゃ
Сейчас нет на сайте
в том что ты скинул лень разбираться, просто скажи. рекаст делается для рендера, т.е. из каждого пикселя пускается луч, или просто пара лучей от самого игрока или еще какого объекта? Есть в общем то несколько решений проблемы, можно разбить уровень на бинарное дерево (KD-Tree или BVH-Tree). Собственно по этим алгоритмам хорошо описано здесь и здесь, ну и на самом сайте много чего интересного можно найти (http://ray-tracing.ru/)
Еще вариант, перенести все расчеты на GPU через шейдеры или OpenCL/CUDA. Если же первое, то тут понятно почему может тормозить, очень много лучей одновременно выпускаются 640*480 = 307200 лучей, обычно такой рекаст делают для пред расчета освещенности сцены и запекания ее потом в lightmap


Сообщение отредактировал Xakep - Вторник, 17 Декабря 2013, 10:51
AlkoshaДата: Вторник, 17 Декабря 2013, 12:02 | Сообщение # 3
участник
Сейчас нет на сайте
Цитата Xakep ()
рекаст делается для рендера, т.е. из каждого пикселя пускается луч, или просто пара лучей от самого игрока или еще какого объекта?


Для рендера слишком жирно.
По-моему, тут всё же предоставлен пример того, как реализован рейкаст в вульфе3д, то есть по столбцам. Из "глаз" игрока пускаются два луча, ну и в соответствии с этим вертикально масштабируется определённый столбец при "столкновении" луча со стеной (+прорисовка пола и потолка)

Цитата Xakep ()
можно разбить уровень на бинарное дерево


это рационально делать для масштабных локаций. Массив карты не шибко-то и большой. Тем более низкий fps даже если в упор на стенку смотреть, а не только вдаль.

Цитата Xakep ()
обычно такой рекаст делают для пред расчета освещенности сцены и запекания ее потом в lightmap

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

Цитата Xakep ()
Еще вариант, перенести все расчеты на GPU через шейдеры или OpenCL/CUDA.


Не вариант. Только CPU... Если уж и задействовать GPU, то всё вышеописанное можно и на openGL осуществить, полигональной графикой.

Добавлено (17.12.2013, 12:02)
---------------------------------------------
Цитата Xakep ()
ну и на самом сайте много чего интересного можно найти (http://ray-tracing.ru/)

Всё же рей-трейсинг и рей-кастинг - несколько разные вещи.
Хоть и там и там происходит просчёт столкновения луча. Рейкастинг ориентирован на лучи фронтальной перспективы.
Рейтрейсинг же определяет столкновения лучей света с поверхностью трёхмерной модели.


Сообщение отредактировал Alkosha - Пятница, 27 Декабря 2013, 10:38
XakepДата: Вторник, 17 Декабря 2013, 12:17 | Сообщение # 4
めちゃくちゃちゃ
Сейчас нет на сайте
Цитата Alkosha ()
Тем более низкий fps даже если в упор на стенку смотреть, а не только вдаль.

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

Цитата Alkosha ()
Всё же рей-трейсинг и рей-кастинг - несколько разные вещи.
Хоть и там и там происходит просчёт столкновения луча. Рейкастинг ориентирован на лучи фронтальной перспективы.
Рейтрейсинг же определяет столкновения лучей света с поверхностью трёхмерной модели.

я работал и с тем и с другим, практически одно и то же, это практически синонимы, и сайт который скинул хороший справочник как для тех кто хочет использовать лучи для столкновения, так и для рендера сцены (по сути опять же проверяются лучи на столкновение объектов), из оптимизаций на пересечение луча я уже сказал: построить дерево или перевести на GPU, других нету, то что у тебя так тормозит вряд ли из-за рейкастига.
AlkoshaДата: Вторник, 17 Декабря 2013, 13:07 | Сообщение # 5
участник
Сейчас нет на сайте
Цитата Xakep ()
а разбиение на дерево как раз отсекает не нужные части сцены.

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

Добавлено (17.12.2013, 13:04)
---------------------------------------------

Цитата Xakep ()
то что у тебя так тормозит вряд ли из-за рейкастига.


Наверное процедурки quickCG.cpp на самом деле не такие уж и быстрые.
Потом на досуге проверю с какой скоростью рисуется попиксельно.

Добавлено (17.12.2013, 13:07)
---------------------------------------------
В вульфенштайне были ассемблерные подпрограммы для вывода пикселя на экран, только это с расчётом того, что прога будет работать на i80286-ом проце.
Мне б хотя бы для 166-ти мегагерцового пентиума оптимизировать.

XakepДата: Вторник, 17 Декабря 2013, 13:16 | Сообщение # 6
めちゃくちゃちゃ
Сейчас нет на сайте
Цитата Alkosha ()
Мне казалось с этим как раз рейкаст и справляется. Ведь луч идёт от игрока к первому встречному объекту, то есть всё что за видимым объектом - автоматически отбрасывается. Ну это при визуализации , разумеется.

объекты занесены в массив, и у них постоянно один и тот же порядок, и пройтись по всем объектам что-то вроде:
for (int i = 0; i < scene.objects.count; i++)
if (TestCast(Player, scene.objects[i]))
return ...

стена может находиться очень далеко от игрока, но при этом быть первой в массиве, и так же стена с которой тест пересечения прошел успешно, может быть последней в массиве, за этим как раз и придумали разбиение пространства, чтобы отбросить ненужные объекты, с которыми точно не может быть пересечения (например луч направлен в противоположную сторону от стены, и никогда не будет с ним столкновения)
AlkoshaДата: Среда, 18 Декабря 2013, 12:06 | Сообщение # 7
участник
Сейчас нет на сайте
evil непонятная шляпка получается.
Скачал и скомпилировал под ту же версию SDL (1.2.9) что и прилагалась к исходнику, с таким же самым разрешением, и всё той же quickCG.cpp , всё то же самое. Тупо скопипастил.
Тот билд, что на исходнике работает ровно вдвое быстрее, чем тот что скомпилирован у меня.(конечно на 800 мегагерцах 30 кадров в секунду - ужасный показатель для этого примера, но всё же.)
Создавал проект в кодблоксе по шаблону SDL Project (тот что прилагается к примеру тоже был скомпилирован в кодблоксе).
Может ли быть это от того, что линкер ненужные либы подключает ?

Добавлено (18.12.2013, 12:06)
---------------------------------------------
И не сказать, что пиксели рисуются медленно.
Всё с того же сайта скомпилировал пример без текстурирования стен (пол и потолок отсутствуют соответственно) - на 2.2 гигагерцах зашкаливает за 100 кадров в секунду (фреймрейт зависит от уровня закраски, немного понижается, когда вплотную к "стене" подойти, но не ниже 100 кадров всё равно).


Сообщение отредактировал Alkosha - Среда, 18 Декабря 2013, 13:24
XakepДата: Среда, 18 Декабря 2013, 12:18 | Сообщение # 8
めちゃくちゃちゃ
Сейчас нет на сайте
может там был использован другой компилятор, например g++ с включенными опциями оптимизации (-Ofast или -O3 -ffast-math) тогда может раза в 2-3 производительность увеличиться
AlkoshaДата: Среда, 18 Декабря 2013, 15:11 | Сообщение # 9
участник
Сейчас нет на сайте
Цитата Xakep ()
с включенными опциями оптимизации (-Ofast или -O3 -ffast-math)

Можно поподробнее?
Где именно эти самые опции включаются ?

Я выставил (в settings->compiler & debugger->toolchain executables)
Цитата
с compiler: gcc.exe
c++ compiler: g++.exe
linker for dynamic libs: g++.exe


и всё остальное оставил по дефолту

Цитата
linker for static libs: ar.exe
debugger: gdb.exe
recource compiler: windres.exe
Make programm: mingw32-make.exe


а куда прописывать этот "-Ofast" ?


Сообщение отредактировал Alkosha - Среда, 18 Декабря 2013, 15:13
XakepДата: Среда, 18 Декабря 2013, 15:38 | Сообщение # 10
めちゃくちゃちゃ
Сейчас нет на сайте
я вообще из командной строки это все прописываю, -Ofast вроде бы только на линуксе работает, в винде нужно писать: -O3 -ffast-math, хотя сейчас вспомнил, -ffast-math лучше не исползовать под виндой, он там не корректно работает.

Сообщение отредактировал Xakep - Среда, 18 Декабря 2013, 15:38
SEvgДата: Среда, 18 Декабря 2013, 16:41 | Сообщение # 11
Алхимик
Сейчас нет на сайте
Цитата Alkosha ()
Где именно эти самые опции включаются ?

В Кодеблокс Project->Build options->Compiler flags
AlkoshaДата: Среда, 18 Декабря 2013, 21:16 | Сообщение # 12
участник
Сейчас нет на сайте
Цитата SEvg ()

В Кодеблокс Project->Build options->Compiler flags


Данкешон.
Все флаги категории optimize включил - и эзешник стал легче (500 кб , а был почти два метра), и фреймрейт стал такой же, как и в примере...
Но всё равно , 25 кадров для 800 мегагерц - маловата будит!
Такой фреймрейт удовлетворителен разве что для 7-ми мегагерцовой MС68000.
XakepДата: Среда, 18 Декабря 2013, 21:26 | Сообщение # 13
めちゃくちゃちゃ
Сейчас нет на сайте
могу только посоветовать использовать OpenGL и GLM для математики, может при расчетах какие-то косяки, лучше самому разобраться как это работает и написать свою функцию с использованием SIMD или вообще рекаст на ГПУ произвести.
AlkoshaДата: Четверг, 19 Декабря 2013, 18:15 | Сообщение # 14
участник
Сейчас нет на сайте
Слишком много вычислений в теле цикла... В частности умножения...
На каждый пиксель "стен"
Код
int d = y * 256 - h * 128 + lineHeight * 128; //256 and 128 factors to avoid floats
          int texY = ((d * texHeight) / lineHeight) / 256;
          int color = texture[texNum][texWidth * texY + texX];
          //make color darker for y-sides: R, G and B byte each divided through two with a "shift" and an "and"
          if(side == 1) color = (color >> 1) & 8355711;
          buffer[x][y] = color;


На каждый пиксель потолка(потолка) приходится такое:
Код
currentDist = h / (2.0 * y - h); //you could make a small lookup table for this instead

   double weight = (currentDist - distPlayer) / (distWall - distPlayer);

   double currentFloorX = weight * floorXWall + (1.0 - weight) * posX;
   double currentFloorY = weight * floorYWall + (1.0 - weight) * posY;

   int floorTexX, floorTexY;
   floorTexX = int(currentFloorX * texWidth) % texWidth;
   floorTexY = int(currentFloorY * texHeight) % texHeight;

   //floor
   buffer[x][y] = (texture[3][texWidth * floorTexY + floorTexX] >> 1) & 8355711;
   //ceiling (symmetrical!)
   buffer[x][h - y] = texture[6][texWidth * floorTexY + floorTexX];



Сообщение отредактировал Alkosha - Четверг, 19 Декабря 2013, 18:15
XakepДата: Понедельник, 23 Декабря 2013, 13:09 | Сообщение # 15
めちゃくちゃちゃ
Сейчас нет на сайте
Код

int d = y * 256 - h * 128 + lineHeight * 128; //256 and 128 factors to avoid floats  
           int texY = ((d * texHeight) / lineHeight) / 256;  
           int color = texture[texNum][texWidth * texY + texX];  
           //make color darker for y-sides: R, G and B byte each divided through two with a "shift" and an "and"  
           if(side == 1) color = (color >> 1) & 8355711;  
           buffer[x][y] = color;

наверное можно немного оптимизировать:
Код

int d = y << 128 - h << 64 + lineHeight << 64; //256 and 128 factors to avoid floats  
           int texY = ((d << (texHeight >> 1)) >> (lineHeight >> 1)) >> 128;  
           int color = texture[texNum][texWidth << (texY >> 1) + texX];  
           //make color darker for y-sides: R, G and B byte each divided through two with a "shift" and an "and"  
           if(side == 1) color = (color >> 1) & 8355711;  
           buffer[x][y] = color;
OpenGOOДата: Понедельник, 23 Декабря 2013, 14:19 | Сообщение # 16
почти ветеран
Сейчас нет на сайте
Цитата Xakep ()
int d = y << 128 - h << 64 + lineHeight << 64; //256 and 128 factors to


так не верно, надо

Код
int d = y << 8 - h << 7 + lineHeight << 7;


Мои проекты:
- Свободный и открытый клон World Of Goo
- TrueEngine2D (2D игровой фреймворк основанный на FreeBASIC)

[GameMaker: Studio v1.4.9999]
XakepДата: Вторник, 24 Декабря 2013, 14:41 | Сообщение # 17
めちゃくちゃちゃ
Сейчас нет на сайте
а ну да, тогда и здесь немного не правильно:
Код
int texY = ((d << (texHeight >> 1)) >> (lineHeight >> 1)) >> 128;
int color = texture[texNum][texWidth << (texY >> 1) + texX];   

так вроде:
Код
int texY = ((d * texHeight) / lineHeight) >> 8;
int color = texture[texNum][texWidth * texY + texX];


Сообщение отредактировал Xakep - Вторник, 24 Декабря 2013, 15:00
AlkoshaДата: Среда, 25 Декабря 2013, 23:34 | Сообщение # 18
участник
Сейчас нет на сайте
Вот только для какой переменной подходит операция побитного сдвига.

Код
    int d1=lineHeight * 128;
       int d2=h * 128;
       for(int y = drawStart; y < drawEnd; y++)
       {
        int d = y *256 - d2 + d1;  //256 and 128 factors to avoid floats
        int texY = ((d * texHeight) / lineHeight) >>8;
         Uint32 color =texture[texNum][texWidth * texY + texX];
         if(side == 1) color = (color >> 1) & 8355711;
         buffer[x][y] = color;
             }


То бишь только для texY
если скроллировать переменную "y" - там шляпа с текстурами ваще конкретная. Что странно, ибо "y" интовый, то есть не дробное число.
И переменные "d1" и "d2" должны быть отдельно. Если до тела цикла записать так:

Код
d1 = lineHeight * 128 + h * 128


То получается, говоря заумным языком геймдевелопера, текстурная шляпенция.

Добавлено (25.12.2013, 23:34)
---------------------------------------------
Подумываю на асме выполнять вычисления... Но я ни разу не пробовал использовать ассемблерные вставки. Более того, не знаю как затем результат вычисления поместить из регистров в переменные.

XakepДата: Четверг, 26 Декабря 2013, 10:24 | Сообщение # 19
めちゃくちゃちゃ
Сейчас нет на сайте
лучше переходи на OpenGL, я всегда все что связанно с текстурами в шейдерах просчитываю (те же текстурные координаты).
AlkoshaДата: Четверг, 26 Декабря 2013, 13:02 | Сообщение # 20
участник
Сейчас нет на сайте
если переходить на openGL , то и рейкастинг как таковой не нужен (за исключением игровых моментов, типа просчёта выстрелов или коллизии с объектами).
Я хочу , чтоб моя прога работала на пентиуме MMX , без 3д акселераторов. Только ЦП и ничего лишнего.


Сообщение отредактировал Alkosha - Пятница, 27 Декабря 2013, 10:37
Форум игроделов » Программирование » C/C++ » Оптимизация рейкастинга
  • Страница 1 из 2
  • 1
  • 2
  • »
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг