4. Frage:

In QuizFrage 3 haben wir gelernt, daß BSP Trees Binär Baume sind. Nun die Frage: Was sind Binär Bäume ? Welche Bedeutung haben Leafs und Nodes hierbei ? Was für Vorteile hat diese Datenstruktur gegenüber Listen ?

Mitraten ist erwünscht. Punkte gibts für eine anschauliche Erklärung.

www.d3opencoop.com - A Doom3 Cooperative Mod

also was ein leaf ist weis ich glub ich schon.

der innenraum einer map (wird ja durch enitis definiert) wird in einzelne 4 eckige regionen eingeteilt. diese regionen werden dann durchnummeriert (?) in einer liste (?) gespeichert. ausserdem wird in der liste gespeichert, welche leafs aus welchem leaf auf irgend eine weise sichtbar sind.
wenn der player dann in einem leaf steht wird die liste aufgeklapt und alle objekte der möglichen leafs werden gerendert.
und das ist der zweck der leafs. sie teilen das level in einzelne teile ein, was man gut erkennen kann, wenn man eine verwinkelte map einmal mit und einmal ohne vis (hier wird die aufteilung vorgenommen) komplimiert.
ohne vis berechnet die engine alle polys aus der map (->grottige r_speeds btw ;). mit vis und somit leaf aufteilung werden immernur teile der map gerendert.
[ädit2]
natürlich wird nur der teil vor dem player gerendert. *beikhanabguck*

[ädit]
nach erneutem lesen der frage bin ich mir nichtmehr so sicher, ob das überhaupt gefragt war.. *g*

-das treppentut: [ part I ][ part II ]

[klugscheiß]
Mal ne ganz andere blöde Frage. Muss es nicht DAS Quiz heißen?
[/klugscheiß]

sry 4 spam :-)

Es genügt nicht, nichts zu sagen zu haben! - Man muss auch noch unfähig sein es auszudrücken!

Und kann man da was gewinnen???? :))

SIMHOME.DE
FORUMSUCHE

Ich versuch mich mal und rate Fröhlich mit:

Also jedes Level beginnt bei einer Node. Die Rootnode. Sozusagen eure Festplatte. Dann hat die Node eine Hyperplane die das Level in 2 Hälften zerteilt und beide hälften haben wieder eine Node (A und B). Die Hyperplane heißt fdisk und macht aus unserer Festplatte 2 Partitionen.
Die neuen Nodes haben wieder je eine Hyperplane und spaltet wieder die Nodes auf, neue Nodes entstehen und die werden wieder gesplittet. Und schon haben wir auf jeder Festplatte einen Verzeichnissbaum.
Sobald nichts mehr zu teilen ist wird auf das Leaf verwiesen, was zwischen den Hyperplanes liegt. Muss ein Leaf berechnet werden wird auf die Hyperplanes zurückgeblickt und dann die Polies berechnet.
Die Leafs haben die Funktion das nicht das ganze Level berechnet werden muss. Für jedes Leaf wird eine Visbility Index List erzeugt auf die Zurückgegriffen wird, wenn man in diesem Leaf steht. Die Vorberechnung der VIL übernimmt VIS ;). Aus der Liste der gesehenen Leafs wird dann noch der 180° Teil hinter einem ausgefiltert. Dann die zu berechnenden Leafs ausgewählt, auf den Tree zurückgegriffen, die richtigen Hyperplanes ausgewählt und dann die Polies an den Renderer geschickt.

Ich hoffe is soweit alles Richtig.

"[...] 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

Tip: Binär Baume sind wie Listen eine Datenstruktur. BSP Trees sind nur eine 'spezielle' Version davon.

Grundsätzlich geht es aber bei dieser Frage um die Eigenschaften von Binär Baumen.

www.d3opencoop.com - A Doom3 Cooperative Mod

Liegich denn zumindest mit dem Magerquark da oben richtig?

"[...] 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

ach. ich rate dann mal einfach.. ;)

also. die struktur des baumes ist auf den ersten blick auch eine liste.
zb: (hier wird in der grundstruktur gezeigt, das am stamm des baumes 4 äste sind)
+baum
|-ast1
|-ast2
|-ast3
|-ast4
wenn dann auf eines dieser elemente zugreift, erhält man eine neue liste mit eingeschaften oder mit verknüpften objekten aus dieser, anderen oder untergeordneten listen.
zb: (hier gibt es dann noch zusätzliche informationen zum ast2)
+baum
|-ast1
|+ast2
-|--blabla bestizt dreizehn blätter auf der unteren seite
-|--ast5
-|--ast6
|-ast3
|-ast4

-> halt eben wie bei windows explorer... :rolleyes:

-das treppentut: [ part I ][ part II ]

Naja... ok. Ein Frustballspiel im Knockoutsystem ist z.b. ein binärer Baum, bloß das man rückwärtsdenken muss.

Ich habs nicht so mit ASCIIs daher mal eben nen Bild:

Eine abzweigung nach Links ist eine "0" eine abzweigung nach rechts eine "1"... um jetzt H anzusteuern muss man nur die Polizei anrufen. Spass beiseite: H ist Binär "110"

Für die Engine heiß das: Ein Leaf das berechnet werden muss grenzt an 2 Hyperplanes in unserem Beispiel (müssen theoretisch mehr sein, weiß ich) und zwar an G und H: Also müssen für unser Leaf die Hyperplanes 101 (G) und 110 (H) berechnet werden...

"[...] 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

Khan der geht an dich *threadverpasthab* ;)

Ich hoffe mal der geht an mich. Hab meine armen grauen Zellen zu höchstleistungen getrieben... ;)

"[...] 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

Ein Binärbaum ist ein Baum mit maximal je zwei abzweigungen pro knoten. ein leafnode enthält konvexe polygone, und ein non-leaf node enthält die definition einer splitting plane, die letztendlich die leafaufteilung definiert. der vorteil eines bintrees in diesem falle ist klar: eine splitting plane erzeugt immer zwei neue gebiete, entweder leafs oder gebiete, die noch weiter gesplittet werden müssen, da sie noch nicht konvex sind.

ich hoffe ich hab alles aus dem dokument über bsptrees richtig behalten o_O

Mar 01 01:10:13 <voice> jo
Mar 01 01:10:40 <voice> bis dann ^^
Mar 01 01:11:20 <Archangel> jo
**** ENDING LOGGING AT Tue Mar 1 01:58:13 2005

In QuizFrage 3 haben wir gelernt, daß BSP Trees Binär Baume sind. Nun die Frage: Was sind Binär Bäume ?

Nunja, schon erklärt - also ich denke mal die beste, einfachste und anschaulichste Erklärung ist einfach: das K.O.-System ist ein binärer Baum - nur eben umgedreht (K.O - Sytem fängt mit vielen an, hört mit einem auf - binärer Baum fängt mit einem an und hört mit vielen auf.)
Auserdem kann bei einem binären Baum eine "Manschafft" einfach mal ein sozusagen "ein Spiel ausfallen lassen" - kommen also einfach so weiter, ohne dass sich bei ihnen etwas ändert.
Auserdem können immer "Manschaften" dazu kommen. (die erklärung, die ich jetz hinzugefügt habe muss man sich natürlich auch anders rum vorstellen, dass sie auf einen Binären Baum passt)

Naja - wenn ich mir den fetten Text da oben anschaue, war er warscheinlich doch nicht der anschaulichste *g*

Welche Bedeutung haben Leafs und Nodes hierbei ?

Um das mal ein wenig zu veranschaulichen möchte ich mich mal auf dieses schöne Applet beziehen, dass Nicemice uns da gezeigt hat (hier)

(zum "Bildformat": zur Beschreibung hab ich die Bildteile mal mit Sektionen benannt - sonst haben diese Sektionen keine Bedeutung!)

Die Nodes sind das, in was das Level zerlegt wird (die "Manschaften"), auf dem Bild in Sektion 1 und 2 die dicken Striche, in Sektion 3 die Felder mit grüner/hellblauer Umrandung .
Die Leafs sind der Raum "unter" den Nodes, Also die Leafs sind das Ergebniss der ganzen Prozedur.
Im Bild werden die Leafs in Sektion 1 und 2 durch die Farbigen Felder dargestellt, in Sektion 3 durch die Farbigen Linien (der übersichthalber sind sie zusätzlich noch nummeriert (die großen Zahlen))

Zur Bedeutung der einzelnen Sektionen bitte auf der hp der Applets nachschaun

Was für Vorteile hat diese Datenstruktur gegenüber Listen ?

mhh... nunja, ich würde erstmal sagen, dass sie einfach viel schneller ist. Also die Zugriffszeit verringert sich extrem, da die Daten geordnet sind.
So wie es z.B. sinnlos wäre, eine große Datenbank mit Telefonnummern einfach verwirrt aufzulisten anstatt sie nach Nummern/Namen alphabetisch zu sortieren.
Auserdem sind die Daten so viel besser abrufbar, da sie eine "Adresse" haben (in dem bild z.B. würde 001 warscheinlich die Adresse für Leaf nummer 3 und 101 die Adresse für Leaf Nummer 6 sein).
So beschleunigt diese Methode die Sichtbarkeitsberechung und die Kollisionsabfrage.

--------------------------------
Hoffe, das war jetzt mal größtenteils richtig und verständlich, ansonsten bitte nich schlagen *g* (*duckundweg*)

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

nochmal ne verbesserte version:

ein binärer baum ist ein baum mit maximal zwei abzweigungen pro "knoten" (node). Ein Baum besteht immer aus mindestens einem anfangsknoten (root-node), und dieser kann maximal zwei abzweigungen zu weiteren nodes haben, jeder dieser maximal zwei nodes kann wieder maximal zwei abzweigungen haben und so weiter.

bintrees in engines:
es gibt zwei arten von nodes: leafnodes und non-leaf-nodes. leafnodes haben keine weiteren abzweigungen, sie enthalten die daten der polygone bzw den start-index im polygonarray und die anzahl der polys in einem "raum". "raum" in anführungszeichen, da es sich nicht um einen normalen raum handelt, sondern eher um das, was man im englischen mit "space" bezeichnet, ich werde hierzu einfach leaf sagen, wie es ja die mapper kennen.
ein leaf muss immer konvex sein, das bedeutet konkret: man kann von jedem punkt innerhalb eines konvexen raums jeden anderen punkt im selben raum sehen (das gilt für engines nicht ganz, denn entities werden bei der leaf-aufteilung meistens nicht berücksichtigt). ein non-leaf-node enthält keine polygondaten, sondern definiert eine "splitting plane", eine ebene, die einen "raum", der noch nicht konvex ist, dh der sich nicht als leaf verwenden lässt, in zwei neue räume aufteilt. diese beiden räume werden meistens als "front" und "back" (relativ zur plane) bezeichnet.
dies wird für jeden raum so lange fortgesetzt, bis er konvex ist.

ein bild:

im ersten bild ist der bisjetzt vorhandene raum noch nicht aufgeteilt, das muss noch gemacht werden, denn er ist nicht konvex (man kann vom punkt p1 nicht den punkt (zB) p2 sehen)

im zweiten bild wurde nun eine splitting plane hinzugefügt, die das Leaf L1 und den noch aufzuteilenden raum R1 erstellt.

im 3. bild ist nun die letzte notwendige splitting plane hinzugefügt worden, die den raum R1 in die leaves L2 und L3 aufteilt.

anm: das ist nur ein beispiel, die leaves müssen nicht unbedingt so aufgeteilt werden !

der vorteil eines bintrees bei engines ggüber zB listen ist klar: eine plane zerteilt einen raum IMMER in zwei neue räume

PS: ich kann nich gut zeichnen o_O

PPS: das bild liegt auf voices webserver, es könnte also sein, dass es nicht 24/7 verfügbar ist, ich habe keinen eigenen webspace

edit: rah voice, mach mal deinen webserver an >:O

Mar 01 01:10:13 <voice> jo
Mar 01 01:10:40 <voice> bis dann ^^
Mar 01 01:11:20 <Archangel> jo
**** ENDING LOGGING AT Tue Mar 1 01:58:13 2005

@Archangel
Das mit dem Bild währ auch kleiner gegeangen ;-) und wieso nimmst du kein Lycos?

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

well lycos, die haben meinen space schonmal gekickt, weil ich da nur bilder draufgeladen hab.. und kleiner.. mja.. nö.. :p

Mar 01 01:10:13 <voice> jo
Mar 01 01:10:40 <voice> bis dann ^^
Mar 01 01:11:20 <Archangel> jo
**** ENDING LOGGING AT Tue Mar 1 01:58:13 2005

Ehm, das Bild ist doch cool :D verdammt groß und verdammt klein zu gleich!

Und er nimmt meinen Webserver, weil:
a) Lycos bei zu viel Traffic kickt
und b) Mein Webserver absolut 1337 ist ;D

Against TCPA | Resourcecode.de | Blender 3D | [ Darkzone | Pandorra | Alpine ]

Achso, deswegen haben die meine Page gelöscht, als ich da ein Flood-Script draufgemacht hab *g*

Aber wenn du da ein paar Bilder für Foren draufmachst, wird das schon nicht zu viel Traffic werden.

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

also, brauchen wir das alles eigendlich wissen??? bumme frage, ich weiss aber bitte nicht hauen.

DMC-INTERACTIVE

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

nein, aber Nicemice macht ds grad in der Uni, da wollte er die Gelegenheit nutzen ;-)

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

Gute Frage... eigentlich net...

"[...] 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

für alle, die nicht wissen, was diese Quiz soll
http://thewall.de/forum/showtopic.php?threadid=28878&time=1026419473

giebts eigentlich ne Belohnung (ausser nimals vergehendem Ruhm ;-) ?

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

Okay.

BinaryTrees sind eine struktur zur datenspeicherung.
sie sind eine sonderform des trees, der sich dadurch auszeichnet dass jeder node maximal zwei weitere nodes als kinder besitzt.

ein node ist die "grundeinheit" eines trees und sieht in pseudocode ungefähr so aus:

struct sNode
{
int Data;
sNode *pLeft;
sNode *pRight;
};

leafs sind nodes die keine weiteren kinder besitzen.

der vorteil gegenüber einer liste ist, das daten einfaher gesucht werden können. (im schlimmsten fall bei nem ausgeglichenen baum afaik mit O(log n)).

because our freedom sits at the end of a gun
we're all here getting beat up and held back
we're all here digging knives from our backs

hab auch ma ne Frage, gehört das hierher? >:D *weglauf*
Ja nu wer hattn nu recht? und macht doch nicht so viele bunte Bildchen, da werd ich konfus

KhanRKerensky hat in seinem ersten Post vollkommen recht gehabt.