Schön währe ein Artikel zur Kollisionserkennung. Also so ne classe die Jedes mit Jedem Testen kann.
Ne Erklährung der dahinterstehenden Ideen währe auch schön.
Punkt
Kugel
Linie
Strahl
Würfel
Quader
Zylinder
Ebene
Dreieck
Vielecke
Kegel ?
Pyramiede ?
usw.
Schließlich bracht man sowas häufiger, wenn man sich mit 3D Grafik beschäftigt.
Und ich habe im Netzt noch keine WIRKLICH brauchbare Sammlung gesehen
(Nur hier mal das eine und dort das andere)
edit by GPC: Vernünftigen Titel gesetzt und 'n Autorengesuch draus gemacht
Zuletzt bearbeitet von estartu am 14:26:10 14.01.2008, insgesamt 3-mal bearbeitet
Das Problem ist, dass das vermutlich entweder ein sehr theoretischer Artikel werden würde, oder aber sich auf eine bestimmte Bibliothek konzentrieren würde (OGL, DX, whatever).
2D ist ja kein Problem, aber bei 3D ... Allerdigns wird einem dass von einer Physik-Engine i.d.R. abgenommen.
Interessant fände ich es aber schon ...
Zuletzt bearbeitet von Reyx am 10:06:53 13.08.2006, insgesamt 1-mal bearbeitet
Das Problem ist, dass das vermutlich entweder ein sehr theoretischer Artikel werden würde, oder aber sich auf eine bestimmte Bibliothek konzentrieren würde (OGL, DX, whatever).
2D ist ja kein Problem, aber bei 3D ... Allerdigns wird einem dass von einer Physik-Engine i.d.R. abgenommen.
Interessant fände ich es aber schon ...
Warum ne Bibliothek?
3 Vectoren bestimmen nen Dreieck
2 Dreiecke kollidieren (Beispielcode) usw.
Da braucht man keine Bibliotheken. Denn so ne Vectorclasse währe schnell gemacht. Aber hinter den Kollisionen steckt mehr Mathematik ...
C/C++ Code:
Allerdigns wird einem dass von einer Physik-Engine i.d.R. abgenommen.
C/C++ Code:
Allerdigns wird einem dass von einer Physik-Engine i.d.R. abgenommen.
C/C++ Code:
Allerdigns wird einem dass von einer Physik-Engine i.d.R. abgenommen.
Das würde mich auch Interessieren. Die Vectorclasse würde ich jka noch selber zusammenfrickeln können und auch die einfachen Kollisionen wie z.B.
Kugel vs Kugel
Ebene vs Gerade
Aber die komplizierteren währen schon interessant.
Vor allem wenn man das Rad nicht immer neu erfinden will, sondern eine Klasse mit gut durchdachtem code hätte mit Kommentaren, die ETWAS die Idee dahinter beschreiben würde.
Was heißt Idee dahinter?
Um die Objekte zu erkennen, wenn du eine Basisklasse hast benötigst du Double-Dispatching. Gibts verschiedene Möglichkeiten zu(siehe z.B. Effektiv C++ oder Modernes C++ Design).
Der Rest ist dann reine Mathematik. Da hilft dann u.U. der alte Mathehefter
Schön währe ein Artikel zur Kollisionserkennung. Also so ne classe die Jedes mit Jedem Testen kann.
Ne Erklährung der dahinterstehenden Ideen währe auch schön.
Punkt
Kugel
Linie
Strahl
Würfel
Quader
Zylinder
Ebene
Dreieck
Vielecke
Kegel ?
Pyramiede ?
usw.
Schließlich bracht man sowas häufiger, wenn man sich mit 3D Grafik beschäftigt.
Und ich habe im Netzt noch keine WIRKLICH brauchbare Sammlung gesehen
(Nur hier mal das eine und dort das andere)
edit by GPC: Vernünftigen Titel gesetzt und 'n Autorengesuch draus gemacht
Würde mich auch interessieren. Vor allem wie man das gut realisiert. Ich würde da mit Doubledispatching vorgehen und dann alle Kombinationen durchgehen. Geht wahrscheinlich mit einer gescheiten Klassenhierarchie aber besser und man muss nicht alle Kombinationen durchnehmen.
Vielleicht auch einfach statisches Funktionsüberladen einsetzen. Eine Physikengine müsste es wahrscheinlich anders machen aber für diesen Artkiel müsste das andere doch völlig reichen. In etwa so
// Vielleicht ganz ohne Vektorklasse un nur Point + Translation?
// Würde dennen die nicht so gewandert in den Mathebegriffen sind wahrscheinlich
// viel helfen. typedef Vector3D Point;
typedef Vector3D Translation;
// Kommt immer als letztes dran template<class Shape1, class Shape2>
bool is_collision(const Shape1&s1, const Shape2&s2){
return is_collision(s2, s1);
}
// Vielleicht ganz ohne Vektorklasse un nur Point + Translation?
// Würde dennen die nicht so gewandert in den Mathebegriffen sind wahrscheinlich
// viel helfen. typedef Vector3D Point;
typedef Vector3D Translation;
// Kommt immer als letztes dran template<class Shape1, class Shape2>
bool is_collision(const Shape1&s1, const Shape2&s2){
return is_collision(s2, s1);
}
// Vielleicht ganz ohne Vektorklasse un nur Point + Translation?
// Würde dennen die nicht so gewandert in den Mathebegriffen sind wahrscheinlich
// viel helfen. typedef Vector3D Point;
typedef Vector3D Translation;
// Kommt immer als letztes dran template<class Shape1, class Shape2>
bool is_collision(const Shape1&s1, const Shape2&s2){
return is_collision(s2, s1);
}
Die Mathematik ist mir größtenteils bekannt allerdings ist bestimmt interessant für die die sie noch nicht kennen. Grundwissen in der Vektor-Mathematik müsste doch aber vorhanden sein oder?
Man wird auch ein Paar gute 3D Graphiken brauchen. Kennt da jemand ein gutes Programm?
Zitat:
Da ich daran komplett scheitere, wollte ich mal fragen wie du das machst?
Entweder Ebene und Gerade sind parallel oder sie schneiden sich. Wie man das am besten testet hängt davon ab wie du deine Gerade und deine Ebene Strukturen definiert hast.
Zuletzt bearbeitet von Ben04 am 23:30:09 09.01.2007, insgesamt 1-mal bearbeitet
Entweder Ebene und Gerade sind parallel oder sie schneiden sich. Wie man das am besten testet hängt davon ab wie du deine Gerade und deine Ebene Strukturen definiert hast.
Mich interessiert vor allem das Ausrechnen der Schnittposition. Meine Ebene ist halt eine rechteckige Oberfläche und für die Gerade ist es eher egal.
Eine Ebene kann mit einer Gleichung der Form:
§a_1 \cdot x + b_1 \cdot y + c_1 \cdot z = d_1 \equiv E_1§
dargestellt werden. Eine Gerade als Schnittpunkt von zwei nicht parallelen Ebenen:
§\left\{ \begin{array}{ll}
a_2 \cdot x + b_2 \cdot y + c_2 \cdot z = d_2 \equiv E_2\\
a_3 \cdot x + b_3 \cdot y + c_3 \cdot z = d_3 \equiv E_3
\end{array} \right§
Die Schnittstelle der Geraden und der Ebene ist die Lösung des Gleichungssystems:
§\left\{ \begin{array}{ll}
a_1 \cdot x + b_1 \cdot y + c_1 \cdot z = d_1\\
a_2 \cdot x + b_2 \cdot y + c_2 \cdot z = d_2\\
a_3 \cdot x + b_3 \cdot y + c_3 \cdot z = d_3
\end{array} \right§
Der schwierige Teil wird wohl sein die Gerade als Schnittpunkt von zwei Ebenen zu schreiben. Versuchen wir zuerst §a_2, b_2, c_2, a_3, b_3§ und §c_3§ zu bestimmen. Da §v = \[ \left( \begin{array}{ccc}a_2\\b_2\\c_2\end{array} \right)\]§ einen Vektor darstellt der rechtwinklig zur Ebene §E_2§ und man analoges über §E_3§ sagen kann, müssen wir also nur zwei Vektoren v und w suchen die rechtwinklig zur Geraden und nicht parallel unter sich sind.
Da wir unsere Gerade höchstwahrscheinlich als Gerade durch 2 Punkte definiert haben sollte es leicht sein einen parallelen Vektor zu finden (gibt ein Fachwort für so einen, kenne aber nur die französische Version und glaub kaum, dass die dir weiter hilft ). Wir müssen nur die Differenz rechnen. Nennen wir diesen Vektor u.
Um die Rechtwinkligkeit auszudrücken benutzen wir das Skalarprodukt.
§u \cdot w = 0§ §u \cdot v = 0§
Da wir aber noch zusätzlich v nicht parallel zu w haben müssen und wir nur eine und nicht alle Lösungen brauchen würde ich es ein wenig strikter formulieren:
§u \cdot w = 0§ §u \times w = v§
w bestimmen wir indem wir drei Variablen einsetzen, das Skalarprodukt ausrechnen und dann irgendeinen möglichen Vektor w nehmen.
Jetzt müssen wir nur noch §d_2§ und §d_3§ bestimmen. Dies ist aber einfach da wir 2 Punkte der Geraden kennen §\[ \left( \begin{array}{ccc}x_1\\y_1\\z_1\end{array} \right)\]§ und §\[ \left( \begin{array}{ccc}x_2\\y_2\\z_2\end{array} \right)\]§
Nun sind uns aber auch die Koeffizienten bekannt also haben wir ein Gleichungssystem mit zwei Unbekannten:
§\left\{ \begin{array}{ll}
a_2 \cdot x_1 + b_2 \cdot y + c_2 \cdot z_1 = d_2\\
a_3 \cdot x_2 + b_3 \cdot y_2 + c_3 \cdot z_2 = d_3
\end{array} \right§
Wichtig ist zu beachten, dass es eine Gerade nicht Schnittpunkt von genau zwei Ebenen ist, sondern es gibt unendlich viele die sich in der gleichen Geraden schneiden.
Alternative Methode:
Man errechnet die Ebene die rechtwinklig zur gegebenen ist und die gegebene Gerade enthält. Man projektiert Ebene und Gerade darauf. Nun sind wir im 2 dimensionalen Raum und haben zwei Geraden. Wenn der Schnittpunkt gefunden ist muss man nur noch den Schritt zurück in den 3 dimensionalen Raum machen. Dazu muss man nur eine Bijektion zwischen Ebene und 2 dimensionalen Raum aufstellen.
Zuletzt bearbeitet von Ben04 am 23:22:25 10.01.2007, insgesamt 1-mal bearbeitet
Eine Ebene kann mit einer Gleichung der Form:
§a_1 \cdot x + b_1 \cdot y + c_1 \cdot z = d_1 \equiv E_1§
dargestellt werden. Eine Gerade als Schnittpunkt von zwei nicht parallelen Ebenen: (...)
Viel zu umständlich!
Eine Gerade lässt sich viel einfacher als Startpunkt und Richtung schreiben.
Dann ist die Kollision zwischen Gerade und Ebene ein Witz (1 Gleichung mit 1 Variable).
da ich selbst nicht die finger davon lassen konnte, wollte ich unbedingt mal anfangen eine 3D umgebung für ein computerspiel zu entwickeln, in dem man einen character in einer abgeschlossenen 3D Umgebung bewegen kann.
mit: OpenGL, Visual C++, Milkshape Models
ein teilproblem war die kollisionserkennung des characters mit der umgebung beim bewegen;
alle flächen werden als dreiecke, von denen ich die eckpunkskoordinaten (p1,p2,p3) habe, dargestellt.
die problemstellung in etwa:
wenn sich character von seiner aktuellen position in richtung seines blickvektors bewegt, tritt dann eine kollision mit der umgebung auf oder nicht.
lösungsansätze:
-> baryzentrische koordinaten: also schnittpunkt zwischen geraden und ebene errechnen; und wenn der schnittpunkt innerhalb des dreiecks liegt, ist die summe der baryzentrischen koordinaten des Schnittpunktes = 1.
dieser lösungsansatz lässt sich mit dem gewissen theoretischen know how auf fast alle kollisionsprobleme im beliebig-dimensionalen raum anwenden.
leider fehlt mir das theoretische know how über diese darstellung, dass ich es leider (noch) nicht geschafft habe diesen lösungsansatz zu implementieren.
-> basistransformation:
es wird eine neue verzerrte und verdrehte basis im 3D-Grundraum geschaffen, welche als ursprung die position des characters hat, und als basisrichtungen die richtungen von der charakterposition zu den eckpunkten des dreiecks.
aus den basisvektoren bildet man eine transformationsmatrix, mit welche wir beliebige vektoren als koordinaten unserer selbst geschaffenen basis darstellen können.
nun wird der blickvektor des charakters in diese basis transformiert, und mittels größenvergleich der einzelnen koordinaten festgestellt, ob der blickvektor innerhalb des dreiecks zeigt (sind alle koordinaten >= 0 dann ist dies der fall).
Hier nun der Code zur Kollisionserkennung mit Basistransformation:
als gegeben ist p1,p2,p3,mp, und mV anzusehen:
p1,p2,p3 ... Ortsvektoren der Eckpunkte des Dreiecks
mP ......... Position des Characters absolut
mV ......... Blickrichtungsvektor des Characters
float x1, x2, x3; // float y1, y2, y3; // MATRIX LOOKS LIKE THIS float z1, z2, z3; //
}tMatrix333;
ich hoffe ich konnte damit vielleicht irgendwem helfen, der so wie ich gestern, auf der suche nach einfachen kollisionserkennungsmethoden für gerade/dreieck ist...
ich bin leider sehr ungeübt in c++, und habe auch kaum erfahrung damit, deshalb entschuldige ich mich hier gleich mal für das was ich mit meinen code so manchem leser antue!!
mfg HH
p.s.: habe auch noch einen ähnlichen algorithmus zur bestimmung des maximalen abstandes eines raumpunktes entlang eines richtungsvektors bis zur kollision!
(diesen hab ich dann für die kamerapositionierung verwendet)....
wenn wer interessiert sein sollte.....
Kenner des 5D
Unregistrierter
Kenner des 5D Unregistrierter
21:24:29 14.03.2008 Titel:
Nächstes Thema anzeigen Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben. Sie können auf Beiträge in diesem Forum antworten. Sie können Ihre Beiträge in diesem Forum nicht bearbeiten. Sie können Ihre Beiträge in diesem Forum nicht löschen. Sie können an Umfragen in diesem Forum nicht mitmachen.
c++.de ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums
für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de
Werbekostenerstattung verdient werden kann.
Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info, www.c-sar.de, www.c-plusplus.net und www.baeckmann.de
enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt
(vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in
privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden.
Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere
übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.
Twitter
Facebook
). Wir müssen nur die Differenz rechnen. Nennen wir diesen Vektor u.
