Hi,

ich hab ein kleines problem mit einer CollisionDetection.. nehmen wir an ich habe einen Würfel und eine flache plane und der würfel steckt halb in der Plane drin.

Ich möchte jetzt alle punkte rausbekommen, wo eine Edge (verbindung von 2 benachbarten Vertices) des Würfels die Plane schneidet.

Auf dem Bild hier habe ich mit einem Roten punkt die punkte markiert die ich gern hätte:


Ich hab das ganze im moment über einen Line-Poly-Intersection Algo gelöst, aber das ist bei halbwegs hoch aufgelöster geometrie endlos langsam...

Hat jemand eine idee wie ich das schneller hinbekommen könnte??

Meine einzige idee ist bisher gewesen vor der Line-Poly-Intersection erstmal zu überprüfen ob sich die zwei Polys (bzw. Triangles) überhaupt überschneiden, nur da hab ich leider keine ahnung wie ich das überprüfe

Aya~

Am einfachsten ist es, wenn du die Ebene in Hesse Normalform bringst. Dann wird die Ebene von einer Würfelkante sicher nicht geschnitten, wenn die Vorzeichen des Ergebnisses, das entsteht wenn Du die zwei Randpunkte einer Kante in die Normalform der Ebene einsetzt, gleich sind.

Ist eines der Ergebnisse 0 so, so liegt einer der Punkte in der Ebene. Sind beide 0, so liegt die Kante parallel in der Ebene.

Sind die Vorzeichen unterschiedlich, so kannst du: Durch Einsetzen der Parametrisierten Geradengleichung, die durch die 2 Eck-Punkte beschrieben wird, in die Normalform der Ebene und anschließendes Nullsetzen entsteht ein Lineares Gleichungssystem, welches leicht mit dem Gauss Algorithmus oder ähnlichem schnell lösbar ist.

Klingt schwerer als es ist

Damit das dann nicht zu sehr an der Performance nagt, macht man dann einfach den üblichen Trick, daß man vom Mittelpunkt von Objekten den Abstand zur Ebene durch Einsetzen ders Mittelpunktes in die Hesse Form bestimmt und dann schaut, ob der Abstand nicht sowieso größer ist, als die Maximale Entfernung von Objektvertices zu Objektmittelpunkt.

huhu,

magst du das nochmal ein wenig genauer erklären?

Was ist denn die HesseNormalform? und wie meinst du das mit dem Performance Sparen?? *schaut verwirrt*
Und, das ist nur dazu da zu testen ob sich zwei flächen überschneiden, oder?

Aya~

Hesse Form einer Ebene: n * ( x - a),
wobei n normierter Normalenvektor der Ebene ist und a ein Punkt in der Ebene. Beliebige Punkte x der Ebene erfüllen dann: n* (x-a) =0.
Häufig wird auch verlangt, daß sgn(n*a) = - 1, wobei immer * das Punktprodukt darstellt.

Setzt man einen Punkt in die Gleichung ein, der nicht in der Ebene liegt, so bekommt man als Ergebnis dessen Entfernung von der Ebene und durch das Vorzeichen auf welcher Seite der Punkt liegt.

Ich hab aber so langsam mal wieder den Verdacht, daß du gar nicht mit Ebenen sondern mit beschränkten Flächen arbeiten willst? Dann kann man meine Methode entweder weiterspinnen, um am Ende zu Prüfen, ob die Schnittpunkte mit der Ebene nun auch noch in der gesuchten Fläche liegen... Oder man informiert sich, ob sich da nichts anderes für finden lässt.

Hi ...

http://de.wikibooks.org/wiki/Lineare_Al ... _der_Ebene
da ist auch gleich die Ebene-Punkt Abstandsfrage erklärt.

Ich glaube was Nico mit der Performance-Einsparung meint ist der Test ob dein Objekt überhaupt nah genug dran ist um die Ebene zu schneiden. Siehe dazu Ebene-Punkt Abstandsberechnung. Damit kannst du feststellen wie weit der Mittelpunkt deines Objekts von der Ebene entfernt ist. Wenn dieser jetzt weiter entfernt ist als der Radius der Bounding-Sphere deines Objekts dann kann schonmal keine Überschneidung statt finden und du kannst den Test sehr früh als fehlgeschlagen abbrechen.

Gruß
Shai

[edit]
arg ... zu langsam
[/edit]

_________________
Der Mensch hat neben dem Trieb der Fortpflanzung und dem zu essen und zu trinken zwei Leidenschaften: Krach zu machen und nicht zuzuhören. (Kurt Tucholsky)
Schwabbeldiwapp, hier kommt die Grütze. (Der Quästor)

Wenn esw irklich viele objekte sind, sollten sie sich automatisch in einem Octree einfügen und nur noch die überprüft werrden die sich durdringen könnten. Stat einer Boundingsphere wäre auch ein auf der Manhattandistance basierender Octaeder als vortest denkbar...