[PATCH] Efficient model culling

[wraitii]

0 A.D. currently implements model culling inefficiently. Every Frame, we pass a "RenderSubmit" message around and components return what should be rendered based on a camera frustrum (point of view, if you will).

In particular any entity with a VisualActor component gets this. It's slow (lots of messages passed around). Furthermore the current frustrum checking uses aligned bounding boxes, which isn't very efficient.

A more efficient system would be to store entities in a separate components (ModelManager) that would hold a list to them, and iterate over all those. This would allow for cleverer implementation (such as quadtrees), and would reduce drastically the number of messages. Furthermore, other components could easily ask ModelManager if a given entity is invisible right now, and in such a case possibly not do some computations.
The downside is that it means storing entities in yet another component, and the current implementation suffers from the same "sparse vector" issue as CCmpRangeManager.

The code below is basically an SVN patch of Philip's "Culling" branch in the experimental git repo, with a few changes from me, mainly experimental and broken. I currently re-cull entities to render reflections, which fixes #579.
The code is very experimental and "proof of concept", but it's easily appliable on SVN which might trigger some feedback. Known issues (might be outdated with latest patch):
-when you jump from one point to another on the minimap, it sometimes takes 2/3 frames for entities to "pop".
-the water reflections look like they lag behind weirdly when you move the camera. No idea why -the minimap might be broken as CCmpVisionActor only checks visibility when an entity is not culled. I'm not sure if the minimap code uses CCmpVisionActor or calls the RangeManager directly.
-it's slower than it should be.

Implementing a fast culling would allow culling for the normal camera, the reflection camera and the shadow camera, fixing #579, #504, and improving performance.

The ModelRenderer might be extended to be a generic ModelHolder component, who the rangemanager and other components which currently store a list of entities might call. This needs some investigation.

[wraitii]

I'll add to this that this might be helpful for the renderer. If we have a clever structure that tells us which models are close together, it could help immensely with batching, as we could group models together, and batch their textures dynamically. I believe from semi-extensive testings in a OpenGL profiler that one of our big issues with the rendering is the number of draw calls, which is quite immense.

[wraitii]

Updated the patches: BoundingSphere contains only code related to bounding spheres, and ModelCulling code for the actual culling implementation. Note that this requires BoundingSphere. I've properly added all the files this time, and stripped it to a minimum (removing my changes from above). It should be a workable base for work on this.

I'm not 100% sure it compiles, I haven't tried (didn't want to update workspaces).

[philip]

In 15265:

New unit renderer.

Instead of each CCmpVisualActor rendering itself individually, collect all the units in a single CCmpUnitRenderer. This avoids the overhead of doing Interpolate/RenderSubmit calls every frame for every object in the world. It also allows more efficient culling.

CCmpUnitRenderer knows the positions of each object at the start and end of each turn, and computes the bounding sphere of the object along that path. That allows quick culling without recomputing the precise interpolated transform every frame. (In the future it could be improved much more.)

Clarify and clean up the sending of PositionChanged messages, and add new InterpolatedPositionChanged.

Remove the forceFloating parameter from GetInterpolatedTransform, since it doesn't fit the new design. Replace it with a (non-synchronised) flag in CCmpPosition.

Move construction progress from CCmpVisualActor to CCmpPosition, so that it consistently affects all position/transform computation.

Refs #2337.

[wraitii]

Actually fixed by Philip in r15265 and r15445