3d Engine Collision

[Memphis]

hi there,

i've been working on a new directx9 3d engine and have a small amount complete, however i do not know what direction to look or even how to begin with collision detection inside of a model..

for example - i have built a simple room (.x) model file, now lets say i put in a player model (human model) again a .x model file, how would i check the collision with floor and walls (basically how to seperate the floor and walls to be checked for collision with the player collision box).. i'm not totally sure how to explain.. hope you understand lol

My Engine Example

thanks in advance

;MM;

[noeska]

First imagine your model to be a sphere. (and your player/camera too)
As a sphere has a radius it is easy to detect collision.

However that is not verry precies. But it is a starter.
So once you detected a sphere collision it is time to move on to perhaps detect collision at triangle level. Leaving you to compare all triangles of both meshes. So for multiple part meshes it could be adiviseable to represent eache part as an sphere before going in deeper.

Also do some research on (axis aligned) bounding box collisions as they are more presice then spheres.

[Memphis]

hi thanks for quick reply

i used collision box for my 2d engine, i understand using a collision/bounding box, however i am unsure how to even begin todo that in 3d with x models, in my 2d engine my models were a custom struct with collision params etc, so now with .x in 3d i am lost.

thanks

[Memphis]

ok i came up with an idea whilst messing around,

[code="delphi"]
stModel = record
pMesh: ID3DXMesh; // mesh object
pMeshMaterials: PD3DMaterial9Array; // Materials for mesh
pMeshTextures: PIDirect3DTexture9Array; // Textures for mesh
NumMaterials: Integer; // Number of mesh materials
x,y,z,a,s: Single;

//bounding box, collision data here. ?
//a linked list of co-ords to check against other stmodels for colli sions ?
end;
PstModel = ^stModel;
[/code]

ok so this is my model struct, holds info on each model i load into my engine, my idea is to have a linked list of co-ords that can be checked against other models in my engine for collision (obviuously once i get this to work i will add some sort of bounding range so no collision is checked if not in range (bounding box)) but my question now would be for when my model is loaded, how can i get a list of triangles and positions from the mesh interface?

by doing this, the position will not have to be changed unless the model is moved which then i can just update the co-ords, however most models will have a static positioning anyways.

hope someone can help.

;MM;

[noeska]

going from 2d boundix boxes to 3d should be equal to doing 2d bounding boxes except that you now also have a z axis ;-)

But here's an tutorial: http://www.toymaker.info/Games/html/collisions.html

[chronozphere]

Do you use ID3DXMesh to load the .x files? Then it's just a matter of locking it's vertex-buffer by calling LockVertexBuffer() and reading data from that buffer. The same can be done with the indexbuffer, if you want to know how the different vertices are used to form triangles. Check MSDN for more information about this:

http://msdn.microsoft.com/en-us/library/bb205749(VS.85).aspx

But i still do not understand your way of collision checking using points. Are you just checking whether any point lies at the other side of let's say a wall?

If you check your meshes against planes and bounding spheres it's okay. But if you want to check collision between two meshes that are both made up of these points, it'll never work. It is extremely unlikely that any point of Mesh A lies on the exact same location as a point of Mesh B. Moreover, it can happen that a small cube (made up of 6 points) lies completely inside a bigger one. A collision check using your points approach will tell us that there is no collision because none of the points of the two meshes are on the same location. It should tell us that a collision has occured because they obviously intersect.

I suggest to think in terms of volumes rather than points. Volumes consist of an infinit ammount of points and will be reliable. Checking two volumes against eachother is like checking whether two collections of an infinit ammount of points share some points. you can use spheres (the easiest way)... Or planes, axis-aligned boxes, oriented boxes (they have rotation)... You could also check out the seperating axis theorem that describes how to check for collision between two convex volumes but that's slightly more advanced.

Hope this helps you.

[Memphis]

Hi thanks both for replies.

yes i use ID3DXMesh to load the x files, the way i was thinking is. if i have a list of points, i can check if any points pass between the points of other models. (that are in range of collision checking)

as for a simple bounding box, i would love just todo this for now, but the problem i have is, one of my models is a room. (walls, floor, etc) if i calculate a bounding box then it covers the whole x model, so my other models (such as a human model) cant enter inside of the room due to collision even on a door way for example. If you have a better solution, i'd love to hear it. thanks in advance


a small example of my problem with bounding box.

model 1 = Room, with no ceiling.



ok so room is loaded up with bounding box, and now camera has a bounding box also. and now the problem, below you will see camera cant enter into the room because a bounding box around the room is useless....



hope you can help. Thanks again.

;MM;

[chronozphere]

That's quite a complicated problem.

If your room-models are very low poly, you could check your player-model's sphere against every triangle of the current room he's in.

An article on collision-detection:


http://www.peroxide.dk/papers/collision/collision.pdf

If your room is high poly, doing this would probably be too CPU-intensive. Then you'd have to make a collision-mesh out of it with a reduced ammount of triangles and do the same. You could also scan your triangles to find unique planes and check them against the sphere of your player-object, but you'd need to limit each plane to it's own area because otherwise you wouldn't be able to enter a door. I've never done this, but i can tell that especially the latter really tests your math skills.

[noeska]

can you break up your room in parts? E.g. make the floor a part and each wall a part. That way each part gets its own bounding box making things a lot simpler.

You bounding box around the complete world is a starter to go looking for collisions with bounding boxes inside it. So you go deeper and deeper inside the structure of your world model.

[Memphis]

yes quite complicated lol, what i was planning was some sort of polygon collision

can you break up your room in parts? E.g. make the floor a part and each wall a part. That way each part gets its own bounding box making things a lot simpler.

You bounding box around the complete world is a starter to go looking for collisions with bounding boxes inside it. So you go deeper and deeper inside the structure of your world model.

do you mean to load the walls etc as seperate mesh / models? i could possibly, only problem being when it comes to larger scale buildings with more floors or so.

thanks,