Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Probleme mit Rekursion in Kollisionsabfrage

Werbeanzeige

Jens

Treue Seele

  • »Jens« ist der Autor dieses Themas

Beiträge: 117

Wohnort: Dresden

  • Private Nachricht senden

1

13.08.2003, 20:09

Probleme mit Rekursion in Kollisionsabfrage

bloß gut, dass hier jemand ordentlich Code gepostet hat.
Dann kann ich ja auch mal, vielleicht sieht ja sofort jemand einen Drehrumbum.

Seit ich ne kleine Änderung in den Abfragen, ob sich eine Linie in der Box befindet oder ne Linie usw. spinnt die Rekursion. Wenn ein Körper durch den anderen läuft, wird keine ordentliche Kollision mehr erkannt und vor allem, ich habe das Gefühl, hier verrennt sich die Logik:

Das C3DModel ist ähnlich wie in der Tribase, Othermodell ist wohl klar...

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

BOOL C3DModel::IntersectModel(const C3DModel* pOtherModel, 
                              const COcTreeNode* pNode,
                              const COcTreeNode* pOtherNode,
                              D3DXVECTOR3* pvOutPos,
                              D3DXVECTOR3* pvOutNormalA,
                              D3DXVECTOR3* pvOutNormalB,
                              int* piOutTriA,
                              int* piOutTriB) const
{
    if (pNode && pOtherNode)
    {
        // locale Boundingboxen beider Modelle transformieren
        D3DXMATRIXA16 mat1 = m_mat * (*pOtherModel->GetMatrixInv());
        D3DXMATRIXA16 mat2 = (*pOtherModel->GetMatrix()) * m_matInv;
        // ist die BBox des anderen Knotens im aktuellen Knoten enthalten
        if (pNode->Intersect(pOtherNode, &mat1) ||
            // oder ist die aktuelle BBox des Knotens im anderen Knoten enthalten
            pOtherNode->Intersect(pNode, &mat2))
        {
            // hat der aktuelle Knoten weitere Unterknoten, dann hineingehen
            if (pNode->HasChilds())
            {
                // Unterknoten durchgehen
                for (DWORD ix = 0; ix < 8; ix++)
                {
                    // rekursives Aufrufen der Unterknoten
                    if (IntersectModel(pOtherModel, pNode->GetChild(ix), pOtherNode,
                            pvOutPos, pvOutNormalA, pvOutNormalB, piOutTriA, piOutTriB))
                        return TRUE;
                }
            }
            // hat der andere Knoten weitere Unterknoten, dann hineingehen
            else if (pOtherNode->HasChilds())
            {
                // Unterknoten durchgehen
                for (DWORD ix = 0; ix < 8; ix++)
                {
                    // rekursives Aufrufen der Unterknoten
                    if (IntersectModel(pOtherModel, pNode, pOtherNode->GetChild(ix),
                            pvOutPos, pvOutNormalA, pvOutNormalB, piOutTriA, piOutTriB))
                        return TRUE;
                }
            }
            // beide Knoten sind Endknoten
            else
            {
                // welcher Knoten hat mehr Dreiecke
                if (pNode->GetTriangleCount() > pOtherNode->GetTriangleCount())
                    // wenn der Knoten des aktuellen Modells mehr Dreiecke hat, das andere transformieren
                    return pOtherModel->IntersectModel(this,
                        pOtherNode, pNode, pvOutPos, 
                        pvOutNormalB, pvOutNormalA, piOutTriB, piOutTriA);

                D3DXVECTOR3 vHitStart, vHitEnd;
                // Dreiecke des anderen Knotens durchgehen
                for (DWORD ixB = 0; ixB < pOtherNode->GetTriangleCount(); ixB++)
                {
                    // sind Dreiecke angelegt worden
                    assert(pOtherModel->m_pTriangles != NULL);
                    // ist der Index im Gültigkeitsbereich
                    assert(pOtherNode->GetTriangleNum(ixB) >= 0 && pOtherNode->GetTriangleNum(ixB) < pOtherModel->m_dwNumFaces * 3);
                    CTriangle TriangleB = pOtherModel->m_pTriangles[pOtherNode->GetTriangleNum(ixB)];
                    TriangleB.Transform(&mat2);
                    // Dreiecke des aktuellen Knotens durchgehen
                    for (DWORD ixA = 0; ixA < pNode->GetTriangleCount(); ixA++)
                    {
                        // sind Dreiecke angelegt worden
                        assert(m_pTriangles != NULL);
                        // ist der Index im Gültigkeitsbereich
                        assert(pNode->GetTriangleNum(ixA) >= 0 && pNode->GetTriangleNum(ixA) < m_dwNumFaces * 3);
                        const CTriangle* pTriangleA = &m_pTriangles[pNode->GetTriangleNum(ixA)];
                        assert(pTriangleA != NULL);
                        if (pTriangleA->Intersect(&TriangleB, &vHitStart, &vHitEnd))
                        {
                            // Es gibt eine Kollision!
                            // Wenn der Ort der Kollision gefragt ist: ausfüllen!
                            // Der Vektor muss aber noch mit der Matrix von Modell A transformiert werden.
                            if (pvOutPos)
                                D3DXVec3TransformCoord(pvOutPos, &D3DXVECTOR3(0.5f * (vHitStart + vHitEnd)), &m_mat);
                            // Sind die Normalvektoren gefragt?
                            // Transformation mit der Matrix des jeweiligen Objekts ist notwendig.
                            // Wir erhalten die Normalvektoren aus den Ebenengleichungen der Dreiecke.
                            if (pvOutNormalA != NULL) 
                                D3DXVec3TransformNormal(pvOutNormalA, m_pTriangles[pNode->GetTriangleNum(ixA)].GetTriangleNormale(), &m_mat);
                            if (pvOutNormalB != NULL) 
                                D3DXVec3TransformNormal(pvOutNormalB, pOtherModel->m_pTriangles[pOtherNode->GetTriangleNum(ixB)].GetTriangleNormale(), pOtherModel->GetMatrix());
                            // Sind die beiden Dreiecke gefragt?
                            if (piOutTriA != NULL) 
                                *piOutTriA = (int)(pNode->GetTriangleNum(ixA));
                            if (piOutTriB != NULL) 
                                *piOutTriB = (int)(pOtherNode->GetTriangleNum(ixB));
                            return TRUE;
                        }
                    }
                }
            }
        }
    }
    return FALSE;
}


Wenn die aktuelle Instanz keine Childs mehr hat und die andere auch nicht, dann werden die Dreiecke verglichen.
Trotzdem wird irgend ein Dreieck zurück geliefert und nicht das am Rand der Berührung (Die Bewegung geht ganz langsam aufeinander vonstatten).

Erkennt hier jemand, wo sich das Dingenz verrennen kann?
Wenn die Triangle-Intersect-Funktion True zurückliefert, obwohl keine Kollision stattfindet, könnte das die Ursache sein./?
Die habe ich aber vollständig aus der Tribase entnommen.
Node-Intersect frage einfach nur die Boxkollision ab und geht so:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    D3DXVECTOR3 vPointTrans[8];
    for (int ix = 0; ix < 8; ix++)
        // Worldbox-Linien in die lokale transformieren
        D3DXVec3TransformCoord(&vPointTrans[ix], &pBox->m_vBounds[ix], pMat);
//      vPointTrans[ix] = pBox->m_vBounds[ix];

    return (IntersectLine(&vPointTrans[0], &vPointTrans[1], pvPointCol) || // Linie unten vorn
            IntersectLine(&vPointTrans[0], &vPointTrans[2], pvPointCol) || // Linie links vorn
            IntersectLine(&vPointTrans[1], &vPointTrans[3], pvPointCol) || // Linie rechts vorn
            IntersectLine(&vPointTrans[2], &vPointTrans[3], pvPointCol) || // Linie oben vorn

            IntersectLine(&vPointTrans[0], &vPointTrans[4], pvPointCol) || // Linie links unten vorn/hinten
            IntersectLine(&vPointTrans[1], &vPointTrans[5], pvPointCol) || // Linie rechts unten vorn/hinten
            IntersectLine(&vPointTrans[2], &vPointTrans[6], pvPointCol) || // Linie links oben vorn/hinten
            IntersectLine(&vPointTrans[3], &vPointTrans[7], pvPointCol) || // Linie rechts oben vorn/hinten
        
            IntersectLine(&vPointTrans[4], &vPointTrans[5], pvPointCol) || // Linie unten hinten
            IntersectLine(&vPointTrans[4], &vPointTrans[6], pvPointCol) || // Linie links hinten
            IntersectLine(&vPointTrans[5], &vPointTrans[7], pvPointCol) || // Linie rechts hinten
            IntersectLine(&vPointTrans[6], &vPointTrans[7], pvPointCol) // Linie oben hinten
            );

Das müsste eigentlich funzen.

Jens

Treue Seele

  • »Jens« ist der Autor dieses Themas

Beiträge: 117

Wohnort: Dresden

  • Private Nachricht senden

2

14.08.2003, 09:35

OK, vergesst es

ich hätte auch keinen Bock, mir diesen Code reinzuziehen.
Aber das Problem lag nicht an der Rekursion. Die hat sich nicht verrannt.

Ich habe nun den Dreieckstest geskipt. Nur den Boxtest durchgeführt. Der reicht ja eigentlich beim OcTree.
Und die Geschichte rennt wieder, wie sie soll :-))