Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Обработка столкновений  (Прочитано 15041 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mfcer__
Команда клуба

ru
Offline Offline

« : 09-08-2004 23:55 » 

Добрый день!

Есть такая задачка.

Существует два массива вершин, то есть Vertex Buffer'а.
каждый из массивов - это какая - либо трехмерная фигура, объект...

Фигуры двигфаюся, то есть изменяются их координаты вершин...
Вопрос: как отследить столкновение объектов?

Можно примерчик на C++   Вот такой я вот

Спасибо заранее.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 10-08-2004 06:26 » 

теорию я не знаю, но примерно должно быть следующее:

Объекты А и В - замкнутые выпуклые трёхмерные объекты. Если они невыпуклые, их надо разбить на выпуклые. Они составлены из треугольных полигонов, которые заданы вершинами.
Пусть определяется, что A столкнулся с B. "А столкнулсяс В" - то есть хотя бы одна из вершин A оказалась внутри B или хотя бы одна из вершин В оказалась внутри А.

Так как объекты выпуклые, то:
1)находим геометрический центр объекта А - СА
2)находим геометрический центр объекта В - СВ
3)проводим линию от СА к СВ. Это нормаль n к некой плоскости Т.
4)проводим плоскость Та перпендикулярно n через вершину объекта А
5)проводим плоскость Тb перпендикулярно n через вершину объекта В
6)через вершину объекта А, НАИБОЛЕЕ БЛИЗКУЮ к плоскости Tb, проводим плоскость Tab.
7)Если плоскость Tab касается (с некоторой точностью) хоть одну вершину объекта B , не пересекая ребёр объекта B, то объекты А и В касаются
8)Если плоскость Tab пересекла хоть одно ребро объекта B , то объекты А и В пересекаются
Записан

Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #2 : 10-08-2004 23:04 » 

осталось реализовать  Отлично

А есть примерчики...
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 11-08-2004 05:02 » 

примерчиков нет...

но, ежели никто больше не отзовётся, можно попытаться :

 :arrow: нахождение геометрического центра(ГЦ) - если объект (ОБ) не неняется, то ГЦ(Cx,Cy,Cz) находим один раз при инициализации

CОБx=S(ОБvxi)/n
CОБy=S(ОБvyi)/n
CОБz=S(ОБvzi)/n

Vi - i-я вершина ОБ,  n - количество вершин

CAx=S(CAvxi)/n
CAy=S(CAvyi)/n
CAz=S(CAvzi)/n

CBx=S(CBvxi)/n
CBy=S(CBvyi)/n
CBz=S(CBvzi)/n

 *** CA, CB - нашли ***

 :arrow:
проводим линию Lcb через точки CA и CB.
Уравнение прямой:
Lcb = (x-CAx)/Lvx = (y-CAy)/Lvy = (z-CAz)/Lvz ;

Lv(Lvx,Lvy,Lvz)=(CBx-CAx, CBy-CAy, CBz-CAz) (направляющий вектор прямой)

(причём здесь направление вектора - от CA к CB)

 :arrow: составляем уравнение плоскости Tb:

Lvx*(x-CBx)+Lvy*(y-CBy)+Lvz*(z-CBz)=0

 :arrow:
теперь находим расстояния от вершин ОБ A до плоскости Tb до .

расстояние D от вершины Av(Avx, Avy, Avz) до плоскости

D = (Lvx*CAx + Lvy*CAy + Lvz*CAz)/ |Lv|

где |Lv| - модуль вектора Lv

 :arrow:

Теперь:
1) Если расстояние  D положительное, то эта вершина ОБ A находится "на расстоянии" от ОБ B
2) Если расстояние  D равно нулю (+- точность=0,0...01), то эта вершина ОБ A находится "коснулась" ОБ B
3) Если расстояние  D отрицательное, то эта вершина ОБ A "пересекла" ОБ B

в кавычках - потому, что это можно использовать только для упрощённой модели столкновений.

Если же надо точно, то:
 :arrow:

находим вершину ОБ A, у которой "наименьшее" расстояние от плоскости Tb. Снова в кавычках, потому что снова условности: расстояние берём не по модулю, а со знаком, как есть.
Пусть вершина Av1 - искомая вершина.

Теперь самое сложное.

проводим через Av1 плоскость Ta1, параллельную Tb:
Lvx*(x-Avx)+Lvy*(y-Avy)+Lvz*(z-Avz)=0

теперь представь, что происходит: плоскость, проходящая через вершину ОБ A, пересекает ОБ B. В результате на этой плоскости образуется замкнутая кривая и точка. Кривая состоит из линий, образованных пересечением полигонов ОБ B с плоскостью Ta1. Это отдельная задача - с ходу я так не придумаю...
А дальше нужно просто определить, попала ли точка внутрь кривой. Но кривая может выродится и в точку (плоскость коснулсь ОБ B) или вообще отсутствовать (точка "перемахнула" за ОБ B). В обоих этих случаях объект А пересёк ОБ B.
Если кривая существует, то есть опять два способа определить, внутри ли точка , или нет : упрощенный и очень точный Улыбаюсь

 :arrow: упрощенный
здесь просто очерчиваем кривую прямоугольником и определяем, находится ли точка внутри него
 :arrow: точный - всеми правдами и неправдами определяем, находится ли точка внутри...

Вот и остались две задачи, которые я с ходу не решу
1) Кривая состоит из линий, образованных пересечением полигонов ОБ B с плоскостью Ta1.
2) здесь просто очерчиваем кривую прямоугольником и определяем, находится ли точка внутри него

на это времени у меня сейчас не хватит Жаль
Записан

npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 11-08-2004 11:09 » 

Цитата: Алексей1153

Пусть определяется, что A столкнулся с B. "А столкнулсяс В" - то есть хотя бы одна из вершин A оказалась внутри B или хотя бы одна из вершин В оказалась внутри А.


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

Более точное определение пересечения -- хотя бы один многоугольник из A пересекается с хотя бы одним многоугольником из B.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 11-08-2004 20:51 » 

Вдобавок, проверяемые многоугольники должны быть выпуклые, а единственный гарантированно выпуклый многоугольник - треугольник. Значит, надо разбить фигуры на треугольники и их проверять. Разбивка на треугольники то же непростая задача...
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 12-08-2004 04:27 » 

RXL,   Вот такой я вот
ты имел в виду - тетраэдры, наверное Ага

но, додекаэдр тоже выпуклый. Эллипсоид тоже выпуклый, а вот бумеранг - "впуклый".

Цитата

Разбивка на треугольники то же непростая задача...

настолько ли... хотя тут тебе, наверное, виднее

А нельзя так: берём одну вершину за общую, а основаниями призм будут кажные 3 вершины (соответственно по дае смежные на соседние призмы, не считая общей вершинй, конечно) ?
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 12-08-2004 09:14 » 

Алексей1153, мне кажется, что ты ошибаешься: традиционно трехмерная графика работает с плоскими элементами, а не с объемными фигурами, которые в данном случае есть набор плоских. Так что не путай многоугольники с многогранниками. :?

Насчет разбивки на треугольники: легко и просто разбить только выпуклый многогранник.

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 12-08-2004 11:17 » 

В трёхмерной графике (практической) все поверхности представляются как наборы треугольников.  Поэтому поверхность триангулировать не надо.

Краткое описание алгоритма.

Отсортировать оба множетсва вершин по какой-нибудь координате, например Z.  

Воображаемая плоскость, расположенная перпендикулярно Z,  двигается вдоль оси Z от точки с наименьшей координатой к точке с наибольшей координатой.  

Заведём два множества, каждое хранит информацию о треугольниках, которые пересекаются воображаемой плоскостью, по одному множеству из каждой фигуры (поверхности).

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

Плоскость движется от точки к точке.  Так как мы отсортировали множества точек, то получается, что плоскость последовательно (по порядку возрастания Z) пройдёт через все точки обеих фигур.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 12-08-2004 11:47 » new

RXL,

Цитата

Насчет разбивки на треугольники: легко и просто разбить только выпуклый многогранник.


в терминах не сошлись немного Улыбаюсь

говоришь: "трёхмерное тело разбить на двухмерные", а имеешь в виду "поверхность трёхмерного тела разбить на полигоны треугольной формы"
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines