Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Jul 10, 2025 18:39

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 6 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Intersection zwischen zwei Objekten
BeitragVerfasst: Do Aug 24, 2006 21:47 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
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:
Bild

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 :roll:

Aya~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Aug 24, 2006 22:10 
Offline
DGL Member

Registriert: Do Mai 30, 2002 18:48
Beiträge: 1617
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Do Aug 24, 2006 22:42 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
huhu,

magst du das nochmal ein wenig genauer erklären? Bild

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~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Aug 25, 2006 08:22 
Offline
DGL Member

Registriert: Do Mai 30, 2002 18:48
Beiträge: 1617
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.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Aug 25, 2006 08:23 
Offline
DGL Member
Benutzeravatar

Registriert: Di Sep 06, 2005 18:34
Beiträge: 362
Wohnort: Hamburg
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)


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Aug 25, 2006 12:44 
Offline
DGL Member
Benutzeravatar

Registriert: So Jun 04, 2006 12:54
Beiträge: 263
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...


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 6 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 5 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.007s | 14 Queries | GZIP : On ]