JLI Spieleprogrammierung

[KI]

Hallo,

Mich würde mal interessieren wie ihr mit dem sogenannten Hidden Surface Removal umgeht.
(HSR bedeutet im Grunde, dass die Ebenen der 3D-Welt, die nicht in das Sichtspektrum des Benutzers fallen, erst garnicht gerendert werden.)

Wenn nämlich immer alle (tausende) Polygone gerendert werden würden, wäre dies sehr unökonomisch und würde das Spiel extrem verlangsamen oder gar unspielbar machen.

Ich beschäftige mich schon seit längerem mit BSP-Trees, die für solche Aufgaben sehr gut geeignet sein sollen.
Link:http://www.gamedev.net/reference/articles/article657.asp

Welchen 3D Editor benutzt ihr, für eure 3D-Welten?
Welches "Map-Format" ist da am besten?
Bei welchen Formaten ist der BSP-Tree integriert.
(Bei manchen 3D-Editoren gibt es ja eine Funktion namens "Compiling the Level")

Ich möchte im Grunde nur Wissen, wie ich "3D-Welten" mit integriertem BSP-Tree (oder ähnlichem) laden kann.

Gibt es da eventuell Open Source Engines?

Bin auf eure Beiträge gespannt.

Euer KI

[Fallen]

Die BSP-Trees werden unter anderem bei der Quake-Engine und Unreal-Engine verwendet, die meisten Engines die Mit dieser Art der Levelarchitektur zu tun haben nutzen BSP. BSP ist meiner Meinung aber nicht geeignet für Levels wo sich alle (oder die meisten) Objekte bewegen da eine Neuberechnung sehr lange dauert.

Der Unrealquellcode soll jetzt frei erhältlich sein (kostenlos). Und die Quake Engine (ka welche Version) auch.

Zum selber machen empfehle ich die Oktanaerbäume (is glaub ich falsch geschrieben) das funktioniert ähnlich wie die BSP-Bäume ist aber leichter zu verstehen und nur etwas langsamer.

Viele Engines nutzen das Quakeformat auch diese die nichts mit Quake zu tun haben. Und der Editor der meist dafür verwendet wird ist der Hammer.
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse."

[Christian Rousselle]

Meinst du Octrees?

[Kampfhund]

Sind BSP-Bäume denn wirklich so gut?

Ich wollte in meiner Engine nämlich statt BSP-Bäumen Portale und Octrees benutzen.

[Fallen]

@Christian: Ja

BSP-Bäume sind wirklich klasse für innen Räume, über Aussenlandschaften hab ich noch nicht viel gehört. Sind aber wirklich hart einzubauen. Wenn du ein RTS game machst brauchst du sowas bestimmt nicht.
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse."

[Fallen]

Kann mir jemad sagen ob diese Methode recht schnell ist (brauche Fremdmeinungen):

[KI]

Wow, eine Leistungssteigerung von 50%!
Das ist auf jeden Fall ein Schritt in die richtige Richtung.

Mich wundert es, dass diese Methode einen solch enormen Performance Vorteil bringt.
Denn in der Zeit, in der die Vertices auf eine Kollision überprüft werden, hätte man sie ja auch zeichnen können.
Denn wenn ich jeden 3D-Punkt in einer großen 3D-Welt auf Kollision mit dem View Frustum überprüfe, kann ich diese genauso gut zeichnen.
Denn das Zeichnen ist ja Hardware beschleunigt.
Kann man das nachvollziehen?

[Christian Rousselle]

@FallenAngel:

Schau dir mal folgendes an:

http://www.flipcode.com/articles/article_frustumculling-pf.shtml

C.

[Fallen]

@KI: ich berechne nur die Position zeichnen tu ich ja nichts, also keine Statechanges und/oder Texturen. Ausserdem will ich das System noch optimieren in dem ich ein Quadtree für die Landschaft erstelle. Ausserdem wird nur Gecullt wenn sich die Camera oder die Landschaft ändert.


@Christian: Ein Quadtree System will ich ja noch einbauen nur gibts da zur Zeit noch einige Probleme bei der Durchführung. Trotzdem Danke für den Artikel werd ihn mir mal genauer anschaun, scheint interessant zu sein.
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse."

[Fallen]

Ich habe nun das Quadtree System bei mir eingebaut. Und setze nun auf die Frustumplanes (die 6 Seiten die meine Sichtbarkeit begrenzen) dazu habe ich Christians link genutzt (super, fast). Nun habe ich aber ein Problem:

Wie kann ich berechnen ob eine Box/Würfel,Raum,... innerhalb meier Frustumplanes ist. Die Möglichkeit das mindestens 1 Punkt meiner Box innerhalb sein muss habe ich. Das alle Punkte ausserhalb sind um nichts anzeigen zu müssen ist nicht gut.

Weil immer noch die Verbindungslinien durch meinen Raum gehen können obwohl alle Punkte ausserhalpb liegen. Die Idee GeradeDurchEbenen tests durchzuführen hatte ich auch schon nur möchte ich gerne erfahren ob es da eine noch schnellere Möglichkeit gibt.

Es gibt bei mir auch noch die Möglichkeit das mein Frustum Raum innerhalb einer Box ist. Somit wären alle Punke ausserhalb und keine Linie würde den Frustum Raum durchqueren. Leider werden dann keinen weiteren und genaueren tests durchgeführt. Was bei einem Quadtree ziemlich schlecht ist.
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse."

[Zyrian]

Eine Frage am Rande:

Wozu werden solche Bäume so generell benutzt? Und aus welchen algorithmischen Elementen besteht so ein Pflänzchen überhaupt?

MFG
#C
_________________
Schau mir in die Augen, Kleines.

[Chewie]

und wie kann es sein, dass Octrees einfacher zu handlen sind als BSP-Trees? Ich dachte das ist dasselbe, nur bei Octrees wird halt ein Knoten in 8 unterteilt, und bei BSP in 2.

[Kampfhund]

Bei einem BSP Tree wird die Geometrie in konvexe Räume unterteilt.
Diese Räume liegen allerdings nur nebeneinander.
Konvexe Räume da man, egal an welcher stelle man sich in dem konvexen raum befindet, beim umsehen die gesammte geometrie des raumes sehen kann. Beim konkaven dagegen nicht. Dort kann es zu überlappungen kommen. Das aufteilen in Konvexe Räume ist hierbei etwas schwierig.

Beim Occtree oder Quadtree wird der Raum in dem die Geometrie liegt mit einer großen box umhüllt.Nun wird geguckt wieviele polygone in der Box liegen. Wenn es mehr als eine bestimmte menge sind dann wird diese Box beim Quadtree in 4(2*2) kleinere boxen und beim Occtree in 8(2*2*2) kleiner boxen unterteilt.Das geht dann immer so weiter.
Der vorteil hierbei ist, dass wenn man weiß dass die umschliesende box nicht im frustrum ist, dann weiß man automatisch dass alle boxen die in ihr liegen auch nicht sichtbar sind.
Wenn die box allerdings zum teil im frustrum liegt, dann überprüft man die childnodes der box(rekursiv).

[Mr.X]

[KI]