-
Hi, I'm currently using simple shapes (colored, without textures) as sprites. To speed up drawing I add all objects' vertices to a single vertex array while culling. So the actual drawing is pretty fast ;D
Unfortunately, I need to transform the vertices referring sprite's position and orientation, so I apply translate() and rotate() to the corresponding sf::Transformation and use transformPoint on each object's vertices. Because each object has individual transformations, I need to calculate those transformations per object. So I cannot use the transformation object/matrix as part of sf::RenderStates.
I'm using a dirty flag, yet, to determine whether a transformation needs to be recalculated. So the entire process runs smoothly in most cases. But if many transformations need to be done, it takes a lot more time.
Do you have any suggestions how to speed up those transformations? .. except multi-threading, I am trying to work single-threaded as long as possible to reduce unnecessary complexity ^^
Kind regards
Glocke
/EDIT: Some more details: Each sprites holds two sets of vertices: the original, untransformed and the currently transformed vertices. On each recalculation, the sf::Transformation object is created and applied to each vertices' position. The resulting vertices are stored as "currently transformed" vertices, which are used for drawing.
/EDIT 2: About the number of object... I'm currently testing with around 5k object, which runs smootly with clang's -O2 on my netbook (in contrast: in debug mode only up to 1.3-1.4k can be handled smoothly.. But using around 10k object is just another frame show ^^ Of course a netbook isn't fast but good to face performance problems early :) So I'm trying to get as much performance as I can ;D
-
Profile where your actual problem is and then try to optimize around that point.
-
For sure, it's an stupid question but... Do you need to perform transforms to such amount of objectes? Can't you appy the "dirty" flag to the non-seen objects and apply transform when needed... or the transform itselfs may move the object to/from camera view and you cannot avoid from applying transform to all?
-
For sure, it's an stupid question but... Do you need to perform transforms to such amount of objectes? Can't you appy the "dirty" flag to the non-seen objects and apply transform when needed... or the transform itselfs may move the object to/from camera view and you cannot avoid from applying transform to all?
To make the object move into camera view, it's position needs to be upated. Hence the transformation needs to be applied.
-
To make the object move into camera view, it's position needs to be upated. Hence the transformation needs to be applied.
Shouldn't this be a part of the physics calculations rather than the drawing calculations and therefore separated?
-
Shouldn't this be a part of the physics calculations rather than the drawing calculations and therefore separated?
Well, position inside the logical world and position on the screen isn't always the same. So for instance, an object's screen position at isometric maps depends on e.g. the tilesize. In my opinion, the physics system shouldn't know about the tilesize or the actual rendering perspective. So transforming a logical world position to a screen position is up to the graphics system.
-
As the other post.. maybe I will say another stupid thing... more seeing your amazing "Rage". But, objects positions, scaling and rotation is up to logic/physics, because graphics "just" interprets this. I think that's what Hapax post is saying, and I agree. Of course, this is a point of sight and doesn't changes your needs for improving transformations to increase FPS.
This is what comes to my mind. But, for sure, you'd considered and/or you won't gain many speed with it:
1. Refactor game logic to reduce the object transformation update needs (As you said, not possible)
2. Improve maths/code (practically useless because of modern compilers optimizations).
3. Reduce at all recursivity.
4. Reduce allocations (global or local -stack-)
5. Memory array (data[ i ]) much faster than linked lists. If you have some linked list (or tree) and you MUST have it, consider to create an array with the list/tree nodes for quicker iterations.
6. Multithread. With...
6.1 Lock entire objects transformations, so game logic must wait for it and code complexity is so low. Maybe, you won't gain many speed.
6.2 Make some kind of "transformations queue" without locks. More speedy but some frames may show objects deformed.
6.3 Locks at object transformation. You'll ensure to don't see any object deformed, but some object can be transformed and other one doesn't.
Sorry if it doesn't helps you or if my english is cryptic :P
BTW: Is this "problem" for Rage? Are you trying to animate all game NPCs?
Silderán.
-
But, objects positions, scaling and rotation is up to logic/physics, because graphics "just" interprets this.
Right! But position isn't just position. Considering e.g. diamon-shaped isometric maps, a position (1.3f, 7.2f) might be totally different compared with the object's screen position.
But anyway... whether moving the transformation of the points to physics or keep it at the graphics system doesn't reduce the complexity of the transformation at all :-\
5. Memory array (data[ i ]) much faster than linked lists. If you have some linked list (or tree) and you MUST have it, consider to create an array with the list/tree nodes for quicker iterations.
BTW: Is this "problem" for Rage? Are you trying to animate all game NPCs?
Yes and no. I'm reimplementing the entire code in a more DOD-way to achieve e.g. faster iteration of contigueos chunks of data. So yes, I'm currently not using any linked lists or trees holding the objects.
About the usage of these many transformations: I'm currently driving some kind of performance edge-case, assuming the following: Each of the 1.4k objects (debug mode without optimization, release mode can handle much more objects) is currently moving, so the transformation need to be updated. This might occur rarely in common game sessions, because having >1k enemies running around is quite insane. Non-moving objects (e.g. chests) won't cause that trouble, because of the dirty flag ;) I already tested this. Having 2k non-moving objects is quite smooth.
So... maybe it isn't such a problem for "Rage" - but it gained my attention, anyway ^^
Kind regards
-
But, a orthogonal to isometric view conversion is not a "transformation" that must be applied to all objects.
Up to view size and position, you must be able to know the tiles and objectes that must be shown in screen using orto to iso conversion. As I understand from your posts, you apply orto to iso conversion on all tiles and objects. That's a wrong aproach, IMHO.
Anyway, not sure if this is the problem. The main problem is the objects iteration, not the maths involved per object transformation apply... if 1K objects move... doesn't mathers if you just make two or four math operation... the problem is the 1000 object batch... and you cannot avoid it :P Well, yes, you can. I have some years of experience with a text MUD games where is quite normal having many objects. The solution is to keep living objects at minimum. I can tell you some tips if you want.
Silderán.
-
As I understand from your posts, you apply orto to iso conversion on all tiles and objects. That's a wrong aproach, IMHO.
Just to objects, but I don't know why this is wrong from your point of view. Yeah, physics should ... but physics don't know anything about the actual representation. The clue of decoupling systems is also to decouple and isolate domain-specific tasks.
The main problem is the objects iteration, not the maths involved per object transformation apply... if 1K objects move... doesn't mathers if you just make two or four math operation... the problem is the 1000 object batch... and you cannot avoid it :P
Well, without transformation everything runs smooth - also over those 1k objects. Each one is picked, each one's dirty flag is checked and then nothing is done (if transformations are disabled in code). And because no optimization is applied, the compiler won't optimize that in any way.
Yes, now the typical "profile your code and you'll see that you're wrong!"-posts might occur ::) But indeed, profiling with -pg gives me not a clue about the bottleneck. So anyway, messuring systems' elapsed time cannot be that bad at all ^^
By the way: the physics system is iterating over the same number of objects in the same way (contigueos array) but will less math... Guess how many time it is consuming xD
I have some years of experience with a text MUD games where is quite normal having many objects. The solution is to keep living objects at minimum. I can tell you some tips if you want.
Well, of course large object numbers might be common. But large numbers of moving objects is not - at least in roleplaying genre. Of course there might be lots of objects: chests, torched, enemys' corpses... but they are all not moving. They stay/lay where they are, do not rotate or everything else. Having lots of non-moving objects inside my system doesn't slow it down the way lots of moving objects do.
So I think the best way might be reducing the number of moving objects - as well as looking for optimization possibilities.
/EDIT: But, profiling gave me at least one clue: pushing back to a vector, which is already large enough to contain those additional objects, seems slow ??? (at least from the profiling output's point of view). Changing this helped a bit, but not quite much. ... Hey, but I've tried :D Iteration with matrix math is quite tough, anyway ^^
-
To make the object move into camera view, it's position needs to be upated. Hence the transformation needs to be applied.
yes, but it is not necessary to actually move all your objects? say, there's a big dungeon with hundreds of enemies moving, is it crucial for you to move all of them always? if you consider chunking the dungeon into the smaller parts and update the enemies in the current chunk only (where the player is located for example), will it hurt your gameplay? of course if you want all the enemies track the player (i.e. each second they're approaching towards the player location), then this approach might not work.
It is all about considerations, after all.
-
yes, but it is not necessary to actually move all your objects? say, there's a big dungeon with hundreds of enemies moving, is it crucial for you to move all of them always? if you consider chunking the dungeon into the smaller parts and update the enemies in the current chunk only (where the player is located for example), will it hurt your gameplay?
Well, anyway I'm using a grid as spatial datastructure, where each object associated with it's tile position. So updating transformations only for those objects might work - same for animation handling.
of course if you want all the enemies track the player (i.e. each second they're approaching towards the player location), then this approach might not work.
Well that isn't the problem. The actual AI is decoupled to an AI-System which handles all AI actions per frame. If the AI wants to move towards the player, the physics system is notified and performes the action. Especially it moves the object to another grid cell if necessary. This grid is just queryed by the graphics system. So this should work :)
Thanks, good idea!
-
Well, without transformation everything runs smooth - also over those 1k objects. Each one is picked, each one's dirty flag is checked and then nothing is done (if transformations are disabled in code). And because no optimization is applied, the compiler won't optimize that in any way.
I see... then, too hard to understand where is the bottleneck indeed. Seems that the problem is at transformation.
Just an idea, if it makes any sence for you, of course... you talk about rotation, position and scale. Did you tried to use sprite->setPosition and change animation textures instead of rotating objects? setPosition instead transformation may (shall) not make any change, but rotation... :P
-
Did you tried to use sprite->setPosition and change animation textures instead of rotating objects? setPosition instead transformation may (shall) not make any change, but rotation... :P
No, I'm pushing all object's vertices (as mentioned: only colored, not textured) to a huge vertex array while drawing. So I need to apply transformations per vertex before drawing.
Of course this won't work with animation textures ^^ When extending the code for animation, I'll use sprites again - as well as their setPosition() etc. :)
-
you store all object's vertices in a big vertex array on each iteration, wouldn't it be expensive?
i.e. I mean there's no need to draw all objects if there're only a few of them in the current view region/visible part of the game.
or am I missing something?
how many objects do you draw in average, 10, 100, 1000? 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").
anyway, I believe that
pushing all object's vertices (as mentioned: only colored, not textured) to a huge vertex array while drawing.
is not a good idea. it is unrelated to the draw purpose IMHO. 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).
hmm, do you recreate the vector on each draw iteration or reuse the present one?
have you tried to do "vector.reserve(...)"?
you might benchmark/measure/output that vector memory-related characteristics during the game and see what is going on with it internally. you might be interested in checking its ".size()" and ".capacity()".
-
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.
-
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.
-
@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).
-
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.
-
...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
-
...
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:
//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.
-
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.
-
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
-
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.
-
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
-
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.
-
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
-
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.
-
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.