Оптимизация рейкастинга
| |
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 |
участник
Сейчас нет на сайте
| непонятная шляпка получается. Скачал и скомпилировал под ту же версию 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 |
|
| |
|