Как сделать бесконечную вселенную?

Мне интересно, каковы лучшие практики в индустрии разработки игр для рендеринга 3D-вселенной?

Чтобы быть более конкретным:

• Точки данных даны и статичны. Каждая точка имеет положение, цвет и размер;
• Весь набор данных намного больше доступной памяти;
• Пользователь должен иметь возможность «уменьшить», чтобы увидеть большую картинку сразу;

Самый наивный подход - разделить вселенную на кубы и визуализировать только то, что видно. Я не уверен, как в этом сценарии я должен реализовать «уменьшение». Должен ли я предварительно вычислять кубы для каждого возможного уровня масштабирования? Или, может быть, есть лучшие подходы?

Я ищу не зависящее от технологии решение.

Это основано на моих размышлениях и просмотре исходного кода Селестии.

Селестия позволяет летать вокруг планеты и уменьшать масштаб, чтобы увидеть всю галактику. Я просмотрел его исходный код и обнаружил, что он использует октри, структуру для рекурсивного разделения пространства на 8 октантов.

Средство визуализации будет визуализировать окружение путем обхода октодерева и не проходить глубоко через дальние объекты.

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

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

Другими космическими играми, которые я могу назвать, являются Orbiter и Kerbal Space Program с закрытым исходным кодом. Я также посмотрел на Галактику Границы, которая процедурно генерировала звездную карту. Существует веб-сайт, анализирующий работу игры по ее разборке: http://www.jongware.com/galaxy1.html

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

• Уровень детализации - автоматический (или «ручной») выбор подробных или упрощенных моделей, или даже спрайтов, или просто точек, или для объектов, которые находятся дальше.
• Отбраковка - выбор только рисовать то, что нужно. Это может быть то, что находится в поле зрения (отбраковка усеченного конуса), что не спрятано за другими вещами (отбраковка окклюзии) или другие специальные методы. (Ответ @Alan Wolfe описывает некоторые способы организации ваших данных, которые помогают упростить выборку.)
• Потоковая передача - извлечение мировых данных из хранилища в память по мере необходимости, если они все не помещаются в память сразу
• Sky box - очень отдаленные объекты можно предварительно визуализировать на сфере, которая находится на «бесконечном расстоянии» от камеры.

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

Все, что является иерархическим и / или редким, должно помочь вам здесь.

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

Октри также очень хорошо подходит для того, чтобы вы могли запрашивать у него список всех объектов в области видимости, который позволит вам получить список только тех объектов, которые находятся в пределах вашего угла обзора и не слишком отдалены. Разреженное решение может быть чем-то вроде разреженной сетки, где вы можете запросить информацию о любом местоположении x, y, z, но вам нужно хранить информацию только для ячеек, которые не являются пустым пространством.

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

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

Некоторые решения (например, BSP) могут быть очень эффективными, но их создание занимает много времени, поэтому они обычно не являются хорошим выбором для перемещения / изменения объектов.

Надеюсь, это поможет, дайте мне знать, если у вас есть какие-либо вопросы о деталях!