4. Containment Test zwischen AABB und Sphere

Containment Test zwischen AABB und Sphere

  • L

    Hiho,

    ich habe eine kleine Frage an euch und zwar bezüglich eines Containment Test. Dabei soll festgestellt werden ob sich eine Kugel innerhalb eines AABB befindet.

    Ich mache bisher folgendes.

    Von den AABB Daten generiere ich folgendermaßen drei Radien.
    x_radius = (maximum.x - minimum.x) / 2
    y_radius = (maximum.y - minimum.y) / 2
    z_radius = (maximum.z - minimum.z) / 2

    Dann berechne ich noch den quadrierten Abstand zwischen dem Mittelpunkt der Kugel und den Mittelpunkt des AABB.
    sq_center_distance = |sphere.center - aabb.center|^2

    Ich dachte mir das jetzt so, dass ich das quasi wie einen Sphere-Sphere Containment Test aufziehe.

    Ich gucke also immer ob der quadrierte Mittelpunktabstand kleinergleich der quadrierten Radiusdifferenz ist.

    Quadr. Radiusdifferenz 1 wäre ja:
    (sphere.radius - x_radius)^2

    Ich müßte also nur testen ob die Bedingung für alle drei Radien (x_radius, y_radius und z_radius) erfüllt ist, dann hätte ich ja raus ob die Kugel im AABB enthalten ist.

    Was meint ihr? Stimmt mein theoretischer Ansatz so? Gibts noch Ansätze zum Optimieren der ganzen Berechnungen, oder liege ich mit meinem Ansatz vollständig daneben??

    cya
    liquid

    PS: Jep, das ist quasi nen Crossposting (für alle die meckern wollen), aber die Version im ZFX Board ist doch nen bissel anders.

    EDIT: Nochwas vergessen. Ich würde auch gern wissen ob das so (wenns überhaupt richtig ist) auch einigermaßen exakt ist, oder ob es Fälle gibt wo der Test versagt und mit Schmu andreht.

    0

  • Nein so klappt das nicht. Das wäre ein Test mit einer Sphere, mit M= Mittelpunkt des AABB und r= min( x_radius, y_radius , z_radius ). Entsprechend auch die Fälle, wo der "Schmu" auffallen würde.

    Bye, TGGC \-/

    0
  • L

    Wie kommst du auf das r = min(...) ?

    cya
    liquid

    EDIT: Hmm, stimmt ja. Schade, muss ich mir was anderes ausdenken.

    0
  • L

    Andere Überlegung:

    Ich berechne ausgehend vom Mittelpunkt der Kugel 3 Intervalle.

    x_interval = <sphere.center.x - radius, sphere.center.x + radius>
    y_interval = <sphere.center.y - radius, sphere.center.y + radius>
    z_interval = <sphere.center.z - radius, sphere.center.z + radius>

    Jetzt teste ich ob jedes Interval innerhalb des AABB liegt.

    Test 1:
    (x_interval[0] >= aabb.min.x) && (x_interval[1] <= aabb.max.x)

    Test 2:
    (y_interval[0] >= aabb.min.y) && (y_interval[1] <= aabb.max.y)

    Test 3:
    (z_interval[0] >= aabb.min.z) && (z_interval[1] <= aabb.max.z)

    Wird hoffentlich nicht noch so ein Reinfall 😃

    cya
    liquid

    0

  • Das sieht schon vernünftiger aus und sollte funktionieren.

    Bye, TGGC \-/

    0
  • L

    OK, thx schonmal an TGCC. Was meinen denn die andere dazu?

    cya
    liquid

    0
  • S

    Hi,

    guckst Du hier: http://www.gamasutra.com/features/19991018/Gomez_4.htm 🙂

    Ciao,
    Stefan

    0
  • L

    Sry Stefan, aber das kannte ich schon und es hat auch direkt nichts mit der Fragestellung zu tun. Überlappen tut die Sphere schon mit dem AABB bevor sie sich in ihm befindet. Auch wenn die Sphere durch den AABB geclipped wird überlappt sie schon.
    Was ich aber wissen wollte ist ob die Sphere IN dem AABB drin ist und zwar vollständig. Der Overlap Test hilft mir hier nicht weiter.
    Außerdem, Gamasutra ist sicherlich eine der erste Seiten die Google beim Thema Intersection Sphere AABB ausspuckt, von daher sollte man annehmen dass der User die Seite auch kennt (ich hätte auch nicht gefragt wenn ich nicht vorher ausgiebig gesucht hätte.

    cya
    liquid

    0

  • Jaja, das sind sie. Erst die Frage nicht ordentlich lesen und dann nur irgendwas hinpasten. 😎

    Bye, TGGC \-/

    0
  • S

    Hi,

    ja wer lesen kann ist klar im Vorteil 🙂

    Was Du oben beschrieben hast ist ja quasi das Erzeugen einer AABB um die Sphere herum und dann ein Test ob diese Sphere-AABB in der anderen AABB enthalten ist. Funktionieren wird das und da es mit simplen Vergleichen auskommt denke ich ist es auch schnell genug.

    Ciao,
    Stefan

    0
  • L

    Allerdings sehe ich dann in dem von dir geposteten Link immer noch keinen Sinn.

    cya
    liquid

    0
  • L

    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

    0
  • S

    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

    0
  • L

    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

    0
  • S

    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

    0

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

    0
  • L

    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

    0

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

    0
  • L

    @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

    0

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

    0
Anmelden zum Antworten