Jump to content
  • Advertisement
KarimIO

Scene Graph Structure / Avoid useless calculations with Scene Graph

Recommended Posts

Posted (edited)

So I was debating whether or not to have a scene graph in my engine, because most people just use it for organization, rather than transformation, and I don't want to waste tons of matrix multiplications on things just when the level designer intended to organize their scene. My solution is to have multiple scene graphs, I was thinking of having one for organization and one for transformation. Does this make sense? If not, how do you handle scene graphs in your projects?


EDIT: Also, if you flatten some of the structure (ie: leaving the transformation for easy editing, but flatten prior to runtime), how do you decide what to flatten?

Edited by KarimIO

Share this post


Link to post
Share on other sites
Advertisement

You seem to be operating under a misapprehension of what a graph is, versus what a tree is. Relationships in one space (e.g. transformation heirarchy) does not need to have any relation whatsoever to another space (e.g. order and nesting shown in the GUI map editor; or inheritance of textures & shaders; or model used to render; or connection to the "sector/level" which an object was loaded with and should be unloaded with; etc).

A scene graph is a way of describing and defining the relationships between your objects, as a means of codifying and prescribing how you implement those relationships and objects... not merely a tree that happens to be notionally created by adding an `SceneObj *parent;` field to all your SceneObj's.

Share this post


Link to post
Share on other sites

@Wyrframe I know the difference between a scene and a graph, I just figured most scene graphs were actually scene trees (I've never seen on that's an actual graph - Unity, Unreal, I think Godot, all use trees). They almost always just act as a transformation hierarchy. Can you point me to any scene graphs in an engine that don't act as such so I can get what you mean?

Share this post


Link to post
Share on other sites

Graphs are hard to visually represent, but trees are easy. The UI doesn't make them easy to spot.

In Unreal's editor, you have access to a bunch of UI organization tools that are not part of the transformation heirarchy. Folders, Layers, Levels. With the exception of Folders, which are discarded at build time, you can iterate over those as easily as iterate over the transformation heirarchy. These are all parts of a graph which has nothing to do with transformation.

In UE4, at least, blueprints are composed of two varieties of components; those which are part of a transformation heirarchy, and those which are not. When you instantiate a blueprint, you're actually instantiating a statically-flattened version of that blueprint, all the way to the root blueprint inheritance nodes. If you have static meshes at several layers of the inheritance, for instance, and all set as Dynamic or Static, instead of Movable, they actually get baked into a single megamesh up to the nearest Movable point in the heirarchy (give or take batch size contraints).

All connections between objects are part of the scene graph; even when the editor doesn't provide a visualization for them. If in Unity or Unreal you set up a "Gang Boss" relationship between a bunch of mooks and their elite leader by assigning the leader object as the value of the myBoss field of the mooks, that's part of the scene graph, too. And either the engine or the mook's code will have to be able to handle the situation that the boss just got excised from the scene graph by a player's sword.

Share this post


Link to post
Share on other sites

@Wyrframe mentioned "set as dynamic", "set as static" etc. Since you probably can't deduce what nodes are translated/rotated/scaled at runtime, you should let the developer/level designer/artist/... decide what's just for organization and what will be adjusted at runtime. You might want to offer special "organizational nodes" that are simple containers with a name but without any special transformation logic to them. These could always be "flattened" out/ignored regarding transformation calculations.

Share this post


Link to post
Share on other sites
Posted (edited)

@Wyrframe By your definition, any graph is a scene graph, which seems technically true but I don't see how a "Gang-boss" relationship is general enough to refer to all objects in the scene, which is what I perceive as the definition.

I have implemented use of Folders and Levels, and will implement layers (or tags, or both), but I'm talking about hierarchy / graphs within a scene / level and don't think anything (except maybe layers) can be considered scene graph.

I do like the idea of using static / dynamic / movable to dictate the use, but there still might be cases where you don't want a static object to move with its parent, which was organized in that way simply for semantic reasons

@Sacaldur Interesting idea for the organizational nodes, might go with it. EDIT: But isn't that made redundant by the use of flattening static nodes?

Edited by KarimIO
Additional Question

Share this post


Link to post
Share on other sites
Posted (edited)

@KarimIO: what @Wyrframe was mentioning was 'your engine might add additional relations between the nodes based on the information in the user edited data'. A simple example would be assigning a certain Mesh to multiple "MeshRenderer" components (if you take Untiy as an example), thus these objects should be taken into consideration for batching while rendering this model -> additional relations -> no tree anymore. (This is just one example.)

Edited by Sacaldur

Share this post


Link to post
Share on other sites
Posted (edited)
8 hours ago, KarimIO said:

EDIT: But isn't that made redundant by the use of flattening static nodes?

What Sacaldur and I are trying to tell you is that an organization tree and a transformation heirarchy tree are orthogonal concepts, that their definitions have no interrelation. If you choose to implement it by mixing them as heterogenous types of node in a single tree, that's your choice, but you might find it easier or nicer or more reliable or more performant or... to have them instead be two (or more) separate systems.

 

8 hours ago, KarimIO said:

I do like the idea of using static / dynamic / movable to dictate the use, but there still might be cases where you don't want a static object to move with its parent, which was organized in that way simply for semantic reasons

I fear you've misunderstood. That 3-way field is an optimization declaration, used by the engine to discover the boundaries of where it can do mesh/material combining and physics baking and such. It's related to the transformation heirarchy, but it's not a way to opt out of it; it's a way to flatten it by declaring what objects cannot be moved at runtime (relative to their parent's coordinate space).

There is no way to prevent a transformation-heirarchy child from moving with its parent (assuming you have a working transformation heirarchy), although you can compensate for it by manually adding an inverse transform to that child whenever you add a positive transform to its ancestors. Mind the cumulative error term.

Again; organization parentage is not transformation parentage. You will get a lot of mileage out of not conflating or combining the two.

Edited by Wyrframe

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!