dynamischer Octree

Hallo zusammen!

Im Forum gibts ja schon einige Beiträge zu standardmäßig
eingesetzten OctreeAlgorithmen. Diese befassen sich allerdings
immer mit statischen Octree-Strukturen. D.h.: es wird davon ausgegangen,
dass keine animierten 3DModelle zum Einsatz kommen!
=> Was mach ich denn jetzt, wenn ich trotzdem Animationen in meine 3DSzenerie
einbinden will? Ich kann ja wohl schlecht mit jedem Frame den Baum löschen
und neu generieren!

Weiss vielleicht jemand von euch Rat?
Kennt jemand entsprechende Artikel im Netz?

Schon jetzt vielen Dank für eure Hilfe!

Grüße,
TS++

rapso

ich hänge die dynamischen entities bei mir nach dem animieren immer neu in den baum ein, bzw ich hänge sie um. den baum generiere ich aus den statischen daten.. klar kann es sein, dass du dadurch z.B. nur eine box des octrees hast und dort dann 1000 laufende mänchen drinne sind, aber die dann bruteforce durch zu cullen ist schneller als sie erst in einen baum aufzuteilen und dann zu cullen (jedes frame)

wenn man nur dynamische objekte hat, dann stopft man die in ein "potential-array" in dem sind die objekte danach sortiert in welchem frame sie potenziel wieder zu sehen sind.
also angenommen du hast ein object und es ist 100Km weit weg, du weißt dass es in 1Km in 1sek zurücklegen kann und die camera ebenso, also setzt du den wert für das potenziel sichtbare frame = aktuelles_frame + 50;
die objekte sortierst du dann

dann jedes frame:
fängst am unteren ende des arrays an objeckt für objeckt zu testen ob bzw. wann es zu sehen ist bis zu dem array element, dass nicht in diesem frame zu sehen sein kann (also ein potential von mindestens aktuelles_frame+1 hat).
dann sortierst du das array und renderst alle die in diesem frame zu sehen sind und fängst das ganze von vorne an.

damit kannst du unheimlich viele dynamisch objekte haben die dann leicht zu verwalten sind, falls nur wenige zu sehen sind.

du solltest beim sortieren gut überlegen ob du das ganze arrays immer neu sortieren willst, ob du nur inkrementel sortierst, also nur ziemlich den anteil des arrays, an dem du manipuliert hast (und die ausläufer davon) aber nicht die grosse menge der objeckte die sowieso erst in 1000frames oder sekunden zu sehen sein werden.

wichtiges dabei ist:
-potänzen speichern anhand der sich am besten geeigneten daten, also wenn du z.B. ein strategiespiel hast und überall stehen "dynamische" windmühlen, dann ist das, was am besten für das potential geeignet ist der weg, den die kamera zurücklegen muss um das objekt zu sehen... machst du ein rennspiel in dem du weißt, dass die kamera nicht im nächsten moment auf der anderen seite der strecke sein kann, aber du weißt, dass ein wagen vor dir auch wegfährt und du diesen also viel später auf der strecke triffst als die zeit die du brauchst um dort hin zu kommen wo der andere wagen gerade ist, dann kannst du mit der "schätzung" der zeit als potential bessere ergäbnisse bekommen als der wegstrecke.
-wenn du portale hast oder desgleichen, dann darfst du nicht vergesssen alles zu resetten.
-wenn du zusammenhängende systeme hast z.B.ein baum aus vielen sich bewegenden ästen, dann sollte der baum als ganzes, und nicht jedes objeckt für sich, zusammen gefasst werden.

übrigens kann sich dieses system auch gut für collisionserkennung nutzen lassen bei vielen dynamischen objeckten.
dabei muss man jedem objekt ein kleines array mit potenzielen collidern haben und am ende das potential gespeichert, bei dem das ganze resettet und dann mit frischen daten befüllt wird. (weil man ja nur einen ausschnitt der potentiellen collider hat)

ich hoffe ich habe mich nicht zu dumm ausgedrückt und konnte ein wenig helfen.

rapso->greets();

ps. das ist nur eine methode von vielen die man nutzen kann, z.B. gibt es noch das ganze als potential map, es wäre auch gut für jedes objekt eine bounding box zu machen die das objekt umschliesst und die positionen die es in vielleicht den nächsten 2sekunden machen kann und dann generiert man nen AABB tree alle 2sek.

Servus!

rapso->danke()
Das hilft mir schon mal weiter!

Potenzielle Bewegungsräume für meine 3DModelle zu erkennen
gestaltet sich für meine Anwendung leider als relativ schwierig,
da ich es dem Endanwender ermögliche einzelnen thematisierten
Objekten beliebige Animationen zuzuordnen, welche wiederum
objektorientiert im Speicher gehalten werden.

Jedoch mit BruteForce könnte ich durchaus weiterkommen!

=> Denn jedes meiner 3DModelle verfügt über einen eigenen BoundingTree,
der auf Modell-,Objekt- und Faceebene BoundingSpheres enthält.
Der Kollisionstest jedes 3DModells mit dem ViewFrustrum dürfte dann
ja nicht ganz so aufwendig werden, zumindest wenn ich mich auf die
Modellebene beschränke.

Da bleibt mir dann erst mal nichts weiter übrig als ein paar Testläufe
zu fahren!
Schau mer mal, dann sehn mer scho!

Danke!

Grüße,
TS++

rapso

dann mußt du den animationen zuordnen um welchen faktor die bounding volume eines objecktes steigt, wenn die animation dort angehaftet wird, oder sind das KI gesteuerte animationen und du kannst das deswegen nicht wissen?

aber ein paar begränzungen bezüglich maximaler verschiebung der objekte und kameras wirste doch eigentlich haben können, oder?

rapso->greets();

rapso! wieviele rechtschreibfehler kann ein mensch eigentlich machen? es heißt "objekt" und nicht "objeckt"! es heißt "potenzen" und nicht "potänzen"!

rapso

Original erstellt von <gormor>:
rapso! wieviele rechtschreibfehler kann ein mensch eigentlich machen? es heißt "objekt" und nicht "objeckt"! es heißt "potenzen" und nicht "potänzen"!

sovile ich mag um leute aufzuregen

ach übrigens, du hast vergessen das ich alles klein schreibe

womit ich auch noch gramatische macken habe

weil z.B.
der gefangene Floh
und
der Gefangene floh
so
der gefangene floh
gramatisch falsch ist, da ich zwei verb'n drinne habe ohne substantiv

danke dass du dich aufrägst, ich genisse es!

rapso->greets();

ps. ich mag die sprache in der man sich die rechtschreibung selber bestimmen kann, c++
#define inteagae int

@rapso
Da kommt mir gerade eine Idee!
Prinzipiell hast du recht.
Das war vielleicht ein Denkfehler von mir!

=> Ich geh jetzt einfach mal davon aus, dass der Endanwender keine
eigenen Animationen definieren kann, sondern lediglich vordefinierte
Animationen verwendet werden können. Dann ist ja bereits vor der Animation bekannt, welche einzelnen Animationsschritte, also neue Position und neues
lokales Koordinatensystem, auf das jeweilige Modell anzuwenden sind.
D.h.: ich könnte doch zuerst einen BoundingTree für den Animationspfad beschreiben und dann eine Kollisionserkennung zwischen Animationspfad
und ViewFrustrum durchführen.
Und nur falls die Kamera den Animationspfad einfängt, werden die Modelle, die
sich auf diesem Pfad befinden gerendert!
Das wär doch mit Sicherheit schon mal eine wesentliche Verbesserung!
Mal schaun . . .

Grüße,
TS++

rapso

wird bestimmt prima laufen

du könntest zusätzlich vielleicht die animation in abschnitte einteilen und für die je eine bounding volume generieren falls die animation länger dauert, aber so meinte ich das ungefähr auch (auch wenn es vielleicht aus meinem wort-matsch nicht ersichtlich war (im 2. posting))

woran arbeitest du eigentlich, klingt ja als würdest du dir sehr viel mühe geben

rapso->greets();

ps. ich mag die sprache in der man sich die rechtschreibung selber bestimmen kann, c++
#define inteagae int

#define = C

@rapso:

Ursprünglich handelte es sich bei meinem Projekt lediglich um
einen kleinen 3DModellierer, ohne auffällige Besonderheiten.
Ich war als WI-Student ein absoluter Neuling auf dem Gebiet der
Grafikprogrammierung und wollte in meiner Freizeit auch mal neben
Datenbanken für Wissensmanagment und Kostenrechnungssystemen
Neuland kennenlernen. Seit dem hat sich sehr viel an dem ursprünglich
kleinen Tool geändert, da mir immer wieder neue Knacknüsse in den
Sinn kamen, die ich ja aber, als Neuling, auch selber wieder knacken musste.
Seit mir schließlich einer meiner Dozenten angeboten hat, mein Projekt
als Basis für meine Diplomarbeit zu verwenden, lässt mich die fixe Idee
nicht mehr los, die Anwendung soweit auszubauen, bis mit ihr die Modellierung
kompletter dreidimensionaler Welten möglich ist(incl. Animationen).

Jetzt wirst du verstehen warum ich so viel Zeit in das Projekt investiere!
Ein Diplom ist doch ein guter Anreiz!

Grüße,
TS++

PS: Wie bist du eigentlich bei diesem Haufen hier gelandet?

rapso

also mit dem erstellen von polys und CSG drinne? alles?

sowas wie der quake level editor oder wie kann ich mir das vorstellen? *g*

rapso->greets();

TS++

Das kommt schon ungefähr hin!

Nur hab ich zunächst vor, mich bei den 3DModellen erst einmal
auf eine vorgegebene Bibliothek zu beschränken, deren Modelle dann
bezüglich ihrer Texturen, Farben, Oberflächenbeschaffenheit usw.
verändert werden und in der Szene plaziert werden können. Einzelnen
3DModellen oder 3DModellgruppen können dann wieder aus einer Bibliothek
entnommene Animationen zugeordnet werden. Ebenso sind die einzelnen
Modelle logisch miteinander verbunden. D.h.: der Benutzer soll die Möglichkeit
haben Reaktionen auf bestimmte Ereignisse einzubauen.
z.B.: sobald Lichtquelle1 eingeschaltet wird, soll Modell31 mit seiner Animation beginnen, worauf 10 Sekunden lang die Soundquelle26 aktiviert
bleibt. Terrain und SkyBox sollen natürlich ebenfalls modifizierbar bleiben.
Vergleichbar wäre vielleicht, was das Grundprinzip anbelangt, das 3DGameStudio.
Allerdings ohne Skripsteuerung. Denn wenn ich jetzt auch noch Parser und Tokenizer für eine eigene Skriptsprache implementieren müsste, würde ich
glaub ich durchdrehen. Kommerziell wollte ich die Anwendung eigentlich garnicht
nutzen.

Ich schau mal wie weit ich komm!

Grüße,
TS++

[ Dieser Beitrag wurde am 10.04.2003 um 18:09 Uhr von TS++ editiert. ]

rapso

http://www.lua.org/

das ist ne freie scriptsprache, ich nutze sie noch net viel, aber ich kenne viele leute die von z.B. python drauf umgestiegen sind. sie soll relativ einfach sein in jeder hinsicht und trotzdem gut!

also das nur als tip

rapso->greets();