Green Units are safe from the Sniper, Red Units are not. The problem is in 3D and I need to be able to calculate where the Saftey Zones will be ... A unit is represented by a cylinder. Its position is taken from the center of the circle on the base of the cylinder and will always be on the Movement Plane. The Saftey Zone will be a polygon on the Movement Plane and if the units position is inside the polygon then the unit will not be visible by the sniper. A Saftey Zone may be produced by multiple Cover Objects (ie the image above should produce only 1 Saftey Zone). Cover Objects will be a made up of a set covex polygons (they can be assumed to be triangles if it makes the problem easier). The Sniper Position and Cover Objects are static so the Saftey Zones will only needed to be calculated once. So efficiency isn't really an issue, however accuracy is. Thanks.

Does a four-word answer help? "Cylinder-frustum intersection test."

Of course, you probably thought of that much. You just need to know how to do it? If so, somebody else can probably give you a better answer than I can.

Alternately, you could always do the dirty brute-force thing and just render the scene from the point of view of the sniper (with black, unlit, untextured geometry, except for, e.g., colored units), and see what color pixels are in the image you generate. (Naturally there are aliasing issues here though.)

If there are many CoverObjects I would try to subdivide the Movement Plane in very little quads and precompute the visibility of each one (you can count the pixels that were drawn with a Query like this).

In run time test you can find where each unit is projected on the movement plane and, counting how many of the quads are visible or occluded, you obtain a percetage of cover.

If there aren't many cover objects probably the Cylinder-frustum way is faster and easier.

If I understand you correctly you want to find one or more polygons in the movement plane which represents safe zones from the sniper. Assuming the height of the cylinders are equal, I would consider a plane parallel to the movement plane, but at the height of the top of the cylinders. Then I would project the silhouette of the cover objects onto this "zone plane". Finally I'd merge the projected polygons.

Quote:Original post by Emergent
Does a four-word answer help? "Cylinder-frustum intersection test."

Thats the easy part. It's the one word answer that I'm afraid of ... Calculus. The hard part is finding the exact area of the saftey zones.

I'm sure I can solve this if the unit was a single point ...

1. Project all faces of the Cover Objects onto the Movement Plane.
2. Combine the projected faces which overlap.

Then I would have a set of polygons on the Movement Plane which if the projected point was inside any of them it would be safe.

I am having real trouble when a box is used instead ( I think a box is easier than a cylinder, all boxes are the same size, are unable to rotate and its position is from the centre of the base).

Somehow I need to convert each polygon in the set to a Saftey Zone for the box.

Quote:
If I understand you correctly you want to find one or more polygons in the movement plane which represents safe zones from the sniper. Assuming the height of the cylinders are equal, I would consider a plane parallel to the movement plane, but at the height of the top of the cylinders. Then I would project the silhouette of the cover objects onto this "zone plane". Finally I'd merge the projected polygons.

Thats what I am working on at the moment. However if the top of the unit is safe it doesn't mean the rest of it is aswell. In the image the 2nd unit from the right almost has its top under cover, if it was moved a little to the left it would be completly under cover however part of the base would still be exposed.

It does simplify the problem by keeping the shape of the units silhoiette the same.

Quote:Original post by squashed_bug
However if the top of the unit is safe it doesn't mean the rest of it is aswell. In the image the 2nd unit from the right almost has its top under cover, if it was moved a little to the left it would be completly under cover however part of the base would still be exposed.

Good point. I think I'd make two zone planes then, top and bottom of unit cylinder, and consider a unit safe only if it's inside a "safe polygon" in both. Alternatively you could keep the "walls" of the shadow volume between the slabs, and perform a quick test against that (store an AABB for each safe zone volume, and check against that first).

Quote:Original post by Lord Crc

Quote:Original post by squashed_bug
However if the top of the unit is safe it doesn't mean the rest of it is aswell. In the image the 2nd unit from the right almost has its top under cover, if it was moved a little to the left it would be completly under cover however part of the base would still be exposed.

Good point. I think I'd make two zone planes then, top and bottom of unit cylinder, and consider a unit safe only if it's inside a "safe polygon" in both. Alternatively you could keep the "walls" of the shadow volume between the slabs, and perform a quick test against that (store an AABB for each safe zone volume, and check against that first).

That may still leave the middle of the unit exposed.

The problem is not to test whether a unit is safe, it is to find out where a unit is safe.

To test if a unit is safe ( I think this should work ):
1. Project all faces of the Cover Objects onto the Movement Plane.
2. Combine the projected faces which overlap. This will produce a set of polygons.
3. Project the unit onto the Movement Plane.
4. Test if the projected unit is inside any of the polygons.


The white dots represent the verticies of a Saftey Zone which is what I want to calculate.

Oh! I see what you actually want! I get it...

OK, here (I think) is the answer:

1. Project the occluder onto the plane at the tops of the dude's heads (as Lord CrC suggested), along the sniper's view lines, to get a 2d polygon in this plane.
2. Project this polygon STRAIGHT DOWN onto the floor, to get a polygon on the floor; I'll call in P1.
3. Project the occluder onto the plane at the dude's feet (aka, the floor), along the sniper's view lines, to get another polygon on the floor. Call it P2.
4. Your safe zone is the intersection of P1 and P2.

Check me on this!

(Edit: Lord CrC beat me to this suggestion; that's essentially what he wrote two posts back.)

Quote:Original post by Emergent
Oh! I see what you actually want! I get it...

OK, here (I think) is the answer:

1. Project the occluder onto the plane at the tops of the dude's heads (as Lord CrC suggested), along the sniper's view lines, to get a 2d polygon in this plane.
2. Project this polygon STRAIGHT DOWN onto the floor, to get a polygon on the floor; I'll call in P1.
3. Project the occluder onto the plane at the dude's feet (aka, the floor), along the sniper's view lines, to get another polygon on the floor. Call it P2.
4. Your safe zone is the intersection of P1 and P2.

Check me on this!

(Edit: Lord CrC beat me to this suggestion; that's essentially what he wrote two posts back.)

Project it STRAIGHT DOWN thats where the money is!!!

Thanks for your help guys!!!