Keskustelu: Koodit: C++: Törmäystarkistus 3D-avaruudessa: jana ja kolmio

int CMaailma::TormaysTarkistus(CVector lahto, CVector suunta) {

    // Tutkitaan törmäysta ensin tason ja janan välillä, jos tässä törmäys katsotaan, onko törmäyspiste kolmiossa
    // Tason yhtälö muotoa
    // Ax + By + Cz = -D
    // A on normaali.x() jne
    // D on kolmio[foo].d
    // Suora 3D-avaruudessa x = p + tpq,       p alkupiste, t reaaliluku ja pq suunta, x suoran piste
    // Taso Ax + By + Cz = -D       -> N dot x = -D
    //----->Piste tasossa, jos N dot x + D = 0
    // Eli leikkaus, jos (p+tpq) dot N + D = 0
    // Sievenee muotoon:
    // tN dot pq = -N dot p - D
    // Josta voidaan ratkaista t:
    //      N dot p + D
    //t = - ------------------
    //      N dot pq
    // Törmäys, jos t välillä [-1,1]


    // Jos N dot pq on 0, on suunta tason suuntainen ja tutkittava, onko alkupiste tasossa ja sitten onko se kolmiossa


    // JOKAINEN (hyi) kolmio erikseen  TODO: Optimointia...
    bool tormays;

    for (int i=0; i<kolmioita; i++) {

        // Ensin tutkitaan ja poistetaan selvät tapaukset

        tormays=true;
        float r=suunta.DotProduct(kolmio[i].normaali);      // r = N dot pq
        float t=0;

        if (r<0.0001 and r>-0.0001){  // Yhdensuuntainen, osuu jos alkupiste tasossa
            // Tutkitaan onko alkupiste tasossa
            float t=lahto.DotProduct(kolmio[i].normaali);
            if (!(t<kolmio[i].d+.9 and t>kolmio[i].d-.9)) {
                tormays=false;
            }
        }
        else {      // Lasketaan t
            float ptulo=lahto.DotProduct(kolmio[i].normaali);
            t = (ptulo-kolmio[i].d) / r;
        }


        if (t>1.03 or t<-1.03) {        // Hyväksytään pientä heittoa
            tormays=false;
        }
        if (tormays==true) {
            // Törmäys tasoon, tutkitaan osuuko kolmioon
            CVector piste=suunta*t; piste+=lahto;       // Törmäyspisteen paikkavektori
            CVector projektiopiste;                     // Törmäyspiste muodostettavassa 2D-projektiossa

            // Nyt tiedetään leikkauspiste, tutkitaan onko se kolmiolla
            // Ensin muodostetaan kolmiosta 2-ulotteinen projektio
            // Jätetään huomiotta se koordinaatti (x/y/z) jota vastaava kerroin tasoyhtälössä Ax+By+Cz on suurin (itseisarvo)
            // Tämän jälkeen tutkitaan montako reunaa pisteestä piirrettyääretön säde leikkaa, ja jos niitä on pariton määrä,
            // niin piste on kolmion (ja itse asiassa minkä tahansa monikulmion) sisällä.
            // Piirretään tämä säde positiivisen x-akselin suuntaan kun on ensin siirretty leikkauspiste origoon

            // Tutkitaan suurin kerroin tasoyhtälöstä
            float a=fabs(kolmio[i].normaali.x()), b=fabs(kolmio[i].normaali.y()), c=fabs(kolmio[i].normaali.z());


            CVector pisteet[3];     // Pisteet 2d-avaruudessa
            if (a>b and a>c) { // Ei huomioida X:ää
                for (int l=0; l<3; l++) {
                    pisteet[l].x(kolmio[i].piste[l].y);
                    pisteet[l].y(kolmio[i].piste[l].z);
                    pisteet[l].z(0);
                    projektiopiste.x(piste.y());
                    projektiopiste.y(piste.z());
                    projektiopiste.z(0);
                }
            }
            else if (b>a and b>c) {  // Ei huomioida Y:tä
                for (int l=0; l<3; l++) {
                    pisteet[l].x(kolmio[i].piste[l].x);
                    pisteet[l].y(kolmio[i].piste[l].z);
                    pisteet[l].z(0);
                    projektiopiste.x(piste.x());
                    projektiopiste.y(piste.z());
                    projektiopiste.z(0);
                }
            }
            else if (c>a and c>b) {      // Ei huomioida Z:aa
                for (int l=0; l<3; l++) {
                   pisteet[l].x(kolmio[i].piste[l].x);
                    pisteet[l].y(kolmio[i].piste[l].y);
                    pisteet[l].z(0);
                    projektiopiste.x(piste.x());
                    projektiopiste.y(piste.y());
                    projektiopiste.z(0);
                }
            }


            // Siirretään pisteitä siten, että törmäyspiste on origossa (eli vähennetään törmäyspisteen koordinaatit)
            pisteet[0]-=projektiopiste;
            pisteet[1]-=projektiopiste;
            pisteet[2]-=projektiopiste;


            // Nyt on selvillä pisteet, tutkitaan moniko niiden välisistä janoista leikkaa positiivisen x-akselin
            int leikkauksia=0;
            for (int l=0; l<3; l++) {
                int p=l+1; if (p>2) p=0;
                // Triviaalit hylkäykset
                if (pisteet[l].x()<=0 and pisteet[p].x()<=0)     //  Y-akselin väärällä puolella
                   continue;
                if ( (pisteet[l].y()>0 and pisteet[p].y()>0) or (pisteet[l].y()<0 and pisteet[p].y()<0))  // Pisteet + tai -
                   continue;

                // Selkeät tapaukset nyt hylätty

                // Selkeästi hyväksyttävät segmentit, eli y-akselin oikealla puolella molemmat ja päätepisteet eri puolilla
                // x-akselia
                if ( pisteet[l].x()>0 and pisteet[p].x()>0) {
                    if ( (pisteet[l].y()<0 and pisteet[p].y()>0) or (pisteet[l].y()>0 and pisteet[p].y()<0) )
                        leikkauksia++;
                }
                else {
                    // Tässä tapauksessa segmentin päät ovat molempien akselien eri puolilla eli leikkaus mahdollinen, mutta
                    // segmentti saattaa myös kulkea origon "väärältä" puolelta
                    // Olkoon p ja q segmentin päätepisteet
                    // Lisäksi olkoon r origo ja s äärettömän kaukana x-akselilla (käytetetään kuitenkin vaikka arvoa (99999,0)
                    // Segmentti pq leikkaa x-akselin, eli segmentin rs, jos käännös p->q->r on eri suuntaan
                    // kuin käännös p->q->s   ( siis käännös q:n jälkeen)
                    // Käännös voidaan laskea 2D-ristutlololla
                    // xy' - yx'     (skalaariluku)
                    // Joka on itse asiassa ristitulon z-koordinaatti


                    // Käytetään vektorista p nimeä vp, koska p on jo int-muuttuja

                    // Vektorit
                    CVector r(0,0,0); CVector s(99999,0,0); CVector vp=pisteet[l]; CVector q=pisteet[p];

                    // p->q->r
                    CVector v1=r-vp; CVector v2=q-vp;
                    float r1=v1.x()*v2.y() - v1.y()*v2.x();

                    // p->q->s
                    v1=s-vp; v2=q-vp;
                    float r2=v1.x()*v2.y() - v1.y()*v2.x();

                    if ((r1<0 and r2>0) or (r1>0 and r2<0)) // Erimerkkiset
                        leikkauksia++;


                }

            }


            if (leikkauksia % 2== 1 ) {  // Leikkaa parittoman määrän sivuja, eli törmäys tapahtui
                return 1;
            }

        } // End if törmäys
    } // End for kolmiot
    return 0;   // Ei törmäystä
}