[dllu]

Related:

1) a tutorial on the same topic by Red Blob Games: http://www.redblobgames.com/articles/visibility/

2) a public domain Javascript visibility polygon library that runs in O(n log n), which is actually used in the Nothing to Hide game: https://code.google.com/p/visibility-polygon-js/

3) a blog post by author of said library discussing the algorithm: http://byronknoll.blogspot.ca/2013/05/on-log-n.html

Shooting a ray to every vertex and then naively computing intersections takes O(n^2) since there are n rays with up to O(n) intersections each. It is interesting to read and think about O(n log n) algorithms for computing the visibility polygon.

[a1k0n]

I didn't see this mentioned in those articles, so I figured I'd mention it: If the level has a lot of geometry, you could also make a BSP tree, and then at runtime you'd just have an O(log n) lookup, plus an O(m log m) running of the same algorithm on a pruned subset of m vertices stored in the BSP node. Each BSP node would contain only the edges which can possibly be seen from a particular area. The tree might be kind of big, though.

[frownie]

I think this particular idea of storing information in the BSP leaves was the big innovation brought to us by Id Software. Now, the elephant in the room is : how to build a well balanced BSP tree... But well, that's an entirely different question (I was a computer geometry researcher years ago... :-) )