[TESTERS WANTED] Speeding up rendering

[Psychedelic_hands]

I don't really have anything to add to this yet, but I'm extremely thankful Will that you're fully focused on this, aswell as the other devs.
I've always hated that I can run other (more intensive) games on max settings but not Glest  .
I'll try to help test later when I'm not busy.

[will]

Softcoder, i think we know the creating layers every time the camera moves is the best way now.  And we have very strong indications of the expected performance.

if you can tidy up and remove all dead code in renderer.cpp, it would help us navigate implementing it.

I am tempted to rewrite the iterator from first principles rather than trying to understand it.

If you can work out how to know if a tile's fow state, and expose it as a list of 0, 1 or 2 textures, we can implement the layer making code in those terms, and later we can support 0ad maps without changing the rendering strategy too much

[will]

Here's some prototype computing the viewable tiles code:

http://gamedev.stackexchange.com/questions/15489/scanline-filling-a-trapezoid/15510#15510

[silnarm]

For GAE I just store the X extrema (min & max x value) for each Y ('row') for an arbitrary convex polygon, this can then be used to quickly iterate and for an isVisible() function (very handy.)

http://sourceforge.net/apps/trac/glestae/wiki/SceneCuller

[will]

Oh the debris in renderer.cpp makes me blind!

I don't really dare submit my patch; it works well enough most of the time, and gives me a very nice speed boost on my Integrated Intel card.  But it has corner cases, literally:

(click to show/hide)

Code: [Select]

Index: source/glest_game/graphics/renderer.cpp
===================================================================
--- source/glest_game/graphics/renderer.cpp (revision 2493)
+++ source/glest_game/graphics/renderer.cpp (working copy)
@@ -714,40 +714,25 @@
  glTranslatef(-position.x, -position.y, -position.z);
 }
 
-static Vec2i _unprojectMap(const Vec2i& pt,const GLdouble* model,const GLdouble* projection,const GLint* viewport,const bool roundDown, const char* label=NULL) {
- Vec3d nearClipWorld,farClipWorld;
- gluUnProject(pt.x,viewport[3]-pt.y,0,model,projection,viewport,&nearClipWorld.x,&nearClipWorld.y,&nearClipWorld.z);
- gluUnProject(pt.x,viewport[3]-pt.y,1,model,projection,viewport,&farClipWorld.x,&farClipWorld.y,&farClipWorld.z);
+static Vec2i _unprojectMap(const Vec2i& pt,const GLdouble* model,const GLdouble* projection,const GLint* viewport,const char* label=NULL) {
+ Vec3d start,stop;
+ gluUnProject(pt.x,viewport[3]-pt.y,0,model,projection,viewport,&start.x,&start.y,&start.z);
+ gluUnProject(pt.x,viewport[3]-pt.y,1,model,projection,viewport,&stop.x,&stop.y,&stop.z);
  // junk values if you were looking parallel to the XZ plane; this shouldn't happen as the camera can't do this?
- const Vec3f start(nearClipWorld.x,nearClipWorld.y,nearClipWorld.z),
-             stop(farClipWorld.x,farClipWorld.y,farClipWorld.z),
-             plane(0,0,0),
-             norm(0,1,0),
-             u = stop-start,
-             w = start-plane;
-
- const float d = norm.x * u.x + norm.y * u.y + norm.z * u.z,
-             n = -(norm.x * w.x + norm.y * w.y + norm.z * w.z);
- const Vec3f i = start + u * (n / d);
-
- //printf("Will stuff: d = %f n = %f\n",d,n);
-
- Vec2i pos(i.x,i.z);
-//#ifdef USE_STREFLOP
-// if(roundDown == true) {
-// pos = Vec2i(streflop::floor(i.x),streflop::floor(i.z));
-// }
-// else {
-// pos = Vec2i(streflop::ceil(i.x),streflop::ceil(i.z));
-// }
-//#else
-// if(roundDown == true) {
-// pos = Vec2i(floor(i.x),streflop::floor(i.z));
-// }
-// else {
-// pos = Vec2i(ceil(i.x),streflop::ceil(i.z));
-// }
-//#endif
+ const Vec3d
+ norm(0,1,0),
+ u = stop-start,
+ w = start;
+ const double d = norm.y * u.y;
+#ifdef USE_STREFLOP
+ if(streflop::fabsf(d) < 0.0001) throw 0;
+#else
+ if(fabsf(d) < 0.0001) throw 1;
+#endif
+ const double nd = -(norm.x * w.x + norm.y * w.y + norm.z * w.z) / d;
+ if(nd < 0 || nd > 1) throw 1;
+ const Vec3d i = start + u * nd;
+ const Vec2i pos(i.x,i.z);
  if(false) { // print debug info
  if(label) printf("%s ",label);
  printf("%d,%d -> %f,%f,%f -> %f,%f,%f -> %f,%f,%f -> %d,%d\n",
@@ -761,42 +746,68 @@
 }
 
 void Renderer::computeVisibleQuad() {
- const GameCamera *gameCamera = game->getGameCamera();
- visibleQuad = gameCamera->computeVisibleQuad();
-
-// const bool debug = false;
-// if(debug) {
-// visibleQuad = gameCamera->computeVisibleQuad();
-// printf("Camera: %d,%d %d,%d %d,%d %d,%d hAng [%f] fov [%f]\n",
-//   visibleQuad.p[0].x,visibleQuad.p[0].y,
-//   visibleQuad.p[1].x,visibleQuad.p[1].y,
-//   visibleQuad.p[2].x,visibleQuad.p[2].y,
-//   visibleQuad.p[3].x,visibleQuad.p[3].y,
-//   gameCamera->getHAng(),
-//   gameCamera->getFov());
-// }
-// // compute the four corners using OpenGL
-// GLdouble model[16], projection[16];
-// GLint viewport[4];
-// glGetDoublev(GL_MODELVIEW_MATRIX,model);
-// glGetDoublev(GL_PROJECTION_MATRIX,projection);
-// glGetIntegerv(GL_VIEWPORT,viewport);
-// const Vec2i
-// tl = _unprojectMap(Vec2i(0,0),model,projection,viewport,true, "tl"),
-// tr = _unprojectMap(Vec2i(viewport[2],0),model,projection,viewport,false, "tr"),
-// br = _unprojectMap(Vec2i(viewport[2],viewport[3]),model,projection,viewport,false, "br"),
-// bl = _unprojectMap(Vec2i(0,viewport[3]),model,projection,viewport,true, "bl");
-// // set it as the frustum
-// visibleQuad = Quad2i(tl,bl,tr,br); // strange order
-// if(debug) {
-// printf("Will:   %d,%d %d,%d %d,%d %d,%d\n",
-//   visibleQuad.p[0].x,visibleQuad.p[0].y,
-//   visibleQuad.p[1].x,visibleQuad.p[1].y,
-//   visibleQuad.p[2].x,visibleQuad.p[2].y,
-//   visibleQuad.p[3].x,visibleQuad.p[3].y);
-// }
-
- //visibleQuad = gameCamera->computeVisibleQuad();
+ const bool debug = false;
+ if(debug) {
+ const GameCamera *gameCamera = game->getGameCamera();
+ visibleQuad = gameCamera->computeVisibleQuad();
+ printf("Camera: %d,%d %d,%d %d,%d %d,%d hAng [%f] fov [%f]\n",
+   visibleQuad.p[0].x,visibleQuad.p[0].y,
+   visibleQuad.p[1].x,visibleQuad.p[1].y,
+   visibleQuad.p[2].x,visibleQuad.p[2].y,
+   visibleQuad.p[3].x,visibleQuad.p[3].y,
+   gameCamera->getHAng(),
+   gameCamera->getFov());
+ }
+ try {
+ // compute the four corners using OpenGL
+ GLdouble model[16], projection[16];
+ GLint viewport[4];
+ glGetDoublev(GL_MODELVIEW_MATRIX,model);
+ glGetDoublev(GL_PROJECTION_MATRIX,projection);
+ glGetIntegerv(GL_VIEWPORT,viewport);
+ Vec2i
+ tl = _unprojectMap(Vec2i(0,0),model,projection,viewport,"tl"),
+ tr = _unprojectMap(Vec2i(viewport[2],0),model,projection,viewport,"tr"),
+ br = _unprojectMap(Vec2i(viewport[2],viewport[3]),model,projection,viewport,"br"),
+ bl = _unprojectMap(Vec2i(0,viewport[3]),model,projection,viewport,"bl");
+ // rotate it to be top-most first
+ Quad2i q(tl,tr,br,bl);
+ int start_y = q.p[0].y;
+ for(int i=1; i<4; i++)
+ start_y = std::min(start_y,q.p[i].y);
+ while(q.p[0].y != start_y) {
+ Vec2i tmp = q.p[0];
+ for(int i=0; i<3; i++)
+ q.p[i] = q.p[i+1];
+ q.p[3] = tmp;
+ }
+ // grow it slightly
+ const Vec2i centre = ((q.p[0]+q.p[3])/2 + (q.p[1]+q.p[2])/2) /2;
+ const int margin = 4;
+ for(int i=0; i<4; i++) {
+ q.p[i] += Vec2i(
+ q.p[i].x < centre.x? -margin: q.p[i].x == centre.x? 0: margin,
+ q.p[i].y < centre.y? -margin: q.p[i].y == centre.y? 0: margin
+ );
+ }
+ // and set it
+ visibleQuad = Quad2i(q.p[0],q.p[3],q.p[1],q.p[2]); // tl,bl,tr,br
+ if(debug) {
+ printf("Will:   %d,%d %d,%d %d,%d %d,%d\n",
+   visibleQuad.p[0].x,visibleQuad.p[0].y,
+   visibleQuad.p[1].x,visibleQuad.p[1].y,
+   visibleQuad.p[2].x,visibleQuad.p[2].y,
+   visibleQuad.p[3].x,visibleQuad.p[3].y);
+ }
+ } catch(int error) {
+ static bool noted = false;
+ if(!noted || debug) {
+ printf("Will: visibleQuad() error %d; reverting to historic camera code\n",error);
+ noted = true;
+ }
+ // fall back on old code
+ visibleQuad = game->getGameCamera()->computeVisibleQuad();
+ }
 }
 
 // =======================================
Index: source/glest_game/world/map.cpp
===================================================================
--- source/glest_game/world/map.cpp (revision 2493)
+++ source/glest_game/world/map.cpp (working copy)
@@ -13,6 +13,7 @@
 #include "map.h"
 
 #include <cassert>
+#include <algorithm>
 
 #include "tileset.h"
 #include "unit.h"
@@ -1481,35 +1482,52 @@
 // class PosQuadIterator
 // =====================================================
 
-PosQuadIterator::PosQuadIterator(const Map *map,const Quad2i &quad, int step) {
- this->map = map;
+PosQuadIterator::PosQuadIterator(const Map *map_,const Quad2i &quad, int step_):
+ map(map_), w(map_->getW()), h(map_->getH()), step(step_) {
+ // work out the y extent
+ int start_y = quad.p[0].y, stop_y = start_y;
+ for(int i=1; i<4; i++) {
+ start_y = std::min(start_y,quad.p[i].y);
+ stop_y = std::max(stop_y,quad.p[i].y);
+ }
+ // quad in is tl,bl,tr,br; reorder into clockwise perimeter
+ this->quad = Quad2i(quad.p[0],quad.p[2],quad.p[3],quad.p[1]);
+        // work out starting position
+        pos = Vec2i(0,std::max(0,start_y)-1);
+        // work out stopping positions
+        stop = Vec2i(0,std::min(h,stop_y+1));
+}
 
- this->quad= quad;
- this->boundingRect= quad.computeBoundingRect();
- this->step= step;
- pos= boundingRect.p[0];
- --pos.x;
- pos.x= (pos.x/step)*step;
- pos.y= (pos.y/step)*step;
- //map->clampPos(pos);
+int PosQuadIterator::_start_x() const {
+ // go down the left side
+ return std::max(0,_side(0,3));
 }
 
-bool PosQuadIterator::next() {
+int PosQuadIterator::_stop_x() const {
+ //go down the right side
+ return std::min(w,_side(3,0)+1);
+}
 
- do {
- pos.x += step;
- if(pos.x > boundingRect.p[1].x) {
- pos.x = (boundingRect.p[0].x / step) * step;
- pos.y += step;
- }
- if(pos.y > boundingRect.p[1].y) {
- return false;
- }
+int PosQuadIterator::_side(int start,int stop) const {
+ const int inc = start < stop? -1: 1;
+ while(quad.p[stop].y < pos.y) {
+ start = stop;
+ stop += inc;
+ }
+ const float f = (float)(pos.y - quad.p[start].y) / (float)(quad.p[stop].y - quad.p[start].y);
+ return (quad.p[start].x + (quad.p[stop].x - quad.p[start].x) * f);
+}
 
- //printf("pos [%s] boundingRect.p[0] [%s] boundingRect.p[1] [%s]\n",pos.getString().c_str(),boundingRect.p[0].getString().c_str(),boundingRect.p[1].getString().c_str());
+bool PosQuadIterator::next() {
+ pos.x += step;
+ while(pos.x >= stop.x) {
+ if(++pos.y >= stop.y)
+ return false; // reached the end
+ pos.x = _start_x();
+ stop.x = _stop_x();
  }
- while(!quad.isInside(pos));
-
+ assert(pos.x >= 0 && pos.x < w);
+ assert(pos.y >= 0 && pos.y < h);
  return true;
 }
 
Index: source/glest_game/world/map.h
===================================================================
--- source/glest_game/world/map.h (revision 2493)
+++ source/glest_game/world/map.h (working copy)
@@ -287,11 +287,14 @@
 
 class PosQuadIterator {
 private:
+ const Map* const map;
+ const int w, h, step;
  Quad2i quad;
- Rect2i boundingRect;
- Vec2i pos;
- int step;
- const Map *map;
+ Vec2i pos, stop;
+
+ int _start_x() const;
+ int _stop_x() const;
+ int _side(int start,int stop) const;
 
 public:
  PosQuadIterator(const Map *map,const Quad2i &quad, int step=1);

I think I've narrowed the problem down the centres of buildings being tested for visibility - which was fine when we were drawing a very wide skirt around the camera, but less fine when we clip it tightly - the centre may be not visible even though the building/unit is.

Also it doesn't like very very close up shots in free camera mode; but I'm more inclined to want to disable such near shots; I think RTSes should be played a bit further away anyway.


Just realised reason c patch has missing edges sometimes when ny patron didn't is that it is important not to truncate to ints too early.   Visiblequad should be doubles.

_{Edit by Omega: merged double post; fixed broken spoiler code}

[will]

Ok I don't think I've got the lust to fix this.

Making it so only the visible tiles are rendered is fairly straightforward if don't use the existing compute visible quad functionality in the camera, and instead unproject the four corners of the viewport.  With proper doubles throughout it draws correctly, and is roughly how I was doing it in glestng.

However, the engine relies on over-drawing in order to ensure it draws shadows for objects offscreen, and to compute the visibility of objects by their centre and such.

And I don't have lust to fix all that.  Sorry.

[Coldfusionstorm]

Hey, don't say say sorry, thanks for taking a go at it.

[Ishmaru]

Awww... I was looking forward to these fixes. Oh well things happen, thanks for trying!