Viewport Culling

Recently we discovered that it would actually save some time if we could figure out which entities that were outside of the visible area and not draw them. So we made a hierarchical grid data structure (hgrid) and some very coarse ‘collision detection’ to do so. The hgrid uses hashing to store the entities, allowing for an infinite number of grid cells, theoretically, maintaining the needlessness of specifying world boundaries when using the engine, since the box2dweb physics engine also allows for infinite world sizes. The hashing combined with a double linked list structure within the hgrid allows for a time complexity of O(1) for┬áinsertion and deletion, making it straightforward to keep the hgrid up to date – an entity that is moved is simply removed from the grid and then inserted again.

However, the first implementation of the hgrid contained a fatal bug: when removing an object from the double linked list, it’s pointers to the previous and next objects weren’t nullified, resulting in circular chains within the list, in turn resulting in infinite loops when checking the viewport against the grid. It was a very hard bug to track down, since the program seemed to work fine until one entity sharing a grid cell with at least one other entity was moved out of that cell and then back into it. The program would then freeze due to the infinite loop as mentioned above, causing confusion among the testers.

Unfortunately, the results of culling are rarely something to show, mainly because the fundamental purpose is to figure out what NOT to show. Nevertheless, appended below is a screenshot showing the successful culling of approximately 2000 entities outside the visible area of the canvas. Enjoy.


Be Sociable, Share!

Leave a Reply