Определение пересечения треугольника и плоскости
У меня есть единственный треугольник и плоскость (в 3 размерных пространствах), Как я вычислил бы линейный сегмент где эти два креста, если нет никакого пересечения затем, я должен обнаружить этот случай.
Конечный результат, который я ищу, равняется двум 3 размерных вектора, которые определяют запуск и конечные точки линейного сегмента.
Для выручения Вас немного я уже вычислил перекрестный луч между плоскостью поверхности и плоскостью, я просто должен найти, что конечные точки отсекают тот луч в линейный сегмент.
Для тех, кому нравится читать вещи в коде:
Face face; //a face, defined by 3 points
Plane plane; //a plane, defined by a normal vector and a distance
Ray intersection; //a ray, defined by a point and a direction, initialised to the intersection of the face plane and the face
Segment s = CalculateSegment(face, plane, intersection); //this method needs defining
4 ответа
Вот некоторый предложенный псевдокод. Сначала простая версия, потом более надежная (просто чтобы отделить принцип от неочевидностей). Простая версия:
// Assume the plane is given as the equation dot(N,X) + d = 0, where N is a (not
// neccessarily normalized) plane normal, and d is a scalar. Any way the plane is given -
// DistFromPlane should just let the input vector into the plane equation.
vector3d planeN;
float planeD;
float DistFromPlane( vector3d P)
{
// if N is not normalized this is *not* really the distance,
// but the computations work just the same.
return dot(planeN,P) + planeD;
}
bool GetSegmentPlaneIntersection( vector3d P1, vector3d P2, vector3d& outP)
{
float d1 = DistFromPlane(P1),
d2 = DistFromPlane(P2);
if (d1*d2 > 0) // points on the same side of plane
return false;
float t = d1 / (d1 - d2); // 'time' of intersection point on the segment
outP = P1 + t * (P2 - P1);
return true;
}
void TrianglePlaneIntersection(vector3d triA, vector3d triB, vector3d triC,
vector3dArray& outSegTips)
{
vector3d IntersectionPoint;
if( GetSegmentPlaneIntersection( triA, triB, IntersectionPoint))
outSegTips.Add(IntersectionPoint);
if( GetSegmentPlaneIntersection( triB, triC, IntersectionPoint))
outSegTips.Add(IntersectionPoint);
if( GetSegmentPlaneIntersection( triC, triA, IntersectionPoint))
outSegTips.Add(IntersectionPoint);
}
Теперь добавим некоторую робастность:
[Edit: Added explicit consideration for the case of a single vertex on the plane]
vector3d planeN;
float planeD;
float DistFromPlane( vector3d P)
{
return dot(planeN,P) + planeD;
}
void GetSegmentPlaneIntersection( vector3d P1, vector3d P2, vector3dArray& outSegTips)
{
float d1 = DistFromPlane(P1),
d2 = DistFromPlane(P2);
bool bP1OnPlane = (abs(d1) < eps),
bP2OnPlane = (abs(d2) < eps);
if (bP1OnPlane)
outSegTips.Add(P1);
if (bP2OnPlane)
outSegTips.Add(P2);
if (bP1OnPlane && bP2OnPlane)
return;
if (d1*d2 > eps) // points on the same side of plane
return;
float t = d1 / (d1 - d2); // 'time' of intersection point on the segment
outSegTips.Add( P1 + t * (P2 - P1) );
}
void TrianglePlaneIntersection(vector3d triA, vector3d triB, vector3d triC,
vector3dArray& outSegTips)
{
GetSegmentPlaneIntersection( triA, triB, outSegTips));
GetSegmentPlaneIntersection( triB, triC, outSegTips));
GetSegmentPlaneIntersection( triC, triA, outSegTips));
RemoveDuplicates(outSegTips); // not listed here - obvious functionality
}
Надеюсь, это дает представление, но есть еще довольно много потенциальных оптимизаций. Если, например, вы вычисляете эти пересечения для каждого треугольника в большой сетке, вы можете вычислять и кэшировать DistanceFromPlane один раз для каждой вершины, и просто извлекать его для каждого ребра, в котором участвует вершина. Может быть и более продвинутое кэширование, в зависимости от вашего сценария и представления данных.
Найдите пересечение каждого отрезка прямой, ограничивающего треугольник с плоскостью. Объедините идентичные точки, затем
- , если существует 0 пересечений, пересечения нет
- если существует 1 пересечение (т. Е. Вы нашли два, но они были идентичны в пределах допуска), у вас есть точка треугольника, только касающаяся плоскости
- если 2 точки, то отрезок прямой между ними является пересечением
следующий шаг, ищите SO алгоритмы пересечения отрезка и плоскости (или просто используйте тот, который предоставлен вашей структурой) ...
Это немного зависит от того, какие библиотеки у вас есть. Я создал свою собственную библиотеку геометрии, которая может вычислять пересечение линии с плоскостью. В этом случае вычислите три точки пересечения трех ребер треугольника, а затем вычислите, какие из них лежат между вершинами. Это может быть 0 (без пересечения) или 2, что вам нужно. (Есть особые случаи, когда две точки совпадают - точка треугольника).
Вставьте 3 точки в уравнение плоскости (определяемое четырьмя перечисленными вами параметрами a, b, c, d) и определите, какие пары находятся на противоположных сторонах плоскости.
Учитывая уравнение плоскости:
Ax + By + Cz + D = 0
где A, B, C - нормаль (единичная длина), а D - расстояние до начала координат IIRC, вы вставляете точки (x, y, z) и смотрите, будет ли этот результат положительным или отрицательным. Для точек на плоскости он будет равен нулю, и знак укажет вам, с какой стороны находится точка, если результат не равен 0. Поэтому выберите пары точек на противоположных сторонах (их будет не более 2) и вычислите пересечение те 2 сегмента с плоскостью, использующие стандартную формулу пересечения луча / плоскости, которая сейчас ускользает от меня. Это будут 2 точки, которые образуют искомый сегмент.
ИЗМЕНИТЬ Если подумать, значения, которые вы получаете от вставки точек в уравнение плоскости, должны быть полезны для интерполяции между парами точек, чтобы получить пересечение сегментов с плоскостью.
Len Fn = A xn + B yn + C * zn + D быть результатом подключения точки n. Тогда предположим, что F1 = -4 и F2 = 8. Значит, точки P1 и P2 находятся на противоположных сторонах плоскости. У нас также будет P = P1 * 2/3 + P2 * 1/3 - точка пересечения отрезка от P1 до P2 с плоскостью. Обобщение этого в правильную формулу остается как изгнание нечистой силы.