Sign in to follow this  

Need scene graph advice, please!

This topic is 794 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am going through the process of rethinking my current game engine's design. And I'd like to ask about some information from other's experiences about scene graph. Before we begin, this graph is in no way shape or form going to be used directly for culling, however, it may possibly send data to the oct-tree system for culling. And it may filter the data before it's sent to the octree.

 

The game's construction is currently using something that might be a bit of an oddball set up. It's an entity component system, but Entities are only crafted in LUA. A few of it's components are just wrappers to the C++ framework.'

Which means that the scene graph does not see entities. It just sees transforms of arbitrary objects. The benefit is that not everything in the scene needs to be an entity. However... I have to currently throw away or modify the code as it uses a structure of arrays design.

Right now, the planed re-implementation of the scene graph will do a few things.

  1. Transform children's to their parent's fixed point.
  2. Act as a loader for Terrain Cells and Dungeons. Cell files will simply be a branch of the scene graph with tags for static, and persistent objects (Objects that can move). The benefit of this is I can just store objects as a local to that cell in it's file, rather than having to have some sort of transform that is world dependent.
  3. Supply the render system with a view-space coordinates (Camera is origin) rather than world coordinates. (I have no idea what DirectX's limitations are. But OpenGL is limited to 32bits last I checked. Float point accuracy becomes a major problem.)
  4. Party Characters can possibly be split up across a large world. Possibly only send the cells near the camera to the render engine.
  5. Entities skeletal system will be a scene graph managed by the entity it's self. But can be updated by the animation system. This is a pre-engineering design inspired by bitsquid. Unlikely to be used, but in case systems need to be reorganized, it helps.

Questions!

What should the scene graph actually handle in the world? Or would this be completely dependent on how I architect the system? From researching the ways a lot of big daddy engines handle things, everything that is a concept of matter is in the scene graph.

 

If I decide to use a cell based system, what owns things that can wander? Example... a player walks into some arbitrary cell (int16 X,int16 Y, in16 Z). When the scene graph calculates world coordinates, it translates into (float64 x, float64 y, float64 z). Should the previous cell surrender ownership to the player, NPC, persistent object, or otherwise to the next cell. Or should the world just own them?

 

And lastly, if you do recommend this system. Could you provide me an example to an SoA method of implementing such a graph using a world Cell coordinate? The problem with SOA, is it usually implies you have a fixed type for everything. Unless, I simply keep everything as transforms. Then add extra data as hints?

Share this post


Link to post
Share on other sites

why do you want to have a scene graph in the first place? most things in the world are not organized as a graph.

 

you'd have a way simpler life if all your objects were just in a vector. when you enter a 'cell' you load everything from it and add it to that vector and unload other cells. that way you won't have issues with ownership.

sometimes it is needed to attach objects to other objects, mostly for characters, but that's a special case and you can attach elements in the vector to those character instances, but otherwise the flat array might be everything you need.

 

most games use floats, doubles sound a little bit over the top. use a typedef to define your position type and keep it float for now, if you encounter at some point precision limits, you can still switch to double. but don't solve a problem now that doesn't really exist yet :)

 

just my 2cent ;)

Share this post


Link to post
Share on other sites

The reason for the scene graph is for several reasons :3. But first. The scene graph so far is technically an array. Though broken up. The highest depth of actual links is going to be about three in my planned redesign. World (There can be multiple worlds), Cells. Cells are Outdoor Cells, Dungeons, mega dungeons (Not really planned to implement this right now; basically a paged system for dungeons, can use 3D blocks)

One of the first, is the ability to attach objects,and allow them to transform with the parent object.

 

Second reason is the scenario of a worst case that can and will happen for the engine's design. Baulders Gate style camera with 8 characters in a near seamless world. Heck the camera might be able to go across the map. The world is large, you can say open world, but there are defined paths to take. Can't get from point A to B by riding up a mountain on a horse. The scene graph filters data submitted to the culling and rendering systems to geometry near the camera. Which... is basically just dump everything in the Cell arrays into the renderer, and let it sort that out.

 

Third reason. The Graph-array I have drafted makes it faster to look up item transforms from Lua. Cell IDs are 32bits. Which is actually Cell x and y coordinates, with a few bit flags. Object IDs are 64bits. It contains Cell ID, Object ID, and a few bit flags.Because parented objects can fall out of whack with children, I can't just rely on array position. So... we sort the Array pretty often.

 

Fourth reason... while you can probably get away with attaching objects directly to bones. You can't really do that without severe problems with vehicles.

Edited by Tangletail

Share this post


Link to post
Share on other sites

i do pretty much everything you listed in Cavaman 3.0, with no scene graph.

 

parents and children: objects with parent-child transforms are implemented as animated rigid body models. that way a model is just another object in the scene, and the drawing details are handled by the model drawing code.

 

cell/level loader: i generate terrain chunks in real-time in the background and on-demand (if needed) from underlying world map data stored in ram. it can just as easily be pre-generated and paged from disk. the terrain chunk cache system handles drawing and paging on demand. cavern (dungeon) levels are generated in real-time the first time the player enters, then paged from disk. caverns use a separate drawing engine for terrain. 

 

i use a camera_relative_coords() function to convert world to camera coords before drawing.

 

only visible terrain chunks are rendered. there can be as many as 50 PCs active at once in a game world 2500 miles across, and the human player can tab between them at any time.

 

i use both rigid body and skinned mesh models. each has its own drawing and skeletal update code.

 

things that wander: PCs are kept in a list. NPCs and animals (monsters) are kept in a second list. projectiles are kept in a third list. dropped objects and items that are immobile or too big to carry (huts, rafts, etc) are kept in a fourth list. only visible things are drawn.

 

attaching things: you can attach anything to any bone of a skinned mesh, or to any limb of a rigid body model.  a bone/limb is just a location, and a thing is just another object to draw. and no scene graph. just draw the attachment whenever you draw the model.

 

the rigid body system currently supports up to 20 limbs per model, allowing for up to 19 levels of parent-child relations per model, for things like "snakes and such" <g>. sort of a 20 element array version of your "scene graph", but a separate one for each rigid body model.

 

Caveman is a continuous (seamless) world. walk from one end to the other in real or accelerated time with no load screens. well, you have to build a raft to cross oceans....

 

you just keep paging chunks/cells as you go. and just draw whats nearby. i start with "is it within 2 map squares?" (at 5 miles per square).  if yes, its close enough for range calculations to not blow up. then i calculate range. if its still close enough, then i frustrum cull, if it passes cull, i convert to camera relative coords and draw_mesh, draw_rigid_body_model, or draw_skinned_mesh.  some objects are drawn as multiple calls to draw single meshes, as opposed to using a simple un-animated rigid body model.

 

re lua:  i'm pure c/c++, directx, and nothing else. if lua is a bottleneck, you should load the lua data into c++ before running. lua for ease, C for SPEED. and speed is god in games. there's a reason why the guts of high performance game engine code usually looks like C.

 

in caveman, you can get on a raft, paddle it across the ocean, walk about the deck while others paddle, and pickup and drop objects on the deck. and everything moves with the raft: you, your followers, your pets, and your dropped objects, the code may even exist already to move world objects too, such as a travois you drag aboard, or a tent you pitch on deck. all you do is track whats on the vehicle. then when you move the vehicle, you move everything aboard, like a parent-child thing. but again, no scene graph, just a list of vehicles, and variables for objects indicating they are aboard a vehicle, and which one. a list of who/whats on board for each vehicle is the other way to do it. more work to keep the list, but then you don't have to iterate though objects seeing if they are aboard and need to be moved. i found brute force iterating through objects to be plenty fast in my case. so i don't need "who/whats aboard" lists for each vehicle.

 

as you see, i use a number of smaller dedicated single-purpose systems working together to accomplish the tasks you describe.

 

also note the heavy use of lists for pretty much everything. lists seems to be the best first choice data structure for many things in games. only special cases need special things like oct-trees, "scene graphs" (IE rigid body stuff with parent-child transforms between meshes), etc. so in caveman, rigid body limbs and skinned mesh skeletons support parent-child "scene graph" type transform relations, but only those systems, because only they need them. simple lists suffice for everything else. even a rigid body model is just a list of limbs, where each limb has a "parent" variable: the index of its parent, or -1 for none.

 

 

these are the basic steps used to draw an outdoor scene in Caveman 3.0:

1. clear screen

2. set lights

3. set camera

4. draw sky

5. draw sun / moon

6. draw clouds

7. draw rain/snow effects

8. draw PCs, NPCs, and animals (monsters)

9. draw missiles

10. draw world objects

11. draw terrain chunks

12. draw player weapon (1st person view only)

13. draw user interface

 

culling is the same for PCs, NPCs, animals, missiles, and world objects: is it within 2 maps squares (so range calculations don't overflow)? is it within visual range? is it in the viewing frustum? ok, convert to cam coords and draw!

 

clouds just get a frustum cull. 

 

particles for rain and snow effects get a frustum cull.

 

calls are made to draw each visible terrain chunk. a terrain chunk is a list (yes another list!) of all objects in a 300x300 foot area: tress, plants rocks etc, as well as 4 interleaved ground meshes with different terrain tile textures. the ground meshes are always drawn, other objects in a terrain chunk (trees, plants, rocks, etc) get a frustum cull.

 

the sky, sun/moon, and player weapon in 1st person view are always drawn with no cull checks.

 

the sky is drawn with zbuf off.

 

clouds are drawn with both clip planes set very far. player weapon is drawn with both clip planes set very near. everything else is drawn with clip planes set to "normal" values.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

I am curious if you read what I wrote or not. It just seems like someone see's scene graph, and blows up. So... let me restate

The most my graph is...
World to N*Cells to 2*NodeLists, and no deeper. The node list is the array where the object transforms, and render information lives. For now anyways. Each Cell only points to two arrays. World keeps arrays of IDs. IDs of active cells. These are the cells that we check for rendering, we check first to see if an object's transform is located there, etc. IDs of passive arrays. Cells previously loaded, not yet released. We hold onto them in case we still need to edit, them, or if the player heads back to the area. The next time we autosave, their states are written to file, and deallocated.

 

Now, I'm sure your implementation will work for you. Your game is multiplayer, which implies that the server is unlikely to ever render anything. It can spend as much time needed to calculate. Not to mention memory constraints are less of a problem. Effects barely show up if it's ran on the same machine. Can't expect a client computer to handle 50 players while playing the game.

 

But, I don't think it will work for me.

I use custom dynamic arrays for all transforms (The array allocates batches, instead of one at a time. Reason for not using Vector). But I took care to make sure it's a Graph after running through a few tests and calculations.

 

For my set up, the big array in a linear search is faster if I am just looking for a few things.

The Divided array is faster if I am looking for a lot of things (Thanks to the ID algorithm)
That is in the best case. Parent items are always at the front.

 

Worst case (most common case) where we could have several items we are looking for. Data is constantly being sorted around. And they can be sometimes at the end of the arrays. Plus the entity we are looking for is not actually loaded, so we hotload from a save file for the location... the divided one came out on top.

 

Not to mention the problem of allocation for that giant array. Reallocating means that you must make a larger empty block, while the old block still exists. Kinda nasty with a 32bit system in mind.

 

Soo... yeah. I got the best of both worlds.

 

Lua is also not slowing me down at all. C is implementation, and the calculator of data. Lua calls to the scene graph for anything relating to transforms. And all Lua throws to it is the generated ID. Lua catches ID for newly spawned objects, and transform information for game logic.

 

I'd just like to know a few recommendations on how to handle a few things. Not "throw out my system because it's archaic", or it's object oriented.

Edited by Tangletail

Share this post


Link to post
Share on other sites

It just seems like someone see's scene graph, and blows up.

 

L Spiro says "every time someone says scene graph an angel loses its wings"  <g>

 

i personally have nothing against scene graphs.  but i have yet to make a game where i need parent-child info in a major way between almost everything in the game. skeletal animation with attached equipment, moving things aboard vehicles, and stuff like rotating turrets on targets are about it.

 

 

 

 


Your game is multiplayer

 

single player. like the sims, but with a family of up to 50 sims, in a continuous FPS/RPG type world (like skyrim, but procedurally generated) that's 2500 miles across.

 

 

 


which implies that the server is unlikely to ever render anything

 

15,000 non-instanced draw calls using just an onboard laptop graphic chip - no problems.

 

 

 


Not to mention memory constraints are less of a problem

 

700 meg working set!   : )

 

 

 


Can't expect a client computer to handle 50 players while playing the game

 

i'm currently testing a band of 21 PCs, and just hit 200+ active NPCs/animals at once in regular gameplay for the first time the other day. no problem.  and that's on a single core at 1.3Ghz clock speed.

 

 

 


I use custom dynamic arrays for all transforms (The array allocates batches, instead of one at a time. Reason for not using Vector).

 

by batches i assume you mean batches of elements, not one element at a time?    i personally implement lists as static arrays of structs sized "big enough" to get the job done, with an active variable for each struct. sort of a memory pool type data structure, and all allocated at startup in the data segment.  but implementation details are a matter of specific requirements and personal preference.

 

 

 

 


I'd just like to know a few recommendations. Not "throw out my system because it's archaic", or it's object oriented.

 

nothing archaic about it, just a different way to do things. perhaps scene graphs were once the rage and aren't now.  beats me, like i said, i never needed that amount of generalized parent-child capability in a game's list of renderables. i just use a renderables list and an indexed render queue, and handle parent-chlid stuff with rigid or skinned models, or the method for moving vehicles, or perhaps some custom code for a rotating turret on a battlestar.

 

object oriented is primarily a way of organizing code.  there's nothing wrong with OO.  all my code, while procedural and PODS, is organized into ADTs (abstract data types - a data structure and the methods that operate on it - a design methodology that was a precursor of OO)  which is more or less like OO code organization. an OO implementation would basically wrap the data structures and related procedures into objects using OO syntax. 

 

sounds like searching your list/graph/tree of renderables is the main issue. when i had similar issues i went with indexed lists (as in indexed database systems). when a renderable passes frustum cull and is passed on to the render queue, the render queue adds the drawing info for that renderable to the list of objects to be rendered this frame. at the same time, it does an in-order insertion into a multi-dimensional index system based on texture, mesh, etc. this eliminates sorting the render queue before rendering. to render you just iterate though the index. i used a similar multi-dimensional index system for determining which of 65,000 shelters need to be drawn each frame. you just use the index to get an instant list of whats in a given map square.  that kind of search sounds more like what you're dealing with. if so, index systems sure saved the day for me, both for drawing terrain in optimal draw order, and for determining possibly visible shelters in a reasonable amount of time. the index system was first developed for drawing terrain chunks, and worked so well i added it to the main render queue for the game. later i used it to solve the shelters issue. same basic concept as indexed vs non-indexed draw calls. and we all know how much faster indexed drawing can be.

 

i'd recommend looking at what you have from a data oriented point of view. that's how i came up with the index system. you know how it is, some parts of  a game like data to be organized a certain way, but other parts of the game may like it organized differently.  in caveman, terrain chunks are a list of renderables and an index. nice for graphics, not so nice for collision checks. so i generate both terrain chunks and matching collision maps. sure all the data could be stored in one or the other and derived as needed, but this is much faster. "Let the format of the data suit the task". and "Different tasks on the same data may call for multiple formats". sounds like you're already doing some of this "store same info two different ways (the regular way and whatever searches fastest) for faster searching" type of stuff. i'm sure you're already familiar with the basic rules for speeding up searches: use fast algos and structures, and search only what you must. traversing parent child lists is slower than just iterating through a list of renderables, so use frame hierarchies only where needed. indexing can be a great way to determine what needs to be searched when dealing with large lists, like 65,000 shelters out of which zero to perhaps 6 at most need to be drawn. also note that when i say "list" i mean so in the most generic terms, with no specific implementation method in mind. it may be AOS or SOA, an array, a vector, a tree, whatever.  whatever appropriate structure is used, its still some sort of "list of things".  i'd also recommend trying the Id software approach: "ok, the PC can't do this fast enough. what IS it good at doing fast? maybe we can use that."  they used this approach when developing some of the optimizations for the quake engine. i attended Abrash's lecture at the '96 CGDC.

 

break out the profiler and determine the biggest bottleneck. fix that. find the next bottleneck. fit it, and so on, what your system evolves into from all this is what its evolves into. you won't know the final form until you're finished modifying it. for me, i went from iterating though multiple lists of renderables to terrain chunks and index systems, and from a conventional ordered list render queue to an indexed render queue system, let data oriented design and the profiler guide you in the right direction for the optimal design for your case.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

Oh come now, Scene graphs aren't all that bad. As long as you don't use them for rendering :P. What if I wanted to make a giant Crab with artilary and goblins on it's back, and each Cannon Goblin runs it's own AI. Then when the crab dies, have the goblins hop off and try to run before the players kill it. Or a hydra snapping turtle. With each of it's heads actually being it's own entity instead of one AI. The head gets lobbed off, it acts like a snake. Or... put a Tower on the back  of a giant sea turtle, that is also a dungeon... and moving through the world. So players can move in it while the turtle moves!

 

Can't do that easily without some form of Entity Parent Child relationship. Yes, your physics engine can do it, but I learned through some profiling and experience that it's like peeling a grape with a sledge hammer when using Bullet Physics.

 

Plus you're also ruling out moving platforms and elevators which will be nice for a scene graph to handle instead of Physics. I remember Left 4 Dead, and several other games had problems with moving platforms.

Share this post


Link to post
Share on other sites
So, to clear the air, “scene graph” had a very different meaning (a very abstract and malleable meaning that changed almost on a per-person basis) long ago.
The old Wikipedia article literally used to read, “The definition of a scene graph is fuzzy because programmers who implement scene graphs in applications and in particular the games industry take the basic principles and adapt these to suit particular applications. This means there is no consensus as to what a scene graph should be.” https://en.wikipedia.org/w/index.php?title=Scene_graph&oldid=408856872

These were the times when I used to say, “Every time someone says ‘scene graph’ an angel loses its wings.”
Also the time when Tom Forsyth wrote that entry.

Unfortunately, because of the abstract meaning of “scene graph”, many people turned to OpenSceneGraph to understand what they are and what they do. Tom and I were mostly referring to the description of scene graphs on OpenSceneGraph’s site, which claimed that their graphs would help with rendering by sorting the scene for fastest material traversal, etc.
This is completely asinine and Tom’s article is completely correct in that context of scene graphs. Sorting the scene is for render-queues. Scene graphs are mainly a relative spatial-relationship structure intended to keep the sword in the fighter’s hand as it moves, or the characters in the seat of the car as they drive.

I try to be very clear on what a scene graph is and is not, and how to and how not to use them here: http://lspiroengine.com/?p=566
Almost 1 year later Wikipedia was updated to match what I wrote there, hopefully clarifying once and for all what a scene graph is.
I will proceed with the assumption that you have read my article.

 

however, it may possibly send data to the oct-tree system for culling.

The scene graph is unrelated to octrees. Spacial-relationship structures such as octrees only need to know an object’s world position and nothing more. The scene graph facilitates the computation of an object’s world position. There is no other relationship between them. Your system should be set up so that you have a linear array of objects and an octree with pointers to those objects. Then, when you add a scene graph, nothing else changes. You simply add a parent/child relationship between the objects and some “world matrix update” routines and you are done. Scene graph is fully implemented and done. Nothing changes in the existing relationship between objects and the octree, or scene manager, etc.
 

And it may filter the data before it's sent to the octree.

It mustn’t. This is not a job related to scene graphs.
 

Act as a loader for Terrain Cells and Dungeons. Cell files will simply be a branch of the scene graph with tags for static, and persistent objects (Objects that can move). The benefit of this is I can just store objects as a local to that cell in it's file, rather than having to have some sort of transform that is world dependent.

Why would this be the job of the scene graph? A scene graph is not a loader, it is a propagator. Use something else for loading.
 

Supply the render system with a view-space coordinates (Camera is origin) rather than world coordinates.

Absolutely not the job of the scene graph.
#1: Stick with world-view-projection matrices.
#2: Scene graphs do not supply anything. They propagate data and transforms down. These transforms may be used for rendering, but that is not the scene graph’s problem. They can also be used for physics or whatever. After the scene graph facilitates the creation of the world coordinates of an object, it sits back and lets the other systems use that data as they please. That’s their problem, not Mr. Graph’s.
 

Possibly only send the cells near the camera to the render engine.

This is a different task for a different system.
 

Entities skeletal system will be a scene graph managed by the entity it's self. But can be updated by the animation system. This is a pre-engineering design inspired by bitsquid. Unlikely to be used, but in case systems need to be reorganized, it helps.

It should all be a single scene graph for all objects and all sub-objects.
Almost all nodes in the graph will be root-level, meaning no parents. Most children will be skeletal nodes. Occasionally you will later have swords in hands, people in cars, give me a million dollars, etc.
 

What should the scene graph actually handle in the world?

Propagating data and transforms down from parents to children. Nothing else.
 

From researching the ways a lot of big daddy engines handle things, everything that is a concept of matter is in the scene graph.

Don’t get misguided by that. Again, almost every single object is a root node. A scene graph is only a tree in very few places. Otherwise it is extremely flat and is never the actual storage mechanism for the objects in your scene. Objects are stored and updated linearly in the scene manager.
 

If I decide to use a cell based system, what owns things that can wander? Example... a player walks into some arbitrary cell (int16 X,int16 Y, in16 Z). When the scene graph calculates world coordinates, it translates into (float64 x, float64 y, float64 z). Should the previous cell surrender ownership to the player, NPC, persistent object, or otherwise to the next cell. Or should the world just own them?

When an object moves its new position must be re-entered into the octree (or whatever system you use). This is a problem you have both before and after implementing a scene graph, and is unrelated to scene graphs.
Any time an object’s world position is changed, a dirty flag is set to indicate that it needs to be re-evaluated in the octree/cell system/whatever.  Updates to the world position made through the scene graph are no different, and again unrelated to this problem.

The reason for the scene graph is for several reasons :3. But first. The scene graph so far is technically an array. Though broken up. The highest depth of actual links is going to be about three in my planned redesign. World (There can be multiple worlds), Cells. Cells are Outdoor Cells, Dungeons, mega dungeons (Not really planned to implement this right now; basically a paged system for dungeons, can use 3D blocks)

This is over-engineering, and is a different kind of spatial management from scene graphs.

One of the first, is the ability to attach objects,and allow them to transform with the parent object.

This is also the final reason.

Second reason is the scenario of a worst case that can and will happen for the engine's design. Baulders Gate style camera with 8 characters in a near seamless world. Heck the camera might be able to go across the map. The world is large, you can say open world, but there are defined paths to take. Can't get from point A to B by riding up a mountain on a horse. The scene graph filters data submitted to the culling and rendering systems to geometry near the camera. Which... is basically just dump everything in the Cell arrays into the renderer, and let it sort that out.

Different tasks that belong to different systems. You might be mixing scene managers and scene graphs mentally.

Third reason. The Graph-array I have drafted makes it faster to look up item transforms from Lua. Cell IDs are 32bits. Which is actually Cell x and y coordinates, with a few bit flags. Object IDs are 64bits. It contains Cell ID, Object ID, and a few bit flags.Because parented objects can fall out of whack with children, I can't just rely on array position. So... we sort the Array pretty often.

I can’t speak to this. But sorting for rendering is done via a render-queue abstractly.

Fourth reason... while you can probably get away with attaching objects directly to bones. You can't really do that without severe problems with vehicles.

If your scene graph is implemented correctly, both bones and objects are “entities” and all entities use a parent/child system that allows any entity to connect to any other in exactly the same way.


L. Spiro

Share this post


Link to post
Share on other sites

So, to clear the air, “scene graph” had a very different meaning (a very abstract and malleable meaning that changed almost on a per-person basis) long ago.

This ^
You're talking about a transform hierarchy / attachment system / skeleton, not a scene graph :)

Follow the single responsibility principle. Making the transform graph responsible for loading terrain data is a violation of that principle :)

Entities can own nodes in the graph. Entities can write to the local transform (local-to-parent transform) member. The graph can then generate local-to-world, local-to-view, local-to-projected, etc members.

Keep it at that. Animation can supply local transforms too. The graph doesnt need to know where that data is coming from.
It also doesnt need to know how/why nodes are created and destroyed. Characters and terrain systems can both create nodes without the graph being aware of the details of those systems.

Share this post


Link to post
Share on other sites

Huh... I never thought that the scene graph was actually used for sorting. It just seemed stupid really. I guess I'll start calling it a transform hierarchy now. You hear that file! You're being renamed!

 

Now let me get this straight. A scene graph, is used for sorting for rendering. Not necessarily representing a scene and it's child components. Even though Maya, Blender, 3Ds  Max, gambryo nifs, etc... all call it a scene graph?

 

So... really my set up is a cross breed between a scene manager, and transform hierarchy array.

 

And Technically. The... world class is not fully responsible for loading in the world. It provides the inter-phase. Annnd... cells are just containers for world fragments. If it's a dungeon, one giant level, or one small level just depends on implementation. Cells hold transform for terrain, because I actually came across a happy little accident that placed terrain a few units over terrain.  Figured it might be worth while to make a bug a feature.

Edited by Tangletail

Share this post


Link to post
Share on other sites


Huh... I never thought that the scene graph was actually used for sorting. It just seemed stupid really. I guess I'll start calling it a transform hierarchy now. You hear that file! You're being renamed!

Now get yourself straight, a general scene "graph" would be putting a property onto every node member, do not nail this to transformations readapting. You can yield tree hierarchy  by an ability of a node to reference a single other node. I use this information for example for "owning", "taking", or any possible relation. Since this information must have space in every scene member, you must design it sparse. I actualy do not use this information for transformations at all, If there is a "transformer" of a node, I have it defined differently.

Share this post


Link to post
Share on other sites

Now let me get this straight. A scene graph, is used for sorting for rendering. Not necessarily representing a scene and it's child components. Even though Maya, Blender, 3Ds  Max, gambryo nifs, etc... all call it a scene graph?

This is why old-school "scene-graph renderers" have a bad name (and have poisoned thr term) -- they used the graph for logical organisation, traversal/sorting, material sharing, transform-hierarchy, and any other sort of parent->child data propagation. It did everything. There was one magic node hierarchy to solve every problem... Which results in a suboptimal solution for all of them :(

It's not a formal term, so any kind of parent->child scene-related structure often has the name applied to it... But due to the terrible "SOLVE ALL THE PROBLEMS!" scene-graphs of days past, I'd recommend avoiding the term and it's bad connotations.

Share this post


Link to post
Share on other sites

Alright... for a Scene "manager", would it be wise to let each cell manage their own list of persistant and dynamic entity transforms, material handles, and mesh handles for easier organization and serialization? Or would there be a better way? Given that this also means that the Cell needs to own the Camera's transform and the player's characters, as well as automated entities.

 

For context... mesh, material, and skeletal handles are only integers. The scene manager just dumps the information near the camera into the culling system, and lets it figure it out.

 

Personally... I don't like the idea of letting the Scene Manager hold all that information. But given Lua does not concern it's self with static objects in the world I really couldn't come up with better options other than...

A. Use two completely different structs. One for statics, and one for Entities. The problem that arises here is a sub optimal submit phase. Scene manager throws Static objects near the camera to the render's culling system. Then Lua explicitly dumps all that information.

 

B. Put Scene manager into Lua. Probably won't be that much of a performance loss for the scene manager, but I loose the ability to thread the scene manager. And it would probably be trickier to stream in data.

 

On the other side... it kinda makes sense to allow the scene manager to hold that information. Anything that is in the scene, is expected to render at some point. Logically, it wouldn't be too far to require anything with a transform to component, to also have a mesh and material.

 

... except for specialized volumes, unless it's for debugging reasons... but they could have a tag on it that tells the data dump to skip it.

Edited by Tangletail

Share this post


Link to post
Share on other sites

Now let me get this straight. A scene graph, is used for sorting for rendering.

Render-queues are used for sorting, several systems are used for rendering (gather, cull, sort, special prepare, etc.) which are high-level managed by the scene manager.

On the other side... it kinda makes sense to allow the scene manager to hold that information. Anything that is in the scene, is expected to render at some point. Logically, it wouldn't be too far to require anything with a transform to component, to also have a mesh and material.

There are plenty of reasons an object could exist in the world and not have a mesh or material. Lights, cameras, particle emitters, invisible walls/blocks, etc. The scene graph would allow you to put a flashlight into a character’s hand, and the flashlight mesh itself has a “spot-light node” which itself has no material (it is a light in the scene) but moves through the world with the player, accurately based on hand position. The scene graph/transform hierarchy has specifically that purpose.

For the rest, I have to just question your overall architecture. Why does Lua own the objects? Using Lua to manage logic is fine, but to use it for data storage, especially for data so critical to the workings of the machine, seems risky.
In an ECS system, non-compile-time customization comes from entities that have script components which update those entities. If your goal is simply to be able to fully customize entities without needing to recompile, that solution should work fine unless you have some other specific requirement you are not mentioning.


L. Spiro

Share this post


Link to post
Share on other sites

Lua owns only game centric objects and data (Health, ammo, etc).  Resources, materials, math etc is handled by C++ through light userdata. And Lua has functions and call backs respectively.

 

This engine is mostly a hobby project at a completely different approach, mostly inspired by the creators of Grimrock.

http://www.grimrock.net/2012/07/25/making-of-grimrock-rapid-programming/

 

The goal is to stuff as much of the engine as you can into Lua. With some low level systems being left inside C++. Rendering, Sound, Background loading, etc. Though, I didn't find the idea of letting Lua handle resources to be wise.  Nor handling math, as Lua has problems with small tables. So... obviously there was some deviation from that for custom memory handling, and sanity.

 

The idea seemed to actually be pretty interesting. The project isn't too large to handle. It's not building "The Unreal Engine". But if it's actually used for a project, there is the benefit that most of the programmers don't actually need to be competent with C++. And... Lua should easily allow you to implement the system you feel comfortable with, and it just works. It seems to be pretty modding friendly. And the benefit of live reloading, almost got it working correctly.

 

So technically, I don't have to use an ECS. I could just very well use an actor pattern, or your good ole object oriented design. That's controlled completely in Lua, but basic items such as meshes, materials, shaders... left out of Lua, and are only accessible through wrappers.

 

However... there are some pretty bad faults in my current design that I can already see.

Threading is open for only C++ objects right now. And sending data back would require registering tables to fixed points in the stack. I know it's possible to thread with lua, and Data has to return via callback from serialization. I'm a little skeptical about implementing it as it'd may require me to have more code in Lua. Though that might not be a valid point... as I recently learned you can have more threads than what the hardware can process.

 

Having too much code in C++ could hurt more than having more code in Lua. repeated pausing and calling C++ stacks takes a penalty at some point.

 

The scene manager, which I am asking about. While having it outside of Lua lets it be threaded right now, and it leaves a level of abstraction... it makes an absolute mess of things when serializing... or trying to render without having unnecessary data for everything. Never mind the fact that for loading up large worlds, You have two completely separate databases being loaded into memory for each terrain cell of 60x60m. The Lua one which holds game data, and it's transform tag. And then the C++ one which holds transform and rendering information.

 

Bone matrixes are being multiplied twice due to update order... than a second transform update is being forced to update the position of attached objects.

 

...List goes on. I might say screw it... and move more things into Lua, and let the engine be as malleable as a politics words.

Edited by Tangletail

Share this post


Link to post
Share on other sites

 

 

Unfortunately, because of the abstract meaning of “scene graph”, many people turned to OpenSceneGraph to understand what they are and what they do. Tom and I were mostly referring to the description of scene graphs on OpenSceneGraph’s site, which claimed that their graphs would help with rendering by sorting the scene for fastest material traversal, etc.
This is completely asinine and Tom’s article is completely correct in that context of scene graphs. 

 

For what it's worth, I've actually used OpenSceneGraph for a number of years at a previous job. It's true that the OSG libraries handle tasks such as asset file loading, culling, state-sorting, and rendering. However, it does not necessarily use the scene graph structure to complete these tasks. For instance, state sorting is performed on a linear list of drawables after the culling step. It is not performed by the scene graph itself. I have my complaints about OSG, but I don't think it can be blamed for the confusion about scene graphs on the basis that people are going to the website and making incorrect assumptions about how it's implemented.

Edited by CDProp

Share this post


Link to post
Share on other sites

This topic is 794 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

Sign in to follow this