TERRAIN collision detection

Fb32dbd11e262c7b60bc949b92d58588
0
Dickie 101 Dec 17, 2010 at 12:29

Hi everyone,
I just got this book:<Programming.Role.Playing.Games.with.DirectX.2nd.Edition> by Jim Adams,and I found the book really bad for a lot of code doesn’t work.I got a BIG problem when I was trying to detect the collision between the terrain and my role.The code was from the book,which doesn’t have a clue:

float GetClosestHeight(ID3DXMesh* pMesh,float XPos,float YPos,float ZPos)
{
    
    D3DXVECTOR3 vecPos=D3DXVECTOR3(XPos,YPos,ZPos);

    D3DXMATRIX m,m_i;
    d3ddev->GetTransform(D3DTS_WORLD,&m);
    
    D3DXMatrixInverse(&m_i,NULL,&m);
    D3DXVec3TransformCoord(&vecPos,&vecPos,&m_i);


    float YBelow,float YAbove;
    YBelow=GetHeightBelow(pMesh,
        vecPos.x,vecPos.y,vecPos.z);
    YAbove=GetHeightAbove(pMesh,
        vecPos.x,vecPos.y,vecPos.z);
    
    if(fabs(YBelow-vecPos.y)<fabs(YAbove-vecPos.y))
        return YBelow;
    return YAbove;
}
float GetHeightBelow(ID3DXMesh* pMesh,float XPos,float YPos,float ZPos)
{
    BOOL hit;
    float u,v,dist;
    DWORD faceIndex;
    
    D3DXIntersect(pMesh,
        &D3DXVECTOR3(XPos,YPos,ZPos),
        &D3DXVECTOR3(XPos,-1.0f,ZPos),
        &hit,&faceIndex,&u,&v,&dist,NULL,NULL);
    
    if(hit==TRUE)
        return YPos-dist;
    return YPos;
}
float GetHeightAbove(ID3DXMesh* pMesh,float XPos,float YPos,float ZPos)
{
    BOOL hit;
    float u,v,dist;
    DWORD faceIndex;
    
    D3DXIntersect(pMesh,
        &D3DXVECTOR3(XPos,YPos,ZPos),
        &D3DXVECTOR3(XPos,1.0f,ZPos),
        &hit,&faceIndex,&u,&v,&dist,NULL,NULL);
    
    if(hit==TRUE)
        return YPos+dist;
    return YPos;
}

and in my main program I wrote:

if(::GetAsyncKeyState(VK_UP)&0x8000f){
    float YPos=GetClosestHeight(level->GetMesh(),            Role.x,
    Role.y,
    Role.z);
        Role->SetAltitude(YPos);
}

I runned the program,the role just went through the scene FREELY,there’s nothing different to before at all.
Could anyone tell me where’s the problem with my code?
Thanks for any replies…

13 Replies

Please log in or register to post a reply.

Fb32dbd11e262c7b60bc949b92d58588
0
Dickie 101 Dec 17, 2010 at 12:34

Or just tell me other methods to detect TERRAIN collision ,which WORKS…
Thanks!

B2d356f97a3d0dec8ae2d8c1e1fa1c2d
0
Nerd_Skywalker 101 Dec 17, 2010 at 12:46

I’m no expert, but wouldn’t you want to be using GetHeightBelow() instead of GetClosestHeight() in your main?
Again, I’m no expert and this probably won’t help.

EDIT: Wait sorry I get it now. /moron

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Dec 17, 2010 at 20:07

This is the paper that I stated out with:

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

It’s been a while since I read it but it will give you really good results once you get it working. This is the type of CD you will often find in MMOs like WoW. You basically have an ellipsoid that surrounds your character and you check for collisions between it and the polygons around you. For each polygon you need to check faces first, then edges, then vertexes. There are a lot of optimizations. For instance if you don’t collide with the plane of the polygon you can’t collide with the edges or vertexes and if you do collide with a face you won’t collide with its edges. If you collide with an edge you won’t collide with the vertexes of that edge.

One thing I tried is instead of using an ellipsoid I used three stacked spheres. This means you have to check three objects with the terrain instead of one but it also means you don’t have to transform all the polygons around you before checking for collisions (the article explains this transformation). It works decently both ways.

Finally the collision response is not fully covered. You may collide with more than one face so you need to handle that. What I did was generate a response vector for each object (face, edge or vertex) you collide with and also each pair of objects. You can get a response vector for the pair by dong a cross product of the contact vectors. Keep in mind you can get two possible directions when doing the cross product. You can take the original force vector and do a dot product with this vector and check the sine to see if you’re vector is the right way and flip it if it isn’t. In any case once you have your set of possible response vectors you can do a dot product with the original force vector and each possible response vector and find which one matches the force vector the best.

This algorithm will let you push up almost vertical mountains with no problems (unless you limit it). It will find the path of least resistance for the given direction you are facing. It works well with gravity and you can add sliding down hills and other fun stuff.

6837d514b487de395be51432d9cdd078
0
TheNut 179 Dec 17, 2010 at 20:31

For landscapes, doesn’t it make more sense to do collision detection with a grid? It’s all about finding the plane you’re standing on, which is quite trivial if you know where in the heightmap you are. If your vertical is in the z-axis, then your (x,y) position dictates where the floor is in the heightmap. From there you either adjust the vertical position of your avatar accordingly or do a simple plane test to calculate the point of intersection. Any more, especially D3DXIntersect, seems like overkill.

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Dec 17, 2010 at 21:23

@TheNut

For landscapes, doesn’t it make more sense to do collision detection with a grid? It’s all about finding the plane you’re standing on, which is quite trivial if you know where in the heightmap you are. If your vertical is in the z-axis, then your (x,y) position dictates where the floor is in the heightmap. From there you either adjust the vertical position of your avatar accordingly or do a simple plane test to calculate the point of intersection. Any more, especially D3DXIntersect, seems like overkill.

What do you do with trees, buildings, overhangs etc? The grid can be handy for finding some of the polygons to test but it won’t give you a natural response by itself. Even with just terrain on a grid what happens when you encounter steep terrain and you want your character to push up that crease? Just using the grid ignores most of the physics and provides much less natural movement. If you ever play a game that won’t let you jump or where your jump is just a graphic it’s probably because they didn’t bother with real collision detection. People go though the trouble of implementing it because it provides much better game play. However if you are just doing this for fun and know the tradeoffs then the grid may be a good solution. I just thought I would provide some pointers to a very common solution in case the OP wanted to take it that far.

6837d514b487de395be51432d9cdd078
0
TheNut 179 Dec 17, 2010 at 23:19

I’m just talking about terrain here, not objects. From the grid you’re going to know the heightmap tiles you can use for testing, whatever that may be. If all you want is to prevent things from falling through the ground, then you can interpolate the ground position from the adjacent vertices. If you want to apply physics, you still can because all the information is there. All this for O(1) speed. Something as crazy as D3DXIntersect on the entire heightmap is overkill. A more general algorithm would be to use a tree structure, but considering the skill level of the OP I don’t think it’s a good idea to get him to jump into such things just yet.

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Dec 18, 2010 at 00:44

By terrain you mean a mesh of triangles; possibly a rectilinear grid with diagonals I take it. If you are pushing obliquely against a steep tri you shouldn’t just go the direction you are facing you will often slide along the face. Moving quickly up the side of a face just because you are facing that direction is not natural, but this is what will happen if you just position yourself on the grid based on you X,Y position and allow yourself to move only in the direction you are facing. Yes you will move but it won’t be realistic. You will actually go faster up hill (or downhill). I hesitate to call this collision detection. You are just evaluating a piecemeal function. Look at the case where you are pushing obliquely against a wall. You should slide along it. The same thing happens long before a face is vertical (i.e. in terrain). Once you start adding trees buildings etc. the situation becomes worse. You won’t be able to use that simplified collision in any kind of real game unless you carefully control where the player can or can’t go. But even with just terrain, simply positioning yourself based on your location is sup-optimal.

6837d514b487de395be51432d9cdd078
0
TheNut 179 Dec 18, 2010 at 01:53

Syntax, you’re jumping over the fence here :) I didn’t bring up movement specifics. I’m only bringing up a solution to solve the problem of finding the tiles and knowing the vertical point, which is fastest with a grid. I didn’t bring up gravity, running up slopes, and bouncing balls on the terrain because these can all be solved after the fact. Just because you use a grid doesn’t mean that once you jump off a cliff you automatically teleport to the bottom, or that you start running up slopes unrealistically. Instead you will know from the grid that you should start falling or sliding. That’s the point I’m getting at.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 104 Dec 18, 2010 at 03:24

nut is right. find location of heightmap its sitting on, make its height the height in the heightmap, that simple.

of course maybe then you could bilinear filter the position… its best to keep things simple, hack the rest on top of this i reckon.

Fb32dbd11e262c7b60bc949b92d58588
0
Dickie 101 Dec 18, 2010 at 05:00

Uhmm…First,thanks to both SyntaxError and TheNut:),although you had different opnions..
I have downloaded http://www.peroxide.dk/papers/collision/collision.pdf, actually ,I found it’s a bit difficult to understand,, so much math equations..
So I will try HeightMap first, and I got some good tutorials by GOOGLE..
Thanks!

5225bc0c3bf66f4c275c332de6388d1f
0
SyntaxError 101 Dec 18, 2010 at 19:11

The height doesn’t give you the contact normal. I personally don’t even calculate it at all. You can get it from the slope but that doesn’t work for edges and vertexs. I still claim their is a difference in how you move but I’m just going to drop it since the OP seems to be satisfied.

92c44e45a6d5fee06626f386d830dfde
0
EddyCharly 101 Dec 18, 2010 at 21:24

The third parameter you pass to D3DXIntersect is not correct.

D3DXIntersect expects a ray direction but you pass a vector that doesn’t represent the ray direction you want at all.

You want to pass a ray direction running up and down along the Y axis, so X and Z should be 0 for both rays and Y should be 1 or -1 respectively.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Dec 19, 2010 at 00:27

@TheNut

I’m just talking about terrain here, not objects.

The definition of terrain usually just means the static objects that make up your level. It does NOT mean that every point on the surface of the terrain has unique x and y coordinates (assuming z is up), like with heightmaps.