Как выполнить обнаружение столкновения на объектах, состоящих из множества маленьких треугольников?
13
Я понимаю, что любая форма может быть создана (или аппроксимирована) меньшими треугольниками. Любой прямоугольник может быть создан двумя меньшими треугольниками. Любой круг может быть создан из множества тонких треугольников "кусочек пиццы". Как это влияет на обнаружение столкновений?
Я понимаю, как рассчитать перекрытие прямоугольника, используя вершины. Я понимаю, как рассчитать перекрытие круга, используя центр, радиусы и расстояние.
Но как обнаруживать столкновения на фигурах из маленьких треугольников? Не конкретика, а просто общая концепция ....
Но как обнаруживать столкновения на фигурах из маленьких треугольников?
Не делая этого.
Обнаружение столкновений с произвольным набором треугольников (или, что еще хуже, между двумя наборами произвольных треугольников) непомерно дорого.
Вместо этого мы обычно выполняем обнаружение коллекции иерархическим образом, начиная сначала с чрезвычайно грубых, простых фигур (таких как прямоугольники или сферы), которые (плохо) аппроксимируют базовый объект.
Это позволяет нам быстро отклонить большинство потенциальных столкновений как «не происходящие», что является обычным случаем. В случае, когда такая грубая проверка проходит, это указывает на потенциальное фактическое столкновение, и мы приступаем к выполнению проверки по более подробному приближению базовой формы (например, из нескольких плотно подогнанных капсул или множества выровненные ограничительные рамки).
По сути, обнаружение столкновений начинается с грубых тестов и, по мере прохождения этих тестов, переходит к все более подробному представлению. Это изображение, предоставленное Широ в комментарии к ответу Александра , иллюстрирует, как сложная модель (человек) может быть представлена серией более простых форм:
В редких случаях нам действительно нужно выполнять столкновение на уровне отдельного треугольника, и когда мы это делаем, мы обычно используем более грубые методы, чтобы детализировать очень маленький набор потенциальных треугольников для проверки. В этот момент для выполнения тестов используются определенные алгоритмы, как если бы вы проверяли, перекрываются ли два прямоугольника. Например, вы можете определить, где и где луч попадает в треугольник .
Благодарю. Да, если бы я на самом деле делал игру, я бы просто использовал какой-нибудь существующий движок. Но я просто хочу понять основные идеи, которые реализованы в готовом механизме обнаружения столкновений. На приведенной выше диаграмме вы использовали бы математику прямоугольников, чтобы увидеть, касается ли что-либо ЛЮБОГО из десятков прямоугольников, из которых состоит человек. Это основная идея?
JackOfAll
Это ориентированные ограничительные рамки (3D), а не прямоугольники. Но да. Если бы я собирался проверить, столкнулся ли луч (представляющий, скажем, пулю) с игроком, я бы проверил луч на этих боксах - возможно, после первого тестирования на одном гигантском боксе, представляющем всего персонажа - не против каждого треугольник сетки рендеринга).
Идея состоит в том, что вы можете использовать грубое приближение символа, такое как ориентированные ограничивающие рамки, показанные на рисунке выше, и проверить, что сначала нужно выполнить менее дорогой тест на попадание, а если есть столкновение, то перейти к более низкому уровню. В случае необходимости, тестирование отдельных треугольников, содержащихся в ограничительной рамке. Как правило, может быть несколько разных BV, используемых иерархически, с внешним, менее точным, но самым быстрым для тестирования (сфера, ограничивающий прямоугольник) и углублением во что-то более конкретное (k-DOP), и потенциально углубление еще более (треугольники) )
Kik
4
Обнаружение столкновений основано на геометрии (примитивы, такие как линии, плоскости, сферы, коробки, капсулы, цилиндры).
Если вам необходимо выполнить обнаружение столкновений на фигурах, сделанных из треугольника, например, на местности, которая не является плоской, вы должны проверить все треугольники, которые образуют сетку.
Если вы дойдете до этого момента, я настоятельно рекомендую использовать готовый механизм обнаружения столкновений, поскольку такие вещи становятся довольно сложными, довольно быстрыми.
Как вы обнаруживаете столкновения на фигурах, составленных из треугольников?
JackOfAll
@JackOfВсе он уже упоминал, что в своем ответе он обычно использует геометрические фигуры i.stack.imgur.com/CAhxn.jpg
dimitris93
@JackOfВсе я отредактировал свой ответ; и, как говорит Широ, если в вашей среде есть более сложные «предметы» (тела, стулья, машины и т. д.), то при разработке игр они обычно состоят из более простых примитивов, которые связаны друг с другом. Обнаружение столкновений производится на примитивных формах, но затем выполняется физическое моделирование всего тела.
Vaillancourt
4
Я буквально не пытаюсь сделать игру, я просто хочу понять основные идеи, которые реализованы в готовом движке обнаружения столкновений. Если бы я на самом деле делал игру, я бы не стал изобретать велосипед, согласился.
Обнаружение столкновений основано на геометрии (примитивы, такие как линии, плоскости, сферы, коробки, капсулы, цилиндры).
Если вам необходимо выполнить обнаружение столкновений на фигурах, сделанных из треугольника, например, на местности, которая не является плоской, вы должны проверить все треугольники, которые образуют сетку.
Если вы дойдете до этого момента, я настоятельно рекомендую использовать готовый механизм обнаружения столкновений, поскольку такие вещи становятся довольно сложными, довольно быстрыми.
источник