Praktikum 3: Schnitttest AABB/AABB

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Praktikum 3: Schnitttest AABB/AABB

Beitrag von arne.lottmann »

Hi,

eine Frage zum Schnitttest zwischen zwei AABBs: gilt eine Berührung bereits als Überschneidung? Also z.B.
  • Box a: min(0,0,0), max(1,1,1)
  • Box b: min(0,0,1), max(1,1,2)
Dabei fängt b praktisch da an, wo a aufhört. Wir interpretieren momentan eine Berührung dieser Art nicht als Schnitt, weil sonst z.B. beim Einfügen in den Octtree Box a in allen acht Oktanten (des Gesamtraums) eingefügt werden würde (da alle acht Oktanten den Mittelpunkt (0,0,0) berühren).

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von mw1039 »

Es ist in der Tat am besten, wenn man eine Beruehrung nicht als Schnitt behandelt. Wenn man z.B. ein triangle mesh hat, beruehren sich die meisten dreiecke, dann waere die szene nicht mehr disjunkt und das rekursive einfuegen in den baum wuerde u.U. nicht mehr terminieren.

Pflücker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 129
Registriert: 21. Sep 2010 14:27

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von Pflücker »

Das dürfte aber doch zu einem Fehlverhalten führen, wenn zwei Dreiecke beispielsweise auf derselben Ebene liegen und sich trotzdem überlappen?
Beispielsweise:
1: (0,0,0), (1,0,1), ( 2, 0, 0)
2: (0,0,0), (2,0,1), (2, 0, 0)

Faktisch könnte man auch zweimal ein solches Dreieck mit denselben Koordinaten produzieren, was zum selben Verhalten führen sollte... Man müsste also an dieser Stelle wirklich abfragen, ob sich die Dreiecke explizit nur an Kanten berühren bzw. ein Dreieck das andere nur mit seiner Kante berührt usw...

Kann jetzt natürlich sein, dass ich mich irre, aber mit einer Annäherung der (obigen) Dreiecke mittels eines AABB haben beide entstehenden Boxen also in Y-Richtung eine Tiefe von 0, womit sie sich also nicht mehr schneiden würden, wenn man es wie vorgeschlagen umsetzt ;)

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von arne.lottmann »

Dreiecke durch Boxen anzunähern ist doch sowieso nur "den Studenten zuliebe", damit wir uns nicht noch mit komplizierteren Schnitttests rumschlagen müssen. Als zweidimensionale Objekte in einem dreidimensionalen System sind die mir sowieso suspekt :). Ebenen kann ich ja irgendwo noch verstehen, aber dreiecke sind da doch etwas…"flach" :p.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von mw1039 »

arne.lottmann hat geschrieben:Dreiecke durch Boxen anzunähern ist doch sowieso nur "den Studenten zuliebe", damit wir uns nicht noch mit komplizierteren Schnitttests rumschlagen müssen.
Genau :p
In einer realen Anwendung wuerde man Dreiecke natuerlich nicht so grob annaehern, aber es ergibt einfach didaktisch wenig Sinn 100 unterschiedliche Schnitttests implementieren zu muessen.

daehn
Erstie
Erstie
Beiträge: 16
Registriert: 5. Okt 2010 13:42

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von daehn »

Könnte es sein, dass der gegebene Pseudocode auf dem Aufgabenblatt dieses Verhalten (Berühren zählt nicht als Schneiden) nicht aufweist? D.h. dort ist es doch so, dass aufgrund der echten größer-Relation schon gleiche Punkte als Überschneiden zählen oder versteh ich da was falsch?
lg

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von arne.lottmann »

Genau deswegen hab ich ja nachgefragt ;).

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von kbraden »

mw1039 hat geschrieben:Es ist in der Tat am besten, wenn man eine Beruehrung nicht als Schnitt behandelt.
Gilt das allgemein (bspw. auch fuer Plane vs. Ray, wenn der Ray in dem Plane liegt)?

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 172
Registriert: 6. Okt 2011 15:25

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von Thomas Huxhorn »

Ich checks nicht.
Wenn ich ein Strahl entlang einer Seite vom der Box führe, dann schneidet er die Seite nicht.
Also Strahl liegt in Ebene -> kein Schnitt.
Aber der Strahl durchquer die fordere und hintere Ebene der Box, wenn auch ganz am Rand. Hier hab ich ein Schnitt.
Was denn nun? :(

An den Kanten überlappen sich die Seiten eben. Wenn sie das nicht tun würden, könnte ein Stahl der genau Diagonal
durch die Box geht nicht erkannt werden.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von mw1039 »

Generell muesst ihr gucken, was im Sinne des Anwendungsfalls sinnvoll ist.
Die Testcases fuer die Schnitttests enthalten diesen Grenzfall nicht. Was beim Einfuegen in den Octree am sinnvollsten ist, muesst ihr selbst entscheiden.
Thomas Huxhorn hat geschrieben:Wenn ich ein Strahl entlang einer Seite vom der Box führe, dann schneidet er die Seite nicht.
Ja, das ist ok so.
Thomas Huxhorn hat geschrieben:Aber der Strahl durchquer die fordere und hintere Ebene der Box, wenn auch ganz am Rand. Hier hab ich ein Schnitt.
Hier musst du auch nicht zwingend true zurueckgeben. false waere auch ok.

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von studypad »

Wir haben jetzt zwei Methoden uns überlegt, die aber die selbe Grundlage verwenden:

Schneiden von AABB AABB generell -> Berührung auch Schnitt return true
Schneiden von AABB in Octree -> Berührung nicht Schnitt return false

Das ist dann für den Spezialfall wenn ein Object z.b. in (0,0,0) anfängt. Wenn die Beführung nicht als Schnitt zählt sortiert man dieses dann nicht in alle acht Unteroctrees..

Ist das so erlaubt???

Danke

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Praktikum 3: Schnitttest AABB/AABB

Beitrag von mw1039 »

Wie gesagt sind die Testcases nicht so spezialisiert. Aber das klingt auf jeden Fall sinnvoll.

Der pathologische Fall fuer deine Octreeloesung waere dann zwar eine AABB mit Kantenlaengen von 0. Die wuerde dann in keinem der Kinder eingefuegt werden. Aber solche Spezialfaelle sind glaube ich nicht so realistisch.

Antworten

Zurück zu „Archiv“