4 ms·
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 runt
by a1k0n 13y ago
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 13y agoI 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... :-) )