[Alg] 3D object-object collision detection

[jos707]

ik ben bezig met mijn eigen mini 3d engine en stoot
op een probleem waar ik nu al een hele tijd mijn
hoofd overbreek. Ik heb google ondertussen al helemaal
afgegoogeld en kan niets vinden dat ik kan gebruiken.
Mijn beperkte wiskunde kennis zal hier waarschijnlijk
ook iets mee te maken hebben


Ik van plan om een soort fps (a la quake of whatever)
te maken met mijn engine. Lukte aardig tot ik dus bij
het stuk collision detection kwam. Ik heb objecten in mijn 3d wereld
die dus afzonderlijk moeten kunnen bewegen(in object space) onafhankelijk van
de camera (world space). Hiervoor heb ik een matrix class gemaakt
en doe het dus op de volgende manier:

CMatrix4x4 matrix;

glPushMatrix;
glLoadMatrix(matrix.matrix);
matrix.rotate(angle,x,y,z);
matrix.translate(x,y,z);
flMultMatrix(matrix.matrix);
drawObject(object1);
glPopMatrix;

Dit doe ik dus voor al mijn objecten waardoor ze dus afzonderlijk
in mijn 3d wereld rondbewegen.
Het probleem vormt zich bij de collision detection. Ik gebruik dus
bounding spheres om de collision te berekenen met de camera en
tussen de verschillende objecten onderling. Nu wanneer ik de
verteces inlaad van een object in een 1D array dan staan deze
op positie 0 en werkt de collision detection vrij goed.

Maar wanneer ik ze doormiddel van bovenstaande code verplaats naar hun eigen
positie gaat de collision det. de mist in omdat het object
natuurlijk voor de camera(world space) nog altijd op positie 0
staan terwijl ze in object space op een andere plaats staan.

Ik weet dat probleem zich situeert in het converteren van de
ene space naar de andere en weet dus niet hoe je dit doet?


Ik hoop dat mijn uitleg wat duidelijk is.

[Janoz]

Je moet de bounding spheres ook transformeren met de verplaatsing van je object voor dat je je collision detection gaat doen.

[.oisyn]

Even een aantal dingen op een rijtje zetten

Je probleem heeft niets te maken met opengl. Je zit idd met transformaties die je door opengl kunt laten doen, maar daar heb je niet bar veel aan aangezien je zelf ook de resultaten van de transformaties wilt weten.
Daarnaast haal je de terminologie een beetje door de war . Je objecten zijn idd in object space, maar bewegen niet in object space maar in world space. Het idee is namelijk dat je de coordinaten van de vertices van het object niet gaat wijzigen: die blijven altijd op een vaste plaats (animaties daargelaten). Je beweegt je objecten door de wereld door hun world matrix te veranderen; ze bewegen dus alleen in world space.

Camera space is vervolgens de ruimte gezien vanuit het camerastandpunt. Het heeft niet veel nut om deze space bij je collision detection te betrekken; het werkt een stuk intuitiever als je dat allemaal in world space uitvoert.

Dus, geef je objecten een positie en een orientatie mee; hier kun je hun world matrix uit vormen. Voor bounding spheres wordt het vrij makkelijk, een bol blijft immers gelijk na een rotatie, dus je neemt simpelweg de translatie (je hoeft niet eens een matrix te gebruiken), en dat is gewoon het middelpunt van de bol van het object.

[jos707]

idd het heeft eigenlijk niet veel te maken met opengl maar ik moest het beestje toch een titel geven

Maar mijn uitleg was misschien niet helemaal duidelijk:
stel concreet:
Ik heb poly met drie verteces (het object). Deze wordt ingeladen op positie 0.
Nu wil ik dat mijn camera zich niet door dit object kan verplaatsen en hiervoor
roep ik mijn collision routine op: testCollision(cameraStandPunt,object).
De routine testCollision krijgt dus het camerastandpunt en een object door en gaat
aan de hand hiervan berkenen(normal,dot-en crossprodunt,..) of er zich een collision voordoet.

Wanneer ik nu doormiddel van een matrix (zie eerste post) het object
tranformeer naar een nieuwe positie en hierna dus terug testCollision
oproep wordt de collision niet meer gedetecteerd. Omdat ik dus eerst zowel
het object en de camera indezelfde space (worldspace?) moet converteren, en de vraag is eigenlijk hoe doe ik dat ?

[ Voor 3% gewijzigd door jos707 op 02-11-2004 16:58 ]

[.oisyn]

Worldspace is het handigst. Maar je weet toch waar het object zich in worldspace bevindt, en waar de camera zich in worldspace bevindt? Dan kun je toch ook gewoon die gegevens gebruiken bij je collision checks?

[FireWood]

Persoonlijk zal ik denken aan een bol(i.v.m. berkenen) die je trekt om al je objecten heen evt. meerdere bollen, maar at is object afhankelijk.

Als de afstand tussen middelpunt a en middelpunt b <= straal bol a + straal bol b is er een probleem en heb je kans dat de objecten botsen.

Het verschil is haast niet merkbaar, terwijl dit zeer snel kan worden uitgevoerd.

Je kunt dit makkelijk driedimensionale wereld uitvoeren met een paar simpele berekningen.

Ik weet dat dit er heel simpel uitziet, maar in de praktijk valt het altijd tegen.(Heb ook zo'n wiskundig probleem die theoretisch heel simpel is, terwijl ik er al een tijd zit mee te knoeien)

[Verwijderd]

Ik weet niet of je hier wat aan hebt, maar iig doe ik mijn object-object collision detection op deze manier (in delpi ):

-ik heb een movecam procedure, deze roept gewoon glulookat aan,
-ik heb objecten, die kan ik tekenen waar en hoe ik maar wil mbv. transformaties als glrotate en gltranslate.

-wanneer ik voor collision wil testen, wil ik de werkelijke coordinaten van de vertices weten. Dus niet de coordinaten die ik bij het maken van het object heb ingevoerd.

-Deze coordinaten vindt ik terug door de vertices van een object te vermenigvuldigen met de huidige matrix (die bij het object hoort (wordt "gescheiden" met push en pop matrix)

- Kortom, de code waarmee het object getekend wordt (in de array triangles staan al mn triangles voor het object, in de array collision komen alle "getransformeerde" triangles (dus ook vertices) te staan:

Delphi:

glPushMatrix();
     glTranslatef(Position.X, Position.Y, Position.Z);
     glRotatef(Rotation.X,1,0,0);
     glRotatef(Rotation.Y,0,1,0);
     glRotatef(Rotation.Z,0,0,1);
      
     glGetFloatv(GL_MODELVIEW_MATRIX, @Matrix); // Haal matrix op
     
     if Length(Collision) <> Length(Triangles) then 
     // maak collision array even groot als triangles
          SetLength(Collision,Length(Triangles));

           for i := 0 to Length(Collision)-1 do begin
               Collision[i].V[1] := MatrixMult(Triangles[i].V[1],Matrix);
               Collision[i].V[2] := MatrixMult(Triangles[i].V[2],Matrix);
               Collision[i].V[3] := MatrixMult(Triangles[i].V[3],Matrix);
               Collision[i].No := Normal(Collision[i]);
          end;
     end;

      glBegin(GL_TRIANGLES);
      for i := 0 to Length(Triangles)-1 do begin
         glNormal3f(Triangles[i].No.X,Triangles[i].No.Y,Triangles[i].No.Z);
         glVertex3f(Triangles[i].V[1].X,Triangles[i].V[1].Y,Triangles[i].V[1].Z);
         glVertex3f(Triangles[i].V[2].X,Triangles[i].V[2].Y,Triangles[i].V[2].Z);
         glVertex3f(Triangles[i].V[3].X,Triangles[i].V[3].Y,Triangles[i].V[3].Z);
      end;
    glEnd;
glPopMatrix();

De matrixmult functie ziet er als volgt uit:

Delphi:

Function MatrixMult(Vertex : TGlVertex; Matrix : array of GlFLoat) : TGlVertex;
begin
   result.x := vertex.x * matrix[0] + 
                    vertex.y * matrix[4] + 
                    vertex.z * matrix[8] + matrix[12];
   result.y := vertex.x * matrix[1] + 
                    vertex.y * matrix[5] + 
                    vertex.z * matrix[9] + matrix[13];
   result.z := vertex.x * matrix[2] + 
                    vertex.y * matrix[6] + 
                    vertex.z * matrix[10] + matrix[14];
end;

Als ik dit allemaal heb gedaan, dan kan ik mn collision detection uitvoeren...

bv, sphere vs sphere collision detection "poly" -vs-"poly" collision detection
(sphere vs. sphere maakt namelijk gebruik van een "ge-matrixmultipliceerde" Center coordinaat... en niet van de omgerekende vertex posities die ik net heb uitgerekend

Delphi:

if PolyVsPoly(GlObject[1].Collision,GlObject[2].Collision) 
   then glColor3f(1,0,0) else glColor3f(0,1,0);

Ik hoop dat je er *iets aan hebt ... Zo niet... dan hebbik dit allemaal lekker voor nix opgekrabbeld

[ Voor 7% gewijzigd door Verwijderd op 02-11-2004 22:30 ]