Den Schnittpunkt eines Dreiecks und einer Ebene bestimmen

Question

Ich habe ein einzelnes Dreieck und eine Ebene (im 3-dimensionalen Raum), wie würde ich das Liniensegment berechnen, wo sich die beiden kreuzen, wenn es keine Kreuzung gibt, dann muss ich dies erkennen Fall.

Das Endergebnis, nach dem ich suche, sind zwei 3-dimensionale Vektoren, die den Start- und Endpunkt des Liniensegments definieren.

Um Ihnen ein wenig zu helfen, habe ich bereits den Schnittpunkt zwischen der Ebene des Gesichts und der Ebene berechnet, muss ich einfach die Endpunkte finden, um diesen Strahl in ein Liniensegment zu schneiden.

Für diejenigen, die in Codelese Dinge wie:

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

Hier ist ein paar vorgeschlagene Pseudo-Code. Einfache Version zuerst, robustere Version später (nur um das Prinzip von den Neunen zu trennen). Einfache Version:

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

Hinzufügen Jetzt einige Robustheit:
[Edit: Hinzugefügt explizite Berücksichtigung für den Fall eines einzelnen Scheitelpunkt auf der Ebene]

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 
} 

Hoffentlich eine Idee gibt, aber es sind noch einige potenzielle Optimierungen. Wenn Sie beispielsweise diese Schnittpunkte für jedes Dreieck in einem großen Netz berechnen, können Sie DistanceFromPlane einmal pro Vertex berechnen und zwischenspeichern und für jede Kante abrufen, an der der Vertex teilnimmt. Es kann auch ein fortgeschritteneres Caching geben. abhängig von Ihrem Szenario und der Datendarstellung.

Answer 2

es auf ein bisschen abhängig, welche Bibliotheken Sie haben. Ich habe meine eigene Geometriebibliothek erstellt, die den Schnittpunkt einer Linie mit einer Ebene berechnen kann. Berechnen Sie in diesem Fall die drei Schnittpunkte der drei Kanten des Dreiecks und berechnen Sie dann, welche von ihnen zwischen den Eckpunkten liegen. Dies könnte 0 (kein Schnittpunkt) oder 2 sein, was der Fall ist, den Sie möchten. (Es gibt spezielle Fälle, wo die zwei Punkte zusammenfallen - ein Punkt des Dreiecks).

Answer 3

Stecken Sie die 3 Punkte in die Ebenengleichung (definiert durch die vier Parameter a, b, c, d) und legen Sie fest, welche Paare sich auf gegenüberliegenden Seiten der Ebene befinden.

die Ebene Gleichung gegeben:

 
Ax + By + Cz + D = 0 

wobei A, B, C die normale (Einheitslänge) ist und D ist der Abstand zum Ursprung IIRC, steckt sie in den Punkten (x, y, z) und Sehen Sie, ob dieses Ergebnis positiv oder negativ ist. Für Punkte auf der Ebene wird es Null, und das Zeichen sagt Ihnen, auf welcher Seite ein Punkt steht, wenn das Ergebnis nicht 0 ist. Wählen Sie also Paare von Punkten auf gegenüberliegenden Seiten (es gibt höchstens 2) und berechnen Sie den Schnittpunkt von diese 2 Segmente mit dem Flugzeug mit einer Standard-Ray/Plane-Schnittpunktformel, die mir jetzt entgeht. Das sind die 2 Punkte, aus denen das gesuchte Segment besteht.

EDIT Kommen Sie, daran zu denken, die Werte, die Sie verstopfen die Punkte in die Ebene Gleichung erhalten sollten zur Interpolation zwischen Paaren von Punkten nützlich sein, den Schnittpunkt von Segmenten mit dem Flugzeug.

Len Fn = A xn + B yn + C * zn + D ist das Ergebnis des Einsteckens von Punkt n. Angenommen, F1 = -4 und F2 = 8. So sind die Punkte P1 und P2 auf gegenüberliegenden Seiten der Ebene. Wir haben auch P = P1 * 2/3 + P2 * 1/3 ist der Schnittpunkt des Segments von P1 zu P2 mit der Ebene. Das zu einer richtigen Formel zu verallgemeinern, bleibt als Exorzismus übrig.

Answer 4

Suchen Sie den Schnittpunkt jedes Liniensegments, das das Dreieck mit der Ebene begrenzt. identische Punkte fusionieren, dann

• wenn 0 Kreuzungen existieren, gibt es keine Schnitt
ist
• wenn ein Schnittpunkt vorhanden ist (dh gefunden Sie zwei, aber sie waren identisch innerhalb der Toleranz) ein Punkt des Dreiecks haben nur die berühren
Ebene
• wenn 2 Punkte dann das Liniensegment zwischen ihnen ist der Schnittpunkt

nächsten Schritt eine Suche für sO Liniensegment zur Ebene Schnittalgorithmen (oder nur die von Ihrem Rahmen vorgesehen man verwenden), ...