Hi hab Das grobe von Octrees hinbekommen.
Meine Frage wäre jetzt wie ich überprüfe ob ein Polygon in ein Node, also eine rBox des Octrees ist?
Wo finde ich die Intersection dafür?

Danke schonmal.

Tschuuus

Um zu prüfen ob ein Polygon in einer Box liegt benötigst du nur 2 Teilschritte:

1)
Du prüfst ob die Diagonale die deinem Normalenvektor deines Polygons am ehesten entspricht das Polygon schneidet (Line-Polygon-Intersection). D.h. wenn alle 3 Komponenten deines Normalenvektors positiv sind (der Normalenvektor zeigt nach rechts, oben, vorn), ist die Diagonale, die du suchst die von der linken, unteren, hinteren Ecke zu der gegenüberliegenden Ecke (rechts, oben, vorn).

2)
Du prüfst ob eine Kante des Polygons deine Box schneidet (Line-Box-Intersection)

Wenn einer der zwei Tests positiv ausfällt, schneiden sich Polygon und Box.

Um das ganze noch zu optimieren kannst du zu Beginn prüfen, ob die Box die Ebene des Polygons schneidet. Ist dies nicht der Fall, schneidet das gesamte Polygon die Box nicht.

Außerdem kannst du noch überprüfen, ob ein Eckpunkt des Polygons in der Box liegt.

Diese Methode habe ich mir selbst ausgedacht und sie lief bei mir bisher immer fehlerfrei. Vielleicht gibt es aber bessere, schnellere Methoden um zu prüfen, ob sich eine Box und ein Polygon schneiden.

_________________
Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Denn jederman ist überzeugt, dass er genug davon habe.
Rene Descartes, frz. Mathematiker u. Philosoph, 1596-1650

Klingt zu kompliziert für mich. Geht das nicht einfacher, dass ich z.B eine Box um das Polygon ziehe und dieses überprüfe, ob es im Node liegt.

Wo finde ich denn Tutorials????

Natürlich kannst du auch eine Box um dein Polygon ziehen. Du kennst alle Punkte deines Polygons und musst nur die 2 extremen Eckpunkte deiner Box finden.
Das ganze ist mitunter sehr ungenau und ist daher nicht zu empfehlen (aber durchaus möglich).

Auf www.gametutorials.com gibt es ein Tutorial zum Thema Line-Polygon-Intersection.

Zum Thema Ray-Box-Intersection kennt google eine Menge Seiten, die dich zum Ziel führen sollten. Du musst allerdings bedenken, dass unter “Ray“ im allgemeinen eine Gerade, die ins unendliche führt verstanden wird.
Zur Verdeutlichung habe ich dir ein Bild gezeichnet.

Wenn du für die Gerade den Stützvektor e1 nimmst, musst du sicherstellen, dass die Entfernung e1-s1 geringer ist, als die Entfernung e1-e2.

Außerdem besteht noch die Möglichkeit, dass die Gerade die Box an einem Punkt schneiden könnte, der gar nicht auf der Polygonkante liegt und die Entfernung e1-Schnittpunkt geringer ist, als e1-e2 (z.B. der Punkt Sm).

Schließe daher mit Hilfe des Skalarproduktes gleich zu Beginn deiner Ray-Box-Intersection den Punkt Sm aus:

rd:=VectorSubtract(e2, e1);
Tmp:=VectorSubtract(Schnittpunkt, e2);
if VectorDotProduct(Normalize(rd), Normalize(Tmp)) = -1 then
falscher Schnittpunkt…

Denke aber daran, dass du auch 2 Schnittpunkte erhalten kannst (s1, s2).

Ich hoffe das hilft dir weiter. Klingt am Anfang alles ein wenig kompliziert, ist es aber gar nicht. Nimm dir ein Blatt Papier und die Probleme lösen sich von selbst.

Ansonsten kannst du deine AAB immer noch durch Polygone beschreiben, bei welchen du wieder die von Gametutorials beschriebene Line-Polygon-Intersection anwenden kannst.

Die Geschwindigkeit ist bei der Generierung deines Octrees schließlich ziemlich egal.

_________________
Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Denn jederman ist überzeugt, dass er genug davon habe.
Rene Descartes, frz. Mathematiker u. Philosoph, 1596-1650

Warum packst du nicht gleich ganze Objekte in den Occtree?
Dann kannst du gleich die AABB des Objektes nehmen und bist ohne Aufwand fertig. Außerdem muß die Grenze zwischen den Unterknoten ja nicht unbedingt immer in der Mitte verlaufen.
Man braucht den Baum ja nur, damit man eine hierachische Struktur hat, und grob von vorne nach hinten sortieren kann. Und da braucht man keine einzelnen Dreiecke einfügen oder gar schneiden.

das ganze ist auch im octree tut von aya (hier bei dgl) erläutert. ich finde es etwas schade, dass du nicht direkt nachgedacht hattest (klingt bei der ausgangsfrage so), da diese überprüfung der aabbs mit den treeleafs recht simpel ist und auch mit wenig logischen aufwand zu schaffen ist.

_________________
Aktuelles Projekt :
www.PicPlace.de

Ich denke Shadow benötigt Octrees zur Unterteilung seiner Geometrie. In großen Außenterrains macht die Unterteilung via Octrees durchaus Sinn. Für diesen Fall muss er selbstverständlich prüfen, ob ein Polygon im Octree liegt oder nicht. Wenn er um jedes Polygon erst eine AABB erstellt und prüft, ob diese im Octree liegt, ist das nicht sonderlich genau.
Es geht ihm hier also IMHO nicht um Objekte wie z.B. Bäume, die nicht direkt zur Geometrie der Map gehören, sondern um die Unterteilung der Map selbst.

_________________
Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Denn jederman ist überzeugt, dass er genug davon habe.
Rene Descartes, frz. Mathematiker u. Philosoph, 1596-1650

Als Objekt könnte in der Landschaft dann z.B. ein Block von 32*32 Flächen oder so etwas in der Art gelten.
Es macht ja keinen Sinn das erst auseinander zu reißen wenn es eh zusammen gerendert wird.

Woher soll ich den wissen, was zusammen gehört?
Bei einer Heightmap mag ich das noch definieren können, wenn ich aber z.B. mehrere Stockwerke habe sieht es schlecht für mich aus.
Ich reiße doch nichts auseinander. Ich teile zu Beginn die Polygone auf meine Leafs des Octrees auf, und gehe den Octree dann von oben bis unten durch. Liegt ein Leaf im Frustum liegen auch die meisten der Polygone des Leafs im Sichtbereich.
Deshalb kann ich sicher sein, dass ich wirklich nur die nötigsten Polygone zeichne.

Außerdem ist es nicht viel Aufwand zu Beginn ein Octree zu berechnen und jedes Polygon darauf aufzuteilen (und die Berechnung ist erstaunlich schnell).

_________________
Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Denn jederman ist überzeugt, dass er genug davon habe.
Rene Descartes, frz. Mathematiker u. Philosoph, 1596-1650

Ich denke mal, daß das Level nicht aus einzelnen Dreiecken/Flächen aufbaut ist, sondern vom Editor her schon in Gruppen oder Objekte eingeteilt ist. Anders als durch verwenden von bereits modellierten Objekten wird man wohl kaum die Polygonanzahlen erreichen können, die bereits heutzutage benötgt werden. Und wenn es da schon eine Struktur gibt, dann nützt es doch nichts das ganze an den künstlichen Octree Grenzen nochmal zu teilen.
Beim Occtree kommt noch im Gegensatz zum BSP Baum hinzu, daß die Grenze nicht mit der Geometrie zu tun hat. Das heißt hinter der Wand und ein Stück vor der Wand können zur selben Zelle gehören.
Daher schlage ich vor, nur die Objekte in einen BSP Baum einzusortieren und sich Ebenen für den Baum aus der Geometrie zu holen. Dann hat man einen kleinen Baum, der trotzdem alle Anforderungen erfüllt.

Also um alles mal zu verdeutlichen...

Ich habe einen Terrain, der aus 128*128 Punkten besteht, diesen lade ich aus einer Bitmap und verbinde dann die Flächen.

Es besteht also alles auf Polygonen und ist in einem Array gespeichert.
Mein Octree funktioniert einwandfrei es ist mir nur ein Rätsel wie ich abfrage, ob ein Polygon des Terrains jetzt in meinem Node(Quadrat des Octrees) ist oder nicht.
Denn ein Dreieck kann ja auch in ein Cube reinragen auch wenn die Vektorenb außerhalb des Cubes liegen. Da hat Magellan mich schon richtig verstanden.
Die INtersektion klingt meiner Meinung nach sehr kompliziert, ich werde es mal so probieren, dass ich ein Qüadrat um das Polygon ziehe und diese auf Kollision überprüfe.
Aber danke für eure antworten.

Wenn du nur eine Höhenkarte hast, kannst du auch einen QuadTree nehmen und die Einteilung dann direkt anhand der Position eines Quadrates vornehmen und z.B. immer 4*4 Quadrate die nebeneinander liegen in einer Zelle speichern.

Für das was Lars vorschlägst, ist ein normaler BSP (ein Octree ist ja nur ein vereinfachender Spezialfall davon) tatsächlich eleganter - allerdings funktioniert das nur für konvexe, geschlossene Geometrien wirklich gut (weshalb die "Brushes" in diversen Editoren auch genau solche Entitäten sind).
In einem kompilierten BSP-Baum ist es dafür einfach, die überflüssigen Polygone (etwa die angrenzenden Flächen zweier Brushes) verschwinden zu lassen.

Objekte direkt (ohne Aufteilung) in einen Octree einzugliedern ist allerdings IMHO nicht die günstigste Variante - jedenfalls nicht beim Erstellen (Kompilieren) eines Octrees:
Ich selbst mache es so: Beim Erstellen des Baumes werden alle statischen Objekte in eine "Polygonsuppe" zusammengeworfen, und diese wird so lange weiter unterteilt, bis eine von zwei Bedingungen erfüllt ist: entweder enthält jeder Leaf weniger als das Minimum an Dreiecken, oder aber eine bestimmte Iterationstiefe ist erfüllt. Hierfür ist tatsächlich eine Dreiecks-Box-Kollision notwendig, bei der ich jetzt aber nicht verstehe, was das Problem sein soll. Die Bounding Box eines Dreiecks ist schnell in Echtzeit bestimmt, ob zwei Bounding Boxen sich überschneiden ist schnell festgestellt. Schwieriger ist es da schon, das Dreieck gegebenenfalls aufzusplitten, da dieses dann (im schlimmsten Fall) mit allen sechs Ebenen der Quaderseiten des Octree-Nodes verschnitten werden muss.

Wenn die statischen Objekte in den Octree eingetragen sind, ist dessen Darstellung einfach, da jeder Octreenode dann genau "weiß" welche Dreiecke ihm zugeordnet sind und welche nicht - eine nochmalige Überprüfung zur Laufzeit ist nicht notwendig (das war ja auch der Sinn der ganzen Sache).
Um nun noch dynamische Objekte in den Octree hineinzubringen, muss ganz einfach herausgefunden werden, in welchen Nodes des Octrees sich die Bounding Box des dynamischen Objektes befindet - und das Objekt wird dann gerendert, wenn sich mindestens einer dieser Nodes im Blickfeld befindet (man kann danach ja immer noch überprüfen, ob es im Frustum liegt, spart sich so aber eventuell viele Frustumtests für Objekte im Vorfeld, muss diese aber bei Positions/Größenänderungen wieder neu in den Octree einsortieren, der Vorteil dieser Methode ist, dass man quasi "gratis" eventuell vorhandene PVS Informationen des Octrees für dynamische Objekte mitverwenden kann) - das Ganze geschieht dann zur Laufzeit, also nach der Kompilierung des Octrees.

Der große Vorteil von Octrees ggü. "normalen" BSP ist, dass man in jedem Leaf eine Dreiecksliste speichern kann, die dann als VBO (oder Displayliste) direkt und schnell an die GraKa gesendet wird, nimmt man dann die einfachere Verwaltung und Eingliederung externer (nicht hineinkompilierter) Objekte hinzu (Bounding Boxes sind schnell überprüft) hat man IMHO ein recht allgemein verwendbares System, das für fast alle Anwendungsgebiete gut verwendbar ist (obwohl es für spezielle Anforderungen (etwa Innenlevels) immer "schnellere" Algorithmen geben dürfte, die dann allerdings für andere Darstellungen (Weltraumsimulation) versagen.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Die Geometrie muß nicht geschlossen oder konvex sein. Das einzige was man wirklich braucht ist eine gute Balancierung des Baumes, damit man von jeder Position aus die Objekte von vorne nach hinten sortieren kann. Wenn man das kann, kann man mit den Occlusion Queries die Sichtbarkeit der Objekte dynamisch bestimmen.

Das sagte ich auch nicht . Allerdings funktioniert die Erstellung eines BSP-Levels am besten, wenn solche Entitäten halbwegs gleichmäßig im Raum verteilt sind (da man diese am besten über beliebige Ebenen, die in diesem Fall ja der Geometrie selbst entnommen werden, unterteilen kann) - für (etwa) eine Landschaft oder eine Weltraumsimulation ist ein normaler BSP Baum hingegen nicht geeignet.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/