Hi,

ich habe eine eigene 3D-Engine geschrieben, um ein eigenes (einfaches) 3D-Spiel zu entwerfen. Bisher klappt alles was mit 3 dimensionalen Ansichten zu tun hat, jedoch kann ich bis jetzt nur Linien darstellen, was für ein Spiel grafisch unangemessen ist. Ich würde jetzt für ein schöneres Aussehen auch gerne Flächen mit einbauen. Das Problem ist allerdings, dass ich herausfinden muss, welches Polygon jeweils (von der Kamera aus gesehen) "vorne" liegt, damit ich weiß in welcher Reihenfolge ich diese zeichnen lasse. Ich weiß nicht, ob es hierfür eine besonders schnelle Rechenmethode gibt, da diese Rechnung vor jeder Bilddarstellung durchgeführt werden muss, sofern ich die Kamera oder die Polygone verschiebe. Einen Denkansatz hätte ich schon, der dauert für den Vergleich zwischen allen Polygonen jedoch relativ lang. (Hinweis: Polygone, die sich schneiden, werden aufgeteilt.)

Meine Überlegung, um bei 2 Polygonen zu überprüfen, welches von der Kamera aus gesehen das "Vordere" ist, also das andere überlappt:
Ich mache aus einem der Polygone (Polygon A) eine Ebene, von der ich den Normalenvektor bestimme. Aus einem der Eckpunkte (Punkt P) von Polygon B und dem Normalenvektor (N) der Ebene von Polygon A, mache ich eine Gerade (g).
g: x = P + r*N
Ich berechne nun den Schnittpunkt der Geraden mit der Ebene von Polygon A und bekomme hierbei einen Wert für den Streckfaktor r der Geraden. Ist der Streckfaktor immer positiv oder immer negativ, so bedeutet das, dass das Polygon B auf einer eindeutigen Seite von Polygon A ist. Befinden sich die Kamera auf der selben Seite von Polygon A aus gesehen, so ist Polygon B (sofern eine Überlappung der beiden Polygone stattfindet) auf jeden Fall vor Polygon A.
Ist der Streckfaktor nicht immer positiv oder immer negativ, dann nehme ich Polygon B als Ebene und überprüfe das Vorzeichen des Streckfaktors zu einem beliebigen Eckpunkt von Polygon A (da in diesem Fall dann alle Streckfaktoren das gleiche Vorzeichen besitzen müssen) und danach gucke ich auf welcher Seite des Polygon B sich die Kamera befindet.

Dieses Vorgehen ist unheimlich rechenaufwändig, da man eine große Menge an Eckpunkten von Polygonen überprüfen muss, um die eindeutige Lageposition herauszufinden. Daher würde mich interessieren, ob es einen CPU-schonenderen Weg gibt um dies zu berechnen. (Hinweise auf Verwendung von OpenGL o.ä. benötige ich hierfür nicht, da dieses Spiel bis auf das Zeichnen von Polygonen und Linien nicht von der Grafikkarte erledigt werden soll.)

Vielen Dank schon mal im Voraus an die Leute die sich bemühen mir zu helfen

Mit freundlichem Gruß
>spEEd>

Schau Dir einmal die Tutorials bei DelphiGL an, dort solltest Du zum Thema Landschaften einige Anregungen finden.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Also erstmal Danke für die schnelle Antwort. Aber die Berechnung der Tiefe von Polygonen im 3 dimensionalen Raum wird hier leider nicht thematisiert (oder ich habe es nur nicht gefunden), da hier immer OpenGl als Grundlage für die Berechnung genutzt wird.

Ich habe allerdings den passenden Artikel zu meinem Problem in Wikipedia gefunden:
de.wikipedia.org/wiki/Sichtbarkeitsproblem

Es gibt hier den Maler-Algorithmus, der anhand der Berschreibung wohl so verfährt, wie ich dies tun würde. Allerdings wird der hier auch als sehr rechenintensiv beschrieben.
"Ein anderes Problem ist, dass der Maleralgorithmus ineffizient ist, weil der Computer die Intensitäten aller Punkte eines Polygons berechnen muss, auch wenn das Polygon in der endgültigen Szene gar nicht sichtbar ist." (Wobei ich vorher testen würde, ob die Polygone sichtbar sind, bevor ich deren Lage zueinander teste.)
Das andere Verfahren, bei dem jeweils die Tiefe der einzelnen Bildpunkte gespeichert wird und das hier als das Verfahren für Grafikkarten genannt wird, habe ich bei meiner ersten Version der 3D-Engine so gemacht. Allerdings musste ich dies aufgeben, da die Berechnung der Tiefe nicht ganz korrekt war und die Rechenzeit für die einzelnen Bilder zu lang wurde, wenn die Bildfläche mit Polygonen voll war.

Ich werde meinen ersten Gedanken zur Tiefenberechnung einfach mal weiterverfolgen und schauen, wie das mit der Rechenzeit dann am Ende aussieht. Falls noch jemand Vorschläge haben sollte, bin ich natürlich gerne offen dafür.
Ansonten erkläre ich vorerst diesen Thread als beantwortet.

>spEEd>

Schau Dir einfach einmal das Tutorial zu den Octrees an, da ist alles benötigte enthalten. Dass die Beschreibung dort mit OpenGL als Grundlage geschieht hängt damit zusammen, dass OpenGL viele Berechnungen (z.B. Face-Sichtbarkeiten) mit unter selber berechnet (bzw. die Tiefen-Berechnung). Teile davon muss man aber mit Octrees auch noch mal selber erledigen (für die Vorsortierung).

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ah, OK. Ich werd mir das mal anschauen. Vielen Dank für den Hinweis!

>spEEd>