collision detection - How to determine which cells in a grid intersect with a given triangle?

I'm currently writing a 2D AI simulation, but I'm not completely certain how to check whether the position of an agent is within the field of view of another.

Currently, my world partitioning is simple cell-space partitioning (a grid). I want to use a triangle to represent the field of view, but how can I calculate the cells that intersect with the triangle?

Similar to this picture:

The red areas are the cells I want to calculate, by checking whether the triangle intersects those cells.

Thanks in advance.

EDIT:

Just to add to the confusion (or perhaps even make it easier). Each cell has a min and max vector where the min is the bottom left corner and the max is the top right corner.

Answer

Calculate the three corners of your fov triangle, rotate them to be facing the correct way and such, and then do one of:

1) do a point-in-triangle test for all the potential targets

2) calculate the bounding box of the this triangle, and do a point-in-triangle test for all potential targets in cells in this bounding box - this will be very straightforward code to debug

A similar approach is to use a quadtree rather than a grid and do the intersections on that. If the O(1) tile access is speeding you up, then just testing all the cells in the bounds of the fov triangle for in-triangle ought to be so fast as to be instant. As you're looking at other options, I presume its not and that the O(1) is actually taking a massive cache miss cost as you thrash your cache. You could of course perhaps look at prefetch instructions to annotate your bounding box walk with...

3) 'rasterise' this triangle and check the cells that it 'paints' - likely the most efficient code, but perhaps only marginally as I'd speculate its all dominated by cache miss times and depends on how complex your cells are and how occupied they are.

An alternative approach is to render the FOV to an off-screen bitmap and then read the pixel value for each of your objects; you can't 'unmix paint' but with a limited number of objects and by carefully choosing your paint you can deduce who saw who. This approach is similar to how many games work out what the user clicked on - they draw the scene off-screen using solid colours for the hit-areas. GPUs are very fast at triangle fill...