language agnostic - triangulo - Determinar la intersección de un triángulo y un plano

hallar las ecuaciones de las medianas y las coordenadas de su punto de interseccion

Question

Tengo un solo triángulo y un plano (en el espacio tridimensional). ¿Cómo calculo el segmento de línea donde se cruzan los dos? Si no hay un cruce, necesito detectar este caso.

El resultado final que estoy buscando es dos vectores tridimensionales, que definen los puntos de inicio y final del segmento de línea.

Para ayudarlo un poco, ya he calculado el rayo de intersección entre el plano de la cara y el plano, simplemente necesito encontrar los puntos finales para recortar ese rayo en un segmento de línea.

Para los que les gusta leer cosas en código:

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

Aquí hay algunos pseudo código sugerido. Versión simple primero, versión más robusta después (solo para ayudar a separar el principio de los nuevos). Versión simple:

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

Ahora añadiendo algo de robustez:
[Editar: Se agregó una consideración explícita para el caso de un solo vértice en el plano]

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 
}

Con suerte eso da una idea, pero todavía hay bastantes optimizaciones potenciales. Si, por ejemplo, está calculando estas intersecciones para cada triángulo en una malla grande, puede calcular y almacenar en caché el Plano de Distancia una vez por vértice, y simplemente recuperarlo por cada borde en el que participa el vértice. También puede haber un almacenamiento en caché más avanzado. Dependiendo de su escenario y representación de datos.

Answer 2

Conecte los 3 puntos en la ecuación del plano (definidos por los 4 parámetros que enumeró a, b, c, d) y determine qué pares están en los lados opuestos del plano.

Dada la ecuación plana:

Ax + By + Cz + D = 0

donde A, B, C es la normal (longitud de la unidad) y D es la distancia al origen IIRC, usted conecta los puntos (x, y, z) y ve si este resultado es positivo o negativo. Será cero para los puntos en el plano, y el signo le dirá en qué lado está un punto cuando el resultado no es 0. Por lo tanto, elija pares de puntos en los lados opuestos (habrá como máximo 2) y calcule la intersección de esos 2 segmentos con el plano usando una fórmula de intersección de rayo / plano estándar que se me escapa ahora mismo. Esos serán los 2 puntos que forman el segmento que buscas.

EDITAR Ahora que lo pienso, los valores que obtiene al insertar los puntos en la ecuación del plano deberían ser útiles para interpolar entre pares de puntos para obtener la intersección de segmentos con el plano.

Len Fn = A xn + B yn + C * zn + D puede ser el resultado de enchufar el punto n. Luego, suponga que F1 = -4 y F2 = 8. Así que los puntos P1 y P2 están en lados opuestos del plano. También tendremos P = P1 * 2/3 + P2 * 1/3 es el punto de intersección del segmento de P1 a P2 con el plano. Generalizar esto en una fórmula adecuada se deja como un exorcismo.

Answer 3

Depende un poco de qué librerías tengas. He creado mi propia biblioteca de geometría que puede calcular la intersección de una línea con un plano. En este caso, calcule los tres puntos de intersección de los tres bordes del triángulo y luego calcule cuál de ellos se encuentra entre los vértices. Esto podría ser 0 (sin intersección), o 2, que es el caso que desea. (Hay casos especiales en los que los dos puntos son coincidentes: un punto del triángulo).

Answer 4

Encuentra la intersección de cada segmento de línea que delimita el triángulo con el plano. Fusionar puntos idénticos, entonces

• Si existen 0 intersecciones, no hay intersección
• Si existe una intersección (es decir, si encontró dos pero eran idénticas a la tolerancia), tiene un punto del triángulo que toca el plano.
• si 2 puntos, entonces el segmento de línea entre ellos es la intersección

En el siguiente paso, busque SO para los algoritmos de intersección línea a plano (o simplemente use el que le proporciona su marco) ...