3. Frage:

Was ist ein BSPTree ?

www.d3opencoop.com - A Doom3 Cooperative Mod

Ein BSP Tree wird verwendet um "Maps" in manchen Game Engines zu "speichern" und anschließend zu rendern.
Dabei werden Polygone eben in einem Tree Model gespeichert, sprich ein Polygon A unterteilt einen Raum und auf der einen Hälfte ist das Polygon B und B² und auf der anderen das Polygon C und C². Das hat den Vorteil dass nicht alles berechnet werden muss sondern nur das was gerade gesehen wird, wie im Beispiel wenn man auf der Seite mit den C Polies steht müssen die B's net berechnet werden.
Wie kann mans zusammenfassen in Worten? Hmm ein BSPTree ist ein Format das Polygone in einem Tree enthält die dann später in einer Engine gerendert werden. (oder so ähnlich =)

menno, die war leicht, was musst du Sau aber auch so schnell sein ;) ?

War doch ausführlich genug, oder?

Nihil timeo, nulla re opprimor, nulli periculo cedo.
www.TheDoenerKing.de

Nicht der Schnellste, sondern die beste Erklärung wird bewertet.

www.d3opencoop.com - A Doom3 Cooperative Mod

Der BSP-Tree (Binary Space Partition) :
Mit diesem Baum wird eine Karte rekursiv in Halbräume aufgeteilt. Daher der Name "Binary Space"! Bei jedem Zeichenschritt wird also eine binärere Baumstruktur abgearbeitet. Der Knoten eines solchen Baums ist eine Kante (math. Gerade). Diese Kante teilt die restliche Karte wieder in zwei Halbräume auf. Die Unterteilung in Halbräume ist genau dann zu Ende, wenn alle Kanten des Halbraumes konvex angeordnet sind (= Blattknoten, mit 1-n Kanten).
Die Durchlaufrichtung des Baumes verläuft wie folgt:

Gehe in den Halbraum, in dem sich die Figur befindet (rekursiv)
wenn die Figur auf der "rechten" Seite der Kante ist, zeichne die Kante

Gehe in den Halbraum, der von der Figur abgewandt ist

Für den Fall daß der Knoten ein Blatt ist, zeichne alle "rechten" Kanten.

xreal
mfg cnuke

@cnuke: http://rfhs8012.fh-regensburg.de/~saj39122/feld/demo/BSPintroduction.html

"[...] you're going to burn in a very special level of Hell. A level they reserve for child molesters and people who talk at the theater." - Book

tja, ich hab keine ahnung (hab ich sowieso nicht)

DMC-INTERACTIVE

Tactical Espionage Action - SuperSteve
- decies Half-Life Adventure Interface (HL-AI)

@cnuke: Leider gilt das nur für 2D BspTrees :-) (Doom)
Wir reden hier aber von der Half-Life Engine...

www.d3opencoop.com - A Doom3 Cooperative Mod

:D
woher soll ich das denn wissen *g*
hab einfach mal gegoogelt :D

is ein interessantes thema.
sollte mich damit mal aus einander setzen...

---
wieso läuft leaf thread eigentlich schon 2std ?!
alda was hab ich da fürn nen bock mist gebaut...

ich google derweil mal weiter :/

xreal
mfg cnuke

Zitat:

Nicht der Schnellste, sondern die beste Erklärung wird bewertet.

Na, dann will ich auch mal versuchen - here it comes:

BSP (Binary Space Partition) Bäume sind eine Methode um Ebenen (hier faces) in einer baumartigen Struktur zu ordnen um beispielsweise das HSR-System zu beschleuningen oder für Kollisionstests. Ein BSP (Binary Space Partitioning)-Tree stellt ein Level dar, indem er es in Nodes zerteilt. Ein Node wird durch folgende Dinge definiert:
- die Hyperplane (die Ebene an der das Level aufgeteilt wird)
- die Polygone die auf der Hyperplane liegen
- ein Verweise auf den Node der hinter der Hyperplane liegt und einer auf den Node der vor der Hyperplane liegt

Von einem Root-Node aus wird nun das ganze Level so lange in Nodes zerteilt, bis alle Polygone irgendwo auf Hyperplanes liegen. Die Leafs liegen zwischen den Hyperplanes.
Ausgehend von dieser Wurzelebene (sprich Root) wird also der gesamte Raum in zwei Teile geteilt. Alle Ebenen im Raum die sich zur Linken der Wurzel befinden werden im Strukturbaum in die linke Seite eingetragen, und die zur Rechten in die rechte. Wenn eine Ebene durch beide Hälften verläuft, wird sie aufgeteilt und beiden Seiten zugeordnet. Nun wird in jeder Hälfte wieder eine Unterwurzelebene bestimmt und das ganze Verfahren wird wieder auf diese beiden Wurzeln angewendet. Dies passiert so lange bis ein bestimmtes Kriterium erfüllt ist (maximale Verästelung, maximale Anzahl von Ebenen).

(bitte nicht verraten, wo das her ist *g*)

Nihil timeo, nulla re opprimor, nulli periculo cedo.
www.TheDoenerKing.de

Menno ihr alten abschreiber =)
Das hätt ich auch machen können! ;)

@Fraghunter: Ich kenn den Thread. Beitrag von Prefect. ;)

"[...] you're going to burn in a very special level of Hell. A level they reserve for child molesters and people who talk at the theater." - Book

Ok, das war jetzt bisher die beste Erklärung (außer einem kleinen Fehler). Wer liefert jetzt noch die Anschaulichste ?

www.d3opencoop.com - A Doom3 Cooperative Mod

Frage 3)a) Was hat Valve am 6.12.1999 gemacht?

Rambo Engineer @ Drippy's 2fort - finest TFC 1.5 || Bild Upload || The world's most advanced open source database

Die richtige Antwort war:

siehe Fraghunters Post

Und hier noch eine graphische Erklärung dazu: Link

PS.: Den kleinen Fehler klären wir später, in einer der nächsten Fragerunden.

Punktestand:
[dP]ThEpOpE: 4 (2++ , weil er versucht hat es selber zu erklären)
Prefect: 2 (2++, für die schöne Erklärung)
cnuke: 1 (1++, nicht schlecht, aber abgeschrieben)
Fraghunter: 1 (1++, für copy&paste)
K-Putt: 1
Deciever: 1

www.d3opencoop.com - A Doom3 Cooperative Mod

@Frage 3.a.: Hier hat Valve nicht rein zufällig mitgemacht?
http://www.bbpp.de/berlin/aktion061299.htm
Aber ich tippe mal auf HL-Releasedate

"[...] you're going to burn in a very special level of Hell. A level they reserve for child molesters and people who talk at the theater." - Book

Die antwort auf Frage 3)a)

Sie haben Nikolaus gefeiert :D

Rambo Engineer @ Drippy's 2fort - finest TFC 1.5 || Bild Upload || The world's most advanced open source database