#### Archived

This topic is now archived and is closed to further replies.

# Terrain Solved :: Now Terrain Collision Detection??

This topic is 5302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Okay, I made a post earlier, that I couldn''t get my terrain class working. I changed a few values, and now it works. =) Now, I have come to a new problem. I have all my vertices for my terrain stored in the "TERRAINVERTEX" array, and I draw the terrain using a vertex buffer and an index buffer. My question is, how do I tell which quad the user is currently on, and how would I perform collision detection on the terrain, to keep the user from walking through the terrain? I haven''t found anything anywhere online, so I thought I''d ask here. =) Thanks in advance, Matt U.

##### Share on other sites
the standard method is to find the quad the player is located above, and do bilinear filtering with the height of the corners of the quad to get the exact height at the player''s position.

##### Share on other sites
Okay, thanks for the information. But that''s my problem. I don''t know how to go about performing those actions. I don''t know how to locate the quad on which the player is currently positioned.

##### Share on other sites
Well assuming its a grid of quads you could prolly just use the players x and z to find which quad he''s over then do a y calculation after that. This is just a guess though, i''ve never done anything like this before.

##### Share on other sites
so *thats* what bilinear filtering is....i had used that method a lot, but didnt have a name for it.

figuring out which quad you''re above:
1. easy case. all quads are same size in x,z. you can get the quad that you''re over by dividing the x,z positions of the player by the quad width/length. then use bilinear filtering.

2. hard case. quads are different sizes. easiest way off the top of my head is to construct planes from the edges of a possible quad, and see if you''re on the ''inside'' of all of them that way. this can be simplified further for 2d (xz only) into line tests instead (faster).

3. i do hope you have another structure for your terrain vertex positions,a dn your indices, because either of thee techniques requires a LOT of reading from whatever buffer you''re using. D3D vertex and index buffers are notoriously slow for reading because of the way AGP is optimized (write is fast, read is slow).

##### Share on other sites
It's bilinear *interpolation*.

You need the four heights at the corners of the quad being stood on, as explained already.
Then you need 3 linear interpolations:
One to find the interpolated height along edge A
One to find the interpolated height along the edge opposite to A
One to find the interpolated height between these two heights.

float MyHeightMap::HeightAtCoord(float aX, float aY)
{
// Calc surrounding heightmap indices:
int x1 = int(aX);
int y1 = int(aY);
int x2 = x1+1;
int y2 = y1+1;

// Shouldn't have got in this method if this asserts!
ASSERT(x1 >= 0 && x2 < mHeightMap->Width() &&
y1 >= 0 && y2 < mHeightMap->Height());

float xFrac = aX - x1;
float yFrac = aY - y1;

// Get heights for corners.
float htTl = mHeightMap->Val(x1, y1);
float htTr = mHeightMap->Val(x2, y1);
float htBl = mHeightMap->Val(x1, y2);
float htBr = mHeightMap->Val(x2, y2);

return LERP(yFrac, LERP(xFrac, htTl, htTr), LERP(xFrac, htBl, htBr));
}

Where LERP is a linear interpolation function:
#define LERP(f,v0,v1) ((1-(f))*(v0)+(f)*(v1))

[edited by - Aph3x on January 9, 2004 7:32:41 AM]

##### Share on other sites
Okay, I was told to (in this post) to divide x/z by tile width/height. What would the equation be? And what data type would the quad the player is on be?

I tried:

int g_nQuad = 0; // Global (just testing it)

// This is where I will get the quad the player is on

What is the equation, given "g_vecPos", which is the player''s position in the world (type D3DXVECTOR3).

Thanks,
Matt U.

##### Share on other sites
If your terrain forms a 2D grid, then the quad the player is standing on is:

ie, Player.X = 128, Player.Y = 128.

iQuadX = 128 / 64 = 2;
iQuadY = 128 / 64 = 2;

##### Share on other sites
That won''t work. This is a 3D terrain map. Thanks for the attempt, but the player''s position is stored in ''float'' values (ex. 8.8837f). Anyone else, please?

##### Share on other sites
That will absolutely work, assuming your terriain is tiled (regular X/Z values, say).

Just take player.x and player.z and divide by the side length of your tiles, and you get a (fractional) tile address. The integer part is what tile it is; the fractional part is how far towards the next tile it is (i e, your interpolation value along each axis).

However, getting the height under the player isn''t the greatest, because you''ll clip through very steep hills if the player is thicker than a single line. Instead, I recommend getting a more or less ready-made collision system, such as OPCODE (http://www.codercorner.com/Opcode.htm) or Magic (http://www.magic-software.com/) or ODE (http://www.q12.com/ode/).

1. 1
2. 2
Rutin
20
3. 3
JoeJ
17
4. 4
5. 5

• 37
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631704
• Total Posts
3001822
×