5. [Suchen Autor für:] Kollisionserkennung bei 3D Objekten

[Suchen Autor für:] Kollisionserkennung bei 3D Objekten

  • ?

    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~

    0
  • R

    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 ...

    0
  • ?

    Reyx schrieb:

    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 ...

    Allerdigns wird einem dass von einer Physik-Engine i.d.R. abgenommen.

    Nur selber machen ist lustig 🙂

    0
  • A

    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.

    0
  • P

    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

    http://www.scherfgen-software.net/ Hier gibts ein paar Tuts zu Kollisionen. Aber Vorsicht bei Dreieck-Dreieck, da ist ne Stelle buggy^^

    0
  • M

    MisterX schrieb:

    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~

    die findest du hier http://www.geometrictools.com/

    deswegen wär ein Artikel überflüssig, meiner Ansicht nach.

    0
  • B

    ..

    0
  • B

    ...

    0
  • J

    Andreas XXL schrieb:

    Ebene vs Gerade

    Da ich daran komplett scheitere, wollte ich mal fragen wie du das machst?

    0
  • B

    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

    typedef double coord;
typedef double length;

struct Vector3D{
  coord x,y,z;
  Vector3D(){}
  Vector3D(coord x, coord y, coord z):
    x(x), y(y), z(z){}
};

// 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; 

double sqr(double n){
  return n*n;
}

length sqr_dist(const Point&a, const Point&b){
  return sqr(a.x - b.x) + sqr(a.y - b.y) + sqr(a.z - b.z);
}

length dist(const Point&a, const Point&b){
  return std::sqrt(sqr_dist(a, b));
}

struct Sphere{
  Point center;
  length radius;
};

bool is_collision(const Sphere&a, const Sphere&b){
  return dist(a.center, b.center) <= a.radius + b.radius;
  // oder besser
  // return sqr_dist(a.center, b.center) <= sqr(a.radius + b.radius);
}

bool is_collision(const Sphere&a, const Point&b){
  return dist(a.center, b) <= a.radius;
}

// 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?

    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.

    0
  • J

    Ben04 schrieb:

    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.

    mfg.

    0
  • B

    Eine Ebene kann mit einer Gleichung der Form:
    a_1⋅x+b_1⋅y+c_1⋅z=d_1≡E1a\_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,b3a\_2, b\_2, c\_2, a\_3, b_3 und c3c_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 E2E_2 und man analoges über E3E_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⋅w=0u \cdot w = 0
    u⋅v=0u \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⋅w=0u \cdot w = 0
    u×w=vu \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 d2d_2 und d3d_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.

    0
  • T

    Ben04 schrieb:

    Eine Ebene kann mit einer Gleichung der Form:
    a_1⋅x+b_1⋅y+c_1⋅z=d_1≡E1a\_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).

    0
  • ?

    Hy@all

    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

    noch eine kleine skizze von der situation:
    http://www.hartl-auto.at/uni/raytracing2.jpg

    tVector3 p1q = p1-mP; p1q = p1q / p1q.abs(); // Seitenkante des Dreiecks
tVector3 p2q = p2-mP; p2q = p2q / p2q.abs(); // Seitenkante des Dreiecks
tVector3 p3q = p3-mP; p3q = p3q / p3q.abs(); // Seitenkante des Dreiecks
tMatrix33 tMq = tMatrix33(p1q,p2q,p3q); // Transformationsmatrix von schiefer in normale Basis
tMq = tMq.inverse(); // Transformationsmatrix von normale in schiefe basis
tVector3 tRq = tMq * mV;
if( (tRq.x>=0) && (tRq.y>=0) && (tRq.z>=0) )
    { //Schnittpunkt innerhalb  des dreiecks
    tVector3 nT = (p1-p2)%(p1-p3);     nT=nT/nT.abs();//Normalvektor auf fläche
    float dist = (nT&(mP-p1)); 
    if(dist<0.3f && dist > -0.3f) // wenn abstand kleiner als 3
	{/*KOLLISION*/}
    }

    zur info noch der aufbau der von mir verwendeten stuktur für voktoren und matrizen:

    typedef struct tVector3				
{			
	tVector3() {}	
	tVector3 (float new_x, float new_y, float new_z) 
	{x = new_x; y = new_y; z = new_z;}

	tVector3 operator+(tVector3 vVector)
	{return tVector3(vVector.x+x, vVector.y+y, vVector.z+z);}

	tVector3 operator-(tVector3 vVector) 
	{return tVector3(x-vVector.x, y-vVector.y, z-vVector.z);}

	tVector3 operator*(float number)	
	{return tVector3(x*number, y*number, z*number);}

	tVector3 operator/(float number)
	{return tVector3(x/number, y/number, z/number);}

	tVector3 operator%(tVector3 vVector)//CROSS PRODUKT
	{return tVector3(y*vVector.z-z*vVector.y,z*vVector.x-x*vVector.z, x*vVector.y-y*vVector.x);}

	float operator&(tVector3 vVector)//DOT PRODUKT
	{return x*(vVector.x) + y*(vVector.y) + z*(vVector.z);}

	float abs()
	{return float(sqrt(x*x+y*y+z*z));}
	float abs2()
	{return (x*x+y*y+z*z);}

	tVector3 normalize()
		{
		float a=abs();
		x=x/a; y=y/a; z=z/a;
		return tVector3(x,y,z);
		}

	float x, y, z;						
}tVector3;

typedef struct tMatrix33				
{			
	tMatrix33() {}	

	tMatrix33 (float new_x1, float new_y1, float new_z1,
				float new_x2, float new_y2, float new_z2,
				float new_x3, float new_y3, float new_z3) 
		{
		x1 = new_x1; y1 = new_y1; z1 = new_z1;
		x2 = new_x2; y2 = new_y2; z2 = new_z2;
		x3 = new_x3; y3 = new_y3; z3 = new_z3;
		}

	tMatrix33 (tVector3 v1, tVector3 v2, tVector3 v3)
		{
		x1 = v1.x; y1 = v1.y; z1 = v1.z;
		x2 = v2.x; y2 = v2.y; z2 = v2.z;
		x3 = v3.x; y3 = v3.y; z3 = v3.z;
		}

	tVector3 operator*(tVector3 vec)	
		{
		return tVector3(	x1*vec.x + x2*vec.y + x3*vec.z,
							y1*vec.x + y2*vec.y + y3*vec.z,
							z1*vec.x + z2*vec.y + z3*vec.z);
		}
	float det()
		{
		return (x1*y2*z3) + (x2*y3*z1) + (y1*z2*x3) - (z1*y2*x3) - (y1*x2*z3) - (z2*y3*x1);
		}

	tMatrix33 inverse()
		{
		float d = det();
		return tMatrix33((y2*z3-z2*y3)/d , (y3*z1-z3*y1)/d, (y1*z2-z1*y2)/d,
						(x3*z2-z3*x2)/d, (x1*z3-z1*x3)/d, (x2*z1-z2*x1)/d,
						(x2*y3-y2*x3)/d, (x3*y1-y3*x1)/d, (x1*y2-y1*x2)/d);
		}

	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.....

    0
  • ?

    Ben04 schrieb:

    Entweder Ebene und Gerade sind parallel oder sie schneiden sich.

    Falsch!

    0
  • B

    Kenner des 5D schrieb:

    Ben04 schrieb:

    Entweder Ebene und Gerade sind parallel oder sie schneiden sich.

    Falsch!

    Lies doch mal die Überschrift:"...bei 3D Objekten"

    0
Anmelden zum Antworten