Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Problem
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.

Question
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... –  akled Feb 8 '12 at 21:46
    
Well it's not. :) –  Martin Källman Feb 8 '12 at 23:26
    
OK, if you say so. –  akled Feb 9 '12 at 14:00
add comment

2 Answers

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
add comment

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
add comment

Your Answer

 
discard

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.