Data Design for Scene Graphs Pt.II

Published December 21, 2014
Advertisement
Last time around, I described current data layout of my primary scene graph class - the Entity3D. After some thought and further research into what direction I want to take the engine, I decided to make a few changes. Let's start with the printout of the current layout - after my recent changes:[code=:0]2> class Entity3D size(288):2> +---2> 0 | m_pParent2> 4 | ?$basic_string@_WU?$char_traits@_W@std@@V?$allocator@_W@2@ m_Name2> 28 | Transform3D Transform2> 216 | ?$ControllerPack@VEntity3D@Glyph3@@ Controllers2> 232 | Renderable Visual2> 252 | ParameterContainer Parameters2> 268 | CompositeShape Shape2> 284 | m_pUserData2> +---
As compared to before, there is a huge reduction in size - from 396 bytes down to 288. Some of this was due to discovering some of my own incompetence (there was an extra unused matrix object in one of the objects that composed the Entity3D) and some due to actual design changes. I suppose this is a good advertisement for checking the resulting layout of your objects - to find extra matrices that don't need to be there!

The design changes show a general refactoring of the objects contents into separate classes. All of the scale, rotation, and position (and their matrices) have been refactored into a Transform3D object. The rendering related objects are now part of the Renderable class. The respective member functions have also been moved accordingly. This type of refactoring helps to consolidate the content, and it also makes it easier to include this same functionality in another class by simply including those new classes.

That leads to the other big change that I have made. Previously the Node3D class was a sub-class of Entity3D, which made both classes virtual (and hence used a vtable). This is less than optimal since it messes with the cache, it makes every single Entity3D and Node3D bigger than it really needs to be (by one pointer) and it doesn't really buy you very much in either functionality or savings. So I decided to split the inheritance hierarchy, and just make Entity3D and Node3D their own standalone classes.

The refactored objects I described above made it pretty easy to build a Node3D without inheriting its functionality. The only real hiccup was that the controller system had to be made template based, but that wasn't really an issue. Overall it was a pretty easy transition, and now the Node3D has a better defined purpose - to provide the links between objects in the scene graph. I'm pretty happy with the change so far...

In the end, there is some objects which were simply removed from the scene graph objects. This is primarily the bounding spheres, which will be relocated into the composite shapes object. That work is still under way, so I'm sure I'll write more about it once it is ready!
3 likes 5 comments

Comments

Washu

The composite shapes object should be, ideally, a pointer or index into a separate array entirely. Such object should have a handle back to this object, and this would allow you to trivially ensure that your culling data is trivially iterable in a cache friendly manner without carrying along a lot of other baggage that you don't care about.

Other things that might end up getting moved around, if you do refactor with that in mind, is the transform3d object, which will likely need to be included (or at least the position and rotation for calculating bounding boxes) in the composite shape object for culling purposes.

December 25, 2014 09:03 PM
Jason Z

Thanks for the suggestion about the shapes organization. A couple years ago when everyone was redesigning their entity systems for components, I was either unwilling or unable (due to time constraints) to the proper research myself. It has been a nice learning experience going through it now, so if there is any other ideas or strong suggestions I would appreciate them!

December 25, 2014 10:56 PM
Washu

I don't necessarily recommend the "entity component" system, as it's a stupid idea (I can elaborate more if you care too desire more about why it's a stupid idea).

But having separate component systems with their own data storage mechanisms which then have handles back to the owning object is a much more manageable system and significantly more extensible (your parent object can then be just a name and the pointer is a shared handle between the different systems, if you want).

A good presentation on the culling scheme I suggested above can be found here, the important take-away from it I've already mentioned above, however just as an additional thing: Hierarchical culling is generally slower than brute force, simply due to cache misses and branching. Unless you have a SIGNIFICANT (i.e. probably greater than around 40k) number of objects, in which case you should generally group them into large chunks which you can brute force process at once, rather than attempting to cull them using a tree or similarly non-cache friendly structure. I.e. If you have a dynamic world of a hundred thousand objects, you might simply break it up into squares of say 20,000 objects each, and then brute force cull those.

December 25, 2014 11:09 PM
Jason Z

I had a chance to go through the paper you linked to, and it was a nice read through. Most of the info coming out of the C++ community lately follows the same guidance - use a linear array of items to enable great cache usage and let the modern CPU pre-fetcher rip through the data.

I think I will follow your advice and come up with a separate 'system' that can house all of its data locally and just let the entity reference that object through a handle or pointer. If I make any significant progress I'll be sure to post it here!

December 27, 2014 12:42 AM
Washu

I had a chance to go through the paper you linked to, and it was a nice read through. Most of the info coming out of the C++ community lately follows the same guidance - use a linear array of items to enable great cache usage and let the modern CPU pre-fetcher rip through the data.

The advice has really always been that. Tree like structures are good in some areas, i.e. insertion heavy ones, where data-locality tends to be lost frequently anyways. However when your set of objects will not change significantly BETWEEN ITERATIONS (i.e. frame to frame) then you find that cache locality plays a much larger role in determining data-structures to be used. One of the things to keep in mind is that RAM speeds have been rapidly out matched by CPU speeds in the last 10 or so years. It's pretty much always been slower since the end of the SDRAM days, but difference has really only grown. So tree like structures are showing, much more, their ineffectiveness in certain areas (traversal heavy ones mainly) compared to brute force methods.

This is much like yee old terrain lod arguments, where in general it's just better to not LOD your terrain and simply throw chunks at the GPU, as it's far better equipped to handle tons of triangles than the CPU is at doing bulk LOD calculations and generating new vertex/index buffers for your terrain.
December 27, 2014 07:09 PM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Advertisement