Jump to content
  • Advertisement

Archived

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

DogDog

Terrain - Ray intersection

This topic is 5241 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''ve coded a simple terrain demo based on a height map. I thought about doing a simple third/first person shoter to play with my friends (since I have multiplayer already working). I''m trying to find the fastest way of doing terrain - ray intersection and finding the intersecting polygon (quad or triangle of the terrain). Since I use a quad-tree for frustum culling the terrain, I also use it to find possible intersecting terrain tiles with the ray, which is quite fast. Now I need to do ray-triangle intersection tests with all the polygons in the ray''s path along the possibly intersecting tile. A size of each tile is 16x16 quads (17x17 vertices), so the intersection test can slow down performance quite a bit. I was thinking of a way of minimizing the ray-triangle tests, and I''ve come up with this method: Since I''m not using the alpha channel for the terrain rendering I can encode 256 values in it. 256 is exactly the number of quads in one tile. So now I can query the frame buffer at the cursor''s location and obtain the alpha value. Now I traverse the quad-tree like before and obtain a list of possible intersecting tiles (fast AABB-ray test). now I need only to check for each tile the quad in the alpha value and the closest intersecting quad is the one I need. The main advantage here is that the triangle-ray tests are minimized to only two per tile instead of a possible 40 per tile if testing each quad along the ray''s path. The main disadvantge is that the alpha channel can''t be used for the terrain and additional color values need to be passed, and of course only 256 values are available. I''m sorry for the long post, but I would really like to know what you think. Is this going to even work? are there any faster ways for doing this? am I just wasting my time with this method???

Share this post


Link to post
Share on other sites
Advertisement
From what I know, querying the frame buffer is usually a bad idea, as it can stall the pipeline. IMO image space solutions such as this are generally to be avoided.

If you really want to speed up your test, beyond the quadtree approach, you could create an AABB tree for each quad, with one AABB for the whole quad, which is then recursively divided into four children. This should home in on the triangles in question pretty fast.

Does that help at all? Also, others may disagree about the image space thing. I''ve never actually done it, so I can''t say for sure.

Share this post


Link to post
Share on other sites
quote:
Original post by jyk
From what I know, querying the frame buffer is usually a bad idea, as it can stall the pipeline. IMO image space solutions such as this are generally to be avoided.


I don't think querying one pixel from the framebuffer will cause any noticeable performance degradation, but I might be wrong.

quote:

If you really want to speed up your test, beyond the quadtree approach, you could create an AABB tree for each quad, with one AABB for the whole quad, which is then recursively divided into four children. This should home in on the triangles in question pretty fast.


Like I said, I'm already doing that, but still I'm left with more than a few triangle-ray tests.
When you say "AABB for each quad" you must mean "for each tile", that's what I'm doing - a quad tree for the tiles.




[edited by - DogDog on May 19, 2004 11:03:26 AM]

Share this post


Link to post
Share on other sites
"Like I said, I''m already doing that, but still I''m left with more than a few triangle-ray tests.
When you say "AABB for each quad" you must mean "for each tile", that''s what I''m doing - a quad tree for the tiles."

I may misunderstand, and you may already be doing this. But you could subdivide the tile AABBs further, to the level of, say, eight triangles per AABB (or even two). Intersecting with the AABB tree would definitely be faster than testing all the tris in the tile.

Again, never mind if you''re already doing this...

Share this post


Link to post
Share on other sites
Querying 1 pixel is hardly likely to cause a major problem.

Reading back from the framebuffer has the effect of causing the querying method to hang untill all queued rendering has be performed. This is bad if you do I halfway though rendering a massive triangle filled vertex buffer. However, if you do it just before you swap the buffers, when a pipeline flush is forced anyway, it will have little noticable impact.

There is the slight side issue that reading data back accross the AGP bus can be a little painfull.

Share this post


Link to post
Share on other sites
I''m currently using 256x256 quads, subdividing the quad-tree to the level of 8 or 2 quads (or triangles) per tile will create a huge tree and a much slower one to traverse.

In my case, I also use the quad-tree for frustum culling, and 16x16 gives me the best performance after a lot of testing and trying of different tile dimensions.

I''m also not testing the ray against every triangle in the tile but only those that lie in the ray''s path inside the tile.

Subdividing the tiles to smaller will give you a better fit on the AABBs, but only to a certain point where it just slows you down.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You can also project your ray origin onto your heightmap, and draw a virtual line on the heightmap in the direction of the ray, and use the heights to check possible collisions between terrain polygons and the ray. If your ray origin is lower or equal than your current heightmap pixel you are checking while ''drawing'' this virtual line, there is a possible intersection.

Maybe there are even faster methods though. But this is very fast Using a quadtree you still end up with lots of polys to test with and you have an overhead of checking the quadtree nodes on intersections too.

You have to be careful about precision though, when traversing the virtual line on the heightmap.

Cheers,
- John

Share this post


Link to post
Share on other sites
quote:
Original post by zoggo
Reading back from the framebuffer has the effect of causing the querying method to hang untill all queued rendering has be performed.


It makes sense that reading from the back-buffer will cause the call to hang, but is reading from the front-buffer will cause the same effect?

Since the ray-test will most likely be an input-event it will be difficult to synchronize the framebuffer querys, espicially with multiplayer involved.


Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
You have to be careful about precision though, when traversing the virtual line on the heightmap.


That is exactly why I dont want to use the height map. For sufficent accuracy I would have to interpolate between the height map values and check very small segments of the ray, and even then I will only get a point of intersection and what I really need is the actual polygon hit, so I could draw a decal over it. Since the terrain map is much bigger than a single quad even the slightest error will give me the quad next to the one actually hit and that will be noticeable up close (think about shooting the ground near your feet).


Share this post


Link to post
Share on other sites
quote:
It makes sense that reading from the back-buffer will cause the call to hang, but is reading from the front-buffer will cause the same effect?


Can go either way. On an ideal card with good drivers your call will simply grab the pixel value straight from the framebuffer and send it back. The slight overhead of going backwards over the AGP bus will hopefully be small.

However, some cards have a nasty habit of bringing the entire frame back over the AGP bus when they detect reads. Hopefully this shouldn''t happen but it''s a little unpredictble. Generally, older graphics cards were optimized with forwards-only operation in mind.

In short, dunno.

Share this post


Link to post
Share on other sites

  • Advertisement
×

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!