Ограниченные узлы иерархии томов (линейная модель)

Сценарий Цепочка точек: (P i ) i = 0, N , где P i связан с его прямыми соседями (P i-1 и P i + 1 ).

Цель : выполнить эффективное обнаружение конфликтов между любыми двумя несмежными ссылками: (P i P i + 1 ) vs. (р J суб> P J + 1 суб>).

Вопрос : во всех работах рекомендуется рассматривать этот предмет обнаружения столкновений, чтобы использовать широкую фазу и реализовать его через иерархию ограниченных томов. Для цепочки, состоящей из узлов P i , она может выглядеть так:

введите описание изображения здесь

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

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

3 голоса | спросил teodron 13 J0000006Europe/Moscow 2012, 12:37:09

2 ответа


2

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

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

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

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

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

ответил MrCranky 13 J0000006Europe/Moscow 2012, 14:51:06
1

В том случае, если вы отправили сообщение, вы все равно получите выгоду от привязанного к оси ограничителя на основе BVH - первое подразделение может разделить левый /правый сегменты (или верхние /нижние сегменты) с очень небольшим перекрытием, объемы тоже будут хорошо разделяться.

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

ответил Vivian 3 rdEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 03 Sep 2015 01:05:17 +0300 2015, 01:05:17

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

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

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