Когда использовать Двоичное Разделение Пространства, Дерево квадрантов, Дерево октантов?
В Java все находится в форме класса.
Если вы хотите использовать любой объект, тогда у вас есть две фазы:
- Объявить
- Инициализация
Пример:
- Объявление:
Object a; - Инициализация:
a=new Object();
То же самое для концепции массива
- Объявление:
Item i[]=new Item[5]; - Инициализация:
i[0]=new Item();
Если вы не дают секцию инициализации, тогда возникает NullpointerException.
7 ответов
Нет никакого четкого ответа на Ваш вопрос. Это зависит полностью, как Ваши данные организованы.
Что-то для учета:
Деревья квадрантов работают лучше всего на данные, которые являются главным образом двумерными как рендеринг карты в системах навигации. В этом случае это быстрее, чем деревья октантов, потому что это адаптируется лучше к геометрии и сохраняет структуры узла маленькими.
Деревья октантов и BVHs (Иерархии Ограничивающего объема) извлекают выгоду, если данные являются трехмерными. Это также работает очень хорошо, если Ваши геометрические объекты кластеризируются в 3D пространстве. (см. Дерево октантов по сравнению с BVH)
преимущество Oc-и Деревьев квадрантов - то, что можно прекратить генерировать деревья каждый раз, когда Вы желаете. Если Вы хотите представить графику с помощью графического акселератора, она позволяет Вам просто генерировать деревья на уровне объектов и отправлять каждый объект в единственном тянуть-вызове к графическому API. Это работает очень лучше, чем отправка отдельных треугольников (что-то, что необходимо сделать при использовании Деревьев BSP для полного объема).
Деревья BSP являются особым случаем действительно. Они работают очень очень хорошо в 2D и 3D, но генерация хороших Деревьев BSP является видом искусства самостоятельно. Деревья BSP имеют недостаток, что Вам, вероятно, придется разделить Вашу геометрию на мелкие кусочки. Это может увеличить полное количество полигона Вашего набора данных. Они хороши для рендеринга, но они намного лучше для обнаружения коллизий и трассировки лучей.
А хорошее свойство деревьев BSP - то, что они разлагают суп полигона на структуру, которая может быть отлично представлена наоборот (и наоборот) от любого положения камеры, не делая фактического вида. Порядок с каждой точки зрения является частью структуры данных и сделанный во время Древовидной BSP компиляции.
, Что, между прочим, причина, почему они были несколько настолько популярные 10 лет назад. Quake использовал их, потому что он позволил графическому механизму / растрирующий процессор программного обеспечения не использовать дорогостоящий z-буфер.
Все упомянутые деревья являются просто семьями деревьев. Существуют свободные деревья октантов, гибридные деревья kd-деревьев и много других связанных структур также.
BSP является лучшим для городских сред.
Дерево квадрантов А является лучшим для того, когда Вы используете карту высоты для ландшафта, и т.д.
, Дерево октантов является лучшим для того, когда у Вас есть глыбы геометрии в 3-м пространстве, такие как солнечная система.
BSPs являются хорошим вариантом для ускорения обнаружения коллизий, в зависимости от которого аромата Вы используете. Они особенно быстры в точке и строке или излучают тесты, несколько менее быстрые и немного более сложные для вещей с объемом.
Что касается их использования в графике, BSPs являются в значительной степени устаревшими. Деревья октантов работают хорошо на вещи как грубый отбор видимости, также, как и деревья AABB.
У меня нет большого опыта с BSPs, но я могу сказать, что необходимо пойти с деревьями октантов по деревьям квадрантов, когда Вы сцена, которую Вы представляете, высоки. Таким образом, высота является больше чем половиной ширины и глубины - мало эмпирического правила. Обычно деревья октантов не принесут огромную стоимость по деревьям квадрантов, и у них есть потенциал для ускорения вещей достойный бит. YMMV.
Обычно эти вещи не имеют ясного ответа. Я предположил бы, что A, B, и C являются результатом функции размера Вашего пространства и суммы материала, который Вы дифференцируете.
BSP лучше для меньшего, более простого пространства, с которым Вы только хотите сделать поглощение газов. Если Вы захотите все пересечения для данного луча, необходимо будет обновить до четверки/дерева октантов.
Что касается дерева квадрантов по сравнению с деревом октантов - о каком количестве размеров Вы заботитесь много? Два размера означают дерево квадрантов, четыре дерево октантов. Столь установленный, как дерево квадрантов может работать в с тремя пространствами, но если Вы хотите каждый размер, предоставленный надлежащее лечение, дерево октантов является способом пойти.
Если Вы не знаете то, что Вы делаете, всегда идут для деревьев октантов, таким образом, можно прекратить фокусироваться на сверхоптимизации и начать работать над более серьезными функциями. Серьезно узкие места всегда будут где-то в другом месте, или Вы разрабатываете Вас код на основе оптимизированной системы, которая в конце предотвращает определенные типы изменений позже.