Calculation: Is a sphere/square/plane visible from a certain point?

Question

I'm searching for a way to detect if a form (shape can be changed if algorithm requires it) is visible from a single point in a 3D tile-based world. This should be used as some kind of wall-hack protection to hide players from the client if they are fully covered behind a wall.

This does not have to be extremely precise. The only condition is that the algorithm never returns a false-negative. Therefore I thought it might be the easiest choice to create a rather large sphere around each other player and peform visibly operations from the viewpoint to that that imaginary sphere. I'm planning to use this on larger maps and only if players are far away from each other. It wouldn't be a problem if you could see players that a behind a wall right next to you.

Since I have no clue how the solution may look like I'm searching for a very abstract description of how such an algorithm works.

I found this very similiar question: Precomputing Visibility But I think this led me into the wrong direction since my main aspect ist speed rather than accurancy.

Answer 1

A system which never has any false-negatives is going to need to rely on some variant of graphics occlusion query. Ray casts and other physics-based measures will not work.

You can use a GPU Occlusion Query for the easiest solution. Render your static geometry (just solid geometry, no need for colors or textures or other surface effects; you don't even need a color output buffer, all you are doing is building a depth buffer and testing against it). Then under a depth-pass query render the player. The query will tell you if any fragment of the player geometry passed the depth test, meaning it was in front of some static geometry and not clipped/culled. Again, the render is just vertex positions (and skeletal animation data) and nothing else and no need for a color buffer; very similar to a shadow map except you never need to read from the generated depth buffer.

I haven't done any performance tests myself and haven't seen any number from recent hardware, but in the past it has been faster to do this in the CPU with a software triangle rasterizer. Part of the reason is that the GPU may be fully utilized rendering the game. The bigger part of the reason is that it takes a lot of time to send the render commands to the GPU, have it render everything, and then return a result. A low-resolution depth-only render of simple geometry is not difficult to do on the CPU, can be easily multi-threaded and vectorized, and might be more efficient (though even if it is, you may not need that extra performance; not every game is a massive AAA affair).

Note again that you can do all these occlusion tests in low resolution. Just because your game is rendering at 1920x1080 doesn't mean the occlusion queries need to happen at that size. It's typical to use some smaller size with multi-sampling disabled, possibly not even the same aspect ration. If it's too small you'll start getting noticeable false-negatives. With any size reduction you may get some very minor false negatives (say, if only a couple pixels of the player is visible, not something other humans would actually notice). If you really, really need zero false-negatives (you don't) you'd want to do occlusion queries at full resolution with the same multi-sampling setup, but that will hit performance pretty hard.

Answer 2

It seems like you need an occlusion query algorithm.

Roughly speaking in order to check if certain object is visible from a certain point of view, one way is to use a ray casting algorithm:

1. Cast a ray from the viewer point of view to the object.
2. If the ray hits any other object in its way before hitting the target object then you can set the target object as partially invisible.
3. This is usually not enough and you need to ray cast multiple rays.

Even if you are ray casting bounding volumes and not actual triangle meshes, this will more likely be very slow (unless you have a very small scene), because the objects are not spatially sorted so you will end up checking every object, even if they are unlikely or even far away from the ray's path.

In order to solve this problem you need to use some kind of spatial partitioning like grid, octree, or even bsp trees. This way you will be able to only test objects that are more likely be in the way.

I also answered a similar question here. And covered multiple types of visibility determination algorithms here.