Distanz von (x1,y1) nach (x2, y2) ermitteln



  • Hi

    Ich muss mal wissen, wie man die distanz von punkt A zu punkt B ermittelt.

    Gegeben: x1, x2, y1, y2, xdist, ydist
    Gesucht: dist

    Hier ein Bild zur veranschaulichung: http://img265.imageshack.us/img265/5760/13964950.jpg

    LK



  • Satz des Pythagoras.



  • Danke, aber dies muss so kurz wie moglich sein, da es extrem viel mal pro sekunde wiederholt wird, und deshalb kann ich keine pow oder sqrt benutzen...


  • Mod

    Ohne kommst du nicht aus. Aber vielleicht reicht dir ja der quadratische Abstand, den kann man sehr viel schneller berechnen, weil die relativ teure Wurzel entfällt (übrigens sind Wurzeln auf neuen CPUs bei weitem nicht mehr so teuer wie vor 10 Jahren).



  • ja, weiß ich, aber 1000 mal pro ms..
    Übrigens, könntest du auch die formal sagen ? Wäre nett 🙂



  • lk schrieb:

    ja, weiß ich, aber 1000 mal pro ms..

    versuch mal so schnell zu blinzeln.

    warum brauchst du das denn so oft? was willst du genau realisieren?



  • Ich arbeite an einer graphic application. Meine partikel verfolgen bereits die maus, jedoch mit einem konstantem tempo. Also wollte ich etwas einbauen, dass umso näher der (der oder das ?) partickel der maus ist, umso schneller ist es.


  • Mod

    Also wenn dein Rechner nicht deutlich mehr als 1000 Abstände pro Milisekunde berechnen kann (egal ob mit oder ohne Wurzel), dann verscherbel deinen C64 und keuf dir einen neuen Rechner.

    Ich habe es gerade mal an meinem Rechner getestet, der berechnet 10.000.000 Abstände (mit Wurzelziehen) schneller als ich blinzeln kann.



  • Also soll es nur gut aussehen und nicht exakt sein. Dann berechnest du erstmal den quadratischen Abstand xdist*xdist + ydist*ydist und schaust, ob das schon reicht. Eventuell ein paar Heron-Iterationen drauf, oder du berechnest die Wurzel durch Interpolation über einer Lookup-Tabelle.
    Alles natürlich nur, wenn das Wurzelziehen echt zu langsam ist.



  • lk schrieb:

    Ich arbeite an einer graphic application. Meine partikel verfolgen bereits die maus, jedoch mit einem konstantem tempo. Also wollte ich etwas einbauen, dass umso näher der (der oder das ?) partickel der maus ist, umso schneller ist es.

    Da reicht auch der quadratische Abstand. Und besser als a*a + b*b = r*r ist nun mal nicht drin.

    keine pow oder sqrt benutzen

    Fuer soetwas einfach solltest du sowieso nicht auf pow zurueckgreifen, da hier mittels e^x und log x potenziert wird.

    Es gibt auch einige floating point Tricks fuer das Inverse der Wurzel: http://en.wikipedia.org/wiki/Fast_inverse_square_root


  • Mod

    knivil schrieb:

    Es gibt auch einige floating point Tricks fuer das Inverse der Wurzel: http://en.wikipedia.org/wiki/Fast_inverse_square_root

    Wieso wird dieser Mist eigentlich immer noch verbreitet? Das war vor 10 Jahren vielleicht mal schneller. Auf heutigen Rechnern ist das etwa 2x so langsam wie das normale Wurzelziehen und teilen, dabei aber ungenauer.



  • Das war vor 10 Jahren vielleicht mal schneller. Auf heutigen Rechnern ist das etwa 2x so langsam wie das normale Wurzelziehen und teilen, dabei aber ungenauer.

    Nein, das kann ich nicht bestaetigen. Wird die reine Wurzel benoetigt, so sind die beiden Methoden etwa gleich schnell. Wird aber das Inverse (z.B. zur Normalisierung) gebraucht, so schneidet InvSqrt besser ab. Aber du kannst es selbst fuer dein System testen:

    #include <iostream>
    #include <cmath>
    
    float InvSqrt (float x)
    {
        float xhalf = 0.5f*x;
        int i = *(int*)&x;
        i = 0x5f3759df - (i>>1);
        x = *(float*)&i;
        return x*(1.5f - xhalf*x*x);
    }
    
    int main ()
    {
        float sum = 0;
        float one = 1.0;
        for(int i=1; i < 10000000; i++)
        {
             sum += InvSqrt( static_cast<float>( i ) );
             //sum += one / std::sqrt( static_cast<float>( i ) );
        }
        //std::cout << InvSqrt(100.0) << std::endl;
        //std::cout << one / std::sqrt(100.0) << std::endl;
        std::cout << sum << std::endl;
    }
    

  • Mod

    knivil schrieb:

    Nein, das kann ich nicht bestaetigen. Wird die reine Wurzel benoetigt, so sind die beiden Methoden etwa gleich schnell. Wird aber das Inverse (z.B. zur Normalisierung) gebraucht, so schneidet InvSqrt besser ab. Aber du kannst es selbst fuer dein System testen:

    Das ist es ja gerade, wie ich darauf komme. Den Test habe ich schon vor langer Zeit mal gemacht, als ich mal die Inverse Wurzel brauchte. Ich habe ihn gerade nochmal wiederholt. Die Quake3 Version braucht 1,5 Mal so lange wie die normale Division mit Wurzel. Und dabei ist die Quake3 Version auch noch haarsträubend ungenau, erst mit zwei Iterationen erreicht man die gleiche Genauigkeit wie bei der Standardwurzelinversen. Und dann ist man schon bei einem Faktor 3 als Laufzeitunterschied.

    edit: Jetziges System ist mit i7 Prozessor natürlich ziemlich aufgemotzt, aber als ich den Test vor ein paar Jahren mal gemacht habe war es auf einem etwas angestaubten Athlon.



  • knivil schrieb:

    Es gibt auch einige floating point Tricks fuer das Inverse der Wurzel: http://en.wikipedia.org/wiki/Fast_inverse_square_root

    dieses int*-nach-float* gecaste geht bestimmt nicht überall. versuch mal den:

    unsigned inv_sqrt (unsigned long v) 
    { 
        unsigned long tmp, r=0, b=32768;
        int shift = 15; 
        do 
        { 
            tmp = ((r<<1)+b) << shift;
            shift--;
            if (v >= tmp) 
            { 
              r += b; 
              v -= tmp; 
            }
        } while (b >>= 1); 
        return r; 
    }
    

    ^^ braucht 16 schleifendurchläufe und hat manchmal leichte abweichungen, aber ist natürlich der knaller auf systemen ohne FPU.
    🙂


Log in to reply