# Heightmap Collision

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

## 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 on other sites
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 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 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 on other sites
Alright that makes sense thanks.

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

##### 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 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 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...

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634091
• Total Posts
3015435
×