Game Programming Algorithm Q: How to determine how much of a model is visible

[JoshV]

So here is a question for technical folks: In a 3D environment, I'm trying to determine how much of a model is visible from a given viewpoint. (For example, model A is shooting at model B in an abstract strategy game, and needs to know how much cover model B is behind.) To top it off, I'd also like to know how much of the cover is Solid cover. Trees/foliage and office buildings are soft cover, while canyon walls and bunkers are solid cover.

I've thought of a few ways to determine this, but both have their downsides, maybe someone has a better idea:

1. RenderToTexture. Render model B as a solid color from the viewpoint of model A to a texture, then render the entire scene to the texture, also color coded. (So target model is red, standard cover is green, solid cover is blue) Obviously lighting & shadows would be disabled for this render. Then I'd just need to compare the two textures to get the percentage of cover, and the percentage of solid cover.

Upside is that its fairly accurate and requires no more than basic ratio math and would work on every single model without any preparation.

Downside is it requires two textures (which could be small, 64x64 could be accurate enough) and rendering the scene. Which could be slow, and also tends to require low level hooks to whatever engine is being used -- which I may not have access to.

2. Raycasting to model parts. Given that most models have a skeleton, I could do a collision ray to each bone from the camera view, and see how many of them are visible. The downside to that is that bones aren't really spaced equally, since their tend to be more bones in the hands and feet than in the head, and then it could fall completely flat for using something other than a humanoid model, like a tank, which might have weird bone layouts. Some of that could be mitigated by flagging certain bones, but that requires the model be tagged in advance.

So anyone else have a good idea how they'd go about determining something like that?

[Lunch of Kong]

Sounds as if you're talking about something related to the visual surface determination work that has to be done to correctly render the image in the first place. If it's possible to reuse the information used to determine how much of an object to draw, you'd get your % hidden.

http://en.wikipedia.org/wiki/Hidden_..._determination

[TheTrunkDr]

So here is a question for technical folks: In a 3D environment, I'm trying to determine how much of a model is visible from a given viewpoint. (For example, model A is shooting at model B in an abstract strategy game, and needs to know how much cover model B is behind.) To top it off, I'd also like to know how much of the cover is Solid cover. Trees/foliage and office buildings are soft cover, while canyon walls and bunkers are solid cover.

I've thought of a few ways to determine this, but both have their downsides, maybe someone has a better idea:

1. RenderToTexture. Render model B as a solid color from the viewpoint of model A to a texture, then render the entire scene to the texture, also color coded. (So target model is red, standard cover is green, solid cover is blue) Obviously lighting & shadows would be disabled for this render. Then I'd just need to compare the two textures to get the percentage of cover, and the percentage of solid cover.

Upside is that its fairly accurate and requires no more than basic ratio math and would work on every single model without any preparation.

Downside is it requires two textures (which could be small, 64x64 could be accurate enough) and rendering the scene. Which could be slow, and also tends to require low level hooks to whatever engine is being used -- which I may not have access to.

2. Raycasting to model parts. Given that most models have a skeleton, I could do a collision ray to each bone from the camera view, and see how many of them are visible. The downside to that is that bones aren't really spaced equally, since their tend to be more bones in the hands and feet than in the head, and then it could fall completely flat for using something other than a humanoid model, like a tank, which might have weird bone layouts. Some of that could be mitigated by flagging certain bones, but that requires the model be tagged in advance.

So anyone else have a good idea how they'd go about determining something like that?

If this is an abstract game how much can you fudge the cover? Both of these seem to give you extremely precise values for how much of the model is visible, but do you really need that level of fidelity, can you not cut it into more finite values (say 25%, 50%, 75%, 100%)? Could you not cast rays to the four bounding box corners to determine cover and be done with it? Unless you're going for some sort of extreme simulation even an extremely rough approximation will likely give acceptable results.

Sounds as if you're talking about something related to the visual surface determination work that has to be done to correctly render the image in the first place. If it's possible to reuse the information used to determine how much of an object to draw, you'd get your % hidden.

http://en.wikipedia.org/wiki/Hidden_..._determination

If the position of the source for the cover calculation doesn't correspond to the camera, this is a whole lot of work and would likely have to be done entirely in software. I would think running a Z-buffer (or something similar) over every possible source/target combination in a strategy game would completely bog down your CPU.

[JoshV]

That's a good point about the collision object, the programmer in me likes the inherent accuracy of the first method, but it may be impractical to set up. It certainly wouldn't be practical for a real time game, but luckily I'm going with a turn based game, so I only have to compute it one at a time, and even a delay of 30ms wouldn't be a huge deal.

The eight corners of a bounding box may not give that much accuracy but I suppose I could go deeper by looking at the bounding box of each of the model's mesh parts, or a halfway step by checking the midpoints (or quarter points) of the bounding box.


Re: Lunch of Kong: That's essentially what the first method is, my standard camera is overhead/iso like an RTS, so to determine cover, it is rendering the scene to a texture in a special way is just giving me a more detailed z buffer.

[TheTrunkDr]

That's a good point about the collision object, the programmer in me likes the inherent accuracy of the first method, but it may be impractical to set up. It certainly wouldn't be practical for a real time game, but luckily I'm going with a turn based game, so I only have to compute it one at a time, and even a delay of 30ms wouldn't be a huge deal.

The eight corners of a bounding box may not give that much accuracy but I suppose I could go deeper by looking at the bounding box of each of the model's mesh parts, or a halfway step by checking the midpoints (or quarter points) of the bounding box.


Re: Lunch of Kong: That's essentially what the first method is, my standard camera is overhead/iso like an RTS, so to determine cover, it is rendering the scene to a texture in a special way is just giving me a more detailed z buffer.

I have no idea what your game design is but I'm getting the feeling that you're going way overboard on the precision. You don't need to know exactly where the target's toe is to get a very good approximation of cover for a game.

That level of accuracy would also have significant gameplay effects. Artistic license and aesthetics would now become game balance concerns as the actual position of every vertex of the model becomes significant. If it doesn't or you don't want it too then you don't need that level of accuracy and can do far more approximating, and far less ray casting.

Much of this is likely from my own personal experience with real time games on more limited hardware where I could count on both hands the number of rays that could be cast in a single frame. The idea of casting hundreds to a single model really just boggles my mind.

[JoshV]

Well, I'm turn based (but not tile based, or I'd use that for cover calculations) , so casting 32 rays for one model is...well only 32 rays, with little to nothing else going on in the background. No AI, no physics, just rendering and animation, and no other rays being cast simultaneously elsewhere. And its only checking rays against objects in the frustum, which should cut things down a bit.

You're correct in that I'm probably going overboard though, but I can think of situations where the bounding box corners alone would run into trouble. A tank with a tree running through the middle, missing all the corners of its rectangular bounding box, for example. So I think at the very least, a center of the bounding box check is in order. I think doing the mid points to all box lines would probably give better accuracy as well, but double the number of rays being cast. Though if we culled the box corners that are behind other corners, that would drop the number of rays that need to be cast.

I'll probably just play with it, starting off with a simple box points + center of box cast and get more complicated only as necessary. Thanks for letting me bounce ideas off of you TheTrunkDr.

[Coca Cola Zero]

What is your target platform? Do you know about hardware occlusion queries (if relevant to your platform)? These are generally performed against the "camera" for culling, but your camera can be whatever you want it to be during the test (including the viewport from another object).

Using HOQ (if available) would likely be faster and easier than rolling your own implementation of it, though you certainly will still want to do something to minimize the amount of queries you're doing if your scenes have a lot of objects because even though HOQ is pretty fast on modern hardware the state changes will still hurt if you're querying many objects against many other objects. But for your purposes you don't even really need frame-exact results, so you could keep a running queue of queries and results (HOQ results don't have to be frame locked) and it wouldn't be too big of a deal.

[JoshV]

I started out my hobby project using XNA, which actually has HOQ support. But I got a little impatient at the thought of doing all the work to build an engine from the ground up, and I am currently working in UDK, but I don't think they have any HOQ access through unreal script from what I can tell. Maybe if I was a licensee and had the source.

[Zylon]

Casting rays sounds a bit doomed for determining a general "visibility" value, because it's very easy to imagine degenerate situations which would break it for any trivial number of rays. A tank sticking out from behind a building: No problem. A tank parked behind a row of trees: Yikes! Discontinuous cover will be this algorithm's undoing.

[Chris Nahr]

Yes, don't try to determine visibility for hit/damage chance purposes by raycasting. You'll waste an enormous amount of computing time, and you'll still have unusable results all over the place.

Instead, think what situations can occur that are relevant to your gameplay, then find proper abstractions so that a hit/damage percentage can be determined by simple geometric calculations:

1. Abstract target to a box, determine area projected to viewing angle.
2. Abstract occluding object to a box, determine area projected to viewing angle.
3. Compute overlapping area between the two, given viewing distance.
4. Combine with some value that determines the occluding object's inherent solidity and transparency.

Substitute spheres, pyramids or cylinders for boxes as appropriate.