# Changes between Version 1 and Version 2 of SceneCuller

Show
Ignore:
Timestamp:
12/20/09 15:10:15 (4 years ago)
Comment:

--

Unmodified
Removed
Modified
• ## SceneCuller

v1 v2
11= `class Game::SceneCuller` =
22
3 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.  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.
3The 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.
44
55The 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.

99To 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.
1010
11[[Image(flat_map.jpg)]]
1112
1213With a bit a variety in tile altitude obviously this can also be quite bad.
1314
15[[Image(max_slope_nocorrection.jpg)]]
16
1417To 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.
18
19[[Image(max_slope_withcorrection.jpg)]]
1520
1621== Finding the visible cells ==

1823Once we have our points of intersection, we push them away from each other a bit to ensure we render partially visible tiles/objects/etc,
1924
25[[Image(pushed_intersections.jpg)]]
26
2027then 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.
28
29[[Image(row_extrema.jpg)]]
30
31and we have our 'visible poly',
32
33[[Image(visible_poly.jpg)]]
2134
2235Having 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().