Как узнать, что отрезок прямой пересекает треугольник в трехмерном пространстве?

Question

У меня есть треугольник, определенный 3 точками в трехмерном пространстве.У меня также есть отрезок, определяемый двумя точками в трехмерном пространстве.Я хочу знать, пересекаются ли они.Мне действительно не нужно знать точку пересечения.

Я не знаю исчисления, но знаю некоторые триггеры.Я знаю кое-что о матрицах, но хорошо понимаю векторы (особенно 3d-векторы).Пожалуйста, сделайте это просто.

Можете ли вы рассказать мне пример проблемы:

треугольник:

a: -4, 3, 0

b:4, 3, 0

c: -3, -5, 4

линейный сегмент:

d: 1, -2, 0

e: -2, 6, 2

РЕДАКТИРОВАТЬ:

Я собираюсь использовать это в физическом движке c ++.

Один ответ связан с вычислением объема тетраэдра из 4 вершин.Пожалуйста, предоставьте формулу или покажите ее в коде.

Answer 1

Вот один из способов решения вашей проблемы.Вычислить объем тетраэдра Td = (a, b, c, d) и Te = (a, b, c, e).Если объем Td или Te равен нулю, то одна конечная точка сегмента de лежит на плоскости, содержащей треугольник (a, b, c).Если объемы Td и Te имеют один и тот же знак, то де лежит строго в одну сторону, и пересечения нет.Если Td и Te имеют противоположные знаки, то de пересекает плоскость, содержащую (a, b, c).

Оттуда есть несколько стратегий.Одним из них является вычисление точки р, где де пересекает эту плоскость.Затем спроецируйте вниз в 2D и решите задачу точка-треугольник в 2D.

Другой способ - вычислить объемы тетраэдров (a, b, d, e), (b, c, d, е) и (с, а, д, е).Тогда только если все три имеют один и тот же знак, де пересекает треугольник (a, b, c).

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