Войти
ФлеймФорумОбщее

Пароль на архиве с исходниками Game7? (5 стр)

Страницы: 1 2 3 4 5 6 7 Следующая »
#60
2:16, 29 мар. 2005

CyberZX
Нет. Попробую объяснить по-другому.
Вот есть туча методов структурирования геометрии: всякие Octree, BSP и прочая ерунда.
Спрашивается, зачем вообще всё это надо, когда можно сгрупировать геометрию и выводить её через один большой батч. Зачем?
Правильно, чтобы отсекать невидимую геометрию.
Пойдём дальше.
Вот у нас octree, но высота (глубина) дерева равна 2, т.е. у нас есть базовый узел (заключает в себя всю сцену в 1 млн. тр-ков) и есть 8 дочерних, в которых инфо о выводимой геометрии, и в каждом дочернем узле у нас по 200 тыч. тр-ков.
Как думаешь такого octree достаточно для быстрого вывода геометрии?
Думаю, что нет. И приходится добавить ещё один уровень. Тогда в последних узлах (листьях по сути) будет уже в среднем 25 тыс. Надеюсь объяснять зачемы мы 2 раза (а точнее 9) делили всё на 8 частей не надо.
Так вот, очевидно, что продолжать этот процесс, пока в листе будет один тр-к бессмысленно. Остановиться надо гораздо раньше. Вот, Zulus & Fly, решили остановиться на 700-1000 тр-ков в листе. А я предлагаю остановиться, скажем на 200-400 тр-ках. Конечно, никаких листьев у них нет, точнее есть, но геометрия хранится не в одной большой куче. Это я пример привёл. Но суть надеюсь понятна.

Fly
Так всё-таки. В чём я ошибся?


#61
14:19, 29 мар. 2005

Fly
>Ты даже не понимаешь сути проблемы с батчами. Ты бы поэкспериментировал для начала, а потом советовал бы алгоритмы.
И всё-таки, скажи уж, пожалуйста, чего я не понимаю, и с чем должен был поэкспериментировать.

#62
14:54, 29 мар. 2005

tav
не важно сколько полигонов имеют объекты в узлах octree, потому что frustrum culling происходит по bbox`ам.  твоя оптимизация направлена на тот редкий случай, когда объекта находиться на границы frustrum`а. это действительно очень редкий случай.
а в других слуаях, это только пессимизация.

#63
15:11, 29 мар. 2005

CyberZX
Нет. Ты непробиваем. :-)
>не важно сколько полигонов имеют объекты в узлах octree
Конечно неважно, важен размер листьев octree. Если нижние узлы (листья) будут на полэкрана (на пол-frustum-а), хорошо это будет? Или может стоит сделать их поменьше, чтобы отсекать геометрию более точно, что я вот уже пятую страницу советую. :-)

#64
16:10, 29 мар. 2005

tav
ну приминительно к Game7. где там такие объекты на полэкрана? кроме террайна все объекты там маленькие

#65
16:53, 29 мар. 2005

CyberZX
>где там такие объекты на полэкрана?
Ну почему они должны быть обязательно на полэкрана?
Там ~60 объектов в кадре. Т.е. если представить наш frustum в виде куба, то он охватывает примерно 4x4x4 (=64) статических обектов. Т.е. каждый обект в своих линейных размерах занимает более четверти экрана и крайних объектов грубо говоря получается 56, т.к. только 8 объектов внутренние (из куба 4x4x4), т.е. лежат целиком во frustum-е и их деление ничего по идее не даст (я же это, чёрт возьми и предлагал -- такие "внутренние" объекты выводить целиком, как и раньше, а если объект пересекает frustum (это элементарно определяется только по BBOX-у объекта), то уже смотреть на подобъекты). А остальные (у нас это почти все) frustum пересекают и если считать, что половина геометрии из них не видна (а реально может быть даже больше), то потенциально можно ускорить рендеринг статичной геометрии в 2 раза.

#66
11:56, 30 мар. 2005

Zulus & Fly
Так вы всё-таки собираетесь продавать игру? А то смотрите, пока до финального релиза дойдёт, тут уже несколько MOD-ов выпустят. :-)

>владелец хостинга gamedev.ru. Он хитрым образом вынудил нас написать игру на 15 метров, и выложить исходники запароленными, чтоб каждый, кто захочет посмотреть исходники обязательно скачал 15 метров игры, чтоб создать трафик, который, в свою очередь, принес сумму, на которую и куплен порш
Вернёмся к нашим баранам.
Я даже спрашивать боюсь почему вы пошли на уступку владельцу хостинга. Ведь ваши интересы диаметрально противоположны -- вы не заинтересованы в широком распространении игры сейчас бесплатно (т.к. потом в неё никто не захочет играть => никто не купит, очень мало во всяком случае), в отличие от этого владельца.
Да и на какие деньги он порш купил. Тоже вопрос, остающийся для меня загадкой. Грубо говоря, откуда взялись эти деньги, не из воздуха же. Я только сейчас понял, что из из этой истории я ничего не понимаю. Что значит "владелец хостинга gamedev.ru"? Зенон лишь регистирирует доменные имена (в зоне .ru в частности) и занимается размещением пространства под сайты. К тому же зенон -- лицо юридическое, и речь, я так понял, идёт о владельце организации, предоставляющей эти услуги.
Кто является администратором домена gamedev.ru (wat, наверное) и кто платит за хостинг я не знаю, но вообще-то wat может распоряжаться доменом gamedev.ru и выделять доменные имена третьего уровня. Но суть в другом, цены на превышение исходящего трафика не очень уж высокие. Ну на порш никак не хватит. В любом случае зенону за трафик платит тот, кто и за хостинг. Этот сайт, надо полагать живёт за счёт рекламы (одного маленького баннера наверху), ну не только, конечно, но всё же. Компания "Зенон Н.С.П." живёт за счёт предоставления платных услуг, в частности хостинга (плата за которые не настолько велика). И при чём тут ваша игра???

#67
12:04, 30 мар. 2005

tav
Это была ироническая шутка :)

#68
12:10, 30 мар. 2005

wat
>tav
>Это была ироническая шутка :)
???
Чья? И какая шутка?

#69
13:50, 30 мар. 2005

Есть такое понятие - чувство юмора.

#70
14:18, 30 мар. 2005

tav
>Чья? И какая шутка?
Зулуса. По поводу хостера, зарабатывающего несметные богатства на траффике.

#71
16:15, 30 мар. 2005

wat
>Зулуса. По поводу хостера, зарабатывающего несметные богатства на траффике.
Понятно. Видно с горя выпил сразу всё пиво, которое ему купил "владелец хостинга gamedev.ru".


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

Для наглядности, рассмотрим случай в 2D.
Построим quad-tree и упорядочим все квады в один буфер в следующем порядке (вначале идут 0,1...9, потом A,B...Z, и наконец a,b...z):

ghklwx??
efijuvyz
YZcdopst
WXabmnqr
ABEFQRUV
89CDOPST
2367IJMN
0145GHKL
? - просто букв не хватило :-)

Камера будет смотреть справа налево. Обозначим # - невидимые квады. Получим примерно следующее:

ghkl#######
efijuv#####
YZcdopst###
WXabmnqr??#
ABEFQRUV###
89CDOP#####
2367#######
0##########
Редерить будем следующим образом.
Определяем видимость поддеревьев 0-F, G-V, W-l и m-?.
Поддерево W-l полностью внутри frustum-а => выводим его целиком за один!!! батч (например, glDrawElements с диапазоном индексов от W до l).
Поехали дальше. После определения видимости выводим поддеревья следующего уровня дерева с диапазонами индексов: 8-B, C-F, O-R, m-p, q-t. И на последнем нижнем уровне дерева выводим одиночные элементы: 0,2,3,6,7,U,V,u,v,?,?.

Итак, в чём суть Batching Scene Graph. Для простоты будем рассматиривать octree вариант, т.к. другие разбиения будут более эффективны только в частных случаях, либо сложно-реализуемы.
Поставим ограничение на геометрию - все меши должны быть из одного материала (ниже я расскажу, как снять это ограничение). Теперь возьмём наши меши (статичные объекты) и запихаем их в одну большую кучу треугольников.
Начинаем строить классическое octree. Т.е. делим все тр-ки на 8 подпространств текущего поддерева и передаём их следующему, и параллельно с этим все треугольники (треугольник = 3 индекса его вершин) помещаем в один индекс-буфер (делать это нужно на последнем уровне). Т.е. формируем структуру, 2D варинт которой я рассматривал выше.
Теперь, по поводу тех тр-ков, которые нельзя отнести только к одному из 8 подпространств (т.е. которые пересекают делящую/-ие плоскости). Я потратил тучу времени на раздумывание, что же с ними делать, но так ни к чему толком не пришёл. Т.е. очевидно, что для каждому поддереву в индекс-буфере соответсвует область (диапазон индексов) и вначале идут подподдеревья поддерева, а потом "неподеленные" треугольники. И таким образом, если поддерево видно полностью, то выводится весь диапазон индексов, и "неподеленные" тр-ки туда входят. Вроде всё здорово, но это так, пока не встретится случай, когда видно, напр., только одно из подподдеревьев поддерева - ведь "неподеленные" тр-ки в этом случае тоже могут быть видны и их надо выводить по идее тоже. А проблема то заключается вот в чём. Если у нас будет гигантское octree на 100 млн. тр-ков (весить это будет гигабайта 2). В каждый момент времени в кадре виден только 1 млн. тр-ков. Начинаем обходить дерево: смотрим, ага одно из поддеревьев дерева видно, переходим в него. Заходим, а в нём видно тоже одно подподдерево. И спрашивается, а что делать с "неподеленными" тр-ками в этом поддереве (а ведь они могут быть и в вершине дерева). Ведь для такого большого дерева их может быть от 250 тыс. до миллиона. И с увеличением отношения общего числа тр-ков на число видимых, ситуация будет ухудшаться. Да и со стримингом могут быть проблемы, ведь "неподеленные" тр-ки могут быть видны из любой части сцены. Значит по идее их надо как-то упорядочить, возможно разбить на некоторые группы и каждому поддереву на самом нижнем уровне (каждому листу) надо сопоставить такую группу. В общем, думал я долго как раз над тем, откуда же взять эти группы. Думал даже "неподеленные" тр-ки не выдирать из исходных мешей статических объектов, и использовать то, что останется от этих мешей (ведь некоторые из тр-ков в них могут лежать полностью внутри какого-либо подпространства), в качестве этих групп. Как вариант, было создание некоей структуры для упорядочивания "неподеленных" тр-ков, рассчитанной на то, что они пересекают делящие плоскости, т.е. располагаются преимущественно вблизи от них.

#72
16:16, 30 мар. 2005

Короче, ничего путного не придумал, а решил делать так:
Мол, раз вся проблема с этими "неподеленными" тр-ками, надо сделать так, чтобы их просто не было. Спрашивается как, ведь всё-равно некоторые исходные тр-ки будут проходить через делящие пл-ти. Всё очень просто. Т.к. размер этих тр-ков относительно самих поддеревьев сравнительно мал, можно эти тр-ки просто относить к одному из поддеревьев, расширяя ими его BBOX. Таким образом BBOX-ы поддеревьев могут пересекаться, но, тем не менее проблема разрешается.

Теперь осталось снять ограничение на число материалов. Ведь я рассматривал случай, когда материал был один и соотв. этот метод нуждается в доработке. Какой? Весьма небольшой.
Для наглядности, представим наш SceneGraph в виде 4-хмерного пространства. 4-м измерением как раз будет материал. Таким образом, при формировании большой кучи треугольников из статичных объектов (в самом начале), на самом деле надо формировать не одну кучу, а несколько - на каждый материал по такой куче.
Кучи по сути могут пересекаться в 3-хмерном пространстве, но т.к. каждая находится в своем измерении, то можно считать, что мухи отделены от котлет.
Вообще-то 4-е измерение - всего лишь условность и создавать несколько octree необязательно (но можно).
Если использовать одно octree, то можно сделать так.
В каждом листе создаётся список, каждый элемент которого содержит идентификатор материала и геометрию (диапазон индексов), соответствующую данному листу.
При первом (и единственном) проходе octree, как только мы дошли до видимого листа, из списка (описанного выше) листа берётся первый материал, устанавливаются все стейты для него и выводятся вся геометрия, соответсвующая этому материалу. Информация об остальной геометрии листа из других материалов помещается в некую очередь, работа с которой осуществляется уже после обхода дерева. Так вот, первый кусок выведенной геометрии мы пометили, а точнее только её материал, и при дальнейшем обходе дерева мы выводим только объекты из данного материала. Объекты из других материалов помещаются в очередь.
После обхода дерева, эта очередь сортируется по материалам и используется для вывода оставшейся геометрии.
Лучше не сортировать эту очередь, а просто создать некий массив A (число эл-тов = числу материалов) из динамических массивов, хранящих инфу о геометрии.
Также надо добавить к инфе о каждом материале (к его параметрам) флаг F, и ещё создать дополнительный список L использованных при выводе материалов.
И тогда при обходе дерева вся геометрия не из текущего материала помечается в массиве A путём добавления инфы о геометрии в дин. массив, соответсвующий материалу данной геометрии. Также проверяется состояние флага F этого материала, и если он сброшен, то флаг устанавливается, а в список L помещается идентификатор этого материала.
В этом случае, после обхода дерева, сортировать ничего не нужно, а надо всего лишь пройтись по списку L, на каждой итерации надо устанавливать нужные стейты, выводить геометрию (инфа о которой хранится в дин. массиве) и сбросить флаг F этого материала.

Таким образом, Batching Scene Graph позволяет, в случае, когда вся сцена из одного материала видна целиком, вывести её за один!!! батч.
К тому же задача сортировки по текстурам решается сама собой и нетрудно расширить сортировку. Т.е. если в сцене половина объектов требует для своей отрисовки один шейдер, а другая половина - другой, ну в каждой половине много мешей их разных материалов, то можно просто эти 4-ые измерения упорядочить таким образом, чтобы вначале шли меши только для первого шейдера, а потом - для второго. И соответсвенно, потребуется всего 2 смены шейдеров, да ещё и по материалам геометрия будет отсортирована.

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


P.S. Полный бред, не правда ли. :-)

#73
17:17, 30 мар. 2005

Не совсем бред, я понял:)
Понравилась идея рассматривать материал, как 4-е измерение. Кстати, несколько октри создавать не придется по другой причине - октри тогда превратится в хекстри. И хотя этот вариант (рассмотрение материала, как 4-е РАВНОПРАВНОЕ измерение) повысит кол-во переключений стейтов, зато сильно упростит структуру программы, повысит наглядность.

А дальше действительно - в очередь, по материалам.

#74
20:37, 30 мар. 2005

tav
Объясняю. Увеличение кол-во батчей спасает только при очень сложном пиксельном или вертексном шейдере. Иногда, уменьшив объекты (разбив на несколько батчей), можно добиться, например, что на объект будет действовать 1 источник света вместо 2-х. Или 2 кости вместо 4-х. Упростится шейдер, увеличится скорость. В нашем жуке при разбивании батчей на более мелкие возрастет только лишь нагрузка на процессор, и, как следствие, упадет FPS. Видюху мы тем самым не разгрузим.

И вообще о каком увеличении кол-ва батчей может идти речь, если игра у нас CPU limited? Известный факт: чем больше батчей, тем сильнее нагружается процессор.

Страницы: 1 2 3 4 5 6 7 Следующая »
ФлеймФорумОбщее

Тема в архиве.