ПрограммированиеТерминыФизикаФизика

Convex (Конвекс, выпуклая геометрия)

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

Несмотря на то, что английские слова «convex hull» означают «выпуклая оболочка», в литературе об определении столкновений (Collision Detection) под конвексом обычно понимается выпуклая замкнутая поверхность, представленная множеством треугольников.

Для нахождения пересечений между выпуклыми телами существует 3 основных метода: Separating Axis Theorem, V-Clip, Gilbert-Johnson-Keerthi. Особой популярностью в последнее время стал пользоваться последний (GJK) ввиду хорошей кешируемости и наличия хороших алгоритмов нахождении дополнительной контактной информации (нормаль контакта, глубина проникновения, точки контакта) — Expanded Polytope Algorithm (EPA), Minkowski Portal Refinement (MPR — он является заменой GJK, основанной на тех же принципах, и позволяет проще получить контактную информацию).

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

Что такое Convex (Конвекс, выпуклая геометрия)?

#collision detection

9 февраля 2008 (Обновление: 2 сен 2009)

Комментарии [4]

#1
1:31, 11 июня 2009

Добавил школьное определение выпуклости ( не, ну а вдруг? ), и добавил про алгоритмы CD для конвексов.
Не совсем понятно,
> Несмотря на то, что английские слова «convex hull» означают «выпуклая оболочка», в литературе об определении столкновений (Collision Detection)
> под конвексом обычно понимается выпуклая замкнутая поверхность, представленная множеством треугольников.
оно зачем? Ведь выпуклая замкнутая поверхность, представленная треугольниками и есть выпуклая оболочка, по сути (можно считать, что точки этого халла находятся внутри триангулированной поверхности же).

#2
1:51, 11 июня 2009

Только сейчас заметил что есть Narrow phase. Но я думаю править не стоит про алгоритмы КД, тут немного другими словами. Пусть повисит пока :)

#3
11:28, 11 июня 2009

XperienS
> Не совсем понятно,
опередил.

"Несмотря на то" совсем не к месту. Должно быть что-то типа:

В дословном переводе «convex hull» означает «выпуклая оболочка». В литературе об определении столкновений (Collision Detection) под конвексом обычно понимается выпуклая замкнутая поверхность, представленная множеством треугольников.

Прошло более 14 лет
#4
7:44, 29 авг 2023

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

ПрограммированиеТерминыФизикаФизика

Тема в архиве.