schneller Panoramaviewer, Überlegungen (Diskussion)

[helgew]

Schon wieder so früh? Hallo erstmal und schön, dass du in diesen Thread gefunden hast.

Es geht um folgendes: Für eine Grafikapplikation benötige ich einen richtig schnellen viewer für sphärische Panoramen. Ein Ausschnitt dessen soll in rectilinearer Abbildung ("normale" Sichtweise mit begrenztem Field Of View, frei von radialer Verzeichnung) mit typisch 1MP (z.B. 1280x800) angezeigt werden können.
Das Problem dabei ist, dass selbst mit SSE-Befehlen beschleunigte, pixelgenaue Berechnungen bei voller Bildschirmauflösung eine Laufzeit in der Größenordnung 1 Sekunde haben, also etwas, das fernab von echtzeitfeeling ist.


Ich habe nach einigen Stunden Bauchschmerzen nun folgendes Konzept aufgestellt:

Es gibt eine Transformation, die Punkte des Quellbildes in kartesischen Koordinaten auf eine Einheitskugel abbildet. Diese Abbildung basiert auf einem Satz von Stützpunkten, die auf einer zugeordneten Skala verwendbar sind. Wird er Skalenbereich überschritten, erfolgt ein Skalensprung so, dass die Stützpunktdichte der Transformation wieder den festgelegten Nennwert hat.

Damit befinden wir uns in einer kartesischen Kugeldarstellung, die man leicht und schnell durch 3x3-Drehmatrizen manipulieren kann, was auch vergleichsweise schnell berechnet ist. Hinzukommend können auch differentielle Drehungen draufmultipliziert werden, sodass man die oben genannte, erste Transformation nur beim zoomen ausführen muss (genaugenommen auch nach einer bestimmten Zahl von differentiellen Transformationen, wenn sich Rundungsfehler akkumuliert haben...).

Um auf die Quellbilddarstellung zu kommen, die aussieht wie eine Weltkartenansicht, sodass am oberen und unteren Bildrand starke Deformationen zu sehen sind, da die Pixel dort in polnähe liegen muss man einfach Polar- und Azimuthalwinkel mit Skalierungskoeffizienten multiplizieren. Der Hund liegt jedoch bei den inversen trigonometrischen Funktionen begraben. Hier kommt der zweite Trick ins Spiel:
Anstatt die faszinierend langsamen arccos und arctan-Funktionen zu bemühen, werden sechs Projektionen von Kugelsektoren erzeugt, sodass man eine Koordinate wählen kann, die >0.5 ist, diese selektiert eine der sechs lookups, die mit den zwei verbleibenden, senkrechten Koordinaten parametrisiert wird. Auch dies sind wiederum durch Stützstellen gefütterte Projektionen. Im Prinzip zerlegt man so den vollen Raumwinkel in sechs umkehrbare (bijektive) Abbildungen. Bildlich gesprochen schaut man in eine Richtung innerhalb der Panoramakugel, quetscht sie in Blickrichtung platt und nimmt nur den inneren Bereich, der nicht zu sehr verzerrt ist.

dieser Quellbild-lookup mit koordinatenbasierter Fallunterscheidung umgeht die Umrechnung auf sphärische Koordinaten.


Bilanz der ganzen Sache:

Der Abbildungsteil von den Viewport-Koordinaten in den Kugelflächenraum erfolgt anhand einer lookup table, die bei Bedarf aus einer genäherten Abbildung neu erzeugt werden kann. die Stützpunkt der genäherten Abbildung müssen gelegentlich der Skala angepasst werden.
Im Kugelflächenraum lässt sich die Blickrichtung und Neigung des viewports durch einfache Drehmatrizen ausführen.
Punkten im Kugelflächenraum wird durch Fallunterscheidung nach der längsten Koordinate (x, y- oder z-Richtung) und anschließende senkrechte Projektion in Richtung dieser Achse anhand einer von sechs interpolierten lookup-Abbildungen ein Punkt im Quellbild zugeordnet.

Ich habe schon zwei abstrahierbare Module identifiziert:

• source lookup engine : Erzeugung und Verwaltung der sechs Ebenen-Lookups, Interpolation der Quellbildkoordinaten
• destination lookup transform : erzeugt die lustig skalenspringende Transformation vom Viewport in den Kugelflächenraum, aus der die rotierbaren Stützpunkte einer Viewport->Kugelflächenraum-Abbildung generiert werden kann

zwischendrin steht die Drehmatrix und die Verwaltung der Viewport->Kugelflächenraum-Abbildung, die beim zoomen und nach Fehlerakkumulation erneuert werden muss.
Das attraktive an diesem ganzen Getrickse ist für mich, dass es sich hierbei nun ausschließlich um lineare (oder wenn es besser sein soll polynomiale) Abbildungen handelt, die man sogar rein in MMX-beschleunigter Integer-Arithmetik implementieren kann. Klar muss man den gesamten Fehler je nach Stützpunktdichten und Approximationsgrad mit 1-3 Pixeln absolut abschätzen, jedoch ist dies vollkommen irrelevant, solange der Nutzer schnelle Drehungen / Zooming durchführen will. Für eine Ansicht im Stillstand werde ich dann in separaten Threads verteilt eine pixelgenaue Abbildung erzeugen, sobald der Viewport stillsteht. Wird in der Zeit eine Modifikation vorgenommen, wird zunächst wieder approximativ gerendert und die verfeinerte Berechnung wieder verworfen.




So was will ich nun von euch? Eure geschätzte Meinung, Kritik und Verbesserungsvorschläge, die mich davor bewahren, nach mehreren Tagen coden alt auszusehen Oder es kommt jemand und sagt er hats schon implementiert... dann ärgere ich mir ein zweites Loch in den Hintern

edit: auf dem laptop schreibt sichs nicht so gut, entschuldigt die Vertipper...
edit2: Übersicht aller sechs maps für den Quellen-Lookup beigefügt

[Namenloser]

Hallo,

ich kenn mich mit der Materie nicht wirklich aus und bin gerade auch etwas zu müde um deinen Post bis ins Detail zu verstehen, also entschuldige bitte, wenn ich irgendwas dummes sage.

Aber könntest du nicht die Darstellung über OpenGL (oder DirectX) abwickeln? Du erstellst einfach eine Kugel, mappst das Panorama als Textur darauf, und den Rest übernimmt dann die Grafikkarte. Das ganze in Echtzeit zu machen, sollte dann kein Problem sein, schließlich schaffen es aktuelle Spiele, weit mehr als nur eine Kugel mit 60 Frames pro Sekunde anzuzeigen.

[Medium]

Was NamenLozer schreibt war auch der erste Gedanke der durch meinen Kopf schoss. Kugel, Textur drauf, und ab dafür. Die Kugel muss dann nur entsprechend skaliert werden, so dass sie zum gerade aktuellen FOV passt - was bei einigermaßen normalen Winkeln schon recht üppig werden kann, weshalb es sich evtl. lohnen sollte das Bild in eine passende CubeMap Textur für eine Skybox zu wandeln. Das ist dann zwar auch ein vergleichsweise aufwendiger Schritt, muss aber nur ein Mal pro Panorama gemacht werden - wenn du das so dann auch speicherst sogar jemals.
QuickTime bietet auch einen 3D Panorama-Viewer der sehr flott ist. Vielleicht bekommt man ja auch raus, wie die das machen als Anreiz.

[neo4a]

Die Lösung von DevalVR kommt als OCX-Plugin und liefert wirklich schnelle Panoramen. Meinst Du so etwas?

--
Andreas

[helgew]

Vielen Dank für eure Vorschläge. Natürlich habe ich schon an die Skybox gedacht, aber nun eines nach dem anderen:
Es soll ich um eine Erweiterung der Standardzeichenroutinen handeln, die auf normalen Bitmaps rechnet. So habe ich schon eine Stretchdraw-routine implementiert, die 1600x1200 auf einer alten CPU (1,83 GHz single core "Barton 2500+") in 5-6ms rendert, MMX-optimiertes Alphablending vergleichbarer performance und noch ein paar andere Sachen. Es zählt zu den Anforderungen des Programms, dass es auch auf älteren Systemen gut lauffähig sein soll, daher würden sich schon 32MB und 64MB Grafikkarten an der Skybox eines 8000x4000-Panoramas verschlucken (~72MB für sechs 2000x2000x24bit-Bilder).

Ein weiteres Problem, das sich dabei ergibt, ist die Initialisationszeit. Der Nutzer soll maximal 1 Sekunde warten müssen, bis der Viewport gestartet ist, das geht nur mit Approximationen. 12000x2000 Pixel exakt berechnen dauert sehr, sehr lange. Für eine 50%-Ansicht des angehängten Panoramas (~1600x800) läuft die Berechnung hier schon etwa 650ms. Durch Optimierung wird man es wohl nach viel Arbeit auf 150-200ms herunterprügeln können (mit SSE und Tricks... der SSE-Befehlssatz bietet Wurzeln und trigonometrische Funktionen im Viererpack).
Was das Kugelgerüst abelangt, so haftet diesem leider auch der Speicherverbrauch auf der Grafikkarte an, allerdings lässt sich die Bildfeldwölbung beim zoomen anpassen. Schnell ist es dafür, ja, aber der Rechenaufwand ist nicht geringer und wird nur durch viele Recheneinheiten der GPU getragen.

Zum Erzeugen der Stützstellen für die lookup-Funktionen benötige ich bei dem 8000x4000x24bit Panorama etwa 10-20MB Arbeitsspeicher (die Speicherreservierung benötigt hier etwa 300ms) und anhand meiner bisherigen Implementierung extrapoliert 250-450ms (zwei der sechs Seiten des source lookups rechne ich gerade für 8000x4000 Pixel des Quellbilds in ~30ms).
Die sechs lookup tables, die an die Stelle der Skybox treten, zu deren Rendering ich wiederum Trigonometrie bräuchte, beinhalten nur ~300x300 Stützstellen, die aus 4-5 Koeffizienten bestehen.

Vielleicht sollte ich mein Anliegen in diesem Thread noch präzisieren:
Ich weiß, dass man sich mit der Thematik etwas befassen muss, um mögliche Probleme zu sehen, aber was könnte mich bei den ganzen Interpolationen noch schlimmes erwarten?

Momentan grüble ich über die Interpolationskoeffizienten...

[helgew]

Nun, es scheinen sich nicht viele zu diesem Thema äußern zu können. Ich habe derweil weiterprogrammiert und alle 6 Stützpunktsätze (Interpolationskoeffizienten 0. Ordnung) erzeugt, das tut soweit und ist mit ~80ms auch noch schnell genug, wenn man bedenkt, dass es sich um einmalige Berechnung handelt.

Das Übersichtsbild ist dem ersten Post angehängt. Da ich schon eine sphärisch-sphärisch-Transformation implementiert habe, ersetze ich in dieser einen Teil der Previewroutine durch die source lookup engine.. mal sehen, ob es tut.

[helgew]

Schade, dass keiner wirklich Ahnung / Erfahrung hat. Ich werde also bald noch einiges an Zeit damit verbrennen müssen *seufz*

Ende des Threads.

[Medium]

Ist halt auch schon ein ganz schöner Klopper . Allein schon Fullscreen-Repaints ohne jede "Ich-bin-Hardware-Nah"-API dürfte schon gut Zeit futtern, wodurch du dich natürlich einiger Freiheiten in den Berechnungen beraubst. Selbst mit Baseline-OpenGL 1.0 sollte sich schon einiges tun lassen, und ich wüsste kaum eine Grafikkarte die nicht mindestens OGL 2.0 versteht, bzw. im schlimmsten Fall durch den Treiber in Software emuliert - was dir dann zumindest etwas Qualm von der Rübe pusten könnte :]. Texturen können auch im Host-RAM gehalten werden, günstig segmentiert kannst du die ja stückchenweise an die API schicken, so dass nicht immer gleich alles im VRAM schlummern muss. Texturen binden ist eine Sache von einstelligen Millisekunden, und wenn du dann noch mit MIP-Mapping arbeitest, kannst du bei entsprechend breitem FOV frei Haus runterskalierte Versionen nehmen die kleiner sind, und bei dem "Zoom" ausreichen um pixelgenau zu sein.

[igel457]

Ich stimme Medium ganz und gar zu: Grafikberechnungen auf dem Hauptprozessor und das Blitten ist nicht nur langsam, sondern sieht in den meisten Fällen nicht so dolle aus. Bilineare Filterung der Texturen bekommst du bei Verwendung der 3D-Schnittstelle geschenkt dazu.

Und wenn es keine Low-Level API wie OpenGL sein soll: Mit Andorra 2D kannst du genauso gut Sphärensegmente erzeugen, mit einer Textur tapezieren und an die Grafikkarte schicken - und bist dann trotzdem von OpenGL oder Direct3D losgelöst.

Durch effizientes Laden und Entladen der Texturteile im Hintergrund solltest du den Speicherbedarf der Anwendung ohne Probleme bei ca. 32MB halten können.
So würde ich die Panoramateile gleich "zerhakt" in einer Datei hinterlegen, sodass du die einzelnen Teile schnell auslesen kannst.

[helgew]

Da sich nun doch noch Medium und igel457 gemeldet haben:

das blitting eines ganzen frames ist nichtmal soo langsam, einzig in Wine unter Linux ist es so richtig langsam (da ist wohl bei denen was schiefgelaufen, es wurden auchs schon verschiedene Wine-Versionen mit verschiedenen Distributionen getestet), auf meinem Laptop (1280x800) braucht es 20-30ms, an meinem PC mit 1600x1200 leider runde 80-100ms. Aber das ist für die Anwendung schnell genug und wenn man nur den Panorama-viewport aktualisiert, der etwa zwei drittel des Bildschirms ausfüllt, ist es noch etwas besser. Meine stretchdraw-routine braucht für die clientarea bei 1600x1200 etwas mehr als 5ms und darin ist sowohl das skalieren der Pixelkoordinaten als das byteweise Kopieren der Pixelwerte enthalten.
Wenn man sich mit den GDI-Wehwehchen abgefunden hat, stellt man sich die Frage: wieviel ist nötiger Rechenaufwand für ein Problem und wieviel ist overhead?
Selbst Bilder rotieren und skalieren lässt sich auf Vollbild mit > 50fps implementieren, indem man den Overhead durch Single-Arithmetik auf Integerarithmetik umbricht. Wozu erst auf 9 Nachkommastellen genau rechnen und dann runden, was beidesmal irre viel Zeit kostet, wenn die dritte oder vierte Nachkommastelle genügt und eine fixe Anzahl Stellen machbar ist?
Der Unterschied liegt in integer->single und frndint-Konversionen vs. shift-Operationen, ich denke das sieht man. Für die exakte Berechnung kann man sich mehr Zeit nehmen, aber für fließende Bewegungen ist der Betracher auch einfach zu langsam, daher kann man kleinere Fehler zeitweise zulassen. Ich suche bei dem von mir beschriebenen Verfahren nach dieser kleinen Lücke, in der ein geometrisch korrektes Panorama angezeigt wird, dessen Fehler aber erst nach einigen Sekunden Betrachtung auffallen würden, dann jedoch ist schon die exakte Version berechnet und wird drübergezeichnet.

Der Schlüssel dazu liegt darin, auf (inverse) trigonometrische Funktionen zu verzichten, denn die Zuordnunng der Quellpixel auf der Panoramakugel ist nur einmalig zu bestimmen. Ebenso verhalten sich Transformationen vom Zielbild auf die Kugel ähnlich, sodass nur beim Herauszoomen neue Informationen hinzugefügt werden müssen, der innere Bildbereich lässt sich durch Verschiebung der Zuordnungen abbilden. Und plötzlich wird alles so einfach, da man ja trotz des dreidimensionalen problems nur 2d->2d->2d-Abbildungen berechnen muss, die bis auf ein paar Sonderflälle wirklich glatt sind und sich auch leicht approximieren lassen. Bei Drehungen des viewports muss ich doch nicht die volle Transformationskette abarbeiten mit einigen sin/cos-Funktionen und 1-2 arccos, arctan, ... Funktionen - da sich nur die assoziierten Punkte in der Zwischenabbildung auf einer Oberfläche herumbewegen.

Eigentlich sollte man alle Quellpixel auf die Kugel mappen, das dauert jedoch verdammt lang und braucht viel Speicher. Außerdem liegen die Punkte unverändert nebeneinander. Das ermöglicht es dann, zwischen Stützstellen zu interpolieren, ohne dass der Fehler über den Bereich zu groß wird. Ja, irgendwo ist es der workaround eines workarounds, aber soweit ich es implementiert habe, funktioniert es auch schon zufriedenstellend.

Wie es aussieht, habe ich sowieso noch ein paar Tage Zeit zum Nachdenken, da der Quellcode auf dem Laptop ist und der liegt zuhause


Ich sehe es übrigens ein, dass OpenGL / DirectX angemessener wäre, jedoch habe ich auch angefangen, eine kleine Control-Hierarchie zu basteln, die auf einen buffer zeichnet (mit und ohne Alphablending). Der viewport ist die clientarea eines dieser Objekte. Eine Bildebenenverwaltung steuert das ganze. Sämtliche Algorithmen sind buffer-basierend. Ich würde die Entscheidung für gdi drawing nicht als Fehler bezeichnen, aber ich würde doch sehr gerne ohne Tricks mit Hardwarebeschleunigung auskommen, zumal ich korrekt abzuschätzen glaube, dass der Rechenaufwand es zulässt.

Der panorama viewer ist eines der letzten features, nach dessen Implementierung und eininiger Ergänzungen / Optimierungen das Programm auf die OpenSource-Halde gekippt wird (ich bin mir sicher, dass sich da auch eine Panoramaviewer-Komponente abdestillieren lässt ). Nebenher habe ich in Zusammenarbeit mit einem Freund ein remake auf Basis von Qt begonnen und wir haben uns auch OpenGL angesehn.