Hallo,
versuche mich an einer bilinearen Interpolation von Stützstellen.
Da das ganze auf einem ATMega644 laufen soll versuche ich es so klein
wie möglich zu halten.
Der Algorithmus an sich sollte schon Funktionieren.
Nur mit der Festkommaarithmetik bin ich unglücklich.
Vielleicht kann mir jemand einen Tip geben wie es besser geht !?
Das ist bis jetzt rausgekommen :
1
//x1|y1 x2|y1
2
// | |
3
// -a---b-
4
// | * | * ux|uy
5
// | |
6
// -c---d-
7
// | |
8
//x1|y2 x2|y2
9
//
10
//
11
// Wertebereich für die Stützstellen a,b,c,d 0 .. 255
12
//
13
// Werte für x1,y2 von 3..72
14
//
15
// Werte für y1,y2 von 20..100
16
//
17
18
19
20
structtQuadel{
21
uint8_ta,b,// die vier zu interpolierenden Eckwerte.
Wenn ich in meinem Wertebereich uint16_t bleiben will kann ich doch für
meinen Faktor anstelle der 100 einfach 256 eintragen.
Denn ich blase den normierten Wert fx,fy der eigentlich 1 ist auf die
256 auf ?
2^8 * 2^8 = 655535
Das untere Listing ist vom Compiler.
Es sind mit den Bibliotheksdivisionen ca 350 Befehle.
Seht ihr da noch irgendwo Optimierungspotential oder Fehler ?
Wie du schon geschrieben hast, ein Faktor von 256 wäre besser, weil sich
das einfach durch hinzufügen bzw. Weglassen eines Bytes machen lässt.
Bei den Multiplikationen bringt das nicht viel, weil der AVR in Hardware
multipliziert, aber die letzte Division geht schneller.
Hmmm ja,
wobei der Compiler daraus immer noch ein "mul" macht.
Ich habe auch kein anderes Verfahren zum interpolieren gefunden das
besser passt.
Beim <Inverse Distance Weightning> hätte ich sogar noch eine Wurzel und
Quadrat pro Stützstelle.
Das dürfte von Haus aus nicht besser werden.
Danke für Deine Zeit :)
Mit avr-gcc (WinAVR 20100110) 4.3.3 und Optimierung -Os wird bei mir
sowohl das Schieben um Acht Bits als auch die Multiplkation mit 256 zu
Highbyte kopieren und Lowbyte löschen umgesetzt... (und bei der Division
durch 256 ebenso)
Wenn ich das richtig sehe kann die ALU immer nur um eine Stelle logisch
sowie arithmetisch Schieben !?
Das erklärt einiges.
Dann sind die 2^8 zufällig richtig gut erwischt... ;)
Ja, die AVRs haben keinen Barrel Shifter. Da gehts immer nur
Einerstellenweise (Im Binärsystem).
Ich erweitere auch oft gerne mit 2^8 oder 2^16, falls man eine hohe
Genauigkeit benötigt. Man kann ja sogar das Teilen durch Kommazahlen mit
2^(n*8) erweitern, sodass man keine Gleitkommatypen mehr benötigt :-)
Unter Anderem habe ich sowas beispielsweise bei der Umwandlung von
geographischen Koordinaten (NMEA) in einen linearen 24 Bit Bereich
benutzt. Da muss die Genauigkeit ja sehr hoch sein.
Ähm das mit der Genauigkeit verwirrt mich.
Der maximalen Fehler den ich mache ist doch Wertebereich * kleinste
Darstellbare Zahl im Faktor:
(Für n = 1)
Liege ich damit richtig ?
Dann ist n eine hübsche Stellschraube :)