Обработка блоков в стиле Minecraft (d3d / c ++)

Question

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

Должен ли каждый куб быть сеткой, которая копируется много раз, или это способ создать соответствующие сетки из данных в вашем буфере вершин?

Я нашел эту статью , в которой рассматриваются некоторые теории реализации того, что я хочу реализовать, но я никогда раньше не использовал октреи, поэтому я не мог извлечь слишком много из исходного кода. , Если октреи - действительно путь, где хорошая отправная точка, чтобы узнать о них? В большинстве моих поисков в Google были только сообщения в блоге о теории с небольшими примерами реализации или без них.

Кажется, что использование вокселей было бы полезно для этого, но, как и в случае с октреями, у меня нет такого опыта, поэтому я не знаю, что изучать в первую очередь.

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

Answer 1

Прежде всего, если вы используете Minecraft в качестве эталона, подумайте об их использовании кусков и соотнесите его с Oct-деревьями. Minecraft делит свой мир на более мелкие куски, чтобы обрабатывать огромное количество информации, которая необходима для хранения, поэтому используйте Oct-деревья для организации этих данных, которые будут храниться. Гоз имеет очень точное описание того, как работают Окт-деревья и Квад-деревья, поэтому используйте его информацию в качестве справки.

Еще одна вещь, которую следует учитывать, это то, что вы на самом деле не хотите рисовать каждый куб на экране, так как это съест вашу частоту кадров. Используйте Object Culling, чтобы рисовать только видимые кубы на экране. Опять же, если вы думаете, Minecraft; Вы когда-нибудь сталкивались с ошибкой, когда вы можете видеть сквозь блоки и под миром? Это потому, что Minecraft рисует только верхний слой блоков. С таким большим количеством объектов на экране было бы целесообразно изучить выборку объектов, используя как усеченную камеру, так и запрос окклюзии.

Для получения информации об использовании DirectX я бы порекомендовал любую книгу Фрэнка Луна. Я сам владею этой книгой, и она никогда не покидает мою сторону при программировании в DirectX. http://www.amazon.com/Introduction-Game-Programming-Direct-9-0c/dp/1598220160/ref=sr_1_3?ie=UTF8&qid=1332478780&sr=8-3 Я очень рекомендую эту книгу, поскольку узнал из нее почти все, что знаю о DirectX.

При поиске в Google я нашел эту ссылку, в которой обсуждается отбор окклюзии, потому что Luna не охватывает отбор окклюзии, а только отбор бороздки Я слышал, что серия «Programming Gems» упоминается очень часто, но лично я не могу подтвердить ее название. http://http.developer.nvidia.com/GPUGems/gpugems_ch29.html

Надеюсь, это поможет.

Answer 2

Oct-деревья довольно простые, особенно выровненные по оси, как те, что в шахте

Это в основном просто трехмерное расширение квад-дерева. Возможно, вам сначала будет легче узнать о Quad-деревьях.

Для краткого обзора четырехугольного дерева; в основном вы начинаете с квадрата. А теперь представьте, что на этом квадрате разместите гораздо меньший квадрат. Если вы хотите построить четырехугольное дерево, представляющее его, сначала разделите исходный квадрат на 4 квадрата одинакового размера.

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

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

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

Окт-деревья имеют то преимущество, что, зная, в каком октанте вы начинаете, вы можете легко направлять лучи через октавное дерево, чтобы найти столкновения (поскольку октант либо полон, либо частично полон, либо он пуст). Если октант пуст, вы проходите через него и затем проверяете октант на другой стороне. Если он частично заполнен, вы проверяете его субоктанты и так далее до тех пор, пока не найдете либо полный октант (т. Е. Вы попали в твердый куб и рендерите его), либо не пройдете через октант полностью и, следовательно, нет куба для рендеринга. , Вот как работает Minecraft (я все равно догадываюсь;)). Это также хороший способ быстрого рендеринга воксельных данных, которые все больше людей рассматривают в качестве возможного будущего механизма рендеринга.

Надеюсь, это поможет! :)

Answer 3

Oct-деревья и quad-деревья полезны для отбраковки участков вашей геометрии для рендеринга. Minecraft использует блоки рендеринга 16x16x16, чтобы разбить местность на управляемые куски.

Другая техника, которую следует рассмотреть, - это создание экземпляров Экземпляр - это то, где вы указываете GPU визуализировать объект несколько раз в разных местах. Он используется для рендеринга толпы, деревьев, чего угодно, где геометрия такая же, но у вас их много.

http://msdn.microsoft.com/en-us/library/windows/desktop/bb173349(v=vs.85).aspx

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter03.html

Вот статья, в которой автор дублирует средство визуализации minecraft в OpenGL 4. Хотя код не применим к вашему случаю, методы (отбраковка кубов, окружающих и т. Д.) Могут быть применены к средству визуализации DirectX.

http://codeflow.org/entries/2010/dec/09/minecraft-like-rendering-experiments-in-opengl-4/

Не обманывайтесь блочной графикой и текстурами низкого качества. Minecraft - чрезвычайно сложный рендер, и вам нужно будет найти способы справиться с огромным количеством задействованных предметов. Например, даже в «маленькой» части мира, скажем, 100х100х100 блоков, это 1 миллион блоков. Передача каждого блока в графический процессор в виде отдельной сетки убьет ваш графический процессор. Рендерер Minecraft гораздо сложнее, чем большинство шутеров от первого лица, когда вы переходите к технологии.