Containment Test zwischen AABB und Sphere

[LiquidAcid]

Wenn wir schonmal dabei sind. Mal das ganze anders rum. Also testen ob sich ein AABB in einer Kugel befindet.

Dazu könnte man ja einfach die umschliessende Kugel des AABB erzeugen und dann testen ob sich diese innerhalb der Kugel befindet. Allerdings gefällt mir daran nicht, dass man zur Berechnung der umschliessenden Kugel die Länge der AABB Diagonale berechnen muss (die Quadratwurzel) - irgendwelche Vorschläge?

cya
liquid

[Stefan Zerbst]

Hi,

zu dem Sinn sagte ich ja bereits, dass klar im Vorteil ist wer lesen kann. Aber ich arbeite daran

Was Deine umschließende Sphere angeht so würde dieser Test ein false zurückliefern wenn die AABB vergleichsweise gross ist aber noch in der Sphere liegt, denn die "Bounding Sphere" der AABB ist natürlich größer als diese. Ein simpler Test wäre einfach, ob alle acht Eckpunkte der AABB innerhalb der Sphere liegen.

Aus dem Bauch heraus gesprochen sollte es auch reichen, wenn man zwei diagonale Punkte der AABB prüft ob sie in der Sphere liegen, also den Minimum und den Maximum-Punkt.

Ciao,
Stefan

[LiquidAcid]

Das letztere wird wohl nicht funktionieren. Man stelle sich (allein zweidimensional) das folgend vor. Ein Punkt (ob Min oder Max ist ja egal) liegt am linken Rand der Kugel, allerdings immer noch innen drin. Der andere Punkt liegt am unteren Rand (ebenfalls noch in der Kugel). Konstruiert man jetzt aus den beiden Punkten (die ja innerhalb des AABB) liegen ein Rechteck dann liegt eine Ecke schonmal nicht in der Kugel. Die Idee mit dem Zwei-Punkte-Test hatte ich nämlich auch, aber das kam mir schon spanisch vor - es war einfach "zu" einfach.

cya
liquid

[Stefan Zerbst]

Hi,

nein es ist nicht egal ob Min/Max Punkte oder nicht. Wenn man den minimum und den maximum Punkt verwendet und beide innerhalb der Kugel liegen dann liegt auch die AABB innerhalb der Kugel. Auch wenn es sehr einfach ist, immerhin sind das ja nur eine Kugel und eine AABB die man gerade deshalb verwendet weil alles so einfach ist

Dein Beispiel mit dem "Punkt am linken Rand" hat den Denkfehler, dass man nur Eckpunkte der Box verwenden darf, keine beliebigen Punkte auf den Kanten der Box.

Ciao,
Stefan

[TGGC]

LiquidAcid schrieb:

Allerdings gefällt mir daran nicht, dass man zur Berechnung der umschliessenden Kugel die Länge der AABB Diagonale berechnen muss (die Quadratwurzel) - irgendwelche Vorschläge?

Muss man das denn wirklich? Ich glaube nicht.

Aber ich glaube dies funktioniert nicht.

Bye, TGGC \-/

[LiquidAcid]

Ich hab mal was kleines gemalt (mit meinen bescheidenen PSP Kenntnissen, könnt ruhig lachen :D)

Link

Sieht das in 3D dann wieder ganz anders aus? Oder bin ich jetzt ganz auf dem Holzweg??

cya
liquid

[TGGC]

Erstmal: haha!

Na aber selbstverständlich funktioniert es mit nur 2 Extrempunkten nicht. Da musst du schon alle 8 testen. Wüsste aber nicht, ob es noch eleganter geht.

Bye, TGGC \-/

[LiquidAcid]

@Stefan: Wie genau meintest du es denn jetzt? Dass man nur die Extrempunkte (zwei Stück) testen muss, oder anders? Mit den Extrempunkten geht es ja nun (gut ersichtlich) nicht.

@TGGC: Wie willst du denn sonst den Radius der umschliessenden Kugel berechnen, ohne die Länge der Diagonale zu berechnen?

Ich hatte mir schon folgendes gedacht:

Man vergleicht ja den quadrierten Mittelpunktabstand der beiden Kugeln (beim Sphere-Sphere Containment Test) mit dem ebenfalls quadrierten Wert der Radiendifferenz. Dachte dort könnte man irgendwie ansetzen. Aber (a - b)^2 = a^2 - 2ab + b^2 wenn mich meine Mathekenntnisse nicht täuschen. Da hätte man ja die beiden quadrierten Radien aber auch die nicht-quadrierten Werte. Hätte man nur die quadrierten Werte wärs ja einfach, da man sich das Wurzelziehen beim Berechnen der Diagonallänge sparen könnte und einfach auf die quadrierte Länge zurückgreifen könnte. Aber geht ja leider nicht so einfach. *Herrn Binomi eine hauen könnte* *gg*

Jetzt müsste ich wahrscheinlich benchen was schneller geht. Das Testen ob alle 8 Punkte des AABB in der Kugel liegen, oder konstruiere ich doch lieber die Boundingsphere des AABB. Wobei mir das mit der Boundingsphere doch lieber ist.

cya
liquid

[TGGC]

Wie gesagt, diese Methode liefert ohnehin falsche Ergebnisse. Daher eigentlich unnötig sich damit genauer zu beschäftigen.

Aber ist es nicht so:

r1 > r2 + d(r1,r2)
gilt für positive Zahlen genau dann wenn
r1^2 > r2^2 + d(M1,M2)^2

Bye, TGGC \-/

[Stefan Zerbst]

Hi,

stimmt mit zwei Punkten geht es nicht. Der Sphere-Sphere Test dürfte schneller sein, wenn man die Konstruktion der Sphere schnell erledigt oder deren Radius beispielsweise mit der AABB vorberechnet und speichert

Ciao,
Stefan

[LiquidAcid]

TGGC schrieb:

Wie gesagt, diese Methode liefert ohnehin falsche Ergebnisse. Daher eigentlich unnötig sich damit genauer zu beschäftigen.

Welche Method meinst du jetzt? Die mit dem Testen der Min und Max Vektoren? Die habe ich ohnehin schon verworfen. Es geht jetzt nur um die Berechnung der "enclosing sphere" des AABB. Und für diese brauche ich einen Radius der sich aus der Diagonalen des AABB berechnet

TGGC schrieb:

Aber ist es nicht so:

r1 > r2 + d(r1,r2)
gilt für positive Zahlen genau dann wenn
r1^2 > r2^2 + d(M1,M2)^2

Ich sehe jetzt keine Möglichkeit das bei mir anzuwenden. Hilfst du mir auf die Sprünge?

@Stefan: Diesen (prinzipiell kleinen, aber dennoch vorhandenen) Overhead würde ich gerne vermeiden. Wenn es jetzt wirklich eine Möglichkeit gäbe den Vergleich ohne die Kenntnis des einfachen Radius durchzuführen wäre das wahrscheinlich die beste Möglichkeit. Vielleicht kann TGCC ja noch ein paar Informationen zu seinen Überlegungen rausrücken.

cya
liquid

EDIT:
x <= (r^2 + b^2 - 2*r*b)
x : quadrierter Abstand zwischen den Mittelpunkten
r : Radius der Kugel
b : Radius der AABB-Kugel

Wann ist der Ausdruck falsch, wann wahr - möglichst nur mit dem Wissen der quadrierten Werte (x, r^2 und b^2).

[Sgt. Nukem]

r^2 >= r falls r >= 1.0 || r <= 0
b^2 >= b falls b >= 1.0 || b <= 0

[TGGC]

Deine Methode "enclosing sphere des AABB" liefert falsche Ergebnisse.

Ist denn die Bedingung, das Kugel 2 vollständig in Kugel 1 liegt, nicht die oben genannte: Radius 1 ist größer als Radius 2 plus Abstand der Mittelpunkte? Das kann man wie gezeigt ohne Wurzel machen.

Und noch das andere:

x <= r^2 + b^2 - 2*r*b
    x - r^2 - b^2 <= 2*r*b
(x - r^2 - b^2)^2 <= (2*r*b)^2
(x - r^2 - b^2)^2 <= 2^2 * r^2 * b^2

Ich glaub ich weiss jetzt, warum unbedingt sqrt optimiert werden soll.

Bye, TGGC \-/

[LiquidAcid]

Sgt. Nukem schrieb:

r^2 >= r falls r >= 1.0 || r <= 0
b^2 >= b falls b >= 1.0 || b <= 0

OK, das ist selbstverständlich logisch.

TGGC schrieb:

Deine Methode "enclosing sphere des AABB" liefert falsche Ergebnisse.

Kannst du das bitte genauer begründen? Liegt es daran, dass die Kugel die den AABB umschließt größer ist (von Volumen her) als der AABB selbst? Daran habe ich nämlich auch schon gedacht, aber dann dürfte der Test den ich für Sphere in AABB ausgetüftelt habe ja auch nicht gelten (da der "virtuelle" AABB um die innere Kugel ja auch größer ist als die Kugel selbst). Ich stehe ein wenig auf dem Schlauch, merkste sicherlich
Oder ist der Algo des Sphere-Sphere Containment Test falsch und ich habe eine völlig falsche Ausgangslage?

TGGC schrieb:

Ist denn die Bedingung, das Kugel 2 vollständig in Kugel 1 liegt, nicht die oben genannte: Radius 1 ist größer als Radius 2 plus Abstand der Mittelpunkte? Das kann man wie gezeigt ohne Wurzel machen.

Ich poste am besten mal meinen Code für den Sphere-Sphere Containment Test. Kannst du dir ja mal angucken und falls der ansich schon falsch ist mir sagen:

const bool basic_sphere::intersect(const basic_sphere& s) const
{
	const basic_vector centerDiff(s.center - this->center);

	return (centerDiff.sqLength() <= _SQ(this->radius + s.radius));
}

TGGC schrieb:

Und noch das andere:

x <= r^2 + b^2 - 2*r*b
    x - r^2 - b^2 <= 2*r*b
(x - r^2 - b^2)^2 <= (2*r*b)^2
(x - r^2 - b^2)^2 <= 2^2 * r^2 * b^2

Jo vielen Dank, ist mir ja eigentlich schon peinlich, dass ich diese simple Umstellung nicht selber hinbekommen hab.

cya
liquid

[TGGC]

Na ich hab auch ein Minus veschlampt...

Bye, TGGC \-/

[LiquidAcid]

Na, das wird ja sowieso wegquadriert.

[TGGC]

Wegen dem Fehler:
Das die Sphere größer ist, als die AABB ist keine hinreichende Bedingung, das ein Fehler entsteht, aber eine notwendige. Ich kann dir den Fehler beweisen (durch ein Beispiel). Aber das es andersrum immer funktioniert ist schwieriger zu beweisen, das lasse ich.

Wegen dem Test:
Ist doch genau das gleiche, was ich sagte, nur umgeformt.

Bye, TGGC \-/

[LiquidAcid]

TGGC schrieb:

Wegen dem Fehler:
Das die Sphere größer ist, als die AABB ist keine hinreichende Bedingung, das ein Fehler entsteht, aber eine notwendige. Ich kann dir den Fehler beweisen (durch ein Beispiel). Aber das es andersrum immer funktioniert ist schwieriger zu beweisen, das lasse ich.

Ich wäre durchaus an beiden interessiert.

TGGC schrieb:

Wegen dem Test:
Ist doch genau das gleiche, was ich sagte, nur umgeformt.

OK, gut - dann wär das ja schonmal geklärt.

cya
liquid

[LiquidAcid]

@TGGC: Meine Frage besteht weiterhin. Außerdem warte ich noch auf deinen Beweis (oder auch Beispiel).

cya
liquid

[TGGC]

Ohh sorry, das hab ich echt verzockt. Ich schaue immer nur die Beiträge oben mit neuen Sachen an, und hab das wohl übersehen oder so. *duck*

Aber kommt jetzt auf jeden Fall (morgen früh oder so...)

Bye, TGGC \-/