Как написать функцию проверки столкновений двух сфероидов?

← →
Кубоид (2007-01-15 06:45) [0]

Сфероид - это сфера с произвольными размерами по осям.
Задаётся матрицей 4x4. GLScene.
Как проверить столкновения сфер знаю. А вот как со сфероидами, которые могут быть вытянутыми - без понятия.
Или хотя бы может кто нибудь знает как сделать проверку столкновения сферы со сфероидом?

← →
Кубоид (2007-01-15 07:19) [1]

Исходники ODE:
http://opende.svn.sourceforge.net/viewvc/opende/

Такое ощущение, что там нет функций столкновений ... Или это я не нашёл?

← →
Elen © (2007-01-15 07:56) [2]

> Такое ощущение, что там нет функций столкновений ... Или
> это я не нашёл?

Если речь идет о GLScene то можно попробовать определить столкновения черезCollisionManager

← →
Думкин © (2007-01-15 08:15) [3]

> Сфероид - это сфера с произвольными размерами по осям.

А параллелепипед - это куб с произвольными размерами по осям. А кактус - это недоразвитый ежик.

Речь об эллипсоиде? В случае двух элипсоидов задача с водится к столкновению сферы и элипсоида. Так как имеется аффиное преобразование переводящее один из эллипсоидов в сферу. При этом пересекаемость будет инвариантна к преобразованию.

Затем можно перенести элипсоид в начало координат - чтобы удобнее было. Провести через центры прямую. Найтй 2 точки на сфере принадлежащие этой прямой.
Точка внутри эллипсоида(в начале координат), для нее верно x^2/a^2+y^2/b^2+z^2/c^2<1 и с братным знаком - вовне. От этого и плясать.

← →
Думкин © (2007-01-15 08:20) [4]

Хотя подумалось тут - этого мало будет. :(

← →
Думкин © (2007-01-15 08:34) [5]

Можно подумать в таком направлении: когда мы один элипсоид засунули в начало координат и хорошо повернули - чтобы оси его и коороси совпадали, то можно рассмотреть такую функцию x^2/a^2+y^2/b^2+z^2/c^2 и найти ее эктсремумы на втором элипсоиде - они будут, потому что множество компактное. Посмотреть на величины экстремумов. Оба меньше 1 - внутри, оба больше 1 - снаружи, по очереди - столкновение.

← →
Кубоид (2007-01-16 04:48) [6]

> Думкин © (15.01.07 08:34) [5]
> Можно подумать в таком направлении: когда мы один элипсоид
> засунули в начало координат и хорошо повернули - чтобы оси
> его и коороси совпадали, то можно рассмотреть такую функцию
> x^2/a^2+y^2/b^2+z^2/c^2 и найти ее эктсремумы на втором
> элипсоиде - они будут, потому что множество компактное.

Ты сам то понял, что сказал?

← →
Кубоид (2007-01-16 04:55) [7]

Непойму. Newton с открытыми исходниками? Если да, то где на sourceforge они лежат?

← →
Кубоид (2007-01-16 05:22) [8]

> Думкин © (15.01.07 08:15) [3]
> Речь об эллипсоиде? В случае двух элипсоидов задача с водится
> к столкновению сферы и элипсоида. Так как имеется аффиное
> преобразование переводящее один из эллипсоидов в сферу.

Если речь об умножении MatrixMultiply на обратную матрицу вычисленную через функцию InvertMatrix, то тогда оси второго сфероида уже не будут взаимоперпендикулярными.

← →
Думкин © (2007-01-16 06:18) [9]

> Кубоид (16.01.07 04:48) [6]

Я то? Я то понял. А вот вы видимо ни разу. Но задавайте вопросы - не стесняйтесь. :)

> Кубоид (16.01.07 05:22) [8]

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

← →
MBo © (2007-01-16 07:05) [10]

http://www.geometrictools.com/Documentation/IntersectionOfEllipsoids.pdf
я бы не сказал, что простая задача...

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

← →
Кубоид (2007-01-16 07:07) [11]

> Думкин © (16.01.07 06:18) [9]
> И что? Нам же надо только факт столкновения выявить? А он
> для аффинных преобразований инвариантен.

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

← →
Думкин © (2007-01-16 07:10) [12]

> Кубоид (16.01.07 07:07) [11]

Я его нашел и описал. Как верно заметил Борис - задача не очень простая. И для ее понимания видимо надо знать чуток больше, чем знаете вы - раз не в состоянии понять того, что я описал. Удачных поисков простых решений.

← →
Думкин © (2007-01-16 07:15) [13]

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

← →
Кубоид (2007-01-16 07:38) [14]

> MBo © (16.01.07 07:05) [10]
>
> http://www.geometrictools.com/Documentation/IntersectionOfEllipsoids.
> pdf
> я бы не сказал, что простая задача...

Да. Это первая ссылка в Гугле на "Intersection of Ellipsoids".
Только кто бы это смог перевести с математического на русский.
Чего и как считать совершенно непонятно.

← →
Рамиль © (2007-01-16 09:30) [15]

> Кубоид (16.01.07 07:07) [11]

Если ты будешь так разговаривать, то тебе никто не переведет.

> перевести с математического на русский.

Математическая запись интернациональна, она - ноты в музыке, которую пишет программист

← →
Кубоид (2007-01-17 06:06) [17]

> ors_archangel © (16.01.07 13:54) [16]
> > перевести с математического на русский.
> Математическая запись интернациональна, она - ноты в музыке,
> которую пишет программист

Ну так и переведи нам, если такой умный.

> Кубоид
> Ну так и переведи нам, если такой умный.

На формумах обычно отвечают на вопросы, а не на оскорбления.
Imho лучше бы параметрически задал эллипс (например, положение в пространстве и поворот вокруг вокруг базовых осей), тогда математику из [3] можно было бы применять.

> ors_archangel © (17.01.07 06:25) [18]

Нет параметрически не надо. Можно пойти 2-мя путями для обоснования решения совершенно одинаковыми - либо перенести один в начало и превратить в сферу, либо работать с уже данными формулами эллипсоидов. Затраты одинаковые, но первый способ легче объяснить - почему работает.

Затем надо найти экстремум функций на множестве задаваемом функциями.
А это либо множители Лагранжа, либо итерации. Тут уже Яндекс в помощь - расписано много где.

> Думкин © (17.01.07 06:52) [19]

Ты меня не убедил. Почему нельзя задать эллипсоид центром, вращением по осям и радиусами a,b,c? Тогда задачу столкновения двух эллипсоидов можно было бы свести к задаче принадлежности точки эллипсоиду, увеличив радиусы эллипсоида на радиус сферы (она получена после аффиного преобразования). Дальше, как ты и предлагал, переходим в новую систему координат: перенося её на минус центр эллипсоида и поворачивая вокруг осей на углы, противоположные тем, что задают эллипсоид. Тогда столкновение есть, если sqr x/a + sqr y/b + sqr z/c < 1. При аффином преобразовании, преобразовывающем один из эллипсоидов в сферу, проще перерассчитать новые радиусы второго эллипсоида, чем итерационно искать экстремум, а что такое множители Лагранжа, я не знаю, может и эффективно считаются, я знаю только интерполяционный многочлен Лагранжа и ещё теорему, про сущ c: f(b)-f(a)=(b-a)f "(c), если есть непрерывность и чё-то там есчо

> ors_archangel © (17.01.07 08:37) [20]

Честно, - не понял.

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

Множители Лагранжажа.
http://iasa.org.ua/iso.php?lang=rus&ch=5&sub=2

Я специально привел пример со сферой в центре. Посмотрите почему я прихожу к выводу, что надо искть экстремумы на втором эллипсоиде функции x^2+y^2+z^2.

Если не понятно - отвечу позже.

Как написать функцию проверки столкновений двух сфероидов? Найти похожие ветки