Я предлагаю на рассмотрение свой алгоритм проверки на пересечение треугольников. Возможно, что я изобрёл велосипед. Но зато свой :).

Вместо предисловия.

Я тут в качестве хобби делаю некую программку, которая имеет дело с 3D объектами. Программка на Java, так что доступа к железу у меня считайте что нет, да и не нужен он для этой задачи - мне ничего рисовать не надо, мне нужно просто файлы с объектами модифицировать. И у меня возникла необходимость проверять на пересечение треугольников. Вообще-то я никогда не имел дела с 3D графикой (не нужно было), но вроде как геометрию ещё помню. Я поискал в интернете по поводу того, как это обычно делают другие и что советуют. Насколько я понял, ничего не предлагается лучше, чем просто в лоб расчитывать прямую пересечения плоскостей и точек пересечения тругольников с прямой и сопоставления их положения на прямой. Мне как-то не верилось, что нельзя проще, ну или хотя бы оптимальнее для большого числа треугольников. В моём случае мне нужно по сути находить все колизии треугольников из двух мешей. Достаточно самого факта пересечения, никаких точных точек пересечения мне не нужно. Насколько я понимаю, это же самое обычно требуется для определения (точного!) факта столкновения объектов в 3D. Так что моя задача достаточно распространённая.

Идея.

Так как нам не нужны координаты пересечения, то мы можем смело использовать преобразования координат, которые не нарушают факт пересечения треугольников, например, аффинные преобразования. Но так как само преобазование тоже довольно дорогое удовольствие, то нужно выбрать такое, которое сильно упрощает задачу. Я выбрал преобразование, которое переводит пару векторов, образующих один треугольник, и их нормализованный векторное произведение в декартовый базис. В новой системе координат один из тругольников это треугольник задаваемый единичными векторами на осях х и y. Формулы нахождения точек пересечения треугольников получаются на удивление простыми, надо просто использовать факт, что там z=0.

Вторая маленькая идея - я использовал сумму x и y координат точек пересечения для того, чтобы понять пересекаются ли образованые ими отрезки. Так как мы знаем, что эти точки точно находятся на прямой, то вроде бы достаточно использовать одну из координат, кроме случая, когда прямая перпендикулирна этой оси. Можно, конечно, сделать сначала проверки и потом выбирать нужную ось, но я подумал, что достаточно использовать сумму координат, тем более, что она легко находится для всех точек (для двух точек даже и складывать не нужно, т.к. вторая координата всегда 0, либо известно, что сумма=1). После этого достаточно двух сравнений чтобы установить факт пересечения.

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

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

> Вторая маленькая идея

Вот тут бы подробностей. У меня пока на уровне - "я нифига не понял".

> Думкин ©   (31.08.10 07:16) [1]
>
> > Вторая маленькая идея
>
> Вот тут бы подробностей. У меня пока на уровне - "я нифига
> не понял".
>

Ну на самом деле всё просто. Концы отрезка пересечения прямой и единичного треугольника (тот, который на декатовом базисе) могут быть или оба на осях, или один на оси и один на гипотенузе. Для всех точек на гипотенузе x+y=1. Для всех точек на осях - вторая координата = 0, причём и первая находится просто.

Для второго треугольника сложнее, но не так, как кажется на первый взгляд.
Чтобы найти точку пересечения стороны треугольника и плоскости нам нужно найти разложение вектора этой точки на сумму векторов концов s*v1 +  (1-s)*v2. Это легко сделать, если рассмотреть проекцию на плоскость x0z(или y0z). Очевидно, что этот значение параметра зависит только от значений z-координат концов. На самом деле мне самому это сначало было неочевидно и я это заметил только после того, как маткад выдал слишком простую формулу и я понял, что был более простой путь найти параметр. А получив его легко считаем x и y точек пересечения, ну или сразу их сумму, чтобы съэкономить на одном умножении.

Ну а теперь о том, почему достаточно сравнивать суммы координат точек. Так как известно, что все точки лежат на одной прямой, то x+y для каждой точки на этой прямой это тоже линейная функция и она не может нарушить факта перечения или непересечения отрезков. А с одним числом (суммой) проще обращаться, чем с парой координат. Теперь мы имеем пару чисел для каждого треугольника, находим из них наибольшее, потом сравниваем минимумы и максимумы двух пар. Если пересекаются - значит треугольники пересекаются.

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

Полезная ссылочка
http://www.realtimerendering.com/intersections.html

> Омлет ©   (06.09.10 13:16) [3]
>
> А не проще ли проверить на пересечение одного треугольника
> и ребер второго, и наоборот? Если все 6 проверок дали отрицательный
> результат, значит треугольники не пересекаются. Если хотя
> бы одна проверка дала положит. рез-тат - пересекаются.
>
А не проще. Потому как тоже предполагает очень много вычислений, причём зачем-то вычисляются координаты точек пересечения отрезков с плоскостями, которые нам в конечном счёте и не нужны. Это и предлагается везде в интернете (не считая откровенно неверных методов проверки).

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

> Омлет ©   (06.09.10 13:19) [4]
> Полезная ссылочка
> http://www.realtimerendering.com/intersections.html

Я описал свой алгоритм адмнистраторам этого сайта и мне уже даже ответили. Говорят, что о таком алгоритме не слышали, но идея им понравилась.
Спасибо за наводку на сайт. Куда бы ещё написать?
Неужели я таки изобрёл свой велосипед ? :)

Спасибо за наводку на сайт. Куда бы ещё написать?

На gamedev.ru?

Что касается самого принципа преобразования системы координат для упрощения вычислений - то он не нов, например, слышал о методе проверки пересечения с OOBB (Object Oriented Bounding Box) трансформацией его в AABB (Axis Aligned...). Хотя не припомню, чтобы это применялось к треугольникам.
И кстати, вы пробовали считать операции, хотя бы теоретически оно может быть быстрее? Допустим, с опр. кол-ва треугольников, когда простота теста компенсирует сложность вычисления матрицы трансформации.
Другое дело, что те же геймдевелоперы, как я понимаю, даже "точные" столкновения проверяют не по детализированным рендер-моделям, а по упрощённым полигональным болванкам, просто нет смысла проверять все полигональные "рюшечки". Так что им проверка очень большого кол-ва полигонов может быть и не нужна, ну и точка столкновения обычно всё же требуется.

Администратор realtimerendering.com (некий Tomas Akenine-Möller) тоже упомянул, что он встречал преобразование координат в других алгоритмах и использовал их в своих статьях, но в других контекстах. Для треугольников он такого подхода не встречал. Естественно, я понимаю, что преобразование координат в 3D графике должно использоваться широко. Тем более для меня, человека с мат.образованием, удивительно, что никто такого решения не предлагает. Для меня это было первое, что пришло в голову для упрощения этой задачи (ну учили нас тогда так).

По количеству операций для одной проверки будет скорее всего больше. Но изюминка в том, что результат доброй половины вычислений можно сохранить и использовать с другим треугольником. И ещё многие части легко параллелятся, что сейчас модно. Например, нахождение обратной матрицы и трансформирование координат. Кстати, возможны и оптимизации нахождения обратной матрицы, ведь вектор нормали у нас уже изначально по построению пердендикулярен двум другим. Наверняка можно упростить, если использовать этот факт, надо поиграться в маткад-матлаб.  
И ещё попутно легко находятся другие факты про эти треугольники. Например, предварительная проверка на то, что вершины второго треугольника находятся по разные стороны от плоскости или лежат на плоскости в моём случае делается просто тривиально в качестве побочного эффекта - достаточно начинать преобразование с вычисления новых z-координат вершин второго треугольника и сравнить их с нулём. Напомню, что для обычного алгоритма для этого нужно считать сначала векторное произведение векторов первого треугольника, а потом скалярное для каждой вершины, т.е. тоже не так уж и мало вычислений. Вырожденый случай, когда треугольники в одной плоскости у меня тоже проще - мы получаем второй треугольник в плоскости z=0 и можем сразу с ним работать. Другой пример - проверки в конце алгоритма, которые тоже намного проще. Например, проверка прохождения прямой пересечения плоскостей - тривиальна, необходимо и достаточно чтобы хотя бы одна из точек пересечения с осями x и y была в интервале [0,1]. Ну и т.д. и т.п..

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

Попробую написать на gamedev.ru ...

> Alex Konshin ©   (07.09.10 13:12) [8]
> По количеству операций для одной проверки будет скорее всего больше.

Возможно, самым большим тормозом здесь будет Java )