Построение Octree для создания ландшафта

9

Ранее я реализовал марширующие кубы / тетраэдры для рендеринга IsoSurface. Это работало ( YouTube ), но производительность была ужасной, так как я никогда не удосужился реализовать переменную Level of Detail, основанную на расстоянии просмотра (или даже удалив старые, отдаленные фрагменты).

Я решил пойти еще раз и сделать это правильно на этот раз. Я начал с создания OctreeNode, который при вызове работает следующим образом Build().

  • Если кусок слишком мал для сборки, немедленно вернитесь.
  • Работайте, если поверхность проходит через объем этого куска.
  • Если так, тогда решите, хотим ли мы поднять LOD (потому что камера находится близко)
  • Если так, то порождайте 8 детей и вызывайте на них один и тот же процесс
  • Если нет, создайте сетку, используя размеры текущего узла

Какой-то псевдокод:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ Помимо возврата плотности в точке, источник плотности может определять возможный диапазон плотности для данного объема.

² Поставщик LoD берет ограничивающую рамку и возвращает максимально желаемый LoD на основе положения камеры / усеченного конуса, пользовательских настроек и т. Д.

Итак ... Все это работает довольно хорошо. Используя простую сферу в качестве источника плотности и показывая все узлы:

Полный октри

И только листья

Октри показывает только листья

Тем не менее, есть несколько проблем:

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

Я подумал о нескольких вариантах, но оба кажутся ошибочными:

  • Сохраняйте коллекцию Octrees и добавляйте / удаляйте в зависимости от расстояния. Не могу понять, как мне было бы хорошо совмещаться… плюс мне нужен список известных пустых узлов, особенно если я хочу произвольные трехмерные поверхности (чтобы избежать повторного расчета пустых объемов)
  • Добавьте родительский узел к текущему корню, затем добавьте семь братьев и сестер для исходного узла. Это будет работать и по требованию, но кажется, что сложно разумно сжиматься, когда игрок движется по ландшафту. Это также сделало бы номера LoD еще менее значимыми.

In [В пояснении к Q ниже] В настоящее время, если 2 физически смежных узла в дереве находятся в разных LOD, у меня есть некоторый код для приведения вершин так, что при создании сеток шва нет. Я могу сделать это, зная плотность для множества окружающих узлов. В сценарии, где у меня есть 2 независимых октода рядом, у меня не было бы легкого способа получить эту информацию, что привело бы к швам.

Какой оптимальный способ подойти к этому?

основной
источник

Ответы:

1

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

Я должен определить начальный ограничивающий объем (и чем он больше, тем больше обработки мне нужно сделать)

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

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

Если вы исправите свое корневое дерево на какое-то «достаточно большое значение», тогда «LoD относительно начального объема» не должно быть проблемой. И, как уже упоминалось выше, я не думаю, что дополнительный уровень на вершине повлияет на общую производительность.

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

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

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

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


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

Я думаю, что логарифмический масштаб октри делает его еще осуществимым. Если ваш верхний уровень имеет ширину 1 000 00 000 000 м (это будет в 25 раз шире, чем у реальной Земли, и с 625-кратной площадью поверхности), а биты самого низкого уровня имеют ширину 10 см, то это 32 уровня в октрее, что, вероятно, достаточно управляемый. Если вы хотели планету в 100 раз шире Земли (и в 10000 раз большую площадь поверхности), это всего лишь дополнительные 3-4 уровня в вашей октрие. В этот момент игроку понадобится сотни лет, чтобы пройтись по миру, и если вы используете наивную математику с плавающей запятой, мир будет накапливать ошибки точности.

Сохраняйте коллекцию Octrees и добавляйте / удаляйте в зависимости от расстояния. Не могу понять, как мне было бы хорошо совмещаться… плюс мне нужен список известных пустых узлов, особенно если я хочу произвольные трехмерные поверхности (чтобы избежать повторного расчета пустых объемов)

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

Джимми
источник
Спасибо за ответы. Я не могу просто выбрать огромный начальный объем, так как моя местность бесконечна (это моя цель). Посмотрите видео, чтобы получить представление. Таким образом, мое дерево узлов станет еще выше. Если предположить, что маленькие узлы имеют масштаб, то это может означать, что я буду путешествовать по континенту десятки, если не сотни уровней. Re: Перебираясь, позвольте мне добавить больше деталей к вопросу [Готово]
Основное
Что касается игрока, то «миллиард миль» довольно близок к «бесконечному». В ответ добавлено больше аргументов для фиксированного начального объема.
Джимми
Я все еще не убежден. Почему 30+ слоев обработки бесполезно известны? Это не элегантно, не говоря уже об эффективности. Я полагаю, что время пришло, чтобы пройтись, но мы просто говорим о создании ландшафта. Ничто из того, что говорит о том, что я должен сосредоточиться в начале координат, и что полеты на высокой скорости невозможны (хотя я бы не стал мешать на этой скорости!). FWIW Я использую удвоения внутри, чтобы избежать этой проблемы точности.
Basic