Farb-Mittelwert und -Varianz in Dreieck berechnen

rapso

Pixie schrieb:

Wie würdet ihr sowas am besten angehen?

wuerde auf gpu triangleID in eine textur rasterisieren und dann mit einem cuda kernel die ID textur und deine quell textur lesen und dann ein atomic min/max auf zwei arrays (mittelds the triangleID) indizieren.

Shader scheinen mir naheliegend, ich würde dann GLSL verwenden. Über die Pixel iterieren geht aufgrund der parallelen GPU-Architektur wohl eher schlecht, oder? Für den Mittelwert wäre schrittweises Downsampling eine Idee, gibts bessere Alternativen?

du willst eigentlich min/max haben pro dreieck, daraus errechnest du dann mittel und varianz, aber downsampling ist eigentlich nicht so optimal, weil dann mehrere texel die zu verschiedenen dreiecken gehoeren zusammenfallen, esseiden du machst das pro dreieck, aber dann bist du x-mal ineffizienter als es auf cpu zu machen.

Zur Vereinfachung können wir vorerst von Grayscale-Texturen ausgehen, 3 der 4 Farbkanäle können also für andere Informationen (wie z.B. Dreiecks-Index) benutzt werden. Die Varianz würde man so skalieren, dass z.B. die grösste Abweichung weiss und die kleinste schwarz entspricht.

die varianz musst du nicht skalieren, die ist maximal so gross wie die input range und die ist ja dann auch 8bit.

Vielen Dank! Also würdest du eher zu CUDA (oder auch OpenCL?) greifen, meinst du mit Shaders kommt man nicht so weit? Oder was könnte man alleine mit GLSL erreichen?

rapso schrieb:

du willst eigentlich min/max haben pro dreieck, daraus errechnest du dann mittel und varianz

Wie kann ich nur aus Minimum/Maximum (2 Werten) den Mittelwert und die Varianz berechnen?

rapso schrieb:

aber downsampling ist eigentlich nicht so optimal, weil dann mehrere texel die zu verschiedenen dreiecken gehoeren zusammenfallen, esseiden du machst das pro dreieck, aber dann bist du x-mal ineffizienter als es auf cpu zu machen.

Hier hätte ich gedacht, man könnte die anderen Farbkanäle brauchen, um die Dreiecks-Zugehörigkeit kennzuzeichnen. Dann würde man nur Farben mit gleichem Index berücksichtigen, aber möglicherweise wäre das dann wieder langsam...

rapso

Pixie schrieb:

Vielen Dank! Also würdest du eher zu CUDA (oder auch OpenCL?) greifen, meinst du mit Shaders kommt man nicht so weit? Oder was könnte man alleine mit GLSL erreichen?

du musst halt sowas implementieren

for(a=0 bis a==PixelAnzahl,a++)
{
DreieckIndex=FindIndexVonDreieckAnPixel(a);
DreiecksListeMin[DreieckIndex]=min(DreiecksListeMin[DreieckIndex],PixelWertBei(a));
DreiecksListeMax[DreieckIndex]=max(DreiecksListeMax[DreieckIndex],PixelWertBei(a));

implementieren.
mit compute (cuda/opencl) ist das relativ einfach, wie kannst du mit OpenGL/GLSL in ein array indizieren? (ich glaube mit opengl 4.2 sollte das gehen, aber alle versionen vorher eher nicht), OpenCL/Cuda ist da sehr einfach, finde ich.

rapso schrieb:

du willst eigentlich min/max haben pro dreieck, daraus errechnest du dann mittel und varianz

Wie kann ich nur aus Minimum/Maximum (2 Werten) den Mittelwert und die Varianz berechnen?

wenn du maximum und minimum von allen texel die zu einem dreieck gehoeren rausfindest, ist:
mittelwert = (Max+Min)/2;
varianz = (Max-Min)/2;

esseiden du meinst 'median' und nicht 'average' wenn du mittelwert sagst.

rapso schrieb:

aber downsampling ist eigentlich nicht so optimal, weil dann mehrere texel die zu verschiedenen dreiecken gehoeren zusammenfallen, esseiden du machst das pro dreieck, aber dann bist du x-mal ineffizienter als es auf cpu zu machen.

Hier hätte ich gedacht, man könnte die anderen Farbkanäle brauchen, um die Dreiecks-Zugehörigkeit kennzuzeichnen. Dann würde man nur Farben mit gleichem Index berücksichtigen, aber möglicherweise wäre das dann wieder langsam...

premature optimization ;), bring es erstmal so einfach wie moeglich zum laufen, dann ist optimieren einfacher da du von einer funktionierenden version schrittweise optimieren kannst und du kannst pruefen ob eine optimierung echt was bringt und nicht eventuell etwas sogar langsammer macht (kann passieren).

rapso schrieb:

wenn du maximum und minimum von allen texel die zu einem dreieck gehoeren rausfindest, ist:
mittelwert = (Max+Min)/2;
varianz = (Max-Min)/2;

Meinen wir mit Mittelwert und Varianz wirklich das Gleiche? Ich bin von den statistischen Messwerten ausgegangen. Wenn ein Dreieck 100 Pixel enthält und davon 99 weiss (1.0) und 1 schwarz (0.0) sind, wäre der Mittelwert nach deiner Formel 0.5 (grau). Er sollte aber 0.99 (also fast weiss) sein...

Darum könnte man statt Min+Max Summe+Anzahl speichern. Für die Varianz wäre die Summe der Quadrate nötig, hier müsste man aufpassen wegen Overflows.

rapso schrieb:

premature optimization ;), bring es erstmal so einfach wie moeglich zum laufen

Ok. Ich dachte nur, dass man eventuell komplett andere Ansätze verfolgen müsste und sich daher die Einarbeitung gar nicht lohnt. Aber etwas Kenntnisse schaden wohl nie

Eine Alternative wäre vielleicht Raytracing/Raycasting. Wenn wir uns die 2D-Textur als Ebene im Raum vorstellen, könnte man entlang jeder "Zeile" der Textur einen Strahl schicken, der die Pixel auf seinem Weg berücksichtigt?

Bisher habe ich z.B. das gesehen...

Also, inzwischen habe ich das implementiert. Mittelwert und Varianz aller Pixel eines Dreiecks berechnen funktioniert mit GLSL.

Bisher habe ich nur ganze Pixel berücksichtigt. Durch die Diskretisierung entsteht eine Ungenauigkeit, diese Fehler möchte ich verkleinern. Wenn zum Beispiel nur 50% der Pixelfläche innerhalb des Dreiecks liegt, sollte dieses Pixel nur mit halber Gewichtung zum Mittelwert beitragen.

Eine Idee wäre Multisampling: Ich verschiebe die Textur um Subpixelwerte, berechne jedes Mal Mittelwert und Varianz, und mittle dann über alle Offsets. Allerdings entstehen dadurch einige zusätzliche Shaderdurchläufe. Da diese das Bottlenecks meines Programms darstellen, möchte ich hier so gut wie möglich optimieren.

Gibt es Alternativen? Könnte man z.B. ein Dreieck so rendern, dass die Kanten "geglättet" werden? D.h. der Alpha-Wert des Pixels wäre von der Zugehörigkeit zum Dreieck abhängig (innerhalb des Dreiecks 1, ausserhalb 0, auf Kante irgendwo dazwischen)? Oder sonstige Ansätze?

Wie werden denn Polygone "smooth" gerendert, geschieht das nur über das Antialiasing-Level beim OpenGL-Kontext? Oder wie kann man das pro Polygon einstellen? GL_POLYGON_SMOOTH scheint ja nichts zu garantieren.

Oder hätted ihr eine andere Idee, wie man den Fehler der Mittelwertberechnung reduzieren könnte?

rapso

Pixie schrieb:

Wie werden denn Polygone "smooth" gerendert

die polygone werden in einer groesseren aufloesung gerendert und dann das ganze bild runterskaliert, dabei vermischt man mehrere pixeln zu einem.
sowohl rasterisieren als auch runterskalieren kennt viele verfahren, zum rasterisieren gibt es
-OGAA (ordered grid AA) was einfach nur die aufloesung groesser macht
-RGAA (rotated grid AA) man rotiert die sub samples etwas
-...
http://www.beyond3d.com/content/articles/37/3
http://en.wikipedia.org/wiki/Supersampling

und ja, garantiert ist nichts, mit einem treiberwechsel kann sich das verhalten aendern, gerade was die optimierungen angeht.

dot

rapso schrieb:

Pixie schrieb:

Wie würdet ihr sowas am besten angehen?

wuerde auf gpu triangleID in eine textur rasterisieren und dann mit einem cuda kernel die ID textur und deine quell textur lesen und dann ein atomic min/max auf zwei arrays (mittelds the triangleID) indizieren.

Ich denk, man könnte auch einfach direkt beim Rasterisieren basierend auf der Primitive ID aus dem PixelShader ein atomic add in ein UAV machen!? Wenn die Dreiecke nicht zu groß sind, könnte das schon ganz gut funktionieren.
Ansonsten lautet das Stichwort wohl Parallel Reduction...

Danke! Momentan baue ich sowas mehr oder weniger in GLSL nach: Ich nehme jeweils 4 Pixel, aus denen ich ein neues berechne. So halbiert sich die Grösse mit jedem Shader-Durchgang, in logarithmischer Zeit berechne ich Mean/Var eines Dreiecks. Dass man eine höhere Auflösung verwenden könnte, ist eine interessante Idee, alternativ wäre eben Supersampling.

Oh oh. Nach einigen Wochen Implementierung und mühsamem Debugging bin ich auf ein enormes Problem gestossen.

Ich muss in kürzester Zeit extrem viele Dreiecke bearbeiten. Und nun ist die Mean/Var-Berechnung mittels GLSL um Längen langsamer, als wenn ich direkt auf der CPU rechne. Ich benutze pro Dreieck Render-to-Texture mittels eines FBO und zwei abwechselnden Texturen (Ping-Pong), die aber die gleiche Dimension haben. Nun scheinen die Texture-Switches extrem teuer zu sein, jedenfalls ruinieren sie mir die Performance.

Eine Idee wäre natürlich, den Shader gleichzeitig über mehrere Dreiecke laufen zu lassen, allerdings geht das nur sehr beschränkt. Mein Algorithmus erzeugt fortlaufend neue Dreiecke, die ich unmittelbar prüfen muss, da weitere Berechnungen davon abhängen.

Hatte vielleicht jemand schon ein ähnliches Problem oder weiss Rat? Ich werde mich jedenfalls schon einmal nach alternativen Ansätzen erkundigen. Vielen Dank für die Hilfe soweit!

knivil

Pixie schrieb:

Danke! Momentan baue ich sowas mehr oder weniger in GLSL nach: Ich nehme jeweils 4 Pixel, aus denen ich ein neues berechne. So halbiert sich die Grösse mit jedem Shader-Durchgang, in logarithmischer Zeit berechne ich Mean/Var eines Dreiecks. Dass man eine höhere Auflösung verwenden könnte, ist eine interessante Idee, alternativ wäre eben Supersampling.

Ist wohl eher O(n log n) und ist im Vergleich zu O(n) fuer Mean/Var suboptiomal. Dabei ist n die Anzahl der Pixel.

Hast recht, ich hoffte allerdings, dass das n aufgrund der parallelen Verarbeitung vernachlässigbar sein sollte. Ist wohl zu optimistisch gedacht