Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Imagine that we have a 2D uniform grid of dimensions N x N. For this grid we have also pre-computed a visibility look-up table, e.g. with DDA, which answers the boolean query is cell X visible from cell Y?

The look-up table is a complete graph KN of the cells V in the grid, with each edge E being a binary value denoting the visibility between its vertices.

If any given cell has its visibility modified, is it possible to extract the subset Edelta of edges which must have their visibility recomputed due to the change, so as to avoid a full-on recomputation for the entire grid? (Which is N(N-1) / 2 or N2 depending on the implementation)

share|improve this question
This smells like homework... – jcora Feb 8 '12 at 21:46
Well it's not. :) – Martin Källman Feb 8 '12 at 23:26
OK, if you say so. – jcora Feb 9 '12 at 14:00
up vote 1 down vote accepted

Perhaps you should look at "The Visibility Skeleton: A Powerful And Efficient Multi-Purpose Global Visibility Tool," Durand et al., a 1997 paper that Google Scholar shows has been cited 148 times since. The question you pose has been heavily studied! One of the key search phrases is walkthrough.

share|improve this answer
Thanks, will have a look at this! – Martin Källman Feb 8 '12 at 23:26

If it is not possible to solve this in closed form, then maintaining a separate mapping of each cell and every cell pair which's line intersects said cell might also be an option. This obviously consumes more memory, but the data is static.

The increased memory requirement could be reduced by introducing a hierarchy, subdividing the grid into smaller parts, and by doing so the above mapping can be reused for each sub-grid. This would come at a cost in terms of increased computation relative to the number of subdivisions; also requiring a resumable ray-casting algorithm.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.