Коллизии кубиков

← →
pasha676 (2003-06-02 12:53) [0]

Подобная тема уже не раз всплывала в размых темах форума. Хотелось бы обсудить поподробнее.

Постоновка задачи.
Дано два 3D-объекта. Каждый описывается габаритным контейнером. Контейнер описывается шестью точками и есть собственно прямоугольник. Как отловить факт пересечения оптимальным способом?

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

Но может быть более оптимальное решение?

← →
Mirovodin (2003-06-02 13:26) [1]

Немного оптимизируем.

Дно куба A1,A2,A3,A4. Вершиа B1,B2,B3,B4. Соединяем A1-В4 диагональ или диаметр описанной сферы. Проще сначало проверять расстояния между центрами этих сфер всего 1 вычисление. Т.к. диаметр и его половину можно рассчитать заранее. Так сразу отметается половина столкновений, а уж если условие выполнилось, то по твоему алгоритму.

← →
JohnJ (2003-06-02 16:57) [2]

А тупо проверить каждую точку не быстрее будет?
Я сейчас прикинул и думаю, что не быстрее! А со сферой - вообще классно придумано! :)

← →
Mirovodin (2003-06-02 17:05) [3]

Можно еще оптимизировать, я подумаю как это можно сделать. Но вся проблема в том, что в итоге все равно придётся анализировать плоскости, если хотим узнать как именно столкнулись объекты.

← →
pasha676 (2003-06-02 17:09) [4]

Со сферой хорошо, если априорно паралепипеды действительно близки к кубической форме и/или предметы находяться достаточно далеко друг от друга. Хороший выигрыш. А вот если предметы вытянутые и рядом... то сфера к сожалению ничего не даст :(.

> А тупо проверить каждую точку не быстрее будет?

Что есть проверить каждую точку?

А есть ли алгоритм по типу находиться точка внутри другого контейнера? Если есть то может попробывать найти по каждой из восьми точек есть ли она в другом контейнере и все.

← →
pasha676 (2003-06-02 17:10) [5]

> если хотим узнать как именно столкнулись объекты.

Для начала нужен факт столкновения. Если уже столкнулись - то понятно.

← →
Mirovodin (2003-06-02 17:32) [6]

2 pasha676

> А вот если предметы вытянутые и рядом... то сфера к сожалению
> ничего не даст :(.

Нее тут нужно действовать методом " разделяй и властвуй " быстрым алгоритмом мы откидываем 90%, а вот 10% которые может быть столкнулись мы анализируем точно. Можно откидывать да же по расстоянию между центрами масс объектов :
Допутим :
Если > 10 м. - 100% не столкнуться.
< 10 м. начинаем сложный анализ.

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

← →
pasha676 (2003-06-03 09:36) [7]

2Mirovodin

Я полностью согласен насчет того, что надо делать предварительный подсчет - это здорово улутшить производительность.

Вот насчет коллизии контейнеров.

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

1) Берем вектора расположения и направления 1-го контейнера
2) Составляем матрицу преобразования (по этим векторам) - шлобальная система координат - локальная система координат контейнера.
3) Берем координаты вертексов 2-го контейнера, преобразовываем к системе координат первого и просто сравниваем покоординатно вертексы, таким образом, чтобы заметить пересечение.

Правда не совсем понятно можно ли сравнить расположение вертексов и сделать вывод о пересечении самих контейнеров...

← →
Mirovodin (2003-06-03 10:52) [8]

2 pasha676

Это конечно хорошо, мы устанавливаем факт колизии контейнеров. Но это несколько сложнее. И опять же мы установили факт стокновения контейнеров ! Но не объектов в них.

Метод описанный мной выше можно оптимизировать еще на порядок.
Алгоритм примерно следующий:

1. Делаем анализ расстояния между объектами т.е. расстояние между их центрами. D

2. Вычисляем радиус описанной сферы объекта - расстояние между центром и самой удаленной от нее точкой сложного объекта. R

Это было описано выше, просто уточняем, а далее новое :

3. Вычисляем радиус вписанной сферы - расстояние между центром и самой близкой к нему точкой сложного объекта. r

4. Сравниваем эти радиусы :

По результатам сравнения возможны 3 варианта :

Сумма a) R1+R2<D - объекты не столкнуться.
б) r1+r2>D - объекты столкнуться.
( результат б ) [8] 2 pasha676

Это конечно хорошо, мы устанавливаем факт колизии контейнеров. Но это несколько сложнее. И опять же мы установили факт стокновения контейнеров ! Но не объектов в них.

Метод описанный мной выше можно оптимизировать еще на порядок.
Алгоритм примерно следующий:

1. Делаем анализ расстояния между объектами т.е. расстояние между их центрами. D

2. Вычисляем радиус описанной сферы объекта - расстояние между центром и самой удаленной от нее точкой сложного объекта. R

Это было описано выше, просто уточняем, а далее новое :

3. Вычисляем радиус вписанной сферы - расстояние между центром и самой близкой к нему точкой сложного объекта. r

4. Сравниваем эти радиусы :

По результатам сравнения возможны 3 варианта :

Сумма a) R1+R2<D - объекты не столкнуться.
б) r1+r2>D - объекты столкнуться.
с) Сложный алгоритм проверки.

Пункты 2 и 3 делаются на этапе создания модели. Производится всего 1 вычисление D. Единственный "-" при столкновении объектов (результат б ) не известно как именно столкнулись модели. Сложные алгоритмы оценки позволяют возвращать результат - фигуру столкновения. Т.е. набор полигонов.

Коллизии кубиков Найти похожие ветки