class Game::SceneCuller

The nature of Glest's mechanics (units exist in a cell, objects exist on a tile) mean it lends itself naturally to a cell division approach to scene culling. The division is already done for us, we just need to determine which cells are visible. Glest used what was described as a 'kind of 2D frustum' to determine this, with much more freedom of camera movement in the Glest Advanced Engine this technique breaks down.

The new solution is to extract the view frustum, determine where the lines defining the 'side' edges of the frustum intersect the map, push those points out a bit to make sure we get partially visible tiles/cells, and then borrow some 2D drawing routines to clip the resulting polygon to the map bounds, and 'scan convert' it. In out case the scan conversion will be storing the scanline extrema so we can quickly iterate over the tiles/cells of the poly later.

Finding the intersections

To start with, we assume the map is completely flat, determining the intersection of each line with our imaginary flat map, at the average map height, gives us a first guess. If the map is very flat, it will probably be quite good.

With a bit a variety in tile altitude obviously this can also be quite bad.

To fix this, we recast each line onto a plane at the height of the cell we got with our first guess, giving us a much better second guess.

Finding the visible cells

Once we have our points of intersection, we push them away from each other a bit to ensure we render partially visible tiles/objects/etc,

then we build a polygon and clip it to the map bounds. We then do our 'scan conversion', using a midpoint line algorithm which instead of writing pixels, records the 'extrema' (the min and max 'x' values) for each scanline.

and we have our 'visible poly',

Having recorded the span extremes for each scanline covered, we can now iterate quickly over the (potentially) visible area, SceneCuller provides an iterator class to do just this, they were designed to look and feel just like standard library iterators, separate iterators are provided for iterating over tiles or cells, using tile_begin() and tile_end() or cell_begin() and cell_end().

SceneCuller::iterator objects only support pre-incrementing.