Schnellere(?) Längenberechnung

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

FireballFlame

Betreff: Schnellere(?) Längenberechnung

BeitragFr, Aug 26, 2016 22:23
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn man die Entfernung zweier Punkte in der Ebene ausrechnen möchte, tut man das normalerweise indem man den Betrag des Vektors von einem der Punkte zum anderen ausrechnet, also nach dem Prinzip Code: [AUSKLAPPEN]
x = p1_x - p2_x
y = p1_y - p2_y
dist = Sqr(x * x + y * y)

Solange man nur Entfernungen miteinander vergleichen möchte, kann man die hier langsamste Operation, die Wurzel, einfach weglassen. Benötigt man aber tatsächlich die Entfernung, ist die obige Formel mit einer selbstgeschriebenen Funktion schwer zu überbieten. Unter Umständen kann man aber auf Kosten eines genauen Ergebnisses doch noch etwas Geschwindigkeit herausholen:

Die Idee ist von hier. Kurz erklärt: es werden für "Sqr(x * x + y * y)" zwei grobe Annäherungen berechnet. Die erste ist "Max(Abs(x), Abs(y))" und funktioniert prima, wenn x oder y sehr nahe an 0 liegt, bei ungefähr gleichgroßen Beträgen von x und y liegt sie aber gründlich daneben. Die zweite ist "(Abs(x) + Abs(y)) / Sqr(2)" und zeigt das umgekehrte Verhalten. Da beide Annäherungen immer einen Wert kleiner oder gleich der richtigen Lösung liefern, nimmt man nun das Maximum aus beiden. Zum Schluss kann man noch mit einem passenden Faktor (im Code unten "a" genannt) den Fehler gleichmäßig zwischen "zu groß" und "zu klein" verteilen. Er liegt dann bei ca. ±4%.

Hier ist die eigentliche Funktion, geschrieben in C Code: [AUSKLAPPEN]
#include <math.h>

inline int   max_int  (int   x, int   y) {return (x > y) ? x : y;}
inline float max_float(float x, float y) {return (x > y) ? x : y;}

float FastNorm(int x, int y) {
   const float invSqr2 = 0.707106781f; // Sqr(0.5)
   //const float a = 1.0f;                           // approximation <= real value
   //const float a = 1.08239220f; // Sqr(4 - 2 * Sqr(2))         // approximation >= real value
   const float a = 1.04119610f; // (Sqr(4 - 2 * Sqr(2)) + 1) / 2;   // approximation ~= real value (max pos error = max neg error)                  
   
   x = abs(x);
   y = abs(y);
   
   const float metricMax     = max_int(x, y);      // good for x ~ 0 or y ~ 0
   const float metricInvSqr2 = invSqr2 * (x + y);   // good for x ~ y
   
   return a * max_float(metricMax, metricInvSqr2);
   // https://majewsky.wordpress.com/2011/04/10/optimization-tricks-fast-norm/
}

und benutzt wird sie in BlitzMax mit einem entsprechenden Import und BlitzMax: [AUSKLAPPEN]
Extern "C"
Function FastNorm:Float(x:Int, y:Int)
End Extern


Der Einsatz der Funktion lohnt sich wahrscheinlich aber nur unter optinalen Bedingungen. Hat man beispielsweise x und y von vornherein als Ints gegeben und speichert das Ergebnis in einer Float/Double-Variablen ab, ist sie in (meinem simplen Test) fast doppelt so schnell wie die Sqr-Standardformel. Speichert man das Ergebnis allerdings in einem Int, geht der Vorteil größtenteils verloren; hat man x und y als Gleitkommazahlen gegeben und muss sie bei jedem Aufruf erst casten, dreht sich das Verhältnis sogar um.

Hier noch eine Visualisierung zur Genauigkeit des Ergebnisses: BlitzMax: [AUSKLAPPEN]
SuperStrict
Framework BRL.Max2D
Import BRL.GlMax2D
Import "fastnorm.c"

Extern "C"
Function FastNorm:Float(x:Int, y:Int)
End Extern



Graphics 1024, 768, 0, , GRAPHICS_BACKBUFFER
SetOrigin 512, 384

Repeat
Cls
SetColor 128, 128, 128
DrawRect -512, 0, 1024, 1
DrawRect 0, -384, 1, 768
SetBlend AlphaBlend

For Local a:Float = 0 Until 360 Step .5
Local x:Float = Cos(a) * 350
Local y:Float = Sin(a) * 350

Local fastdist:Float = FastNorm(x, y)
Local x2:Float = Cos(a) * fastdist
Local y2:Float = Sin(a) * fastdist

SetAlpha 1
SetColor 255, 255, 255
Plot x, y
SetColor 255, 0, 0
SetAlpha .5
DrawLine 0, 0, x2, y2

Next

Flip
Until AppTerminate() Or KeyHit(KEY_ESCAPE)
EndGraphics

Zu sehen ist ein Kreis aus weißen Punkten, rot eingezeichnet die von der Funktion aus diesen Punkten errechnete Distanz vom Mittelpunkt.
PC: Intel Core i7 @ 4x2.93GHz | 6 GB RAM | Nvidia GeForce GT 440 | Desktop 2x1280x1024px | Windows 7 Professional 64bit
Laptop: Intel Core i7 @ 4x2.00GHz | 8 GB RAM | Nvidia GeForce GT 540M | Desktop 1366x768px | Windows 7 Home Premium 64bit

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group