Schnittpunktberechnung: Strahl schneidet Dreieck (bzw. Polygon)

Im heutigen Artikel werden wir darüber sprechen, wie sich der Schnittpunkt eines Strahls mit einem Dreieck (bzw. Polygon) berechnen oder aber frühzeitig ausschließen lässt – ein unverzichtbares mathematisches Verfahren, wenn wir bei einem Treffer- bzw. Kollisionstest die einzelnen Dreiecke des Render- oder Kollisionsmeshes berücksichtigen wollen.

Unsere erste Aufgabe besteht nun darin, für jedes Mesh-Dreieck die Ebene zu konstruieren, in der das betreffende Dreieck eingebettet ist. Die Konstruktion besagter Ebenen erfolgt sinnvollerweise im Zuge der Initialisierung des 3D-Modells.

Die eigentliche Schnittpunktberechnung verläuft dann in zwei Teilschritten. Im ersten Schritt wird falls möglich ein Schnittpunkt mit der Dreiecks-Ebene berechnet. Sofern diese Berechnung erfolgreich ist, wird anschließend überprüft, ob der Schnittpunkt innerhalb oder außerhalb des Dreiecks liegt.

Anhand der nachfolgenden Abbildung sollte sich die Konstruktion einer Dreiecks-Ebene aus den Eckpunkten (Vertices) eines Dreiecks ohne Schwierigkeiten nachvollziehen lassen:

Die eigentliche Implementierung ist denkbar einfach:

// Initialisierungsarbeiten:

D3DXVECTOR3 normal;

. . .

// Spannvektoren (Dreieckskanten) berechnen:
D3DXVECTOR3 DiffVektor1 = Vertex_3 - Vertex_1;
D3DXVECTOR3 DiffVektor2 = Vertex_2 - Vertex_1;

// Flächennormale des Dreiecks berechnen:
D3DXVec3Cross(&normal, &DiffVektor2, &DiffVektor1);
D3DXVec3Normalize(&normal, &normal);

Der Halbseitentest

Im Artikel „Strahl schneidet Ebene“ haben wir darüber besprochen, wie sich der Schnittpunkt eines Strahls mit einer Ebene berechnen lässt. Ein erfolgreicher Schnittpunkttest sagt jedoch noch nichts darüber aus, ob der Schnittpunkt auch innerhalb des in der Ebene eingebetteten

Dreiecks liegt oder aber sich außerhalb befindet.

Eine Methode, um das festzustellen, ist der sogenannte Halbseitentest. Bei diesem Test wird überprüft, auf welcher Seite einer Dreieckskante sich der Schnittpunkt befindet.

Der Schnittpunkt liegt immer dann innerhalb des Dreiecks, sofern sich dieser auf den Innenseiten aller Dreieckskanten befindet.

Hinweis

Mathematiker bezeichnet sowohl die Innen- als auch die Außenseite als eine Halbseite – daher auch der Name dieses Tests.

Dieser Test lässt sich bei allen zweidimensionalen konvexen Polygonen anwenden. Konvex bedeutet, dass die Innenwinkel aller benachbarten Kanten <180° sein müssen. Andernfalls spricht man von einem konkaven Polygon.

Notwendig für die Durchführung eines Halbseitentests sind die sogenannten (Dreiecks)-Senkrechten, Vektoren, die sowohl senkrecht zur Dreiecks-Normale als auch senkrecht zu einer der Dreieckskanten orientiert sind:

// Initialisierungsarbeiten:

D3DXVECTOR3 normal;
D3DXVECTOR3 Senkrechte21;
D3DXVECTOR3 Senkrechte32;
D3DXVECTOR3 Senkrechte13;

. . .


// Spannvektoren (Dreieckskanten):
D3DXVECTOR3 DiffVektor2 = Vertex_2 - Vertex_1;
D3DXVECTOR3 DiffVektor1 = Vertex_3 - Vertex_1;

// Flächennormale des Dreiecks berechnen:
D3DXVec3Cross(&normal, &DiffVektor2, &DiffVektor1);
D3DXVec3Normalize(&normal, &normal);

// Dreiecksenkrechten berechnen:
D3DXVec3Cross(&Senkrechte21, &DiffVektor2, &normal);

DiffVektor2 = Vertex_3 - Vertex_2;
D3DXVec3Cross(&Senkrechte32, &DiffVektor2, &normal);

DiffVektor2 = Vertex_1 - Vertex_3;
D3DXVec3Cross(&Senkrechte13, &DiffVektor2, &normal);

Der eigentliche Testablauf lässt sich anhand einer Abbildung wohl am leichtesten nachvollziehen:

Kommen wir nun zur praktischen Implementierung des Tests. Beachten Sie in diesem Zusammenhang den Ausschluss-Charakter des Halbseitentests. Sobald eine der Testbedingungen nicht erfüllt ist (eines der Skalarprodukte ist größer null), kann der Test vorzeitig abgebrochen werden. Selbst wenn alle weiteren Skalarprodukte kleiner null sind, ändert das nichts am Resultat – es ist ausgeschlossen, dass sich der Schnittpunkt innerhalb des Dreiecks befindet.

bool Test_for_Ray_Intersection(D3DXVECTOR3* pRayStartPosition,
                               D3DXVECTOR3* pRayDirection,
                               D3DXVECTOR3* pTriangleNormal,
                               D3DXVECTOR3* pTriangleVertex1,
                               D3DXVECTOR3* pTriangleVertex2,
                               D3DXVECTOR3* pTriangleVertex3,
                               /*Dreiecks-Senkrechten:*/
                               D3DXVECTOR3* pPerpendicular21,
                               D3DXVECTOR3* pPerpendicular32,
                               D3DXVECTOR3* pPerpendicular13,
                               float* pIntersectionParameter,
                               D3DXVECTOR3* pIntersectionPoint)
{
    // Wenn Ebene und Strahlrichtung parallel verlaufen
    // (bzw. wenn Strahl und Flächennormale einen rechten Winkel bilden),
    // dann ist kein Schnitt möglich, sofern die Strahl-Ausgangsposition
    // nicht schon innerhalb der Ebene liegt.
    // Bei einem Skalarprodukt > 0 bewegt sich der Strahl
    // von der Ebene weg, und es ist ebenfalls kein Schnitt möglich:
    float tempDot = D3DXVec3Dot(pTriangleNormal, pRayDirection);

    if(tempDot >= 0.0f)
        return false;

    // Berechnung des Schnittpunkts mit der Ebene:
    D3DXVECTOR3 helpVektor = *pRayStartPosition - *pTriangleVertex1;

    float intersection_parameter = -D3DXVec3Dot(pTriangleNormal,
                                                &helpVektor)/tempDot;

    D3DXVECTOR3 IntersectionPoint = *pRayStartPosition +
                intersection_parameter * (*pRayDirection);

    // Halbseitentest:

    D3DXVECTOR3 TempDiffVektor1 = IntersectionPoint - *pTriangleVertex1;

    if(D3DXVec3Dot(&TempDiffVektor1, pPerpendicular21) > 0.01f)
        return false;

    TempDiffVektor1 = IntersectionPoint - *pTriangleVertex2;

    if(D3DXVec3Dot(&TempDiffVektor1, pPerpendicular32) > 0.01f)
        return false;

    TempDiffVektor1 = IntersectionPoint - *pTriangleVertex3;

    if(D3DXVec3Dot(&TempDiffVektor1, pPerpendicular13) > 0.01f)
        return false;

    *pIntersectionPoint     = IntersectionPoint;
    *pIntersectionParameter = intersection_parameter;

    return true;
}

Hinweis:

Der hier vorgestellte Schnittpunkttest lässt sich ohne große Schwierigkeiten verallgemeinern und für konvexe Polygone mit einer beliebigen Anzahl von Kanten (Edges) verwenden:

bool Test_for_Ray_Intersection(D3DXVECTOR3* pRayStartPosition,
                               D3DXVECTOR3* pRayDirection,
                               D3DXVECTOR3* pPolygonNormal,
                               long NumPolygonEdges,
                               D3DXVECTOR3* pPolygonVertexList,
                               D3DXVECTOR3* pPerpendicularList,
                               float* pIntersectionParameter,
                               D3DXVECTOR3* pIntersectionPoint)
{

    . . .

    // Berechnung des Schnittpunkts mit der Ebene:
    D3DXVECTOR3 helpVektor = *pRayStartPosition - pPolygonVertexList[0];

    . . .

    // Halbseitentest für beliebige konvexe Polygone:

    D3DXVECTOR3 TempDiffVektor1;

    for(long i = 0; i < NumPolygonEdges; i++)
    {
    TempDiffVektor1 = IntersectionPoint – pPolygonVertexList[i];

    if(D3DXVec3Dot(&TempDiffVektor1, &pPerpendicularList[i]) > 0.01f)
        return false;
    }

    . . .
}