Hi

Ich bin gerade dabei eine Octree klasse zu programmieren und bin da auf ein kleines Problem gestoßen. Und zwar bin ich jetzt schon so weit das meine Welt immer weiter in Boxen aufgeteilt wird, aber ich weiß nicht genau wie man prüfen kann ob ein Vertex sich inerhalb einer Bounding Box befindet.
Ich hab mir da bis jetzt folgendes überlegt: Man erstellt für jede Fläche der Box eine Ebene und prüft dann ob das Vertex sich inerhalb dieser 6 Ebenen Befinden. Nur find ich im Internet nicht genügend Informationen über Ebenen. Kann mir jemand ne Formel sagen womit ich die Infos für eine Ebene anhand eines Dreieckes kriege(Normale hab ich schon ) und wie ich dann teste ob sich ein Vertex vor oder hinter dieser ebene befindet.

Das mit der BBox geht einfacher, wenn es eine AABB ist, also wenn die Box an den Achsen ausgerichtet ist. Dann hat man ja zwei Punkte min und max. Ein Punkt p liegt dann innerhalb der Box, wenn gilt:



Bei den Ebenen hat man die Normale n und die Entfernung zum Ursprung s. Die Ebenengleichung sieht dann so aus: (n dot x) + d=0

Um die Entfernung eines Punkte p von der Ebene auszurechnen setzt man p in die Gleichung für x ein:
|n.x*p.x+n.y*p.y+n.z*p.z+d|= Entfernung von p von der Ebene (n,d)

Es gibt außerdem noch ein Mathe Tutorial, ein Octree Tutorial und auch verschiedene Mathe Units hier auf der Seite.

Danke für die Antwort.


Man bin ich ... . Das hätte mir auch echt selber einfallen können. Naja ist heut nicht mein tag .

Auch nochmal danke das du mir das mit den Ebenen erklärt hast. Kann ich irgendwann sicherlich noch gebrauchen.


Hm das mathe Tutorial erklärt nicht wirklich das was ich hier wissen wollte und das Octree Tutorial erklärt nur das Prinzip der Octrees.

Naja falls die klasse jetzt auf anhieb richtig arbeiten sollte, dann... wär ich sehr froh

So einen Code, der vermutlich sehr oft ausgeführt wird, kann man dann natürlich noch optimieren, damit ihn die CPU schneller bearbeiten kann.

Mal ein Beispiel:

Das ist jedenfalls das schnellste was mir in Delphi direkt einfällt.
Mit dem Inline Assembler könnte man vielleicht noch etwas mehr rausholen, aber ich hab bis jetzt noch keinen Code geschrieben, da meine Kollisionen mit der Kugelmethode gut funktionieren.

Und wo ist da jetzt der Vorteil?
Die Vergleiche ersetzt du durch Subtraktionen und fügst zusätzlich noch drei Multiplikationen und drei Integervergleiche hinzu. Zusätzlich verhinderst du effizient, dass Testvalue vom Optimizer in einem Fließkommaregister gehalten werden kann (und Testaccess natürlich auch nicht in einem CPU Register).
Der ursprüngliche Code kann auch früher abbrechen, da man normalerweise davon aus gehen kann, dass full boolean evaluation ausgeschaltet ist.

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

Ich hab's getestet, es ist wirklich etwas schneller.
Wenn du's mir nicht glaubst, ich hab den Ansatz aus einem Tutorial für Assembly-Optimierung.

Hauptsächlich wird die "FCOMP FSTSW SAHF JNB" Kombination zum Testen von Fließkommazahlen vermieden, die je nach Prozessor auch mal 9-14 Takte dauern kann.
Durch die Subtraktionen und die Multiplikation führe ich jeweils zwei Tests in 9 Takten aus, der Integervergleich(1 Takt) und der konditionelle Sprung brauchen dann noch 2-3 Takte.

Wieso sollte man TestValue denn in einem Register halten? Zum Beginn jedes neuen Testes muss der alte Wert doch eh verworfen werden.
Bis auf das eine Speichern und Neuladen als Integer werden die Register eigentlich sehr effizient genutzt. Der Wert $80000000 wird außerdem direkt aus dem Code gelesen und muss nicht geladen werden.