PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Logarithmische Funktion interpolieren ...


zeckensack
2004-03-14, 04:12:11
Die Funktion sieht so aus:
f(x)=k*log(x), k ist konstant und IMO nicht weiter wichtig.

Ich suche eine möglichst gute Näherung, um Teilstücke davon mit möglichst geringer Abweichung zu interpolieren. Es muss natürlich nicht perfekt sein ...

Also als vernünftige Aufgabenstellung ungefähr so:
f(a)=k*log(a)
f(b)=k*log(b)

c:=a+t*(b-a), t ist Element von [0...1]
f(c) ist gesucht.

An Werkzeugen habe ich leider nicht die komplette Algebra, sondern nur lineare Interpolation zwischen den Endpunkten, und "Perspektiv-Division" könnte ich auch nutzen. Mehr ist nicht drin. Das ist das Problem.

Mit Perspektiv-Division meine ich dass ich eine beliebige zweite Funktion, nennen wir sie mal q(x) für die Endpunkte ausrechnen kann, und diese ebenfalls linear interpoliere. Den "eigentlichen" Wert der Endpunkte multipliziere ich vor der Interpolation mit q(x), und dividiere dann durch das interpolierte q, um den "eigentlichen" interpolierten Wert zu erhalten.
Der Wert der Endpunkte ändert sich dadurch nicht, aber die Interpolation erhält dadurch eine Krümmung.

Nur leider fehlt mir ein passendes q(x) :(
*jammer*

zeckensack
2004-03-14, 05:22:40
Das Teilstück von knapp über 0 bis 1.
In grün die Original-Funktion f(x)=-log2(x)
In orange die simple lineare Interpolation, aka q(x):=1. Das ist natürlich brutal schlecht, demonstriert aber schön, dass ich eine "bessere" Interpolation ganz gut gebrauchen kann.
In rot das Ergebnis von ausgiebigem Raten und Rumpopeln. q(x)=1.0f/4096+pow(1.0f/64,2.0f-x)

:(

Die Skalen sind btw linear, und auf den genutzten Wertebereich normalisiert.

mrdigital
2004-03-14, 11:36:41
mach doch eine Taylor-Reien Entwicklung, ich denke, dass du nach dem 3 oder 4 Glied eine hinreichend gute Annäherung hast.
Das sieht dann so aus :
http://mo.mathematik.uni-stuttgart.de/inhalt/aussage/aussage180/img1.png
a ist dein Entwicklungspunkt, also der Punkt, in dessen Umgebung die Funktion durch diese Potenzreihe angenähert wird. Je mehr Glieder du zur Näherung herranziehst, umso grösser wird der Konvergenzradius, d.h. der "Gültigkeitsbereich" der Näherung. Für f (n) nimmst du die n-te Ableitung der Funktion an der Stelle a.

mrdigital
2004-03-14, 11:39:02
Du kannst aber auch eine Fourierreihenentwicklung machen, wobei die in diesem Fall nicht so effektiv ist, weil sich die Potenzen der Taylor Reihe sicher leichter berechnen lassen, als eine Sinus / Cosinus Reihe..

Demirug
2004-03-14, 11:48:38
Taylor dürfte hier nicht alzu viel bringen da sich die einzelnen Elemente ja auch nicht linear interpolieren lassen.

Zecki, welche "Grafikhardware" möchtest du den genau missbrauchen?

zeckensack
2004-03-14, 11:52:30
Original geschrieben von mrdigital
mach doch eine Taylor-Reien Entwicklung, ich denke, dass du nach dem 3 oder 4 Glied eine hinreichend gute Annäherung hast.
Das sieht dann so aus :
http://mo.mathematik.uni-stuttgart.de/inhalt/aussage/aussage180/img1.png
a ist dein Entwicklungspunkt, also der Punkt, in dessen Umgebung die Funktion durch diese Potenzreihe angenähert wird. Je mehr Glieder du zur Näherung herranziehst, umso grösser wird der Konvergenzradius, d.h. der "Gültigkeitsbereich" der Näherung. Für f (n) nimmst du die n-te Ableitung der Funktion an der Stelle a. Ich bin mir nicht sicher, ob mir das hilft.
Die Funktion in rot ist nicht die Potenzfunktion selbst, sondern das Ergebnis der (durch eben diese Potenzfunktion verzerrten) Interpolation zwischen den beiden ausgerechneten Stützpunkten.

Es geht mir nicht darum, die Funktion für einen festen Wert auszurechnen. Konstante*log2(x) ist ja nun wirklich nicht schwer :)
Es geht mir darum, die Genauigkeit einer Interpolation zwischen zwei Stützpunkten zu verbessern.

Also nochmal:
f(a) ist bekannt
f(b) ist bekannt

Interpolieren kann ich nur linear. Die Krümmung bekomme ich, indem ich Wertepaare linear interpoliere, und dann nach der Interpolation dividiere. In dieser Form:

Stützpunkte:
A'=f(a)*q(a)
qA=q(a)

B'=f(b)*q(b)
qB=q(b)

Interpoliertes Wertepaar:
i'=A'+t*(B'-A')
q=qA+t*(qB-qA)

"Rückgewinnung":
i=i'/q

Das ganze lässt sich btw trivial auf lineare Interpolation reduzieren, indem ich q(x):=1 setze.
Es ist im übrigen eine Hardware-Limitierung ;)
________________________
Wenn ich zur Minimierung des Fehlers tatsächlich mit dem Taylor arbeiten kann, dann habe ich noch nicht begriffen wie :)

zeckensack
2004-03-14, 12:04:55
Original geschrieben von Demirug
Taylor dürfte hier nicht alzu viel bringen da sich die einzelnen Elemente ja auch nicht linear interpolieren lassen.

Zecki, welche "Grafikhardware" möchtest du den genau missbrauchen? Mit der ursprünglichen Funktion (in grün) wir eine "fog table" indiziert. Mit Texturen kann ich schlecht arbeiten, weil ich a)dann einen dependent read am Hals hätte, und b)das Ding riesig gross sein müsste, wenn die Präzision akzeptabel bleiben soll.

DRs wären sowieso ganz schlecht, weil meine Planung eigentlich vorsah, die unterstütze Hardware-Basis nach unten zu erweitern (Kyro, Wildcat VP).

Es ist im Grunde nicht weiter kritisch, aber es wurmt mich enorm, dass ich es nicht durchschaue :)

mrdigital
2004-03-14, 12:14:15
kannst du potenzieren? Wenn ja, dann machst du auf jeden Fall eine Taylorreihenentwicklung, man kann mit einer Taylorreihe jede Funktion beliebig genau in einer Umgebung um a annähern. Du musst dann nicht mehr interpolieren, Taylor liefert dir ja "direkt" die gesuchten Werte (mit einem Fehler kleiner als das Restglied, wie gesagt, Talyor konvergiert ab der 3 oder 4 Ordnung recht schnell, selbst bei "wilden" Funktionen). Wenn du nicht potenzieren kannst, wird es schwierig, denn mit einer linearen Funktion kann man den log eben nur schwer annähern und der Fehler wird recht schnell gross, ausser du kannst abschnittsweise verschiedene Annäherungen definieren, was aber den Aufwand nicht gerade verkleinert

Demirug
2004-03-14, 12:41:53
Original geschrieben von zeckensack
Mit der ursprünglichen Funktion (in grün) wir eine "fog table" indiziert. Mit Texturen kann ich schlecht arbeiten, weil ich a)dann einen dependent read am Hals hätte, und b)das Ding riesig gross sein müsste, wenn die Präzision akzeptabel bleiben soll.

DRs wären sowieso ganz schlecht, weil meine Planung eigentlich vorsah, die unterstütze Hardware-Basis nach unten zu erweitern (Kyro, Wildcat VP).

Es ist im Grunde nicht weiter kritisch, aber es wurmt mich enorm, dass ich es nicht durchschaue :)

Zusammengefasst hast du also das Problem das du für ein beliebiges X einen Fogwert Y brauchst? Der Fogwert liegt im Bereich von 0 bis 1 nehme ich jetzt mal an.

In welchem Zahlenbreich bewegt sich dein x und wie gross ist die Fog Table?

zeckensack
2004-03-14, 12:49:47
Original geschrieben von mrdigital
kannst du potenzieren? Wenn ja, dann machst du auf jeden Fall eine Taylorreihenentwicklung, man kann mit einer Taylorreihe jede Funktion beliebig genau in einer Umgebung um a annähern. Du musst dann nicht mehr interpolieren, Taylor liefert dir ja "direkt" die gesuchten Werte (mit einem Fehler kleiner als das Restglied, wie gesagt, Talyor konvergiert ab der 3 oder 4 Ordnung recht schnell, selbst bei "wilden" Funktionen). Wenn du nicht potenzieren kannst, wird es schwierig, denn mit einer linearen Funktion kann man den log eben nur schwer annähern und der Fehler wird recht schnell gross, ausser du kannst abschnittsweise verschiedene Annäherungen definieren, was aber den Aufwand nicht gerade verkleinert Ich kann an den Stützpunkten alles machen was ich mir vorstellen kann :)
... nur eben dazwischen nicht. Auch dieses ominöse q(x) kann ich nur an den Stützpunkten ausrechnen. Ein anderes Mittel als ein geeignetes q(x) zu finden, habe ich leider nicht - die Arbeitsweise der Interpolation selbst kann ich nicht beeinflussen :sick:

q(x) kann aber völlig beliebig sein, gerne auch segmentweise gestückelt. Die Variante, die oben den roten Graphen erzeugt hat, ist das Ergebnis von purer Rumprobiererei, und das ist irgendwie ... beschämend :|

zeckensack
2004-03-14, 12:59:04
Original geschrieben von Demirug
Zusammengefasst hast du also das Problem das du für ein beliebiges X einen Fogwert Y brauchst? Der Fogwert liegt im Bereich von 0 bis 1 nehme ich jetzt mal an.

In welchem Zahlenbreich bewegt sich dein x und wie gross ist die Fog Table? Ist alles schon drin, und normalisiert.
Der Wertebereich des "Inputs" ist >0, <=1.
Der resultierende Index in die Tabelle soll >=0, <=1 sein
Die Tabelle hat 64 Einträge, das ist aber eher wurscht, weil die Texturaddressierung sowieso auf [0...1] normalisiert ist. Eine grössere oder kleinere Tabelle ändert daran also nichts.
edit: Genau, die fog table ist nämlich als 1D-Textur gelöst, und wird dann pro Pixel - mit dem hoffentlich korrekt interpolierten Index ;) - ausgelesen

Und es ist exakt die Funktion, die ich oben angegeben habe: von "Input" nach "Index" komme ich mit f(x)=-log2(x). Zu sehen in grün :)
Der Input ist nie Null, und nie negativ. Er kann in Extremfällen >1 sein, aber der Bereich ist nicht weiter von Interesse, weil später (nach der Interpolation) sowieso auf [0...1] geclampt wird.

Brutalstmögliche Lösung:
Alle Dreiecke so weit zerlegen, dass jedes nur noch ein Pixel gross ist. Dann kann ich die Geschichte pro Vertex ausrechnen, und brauche mir um die Interpolation keine Sorgen mehr zu machen :D

Demirug
2004-03-14, 13:26:54
Rein vom Gefühl her würde ich die Fogtable auf 2048 (oder was der entsprechende Chip eben hergibt) Elemente vergrössern und dort dann den Fogwert direkt in Abhängigkeit von X hinterlegen.

Eine 2048*1 Textur dürfte speichertechnisch ja noch vertretbar sein.

Solange man nicht ständig die ursprüngliche Tabelle verändert sollte das Berechnen der vergrösserten Tabelle nicht sonderlich ins Gewicht fallen.

mrdigital
2004-03-14, 16:03:33
so der gute Bronstein (5. Auflage S.1043) liefert folgende Reihenentwicklung für
ln x :

2 [ (x - 1) / (x + 1) + (x - 1)³ / 3(x + 1)³ + (x - 1)^5 / 5(x + 1)^5 + .... + (x - 1)^2n+1 / (2n + 1)(x + 1)^2n+1 ]

gilt für x > 0

wenn du allerdings den Bereich von x eingrenzen kannst auf Werte zwischen 0 < x < 2, dann gibts eine einfachere Näherung, bei Bedarf kann ich die dir schreiben (bin grad zu faul das in ASCII zu hacken ;))

zeckensack
2004-03-14, 23:32:06
Original geschrieben von mrdigital
so der gute Bronstein (5. Auflage S.1043) liefert folgende Reihenentwicklung für
ln x :

2 [ (x - 1) / (x + 1) + (x - 1)³ / 3(x + 1)³ + (x - 1)^5 / 5(x + 1)^5 + .... + (x - 1)^2n+1 / (2n + 1)(x + 1)^2n+1 ]

gilt für x > 0

wenn du allerdings den Bereich von x eingrenzen kannst auf Werte zwischen 0 < x < 2, dann gibts eine einfachere Näherung, bei Bedarf kann ich die dir schreiben (bin grad zu faul das in ASCII zu hacken ;)) Ich will ja nicht undankbar erscheinen, aber ich glaube wir reden immer noch aneinander vorbei. Ich kann an den Stützpunkten (deren Abstände ich mir leider nicht aussuchen kann, was einer der Gründe für das Problem ist) alles rechnen, was ich möchte. Ich kann dort auch gleich richtig -log2(x) ausrechnen, und brauche keine Näherung.
Zweierlogarithmen sind sowieso sehr einfach, dafür reicht es fast schon, wenn man den Exponenten (aus der Gleitkommazahl) extrahiert, und ein wenig schummelt :)
Alternativ kann ich auch in einem Vertex Shader direkt LG2 benutzen, und kriege sofort ein ziemlich korrektes Ergebnis (>=10 signifikante Dualstellen, also <0,1% relativer Fehler).

Zwischen den Stützpunkten ist in Punkto Flexibilität das Gegenteil der Fall. Ich habe einfach keine Chance, dort so eine Reihe durchzurechnen. Auf Architekturen, wo ich das dann doch könnte (NV3x, R(V)3xx), steht mir direkt LG2 zur Verfügung - da kann ich mir den Taylor auch gleich wieder schenken.


Es gilt immer noch, dass ich ein von den Stützpunkten ausgehend linear interpoliertes Wertepaar hineinbekomme, und noch einmal dividieren kann. Sonst nichts.
Wenn ich auf die Division verzichte, oder durch eine Konstante dividiere, ist die Interpolation vollständig linear.

zeckensack
2004-03-15, 00:12:29
Original geschrieben von Demirug
Rein vom Gefühl her würde ich die Fogtable auf 2048 (oder was der entsprechende Chip eben hergibt) Elemente vergrössern und dort dann den Fogwert direkt in Abhängigkeit von X hinterlegen.

Eine 2048*1 Textur dürfte speichertechnisch ja noch vertretbar sein.

Solange man nicht ständig die ursprüngliche Tabelle verändert sollte das Berechnen der vergrösserten Tabelle nicht sonderlich ins Gewicht fallen. Ist IMO unbefriedigend, weil der Logarithmus viel zu ungleichmässig, und punktuell zu stark gekrümmt ist.

Mal rechnen: f(x)=-log2(x)/16 => bildet mir [1/65536...1] nach [0...1] ab.
Umkehrfunktion ist f'(x)=2^(-16*x).

Dh also, um den 63ten Eintrag in der Tabelle zu treffen (f(x)=1), muss x=2^(-16) sein. Um den 62ten Eintrag zu treffen (f(x)=62/63), muss x=2^(-16*62/63)~=0.000018 sein.

Die Grösse der Textur, um jeden Eintrag der ursprünglichen fog table überhaupt nutzen zu können, müsste also 65536*1 sein. No go.

Trap
2004-03-15, 01:50:38
Warum nimmst du nicht einfach ein passendes Programm, gibst deine Formel mit Variablen ein und lässt die Variablen optimieren?

mrdigital
2004-03-15, 09:48:06
ok nochmal für doofe wie mich ;D
wie viele Stützpunkte hast du bei deinem Problem? Liegen die so weit auseinander, dass wenn du die Stützpunkte direkt verbindest, nur crap rauskommt?

zeckensack
2004-03-17, 17:00:01
Original geschrieben von Trap
Warum nimmst du nicht einfach ein passendes Programm, gibst deine Formel mit Variablen ein und lässt die Variablen optimieren? Ich kann sie nicht "passend" parametrieren. Es muss irgendeine andere Basisfunktion her, ich weiss eben nur noch nicht welche. Die Potenzfunktion hat die falsche Charakteristik, egal welche Parameter ich einsetze.

zeckensack
2004-03-17, 17:04:46
Original geschrieben von mrdigital
ok nochmal für doofe wie mich ;D
wie viele Stützpunkte hast du bei deinem Problem? Liegen die so weit auseinander, dass wenn du die Stützpunkte direkt verbindest, nur crap rauskommt? Die Stützpunkte kann ich mir nicht aussuchen. Sie werden von einem Client-Programm geliefert. Es kann durchaus vorkommen, dass der volle Wertebereich überstrichen wird.
Wenn ich sie direkt verbinde, passiert das, was oben im zweiten Posting in orange eingezeichnet ist.
... und das ist ziemlich weit daneben :)

Ich habe mich eigentlich schon damit abgefunden, dass ich keine perfekte Lösung finde. Ich setze jetzt einfach q(x)=1/sqrt(x). Das ist zwar auch relativ shice, dafür ist es sehr simpel zu rechnen, und es ist immer noch um Längen besser als die aktuelle Implementation.
Wenn sich die "richtige" Lösung noch einfindet, kann ich immer noch nachbessern.