Jump to content
• Advertisement

# Heightmap Collision

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

If you intended to correct an error in the post then please contact us.

## Recommended Posts

I'm using the code at the bottom of this post to render a heightmap using triangle strips. I need to implement collision detection for the heightmap and have a good idea on how to do so. However, I need to calculate which triangle the object is currently above. How can I find this out? Thanks for any replies.
for(int z = 0; z < mapsize - 1; z++)
{
glBegin(GL_TRIANGLE_STRIP);
for(int x = 0; x < mapsize; x++)
{
glVertex3i(x, (int)(coords[x][z] * scale), z);
glVertex3i(x, (int)(coords[x][z + 1] * scale), z + 1);
}
glEnd();
}


[Edited by - dotnetted on August 9, 2005 11:11:31 PM]

#### Share this post

##### Share on other sites
Advertisement
Finding the triangle is the easy part, assuming your heightmap is a regular grid. Given an xz coordinate, you first need to find the corresponding quad, and then the corresponding triangle. The first step requires simple division, and the second can be done with the perp-dot product.

If you need more details, I could probably sketch out some pseudocode.

#### Share this post

##### Share on other sites
Im also working on something similar. I understand how to find the quad, but Im not sure how the perp-dot product is used to find the triangle. Can you how its done? Thanks.

#### Share this post

##### Share on other sites
Assuming a regular grid, each quad is divided into two triangles by a diagonal line connecting two of the corners. Once you've determined in which quad the point lies, you just have to determine which side of the line the point is on to determine the corresponding triangle.

If you've worked with planes in 3d at all, it's exactly the same principal. You can express the line in normal-distance, point-normal, or equation form (your choice). You can then find the signed distance from the point to the line, which will tell which side of the line the point is on.

In 2d, the normal to a line is perpendicular to the line direction vector. The vector perpendicular to a vector (x,y) is either (-y,x) or (y,-x). Note that since you're only interested in the sign of the distance, the normal needn't be normalized. Note also that all the lines (presumably) have the same normal, probably (1,1) or (-1,1), so the actual computation is quite simple.

#### Share this post

##### Share on other sites
Alright that makes sense thanks.

#### Share this post

##### Share on other sites
Yep problem solved, thanks.

#### Share this post

##### Share on other sites
Surely it's even simpler than that?

a line from bottom left to top right of a square, and a point at x,y in that square. all coordinates relative to the bottom left corner. The point is in the bottom right triangle if (x > y). No dot products required.

#### Share this post

##### Share on other sites
Quote:
 Surely it's even simpler than that?a line from bottom left to top right of a square, and a point at x,y in that square. all coordinates relative to the bottom left corner. The point is in the bottom right triangle if (x > y). No dot products required.
Yup, the dot product test reduces to a simple comparison in this case. I just thought I'd explain the theory behind the test, as it could be useful for other situations.

#### Share this post

##### Share on other sites
Once you know the triangle you are over, you use the dot product with the normal of the triangle to findout if you are below the triangle. If you are below the triangle, how do you find a point on the triangle that has your current x and z coordinates but a y coordinate directly on the triangle face?
I think you solve the dot product equation for y...

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5
• Advertisement

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633297
• Total Posts
3011247
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!