Determinación de la intersección de un triángulo y un plano

Question

Tengo un solo triángulo y un plano (en espacio tridimensional), ¿cómo puedo calcular el segmento de línea donde los dos cruzan, si no hay cruce entonces necesito detectar esto caso.

El resultado final que estoy buscando es dos vectores tridimensionales, que definen los puntos de inicio y fin 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 acoplar ese rayo en un segmento de línea.

Para aquellos 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 pseudocódigos sugeridos. Primero, versión simple, versión más robusta después (solo para ayudar a separar el principio de las discrepancias). Versión sencilla:

// 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 un poco de solidez:
[Editar: Se ha añadido 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 
} 

Esperemos que da una idea, pero hay todavía hay bastantes optimizaciones potenciales. Si, por ejemplo, está calculando estas intersecciones para cada triángulo en una malla grande, puede calcular y guardar en caché la DistanceFromPlane una vez por vértice, y solo recuperarla para cada borde en el que participe el vértice. También puede haber más caché avanzado, dependiendo de su escenario y representación de datos.

Answer 2

Depende un poco en lo que las bibliotecas que tiene. Creé 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 donde los dos puntos son coincidentes, un punto del triángulo).

Answer 3

Enchufa los 3 puntos en la ecuación del plano (definida por los 4 parámetros enumerados a, b, c, d) y determina qué pares están en lados opuestos del plano.

Dada la ecuación avión:

 
Ax + By + Cz + D = 0 

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

EDITAR Ahora que lo pienso de ella, los valores que obtiene de tapar los puntos en la ecuación de avión deben ser útiles para interpolar entre los pares de puntos para obtener la intersección de los segmentos con el avión.

Len Fn = A xn + B yn + C * zn + D ser el resultado de conectar el punto n. Supongamos F1 = -4 y F2 = 8. Por lo tanto, 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 avión. Generalizar esto en una fórmula adecuada se deja como un ejercicio.

Answer 4

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

• si existen 0 intersecciones, no hay intersección
• si existe 1 intersección (es decir, se encontraron dos pero eran idénticas a dentro de la tolerancia) que tiene un punto del triángulo sólo tocar la
avión
• si 2 puntos, entonces el segmento de línea entre ellos es la intersección

siguiente paso, la búsqueda así para la línea del segmento de algoritmos de intersección plano (o simplemente utilizar el proporcionado por el marco) ...