Как я могу оптимизировать мир вокселей Minecraft-esque?

Я обнаружил, что чудесные большие миры Minecraft чрезвычайно медленны для навигации, даже с четырехъядерным ядром и мясистой графической картой.

Я предполагаю, что медленность Minecraft происходит от:

  • Java, поскольку пространственное разбиение на разделы и управление памятью быстрее в C ++.
  • Слабое разделение мира.

Я мог ошибаться в обоих предположениях. Тем не менее, это заставило меня задуматься о лучшем способе управления большими воксельскими мирами. Поскольку это настоящий 3D-мир, где блок может существовать в любой части мира, это в основном большой 3D-массив [x] [y] [z], где каждый блок в мире имеет тип (т.е. BlockType.Empty = 0, BlockType.Dirt = 1 и т. д.)

Я предполагаю, что для того, чтобы этот мир работал хорошо, вам нужно:

  • Используйте дерево некоторого разнообразия ( oct / kd / bsp ), чтобы разбить все кубы; похоже, что oct /kd будет лучшим вариантом, так как вы можете просто разделить на куб уровне не на уровень треугольника.
  • Используйте какой-либо алгоритм для определения того, какие блоки в настоящее время могут быть видны, поскольку блоки, расположенные ближе к пользователю, могут обмануть блоки позади, делая их бессмысленными для их отображения.
  • Удерживайте объект блока очень легким, поэтому его можно быстро добавить и удалить из дерева.

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

71 голос | спросил SomeXnaChump 31 Maypm11 2011, 13:21:34

6 ответов


102

Voxel Engine Rocks

Voxel Engine Grass

Что касается Java vs C ++, я написал движок voxel в обоих версиях (версия C ++, показанная выше). Я также писал мотивы вокселей с 2004 года (когда они не были моде). :) Я могу сказать с небольшим колебанием, что производительность C ++ намного превосходит (но это также сложнее кодировать). Его меньше о вычислительной скорости и больше об управлении памятью. Руки вниз, когда вы выделяете /освобождаете столько данных, сколько в мире вокселей, C (++) - это язык, которым нужно бить. Однако , вы должны подумать о своей цели. Если производительность вашего наивысшего приоритета, перейдите на C ++. Если вы просто хотите написать игру без снижения производительности, Java определенно приемлем (о чем свидетельствует Minecraft). Есть много тривиальных /крайних случаев, но в целом вы можете ожидать, что Java будет работать примерно в 1,75-2,0 раза медленнее, чем (хорошо написано) C ++. Вы можете увидеть плохо оптимизированную, более старую версию моего движка в действии здесь (EDIT: newer версия здесь ). В то время как генерация блоков может показаться медленной, имейте в виду, что она генерирует 3D-диаграммы voronoi волюметрично, вычисляя нормали поверхности, освещение, АО и тени на процессоре с помощью методов грубой силы. Я опробовал различные методы, и я могу получить примерно 100-кратное ускорение генерации блоков, используя различные методы кэширования и инстанса.

Чтобы ответить на оставшийся ваш вопрос, вы можете сделать многое для повышения производительности.

  1. Caching. Где бы вы ни находились, вы должны вычислить данные один раз. Для Например, я испекаю освещение в сцену. Он может использовать динамические освещение (в пространстве экрана, как пост-процесс), но выпечка в освещение означает, что мне не нужно проходить в нормалях для треугольники, что означает ....
  2. Пропустите как можно меньше данных на видеокарту. Одна вещь люди склонны забывать, что чем больше данных вы переходите на GPU, тем больше времени требуется. Я пропускаю один цвет и вершинную позицию. Если я хочу делать дневные /ночные циклы, я могу просто сделать оценку цвета, или я может повторять сцену, когда солнце постепенно меняется.

  3. Поскольку передача данных на GPU настолько дорога, возможно напишите двигатель в программном обеспечении, который в некоторых отношениях быстрее. Преимущество программного обеспечения в том, что он может выполнять все виды данных манипуляции /доступ к памяти, что просто невозможно на графическом процессоре.

  4. Играйте с размером партии. Если вы используете графический процессор, производительность может сильно варьироваться в зависимости от того, насколько велика каждая массив вершин является. Соответственно, поиграйте с размером кусков (если вы используйте куски). Я обнаружил, что 64x64x64 куски работают очень хорошо. нет важно, что ваши куски кубические (без прямоугольных призм). Эта будет делать кодирование и различные операции (например, преобразования) проще, а в некоторых случаях более совершенным. Если вы храните только один значение для длины каждого измерения, имейте в виду, что два меньше регистры, которые меняются местами во время вычисления.

  5. Рассмотрим списки отображения (для OpenGL). Несмотря на то, что они являются «старый» способ, они могут быть быстрее. Вы должны выпекать список отображения в переменная ... если вы вызываете операции создания списка отображения в реальном времени, это будет нечестиво медленно. Как список отображения быстрее? Это только обновляет атрибуты состояния, vs per-vertex. Это означает, что я могу пройти до шести лиц, затем один цвет (по сравнению с цветом для каждой вершины вокселей). Если вы используете GL_QUADS и кубические вокселы, это может сэкономить до 20 байт (160 бит) за воксел! (15 байт без альфа, хотя обычно вы хотите сохранить 4-байтовое соответствие.)

  6. Я использую метод грубой силы для рендеринга «кусков» или страниц данных, что является общей методикой. В отличие от осей, это много проще /быстрее читать /обрабатывать данные, хотя гораздо меньше памяти (однако в эти дни вы можете получить 64 гигабайта памяти для $ 200- $ 300) ... не то, что средний пользователь имеет это. Очевидно, вы не может выделить один огромный массив для всего мира (1024x1024x1024 набор вокселей - 4 гигабайта памяти, предполагая, что 32-битный int используется на вокселе). Таким образом, вы выделяете /dealloc многие малые массивы, основанные на их близость к зрителю. Вы также можете выделить данные, получить необходимый список отображения, а затем сбрасывать данные для сохранения памяти. я думаю идеальной комбинацией может быть использование гибридного подхода осей и массивы - хранить данные в массиве при выполнении процедурных поколение мира, освещение и т. д., а затем поддерживайте октет для обнаружения столкновений и других менее дорогостоящих задач.

  7. Render near far far ... пиксель с подрезанным временем сохраняется. Gpu будет бросать пиксель, если он не проходит тест буфера глубины.

  8. Отображать только куски /страницы в окне просмотра (самоочевидно). Даже если gpu знает, как скопировать polgyons внеокно просмотра, передача этих данных еще требует времени. Я не знаю, что больше всего Эффективная структура для этого была бы («позорно», я никогда не написано дерево BSP), но даже простой raycast на каждой части может улучшить производительность и, очевидно, проверить против просмотра frustum сэкономит время.

  9. Очевидная информация, но для новичков: удалите каждый отдельный полигон который не находится на поверхности, т. е. если воксель состоит из шести граней, удалите лица, которые никогда не оказываются (прикасаются к другому вокселей).

  10. Как общее правило всего, что вы делаете в программировании: CACHE МЕСТОНАХОЖДЕНИЕ! Если вы можете хранить кеш-локальные (даже для небольшого количество времени, это будет иметь огромное значение. Это означает сохраняя ваши данные конгруэнтными (в той же области памяти), а не переключение областей памяти на обработку слишком часто. Так, в идеале, работа на один кусок на поток, и сохранить эту память исключительно для нить. Это относится не только к кэшу CPU. Подумайте о кэш-иерархия, как эта (самая медленная и самая быстрая): сеть (облако /база данных /etc) -> жесткий диск (получить SSD, если вы еще этого не сделали иметь один), ram (получить тройной канал или большую ОЗУ, если вы не уже есть), CPU Cache (s), регистры. Попытайтесь сохранить свои данные на последний конец, а не поменять его больше, чем вам нужно.

  11. Threading. Сделай это. Миры Voxel хорошо подходят для нарезки резьбы, так как каждая часть может быть рассчитана (в основном) независимо от других ... I видел буквально почти 4-кратное улучшение (на 4-жильном, 8-ти точечном Core i7) в процессуальном поколении мира, когда я писал процедуры для нарезание резьбы.

  12. Не используйте типы данных char /byte. Или шорты. Ваш средний у потребителя будет современный процессор AMD или Intel (как вы, вероятно). Эти процессоры не имеют 8-битных регистров. Oни вычислять байты, помещая их в 32-разрядный слот, а затем конвертировать их обратно (возможно) в память. Ваш компилятор может делать всевозможные voodoo, но использование 32 или 64-битного номера даст вам наиболее предсказуемые (и самые быстрые) результаты. Аналогично, значение «bool» не принимает 1 бит; компилятор часто использует 32 бита для bool. Может возникнуть соблазн сделать некоторые типы сжатия на ваши данные. Например, вы можете хранить 8 вокселей в виде одного номера (2 ^ 8 = 256 комбинаций), если они были одного типа /цвета. Однако вы должны думать о последствиях этого - это может сэкономить немалую память, но это также может помешать производительность даже с небольшим временем декомпрессии, поскольку даже это небольшое количество дополнительных временных шкал кубически с размером вашего Мир. Представьте себе расчет расиста; для каждого шага raycast, вам нужно будет запустить алгоритм декомпрессии (если только вы придумали разумный способ обобщения расчета для 8 вокселов на одном шаге луча).

  13. Как отмечает Хосе Чавес, шаблон дизайна мухи может быть полезно. Так же, как вы использовали бы растровое изображение для представления плитки в 2D игра, вы можете построить свой мир из нескольких 3D-плиток (или блоков) типы. Недостатком этого является повторение текстур, но вы можете улучшите это, используя текстуры дисперсии, которые подходят друг другу. Как эмпирическое правило, вы хотите использовать instancing, где бы вы ни находились.

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

  15. Размотайте петли и держите массивы плоскими! Не делайте этого:

    for (i = 0; i <chunkLength; i ++) {
     для (j = 0; j <chunkLength; j ++) {
      для (k = 0; k <chunkLength; k ++) {
       MyData [i] [j] [k] = newVal;
      }
     }
    }
    //Вместо этого сделаем следующее:
    для (i = 0; i <chunkLengthCubed; i ++) {
     //вычисляем x, y, z индекс куска с использованием модулей и операторов div на i
     //myData должно иметь chunkLengthCubed количество индексов, очевидно
     myData [i] = newVal;
    }
    

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

РЕДАКТИРОВАТЬ 2: при использовании многоиндексных циклов лучше всего использовать цикл z, y, x, а не наоборот. Ваш компилятор может оптимизировать это, но я был бы удивлен, если бы это произошло. Это максимизирует эффективность доступа к памяти и местоположения.

for (k <0; k <volumePitch; k ++) {
    для (j = 0; j <volumePitch; j ++) {
        для (i = 0; i <volumePitch; i ++) {
            myIndex = k * volumePitch * volumePitch + j * volumePitch + i;
        }
    }
}
  1. Иногда вам приходится делать предположения, обобщения и жертвы. Лучшее, что вы можете сделать, это предположить, что большая часть вашего мира полностью статична и меняет только каждые несколько тысяч кадров. Для анимированных частей мира это можно сделать в отдельном проходе. Также предположите, что большая часть вашего мира полностью непрозрачна. Прозрачные объекты могут отображаться в отдельном проходе. Предположим, что текстуры изменяются только в единицах x, или что объекты могут быть помещены только в x приращений. Предположим, что размер фиксированного мира ... как соблазнительный, как бесконечный мир, может привести к непредсказуемым системным требованиям. Например, для упрощения генерации воронного рисунка в вышележащих породах я предположил, что каждая точка центра voronoi находится в единой сетке с небольшим смещением (другими словами, подразумеваемым геометрическим хешированием). Предположим, что мир не обертывает (имеет ребра). Это может упростить многие сложности, введенные системой обертывания, при минимальных затратах на пользовательский интерфейс.

Подробнее о моих реализациях читайте на моем сайте

ответил Gavan Woolery 15 J0000006Europe/Moscow 2012, 04:00:24
7

Есть много вещей, которые Minecraft мог бы сделать более эффективно. Например, Minecraft загружает все вертикальные столбы размером около 16x16 плиток и делает их. Я чувствую, что очень неэффективно отправлять и отображать много ненужных фрагментов. Но я не хочу, чтобы выбор языка был важным.

Java может быть довольно быстрой, но для чего-то такого ориентированного на данные, C ++ имеет большое преимущество со значительно меньшими накладными расходами для доступа к массивам и работы в байтах. С другой стороны, гораздо проще выполнять потоки на всех платформах Java. Если вы не планируете использовать OpenMP или OpenCL, вы не найдете этого удобства в C ++.

Моя идеальная система была бы немного более сложной иерархией.

Плитка - это единое целое, вероятно, около 4 байтов, чтобы хранить информацию, такую ​​как тип материала и освещение.

Сегмент будет представлять собой 32х32х32-фрагмент фрагментов.

  1. Флаги будут установлены для каждой из шести сторон, если эта целая сторона является сплошными блоками. Это позволит рендерингу закрывать сегменты за этим сегментом. В настоящее время Minecraft не выполняет тестирование окклюзии. Но было упоминание о доступности отбраковки оборудования , которая может быть дорогостоящей, но лучше, чем предоставление огромных сумм многоугольников на низкоуровневых картах.
  2. Сегменты будут загружаться только в память во время активности (игроки, NPC, физика воды, рост деревьев и т. д.). В противном случае они будут отправляться напрямую, все еще сжимаемые с диска на клиенты.

Sectors будет блоком сегментов размером 16x16x8.

  1. Секторы будут отслеживать самый высокий сегмент для каждого вертикального столбца, так что сегменты, превышающие это, могут быть быстро определены пустым.
  2. Он также будет отслеживать нижний окклюзионный сегмент, так что каждый сегмент, который нужно визуализировать с поверхности, можно быстро схватить.
  3. Секторы также будут отслеживать следующий раз, когда каждый сегмент должен быть обновлен (физика воды, рост деревьев и т. д.). Таким образом, загрузка в каждом секторе будет достаточной, чтобы сохранить мир в живых и загружать только в сегменты, достаточные для выполнения своих задач.
  4. Все позиции сущностей будут отслежены относительно Сектор. Это предотвратило бы ошибки с плавающей запятой, присутствующие в Minecraft во время путешествия очень далеко от центра карты.

World будет бесконечной картой секторов.

  1. Мир будет отвечать за управление секторами и их последующие обновления.
  2. Мир будет превентивно отправлять сегменты игрокам по их потенциальным путям. Minecraft реагирует на сегменты, которые клиент запрашивает, вызывая задержку.
ответил Josh Brown 24 J0000006Europe/Moscow 2011, 07:22:57
5

Minecraft довольно быстр, даже на моем 2-ядерном. Java, похоже, не является ограничивающим фактором, здесь, хотя есть немного задержки сервера. Местные игры кажутся лучше, поэтому я собираюсь предположить некоторые неэффективности, там.

Что касается вашего вопроса, Notch (автор Minecraft) долгое время рассказывал об этой технологии. В частности, мир хранится в «кусках» (иногда вы их видите, особенно когда его нет, поскольку мир еще не заполнен.), Поэтому первая оптимизация - решить, можно ли увидеть кусок или нет .

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

Обратите также внимание на то, что существуют блоки FACES, которые можно считать невидимыми из-за того, что они скрыты (например, другой блок закрывает лицо) или в каком направлении указывает камера (если камера обращена к северу , вы не можете видеть Северное лицо ЛЮБЫХ блоков!)

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

Ваш вопрос непонятен, если вы хотите оптимизировать скорость рендеринга, размер данных или что. Уточнение там было бы полезно.

ответил Olie 12 J0000006Europe/Moscow 2011, 23:38:16
4

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

Причина, по которой Minecraft работает медленно, имеет LOT, чтобы делать некоторые сомнительные, низкоуровневые дизайнерские решения - например, каждый раз, когда на блок ссылается позиционирование, игра проверяет координаты примерно с 7 операторами if, чтобы убедиться, что это не за границами. Кроме того, нет возможности захватить «кусок» (блок 16x16x256 блоков, в котором работает игра), а затем ссылаться на него непосредственно, чтобы обойти проверки кеша и, кроме того, глупые вопросы проверки (так как каждая ссылка на блок также включает в частности, с помощью куска). В моем модуле я создал способ захватить и изменить массив блоков напрямую, что увеличило массовое поколение подземелий от неумелого отставания до незаметно быстрого.

EDIT: Удалено утверждение о том, что объявление переменных в разных областях привело к повышению производительности, на самом деле это не так. Я полагаю, что в то время, когда я объединил этот результат с чем-то другим, над которым я экспериментировал (в частности, удалением бросков между удвоениями и поплавками во взрывоопасном коде путем консолидации до удвоения ... понятно, это оказало огромное влияние!)

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

Итак, любой язык, который вы выберете, попытайтесь получить очень интимную информацию о деталях реализации /низкого уровня, потому что даже одна небольшая деталь в проекте, такая как это, может иметь значение (один пример для меня в C ++: «Может ли компилятор статические встроенные указатели функций? »Да, это возможно! Сделал невероятную разницу в одном из проектов, над которыми я работал, поскольку у меня было меньше кода и преимущество вложения.)

Мне очень не нравится этот ответ, потому что он затрудняет разработку на высоком уровне, но это болезненная истина, если производительность является проблемой. Надеюсь, вы нашли это полезным!

Кроме того, ответ Гэвина охватывает некоторые детали, которые я не хотел повторять (и многое другое! Он явно более осведомлен по этому вопросу, чем я), и я согласен с ним по большей части. Мне придется поэкспериментировать с его комментариями относительно процессоров и более короткими переменными размерами, о которых я никогда не слышал. Я хотел бы доказать себе, что это правда!

ответил Philip 17 J0000006Europe/Moscow 2012, 05:11:53
2

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

То, что вы делаете с этими данными, зависит от вас. Для производительности GFX вы можете использовать Обрезание для клипа скрытых объектов, объектов, которые слишком мал, чтобы быть видимым и т. д.

Если вы просто ищете технологии графической производительности, я уверен, что вы можете найти горы вещей в сети.

ответил Jonathan Connell 31 Maypm11 2011, 16:32:37
1

Что-то посмотреть - это шаблон дизайна Flyweight . Я считаю, что большинство ответов здесь так или иначе ссылаются на этот шаблон дизайна.

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

Но даже местоположение может быть сведено к минимуму: если вы знаете, что участок земли имеет один тип, почему бы не сохранить размеры этой земли как одного гигантского блока с одним набором данных о местоположении?

Очевидно, что единственный способ узнать - начать реализовывать свои собственные и сделать некоторые тесты памяти для производительности. Дайте нам знать, как это происходит!

ответил Jose Chavez 25 J0000006Europe/Moscow 2011, 01:31:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132