Określanie punktu przecięcia trójkąta i płaszczyzny

Question

Mam pojedynczy trójkąt i płaszczyznę (w przestrzeni trójwymiarowej), Jak obliczyć odcinek linii, gdzie dwa krzyże, jeśli nie ma przecinania, muszę to wykryć walizka.

Końcowy wynik, którego szukam, to dwa trójwymiarowe wektory, które definiują punkt początkowy i końcowy odcinka linii.

Aby pomóc Ci trochę, już obliczyłem promień skrzyżowania między płaszczyzną twarzy, a płaszczyzną, po prostu muszę znaleźć punkty końcowe, aby przyciąć ten promień do segmentu linii.

Dla tych, którzy lubią czytanie rzeczy w kodzie:

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

Oto kilka sugerowanych pseudo kodu. Najpierw prosta wersja, bardziej rozbudowana wersja później (aby pomóc oddzielić zasadę od niuansów). Prosta wersja:

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

Teraz dodając trochę solidności:
[Edycja: Dodano wyraźne uwzględnienie w przypadku jednego wierzchołka na płaszczyźnie]

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 
} 

miejmy nadzieję, że daje wyobrażenie, ale nie wciąż jest kilka potencjalnych optymalizacji. Jeśli, na przykład, obliczasz te przecięcia dla każdego trójkąta w dużej siatce, możesz obliczyć i buforować DistanceFromPlane raz na jeden wierzchołek, i po prostu pobrać go dla każdej krawędzi, w której uczestniczy dany wierzchołek. Może być też bardziej zaawansowane buforowanie, w zależności od scenariusza i reprezentacji danych.

Answer 2

To zależy trochę od tego, co masz biblioteki. Stworzyłem własną bibliotekę geometrii, która może obliczyć przecięcie linii z płaszczyzną. W tym przypadku obliczyć trzy punkty przecięcia trzech krawędzi trójkąta, a następnie obliczyć, które z nich znajdują się między wierzchołkami. Może to być 0 (brak przecięcia) lub 2, w zależności od potrzeb. (Istnieją szczególne przypadki, w których dwa punkty są zbieżne - punkt trójkąta).

Answer 3

Podłącz 3 punkty do równania płaszczyzny (zdefiniowanego przez 4 parametry, które wymieniono a, b, c, d) i określ, które pary znajdują się po przeciwnych stronach płaszczyzny.

względu na równanie płaszczyzna:

 
Ax + By + Cz + D = 0 

, w którym A, B, C jest normalnym (długość jednostki), a D oznacza odległość od pochodzenia IIRC, podłączeniu punktów (x, y, z) zobacz, czy wynik jest pozytywny czy negatywny. Będzie to zero dla punktów na płaszczyźnie, a znak wskaże, po której stronie znajduje się punkt, gdy wynik nie jest równy 0. Wybierz pary punktów po przeciwnych stronach (nie więcej niż 2) i oblicz punkt przecięcia te 2 segmenty z płaszczyzną przy użyciu standardowej formuły przecięcia promienia/płaszczyzny, która teraz mi ucieka. Będą to 2 punkty, które tworzą segment, którego szukasz.

EDIT Przyjdź, aby myśleć o tym, wartości można uzyskać z podłączeniem punktów do równania płaszczyzny powinny być użyteczne dla interpolację między parami punktów, aby dostać się do skrzyżowania z segmentów z samolotu.

Len Fn = A xn + B yn + C * zn + D być wynikiem podłączania punktu n. Załóżmy, że F1 = -4 i F2 = 8. Tak więc punkty P1 i P2 znajdują się po przeciwnych stronach płaszczyzny. Będziemy mieć również P = P1 * 2/3 + P2 * 1/3 jest punktem przecięcia segmentu od P1 do P2 z płaszczyzną. Uogólnienie tego na odpowiednią formułę jest pozostawione jako egzorcyzm.

Answer 4

Znaleźć przecięcie każdego odcinka linii ograniczającego trójkąt z płaszczyzną. Scalanie identyczne punkty, a następnie

• jeśli istnieją 0 skrzyżowań, nie ma przecięcia
• jeśli 1 przecięcie istnieje (tzn znaleźliście dwa, ale były one identyczne w granicach tolerancji) masz punkt trójkąta prostu dotykając samolot
• czy 2 punkty to odcinek między nimi polega na przecięciu

następny krok, szukaj więc dla odcinka linii do algorytmów płaszczyzna przecięcia (lub po prostu użyć jednego dostarczony przez ramowa) ...