Aufwandsabschätzung und Ablauf Erstellung 3D-Szene

[Benja]

Hi

Ich möchte gern anhand eines simplen Beispiels eine Abschätzung machen wie aufwändig es ist, eine 3D-Szene zu erstellen. Hier steht jetzt NICHT die Technik und auch nicht der Aufbu wie es intern gemacht wird zur Frage sondern die Frage
"Wieviele Operationen sind nötig um 1 Dreieck von der Erstellung aus 3 Punkten auf dem Bildschirm anzuzeigen?"
Das soll natürlich nur ne grobe Abschätzung sein. Genauer geht es eh nicht (denke ich). Die Größenordnung wäre halt interessant zu wissen.

Ist dieser Ansatz hier korrekt oder ist der falsch ?

1 Erstelle ein Dreieck
2 Skaliere es mit Faktor m (größer oder kleiner)
3 Transformiere in „World Space“ (Dabei:
a Drehe es um a° um x-Achse, um b° um y-Achse, um c° um z-Achse
b Verschiebe es an Koordinate (x, y, z) bzw. Verschiebe es um x nach rechts, y nach oben, z nach hinten
4 Lege eine (oder mehrere) Textur(en) aus dem lokalen Speicher darüber
5 schicke es durch ein Raster und berechne, welche Bildschirmpunkte von ihm gefüllt werden
6 Teste, ob das Dreieck überhaupt sichtbar ist (über z-Buffer und Vergleich anderer Bildpunkte)

Berechne das nächste Dreieck

--

Ich bin bisher soweit:

1 9 direkte Wertzuweisungen (dabei nehme ich an, daß ein Punkt der Ursprung ist, einer auf einer der Achsen liegt und nur der 3. Punkt von Null verschiedene Koorsinaten hat)
2 Nullpunkt bleibt unverändert, Punkt auf Achse wird mit m multipliziert (3 Operationen), Punkt außerhalb sind auch 3 Operationen (irgendwie)
3a Pro Drehung und Punkt 9 Operationen (Vektor_neu = Drehmatrix * Vektor_alt)
-> 3*3*9 = 81 Rechenoperationen
3b Pro Punkt 3 Operationen (Vektor_neu = Vektor_alt + Verschiebungsvektor)
-> 3*3 = 9 Operationen
4 ?
5 ?
6 1 Vergleichsoperation

3+3+81+9 = 86 Operationen

Oder sind diese ganzen Dinge total falsch ?


Ich weiß, daß ich z.Z. hier mit vielen Fragen nerve :) Ich hoffe, das ihr dennoch ne kurze Antwort geben könnt...

Vielen Dank schonmal.

Gruß,
Benja

[Demirug]

Die Frage ist schwer zu beantworten. Die Grösse des Dreicks auf dem Bildschirm spielt dabei eine ganz wichtige Rolle.

Zudem gibt es für die meisten Probleme mehr als eine Lösung die unterschiedlich aufwendig sind.

Am einfachten ist noch das ermitteln der Bildschirmposition eines Dreieckseckpunkts. Egal was man alles benötigt (Skalieren, Verschieben, Rotieren) man braucht immer nur eine Multiplikation des Positions-Vektors mit einer 4*4 Matrix.

Wenn es dann aber um die Rasterisierung und die Pixelverarbeitung geht wird es kompliziert. Da macht jeder was anderes.

[zeckensack]

2 Skaliere es mit Faktor m (größer oder kleiner)
3 Transformiere in „World Space“ (Dabei:
a Drehe es um a° um x-Achse, um b° um y-Achse, um c° um z-Achse
Möglich, aber nicht flexibel genug. Google mal nach "gimbal lock".
Das macht man in der Praxis mit einer 4x4-Matrix (homogene Koordinaten).

Btw ist der korrekte Terminus IMO "Transformation von object space nach eye space". "world space" ist eine Zwischenstation auf diesem Weg, das braucht man aber nicht zu berechnen, man kann hier einfach die beiden entsprechenden Matrizen zu einer einzigen zusammenmultiplizieren.

Homogene Koordinaten sind auch quasi Pflicht für korrektes Texturieren.

Um's mit OpenGL-Termini zu halten, nach Division durch w bekommst du die Koordinaten in clip space (ein Quader; eye space ist ein Frustum).

Das alles wäre wesentlich einfacher, wenn du nicht auf Texturen achten müsstest :)

4 Lege eine (oder mehrere) Textur(en) aus dem lokalen Speicher darüber
5 schicke es durch ein Raster und berechne, welche Bildschirmpunkte von ihm gefüllt werden
Die Reihenfolge ist nicht sinnvoll. Texturieren erfolgt auf Pixel-Ebene (bzw Fragment-Ebene). Die Zuweisung der Texturkoordinaten erfolgt auf Vertex-Ebene, und unterliegt einer Interpolation.
Dh die passenden Sample-Positionen aus der Textur kann man erst wissen, wenn man das Dreieck in Pixel zerlegt, und die Interpolation ausgeführt hat.

[Benja]

wenn ich etwas zur leistungsfähigkeit von GPUs sagen muß und auch auf irgendeine art und weise etwas dazu vorrechnen bzw dimensionen abstecken muß - wie mache ich das dann am besten ?
voraussetzungen der hörerschaft: mehr oder weniger null

also muß es nicht 100% der wirklichkeit entsprechen sondern muß eher nachvollziehbar sein und soll auch bissel aufzeigen, was denn so passiert

-

anderes thema: homogenen Komponente

Offengestanden habe ich den Sinn da nicht wirklich verstanden - deswegen wollte ich das weglassen in meiner Berechnung ;) bisher habe ich dazu nur auf www.3dsource.de was gefunden - und wirklich geholfen hat mir das nicht.
Letztendlich sind die 4x4-Matrizen die man für Berechnungen nutzt ja auch 3x3 Matrizen da bis auf die Komponente 44 (unten rechts) die Komponenen der 4. Zeile & Spalte scheinbar immer 0 sind.

@zeckensack: wenn ich das alle mit EINER Matrixmultiplikation mache - die matrix muß ich vorher aber berechnen, oder ? wenn ja - wo wird das dann gemacht ?

[Demirug]

Original geschrieben von Benja
wenn ich etwas zur leistungsfähigkeit von GPUs sagen muß und auch auf irgendeine art und weise etwas dazu vorrechnen bzw dimensionen abstecken muß - wie mache ich das dann am besten ?
voraussetzungen der hörerschaft: mehr oder weniger null

also muß es nicht 100% der wirklichkeit entsprechen sondern muß eher nachvollziehbar sein und soll auch bissel aufzeigen, was denn so passiert

Vertexdurchsatz, Fillrate, ...

anderes thema: homogenen Komponente

Offengestanden habe ich den Sinn da nicht wirklich verstanden - deswegen wollte ich das weglassen in meiner Berechnung ;) bisher habe ich dazu nur auf www.3dsource.de was gefunden - und wirklich geholfen hat mir das nicht.
Letztendlich sind die 4x4-Matrizen die man für Berechnungen nutzt ja auch 3x3 Matrizen da bis auf die Komponente 44 (unten rechts) die Komponenen der 4. Zeile & Spalte scheinbar immer 0 sind.

Spalte Ja, Zeile Nein. Wobei man auch die 4 Spalte nutzen kann. Es muss aber einen 4*4 Matrix sein weil sonst eine Matrix Matrix Multiplikation nicht mehr so richtig funktionieren würde. Man kann die Kenntniss das an bestimmen Stellen nullen oder eines sind natürlich ausnutzen.

@zeckensack: wenn ich das alle mit EINER Matrixmultiplikation mache - die matrix muß ich vorher aber berechnen, oder ? wenn ja - wo wird das dann gemacht ?

Mit der CPU verrechnet man die einzelnen Matrixen. Ist ja nur einmal pro Objekt notwendig.

[Benja]

vertexdurchsatz, fillrate usw sind (sofern man infos dazu findet)ja nur "abstrakte zahlen" - ich würde halt gern zeigen, wie sich das zusammensetzt :)

-

Zur Sicherheit folgende Frage:
Die (nennen wir sie mal so) 4x4-Gesamtmanipulationsmatrix wird also in der CPU - nicht in der GPU - berechnet ?
Hast du zwar geschrieben aber da will ich schon auf Nummer sicher gehen. :)

[zeckensack]

Original geschrieben von Benja
anderes thema: homogenen Komponente

Offengestanden habe ich den Sinn da nicht wirklich verstanden - deswegen wollte ich das weglassen in meiner Berechnung ;) bisher habe ich dazu nur auf www.3dsource.de was gefunden - und wirklich geholfen hat mir das nicht.
Letztendlich sind die 4x4-Matrizen die man für Berechnungen nutzt ja auch 3x3 Matrizen da bis auf die Komponente 44 (unten rechts) die Komponenen der 4. Zeile & Spalte scheinbar immer 0 sind.Dann wäre es in der Tat überflüssig ;)
Ein 3D-Eckpunkt wird in eine homogene Koordinate umgewandelt, indem man w:=1 setzt. Die vierte Spalte der Matrix kann dadurch für Verschiebungen genutzt werden. Rotation kriegt man im oberen 3x3-Quadranten.
Das 'neue' W ergibt sich durch die vierte Zeile der Matrix. Das braucht man nicht nur für perspektiv-korrigierte Interpolation der Parameter, sondern eben auch für die Perspektive selbst (ie Objekte werden 'automatisch' kleiner, wenn sie weiter 'hinten' sind; setzt natürlich eine anschließende Division der Komponenten durch w voraus). Das kann man alles in diese eine Matrix stopfen.

Die Perspektive kann man naiv betrachtet auch direkt über eine von Z abhängige Skalierung lösen, das funktioniert aber nicht mehr, wenn die 'Kamera-Achse' gedreht ist.
@zeckensack: wenn ich das alle mit EINER Matrixmultiplikation mache - die matrix muß ich vorher aber berechnen, oder ? wenn ja - wo wird das dann gemacht ? Das kann man so pauschal nicht beantworten :)
Ein Chip könnte die Matrizen in Hardware verwalten, und kombinieren sobald sich eine 'Teilmatrix' verändert. Da das idR nicht oft (pro Frame) passiert, ist es meist ausreichend, das in Software zu lösen.

Wie genau das nun implementiert ist, ist IMO nicht wirklich wichtig (und wird von den gängigen Grafik-APIs auch nicht vorgeschrieben).

Die Kombination der Matrizen bringt trotzdem große Vorteile. GL definiert zwei seperate Matrix-Transformationen pro Eckpunkt (modelview und projection), DX Graphics definiert drei (AFAIR wold, view, projection).

Vektor*Matrix sind 16 MULs und 12 ADDs (oder 4 Skalarprodukte). Es sollte einleuchten, daß man hier recht einfach viel Rechenleistung sparen kann :)

[Benja]

okay, Zusammenfassung:

Meine Idee ist nicht umzusetzen.

Ich werde dann eher auf der Schiene reden:
"Eine 3D-Szene besteht aus x Objekten. Jedes Objet besteht aus y (y >>x) Primitiven (Dreiecken). Diese Objekte kann man manipullieren (drehen, verschieben, skallieren), was recht einfach über eine Multiplikation der einzelnen Eckpunkte mit einer 4x4 Matrix gemacht werden kann. Man legt Texturen drüber usw usw ...


-----

Was ich eigentlich überhaupt denen denen ich was erzählen will/soll verdeutlichen möchte, ist, wie kompliziert die Vorgänge bei 3D sind und wie toll GPUs sind :)

Vielleicht habt ihr dazu ja nen Vorschlag/Link o.ä. ?

[Xmas]

Original geschrieben von Benja
Ich werde dann eher auf der Schiene reden:
"Eine 3D-Szene besteht aus x Objekten. Jedes Objet besteht aus y (y >>x) Primitiven (Dreiecken).
x und y haben hier gar keinen direkten Zusammenhang. Du kannst eine Szene haben, die aus 1000 simplen Würfeln besteht, oder eine die aus 3 Objekten mit je 50000 Polygonen besteht.

[Benja]

schon klar - aber ich muß ja irgendwas sagen.
ich suche dann mal, ob man da typische zahlen für pc-spiele finden kann.
das das direkt nichts miteinander zu tun hat ist klar :)

[Benja]

Original geschrieben von zeckensack
Dann wäre es in der Tat überflüssig ;)
Ein 3D-Eckpunkt wird in eine homogene Koordinate umgewandelt, indem man w:=1 setzt. Die vierte Spalte der Matrix kann dadurch für Verschiebungen genutzt werden.
Verschiebung inwiefern ? Ich dachte, dazu reicht auch der obere 3x3 Quadrant ... ?
Das 'neue' W ergibt sich durch die vierte Zeile der Matrix. Das braucht man nicht nur für perspektiv-korrigierte Interpolation der Parameter, sondern eben auch für die Perspektive selbst (die Objekte werden 'automatisch' kleiner, wenn sie weiter 'hinten' sind; setzt natürlich eine anschließende Division der Komponenten durch w voraus). Das kann man alles in diese eine Matrix stopfen.
Okay, harter Brocken - aber ich verstehe was gemacht wird. Wie noch nicht ;)

Ein Chip könnte die Matrizen in Hardware verwalten, und kombinieren sobald sich eine 'Teilmatrix' verändert. Da das idR nicht oft (pro Frame) passiert, ist es meist ausreichend, das in Software zu lösen.
Hauptfrage
Vorweg: Ich kenne mich in 3D-Programmierung leider nicht aus.
Ich habe mir das bisher so vorgestellt:
Ich gehe von statischen Objekten aus (also keine Menschen die ihre Beine bewegen).
Man programmiert ein Objekt. z.B. ein Haus mit Tür, Fenster, Mauerwekr, Dach, Schornstein, Hausnummer usw...
Dies besteht aus vielen vielen Dreiecken. Man instanziert dieses Objekt und kann dann jederzeit auf das ganze Objekt Operationen durchführen. Also "drehe Haus1 90° rechts". Drehen, Kippen, Skallieren, usw. als Mögliche Operationen.
Das wird dann von der Programmiersprache intern so umgerechnet, daß die Hardware über die Treiber die Daten so bekommt um auf jedem der Dreiecke des Objekts diese Operation auszuführen.
Ist das jetzt totaler Bullshit oder ungefähr die richtige Richtung ?

Vektor*Matrix sind 16 MULs und 12 ADDs (oder 4 Skalarprodukte). Es sollte einleuchten, daß man hier recht einfach viel Rechenleistung sparen kann :)
Jo, leuchtet ein. Aber ich will zeigen wie toll die aktuellen GPUs sind :D Da kommen große Zahlen besser als kleine.

Hintergrund der ganzen Geschichte ist übrigens immernoch:
http://www.forum-3dcenter.org/vbulletin/showthread.php?s=&threadid=93308
Und die logische Ebene reicht - das ist schon kompliziert genug und mehr Infos kriegt man eh nicht.

[Demirug]

Original geschrieben von Benja
Hauptfrage
Vorweg: Ich kenne mich in 3D-Programmierung leider nicht aus.
Ich habe mir das bisher so vorgestellt:
Ich gehe von statischen Objekten aus (also keine Menschen die ihre Beine bewegen).
Man programmiert ein Objekt. z.B. ein Haus mit Tür, Fenster, Mauerwekr, Dach, Schornstein, Hausnummer usw...
Dies besteht aus vielen vielen Dreiecken. Man instanziert dieses Objekt und kann dann jederzeit auf das ganze Objekt Operationen durchführen. Also "drehe Haus1 90° rechts". Drehen, Kippen, Skallieren, usw. als Mögliche Operationen.
Das wird dann von der Programmiersprache intern so umgerechnet, daß die Hardware über die Treiber die Daten so bekommt um auf jedem der Dreiecke des Objekts diese Operation auszuführen.
Ist das jetzt totaler Bullshit oder ungefähr die richtige Richtung ?

Ja, im wesentlichen stimmt das schon.

Die Grafikkarte bekommt Objekte in Form von Vertexinformationen übergeben. Diese Informationen enthalten mindestens eine Position im Objekt space. Zusätzlich zu den Eckpunkten muss man der Grafikkarte noch mitteilen wie aus diesen Dreiecken zu bilden sind. Eine Möglichkeit dazu wäre aus jeweils drei aufeinader folgenden Eckpunkten ein Dreieck zu erzeugen.

Das Vertexprogramm enthält dann die Informationen was mit jedem Vertex passieren soll bevor daraus Dreiecke gebildet werden. Bei den neuen Karten kann man dafür richtige kleine Programme schreiben bei den älteren HT&L Karten aus einer vorgegeben Anzahl von Optionen wählen. Bezüglich der Position gibt man bei den HT&L Karten die Transformationsmatrixen an um die Position von einem Bezugraum in einen anderen zu überführen. Objectspace -> Worldspace -> Viewspace. Intern kann man diese ganzen Matrixen zu einer Verbinden und so die gesamten Transformationen auf einmal durchführen.

[Benja]

Das hat mir schonmal sehr geholfen. Danke !
Ich geb mal einen aus wenn ich fertig bin mit fragen.

Zum Verständnis:
zweidimensionales Beispiel:

(0,0) (4,0) (4,3) <- Dreieck 1 Eckpunkte
(0,0) (4,3) (0,3) <- Dreieck 2 Eckpunkte
(0,3) (4,3) (2,6) <- Dreieck 3 Eckpunkte

Das könnte man dann als Haus mit Dach interpretieren ? Also, Geometrisch, ohne Texturen usw...

Weil dann könnte ich das schön an diesem Beispiel zeigen und dann sagen "So, Leute, und für 3D funktioniert das genauso nur komplizierter" :)

Die von dir angesprochenen kleinen Programme sind dann je nach Karte in Assembler-linke Vertex Shader 1.x oder 2.0 bzw (für ganz tolle mit mehr Komfort und mehr Funktionen) auch in Cg ... ?

[Demirug]

Original geschrieben von Benja
Das hat mir schonmal sehr geholfen. Danke !
Ich geb mal einen aus wenn ich fertig bin mit fragen.

Zum Verständnis:
zweidimensionales Beispiel:

(0,0) (4,0) (4,3) <- Dreieck 1 Eckpunkte
(0,0) (4,3) (0,3) <- Dreieck 2 Eckpunkte
(0,3) (4,3) (2,6) <- Dreieck 3 Eckpunkte

Das könnte man dann als Haus mit Dach interpretieren ? Also, Geometrisch, ohne Texturen usw...

Weil dann könnte ich das schön an diesem Beispiel zeigen und dann sagen "So, Leute, und für 3D funktioniert das genauso nur komplizierter" :)

Ja, im 3d Raum hat man eben noch zusätzlich eine Z-Koordinate.

Die von dir angesprochenen kleinen Programme sind dann je nach Karte in Assembler-linke Vertex Shader 1.x oder 2.0 bzw (für ganz tolle mit mehr Komfort und mehr Funktionen) auch in Cg ... ?

oder HLSL bzw glslang (für die OpenGL Seite).

[zeckensack]

Original geschrieben von Benja
Verschiebung inwiefern ? Ich dachte, dazu reicht auch der obere 3x3 Quadrant ... ?Nein. Mit dem 3x3-Quadranten oben links lassen sich (entsprechend einer 3x3-Matrix) nur Rotationen und Skalierungen darstellen.

Mal ein paar Beispiele zu Vektor*Matrix:
Identität
(1) (1 0 0 0 ) (1*1) (1)
(2) X (0 1 0 0 ) = (2*1) = (2)
(3) (0 0 1 0 ) (3*1) (3)
(1) (0 0 0 1 ) (1*1) (1)

Skalierung
(1) (2 0 0 0 ) (1*2) (2)
(2) X (0 2 0 0 ) = (2*2) = (4)
(3) (0 0 2 0 ) (3*2) (6)
(1) (0 0 0 1 ) (1*1) (1)

Verschiebung
(1) (1 0 0 2 ) (1*1+2*1) (3)
(2) X (0 1 0 2 ) = (2*1+2*1) = (4)
(3) (0 0 1 2 ) (3*1+2*1) (5)
(1) (0 0 0 1 ) ( 1*1) (1)

Rotation 90° im Gegenuhrzeigersinn (um die Z-Achse)
(1) (0 -1 0 0) (2*-1) (-2)
(2) X (1 0 0 0) = (1* 1) = ( 1)
(3) (0 0 1 0) (3* 1) ( 3)
(1) (0 0 0 1) (1* 1) ( 1)

Rotation, Skalierung und Verschiebung
(1) (0 -2 0 4 ) (2*-2+1*4) ( 0)
(2) X (2 0 0 5 ) = (1* 2+1*5) = ( 7)
(3) (0 0 2 6 ) (3* 2+1*6) (12)
(1) (0 0 0 1 ) ( 1*1) ( 1)

Ich hoffe mal, daß das alles so stimmt :)

Hauptfrage
Vorweg: Ich kenne mich in 3D-Programmierung leider nicht aus.
Ich habe mir das bisher so vorgestellt:
Ich gehe von statischen Objekten aus (also keine Menschen die ihre Beine bewegen).
Man programmiert ein Objekt. z.B. ein Haus mit Tür, Fenster, Mauerwekr, Dach, Schornstein, Hausnummer usw...
Dies besteht aus vielen vielen Dreiecken. Man instanziert dieses Objekt und kann dann jederzeit auf das ganze Objekt Operationen durchführen. Also "drehe Haus1 90° rechts". Drehen, Kippen, Skallieren, usw. als Mögliche Operationen.
Das wird dann von der Programmiersprache intern so umgerechnet, daß die Hardware über die Treiber die Daten so bekommt um auf jedem der Dreiecke des Objekts diese Operation auszuführen.In weiten Teilen: siehe Demirug. Ich will's auch nochmal ausführen, vielleicht hilft's ja wenn du mehrere Perspektiven hast ;)

Ein starres Objekt wie dein Haus liegt erstmal als Satz von Eckpunkten vor, bezogen auf ein eigenes Koordinatensystem ("Haustürklingel:=(0;0;0)"). Wenn man das ganze jetzt um 90° drehen will, dann macht man das idR* nicht so, daß man die Koordinaten des Objekts im Speicher verändert, sondern man verändert die passende Transformationsmatrix. Dadurch werden dann alle Eckpunkte die man der Grafik-API übergibt dieser Transformation "on the fly" unterzogen, und damit eben das komplette Objekt. Die Transformierten Eckpunkte braucht man jedenfalls nirgends abzuspeichern.

Beim nächsten Objekt muß man dann wieder schauen. Wenn das Bezugssystem das gleiche ist (zB der Gartenzaun, der sich hoffentlich nicht relativ zum Haus gesehen bewegt), dann lässt man die Transformationsmatrix so wie sie ist, und übergibt das Objekt.

Wenn nicht (vorbeifahrendes Auto), dann muß man die Matrix wieder anpassen, und übergibt dann das Objekt, etc.

*die Software kann die Transformation auch selbst erledigen, sollte dann aber die Matrizen in Ruhe lassen. Die Identitätsmatrix hochladen wäre eine gute Idee.
Spiele aus der Software-T&L-Ära mussten das noch tun, heutzutage ist man mit HW-T&L besser bedient.
Bei nicht-starren Objekten (Pferde, Igel ...), wird's schon wieder kompliziert :)

[Benja]

Hi schonwieder.

Kann mir jemand ne beispielhafte Zahl nennen, aus wievielen Dreiecken so eine Szene in einem 3D-Shooter besteht ?
Die Größenordnung ist entscheidend. Die genaue Zahl eher unwichtig.
Sind es eher 10^3, 10^6, 10^9 ?

[Aquaschaf]

Ganz grob geschätzt 10^4 bis 10^5 Tri's würde ich sagen, differiert natürlich je nachdem welches Spiel man betrachtet.

[Benja]

Sorry, ich muß nochmal doof nachfragen:

Objectspace -> Worldspace -> Viewspace. Intern kann man diese ganzen Matrixen zu einer Verbinden und so die gesamten Transformationen auf einmal durchführen.

Das passiert dann alles in einem Schritt ?

Oder werden erst die ganzen Manipulationen am Objekt gemacht bevor es in andere "Spaces" umgerechnet wird ?

---


Ganz anderes Thema:
Zu den Geometrie-Abläufen kann ich ja schon bissel was schreiben und vorrechnen.

Aber wie is n das bei den Pixel-Shadern bzw bei Texturen usw ? Da würd ich auch gern bissel schreiben was da so an Rechenpower im Hintergrund steht.

Zum Verständnis:
Die Objete im World-Space werden mit Texturen, Effekten usw belegt und danach erfolgt erst die Transformtion in den View-Space ? Oder passiert die Transformation in den View Space auh schon vorher ?

-
Falls ich hier jetzt was doppelt gefragt habe sorry, ich kann grad nichtmehr genau denken und das fällt mir grad noch so ein an Fragen die ich habe :)