[OpenGL] Collision Detection

[The - DDD]

Voor school ben ik dus bezig met een 3D zelfstudie project.

En nu ben ik dus al een tijdje aan het aan kloten met Collision detection.

Ik wil eerst bounding box detection aan de praat hebben, omdat ik daarmee bijna al mijn objecten op botsingen kan scannen. Poly detection kom ik later wel aan toe.

En nu zit ik dus te dubben hiermee. Echt ik wordt er gek van. Ik ben inmiddels zover dat ik door heb dat ik ervoor moet zorgen dat mijn objecten in dezelfde coordinaat ruimte zitten. (liefst in World space)

De theorie snap ik wel aardig, maar probeer het dan maar is in de praktijk de implementeren.

Ik heb al aardig wat lopen zoeken en kan maar geen voorbeelden vinden. De tutorial heb ik doorgenomen, hij helpt zeker, maar ik wil nog wat meer voorbeelden zien te vinden. En dat lukt dus niet.

Heeft iemand toevallig nog een eenvoudig appje liggen met collision detection waar ik de source van mag bekijken? Of weet iemand nog een goeie link hierover?

(ik heb thuis Alan Watt's 3D graphics er ook al op na geslagen, maar die zegt niks over local naar world transformaties en vice versa)

[.oisyn]

even afgezien van het feit dat het nix met opengl te maken heeft...

er zijn idd weinig tuts over CD&R te vinden... maar uit de informatie die ik stukjes bij beetjes bij elkaar heb verzameld heb ik het toch succesvol geimplementeerd (AABB CD&R tegen bsp-based geometry)

hoewel AABB-AABB CD&R ook niet echt moeilijk te implementeren moet zijn. Bounding spheres is relatief gezien een stuk makkelijker, en axis aligned cylinders zijn ook wel te doen (beetje combinatie van AABB en spheres)

Al mijn objecten bewegen overigens lineair, en zonder rotatie (moet nog steeds uitvinden hoe dat werkt)

Ik heb me al voorgenomen om hier zelf een tutorial over te schrijven (als content voor http://www.gameskool.nl), maar voorlopig begin ik daar nog niet aan


Dus als je specifieke vragen hebt: vraag ze

* .oisyn ziet een mooie discussie tegemoet


^{Bijlage 1
CD&R: Collision Detection and Response
AABB: Axis Aligned Bounding Box
BSP: Binary Space Partitioning}

[The - DDD]

Het probleem waar ik nu mee bezig ben is het efficient converteren van de diverse local coordinate spaces naar 1 world coordinate space.

Als ik bijvoorbeeld met OpenGL een structuur teken die verbonden is aan de uiteinden om bijvoorbeeld een robot arm te maken. Dan pas je een aantal keren herhaald een rotatie en een translatie toe. Hoe reken je dat makkelijk terug. Ok met een matrix, maar hoe bepaal je dus die matrix.

Om even een voorbeeldje te geven van wat ik hierboven bedoel:

code:

#define WIN32_LEAN_AND_MEAN
#define WIN32_EXTRA_LEAN

#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>

// glaux to simplify drawing simple objects.
#include <gl/glaux.h>

/*
    This class provides is the base of all implementations concerning
    the robotarm. Instantiate this class and you'll have a fully oparational robotarm.
    All internal implementation issues (like internal collision detection and response
    are handled in this class. For external implementation isseus, access funtions are provided
*/
class CArmEngine {

public:
    CArmEngine();                           // constructor
    CArmEngine(GLfloat,GLfloat,GLfloat,GLfloat);        // constructor

    void update(GLfloat);                   // update the states of the arm
    void draw();                            // draw the arm

    void adjustBaseRotateSpeed(GLfloat);
    void adjustMember1RotateSpeed(GLfloat);
    void adjustMember2RotateSpeed(GLfloat);
    void adjustMember3RotateSpeed(GLfloat);
    
private:
    GLfloat baseAngle;              // the angle of rotation of the base, value: {0 < 360}
    GLfloat member1Angle;           // the angle of rotation of member one, value: {0 < 360}
    GLfloat member2Angle;           // the angle of rotation of member two, value: {0 < 360}
    GLfloat member3Angle;           // the angle of rotation of member three, value: {0 < 360}

    GLfloat baseRotateSpeed;        // the amount of rotation of the base in degrees per second
    GLfloat member1RotateSpeed;     // the ammount of rotation of member one  in degrees per second
    GLfloat member2RotateSpeed;     // the amount of rotation of member two in degrees per second
    GLfloat member3RotateSpeed;     // the amount of rotation of member three in degrees per second

};

// The constructor sets all variables to their initial values
CArmEngine::CArmEngine(GLfloat angleBase, GLfloat angleOne, GLfloat angleTwo, GLfloat angleThree)
{
    baseAngle       = angleBase;
    member1Angle    = angleOne;
    member2Angle    = angleTwo;
    member3Angle    = angleThree;

    baseRotateSpeed     = 0;
    member1RotateSpeed  = 0;
    member2RotateSpeed  = 0;
    member3RotateSpeed  = 0;
}

CArmEngine::CArmEngine()
{
    baseAngle       = 0.0f;
    member1Angle    = 0.0f;
    member2Angle    = 0.0f;
    member3Angle    = 0.0f;

    baseRotateSpeed     = 0;
    member1RotateSpeed  = 0;
    member2RotateSpeed  = 0;
    member3RotateSpeed  = 0;
}

void CArmEngine::update(float deltaTime)
{
    baseAngle       += deltaTime * baseRotateSpeed;
    // check if bounds are not crossed
     // do some sin, cos & tan stuff to check.
    // if bounds are crossed, reset to touch

    member1Angle    += deltaTime * member1RotateSpeed;
    if (member1Angle > 45.0f)
    {
        member1Angle = 45.0f;
        member1RotateSpeed = 0;
    }
    if (member1Angle < -45.0f)
    {
        member1Angle = -45.0f;
        member1RotateSpeed = 0;
    }

    // check if bounds are not crossed
    // do some sin, cos & tan stuff to check.
    // if bounds are crossed, reset to touch

    member2Angle    += deltaTime * member2RotateSpeed;
    if (member2Angle > 135.0f)
    {
        member2Angle = 135.0f;
        member2RotateSpeed = 0;
    }
    if (member2Angle < 0.0f)
    {
        member2Angle = 0.0f;
        member2RotateSpeed = 0;
    }
    // check if bounds are not crossed
    // do some sin, cos & tan stuff to check.
    // if bounds are crossed, reset to touch

    member3Angle    += deltaTime * member3RotateSpeed;
    if (member3Angle > 135.0f)
    {
        member3Angle = 135.0f;
        member3RotateSpeed = 0;
    }
    if (member3Angle < 0.0f)
    {
        member3Angle = 0.0f;
        member3RotateSpeed = 0;
    }
    // check if bounds are not crossed
    // do some sin, cos & tan stuff to check.
    // if bounds are crossed, reset to touch
}


void CArmEngine::draw()
{
    // save current matrix
    glMatrixMode(GL_MODELVIEW);
    glPushMatrix();

    // rotate around base
    glRotatef( baseAngle, 0.0f, 1.0f, 0.0f);
    // draw base
    glPushMatrix();
        glTranslatef( 0.0f, 0.125f, 0.0f);
        glColor3f( 0.5f, 0.2f, 0.8f);
        auxSolidBox( 1.0, 0.25,1.0);
    glPopMatrix();


    // move to next joint
    glTranslatef( 0.0f, 0.25f, 0.0f);
    // rotate around this joint
    glRotatef( member1Angle, 0.0f, 0.0f, 1.0f);
    // draw member 1
    glPushMatrix();
        glTranslatef( 0.0f, 1.0f, 0.0f);
        glColor3f( 0.5f, 0.4f, 0.6f);
        auxSolidBox(0.5, 2.0, 0.5);
    glPopMatrix();


    // move to next joint
    glTranslatef( 0.0f, 2.0f, 0.0f);
    // rotate around this joint
    glRotatef( member2Angle, 0.0f, 0.0f, 1.0f);
    // draw member 2
    glPushMatrix();
        glTranslatef( 0.0f, 1.0f, 0.0f);
        glColor3f( 0.5f, 0.6f, 0.4f);
        auxSolidBox(0.5, 2.0, 0.5);
    glPopMatrix();


    // move to next joint
    glTranslatef( 0.0f, 2.0f, 0.0f);
    // rotate around this joint
    glRotatef( member3Angle, 0.0f, 0.0f, 1.0f);
    // draw member 3
    glPushMatrix();
        glTranslatef( 0.0f, 1.0f, 0.0f);
        glColor3f( 0.5f, 0.8f, 0.2f);
        auxSolidBox(0.5, 2.0, 0.5);
    glPopMatrix();


    // move to next joint
    glTranslatef( 0.0f, 2.0f, 0.0f);
    // rotate around this joint
    glRotatef( 0.0f, 0.0f, 0.0f, 1.0f);
    // draw graber
    glPushMatrix();
        glTranslatef( 0.0f, 0.5f, 0.0f);
        glColor3f( 0.5f, 1.0f, 0.0f);
        auxSolidBox(1.0, 1.0, 1.0);
    glPopMatrix();

    // restore current matrix
    glPopMatrix();
}


void CArmEngine::adjustBaseRotateSpeed(GLfloat amount)
{
    baseRotateSpeed     += amount;
    if (baseRotateSpeed > 45.0f)
    {
        baseRotateSpeed = 45.0f;
    }
    if (baseRotateSpeed < -45.0f)
    {
        baseRotateSpeed = -45.0f;
    }
}

void CArmEngine::adjustMember1RotateSpeed(GLfloat amount)
{
    member1RotateSpeed  += amount;
    member1RotateSpeed      += amount;
    if (member1RotateSpeed > 45.0f)
    {
        member1RotateSpeed = 45.0f;
    }
    if (member1RotateSpeed < -45.0f)
    {
        member1RotateSpeed = -45.0f;
    }
}

void CArmEngine::adjustMember2RotateSpeed(GLfloat amount)
{
    member2RotateSpeed  += amount;
    member2RotateSpeed      += amount;
    if (member2RotateSpeed > 45.0f)
    {
        member2RotateSpeed = 45.0f;
    }
    if (member2RotateSpeed < -45.0f)
    {
        member2RotateSpeed = -45.0f;
    }
}

void CArmEngine::adjustMember3RotateSpeed(GLfloat amount)
{
    member3RotateSpeed  += amount;
    member3RotateSpeed      += amount;
    if (member3RotateSpeed > 45.0f)
    {
        member3RotateSpeed = 45.0f;
    }
    if (member3RotateSpeed < -45.0f)
    {
        member3RotateSpeed = -45.0f;
    }
}

Dit is een proef projectje waar ik net mee bezig ben. Mijn doel is dus om dit geval met collision detection te implementeren. (ik zal nog wel het een en ander moeten aanpassen om nette collision detection toe te staan)

[The - DDD]

Waarschijnlijk zal het er op neer komen dat ik de diverse elementen moet loskoppelen en elk onder een eigen object moet onder brengen met connectie punten. Maar dan nog blijft het converteren naar world coordinate.

Ik ben zelf nu aan het rekenen of het effectief is om een middelpunt per element te definieren waarvan in de klasse de world coordinaten bij worden gehouden. Dit geval heeft ook een orientatie gedefinieerd met drie vectoren (x y z) deze orientatie samen met het punt in de world coordinaten geeft voldoende info om het geval te tekenen. Het middelpunt is dan de oorsprong van mijn lokale coordinaat stelsel.

Maar hoe koppel je dan het ene object aan een ander object dusdanig dat het andere object meedraait met het ene object. Een gelinkde structuur dus.

Daarvoor zou ik het middelpunt van het ene object naar het andere object moeten transleren de transformatie toepassen en vervolgens het middelpunt weer terug transleren naar zijn eigen coordinaat stelsel.

(En deze laatste alinea is dus precies waar ik een beetje moeite mee heb om uit te denken.)

[.oisyn]

In principe is de totale rotatiematrix van een object z'n eigen transformatiematrix vermenigvuldigd met die van z'n ouder (dus waar het object aan vast zit). Vergeet niet dat onder z'n eigen transformatiematrix ook de translatie valt om m op de goede plek te zetten ten opzichte van z'n ouder.

Eigenlijk is het te zien als:
eigen rotatie -> translatie tov de ouder -> transformatie van de ouder

Dit valt trouwens onder het kopje "hierarchical transformation"

Een goede plek voor het middelpunt, ook wel de pivot point genoemd, is het punt waar ie aan zijn ouder vast zit. Ik zal even een tekeningetje maken



per element ligt de pivot point in de oorsprong (0, 0, 0)
Stel, deze 3 armen in mijn superieure () tekeningetje noem je arm1 t/m arm3

Als je nou elke arm 20 graden over z'n pivot point laat draaien, dan krijg je de volgende matrices:

m1 = rotatie (20) * translatie (positie van de robot in de wereld)
m2 = rotatie (20) * translatie (arm2 pivot tov arm1) * m1
m3 = rotatie (20) * translatie (arm3 pivot tov arm2) * m2

(vooropgesteld dat je 4x4 matrices gebruikt waar de translatie op de onderste rij staat, anders moet je alle vermenigvuldigingen omdraaien)

[The - DDD]

Ik gebruik OGL matrices, dus 4x4...

En inderdaad, ik kan natuurlijk de huidige translatie matrix kopieren van de stack en deze in het object opslaan.
En op basis daarvan werken, maar wat als ik meer dan 2 pivot points wil, dan wordt het lastig.

Hoe werkt dat? Je kan bij mijn weten namelijk slechts met een root pivot point werken.

[The - DDD]

Op zich als ik zoals al eerder aangegeven kan werken met een middelpunt waarin een orientatie is opgeslagen.
Dan zou het kunnen werken.

Als je een verwijzing houdt naar alle objecten die vast zitten aan je object dan zou ik bijvoorbeeld zo kunnen werken:

Roteer, transleer je object. Ga alle pivot points na en transleer alle objecten in dezelfde ruimte rond dit punt.

Op die manier kan ik in principe alles overal aanknopen op elk punt aan mijn object. tevens kan ik op basis van dit punt + orientatie in de world space de collisions makkelijk bepalen omdat ik van elk object ten opzicte van elkaar kan bepalen of er een collision is of niet.

Klinkt logisch, of mis ik iets? Ik denk namelijk wel dat het de oplossing is om alle collisions te doen in 1 coordinaat stelsel en wel het world stelsel.

Door een graaf achtige structuur te maken (zonder zelf referenties, dus loops) zou het moeten werken.

Bijkomend voordeel is dat ik op elk punt in mijn object kan gaan werken. (mits ik kies voor double linken) En alles wordt gedaan in World coordinaten. Voordeel daarvan is dat ik andere objecten in World coordinaten makkelijk op collisions kan checken.

Nadeel, extra berekeningen, maar hoeveel?
Als ik twee quads (waar je bounding box uit is opgebouwd) dan moet ik dus per quad 2 punten transleren, dus 4 punten totaal (= voldoende info voor twee quads).

[.oisyn]

waarom zou je meerdere pivot points hebben

[Verwijderd]

Volgens mij is erop nehe wel een tutorial over collision detection nehe.gamedev.net

[.oisyn]

neuh, die cd&r tut van nehe heb je zo goed als nix aan (dat vind ik trouwens van al zijn tuts, maar das mijn mening )

[The - DDD]

Op dinsdag 27 november 2001 10:04 schreef OiSyN het volgende:
neuh, die cd&r tut van nehe heb je zo goed als nix aan (dat vind ik trouwens van al zijn tuts, maar das mijn mening )

Jij ook al...

En waarom meerdere pivot points.

Tja, stel je een menselijk lichaam voor. rug, heup, twee benen. Hee da's van 1 naar 2. Vandaar.

En bovendien lijkt het mij gewoon het beste om als middelpunt het zwaarte punt van het object te nemen, wordt je respons weer een stuk beter van. Maar ik denk wel dat het de oplossing wordt. Een zwaartepunt met daarin een orientatie in drie vectoren. Dit zwaarte punt wordt dan in world coordinaten opgeslagen. Hiermee kan ik dan transleren van world naar local en vervolgens de orientatie roteren aan de hand van de drie vectoren. en vice versa natuurlijk.

Ok, tijd om maar weer is een paar daagjes te gaan proggen.

[.oisyn]

tja, het idee is als je meerdere pivot points hebt, dat je die delen dan ook weer apart onder gaat verdelen, dus dan eindig je met 1 pivot point per element

[The - DDD]

Ik vind het wel opvallend dat er inweze maar een paar mensen zijn die iets in deze thread posten.

[.oisyn]

en zwaartepunt kun je idd voor je cd&r gebruiken, maar voor hierarchical transformation kun je dus beter de draaipunten als pivot nemen, dat scheelt echt een hoop hoofdpijn (en dit is ook gewoon met elkaar te combineren... is gewoon een extra translatie van pivot naar zwaartepunt)

[.oisyn]

Op dinsdag 27 november 2001 23:33 schreef The - DDD het volgende:
Ik vind het wel opvallend dat er inweze maar een paar mensen zijn die iets in deze thread posten.

hier zitten niet echt veel 3d'ers