Hi Leute, ich bin zur Zeit auf der Suche nach guten Alternativen zum guten alten BSP Tree, gibt es da zur Zeit irgend etwas, daß sich da anbieten würde?

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

ähh... was solls den dazu für vernünftige Alternativen geben???

Hmm.. ich habe da ne Menge drüber nachgedacht. Die Frage ist: was bringt ein BSP-Tree:
- verdammt schnelles VISing
- Back-to-Front-culling (kein Z-Buffer nötig für Worldrendering)
- relativ schnelles tracing

Ich habe eine andere Methode entwickelt die relativ effektiv sein könnte - ich müßte dazu aber wissen wie viel ein Z-Buffer ausmacht. Also auf gut deutsch: ist es besser, mit VISing, Z-Buffer only-write, von hinten nach vorne (also mit Overdraw!) oder mir VISing, volles Z-Buffering und von vorne nach hinten (also ohne Overdraw!) zu rendern. Ersteres ist bei BSP-Trees der Fall, letzteres bei meiner rein Leafbasierten Methode.

Diese Leaf-Methode sieht so aus, dass die Karte einfach als eine große Ansammlung an Leafs (also convexen Raumeinheiten) besteht, die über Portals miteinander verbunden sind.
Ich fasse hier mal die Vor- und Nachteile gegenüber BSP-Trees kurz zusammen:
+ direkte Kontrolle der Map, kein Kompilieren notwendig
+ der Mapper hat direkte Kontrolle über Map/Facesplitting, und damit bessere Kontrolle über r_speeds
+/- VISing braucht für kleine Maps mehr Speicher als BSP-Trees, bei größeren Maps ist aber die reine Leaf-Methode effektiver; meine VISing-Methode für Leafs unterstützt außerdem auch automatisch an- und ausschaltbare Portals (geschlossene Türen als VIS-Blocker!)

- typische Gameengine-Funktionen müssen relativ umständlich optimiert werden (erfordert einiges Umdenken wenn man von HL kommt), näheres Coden an der Engine (was aber auch ein Vorteil sein kann)
+/- Tracelines etc.. sind etwas langsamer, besonders auf kleinen Maps. Bei großen Maps kann sich das ganze ziemlich ausgleichen

Ich denke das wars. Ich habe diese Methode ganz allein in meiner computerlosen Zeit in Irland entwickelt *g* ich kann dir also keine Verweise auf Ressourcen im Netz geben oder so.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Dann ist theoretisch auch der OpenGL-Bug ausgemerzt, dass man mit geleakten Treibern auch durch Wände durch sehen kann...

Wie ist eigentlich die Methode von Unreal? Die Maps muss man ja auch nicht kompilieren. Ich hab ehrlich gesagt keinerlei Ahnung von Unreal (und auch kein Interesse), aber vielleicht kann mich ja mal jemand in dem Punkt aufklären...

Prefect's Methode klingt ganz interessant (auch wenn ich aus der kleinen Beschreibung nicht kapiert habe, wie nun die einzelnen Leafes verbunden werden - über Portals, ok, aber wie genau?). Bei so einer Methode kann man dann zwar ne Lightmap vergessen (die müsste ja vorher berechnet werden) aber dafür sind dynamische Lichteffekte perfekt möglich. Und die Rechner von heute brauchen ja auch keine vordefinierte Lightmap - GHz lässt grüßen *g*
Auf jeden Fall sollte man mal mit den maroden Entity-Systemen aufräumen. Das von Quake ist zwar schön aufgeräumt und strukturiert, aber unflexibel. Unreal ist da besser, aber nicht wirklich gut.
Ganz einfach ist das aber nicht...

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

infos zum bsp format, was dies beinhaltet etc gibts auf http://waste.informatik.hu-berlin.de/rpk/diplomarbeit/default.html

ich zitiere von http://waste.informatik.hu-berlin.de/rpk/diplomarbeit/default.html :

"Als Kern der Arbeit wird ein Raycastingalgorithmus entwickelt, bei dem der Rechenaufwand zur Erzeugung eines einzelnen Bildes unabhängig von der Gesamtgröße der Szene ist (d.h. es können beliebig große Szenen konstruiert werden, ohne das der Bildaufbau mit zunehmender Szenengröße langsamer wird).

Im Prinzip basiert dies auf der Überlegung, nicht wie sonst in der 3D-Grafik festzustellen, welche Teile einer Szene nicht sichtbar sind, und dann nur den übrigbleibenden Rest zu rendern, sondern zu ermitteln, welche Teile sichtbar sind. Das Ergebnis ist – zwangsläufig – das selbe, der Rechenaufwand ist aber– insbesondere für "dichte" Szenen wie z.B. Gebäudekomplexe – erheblich geringer"

also nichts weiter als eine raycaster engine wie sie auch in doom genutzt wurde (fact: 2 1/2 dimensionale Szenengeometrie (senkrechte Wände, waagerechte Böden und Decken) also keine voll-3d engine. doch setzt das mal auf 3d um:

die engine sendet eine art laserstrahl in bestimmter dichte vom player(winkelbreite x) aus in den level und wenn der ray mit einem polygon kollediert wird es berechnet. die überlegung ist easy, das militär nutzt sowas schon lange um nachts entfernungen zu objekten festzustellen. die genaue umsetzung kenne ich nicht doch es funktioniert einwandfrei bis auf einige kleine nachteile ist das system dem von id-software haushoch überlegen.

und das oben beschriebene system existiert bereits und arbeitet wunderbar. genauere facts und technische hintergründe kenne ich (noch) nicht doch der BSP tree wird durch ein neues format, AL1, ersetzt und leafs sind überhaupt nicht vorhanden. ausserhalb der lightmap ist kein compile von nöten, einzig diese muss berechnet werden was mit einem extra illumination-editor aber auch recht fix geht.

und was unreal angeht hab ich die selbe frage heute schoneinmal gestellt. auch mich interessieren die routinen der unreal engine...

Ich bin wegen den Entitys von Unreal weg, weil es IMHO keine Brush sondern nur Points gibt (und es gibt auch keine art das anders zu regeln als mit zones, und das ist extrem nervig)

@TTT:Wegen den Lightmaps muss ich widersprechen, Black& White sowie Loose Cannon verwenden soweit ich weiß Real Time Light Maps.

@Prefect: Deine Methode kling Intressant, sag mal beschied wenn mehr draus wird, würde mich interressieren

@Apfelkorn: Es gibt außer dem BSP Tree:
Z.B: Octree's
Quadtree's
Das Zeug das Drakhan verwendet

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

@Blair: Das mein ich doch, Licht muss dynamisch berechnet werden - dazu gehört in meinen Augen auch ne dynamische Lightmap.

@Linga: Die Seite ist gut, ziemlich informativ. Muss ich mir bei Gelegenheit mal ganz reinziehen.

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

real time pixel per pixel shadowing ist doch nichts seltenes mehr als beispiel new world oder von insomniasoftware. die technik besteht schon seit ~3 jahren und die facts verraten es: "- True realtime dynamic lighting, no lightmaps"
screenshots gibts zb. auf http://www.3dgamers.com/screenshots/games/newworldorder/

EDIT

noch ein paar informationen zum bsp format an sich:

"Die Verfahren basieren darauf, eine Szene in eine Menge von zumeist konvexen Regionen oder
Zellen (Cells), die durch Öffnungen (Portals) miteinander verbunden sind, und die in diesen
Zellen befindlichen Objekte zu zerlegen. Eine naheliegende Unterteilung wären beispielsweise
Räume als Zellen und Türen als Öffnungen.
Die Vorausberechnung besteht nun darin, für jede dieser Zellen festzustellen, welche anderen
Teile der Szene durch ihre Portals sichtbar sind. Normalerweise basiert dieser Prozeß auf den
Nachbarschaftsrelationen der Zellen: Für eine bestimmte Zelle sind die sichtbaren Teile der
Nachbarzellen und die durch deren Portals sichtbaren Teile der darauffolgenden Zellen zu fin-den.
Mit anderen Worten: Es sind Folgen von Portalen zu finden, die einen beliebigen Sicht-strahl
ungehindert passieren lassen. Das Problem dabei ist, daß dieser Sichtstrahl bzw. die
Position des Benutzers vorab nicht bekannt ist; es muß vielmehr die prinzipielle Möglichkeit
des Passierens eines Strahls durch eine Folge von Portalen untersucht werden, was mit erhebli-chem
Rechenaufwand verbunden ist.
Es gibt mehrere Optionen bezüglich der Feinheit der Sichtbarkeitsberechnung: Bei einer gro-ben
„Auflösung“ wird für eine bestimmte Zelle nur berechnet, welche anderen Zellen von ihr
aus sichtbar sind (cell-to-cell visibility); eine feinere Auflösung ermittelt z.B. die von einer
Zelle aus sichtbaren Bereiche (cell-to-region visibility) oder sogar Objekte (cell-to-object visi-bility)
anderer Zellen. Im Extremfall wird für jede Zelle die Menge der von ihr aus sichtbaren
Flächen (Potentially Visible Set, PVS) berechnet und gespeichert, was nicht nur von der
Rechenzeit, sondern auch vom benötigten Speicherplatz her ein Problem darstellen kann. Cell-to-
cell-Beziehungen hingegen lassen sich z.B. mit einem stab-tree ([TELL92], S. 25) pro Zelle
wesentlich weniger speicherintensiv darstellen (laut [TELL92] sind selten Portal-Sequenzen
mit mehr als zehn Portalen zu finden).
Das Rendern einer auf diese Weise aufbereiteten Szene ist dann relativ einfach: Es wird ermit-telt,
in welcher der Zellen sich der Benutzer aktuell befindet. Für diese Zelle werden dann die
gespeicherten Sichtbarkeitsinformationen ausgewertet und die dadurch gefundenen Flächen
als „Eingabemenge“ für eines der normalen Renderverfahren benutzt – typischerweise einen
durch spezielle Hardware realisierten Z-Buffer Renderer."

"Binary-Space-Partitioning Tree: Die dieser Technik zugrundeliegende Idee ist
folgende: Angenommen, die Flächen einer Szene lassen sich in zwei Gruppen
einteilen, die durch eine beliebig ausgerichtete Ebene getrennt werden. Die
Flächen, die sich auf der gleichen „Seite“ der Ebene befinden wie der
Benutzer,können dann aus dessen Sicht die Flächen auf der anderen Seite
verdecken; umgekehrt ist dies aber nicht möglich. Bei einem Back-to-Front
Rendering würde man also zunächst die auf der dem Benutzer abgewandten
Seite der Ebene liegenden Flächen rendern und dann die auf derselben Seite
wie der Benutzer liegenden. Die Position des Benutzers ist dabei für die
Zuordnung der Flächen zu den Gruppen oder für die Lage der Trennebene
irrelevant: Würde sich der Benutzer auf der anderen Seite der Fläche
befinden, so würde sich lediglich die Renderreihenfolge der beiden
Flächengruppen ändern. Der Rest ist Rekursion: Jede der beiden Gruppen
läßt sich weiter unterteilen, wobei für die beiden neuen Gruppen dann wieder
die gleichen Überlegungen bezüglich der Renderreihenfolge und der
Benutzerposition gelten. Dieses Verfahren läßt sich fortsetzen, bis sich
auf jeder Seite einer Trennebene nur noch eine Fläche befindet. Die Struktur,
die man erhält, wenn man eine Szene auf die beschriebene Weise unterteilt,
ist ein binärer Baum: die Knoten enthalten jeweils die Trennebene und
Referenzen auf die beiden Subknoten oder Blätter. Blätter enthalten dann die
Flächen. Da an jedem Knoten der Raum in zwei Bereiche eingeteilt wird,
nennt man den Baum "Binary-Space-Partitioning Tree"

@TTT: Ich weiß das du das meintest, aber wenn du dir zum Beispiel (ist kein besonders Gutes) das Black & White Winamp Plugin reinziehst, wirst du erkennen das es (trotz einer begrenzten Welt) schon auf einem P200 MMX mit Voodoo 2 relativ flüssig läuft, von Ghz kann IMHO da nicht die Rede sein.

@Linga: Wirklich Super Material, danke für den Link!

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

@Blair: Wo gibt's denn das Plugin? Würd ich mir gerne mal angucken...

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

War auf der Gamestar CD... (ich schäm mich ja, die zu lesen,) außerdem kriegst du es hier: http://dance.bwgame.com/

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

@Linga: Das-per-pixel-rendering ist schon uralt .. wird von allen möglichen Cad und 3D Programmen zum Szenenrendern benutzt (bsp: 3D Studio Max)

Another1

...relaxing..atm =)
... und Schweiz suckt!

@apfelkorn (von ganz oben): Leider nicht.. die 3d-Hardware (bzw. -treiber) kann immer noch manipuliert werden.

Dynamische Schatten gibt's in Sonderfällen auch schon lange (Volumenschatten, und eine Art "Lichtquellen-Z-Buffer"). Allerdings funktionieren diese Methoden zumeist entweder nicht mit beweglichen Lichtquellen, oder eben nicht mit mehreren Lichtquellen. Ein Vorberechnen der Lichtverhältnisse ist immer noch am schnellsten (es sei denn man schraubt die Qualität herunter). Ach ja, Vorberechnen muß nicht unbedingt Lightmap heißen...

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.