Пересечение треугольников в 3d

@karaulov6 · Регистрация: 23.03.2013

Author24 — интернет-сервис помощи студентам

Вот например 2 треугольника: (для примера)

C++

struct Point
{
   int X;
   int Y;
   int Z;
};
 
struct Triangle
{
   Point p1;
   Point p2;
   Point p3;
};
...
 
//First triangle
Point p1;
p1.X = 0;
p1.Y = 0;
p1.Z = 0;
Point p2;
p2.X = 0;
p2.Y = 0;
p2.Z = 10;
Point p3 ;
p3.X = 10;
p3.Y = 0;
p3.Z = 0;
Triangle t1 ;
t1.p1 = p1;
t1.p2 = p2;
t1.p3 = p3;
...
//Second Triangle
Point p1;
p1.X = 5;
p1.Y = 5;
p1.Z = 5;
Point p2;
p2.X = 5;
p2.Y = -5;
p2.Z = 5;
Point p3;
p3.X = 5;
p3.Y = 0;
p3.Z = 10;
Triangle t2;
t2.p1 = p1;
t2.p2 = p2;
t2.p3 = p3;

Как определить пересекаются они или нет.

Есть ли готовая функция для этого? (не важно c++ или c#)

@_Ivana · 19.10.2014, 21:37

Может в опЕнгле или директиксе каком-нибудь есть, хотя не факт. Можно попробовать самому написать. 3 точки не лежащие на одной прямой (а треугольник это подразумевает) однозначно задают плоскость. 2 плоскости либо параллельны, либо пересекаются по прямой, уравнение которой можно получить из уравнений плоскостей. Эта прямая лежит в плоскостях каждого треугольника, можно проверить, пересекает ли она его - если пересекает хотя бы одну из сторон. Если она пересекает оба треугольника, то они пересекаются. Предварительно можно перейти в другую систему координат через сдвиг+поворот, но навскидку особого облегчения расчетов при этом не получится.

@karaulov6 · 19.10.2014, 22:32 **[ТС]**

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

@_Ivana · 19.10.2014, 22:33

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

Ilot · 23.10.2014, 08:31

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

@Alexandr_1982 · 23.10.2014, 08:49

В boost возможно есть или в CryEngine / unreal engine.

@Mr.X · 14.12.2014, 06:08

Сообщение от _Ivana

Может в опЕнгле или директиксе каком-нибудь есть, хотя не факт. Можно попробовать самому написать. 3 точки не лежащие на одной прямой (а треугольник это подразумевает) однозначно задают плоскость. 2 плоскости либо параллельны, либо пересекаются по прямой, уравнение которой можно получить из уравнений плоскостей. Эта прямая лежит в плоскостях каждого треугольника, можно проверить, пересекает ли она его - если пересекает хотя бы одну из сторон. Если она пересекает оба треугольника, то они пересекаются. Предварительно можно перейти в другую систему координат через сдвиг+поворот, но навскидку особого облегчения расчетов при этом не получится.

Сообщение от Ilot

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

По этим гипотезам непересекающиеся треугольники
{ (0,0,-1), (0,0,1), (-1,0,0) } и
{ (1,-1,0), (1,1,0), (2,0,0) }
пересекаются.
На самом деле к гипотезе _Ivana нужно добавить, чтобы отрезки, по которым прямая пересечения плоскостей пересекает треугольники, имели бы больше одной общей точки.

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	19.10.2014, 21:37	2
	Сообщение было отмечено karaulov6 как решение Решение Может в опЕнгле или директиксе каком-нибудь есть, хотя не факт. Можно попробовать самому написать. 3 точки не лежащие на одной прямой (а треугольник это подразумевает) однозначно задают плоскость. 2 плоскости либо параллельны, либо пересекаются по прямой, уравнение которой можно получить из уравнений плоскостей. Эта прямая лежит в плоскостях каждого треугольника, можно проверить, пересекает ли она его - если пересекает хотя бы одну из сторон. Если она пересекает оба треугольника, то они пересекаются. Предварительно можно перейти в другую систему координат через сдвиг+поворот, но навскидку особого облегчения расчетов при этом не получится. 0

@karaulov6 23 / 23 / 6 Регистрация: 23.03.2013 Сообщений: 245
	19.10.2014, 22:32 [ТС]	3
	Просто думаю где-нибудь должны использоваться такие функции) гуглил так и не нашел готовой)) 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	19.10.2014, 22:33	4
	А вот я не думаю, что она еще кому-нибудь нужна. Поэтому чем искать "такой же, но с перламутровыми пуговицами", проще написать свою. 0

Ilot $Эксперт по математике/физике$ 2048 / 1366 / 395 Регистрация: 16.05.2013 Сообщений: 3,506 Записей в блоге: 6
	23.10.2014, 08:31	5
	Определить просто. Берете первый треугольник и ищете скалярное произведение векторов проведенных от любой точки первого треугольника к вершинам второго на нормаль к первому треугольнику. Если все произведения имеют один знак значит треугольники не пересекаются. Если для одной вершины знак будет противоположен проделываем ту же операцию, но теперь меняем треугольники местами. Если произведения имеют разные знаки треугольники пересекаются. Если же одного знака - не пересекаются. 0

@Alexandr_1982 191 / 90 / 33 Регистрация: 04.11.2013 Сообщений: 474 Записей в блоге: 4
	23.10.2014, 08:49	6
	В boost возможно есть или в CryEngine / unreal engine. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	14.12.2014, 06:08	7
	Сообщение от _Ivana Может в опЕнгле или директиксе каком-нибудь есть, хотя не факт. Можно попробовать самому написать. 3 точки не лежащие на одной прямой (а треугольник это подразумевает) однозначно задают плоскость. 2 плоскости либо параллельны, либо пересекаются по прямой, уравнение которой можно получить из уравнений плоскостей. Эта прямая лежит в плоскостях каждого треугольника, можно проверить, пересекает ли она его - если пересекает хотя бы одну из сторон. Если она пересекает оба треугольника, то они пересекаются. Предварительно можно перейти в другую систему координат через сдвиг+поворот, но навскидку особого облегчения расчетов при этом не получится. Сообщение от Ilot Определить просто. Берете первый треугольник и ищете скалярное произведение векторов проведенных от любой точки первого треугольника к вершинам второго на нормаль к первому треугольнику. Если все произведения имеют один знак значит треугольники не пересекаются. Если для одной вершины знак будет противоположен проделываем ту же операцию, но теперь меняем треугольники местами. Если произведения имеют разные знаки треугольники пересекаются. Если же одного знака - не пересекаются. По этим гипотезам непересекающиеся треугольники { (0,0,-1), (0,0,1), (-1,0,0) } и { (1,-1,0), (1,1,0), (2,0,0) } пересекаются. На самом деле к гипотезе _Ivana нужно добавить, чтобы отрезки, по которым прямая пересечения плоскостей пересекает треугольники, имели бы больше одной общей точки. 0

Пересечение треугольников в 3d

Решение