Archived

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

SimDemon

Terrain Solved :: Now Terrain Collision Detection??

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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
// Each quad is 64x64

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

Thanks,
Matt U.

Share this post


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

iQuadX = Player.x / 64;
iQuadY = Player.y / 64;

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

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

The Player is on the quad 2,2 in your grid.

Share this post


Link to post
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 this post


Link to post
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/).

Share this post


Link to post
Share on other sites
Okay, well I ended up using the functions given by Aph3x, but I have a problem. I have a single array (not -2 or 3-dimensional) for storing the vertices of the terrain. In the code, it has this:


float htTl = mHeightMap->Val(x1, y1);
float htTr = mHeightMap->Val(x2, y1);
float htBl = mHeightMap->Val(x1, y2);
float htBr = mHeightMap->Val(x2, y2);


and this is my vertex structure:


struct TERRAINVERTEX // Define the terrain vertex structure

{
FLOAT x, y, z; // Position (x-, y-, and z-axis)

DWORD m_dwColor; // Vertex color

FLOAT u, v; // Vertex texture coordinates

};


How would I use x1, y1, x2, and y2 in my array of "TERRAINVERTEX"? It''s stored in the terrain class as "TERRAINVERTEX *m_pVertex;". If I knew how the "Val" function was meant to work, the way Aph3x showed me, I should be able to get it working in my own code.

If I cannot get this possible solution to work, I will go with your suggestion, hplus0603. =)

Thanks,
Matt U.

Share this post


Link to post
Share on other sites
Hmm yes - what I posted was assuming you had a regular 2d heightmap.
The Val function simply returns the height at the given heightmap coords. You're going to have an ugly job working out which are the four vertices required.

Have you considered using a regular 2d heightmap instead? Most other people do


[edited by - Aph3x on January 8, 2004 7:47:47 AM]

Share this post


Link to post
Share on other sites
Okay, I know what you mean. I have also stored the values in an "unsigned char" array. Is that what I would use for the equivelant of the "Val" function?

Share this post


Link to post
Share on other sites
not to be disparaging(sp?) SimDemon, but it sounds like you need to take some more mathematic courses, or get some books and self learn. I would actually recommend you get a whiteboard, they are excellent for cases like these if you dont visualize 3D well in your head(dont worry, most people don''t), just draw an example quad and figure out how to get certain values out of it, its mostly trig/geometry/algebra when you get to the basics of it.

Share this post


Link to post
Share on other sites
Thanks a lot, tri-thanatos. I may consider your suggestion. I can''t take very advanced 3D Math courses, as I am only a sophomore in high school. I may get a book or two.

Share this post


Link to post
Share on other sites
Hey guys, I''m sorry for so many posts, but I want to finish this project. Here''s a question Aph3x. When you gave me the code that included the "LERP" linear interpolation function, you passed "zFrac" as the first parameter to "LERP" inside the heightmap function. How is the "zFrac" variable defined?

Share this post


Link to post
Share on other sites
Hey! I got it working perfectly! I used Aph3x''s code for the 1D-Array for the XY quad index. Thank you all so much for the help! =) See you all around.

Share this post


Link to post
Share on other sites
The zFrac was a typo (my code is for OpenGL, using the Z axis instead of the Y axis) forgot to change it to yFrac :o

Yes, Thanatos is correct - you''ll need to understand the solution to get ahead
Take some time to understand the LERP macro - the interpolation idea is fundamental to many maths problems.

Share this post


Link to post
Share on other sites
I''ve been looking around on various websites about linear interpolation. I''m still looking at some, but I am understanding it. =)

Share this post


Link to post
Share on other sites