Square and Circle Segment intersection

square-visible = (distance to origin < radius) and (abs(angle - centre-angle) < half-angle)

You'd typically test the angle with a dot-product or a cosine test to avoid having to do the abs.

you mean:

square-visible = (distance to square_origin < radius) and (abs(angle - centre-angle_of_the_square) < half-angle) ?

And by square origin you mean square center?

I think I've tried that one and it doesn't work, when radius > distance to square_origin and field of view doesn't cover the square.

That previous formula is wrong. When radius >= distance to square_origin every square, no matter at what angle, isn't seen.

I've finally had some time to think about this. To be specific:


There are 4 diffirent cases:


1. Fully inside FOV = SEEN
2. Intersecting the FOV arc = SEEN
3. Intersecting the circle, but not the FOV arc, and in the FOV angle = NOT SEEN (that's the hardest one which I can't figure out)
4. Fully outside = NOT SEEN

Hope it's clearer now.

I don't know if this is an option, but if you were to change the shape of the frustum to a simple triangle, the test would become dead simple (basically, you'd be able to use standard frustum culling techniques, only simplified for 2-d).

I'll also mention that frustum culling tests are often implemented in such a way that your example number '3' would actually pass. This makes the test conservative, of course (that is, it may return false positives in some cases), but also makes it more efficient (the rationale being that those cases will be infrequent enough that simplifying the test will be a win overall in terms of efficiency).

If you want an exact test though, you could simply perform the entire SAT (separating axis test) rather than the conservative version (again, using a triangle-shaped frustum). Since the 2-d test is much simpler overall than the 3-d version, doing the full test would probably be a perfectly reasonable thing to do.

As for testing against the current shape, here's what comes to mind:

1. Create a triangle that encloses the wedge (that is, the far edge of the triangle is tangent to the circle).

2. If the box touches both the triangle and the (full) circle, you have an intersection.

The circle-box test is very cheap, so this test probably wouldn't be that much more expensive than just performing the SAT alone.

The above is off the top of my head though, so I may have missed something. Also, there may be more efficient ways to test for intersection between a box and a wedge that I'm not thinking of. Actually, the test I proposed - the SAT-plus-circle-box test - could probably be streamlined a bit. For example, I think you might be able to do the initial culling based on the left, right, and near planes of the frustum (which would be a little more efficient than the full SAT), and then apply the circle-box test.