Sign in to follow this  
jakesee

Height Map collision for R * 2^N square cells

Recommended Posts

Hi,

I have a height map 1200x1200 cells which translates to (75*2^4)(75*2^4) cells. aka, my smallest quad tree node contain 75x75 cells.

I figured that if the dimension were exactly 2^N by 2^N then I can traverse the tree all the way down to a single cell and then interpolate the single-cell-node's highest and lowest AABB corners for that cell and it will give me the correct intersection.

Unfortunately this is not the case, I wonder what is the method to do collision for R * 2^N square cells?

I am not sure if I want to use a physics library just for this function... but even if I do, which one will support height maps of arbitary dimensions?

Thanks.

Share this post


Link to post
Share on other sites
What platform are you running on? 1200 x 1200 is just a million and a half heights to store, not too much data...for a heightfield representation, on most platforms. (Single precision floating point would need 5.5Mb...just a bit more than a single 1024x1024 uncompressed RGBA 8-bit texture.) For collision purposes, why not just keep in system RAM an array with all the height values, then directly index into that to compute the exact height without bothering with the quadtree? Just use your quadtree partitioning for rendering.

The situation is a bit trickier if you're doing something other than a pure height lookup. If you do have an object that approaches the terrain from some angle, and might hit a mountain from the side rather than from above, then you could use the quadtree node bounding boxes to determine candidate regions where you might collide, then within each candidate box do collision tests with the triangles.

There's a lot of documentation and reference material available for doing this sort of thing for general collision detection, of course.

Share this post


Link to post
Share on other sites
@grhodes_at_work

[qoute]There's a lot of documentation and reference material available for doing this sort of thing for general collision detection, of course.[/qoute]

I tried searching a lot but most examples start with a height field of (2^n)^2 dimension. I am not just doing 1200x1200, but at any one time, 4 of these map will be in memory. The maps are streamed/deleted on another thread as the eye position navigates around.

Anyone can tell me whether existing collision library also has this limitation? I could try my luck reading some opensource implementation if anyone can recommend.

Share this post


Link to post
Share on other sites
Depends on your situation and collision needs.

If you are just trying to have a capsule shape "walk" around on the terrain, you can collect some height values for a sub-square around the capsule's position and then create a mini-grid and submit this to a collision library.

For example, if the player starts in the center of an 8192x8192 heightmap, you can estimate from the player's maximum velocity that it would never need to collide with more than 10 height-values around itself. Then generate a 20x20 sub-square centered at players (x,z) position.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this