Why is a Sprite Batcher faster?

I am reading Beginning Android Games (Mario Zechner) at the moment.

While reading about 2D games with OpenGL ES 1.0 the author introduces the concept of the SpriteBatcher that takes for each sprite it shall render the coordinates and an angle. The SpriteBatcher then calculates the final coordinates of the sprite rectangle and puts that into a single big buffer.

In the render method the SpriteBatcher sets the state for all the sprites once (texture, blending, vertex buffer, texture coordinates buffer). All sprites use the same texture but not the same texture coordinates.

The advantages of this behavior are:

• The rendering pipeline does not stall, since there are no state changes while rendering all the sprites.
• There are less OpenGL calls. (= less JNI overhead)

But I see a major disadvantage:

• For rotation the CPU has to calculate the sine and cosine and perform 16 multiplication for each sprite. As 开发者_如何学Cfar as I know calculating sine and cosine is very expensive and slow.

But the SpriteBatcher approach is lots faster than using lots of glRotate/glTranslate for rendering the sprites one by one.

Finally my questions:

• Why is it faster? Are OpenGL state changes really that expensive?
• The GPU is optimized for vector multiplications and rotations, while the CPU is not. Why doesn't that matter?
• Would one use a SpriteBatcher on a desktop with a dedicated GFX-card?
• Is there a point where the SpriteBatcher becomes inefficient?

But I see a major disadvantage:

• For rotation the CPU has to calculate the sine and cosine and perform 16 multiplication for each sprite. As far as I know calculating sine and cosine is very expensive and slow.

Actually sin and cos are quite fast, on modern architectures they take 1 clock cycle to execute, if the pipeline has not been stalled before. However if the each sprite is rotated individually and an ordinary frustum perspective projection is used, the author of this code doesn't know his linear algebra.

The whole task can be simplified a lot if one recalls, that the modelview matrix maps linear local/world coordinates map to eye space. The rotation is in the upper left 3×3 submatrix, the column forming the local base vectors. By taking the inverse of this submatrix you're given exactly those vectors you need as sprite base, to map planar into eye space. In case of only rotations (and scaling, maybe) applied, the inverse of the upper left 3×3 is the transpose; so by using the upper left 3×3 rows as the sprite base you get that effect without doing any trigonometry at all:

/* populates the currently bound VBO with sprite geometry */
void populate_sprites_VBO(std::vector<vec3> sprite_positions)
{
    GLfloat mv[16];
    GLfloat sprite_left[3];
    GLfloat sprite_up[3];

    glGetMatrixf(GL_MODELVIEW_MATRIX, mv);

    for(int i=0; i<3; i++) {
        sprite_left[i] = mv[i*4];
        sprite_up[i]   = mv[i*4 + 4];
    }

    std::vector<GLfloat> sprite_geom;
    for(std::vector<vec3>::iterator sprite=sprite_positions.begin(), end=sprite_positions.end();
        sprite != end;
        sprite++ ){
           sprite_geom.append(sprite->x + (-sprite_left[0] - sprite_up[0])*sprite->scale);
           sprite_geom.append(sprite->y + (-sprite_left[1] - sprite_up[1])*sprite->scale);
           sprite_geom.append(sprite->z + (-sprite_left[2] - sprite_up[2])*sprite->scale);

           sprite_geom.append(sprite->x + ( sprite_left[0] - sprite_up[0])*sprite->scale);
           sprite_geom.append(sprite->y + ( sprite_left[1] - sprite_up[1])*sprite->scale);
           sprite_geom.append(sprite->z + ( sprite_left[2] - sprite_up[2])*sprite->scale);


           sprite_geom.append(sprite->x + ( sprite_left[0] + sprite_up[0])*sprite->scale);
           sprite_geom.append(sprite->y + ( sprite_left[1] + sprite_up[1])*sprite->scale);
           sprite_geom.append(sprite->z + ( sprite_left[2] + sprite_up[2])*sprite->scale);


           sprite_geom.append(sprite->x + (-sprite_left[0] + sprite_up[0])*sprite->scale);
           sprite_geom.append(sprite->y + (-sprite_left[1] + sprite_up[1])*sprite->scale);
           sprite_geom.append(sprite->z + (-sprite_left[2] + sprite_up[2])*sprite->scale);
    }
    glBufferData(GL_ARRAY_BUFFER, 
                 sprite_positions.size() * sizeof(sprite_positions[0]), &sprite_positions[0], 
                 GL_DRAW_STREAM);
}    

If shaders are available, then instead of rebuilding the sprite data on CPU each frame, one could use the geometry shader or the vertex shader. A geometry shader would take a vector of position, scale, texture, etc. and emit the quads. Using a vertex shader you'd send a lot of [-1,1] quads, where each vertex would carry the center position of the sprite it belongs to as an additional vec3 attribute.

Finally my questions:

• Why is it faster? Are OpenGL state changes really that expensive?

Some state changes are extremely expensive, you'll try to avoid those, wherever possible. Switching textures is very expensive, switching shaders is mildly expensive.

• The GPU is optimized for vector multiplications and rotations, while the CPU is not. Why doesn't that matter?

This is not the difference between GPU and CPU. Where a GPU differs from a CPU is, that it performs the same sequence of operations on a huge chunk of records in parallel (each pixel of the framebuffer rendered to). A CPU on the other hand runs the program one record at a time.

But CPUs do vector operations just as well, if not even better than GPUs. Especially where precision matters CPUs are still preferred over GPUs. MMX, SSE and 3DNow! are vector math instruction sets.

• Would one use a SpriteBatcher on a desktop with a dedicated GFX-card?

Probably not in this form, since today one has geometry and vertex shaders available, liberating the CPU for other things. But more importantly this saves bandwidth between CPU and GPU. Bandwidth is the tighter bottleneck, processing power is not the number one problem these days (of course one never has enough processing power).

• Is there a point where the SpriteBatcher becomes inefficient?

Yes, namely the CPU → GPU transfer bottleneck. Today one uses geometry shaders and instancing to do this kind of thing, really fast.

I don't know about SpriteBatcher, but looking at the information you provided here are my thoughts:

• It is faster, because it uses less state changes and, what is more important, less draw calls. Mobile platforms have especially strict constraints on draw call number per frame.
• That doesn't matter because, probably, they are using CPU for rotations. I, personally, see no reason not to use GPU for that, which would be way faster and nullify bandwidth load.
• I guess it would still be a good optimization considering point 1.
• I can mind two extreme cases: when there are too few sprites or when the compound texture (containing all rotated sprites) grows too big (mobile devices have lower size limits).