Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
KI JLI Master
Alter: 39 Anmeldedatum: 04.07.2003 Beiträge: 965 Wohnort: Aachen Medaillen: Keine
|
Verfasst am: 18.10.2003, 10:18 Titel: Hidden Surface Removal - HSR |
|
|
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 |
|
Nach oben |
|
|
Fallen JLI MVP
Alter: 40 Anmeldedatum: 08.03.2003 Beiträge: 2860 Wohnort: Münster Medaillen: 1 (mehr...)
|
Verfasst am: 18.10.2003, 11:30 Titel: |
|
|
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." |
|
Nach oben |
|
|
Christian Rousselle Site Admin
Alter: 48 Anmeldedatum: 19.07.2002 Beiträge: 1630
Medaillen: Keine
|
Verfasst am: 24.10.2003, 22:40 Titel: |
|
|
Meinst du Octrees? |
|
Nach oben |
|
|
Kampfhund Super JLI'ler
Alter: 42 Anmeldedatum: 20.07.2002 Beiträge: 408
Medaillen: Keine
|
Verfasst am: 25.10.2003, 13:52 Titel: |
|
|
Sind BSP-Bäume denn wirklich so gut?
Ich wollte in meiner Engine nämlich statt BSP-Bäumen Portale und Octrees benutzen. |
|
Nach oben |
|
|
Fallen JLI MVP
Alter: 40 Anmeldedatum: 08.03.2003 Beiträge: 2860 Wohnort: Münster Medaillen: 1 (mehr...)
|
Verfasst am: 25.10.2003, 18:37 Titel: |
|
|
@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." |
|
Nach oben |
|
|
Fallen JLI MVP
Alter: 40 Anmeldedatum: 08.03.2003 Beiträge: 2860 Wohnort: Münster Medaillen: 1 (mehr...)
|
Verfasst am: 26.10.2003, 19:18 Titel: |
|
|
Kann mir jemad sagen ob diese Methode recht schnell ist (brauche Fremdmeinungen):
Code: |
inline bool DFXIsPolyInsideFrustum(D3DVIEWPORT9 *Viewport, D3DXMATRIX *matProject, D3DXMATRIX *matView, D3DXMATRIX *matWorld, D3DXVECTOR3 *v1, D3DXVECTOR3 *v2, D3DXVECTOR3 *v3, float range=0)
{
//check if the 3 vertexes are inside a given frustum
D3DXVECTOR3 p1,p2,p3;
D3DXMATRIX WorldView;
Viewport->X=0;
Viewport->Y=0;
Viewport->MaxZ=0;
Viewport->MinZ=0;
D3DXVec3Project(&p1,v1,Viewport,matProject,matView,matWorld);
D3DXVec3Project(&p2,v2,Viewport,matProject,matView,matWorld);
D3DXVec3Project(&p3,v3,Viewport,matProject,matView,matWorld);
bool bIn=(
((p1.x+range>=0 && p1.x-range<=Viewport->Width) && (p1.y+range>=0 && p1.y-range<=Viewport->Height)) ||
((p2.x+range>=0 && p2.x-range<=Viewport->Width) && (p2.y+range>=0 && p2.y-range<=Viewport->Height)) ||
((p3.x+range>=0 && p3.x-range<=Viewport->Width) && (p3.y+range>=0 && p3.y-range<=Viewport->Height))
);
return bIn;
}
|
Somit habe ich meiner Engine immerhin 50% Leistung geschenkt indem ich diese Technik auf mein Terrain anwende.
Ich berechne einfach ob ein Polygon ganz oder teilweise im Bildschrimbereich liegt. Dazu wird das Polygon auf den Bildschrim projeziert. Danach wird überprüft ob sich die projezierten Polygonpunkte innerhalb der Bilschrimmaße befinden. _________________ "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." |
|
Nach oben |
|
|
KI JLI Master
Alter: 39 Anmeldedatum: 04.07.2003 Beiträge: 965 Wohnort: Aachen Medaillen: Keine
|
Verfasst am: 26.10.2003, 21:03 Titel: |
|
|
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? |
|
Nach oben |
|
|
Christian Rousselle Site Admin
Alter: 48 Anmeldedatum: 19.07.2002 Beiträge: 1630
Medaillen: Keine
|
|
Nach oben |
|
|
Fallen JLI MVP
Alter: 40 Anmeldedatum: 08.03.2003 Beiträge: 2860 Wohnort: Münster Medaillen: 1 (mehr...)
|
Verfasst am: 27.10.2003, 09:00 Titel: |
|
|
@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." |
|
Nach oben |
|
|
Fallen JLI MVP
Alter: 40 Anmeldedatum: 08.03.2003 Beiträge: 2860 Wohnort: Münster Medaillen: 1 (mehr...)
|
Verfasst am: 29.11.2003, 19:07 Titel: |
|
|
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." |
|
Nach oben |
|
|
Zyrian Super JLI'ler
Anmeldedatum: 30.08.2003 Beiträge: 321 Wohnort: Essen Medaillen: Keine
|
Verfasst am: 29.11.2003, 20:34 Titel: |
|
|
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. |
|
Nach oben |
|
|
Chewie Super JLI'ler
Anmeldedatum: 17.07.2003 Beiträge: 382
Medaillen: Keine
|
Verfasst am: 29.11.2003, 21:36 Titel: |
|
|
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. |
|
Nach oben |
|
|
Kampfhund Super JLI'ler
Alter: 42 Anmeldedatum: 20.07.2002 Beiträge: 408
Medaillen: Keine
|
Verfasst am: 29.11.2003, 21:45 Titel: |
|
|
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). |
|
Nach oben |
|
|
Mr.X Junior JLI'ler
Anmeldedatum: 15.04.2003 Beiträge: 88
Medaillen: Keine
|
Verfasst am: 29.11.2003, 22:00 Titel: |
|
|
Zyrian hat Folgendes geschrieben: | ...Wozu werden solche Bäume so generell benutzt... |
Zur Suchoptimierung in Datenbeständen/-banken. Ist das weitaus größte Anwendungsgebiet für gerichtete Graphen.
Chewie hat Folgendes geschrieben: | ...Ich dachte das ist dasselbe, nur bei Octrees wird halt ein Knoten in 8 unterteilt, und bei BSP in 2.... |
Du liegst richtig
Die Handhabung, welche Du anspricht, bezieht sich dabei eher auf den speziellen Anwendungsfall und hat mit dem Baum an sich nichts mehr zu tun.
Anzumerken wäre höchstens, das ein Octree mehr in die Breite wächst, während der BSP-Tree mehr in die Tiefe wächst, wodurch der längste Weg beim Octree natürlich kürzer ist. Vielleicht war es das was du als einfacher (eventuell schnellere) Handhabung aufgefasst hast. |
|
Nach oben |
|
|
KI JLI Master
Alter: 39 Anmeldedatum: 04.07.2003 Beiträge: 965 Wohnort: Aachen Medaillen: Keine
|
Verfasst am: 30.11.2003, 01:09 Titel: |
|
|
Kampfhund hat Folgendes geschrieben: | Sind BSP-Bäume denn wirklich so gut?
Ich wollte in meiner Engine nämlich statt BSP-Bäumen Portale und Octrees benutzen. |
BSP-Trees sind schon ziemlich gut.
BSP-Bäume werden nämlich auch in Verbindung mit Portalen und den sogenannten PVS (Potentially Visible Sets) benutzt.
Es gibt außerdem unterschiedliche Arten von BSP-Trees:
Node-Trees, Leaf-Trees und Solid-Trees.
Mit der BSP-Tree Technik kann man auch Octrees simulieren. So gesehen sind BSP-Trees eine Weiterentwicklung.
Zuletzt bearbeitet von KI am 30.11.2003, 01:23, insgesamt 3-mal bearbeitet |
|
Nach oben |
|
|
|