Dreieck zeichnen

[Schreiberling]

Hallo, folgende Problematik:

Hintergrund:
Ich bin Student und belege das Modul Computergrafik und versuche derzeit mit Java eine kleine 3D-Grafikbibliothek zu programmieren in dem ich die Konzepte der Computergrafik nachprogrammiere (zB. Clipping, Culling, Kameraperspektiven, zBuffer).

Früher habe ich ohne zBuffer gearbeitet, nun möchte ich einen zbuffer realisieren. Also erzeuge ich ein BufferedImage und erweiteres das ganze um ein Float-Array um den Z-Wert abzuspeichern und zu vergleichen. Ich ermittle als erstes den Dreieckstyp (wo sind die Ecken) und ermittle dan per Schleife jeden Pixel des Dreiecks und setze (sofern der zWert kleiner ist) den Pixel mit setPixel. Wenn das ganze fertig ist gebe ich alles mit drawImage wieder aus.
Leider dauert das ganze viel zu lange!!! Ich habe mit System.nanoTime() die Laufzeiten gemessen. Mit fillPolygon braucht das zeichen bei mir 0.036 Millisekunden, mit dem selbstberechnen benötige ich 15 Millisekunden das ist die 400fache Zeit!

Wie bekomme ich das schneller hin? Hat irgendjemanden einen effektiven Algorithmus zum Dreiecks(Pixel) berechnen?

 

[Marco13]

Einerseits ist das eine Kunst für sich... du hast ja nicht beschrieben, WIE du die Pixel bestimmst, die (vielleicht) gesetzt werden müssen (außer "mit einer Schleife" - was klar ist). Zusätzlich ist die "setRGB"-Methode (die du wohl mit setPixel meintest) u.U. SEHR (SEHR!) ineffizient: Der Aufruf wird an's Raster weitergereicht, und das ColorModel hat da auch noch ein Wörtchen mitzureden ....
Aber abgesehen davon kann Java bei solchen Sachen ja auf die nativen Methoden zugreifen, d.h. es kann (theoretisch) sein, dass das Polygon (sozusagen!) nativ mir OpenGL gezeichnet wird - genauso schnell wird deine Methode also nie werden.

 

[Schreiberling]

du hast natürlich recht, die BufferedImage Methode heisst SetRGB (setPixel hiess die Methode bei meiner abgeleiteten Klasse, verwechselt).

Ich habe folgendes verfahren zur Berechnung der Dreieckspixel:
1. Bestimmung vom maximalen X, minimalen X, maximalen Y und minimalen Y Wert
2. Aufgrund dieser Werte schaue ich wieviele "Eckpunkte" (also schnittwerte mit den maximas/minimas) ich besitze
3. Gabelung nach Anzahl der Eckpunkt.
4. Nun wird jeder Y-Wert durchgegangen (also von maxY bis minY).
5. Die Methode calculateDistanceFromPointOnLine berechnet die Koordinaten der Punkte auf den Dreieckskanten (inkl. Z-Wert). (welche Kante wo ist hängt von der Anzahl der Eckpunkt an)
6. Nun werden die X-Werte durchgegangen, die Methode calculateDistanceFromPointOnLine berechnet wieder den Z-Wert des Pixels.
7. im zBuffer wird geprüft ob der aktuelle Z-Wert kleiner ist als der bisherige. Wenn ja wird der Pixel mit setRGB gesetzt.

Früher bin ich alle Pixel in dem Rechteck (gebildet von minX, maxX, minY, maxY) durchgegangen und habe über die Winkel geprüft ob der Pixel im Dreieck liegt, das mach ich inzwischen nicht mehr. Es reicht ja nur die Pixel zwischen den Kanten Links und Rechts zu überprüfen, und diese Werte muss ich sowieso berechnen um später die zWerte korrekt zu berechnen.

Das mit OpenGL usw. hab ich mir auch schon überlegt. Führt die Zeichenoperation bei fillPolygon die Grafikkarte aus (die ja deutlich schneller ist) oder macht das direkt auch der Prozessor (was ja bei mir der Fall ist, oder?). Ich erwarte auch nicht das es so schnell wie die fillPolygon wird, aber das 400fache ist schon arg langsam.

EDIT:
Mein geseztes Ziel war es die Platonischen Körper (Oktaeder, Tetraeder, etc. ) flüssig (bei aktuellem PC) in einem Applet sich drehend anzeigen zu können.

EDIT:
Ich hab noch ein paar PerformanceMessungen durchgeführt:
ca. 22% der Zeit benötigt die Funktion calculateDistanceFromPointOnLine
ca. 30% der Zeit benötigt die Funktion setRGB

 

[Marco13]

Der Algorithmus (speziell das "calculateDistanceFromPointOnLine") klingt sehr kompliziert. Der "bekannteste" ist der Scanline-Algorithmus, aber kannst ja mal mit http://www.google.com/search?hl=de&...sult&cd=1&q=polygon+filling+algorithm&spell=1 allgemein suchen (z.B. schon der erste Link).

Das mit OpenGL usw. hab ich mir auch schon überlegt. Führt die Zeichenoperation bei fillPolygon die Grafikkarte aus (die ja deutlich schneller ist)
das definitiv zu sagen ist schwierig - aber es KÖNNTE (meines Wissens nach) sein.

oder macht das direkt auch der Prozessor (was ja bei mir der Fall ist, oder?).
Ja, wenn man das so "von Hand" macht, macht das nur der Prozessor... Aber selbst da kann die Frage, ob man ein "setRGB" auf einem BufferedImage ausführt, oder nur einen int in einem Array setzt, einen Unterschied von etlichen Größenordnungen ausmachen. Ggf. wäre es effizienter, direkt in das BufferedImage zu schreiben, wenn man sich mit "getRaster().getData()" (oder so, müßt' ich nachsehen) den darunterliegenden int-Array holt...

 

[Guest]

ok, ich habe das Programm gut optimieren können.

Der Tip mit dem getRaster().setPixel() war echt wertvoll. Ich habe dadurch die Funktion von 15 Millisekunden auf 10 Millisekunden senken können, danke!

Außerdem konnte ich noch 2 Millisekunden bei der Berechnung der Pixel einsparen. Früher habe ich mit calculateDistanceFromPointOnLine immer die Höhe und die Position der Pixel ermittelt (die hat intern die Steigung ausgerechnet und das auf meinen Punkt umgerechnet). Das hab ich jetzt komplett rausgenommen. Stattdessen berechne ich einmal die Steigung an den Linien und zähle die Linienwerte einfach bei jedem Schleifendurchlauf um die Steigung hoch. Also bin ich jetzt bei 7 - 8 Millisekunden!

Doppelt so schnell ist schonmal ganz gut. Wenn noch jemand eine Idee hat wie man das ganze beschleunigen kann, nur zu!

 

[Marco13]

Poste ggf. mal den Code. Am besten so, dass man ihn mit Copy&Paste rauskopieren und direkt compilieren und starten kann. Falls das nicht geht, vielleicht die "Kernfunktionen"...

 

[Guest]

hier kannst du dir mal meine ganzen Quellcode anschauen/runterladen: java3dLite.java

Momentan habe ich nur die testFunktion(D2Polygon testPolygon, Color color) auf die schnellere Berechnung umgestellt. Ansonsten ist die testFunktion erstmal nur zum ausprobieren, später soll der Code in die D3Kamera.render(Graphics g) übernommen werden.

 

[Schreiberling]

sorry, die beiden letzten beiträge sind natürlich von mir, hab vergessen mich einzulogen.

 

[Marco13]

Wo-ho :shock: OK.

Klassennamen schreibt man Groß, Variablen- und Methodennamen klein und ohne Unterstrich. Kommentare würden auch helfen... Insbesondere, weil sowas wie "triangleType.threeEckpunkte" und "eckpunktRechtsUnten" relativ un-generisch aussehen - aber vielleicht hab' ich das nur nicht genau genug nachvollzogen... Sich für eine Sprache zu entscheiden (Deutsch oder (besser) englisch) wäre vielleicht auch nicht verkehrt.

Aber in bezug auf die Effizienz: Die "testFunktion" nur EINmal auzurufen sagt nicht viel aus. Man sollte dem Just-In-Time-Compiler eine Chance zu geben, den Code zu optimieren - und die "testFunktion" in einer Schleife z.B. 100 mal aufzurufen. Dabei aber beachten, dass (wenn der z-Buffer funktioniert) bei den weiteren Durchläufen "eigentlich" nichts gemacht wird - ggf. müßte man den zwischendrin immer clearen....

Ansonsten ... bei mir sieht die Ausgabe erstmal etwa so aus...

Durchlauf 0 Millisekunden: 19,8573
Durchlauf 1 Millisekunden: 16,2920
Durchlauf 2 Millisekunden: 14,2714
Durchlauf 3 Millisekunden: 13,3453
...
Durchlauf 98 Millisekunden: 12,3499
Durchlauf 99 Millisekunden: 12,2602

Wenn in der setRGB die Zeitmessung (nur die Messung!) rausnimmt muss NICHT mehr zig-tausend mal pro Dreieck "System.nanoTime()" aufgerufen werden. Diese Methode ist für das Messen größerer Zeiträume vielleicht OK, aber für so eine winzuge, extrem oft aufgerufen Funktion eher ungeeignet: Erstens stößt bei dem Versuch, die Ausführungszeit von 2 oder 3 Codezeilen zu messen schon der Windows-Interne Timer an seine Grenzen, und zweitens benötigt diese Methode ja SELBST Zeit - und (im Vergleich zum Rest in setRGB) nicht zu knapp!!!

Wenn man die System.nanoTimes aus der setRGB rausnimmt, sieht die Ausgabe bei mir dann so aus...

Durchlauf 0 Millisekunden: 8,7525
Durchlauf 1 Millisekunden: 0,9127
Durchlauf 2 Millisekunden: 0,6560
Durchlauf 3 Millisekunden: 0,6425
Durchlauf 4 Millisekunden: 0,6445
Durchlauf 5 Millisekunden: 0,4618
Durchlauf 6 Millisekunden: 0,4559
...
Durchlauf 71 Millisekunden: 0,4556
Durchlauf 72 Millisekunden: 0,4732 // Hier gibt sich der Just-In-Time-Compiler...
Durchlauf 73 Millisekunden: 0,1629 //  noch mal ein bißchen Mühe :-)
Durchlauf 74 Millisekunden: 0,0715
Durchlauf 75 Millisekunden: 0,0718
...
Durchlauf 99 Millisekunden: 0,0751

... und das ist ja dann schon nicht schlecht.


Allgemein: Solche "Micro-Benchmarks" sind ziemlich schwierig vernünftig hinzukriegen. Für eine grobe Einordnung KÖNNEN sie OK sein, aber eine der möglichen "Pitfalls" hast du ja jetzt gesehen. Wenn man genaue(re) Informationen haben will, sollte man einen Profiler verwenden.

BTW: Wie man die "Kernfunktionen" jetzt noch dramatisch schneller machen könnte, wüßte ich spontan nicht. Man kann zwar noch mit
int imageData[] = ((DataBufferInt)bufferedImage.getRaster().getDataBuffer()).getData();
direkt einen int-Array verwenden und dort dann EINEN int (mit den rgb-Werten) reinschreiben (auch wenn das BufferedImage dadurch unmanaged wird), aber bei einem ersten (ungenauen!) Test hat das im Vergleich zum
getRaster().setPixel(x+m_iXOffset, -y+m_iYOffset, rgb);
nicht viel gebracht - wenn es mal um "viele" Dreiecke geht, könnte man das nochmal testen, aber ich schätze, dass dann auch solche Sachen wie "GetTriangleType" und "GetEckpunktRechtsOben" usw. auf die Performance drücken...

 

[Schreiberling]

Das mit den Stilkonventionen ist so eine Sache. Ich arbeite noch als Werkstudent in einer Firma und versuche mich an deren Konventionen zu halten. Natürlich sollte es dan alles einheitlich sein (insbesondere die gleiche Sprache) da hast du natürlich recht, genau wie mit den Kommentaren.

Das mit der System.nanoTime() war auch nur zum groben messen drinnen, normalerweise habe ich das natürlich auskommentiert (dar es selbst, wie du ja auch sagst, viel Zeit braucht).

Das mit dem Just-In-Time Compiler hab ich nicht gewusst, dan sieht die ganze sache schon wieder ganz anderst aus.

Ich werde jetzt mal versuchen das mit der Dreiecksberechnung noch ein bisschen zu optimieren (vielleicht bekomme ich das auch irgendwie allgemeiner hin als mit den Dreieckstypen) und meinen Code aufzuräumen und zu kommentieren. Danke für deine Hilfe.

Gruss Schreiberling
(und diesmal bin ich eingelogt :wink: )