Определение пересечения треугольника и плоскости

Question

У меня есть один треугольник и плоскость (в 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

Answer 1

Вот несколько предложенных псевдокодов. Сначала простая версия, позже более надежная версия (просто для того, чтобы отделить принцип от новых моментов). Простая версия:

// 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);
}

Теперь добавим немного надежности:
[Редактировать: Добавлено явное рассмотрение случая одиночной вершины на плоскости]

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 один раз для каждой вершины и просто извлекать его для каждого ребра, в котором участвует вершина. Также может быть более сложное кэширование в зависимости от вашего сценария и представления данных.

Answer 2

Вставьте 3 точки в уравнение плоскости (определенное 4 параметрами, которые вы перечислили a, b, c, d) и определите, какие пары находятся на противоположных сторонах плоскости.

Учитывая уравнение плоскости:

Ax + By + Cz + D = 0

где A, B, C - нормаль (единичная длина), а D - расстояние до начала координат IIRC, вы подключаете точки (x, y, z) и смотрите, является ли этот результат положительным или отрицательным. Это будет ноль для точек на плоскости, и знак скажет вам, на какой стороне находится точка, если результат не равен 0. Поэтому выберите пары точек на противоположных сторонах (их будет не более 2) и вычислите пересечение эти 2 сегмента с плоскостью, используя стандартную формулу пересечения луча / плоскости, которая ускользает от меня прямо сейчас. Это будут те 2 точки, которые образуют сегмент, который вы ищете.

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

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 с плоскостью. Обобщение этого в правильную формулу оставлено как изгнание.

Answer 3

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

• , если существует 0 пересечений, пересечение не существует
• , если существует 1 пересечение (т.е. вы нашли два, но они были идентичны с точностью до допуска), у вас есть точкатреугольника, просто касающегося плоскости
• , если 2 точки, то отрезок линии между ними является пересечением

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

Answer 4

Это немного зависит от того, какие библиотеки у вас есть.Я создал свою собственную библиотеку геометрии, которая может рассчитать пересечение линии с плоскостью.В этом случае вычислите три точки пересечения трех ребер треугольника, а затем вычислите, какие из них лежат между вершинами.Это может быть 0 (без пересечения) или 2, что вам и нужно.(Существуют особые случаи, когда две точки совпадают - это точка треугольника).