Schnellstmöglicher Schnittpunkt Strahl<->Kugel



  • Hallo,

    ich suche den schnellstmöglichen Algorithmus, um den Schnittpunkt eines Strahls im R³ (o + td) mit einer Kugel mit Radius r zu bekommen.
    Ich habe dabei einige günstige Ausgangsvoraussetzungen:
    1. Die Kugel hat den Mittelpunkt IMMER im Ursprung (0,0,0)
    2. Der Strahl beginnt IMMER in der Kugel, es wird also IMMER exakt einen Schnittpunkt geben. (Ferner ist der Startpunkt o des Strahls immer genau über dem Kugelmittelpunkt: o = (0, h, 0))

    Momentan benutze ich folgenden Algorithmus:
    http://wiki.cgsociety.org/index.php/Ray_Sphere_Intersection (bei Practical Simplification):
    Berechnung von t: (o + td) * (o + td) = r², sprich: At² + Bt + C = 0
    mit A = d*d, B = 2*(d*o) und C = O*o - r².
    Ich löse dann einfach die quadratische Gleichung auf und erhalte t0 und t1, wobei ein t natürlich immer negativ ist (quasi der Schnittpunkt in der Gegenrichtung von d).
    Ich kriege also immer ein Ergebnis zu viel und frage mich nun, ob das auch effizienter geht?



  • ja. indem du nur das t berechnest das positiv ist. ansonsten ist die lösung auf der seite schon sehr gut optimiert, wenn man keine weitere annahmen treffen kann.
    wenn du beiden lösungen (t_0,t_1) mal anschaust, wirst du feststellen, dass das, was auf der seite, die du verlinkt hattest, als t_1 bezeichnet wird, grundsätzlich größer ist als t_0. da du immer genau eine positive und eine negative herausbekommst, spricht einiges dafür, dass das t_1 sein wird.



  • sollte es nicht einfach nur

    t = RadiusSphere-dot(SphereCenter,normalize(RayDir));
    

    sein?
    je nachdem koennte RayDir schon normalisiert sein, somit nur dot ohne normalize.

    Falls du hardware mit eingebautem dot4 hast (z.b. nen neueren intel chip), kannst du noch ein wenig mehr optimieren, indem du 4dimensionale vectoren benutzt:n spherecenter *-1 und dann den radius als w komponente setzen. Raydir muss ebenfalls 4dimensional (x,y,z,1.f) sein.

    das ganze ist dann

    t = dot4(SphereCenter4,RayDir4);
    

    ist eine instruktion genug optimierung? 🙂

    alles unter der annahme dass ich mich bei der ersten formel nicht versehen habe 🙂


Log in to reply