Archived

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

Terrain - Ray intersection

This topic is 4955 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
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
Any read back from the card can cause a serious stall and should be avoided at all costs! You could keep a duplicate somehow but that may also be painful

Share this post


Link to post
Share on other sites
quote:
Original post by Trip99
Any read back from the card can cause a serious stall and should be avoided at all costs! You could keep a duplicate somehow but that may also be painful


What do you mean by duplicate?
Do you mean allocating an offline pbuffer and reading from it will not stall the pipeline?
I could allocate a really small buffer, just for the area around the crosshair, and transfer the pixels from the frame buffer to the pbuffer (which is done on VRAM) and then read back from the pbuffer.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"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."

No, that''s not needed.
If your terrain has uniform spacing between vertices, then you don''t need to do this. Every pixel in your heightmap then represents two triangles. So you can easily check when there would be a possible intersection. And then you also know with what triangles it would possibly collide. You then perform real ray/triangle tests on only those polys.

On that way you end up with a lot less ray/triangle tests than you would have using your quadtree what you do now.

Similar algorithms are also used to trace through voxel grids when doing raytracing or volumetric stuff.

Cheers,
- John

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
No, that''s not needed.
If your terrain has uniform spacing between vertices, then you don''t need to do this. Every pixel in your heightmap then represents two triangles.


What if I use more vertices than there are pixels in the height map?
And even if I use less, every pixel represents a vertex, not two triangles, the triangles which OpenGL assembeles are the result of connecting those vertices, so actually most triangles don''t correspond to any pixel in the height map but to an interpolation between them.

Checking the height map will be accurate for voxels, which are discreet by definition but not on a continiues domain like a triangle mesh.

I''m not saying that checking the height is wrong, It might give an accurate intersection point with enough tests, but it''s not reliable enough for picking the right polygon.

Take a look at UT2003 for example. If you shoot the ground with the deafult gun it just creats a puff of smoke on the intersection point. But if you use the green goo gun it sticks to the polygon it hits with correct orientation, for that you need to pick the right polygon.
I want to be able to achieve both types of effects so I need a reliable (and fast) picking method for ray-terrain collision.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"What if I use more vertices than there are pixels in the height map?"

Do you? Even if so, do the same as what you did with your quadtree. You know how to construct the triangles in the neighborhood of the pixel. This is always faster than checking full 16x16 quads. Besides that the first intersection you get is the closest using this way.


"And even if I use less, every pixel represents a vertex, not two triangles, the triangles which OpenGL assembeles are the result of connecting those vertices, so actually most triangles don''t correspond to any pixel in the height map but to an interpolation between them."

Yes sorry that''s what I meant But you can get the triangles based on the heightmap.

Anyway, it will work, I implemented it myself too. But I''ll leave it up to you. Maybe it won''t work in your case, you probably know that better than me. But it definitely works for regular heightmaps.


Share this post


Link to post
Share on other sites
DogDog: no, that would still mean you would have to read back from the graphics card, I meant actually render again into another surface not held in video memory but then now I think about it that would probably be just as slow - so sorry but I think you will have to go with one of the other ideas.

Share this post


Link to post
Share on other sites