Линия пересечения двух плоскостей

Как найти линию пересечения между двумя плоскостями?

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

но как программно получить линию из приведенного вектора

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

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


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

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 1 y + C 1 z + D 1 = 0

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

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

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

-B 2 y + (-B 2 / B 1 ) * C 1 z + (-B 2 / B 1 ) * D 1 = 0

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

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

z = ((-B 2 / B 1 ) * D 1 – D 2 ) / (C 2 * B 2 / B 1 ) * C 1 )

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

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

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

Вышеупомянутое решение все еще может быть испорчено, если B 1 = 0 (что не так маловероятно). Вы можете добавить в некоторые операторы if, которые проверяют, если B 1 = 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 1 равен 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 
  • Как измерить сходство между двумя изображениями?
  • Сгенерировать список всех возможных перестановок строки
  • Что такое композиция, относящаяся к объектно-ориентированному дизайну?
  • Уравнение для тестирования, если точка находится внутри круга
  • Как найти пару с k-й наибольшей суммой?
  • Как работает переопределение переменных XOR?
  • Для чего нужен пузырь?
  • Что такое самоуверенное программное обеспечение?
  • Алгоритм естественной сортировки
  • Вычислить наибольший прямоугольник во вращающемся прямоугольнике
  • Является ли двойным действительно неподходящим для денег?
  • Давайте будем гением компьютера.