4. Containment Test zwischen AABB und Sphere

Containment Test zwischen AABB und Sphere


  • 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 \-/

    0
  • L

    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

    0

  • Na ich hab auch ein Minus veschlampt...

    Bye, TGGC \-/

    0
  • L

    Na, das wird ja sowieso wegquadriert.

    0

  • 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 \-/

    0
  • L

    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

    0
  • L

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

    cya
    liquid

    0

  • 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 \-/

    0
  • L

    Thx schonmal im voraus, wär mir echt wichtig.

    cya
    liquid

    0

  • Also erstmal das Beispiel:
    Wir haben einen Quader mit Mittelpunkt bei (1;0;0), die Kantenlängen seien (2;10;2). Eine Kugel mit Mittelpunkt (0;0;0) und Radius sqrt( 2^2 + 5^2 + 1^2 ) umschliesst diesen Quader. Dies kannst du einfach nachprüfen, indem du alle acht Ecken überprüfst. Die Kugel um diesen Quader hätte den Radius sqrt( 1^2 + 5^2+ 1^2 ). Es ist leicht einzusehen, der Punkt mit der höchsten X-Koordinate der Kugel ist ( 1 + sqrt( 1^2 + 5^2+ 1^2 ), 0, 0 ). Dieser Punkt hat zu (0;0;0) den Abstand 1 + sqrt( 1^2 + 5^2+ 1^2 ) und liegt so außerhalb der ersten Kugel.

    Bei dem anderen, kann ich dir evtl. einen Denkanstoß für den Beweis geben. Wenn deine Kugel gerade noch in der AABB ist und sie berührt, so geschieht dies an einem von 6 Punkten (oben/unten/links/rechts/hinten/vorn), dort ergeben sich 6 Tangentialebenen. Die AABB liegt "innerhalb" dieser Tangentialebenen, fügt also keine Punkte hinzu, die beim Berühren der Kugel schon ausserhalb sind.

    Bye, TGGC \-/

    0
Anmelden zum Antworten