Sign in to follow this  

Scene graph design..

This topic is 4597 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

Howdy everyone! I'm currently designing a rather complex project called M²E (Massive Multiplayer Engine). I've come to the point where I need a solid scene graph for M2E but am slightly stumped on how to proceed. The requirements are that it is expandable, good at handling enormous amounts of scene data and overall very fast. The current scene graph I've designed works great at this point, but I have a feeling it will show weakness when pushed to its limits. Therefore, I'm looking towards all the wizards on these forums for help in anyway possible (preferably just concepts and or suggestions) The current scene graph is more or less a "hack" to make the system functional - it currently stores all scene objects and processes them each frame. Although the unwritten rule of online games is to not trust the client, I've come to the point where I feel it will be necessary to let the client decide if it can bypass large quantities of scene data (thereby speeding up the processing step). I honestly don't see why a cheater would want to fake the scene data so it didn't render parts of the world because that would be separate from collision detection and therefore wouldn't beneficial. Again, any suggestions would be greatly appreciated! If anyone is interested in what M2E actually is, here is a small snippet from the technical spec document: ************************* M²E [officially named Massive Multiplayer Engine, herein M2E] was created because 12-42 Studios understands the time it takes to create a massive multiplayer game project. We’ve seen countless MMO game projects fail because they didn’t estimate how long it would take to create the entire graphics, networking, database and player handling code. Unlike other MMO development systems, M2E was originally designed for independent game studios and educational facilities who can not afford the huge budgets required to create projects of such undertaking. You should understand before proceeding any further that M2E does not alleviate all of the programming required for an MMO project. You’ll still have to program your game specific features, but you’ll not have to concern yourself with how these features are rendered or propagated over a distributed network. ************************* Regards, Nate Strandberg

Share this post


Link to post
Share on other sites
I think its hard for anyone to give any suggestions as your post was a little vague and without further specific information, perhaps if you described your scene graph in detail and say what exactly you want suggestions on.

What does your scene graph represent, some people use the term to mean the game object system which is what scene graph was never originally intended for. Its meant to efficiently tie all heterogeneous renderable and non-renderable objects in the scene, game objects would probably reference these.

A scene graph represents the semantical and spatial relationships among objects in the scene, generally arranged in a hierarchical format (a n-ary tree or directed acyclic graph (DAG)) and before anyone says anything yes scene graphs do contain spatial information however its not a spatial partitioning structure like BSP trees, quad/octrees etc but they typically are object partitioning structures as they are typically augmented bounding volume hierarchies (BVH).

@nstrg

That is what you probably want to do with your scene graph, Nary-tree or a restricted form of directed acyclic graph where only leaf nodes are shared, Then place bounding volumes (spheres are perfect here)in all node types that allows you to nest bounding volumes (the root bounds encapsulates the entire scene). This allows you to skip entire branches for certain operations turning it from linear time to logarithmic time complexity. Geometry (among other things) is exclusively referenced in leaf node types.

Once you have that it also represents a modellers hierarchy now to be more efficent you want to spatially index certain things like large static geometry with a spatial data structure, etc, etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by nstrg
I honestly don't see why a cheater would want to fake the scene data so it didn't render parts of the world because that would be separate from collision detection and therefore wouldn't beneficial.


Have you ever tried to look at enemies through a wall or maybe an entire building?
Because that could be a serious problem with that thought if you let players decide what to render :-D
Maybe you wouldn't be able to shoot enemies through buildings, but at least you would know when and where their heads will stick out from their cover ;-)

Share this post


Link to post
Share on other sites
Quote:


Have you ever tried to look at enemies through a wall or maybe an entire building?
Because that could be a serious problem with that thought if you let players decide what to render :-D
Maybe you wouldn't be able to shoot enemies through buildings, but at least you would know when and where their heads will stick out from their cover ;-)



That’s actually a very good point.. What I was considering was some type of "cell" system whereas each cell chunk would have its own root scene graph. Depending on where the active camera is, we could render that cell and any other visible ones instead of processing the entire world. A good example would be something very similar to an octree, wherein the world is split into sections and each one of these sections would have a scene graph associated with it.


Quote:


I think it’s hard for anyone to give any suggestions as your post was a little vague and without further specific information, perhaps if you described your scene graph in detail and say what exactly you want suggestions on.



In the current scene graph, child objects are stored in STL lists for lack of a better storage method. Each node has the ability to decide if it is visible in the current scene - if it isn't visible, none of its children are processed and rendering stops for that scene branch.

What I'd like suggestions on is the best approach for scene node storage (algos, etc), views of the scene method I described above (the cell method) and anything else people can come up with relating to scene graphs.

Quote:


What does your scene graph represent, some people use the term to mean the game object system which is what scene graph was never originally intended for. Its meant to efficiently tie all heterogeneous renderable and non-renderable objects in the scene, game objects would probably reference these.



The scene graph will represent all game objects and their controllers (animators). For example, the scene graph ties into the networking system whereas when a new distributed object is subscribed to, it is inserted into the scene graph in the correct position - does that make any sense?

Quote:


A scene graph represents the semantically and spatial relationships among objects in the scene, generally arranged in a hierarchical format (a n-ary tree or directed acyclic graph (DAG)) and before anyone says anything yes scene graphs do contain spatial information however its not a spatial partitioning structure like BSP trees, quad/octrees etc but they typically are object partitioning structures as they are typically augmented bounding volume hierarchies (BVH).

That is what you probably want to do with your scene graph, Nary-tree or a restricted form of directed acyclic graph where only leaf nodes are shared, Then place bounding volumes (spheres are perfect here)in all node types that allows you to nest bounding volumes (the root bounds encapsulates the entire scene). This allows you to skip entire branches for certain operations turning it from linear time to logarithmic time complexity. Geometry (among other things) is exclusively referenced in leaf node types.



Makes absolutely perfect sense! I've been trying to decide on the best object storage method and have considered options such as Red - Black trees, hashed binary trees, etc. As for DAG, I've always been told that is usually too complex and too much of a hassle to bother with - but I don't have any direct experience with them so what do I know? :)

@snk_kid - You seem to have a very strong understanding of scene graphs - which is quite impressive. If I were to post more information on M2E, would you be willing to listen and possibility consider a position as a freelance programmer? I assure you, this project is quite an undertaking, but we've already secured a number of business partners including Replica Systems (www.replicanet.com) and we're moving forward as quickly as possible.

Hope I answered all questions to this point. Substantial thanks go to snk_kid for the post - it got the gears moving again!


Regards,

Nate Strandberg
nstrg AT 1242studios . net

[Edited by - nstrg on May 16, 2005 10:32:58 AM]

Share this post


Link to post
Share on other sites

This topic is 4597 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