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

Хотя другие ответы здесь уже охватывали принципы .

---

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

2-й, «более надежный метод» из ответа bobobobo ссылается на 3-плоскостное пересечение.

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

• Нет необходимости использовать матричный определитель 3×3,
  вместо этого мы можем использовать квадрат длины поперечного произведения между первой и второй плоскостью (которая является направлением 3-й плоскости) .
• Не нужно включать расстояние 3-го самолета,
  (вычисление конечного местоположения) .
• Не нужно отрицать расстояния.
  Сохраните некоторые CPU-циклы, заменив вместо этого перекрестный заказ.

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

// Intersection of 2-planes: a variation based on the 3-plane version. // see: Graphics Gems 1 pg 305 // // Note that the 'normal' components of the planes need not be unit length bool isect_plane_plane_to_normal_ray( const Plane& p1, const Plane& p2, // output args Vector3f& r_point, Vector3f& r_normal) { // logically the 3rd plane, but we only use the normal component. const Vector3f p3_normal = p1.normal.cross(p2.normal); const float det = p3_normal.length_squared(); // If the determinant is 0, that means parallel planes, no intersection. // note: you may want to check against an epsilon value here. if (det != 0.0) { // calculate the final (point, normal) r_point = ((p3_normal.cross(p2.normal) * p1.d) + (p1.normal.cross(p3_normal) * p2.d)) / det; r_normal = p3_normal; return true; } else { return false; } } 

Уравнение плоскости равно ax + by + cz + d = 0 , где (a, b, c) нормаль плоскости, d – расстояние до начала координат. Это означает, что каждая точка (x, y, z), которая удовлетворяет этому уравнению, является членом плоскости.

Учитывая два самолета:

 P1: a1x + b1y + c1z + d1 = 0 P2: a2x + b2y + c2z + d2 = 0 

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

 y = (-c1z -a1x -d1) / b1 z = ((b2/b1)*(a1x+d1) -a2x -d2)/(c2 - c1*b2/b1) 

Если вы сделаете x=0 , это станет проще:

 y = (-c1z -d1) / b1 z = ((b2/b1)*d1 -d2)/(c2 - c1*b2/b1) 

Поиск точки на линии

Чтобы получить пересечение двух плоскостей, вам нужна точка на линии и направление этой линии.

Найти направление этой линии очень просто, просто пересечь 2 нормали двух плоскостей, которые пересекаются.

 lineDir = n1 × n2 

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

Если вы хотите увидеть вывод о том, как это решить, вот математика за ним:

Пусть сначала x = 0. Теперь у нас есть 2 неизвестных в 2 уравнениях вместо 3 неизвестных в 2 уравнениях (мы произвольно выбрали одно из неизвестных).

Тогда плоские уравнения (члены A исключены, так как мы выбрали x = 0):

B ₁ y + C ₁ z + D ₁ = 0

B ₂ y + C ₂ z + D ₂ = 0

Нам нужны y и z такие, что эти уравнения решаются правильно (= 0) для данных B ₁ , C ₁ .

Итак, просто умножьте верхний eq на (-B ₂ / B ₁ ), чтобы получить

-B ₂ y + (-B ₂ / B ₁ ) * C ₁ z + (-B ₂ / B ₁ ) * D ₁ = 0

B ₂ y + C ₂ z + D ₂ = 0

Добавьте eqs, чтобы получить

z = ((-B ₂ / B ₁ ) * D ₁ – D ₂ ) / (C ₂ * B ₂ / B ₁ ) * C ₁ )

Бросьте z, который вы найдете в первом уравнении, чтобы найти y как

y = (-D ₁ – C ₁ z) / B ₁

Обратите внимание, что лучшая переменная, чтобы сделать 0, является с наименьшими коэффициентами, потому что она не имеет никакой информации. Поэтому, если C ₁ и C ₂ равны 0, выбор z = 0 (вместо x = 0) был бы лучшим выбором.

Вышеупомянутое решение все еще может быть испорчено, если B ₁ = 0 (что не так маловероятно). Вы можете добавить в некоторые операторы if, которые проверяют, если B ₁ = 0, и если это так, обязательно решите для одной из других переменных.

Решение с использованием пересечения трех плоскостей

Из ответа пользователя решение закрытой формы для пересечения трех плоскостей было фактически в Графических драгоценных камнях 1. Формула:

P_intersection = ((point_on1 • n1) (n2 × n3) + (point_on2 • n2) (n3 × n1) + (point_on3 • n3) (n1 × n2)) / det (n1, n2, n3)

Фактически point_on1 • n1 = -d1 (при условии, что вы пишете ваши планы Ax + By + Cz + D = 0, а не = -D). Итак, вы можете переписать его так:

P_intersection = ((-d1) (n2 × n3) + (-d2) (n3 × n1) + (-d3) (n1 × n2)) / det (n1, n2, n3)

Функция, которая пересекает 3 плоскости:

 // Intersection of 3 planes, Graphics Gems 1 pg 305 static Vector3f getIntersection( const Plane& plane1, const Plane& plane2, const Plane& plane3 ) { float det = Matrix3f::det( plane1.normal, plane2.normal, plane3.normal ) ; // If the determinant is 0, that means parallel planes, no intn. if( det == 0.f ) return 0 ; //could return inf or whatever return ( plane2.normal.cross( plane3.normal )*-plane1.d + plane3.normal.cross( plane1.normal )*-plane2.d + plane1.normal.cross( plane2.normal )*-plane3.d ) / det ; } 

Доказательство работы (желтая точка – это пересечение плоскостей rgb)

Получение линии

Когда у вас есть точка пересечения, общая для двух самолетов, линия просто идет

P + t * d

Где P – точка пересечения, t может перейти от (-inf, inf), а d – вектор направления, являющийся перекрестным произведением нормалей двух исходных плоскостей.

Линия пересечения между красными и синими плоскостями выглядит так:

Эффективность и стабильность

«Устойчивый» (2-й способ) принимает 48 элементарных операций по моему счету, по сравнению с 36 элементарными операциями, которые использует 1-й способ (изоляция x, y). Существует обмен между стабильностью и # вычислением между этими двумя способами.

Было бы довольно катастрофично получить (0, inf, inf) обратно от вызова к первому способу в случае, если B ₁ равен 0, и вы не проверяли. Таким образом, добавление операторов if и обеспечение того, чтобы не делиться на 0 на 1-й способ, может дать вам стабильность за счет разбухания кода и добавленное разветвление (что может быть довольно дорого). Метод 3-мерного пересечения почти бесветренный и не даст вам бесконечности.

Этот метод позволяет избежать деления на ноль, если две плоскости не параллельны.

Если это плоскости:

 A1*x + B1*y + C1*z + D1 = 0 A2*x + B2*y + C2*z + D2 = 0 

1) Найдите вектор, параллельный линии пересечения. Это также нормаль третьей плоскости, которая перпендикулярна двум другим плоскостям:

 (A3,B3,C3) = (A1,B1,C1) cross (A2,B2,C2) 

2) Создать систему из трех уравнений. Они описывают 3 плоскости, которые пересекаются в точке:

 A1*x1 + B1*y1 + C1*z1 + D1 = 0 A2*x1 + B2*y1 + C2*z1 + D2 = 0 A3*x1 + B3*y1 + C3*z1 = 0 

3) Решите их, чтобы найти x1, y1, z1. Это точка на линии пересечения.

4) Параметрическими уравнениями линии пересечения являются:

 x = x1 + A3 * t y = y1 + B3 * t z = z1 + C3 * t 

Основанный на детерминантах подход является опрятным, но трудно понять, почему он работает.

Вот еще один способ, более интуитивный.

Идея состоит в том, чтобы сначала перейти от начала координат к ближайшей точке на первой плоскости ( p1 ), а затем оттуда перейти к ближайшей точке линии пересечения двух плоскостей. (Вдоль вектора, который я называю v ниже.)

 Given ===== First plane: n1 • r = k1 Second plane: n2 • r = k2 Working ======= dir = n1 × n2 p1 = (k1 / (n1 • n1)) * n1 v = n1 × dir pt = LineIntersectPlane(line = (p1, v), plane = (n2, k2)) LineIntersectPlane ================== #We have n2 • (p1 + lambda * v) = k2 lambda = (k2 - n2 • p1) / (n2 • v) Return p1 + lambda * v Output ====== Line where two planes intersect: (pt, dir) 

Это должно дать тот же момент, что и подход, основанный на детерминантах. Между ними почти наверняка есть связь. По крайней мере, знаменатель, n2 • v , тот же, если применить правило «скалярное тройное произведение». Таким образом, эти методы, вероятно, схожи, поскольку номера условий идут.

Не забудьте проверить (почти) параллельные плоскости. Например: if (dir • dir < 1e-8) должен хорошо работать, если используются нормальные единицы.

Перекрестное произведение линии – это направление линии пересечения. Теперь вам нужна точка в пересечении.

Вы можете сделать это, взяв точку на кросс-продукте, затем вычитая нормаль плоскости A * расстояния до плоскости A и нормали плоскости B * до плоскости b. Очиститель:

p = точка на поперечном продукте

точка пересечения = ([p] – ([Нормальная плоскость A] * [расстояние от p до плоскости A]) – ([Нормальная плоскость B] * [расстояние от p до плоскости B]))

Редактировать:

У вас есть два самолета с двумя нормалями:

 N1 and N2 

Перекрестное произведение – это направление линии пересечения:

 C = N1 x N2 

У вышеприведенного classа есть функция для вычисления расстояния между точкой и плоскостью. Используйте его, чтобы получить расстояние от точки p на C до обеих плоскостей:

 p = C //p = 1 times C to get a point on C d1 = plane1.getDistance(p) d2 = plane2.getDistance(p) 

Линия пересечения:

 resultPoint1 = (p - (d1 * N1) - (d2 * N2)) resultPoint2 = resultPoint1 + C