Я думал об этой проблеме. Возможно ли с помощью современной технологии создать точную копию земли 1: 1 в игре на основе вокселей? Какая структура данных лучше всего подходит для хранения этой гигантской карты? Какой алгоритм следует использовать для визуализации этой структуры данных в режиме реального времени?
Эти вопросы делают следующие предположения:
Каждый воксель имеет разрешение 1 кубический метр.
Для простоты каждому вокселю требуется только 1 байт информации метаданных. Эта информация будет использоваться для хранения идентификатора «типа» вокселя (земля, вода, камень и т. Д.).
Объем земли составляет 1 * 10 21 куб.
Под «современной технологией» я понимаю все, что имеется в продаже, но не суперкомпьютеры.
Для составления карты будут использоваться только топография и батиметрия Земли. Человеческое здание, растения или пещеры исключены. Подземные блоки будут выбраны на основании геологических исследований, например: если глубина превышает 3000 км, то визуализируют воксель «магмы».
Как и в Minecraft, карта не является статичной, ее можно изменять в игре.
«Бесконечное» расстояние прорисовки - большой плюс, какой смысл иметь всю карту на карте, если вы не можете взлететь и наблюдать за всей планетой?
Первый вывод, который я пришел, когда подумал об этой проблеме, заключается в том, что хранение данных о Земле линейным способом невозможно, если предположить, что каждый воксел занимает только 1 байт памяти, для сохранения карты все равно потребуется 1 зетабайт. Так что требуется какое-то сжатие.
Я думаю, что воксельное октри может сжать карту, но я не уверен, насколько. Энтропия этой воксельной карты, вероятно, очень низкая, поэтому я предполагаю, что может быть достигнут очень высокий уровень сжатия.
отказ
Это теоретический вопрос, я не собираюсь писать воксельную землю
РЕДАКТИРОВАТЬ
ESA GOCE уже нанес на карту геоид Земли с точностью 1–2 см. Я считаю, что эта информация может быть использована для создания очень точной карты высот Земли. Это исключило бы необходимость использования алгоритма для заполнения пробелов в топографии Земли.
источник
Ответы:
Это зависит от используемого вами метода пространственного разделения, хотя все методы разделения (как и любой метод сжатия) в конечном итоге оказываются там, где дальнейшее сжатие невозможно, из-за издержек структуры данных и других логических / математических факторов. Пример можно найти в октреях. Для каждого узла в октрее необходимо сохранить указатель на его родителя и / или потомков (в зависимости от того, как вы работаете с архитектурой структуры данных), чтобы обеспечить значимый обход. Любая древовидная структура может содержать n детей. Чем ниже соотношение 1: n, тем более эффективно используется пространство, которое вы получаете, и, следовательно, тем больше накладных расходов при обходе дерева, поскольку у вас должно быть больше узлов-предков, чтобы содержать такое же количество листовых вокселей (в вашем случае, примерно 510 триллионов из них представляющих площадь поверхности).
Учитывая, что в вашем случае основными проблемами являются стоимость хранения и рендеринг всей планеты (или ее частей) с достаточного расстояния, нет структуры данных, которую я бы порекомендовал бы за октри. Mipmapping является необходимостью: диаметр 12,8 миллиона метров при ближайшей более высокой степени 2 составляет 2 ^ 24 = 16,8 миллиона. 24 уровня восхождения на октаву означали бы огромное количество ветвлений - очень дорого для GPU и CPU. Но при условии, что вы все делаете правильно, вам нужно будет пройти только несколько уровней за раз. Однако, учитывая количество места, которое требуется, альтернативы немногочисленны и далеко друг от друга (см. Ниже).
Возможности mipmapping в ocerees делают его таким невероятно мощным инструментом для больших объемов, которые вы описываете. В отличие от всех других известных методов деления (за исключением KD-деревьев), октроя сохраняет деление на уровень минимальным, что означает, что визуальные и физические различия между уровнями mipmap также сохраняются минимальными, что означает гораздо более тонкие различия в детализации при переходе вверх и вниз по дереву.
Если, с другой стороны, вы хотите создать мир, в котором обход иерархической сетки сведен к минимуму, вам нужно будет обменять пространство на увеличение скорости.
Говоря об идеальном соотношении 1: n, в этом отношении нет более тонкой структуры, чем kd-дерево. Если октри делится на 2 для каждой оси, в результате чего 2 ^ 3 = 8 отдельных дочерних ячеек, дерево kd разделяется ровно один раз на уровень подразделения. Проблема в том, что вы должны выбрать гиперплоскость для разделения, и эту гиперплоскость можно выбрать вокруг любой из 3 осей. Несмотря на то, что он является оптимальным с точки зрения пространства, он делает 3D-обходы (например, во время лучевых меток, основной операцией при использовании октодеев для физики или рендеринга) гораздо более трудными, чем в октодереве, так как для записи необходимо сохранять динамическую структуру типа портала интерфейсы между отдельными узлами дерева kd.
RLE - это другой подход к сжатию, но его во многих отношениях сложнее применить к такой проблеме (где основа операций сферическая), поскольку сжатие RLE является одномерным, и вы должны выбрать ось, в которой оно работает. планета, можно было бы выбрать полярную ось, но любой одноосный выбор привел бы к определенным проблемам с обходами для рендеринга и физики при действии с определенных неоптимальных углов. Конечно, вы можете также запустить RLE по 3 осям одновременно, утроив стоимость хранения или по 6 осям (-x, + x, -y, + y, -z, + z) в качестве дополнительной оптимизации.
Так что ответить на ваш вопрос (или нет!)
Я не собираюсь прямо отвечать на вопрос о том, какое оборудование, но я думаю, что рассмотрение этого вопроса с точки зрения октодерева начинает давать вам представление о том, что на самом деле возможно на каком типе оборудования. Я бы посоветовал вам пойти по этому пути, если вы действительно хотите знать, может быть проще всего реализовать простое разреженное октри(см. статью Лейна в ссылках) и поместите в нее сферическую оболочку поверхностных вокселей и посмотрите, каково полученное в результате использование пространства. Шаг вперед оттуда. Посмотрите, как далеко вы можете пройти, прежде чем ваша системная память начнет выдавать. Это не требует написания рендерера, если вы не хотите визуализации. Также имейте в виду, что это лучше всего делать на процессорах - графические процессоры в целом не имеют емкости памяти для решения проблем такого масштаба. Это одна из причин, по которой Intel рассматривает переход к массово параллельным процессорам: преимущества GPGPU, который лучше в этом деле, могут быть применены к гораздо более обширному пространству памяти без узких мест системной шины. Есть, вероятно, другие здесь или на mathematics.stackexchange.com,
Конечно, с точки зрения вашего требования к расстоянию до бесконечности, но вопрос всегда сводится к тому, «сколько деталей на каком расстоянии». Рендеринг бесконечных деталей потребовал бы бесконечных ресурсов. Вот тут-то и вступают в игру переменные на сцену. Также имейте в виду, что все структуры данных воплощают некоторый компромисс скорости для пространства или наоборот. Это означает меньше / медленнее рендеринг, если вы хотите больший мир за то же количество инженерных усилий.
источник
Поскольку вы, скорее всего, никогда не узнаете свойства каждого кубического метра реального мира, вам понадобится какой-то способ генерировать эти данные, которые являются неопределенными на основе предположений. Так что, если вы это выяснили, нет необходимости вычислять и хранить все эти данные, но вы можете сгенерировать их на лету.
Прежде всего, вы можете отказаться от всех вокселей в земле, потому что их нужно будет рассчитать только в том случае, если кто-то действительно выкопает яму, например. воксели становятся видимыми.
Для поверхности Земли я бы, вероятно, взял изображение в качестве отправной точки для моих расчетов. Может быть, какая-то карта температуры и влажности позволит вам рассчитать тип применяемых блоков. Например. Вода, песок (пустыня), трава, снег и т. Д. Поскольку на изображении, вероятно, не будет одного пикселя информации на каждый квадратный метр земной поверхности, вам придется смешать его с некоторым шумом, чтобы немного изменить поверхность. Если вы всегда используете одни и те же случайные числа, ваш результат должен быть детерминированным.
Кроме того, будет полезна карта высот, чтобы вы могли определить высоту элементов поверхности. Таким образом, вы можете добавить горы и т. Д.
Таким образом, это сводится к объему данных некоторых 2D-изображений, которые содержат информацию о земной поверхности. Для всего, что находится внутри, вы вернетесь к чисто процедурному подходу, при котором вы будете рендерить различные типы блоков, в зависимости от расстояния от центра земли. Но, как сказано выше, они должны быть рассчитаны только, когда кто-то копает яму.
Чтобы сделать изменения постоянными, я бы только сохранил изменения в мире. Поэтому, если кто-то вырыт яму, я буду хранить информацию о том, какие воксели были удалены, так как я должен быть в состоянии процедурно визуализировать окружающие воксели.
Что касается рендеринга: вам понадобятся некоторые сложные алгоритмы уровня детализации и отбора, чтобы сделать эту работу. Глупо рендерить все поверхностные вокселы, когда камера находится на уровне масштабирования, который показывает весь мир. На этом уровне вокселы должны быть намного больше, может быть, даже простой текстурированной сферы будет достаточно.
Я предполагаю, что самой сложной вещью будет иметь твердотельный генератор, который позволяет вам рассчитывать свойства вокселей даже для разных «разрешений», чтобы вы могли использовать его для генерации разных уровней детализации.
источник
Вы можете сделать то же самое, что Minecraft. Вместо того, чтобы создавать такой объем данных, вы можете определить мир как математическую формулу, когда для отображения необходим фрагмент данных, вы генерируете его с помощью формулы.
Такая формула обычно строится с использованием концепции шума Перлина , она учитывает детали на всех уровнях, у вас могут быть такие же большие горные цепи, как в реальном мире, но вы можете выбрать только небольшую их часть. Вы можете генерировать количество деталей, которое вам нравится, так что можно делать очень мелкие детали для близких вещей, а также создавать отдаленные пейзажи с требуемым уровнем детализации.
Minecraft сохраняет все те блоки, которые вы посетили, в комплекте с любыми внесенными изменениями, можно просто сохранить только разницу между созданным миром и обновленным миром, но я думаю, что сохранять большие блоки было проще, и они сжимаются относительно хорошо.
Я не думаю, что есть какая-то игра, которая действительно доводит это до предела, но очень часто используют формальную генерацию всех «неважных» деталей больших игровых миров. Я не уверен, насколько распространен подход генерации при необходимости, в отличие от простого генерирования партии и ее записи на диск.
источник
Вы можете искать векторные данные наземных массивов Земли, поскольку векторные данные имеют преимущество в масштабировании до любого масштаба, который вы хотите. Объедините его с картой высоты Земли, чтобы получить высоту местности. Последний шаг - это детальные спутниковые снимки, из которых вы можете выбрать тип верхнего блока на основе изображения, чтобы получить камень там, где есть камень, песок там, где есть песок и т. Д. Вероятно, должны быть сгенерированы фактические внутренние поверхности планеты. как Minecraft делает это, если вы не можете найти подробные географические данные для работы. По сути, вы хотите найти географические данные и экстраполировать их, учитывая только ввод координат XYZ. Это означает, что у вас ограниченные данные, и вы экстраполируете все остальное как можно точнее.
источник