1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ This smells like homework... \$\endgroup\$ – jcora Feb 8 '12 at 21:46
  • \$\begingroup\$ Well it's not. :) \$\endgroup\$ – awdz9nld Feb 8 '12 at 23:26
  • \$\begingroup\$ OK, if you say so. \$\endgroup\$ – jcora Feb 9 '12 at 14:00
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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