Hej!

Sitter på ett problem som inte borde vara så knepigt eftersom det känns tämligen grundläggande men som jag inte lyckas lösa trots att Google gått på högvarv och jag snart ryckt av alla hårstrån på huvudet...

Jag håller på med ett enkelt 3D-spel (i C# med Direct3D) och har nu kommit till kollisionshanteringen. Det objekt som ska krocka är inbakat i en "bounding box" d.v.s. ett simpelt box-element vars enda syfte är att ringa in min komplexa figur med åtta noder för att underlätta kollisionsdetekteringsberäkningarna.

För att modellera rummet min figur befinner sig i använder jag mig av insidan ett egenskapat objekt med inverterade normaler (d.v.s. byggt av polygoner som alla pekar inåt istället för utåt). Att skapa enskilda väggar av andra bounding boxar känns inte aktuellt, då jag skulle behöva modifiera alldeles för mycket kod i baneditorn.

För varje "steg" objektet rör sig kontrollerar jag om någon av punkterna i dess bounding box på vägen har passerat något plan, och i så fall vill jag studsa objektet. Problemet jag nu stött på är att jag inte kommer ifrån att beräkningen sker just mot ett plan - jag vill ju egentligen begränsa kollisionskollen till rummets polygoner. Det resulterar i att objektet studsar fint mot en av väggarna i rummet, men när det vänder och ska passera genom en dörröppning registreras en krock med ett av planen (en av polygonerna) som spänner upp väggen bredvid dörröppningen. Så, detta är min fråga: Hur kollar jag om krocken verkligen sker inom ramen för polygonen och inte bara mot det i storlek obegränsade planet?

Vid kollisionstillfället finns diverse vektorer tillgängliga att använda för min beräkning av huruvida kollisionen verkligen skett med en polygon. Har t.ex. samtliga noder (för både bounding boxen och polygonen i rummet som krocken sker med) tillgängliga och kan ju med hjälp av dessa efter att figuren rört sig minst ett steg beräkna en riktningsvektor. Det känns som att jag ska använda denna på något sätt, men jag har som sagt inte lyckats klura ut exakt hur. En googling på t.ex. "Intersection between ray and polygon" ger många träffar, men mina försök att dekryptera dessa har misslyckats. Det var något år sedan jag läste senaste mattekursen med skalärprodukter, determinanter och sånt skoj. :)

Har hört mycket gott om detta forum. Upp till bevis! :)

Edit: Lade märke till att det även finns ett forum för "matte/fysik/beräkna". Vet inte om detta inlägg kanske hör hemma bättre där?

Hmm, borde det inte vara så att du ska testa alla polygonens vertex mot "bounding box" och undersöka om någon av dessa hamnar innanför "bounding box", iså fall ska det studsas, annars är det bara att fortsätta.

Mvh

Johan Lindfors
Microsoft AB

Johan Lindfors: Jag är inte hundra på exakt hur du menar, men innebär inte det att ett objekt kan åka emellan två hörn?

Typ att följande:

<code>
'----------------
'| | /'
'| |/
'| /|
'| / | /
'| \| /
'| |\ /
'| | \/
'----------------
</code>

inte kommer räknas som en krock?

Johannes: Om jag har tänkt rätt där så är nog principen följande:
1. Du har 12 stycken kanter (alltså linjer) i din bounding box.
2. Du kollar varje linje mot den polygon du kommer krocka mot (ev. lite optimeringsmöjligheter här, men du fattar).
3. Då får du fram 12 kollisionspunkter.
4. Först kollar du så att punkterna sitter på bounding-boxen, det blir ju ganska enkelt. De som inte är med är ointressanta.
5. Sen kollar du så att punkterna som är kvar också sitter i polygonen. Det gör du via orientering som du ganska lätt får ut med vektorprodukten. Om polygonen är en triangel ABC och kollisionspunkten är en punkt D så är principen något i stil med att du bildar vektorprodukten av DA och DB, DB och DC, DC och DA, och då ska alla ha samma tecken. Om polygonen är konvex tror jag att du klarar det om du gör det i rätt ordning. Är den inte konvex så får du göra en triangulering av den.

Detta är hur det funkar matematiskt. Vad som finns i Direct3D som kan underlätta är tyvärr inget jag vet.

En annan variant som ofta är enklare är faktiskt att istället skapa en bounding sphere.

EDIT: Vetefan varför min elegenta ascii-art inte funkar. code-taggen verkar vilja flytta om texten.

Är dina polyedrar (bounding box) alltid konvexa?

Niklas: Du har rätt, "tänkte inte på det"...

Så då fortsätter jag: Om det redan gjorts en kollision-detektion mot ett plan (enligt första inlägget) och det verkar ha uppstått en kollision så är väl det endast en kollision om inte alla polygonens vertex befinner sig på samma sida om bounding box? Är jag tillräckligt otydlig?

Jag vill så gärna komma på en enkel lösning på detta... :)

Mvh

Johan Lindfors

<b>Det objekt som ska krocka är inbakat i en "bounding box" d.v.s. ett simpelt box-element vars enda syfte är att ringa in min komplexa figur med åtta noder för att underlätta kollisionsdetekteringsberäkningarna.</b>

Förstår jag rätt att det räcker att kolla om två rätblock kolliderar?

Ett rätblock spänns upp av tre intervall, ett i var dimension. Två rätblock överlappar (kolliderar) om respektive intervall i var dimension överlappar. Två intervall (a1, b1), (a2, b2) överlappar varandra om max(a1, a2) < min(b1, b2).

Alltså, om de två rätblocken spänns upp av intervallen (ax1, bx1), (ay1, by1), (az1, bz1) resp (ax2, bx2), (ay2, by2), (az2, bz2), kolliderar de om max(ax1, ax2) < min(bx1, bx2) och max(ay1, ay2) < min(by1, by2) och max(az1, az2) < min(bz1, bz2).

Men detta enbart om själva väggarna verkligen är "axel-parallella" rätblock. Annars kommer man få oönskade kollisioner.

Ledsen att jag inte har hunnit ge feedback på era svar, ni ska dock veta att de är väldigt uppskattade. Jag kommer att höra av mig så fort jag testat de olika metoderna.

Efter en tids uppehåll har vi nu åter kommit igång med arbetet för att slutföra det här lilla spelet. Och det ursprungliga problemet kvarstår tyvärr, trots uppskattade inlägg i denna tråd. Vi har sedan tidigare försökt lösa det med en metod väldigt lik Niklas Janssons här ovan ("Om polygonen är en triangel ABC och kollisionspunkten är en punkt D så är principen något i stil med att du bildar vektorprodukten av DA och DB, DB och DC, DC och DA, och då ska alla ha samma tecken.") men det har fallit på att vektorprodukten inte kan skilja på om vinkeln är mer än 180 grader eller inte (då det ju är cos-värdet man får ut). Några tips om detta?

Har faktiskt av en ren händelse börjat med ett litet hobbyprojekt själv, där jag använder nämnda grejer.

Metoden jag sa först funkar, kommer inte ihåg om det är någon twist med den, men annars är det väl bara att kolla på normalen för att se om det är åt rätt eller fel håll?

Hur som helst, jag har hittat en annan lösning, som ska vara lite snabbare. Kommer tyvärr inte ihåg var. Koden (C++) ser ut som följer:

inline bool inside_triangle(point p, tri t)
{
    // Compute vectors
    point v0 = t.p3 - t.p1;
    point v1 = t.p2 - t.p1;
    point v2 = p - t.p1;

    // Compute dot products
    double dot00 = dot_prod(v0, v0);
    double dot01 = dot_prod(v0, v1);
    double dot02 = dot_prod(v0, v2);
    double dot11 = dot_prod(v1, v1);
    double dot12 = dot_prod(v1, v2);

    // Compute barycentric coordinates
    if (fabs(dot00 * dot11 - dot01 * dot01) < 0.001)
        return false;
    double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    double v = (dot00 * dot12 - dot01 * dot02) * invDenom;

    // Check if point is in triangle
    return (u > 0) && (v > 0) && (u + v < 1);
}

Underbart, Niklas, du är min hjälte! Tack. :) Provade att skriva om C++-koden i C# och det fungerade ypperligt.