Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Как проверить пересекаются ли два куба?
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

Mask


Новичок

Кубы заданы матрицами как в OpenGL. Векторы Up, Direction, Right и позиция. Длины векторов могут быть различными, они задают длины граней кубов по своим направлениям.

Вопрос как проверить входят они один в другой или нет.

Самое простое, что приходит в голову, найти обратную матрицу для одного из них. Домножить на неё матрицу второго, и проверять попадают ли его вершины и грани внутрь первого.

После чего найти обратную матрицу второго, и проделать всё тоже самое с первым.

Но это долго. Может есть более быстрый путь?

Искал в Гугле.
http://www.google.ru/search?num=100&hl=ru&as_qdr=all&q=box-box+intersection&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&lr=
Безуспешно.

Всего сообщений: 21 | Присоединился: январь 2007 | Отправлено: 11 янв. 2007 7:04 | IP
Ntony


Удален

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

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

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

P.S. А вы, никак, компьютерную игру делаете?

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 11 янв. 2007 14:21 | IP
Mask


Новичок

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

Поэтому проверять наверное нужно пересечение эллепсоидов. Только не пойму как. Они же повёрнуты. А через поиск обратной матрицы не хочется. Потому, что это долго.

Всего сообщений: 21 | Присоединился: январь 2007 | Отправлено: 14 янв. 2007 5:38 | IP
VF



Administrator

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

Всего сообщений: 3109 | Присоединился: май 2002 | Отправлено: 14 янв. 2007 7:19 | IP
Ntony


Удален


Поэтому проверять наверное нужно пересечение эллепсоидов. Только не пойму как. Они же повёрнуты. А через поиск обратной матрицы не хочется. Потому, что это долго.

Если вы про время выполнения операций, то это не должно быть долго - набор SSE инструкций, насколько я помню, оптимизирован как раз под работу с матрицами. Да и в том же OpenGL есть элементарные способы умножения на матрицу поворота в одно действие...

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 14 янв. 2007 11:20 | IP
Mask


Новичок

SSE - это только для данных идущих подряд, поэтому для вычисления обратной матрицы они не подходят. ( Или может быть я какого-то метода не знаю ).

В общем я написал функцию. Работает не особо быстро, но это лучше, чем ничего. Благодарю.


Теперь вопрос, как проверить столкновения сфероидов? Сфероид - это сфера, заданная матрицей 4x4, то есть три вектора и позиция, но векторы могут быть различной длины.

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

Такая задача вообще решаемая?
Если да, то какие используются подходы?

Всего сообщений: 21 | Присоединился: январь 2007 | Отправлено: 15 янв. 2007 6:56 | IP
Mask


Новичок

Есть такой документ: http://www.geometrictools.com/Documentation/IntersectionOfEllipsoids.pdf

Но там пересечение элепсоидов описано на математическом языке. Мне бы как нибудь его перевести на язык простых формул.

Чтобы это вычислить, потом это, потом это. И т. д. А ?

Всего сообщений: 21 | Присоединился: январь 2007 | Отправлено: 16 янв. 2007 7:46 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com