Пересечение двух прямоугольников в 3D

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

Проблема заключается в том, что линия параллельна трем сегментам и пересекается только с одним в NAN, NAN, NAN, что совершенно неверно. Можете ли вы сообщить мне, что неправильно в моем коде?

и создал мой класс плоскости следующим образом

и это тестовые значения С наилучшими пожеланиями

Ответы

Ответ 1

Сначала нужно указать одну вещь:

3D-прямоугольником, вы имеете в виду прямоугольник прямоугольника на трехмерной плоскости. (а не прямоугольная призма).

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

Учитывая это предположение, их четыре возможные ситуации для пересечения двух прямоугольников R1 и R2:

(примечание: иногда D1 не пересекается ни с R1, ни с R2, а R1, R2 может немного вращаться, так что D1 не всегда пересекается на параллельных сторонах, но с последовательными сторонами)

Когда есть пересечение между двумя прямоугольниками, D1 всегда пересекает R1 и R2 на одном и том же пересечении (cf 1st и 2nd picture)

Ваша модель не хороша, потому что ваша линия не может быть параллельна 3 сегментам одного и того же прямоугольника...

Как вы задали в этом вопросе: алгоритм пересечения 3D-линий, когда у вас есть D1 (Получить конечные точки определенного сегмента линии через пересечение двух прямоугольников) просто определит пересечение с каждым сегментом прямоугольника. (Необходимо проверить 4 сегмента каждого прямоугольника)

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

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

Надеюсь, что это поможет.

EDIT:

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

R2 {A ,u ,v}
R1 {B, u',v'}

определяют плоскости, обозначенные R1 и R2: P1 и P2

Один ортогональный вектор для P1 (соответственно P2) равен n1 (соответственно n2).Let n1 = u ^ v и n2 = u' ^ v 'с:

затем

P1: n1.(x-xA,y-yA,z-zA)=0
P2: n2.(x-xB,y-yB,z-zB)=0

Тогда, если вы просто ищете D1, уравнение D1:

D1: P1^2 + P2 ^2 =0 (x,y,z verify P1 =0  an P2 =0 )

D1 : n1.(x-xA,y-yA,z-zA)^2 + n2.(x-xB,y-yB,z-zB)^2 =0

(так что просто с выражением ваших прямоугольников вы можете получить уравнение D1 с закрытой формулой.)

Теперь посмотрим на пересечения:

4 точки в R1:

{A, A + u, A + v, A + u + v}

как описывается в алгоритме пересечения 3D-линий:

D1 inter [A,A+u] = I1
D1 inter [A,A+v] = I2
D1 inter [A+u,A+u+v] = I3
D1 inter [A+v,A+u+v] = I4

(I1, I2, I3, I4 может быть нулевым)

same for D2 you get I1' I2' I3' I4'

, если Ij '= Ik'!= null, то это точка пересечения

Если вы сделали это правильно шаг за шагом, вы должны перейти к правильному решению; если я не полностью понял вопрос...

Ответ 2

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

Пропустите код и найдите вещи, которые могут быть неправильными.

Программа вычисляет линию, проходящую через две плоскости, как это:

Vector3 LineDirection = Normal.Cross(SecondOne.Normal);

float d1 = this.GetDistance(LineDirection);
float d2 = SecondOne.GetDistance(LineDirection);

temp = (LineDirection - (this.Normal * d1) - (SecondOne.Normal * d2));

temp.x = Math.Abs((float)Math.Round((decimal)FirstPoint.x, 2));
temp.y = Math.Abs((float)Math.Round((decimal)FirstPoint.y, 2));

Line line;
line.direction = LineDirection;
line.point = temp;

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

Программа вызывает AreLinesParallel(), чтобы избавиться от ребер, параллельных линии через плоскости. Код выглядит следующим образом:

Vector3 vector = (first.secondPoint - first.firstPoint);
vector.Normalize();

float kl = 0, km = 0, kn = 0;
if (vector.x != aSecondLine.direction.x)
{
    if (vector.x != 0 && aSecondLine.direction.x != 0)
    {
        kl = vector.x / aSecondLine.direction.x;
    }
}
if (vector.y != aSecondLine.direction.y)
{
    if (vector.y != 0 && aSecondLine.direction.y != 0)
    {
        km = vector.y / aSecondLine.direction.y;
    }
}
if (vector.z != aSecondLine.direction.z)
{
    if (vector.z != 0 && aSecondLine.direction.z != 0)
    {
        kn = vector.z / aSecondLine.direction.z;
    }
}

// both if all are null or all are equal, the lines are parallel
return ((kl == km && km == kn));

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

Теперь идет мясо кода, проверка пересечения между краем и строкой:

float d = 0, dt = 0, dk = 0;
float t = 0, k = 0;

if (Math.Abs(n1.x * n2.y - n2.x * n1.y) > float.Epsilon)
{
    d = n1.x * (-n2.y) - (-n2.x) * n1.y;
    dt = (p2.x - p1.x) * (-n2.y) - (p2.y - p1.y) * (-n2.x);
    dk = n1.x * (p2.x - p1.x) - n1.y * (p2.y - p1.y);
}
else if (Math.Abs(n1.z * n2.y - n2.z * n1.y) > float.Epsilon)
{
    d = n1.z * (-n2.y) - (-n2.z) * n1.y;
    dt = (p2.z - p1.z) * (-n2.y) - (p2.y - p1.y) * (-n2.z);
    dk = n1.z * (p2.z - p1.z) - n1.y * (p2.y - p1.y);
}
else if (Math.Abs(n1.x * n2.z - n2.x * n1.z) > float.Epsilon)
{
    d = n1.x * (-n2.z) - (-n2.x) * n1.z;
    dt = (p2.x - p1.x) * (-n2.z) - (p2.z - p1.z) * (-n2.x);
    dk = n1.x * (p2.x - p1.x) - n1.z * (p2.z - p1.z);
}

t = dt / d;
k = dk / d;

result = n1 * t + p1;

Ошибка этого кода - отсутствие комментария, объясняющего происхождение алгоритма. Если для ссылки нет документального алгоритма, комментарий может содержать вывод, приводящий к формулам. Первая ветвь относится к (x, y), вторая - к (y, z), а третья - к (z, x), поэтому я предполагаю, что ветки решают для пересечения в 2D и поднимают эти результаты в 3D. Он вычисляет детерминанты для проверки параллельных линий для каждой двумерной проекции. Мне не нужно было делать такую обратную инженерию.

В любом случае, это код, который генерирует значения NaN. Ни одна из трех ветвей не запускается, поэтому d = 0 в конце, что дает деление на ноль. Вместо того чтобы полагаться на AreLinesParallel(), чтобы избежать деления на ноль, лучше проверить значение, которое действительно имеет значение, а именно d.

Конечно, код по-прежнему нуждается в дополнительной работе, потому что мы еще не знаем, пересекаются ли строки в 3D. Также точка находится на краю, только если 0 <= t && t <= 1. И, вероятно, больше ошибок будет отображаться, поскольку ранние исправляются.