[SOLVED] Sprite Transformation Batching

[Laurent]

now you have a lot of problems coming from performing operations on a vector (vector grows -> it has a dramatic impact on performance, i.e. it needs to reallocate a new chunk  of memory big enough to hold the new data, then it must shift all the present items around, append the newly created ones in the end, etc).

A vector never clears its allocated memory (unless explicitly requested), so once you've reached the maximum size, all that your clear() and push_back() calls do is a simple copy.

[Glocke]

you store all object's vertices in a big vertex array on each iteration, wouldn't it be expensive?

I cannot store the vertex array for the next draw call, because the camera might move, which would force me to rebuild the vertex array, anyway.

if you draw them as a single vertex array, they must be the same, i.e. they hold same texture, is it so? otherwise there will be many "renderStates.texture = ..."  operations which has a big impact on the performance (swapping textures is not "free").

That's why I'm currently working with non-textures, just colored vertices (as mentioned some times before in this thread)

hmm, do you recreate the vector on each draw iteration or reuse the present one?

Reuse. But anyway, I changed this: No clean and no push_back are performed now, just operator[] for updateing.

[grok]

@Laurent , yes, I do agree.
I was discussing the scenario where one doesn't perform ".clean()' and just pushes the data over and over into a vector.
eventually it  will reach its maximum capacity and will need to perform reallocations.
if we do ".clean()", we might end up with having a large vector in memory with a few items for example, yet occupying a lot of memory. (now there's ".shrink_to_fit()" which might help).

[Glocke]

Well, anyway I'm going to implement a texture-based animation system. Hence I'll use sf::Sprite and seperate animation handling from the rendering system.
Assuming, the animation system handles changing frame animation's frames over time, it will set a dirty flag if the frame was changed. Finally, I want to decouple those systems (animation and rendering) so the animation system does not access the render system's component. Hence it does not know whether the render system is using sf::Sprite or another structure. If even doesn't know whether the render system is using OpenGL directly or not. Hence a dirty flag is necessary to make the render system detect that the animation frame has changed.

Also assuming that a sprite is always using one texture (else it would be a bit more complex, but that's not necessary to explain my idea, anyway) "forever". So updating and drawing (at the rendering system) might be the following (as pseudo-code):

Update: (per given view)

for each visible tile (depending on given view):
        for each object at this tile:
                if physics component has a set dirty flag:
                        calculate sprite's rendering position
                        apply position to sprite
                        reset dirty flag
                if animation component has a set dirty flag:
                        determine texture rectangle
                        apply rectangle to sprite
                        reset dirty flag

Drawing: (per given view)

create vertex array
create array of Sprite pointers
for each visible tile (depending on given view):
        add tile's vertices to vertex array
        for each object at this tile:
                add pointer to the object's sprite to the array
draw vertex array
for each sprite pointer in array:
        draw sprite

What do you think about that solution? Might it be worth implementing - or do you see possible issues / things that should be changed? Maybe both loops could be united, so the sprite update is done while collecting all visible sprites.

btw using sprite pointers while drawing might be necessary, because std::vector cannot contain lreferences.

btw2: both (vertex array and sprite array) might be resized before the loop by heuristical estimations to avoid multiple reallocations. So e.g. the vertex array could be resized to 4*(Number of visible Tiles) (if using sf::Quads), and the sprite array might be resized to 5*(Number of visible Tiles), assuming a tile is holding not more than 5 objects in most cases.

[Ztormi]

...snip...

You'll want as few loops as possible in your drawing methods. It also doesn't make much sense to me to rebuild the vertex array each frame. You can draw vertex arrays by giving the count of vertices you want to draw, starting from certain index. I'd personally just store the map in a single vertex array unless it's absolutely huge. Then I'd draw visible vertices row by row.

This way you can update texcoords and colors only when necessary, without rebuilding vertexarray.

In draw:

for each row of tiles in screen
  draw num_tiles_in_screen.x * 4 vertices
  from first_tile_in_screen.x * 4 + num_tiles_in_screen.x * row * 4 + (totaltiles.x - num_tiles_in_screen.x) * 4 * row
 

edit: remember to clamp num_tiles_in_screen

[grok]

...
for each object at this tile:
        add pointer to the object's sprite to the array
...
for each sprite pointer in array:
    draw sprite

how is it different from the classic way:

for each visible tile:
    draw tile
    for each object in tile:
        draw object
    end
end

?

Isn't it better to simply draw them "in the first place"?

and, as it has been already mentioned above, there's no need to rebuild the vertex array. if you know the index of the tile in the "global" vertex array, you can simply render just these 4 (speaking of tile) vertices directly as Ztormi explained.

moreover, if you know that "okay, I am iterating over the 4th row of tiles and there's a chunk of 10 tiles holding the same texture region" then you might even simplify the render: you might render all these 10 tiles in one go (again, utilizing the vertex array, and using the range [index_of_the_1st_tile's_vertex_in_array, index_of_the_10th_tiles_4th_vertex_in_array])!
for this example it might be, for instance, [5, 5+10*4], keeping in mind the tile consists of 4 vertices.

I'll try to clarify my approach in the pseudocode:

Code: [Select]

//1 = grass; 2 = dirt; 3 = water
tileMapVertexArray = [
1,2,1,1,1,1,1,2,2,2, //10 items
3,3,3,3,3,1,2,2,2,2  //10 items
...
]
here, if the first and second rows fall into the view area/screen region, you can draw them (if you still want to draw the tiles one by one)  using 7 draw operations only, not 20.

nevertheless I prefer just to draw the whole vertex array (where vertex array = your tile map's data).
if it is not tremendously big it is okay. otherwise I would partition it into the smaller chunks (also the vertex arrays) and draw some of them according to the visible region/screen.

hope that helps.

ps: why do you speak about objects as if they were tied to the tiles? what about this: draw the objects which are visible only.
you can get the visible ones using some math and their positions and it is not necessary needed to refer to the tiles to achieve that information.

[Glocke]

Isn't it better to simply draw them "in the first place"?

Drawing the entire floor at once is faster because all tiles share the same tileset texture. Also, drawing each floor tile alone means drawing tile, objects, tile, objects and so on. If the object of the previous tile overlaps with the current tile, the tile is drawn over the object, but the object should be drawn over all floor tiles - always. So you might argue: Render entire lines instead single cells. But an object might also overlap a tile from the next line.
So, culling first, drawing then seems more suitable

and, as it has been already mentioned above, there's no need to rebuild the vertex array. if you know the index of the tile in the "global" vertex array, you can simply render just these 4 (speaking of tile) vertices directly as Ztormi explained.

Well, rebuilding the vertex array for this view and having one draw call for the entire floor tiles isn't slower than drawing each tile on it's own. So I don't see a reason why to to multiple draw calls instead of one.

you can draw them (if you still want to draw the tiles one by one)  using 7 draw operations only, not 20.

Assuming all tiles share the same tileset, only one draw call is necessary.

/EDIT: That's all assuming orthogonal view. If isometric view (with wall tiles, which can overlap over objects), a modified approach is necessary:

• fetch entire floor; fetch walls and objects per line
• draw entire floor
• draw objects and walls per line

Else walls and objects do not overlap each other as they are used to from the camera's point of view. Traditional drawing ordern isn't working here.

[Silderan]

IMHO....

update time

move_player();
move_camera();
clear_viewable_list();
for each animated_object // Not just viewable or you'll loose IA on non-seen NPCs
{
    apply_position_up_to_physics();
    if( is_object_viewable )
    {
        add_to_viewable_list();
        update_textures_source_rect();
    }
}
if( camera_points_to_new_tile_position )
    update_tile_vertex_array_positions_and_textures_source_rect();
 

drawing time

draw_vertex_array(); // The tilemap.
for each object in viewable_list
  draw(object);
 

I don't see the needs for "dirty" flag thanks to viewable_list that avoids the re-loop entire animated objects again in drawing time.

Well, it's so simplified. For example, not sure how handle when player is behind a tile xD

[Glocke]

drawing time

draw_vertex_array(); // The tilemap.
for each object in viewable_list
  draw(object);
 

Well this works if no object or tile should overlap each other, because there's no render-specific order in viewable_list.

I don't see the needs for "dirty" flag thanks to viewable_list that avoids the re-loop entire animated objects again in drawing time.

Well, if you don't try to decouple systems of your game, you'll end up with heavy data dependencies. Dirty flags are one way to let decoupled systems work together.

[grok]

So you might argue: Render entire lines instead single cells. But an object might also overlap a tile from the next line.
So, culling first, drawing then seems more suitable

it is not a problem if you separate tiles draws and objects draws: draw all the visible tiles, then draw all the visible objects (as a result they will be drawn "upon" the tiles; achievement unlocked .

as for "heavy data dependencies". I am sorry, but you do have the heavy data dependencies already.

I still don't get:
1) why do you need to reposition/update all your game objects on each iteration. suppose there're tons of them.
2) why do you need to draw tiles and objects in one go.
3) why do you need to separate sprites data into sprite's data and its position/whatever, being pushed into the global vertex array
4) as for animations: why don't you update the sprites' texture regions during the update phase just in place (i.e. someEntity->updateTextureRegion()); in OOP approach I would put that in the "AnimatedEntity::update(float timeDelta)" method and Bob's your uncle)
5) why doesn't the classic render approach (has been mentioned a few times above) work for you.
6) did you perform any benchmarks which led you to the conclusion that the classic approach doesn't work for your requirements

[Ztormi]

Assuming all tiles share the same tileset, only one draw call is necessary.

You do realize that drawing with single call doesn't do anything to increase performance if you are iterating thousand+ elements every single frame?

Like grok said. You wouldn't probably notice any difference in performance if you are drawing them during the iteration, as opposed to adding them to empty vertex array each frame and drawing the array after that.

[Glocke]

why do you need to reposition/update all your game objects on each iteration. suppose there're tons of them.

As mentioned: I see a possibility why not to do so anymore. See above for details.

why do you need to draw tiles and objects in one go.

Because objects and tiles might overlap.

why doesn't the classic render approach (has been mentioned a few times above) work for you.

Overlap when stepping per tile, because an object might be located between two tiles, but is "linked" to one tile position at a time. I use this link for culling visible objects by using their "rough" tile pos.

why do you need to separate sprites data into sprite's data and its position, being pushed into the global vertex array

As mentioned: I was previously using non-textured Shapes and now I'm moving to textured Sprites. Meanwhile the vertex array is only used for tile vertices.

as for animations: why don't you update the sprites' texture regions during the update phase just in place (i.e. someSprite->updateTextureRegion()); in OOP approach I would put that in the "AnimatedSprite::update(float timeDelta)" method and Bob's your uncle)

Because I was neither using sprites nor textures, yet.

You do realize that drawing with single call doesn't do anything to increase performance if you are iterating thousand+ elements every single frame?

Do you realize that I stated, that multiple draw calls might effect rendering performance? Of course it has nothing to do with the speed of iterating lots of elements for updating.

Like grok said. You wouldn't probably notice any difference in performance if you are drawing them during the iteration, as opposed to adding them to empty vertex array each frame and drawing the array after that.

As mentioned: Directly drawing isn't possible because objects and tiles might overlap.

About that overlap: Assuming each object is located at one tile position at a time. And assuming each object can freely move between them. Consider x the be the tile, that tile position the object is attached to. See the attached image for details about the rendering bug, which is caused by the traditional approach.

Kind regards
Glocke

[grok]

if you have such bug, then something is wrong with your "draw tiles" algorithm.
suppose you have two layers: background and foreground.
do I need to convince you that if you draw the background and only after that you draw the foreground, the foreground will be completely visible? it even doesn't matter whether you work with the isometric scene or whatever. the foreground will be visible *always* if you don't draw something *after* you drawn the foreground.

you draw tile,then you draw the object(s), then you draw the next tile, then the object(s) on it, etc.
no wonder that you have such issue.
instead do the following:
draw all the tiles which are visible at the current moment, and only after that you draw all the visible objects,
then it will be correct.

[Glocke]

suppose you have two layers: background and foreground.

Yes but no. There is a background-layer which contains all floor tiles. The foreground layer contains wall tiles and objects, which might overlap each other.

Drawing the background isn't that problem... just use the vertex array. By the way it does matter whether precreated or not. On very large maps with many floor tiles, drawing a vertex array with tons of background/floor tiles might be slow. In this case recreating the background vertex array for a view floor tiles is faster.

But anyway, that's exactly the idea I tryied to state: draw floor at once, than draw objects (and wall tiles, but I didn't previously mentioned them) in render order.