# Collision Detection/Prevention bei Drag & Drop



## whitebrazilian (1. Jun 2011)

Hallo,

ich würde gerne in Java 3D Kisten per Drag & Drop verschieben und vor einer Wand absetzen. Dazu benötige ich eben eine Kollisionserkennung die mir sagt, dass dort eine Wand ist und dass man jetzt die Kiste nicht mehr in diese Richtung bewegen kann.
Wie könnte ich sowas denn implementieren? Der CollisionDetector sollte nicht das Problem sein, nur habe ich keine wirkliche Vorstellung wie ich die Bewegung in die "Wandrichtung" dann unterbinde.

Vielen Dank schon mal!


----------



## Evil-Devil (1. Jun 2011)

Du könntest die Kiste rot färben und oder an die letzte mögliche Position setzen bzw. wenn der Nutzer versucht die Kiste abzusetzen an ihren Ursprungsort zurücksetzen.

Ist eher die Frage wie sehr du den User ärgern willst


----------



## whitebrazilian (2. Jun 2011)

Danke, für die Antwort. Meine Frage zielte aber eher darauf ab, wie ich in Java verhindere, dass die Kiste weiter "in Wandrichtung" verschoben werden kann. Dass die Kiste also nicht durch die Wand manövriert werden kann, sondern "diese Bewegungsrichtung" deaktiviert wird.


----------



## Evil-Devil (3. Jun 2011)

Soweit würde ich gar nicht gehen. ALles was den Enduser in einem Editor "einschränkt" ist schlecht. 

Abfangen kannst es imo nur wenn du direkt bei der Auswahl der Box abfragst in welche Richtungen noch Platz zum verschieben ist. Oder das direkt am Objekt-Status im Editor hinterlegst. Dann musst nicht jedes Mal abfragen ob es in die Richtung geht ^^


----------



## whitebrazilian (5. Jun 2011)

Hey,

entschuldige die späte Antwort. Du meinst also, dass ich dem "Kistenobjekt" mitgeben soll in welche Richtung es noch kann, bzw. welche Richtung blockiert ist?
Hättest du da eventuell etwas Pseudo-Code für mich, wie du dir das vorstellen würdest?

MfG,
whitebrazilian


----------



## ChrisKu (6. Jun 2011)

> Du meinst also, dass ich dem "Kistenobjekt" mitgeben soll in welche Richtung es noch kann, bzw. welche Richtung blockiert ist?
> Hättest du da eventuell etwas Pseudo-Code für mich, wie du dir das vorstellen würdest?



Vielleicht habe ich den Lösungsansatz nicht richtig verstanden aber IMHO muss der Status, ob die Kiste in eine bestimmte Richtung verschoben werden kann, doch laufend während der Verschiebung aktualisiert werden. Also im Prinzip während des Verschiebens so:

1. Berechne Position der Kiste ohne die Wand zu berücksichtigen
2. Prüfe auf Kollision mit der Wand
3. Wenn keine Kollision, dann nutze Koordinaten aus 1. für neue Kistenposition, sonst
4. Wenn Kollision dann berechne zulässige Position und weise dieser der Kiste zu.


----------



## whitebrazilian (6. Jun 2011)

Wenn ich die Position immer berechne, dann habe ich ja im Prinzip eine eigene Implementierung der WakeupOnCollisionEntry-Klasse oder?
Ich hätte das jetzt eben über die von Java3D zur Verfügung gestellten Klasse WakeupOnCollisionEntry gemacht, aber da habe ich eben das Problem, dass ich nicht wirklich weiß in welcher Richtung jetzt die Collision auftritt.
Ich bin noch Anfänger in Java3D, man möge mir also bitte verzeihen, wenn ich ab und an Non-Sense schreibe 

Grüße


----------



## ChrisKu (6. Jun 2011)

> Wenn ich die Position immer berechne, dann habe ich ja im Prinzip eine eigene Implementierung der WakeupOnCollisionEntry-Klasse oder?



Hmm, da bin ich mir nicht sicher. Wie implementierst Du denn das dragging der Kiste?


----------



## ChrisKu (6. Jun 2011)

> aber da habe ich eben das Problem, dass ich nicht wirklich weiß in welcher Richtung jetzt die Collision auftritt.



Sorry, stehe wohl gerade auf meiner Leitung. Die Kollision kann doch nur in Richtung der Mauer auftreten. Also, wenn die Mauer z.B. parrallel zur x - Achse steht, kann doch die Kollision nur in z-Richtung auftreten. Oder verstehe ich da was falsch?


----------



## whitebrazilian (6. Jun 2011)

ChrisKu hat gesagt.:


> Hmm, da bin ich mir nicht sicher. Wie implementierst Du denn das dragging der Kiste?



Mit der Mouse-Translate Klasse + einem KeyBahavior. Selbst wäre das dann per Picking und MouseMotionListener möglich oder?


----------



## whitebrazilian (6. Jun 2011)

ChrisKu hat gesagt.:


> Sorry, stehe wohl gerade auf meiner Leitung. Die Kollision kann doch nur in Richtung der Mauer auftreten. Also, wenn die Mauer z.B. parrallel zur x - Achse steht, kann doch die Kollision nur in z-Richtung auftreten. Oder verstehe ich da was falsch?



Also: EIGENTLICH soll ich einen LKW (eine große Box) mit kleinen Boxen beladen. Dazu kann ich ja in der großen Box oben, unten, links und rechts, vorne und hinten anstoßen. Zum einen an der großen Box oder aber an kleinen Boxen, die auch gestapelt werden können. Das heißt ich habe sechs Möglichkeiten wo die Kollision aufgetreten ist.


----------



## ChrisKu (6. Jun 2011)

> Also: EIGENTLICH soll ich einen LKW (eine große Box) mit kleinen Boxen beladen. Dazu kann ich ja in der großen Box oben, unten, links und rechts, vorne und hinten anstoßen. Zum einen an der großen Box oder aber an kleinen Boxen, die auch gestapelt werden können. Das heißt ich habe sechs Möglichkeiten wo die Kollision aufgetreten ist.



Ok, verstehe. 



> Selbst wäre das dann per Picking und MouseMotionListener möglich oder?



Ich denke schon. Du musst dann noch deine x, y coordinaten der Mouse in Deine VW umsetzen und den aktuellen Punkt3d mit dem vorherigen vergleichen um Deinen Transformationsvektor zu bekommen.

Vielleicht hilft Dir hierbei der folgende Link

Of Mice And Men


----------



## whitebrazilian (8. Jun 2011)

Ok, danke für die Antwort, aber das löst ja noch nicht mein Problem mit der Kollision.

Zum Thema MouseMotionListener: Ich kann/soll die große Box auch drehen können. Die Achsen bleiben dabei aber "an Ort und Stelle". D.h. der Benutzer dreht sich ja bei der MouseRotation um die Box, oder?
Jedenfalls kann es dann passieren (Seitenansicht der Box(Start ist bei Rückansicht)), dass, wenn ich die Maus nach links ziehe, die Kiste "auf mich zu kommt". Weil das eben die X-Achse ist, die jetzt, nach der Rotation" auf mich "zuläuft". Ich müsste also interaktiv immer berechnen wo sich der Benutzer befindet und dann den Boxen die Richtung der Verschiebung mitgeben. Das glaube ich ist sehr schwer. Gibt es eine alternative, am besten leichtere, Lösung?
Danke für deine Geduld mit mir


----------



## ChrisKu (8. Jun 2011)

Ich habe an Deinem Problem noch einmal ein bisschen rumgetüftelt und Deinen Ansatz mit MouseTranslate und Behavior verfolgt. Hat geklappt. Dabei habe ich eine Collision Detection Klasse von dieser Seite

Java Tips - Collision Detection with Java3D

etwas modifiziert. Statt des Shape3D habe die TranformGroup meiner "Kiste" (na gut, bei mir war es eine Kugel ;-)). Bei Kollision habe ich dann den Kollisionspunkt "zu  Fuss" ausgerechnet und die Kiste wieder vor die Wand zurück gesetzt.

Vielleicht hilft Dir das weiter?


----------



## whitebrazilian (9. Jun 2011)

Kannst du mir den Code zukommen lassen oder posten?


----------



## ChrisKu (10. Jun 2011)

> Kannst du mir den Code zukommen lassen oder posten?



Im Prinzip kein Problem. Ich habe nur wirklich sehr quick and dirty an einer vorhanden Lern App rumgebastelt - also bitte keine Kommentare über "Coding Style" usw. 

Ich hänge den Code (da er aus 4 Klassen besteht und damit hier den Post etwas sprengt) einfach mal als Anhang unkommentiert dran. Falls Fragen da sind, einfach wieder posten.


----------



## whitebrazilian (11. Jun 2011)

Hey,

zuallerst vielen Dank!
In erster Linie ist mir aufgefallen (abgesehen von einigen Befehlen, die ich noch gehört habe  ), dass die Kollision bzw. die Funktionalität dafür funktioniert, aber in der Konsole der "Hit" bereits bei y=3,7 eintritt, wobei die Kugel da noch weit vom Boden entfernt ist.
Du vergleichst ja hier mit dem Radius der Kugel, das ist sinnvoll und einfach bei einer Kugel. Der Abgleich von Boxen (den ich benötige) scheint mir da schon noch komplexer zu sein... :/

Grüße,
Tobi


----------



## ChrisKu (11. Jun 2011)

Moin,



> in der Konsole der "Hit" bereits bei y=3,7 eintritt, wobei die Kugel da noch weit vom Boden entfernt ist.



Das ist korrekt und mir auch aufgefallen. Es scheint daran zu liegen, dass die BoundingSphere der übergebenen TranformGroup größer ist als die Kugel (der Radius ist 1.97 glaube ich). Frage mich nicht, warum das so ist. Ich habe den Punkt aber erst einmal ignoriert, da er auf die Funktionalität keinen Einfluss hat. Das Rücksetzen  tritt ja erst dann ein, wenn die Kugel wirklich auf dem Boden ist.



> Der Abgleich von Boxen (den ich benötige) scheint mir da schon noch komplexer zu sein..



Im Prinzip ja, zumindestens meisten. Wenn man weiß, wie die Kiste zur Wand steht, ist es genauso einfach. Ich habe die Kugel schon mal durch eine Kiste ersetzt, geht genauso. Nun habe ich aber daran rumgetüftelt, wie man den Funktionalität hinkriegt, wenn man die Kiste auf drehen kann und somit der Winkel zu Wand unbekannt ist. Ich glaube, ich habe die Lösung! Ich mache es mal fertig und poste es dann.


----------



## ChrisKu (11. Jun 2011)

Ich muss zugeben, Du hast hier mit Deinem Thread wirklich eine spannende Kopfnuss in den Ring geworfen  Ich denke, die Funktionalität soll auch dann gegeben sein, wenn die Kiste nicht orthogonal zum Boden steht, sondern auch dann, wenn z.B. gekippt ist.

Der Schlüssel ist die an den Collision Detector übergebene TransformGroup. Sie enthält alle Informationen über Lage, Rotation usw. der Kiste bezogen auf die ursprünglichen Koordinaten. Diese Informationen sind dort allerdings in Matrix Form abgelegt, die Nutzung erfordert also ein bisschen Mathe.

Wie man die Lage eines Punkte berechnet, nachdem eine Transformation (z.B. Verschieben und Rotieren) ausrechnet, findest Du dort:

Transform3D (Java 3D API)

Nun aber zu der Umsetzung:

Nachdem ich die Kiste erstellt habe, habe ich die Eckpunkte der Kiste berechnet und über setUserData() gespiechert. Diese Eckpunkte kann ich dann später bei der Kollisionserkennung verwenden.

Nach der Kollision läuft folgender Algo ab:
1. Die jetzigen Eckpunkte der Kiste berechnen, bezogen auf das ursprüngliche Koordinatensystem. Hierzu hole ich mir aus der übergebenen TransformGroup die Transformationsmatrix und berechne die jetzigen Eckpunkte wie in dem o.a. Link beschrieben
2. Dann prüfe ich, welche Ecke am weitesten "unter" dem Boden liegt. Um diese Distanz muss die Kiste zurück verschoben werden
3. Dann wird es noch mal tricky - den eigentlich einfachen Verschiebungvektor (0, y, 0) muss man noch mal in das neue Koordinatensystem umrechnem denn der Würfel kann ja gekippt sein. Hierzu muss der Vektor (0, y, 0) mit der inversen Transformationsmatrix multipliziert werden. 
4. Dann wird die Kiste zurückgesetzt.

Das Problem, was jetzt noch besteht, ist das der Würfel in den Boden etwas eintaucht. Um das zu verhindern wäre meine Idee, den y - Faktor des MouseTranslate bei Kollision auf 0 zu setzen. Da muss ich mir aber noch ein paar Gedanken zu machen (z.B. was tun, wenn der Boden nicht senkrecht zur y - Achse steht). Mal sehen.

Angehängt ist jedenfalls der geänderte Code, ein paar Kommentare habe ich auch da eingefügt.


----------



## whitebrazilian (14. Jun 2011)

Vielen Dank erstmal!
Das funktioniert ja zunächst mal schon recht gut.
Das Problem ist noch, dass wenn sich der Würfel parallel (also nicht verdreht) zum Boden auf diesem befindet, und man nun dreht, dass sich der Würfel noch unter den Boden senkt. Für MEIN Modell sollte das allerdings reichen, da die Kisten nie gedreht werden, sondern nur um 90° rotiert, alles andere macht bei Beladung wenig Sinn.

Ich werde jetzt mal versuchen die Kollision so anzupassen, dass er alle "Richtungen" erkennt.
Dass die Boxen im späteren Modell eben in einer größeren Box in allen "Himmelsrichtungen" anstoßen können. Dazu muss ich noch erkennen mit welchem Objekt kollidiert wird. Kollidiert die kleine Box am Boden, der Decke oder einer Wand der großen Box (LKW) oder mit einer anderen Box (anderes Ladungsstück), dann muss ich nämlich nicht 0.0 mit pushback vergleichen, sondern die Höhe, Breite Tiefe der kleinen Box.

Grüße,
Tobi

P.S.: Die Methode calTopLeftCorner(Matrix4d mat, double[] corn) wird nie angesprochen. Ich weiß nicht, ob du die an einer Stelle verwenden wolltest...


----------



## ChrisKu (14. Jun 2011)

> Dazu muss ich noch erkennen mit welchem Objekt kollidiert wird



In der "processStimulus()" Methode des CollisionDetectors wird auf das Object, mit kollidiert wurde, zugegriffen ("theLeaf"). Ich habe es nur für meine Propiererei nicht gebraucht.



> P.S.: Die Methode calTopLeftCorner(Matrix4d mat, double[] corn) wird nie angesprochen. Ich weiß nicht, ob du die an einer Stelle verwenden wolltest...



...das sind noch die Überreste der verschiedenen Versuche - ist wahrscheinlich noch mehr überflüssiger Müll im Code 

Viel Erfolg!


----------



## whitebrazilian (14. Jun 2011)

ChrisKu hat gesagt.:


> In der "processStimulus()" Methode des CollisionDetectors wird auf das Object, mit kollidiert wurde, zugegriffen ("theLeaf"). Ich habe es nur für meine Propiererei nicht gebraucht.


Ich würde mir hier jetzt das Transform3D-Objekt und davon den Vektor holen. Den würde ich der reset(Vector3f vec) übergeben.

Bei der Erkennung von welcher Seite ich auf die andere Kiste auftreffe, kann ich mir im Moment nur vorstellen, die Mausbewegung abzufragen, indem ich die vorletzte Position speichere und mit der letzten Vergleiche. Da hätte ich dann die Veränderung einer Position wobei ich nicht weiß was bei schrägem Ziehen der Maus passiert (vllt zwei veränderte Werte).


----------



## ChrisKu (14. Jun 2011)

> Bei der Erkennung von welcher Seite ich auf die andere Kiste auftreffe, kann ich mir im Moment nur vorstellen, die Mausbewegung abzufragen, indem ich die vorletzte Position speichere und mit der letzten Vergleiche. Da hätte ich dann die Veränderung einer Position wobei ich nicht weiß was bei schrägem Ziehen der Maus passiert (vllt zwei veränderte Werte).



Wäre mit Sicherheit eine der Möglichkeiten, wobei das wohl nur "einfach" funktioniert, wenn sich die x/y Ebene der Maus irgendwie im rechten Winkel zu dem Koordinatensystem deiner virtuellen Welt befindet. Sonst muss die Bewegung Deiner Maus in Virtual World Koordinaten umrechnen.

Besteht aber nicht auch eine Möglichkeit, die Richtung der Kollision aus den Kollisionsdaten zu ermitteln? Bei einer Kollision von 2 Kisten ist ja die sich bewegende Kiste "leicht" in die andere Kiste eingedrungen. Ich versuche es mal am Beispiel zu erklären.

2 Kisten kollidieren. Nun prüfst du folgendes ab
1. Befindet sich die am weitesten rechts liegende Ecke der sich bewegenden Kiste in der stehenden Kiste? Wenn ja, dann Kollision von rechts
2. Befindet sich die am weitesten links liegende Ecke der sich bewegenden Kisten in der stehenden Kiste? Wenn ja, dann Kollision von links
3. usw


----------



## whitebrazilian (14. Jun 2011)

ChrisKu hat gesagt.:


> 2 Kisten kollidieren. Nun prüfst du folgendes ab
> 1. Befindet sich die am weitesten rechts liegende Ecke der sich bewegenden Kiste in der stehenden Kiste? Wenn ja, dann Kollision von rechts
> 2. Befindet sich die am weitesten links liegende Ecke der sich bewegenden Kisten in der stehenden Kiste? Wenn ja, dann Kollision von links
> 3. usw



Danke für den Tipp. Laut Google ist diese Abfrage ein mathematisch nicht triviales Problem. Aber ich überlege gerade, ob der Punkt nicht auch wie eine Box einfach abgefragt werden kann, weil er ja auch ein Objekt ist.


----------

