Scene Manager Design

Nov 12, 2007 at 10:00 AM
This is the Discussion thread for the issue: Scene Manager Design
Nov 12, 2007 at 11:04 AM
I think that you are mixing up the terms here, there is a lot more to a scene than terrain and drawables. There's also camera, audio, huds,etc.

I think what you are describing in the doc is a QuadTree structured terrain. But I really think we should consider making the terrain base agnostic to the type of terrain used. A terrain should have the possibility to determine by itself the type of algorithm it want to use. This would give a base implementation similar to:
    public interface ITerrain : IUpdateable, IDrawable, IDisposable
        public float GetHeight(Vector3 position);
        public Vector3 GetNormal(Vector3 position);
        public void Smooth(object degree); // I don't know what to pass here
        // How terrain name maps to an actual terrain data is determined
        // by the implementation of the current terrain type. It might 
        // be a file/resource name, it might be something different.
        public void Load(string terrainName);

Then ITerrain would still just be a node on the SceneGraph (Hence forward I'm refering to that as the SceneManager)
public class SceneManager   
    CameraCollection cameras;
    ITerrain terrain;  // Terrain spatial partitioned in any format Quad/BSP
    ScreenCollection screens;
    EntityCollection dynamics; // Sorted for optimum rendering
    EntityCollection statics; //Whatever sorting makes sense
    AudioCollection sounds;
The reason for this seperation is that though you can use patches in QuadTree and assign the entities to each patch there are other algorithms which do not have this facility.

Also when working with a moddelling tool (some time in the future) it makes much more sense to have a seperation, as this eases the developer experience. Internally the QuasTreeTerrin might be the one setting visible on the entities directly depending on the patches currently being drawn.

Of cause this is all base on the assumption that we would allow different types of terrain, if that's not so, and we only consider QuadTrees then I can see that merging the nodes makes much more sense.
Nov 12, 2007 at 3:09 PM
I understand that a scene manager has all of those things. I was just getting started with the terrain part.

Right now, in the template, gamemain is the closest thing to a scene manager we have. It includes lights, cameras, terrain, an entity manager, physics components, etc....

Nov 12, 2007 at 3:21 PM
I realize that more than just renderables are contained here. It doesn't even matter, its up to the entity itself to decide what it wants to do: render something, play a sound, injure the player, etc., and that's all contained in the Update/Draw methods of the entity.

So, to make sure I understand you right, you're proposing separate sorting for the static world geometry, the static entities, the moving entities, and the sounds that will play in the level, with little if any link between the world and the children entities?
Nov 12, 2007 at 3:31 PM
Yes, but you want to move all logic out of GameMain and into components, there is no reason for those using the framework to go and reimplement. Having a SceneManager is one step in that direction.
Nov 12, 2007 at 3:35 PM
Edited Nov 12, 2007 at 3:36 PM
Yes it's all seperated but there could easily be a link between the terrain and any entity, you def want to take advantage of QuadTree partioning, but you would have to call render on each root node individually, not from within the terrain. The advantage here is that this will work with almost any type of terrain mix. We do not rely on terrain to call update/draw on entities.
Nov 12, 2007 at 10:00 PM
Well we should understand that we will not have a quad-tree without a terrain unless we find another way to make it. Interiors would need to be done with BSPs or portals or something. It would also be a very difficult to set one up if we had a geometric terrain. The only quad-trees I've setup are dependent in many ways upon power-of-two values, and perfectly square polys and quad-tree sections. If you setup a geometric terrain then that disappears, unless you re-process the vertices of the model somehow. This is why I was hoping the culling and processing of entities was independent of the current terrain quad-tree.
Nov 12, 2007 at 11:51 PM
An simple implementation would simply be to use the cameras view frustrum and cull out everything not inside (or intersecting). The simply check if a the bounding sphere from the entity is inside the frustrum of the camera. Though this will Draw more entities than are visible since it uses spheres as bounding. But this makes testing very fast at max 4 tests are needed for each entity to determine if it's inside the frustrum or not distance(center sphere, side1/side2/side3/side4) > sphere radius, since all of these are point to plane checks they are "fast".

You wouldn't have to update all entities all the time either. Only if an entity changes position you would need to update that entity or the camera changes position/rotation you would need to update all entities visibility (asuming fixed infinite frustrum of the camera).

You can still do some binary/quad partitioning of the entities in order to improve performance and limit the frustrum size (infinite isn't very usefull).

I would guess that the terrain would simply get the visible patches and render those.
Nov 13, 2007 at 12:02 AM
I guess I'm outnumbered, so fine.
Nov 13, 2007 at 12:07 AM
The frustum for culling is simply the viewmatrix * projectionmatrix. This means we can cull out anything too far away, so we won't end up with an infiinite frustum.
Nov 13, 2007 at 4:53 AM
The problem I've had with culling entities is that bounding regions have relative positions, not absolute, and so a bounding region must literally be created every frame to be able to check it against the frustum.

For example, the spheres in the current demo have bounding spheres that match their size. However, if I check those bounding spheres against a frustum I get all entities culled out unless 0,0,0 is in view. This is because all of the bounding sphere centers are at 0,0,0 (relative positions). If I have 200 spheres I have to create 200 bounding spheres, 60 times per second with positions at the positions of the spheres. Then I can check the frustum against them.

I believe I will have to use a viewing cone, in which I can check a point in space against. This is much less accurate, especially with large models, but will cull out around 2/3rds of the worlds entities if they were spread out evenly, and will be much faster than frustum culling were even if we didn't have to re-create the bounding spheres each frame.
Nov 13, 2007 at 6:14 AM
You do not have to recreate the BoundingSphere, simply set the center equal to the entity position and you are set. In the future bounding information isn't really a concern as the PhysicsManager will contain all this information.

Not only is a cone less accurate, but isn't it much more expensive as you can't use plane to point calculations?
Nov 13, 2007 at 6:57 AM
Edited Nov 13, 2007 at 7:00 AM
There is a fairly simple method for sphere to cone checking, I believe it may be less than plane to cone, however I will have to see.

You can change the position of the bounding sphere if you give every Entity a bounding sphere variable. If you use the bounding sphere from model.meshes[0].boundingsphere then position is readonly.

The point/cone test is currently working more slightly more efficiently than the bounding frustum - bounding sphere test I was running. although I haven't put a whole lot of time into the test, so take it for what it is worth.

Testing a point is very little math

public bool Intersects( Vector3 TargetPosition )
            Vector3 tempVect = Vector3.Normalize(TargetPosition - this.Position);
            return Vector3.Dot(Forward, tempVect) >= Math.Cos(Theta);

where this.Position is the camera's position, and Forward is the camera's forward.

I would still need to do some changes for a sphere. Check this link out, equation still very simple, and doesn't require checks against 4-6 sides.
Nov 13, 2007 at 7:14 AM

shawmishrak wrote:
I realize that more than just renderables are contained here. It doesn't even matter, its up to the entity itself to decide what it wants to do: render something, play a sound, injure the player, etc., and that's all contained in the Update/Draw methods of the entity.

So, to make sure I understand you right, you're proposing separate sorting for the static world geometry, the static entities, the moving entities, and the sounds that will play in the level, with little if any link between the world and the children entities?

The only sorting I would separate is the terrain and anything connected directly to it, like billboards and earthbound scenery. Everything else should be culled for drawing according to some other scheme than the quad-tree I believe. As I've stated before, if we have something 500 meters above the terrain, the quad-tree will do no good to cull it. We need another way.

Didn't we talk about a parent/child node relationship, in which if you cull out a parent, all childred are culled as well? Similar to the parent/child quad-tree relationship.

Sounds would have to be different than view culling. You can still hear something that is out of sight, like something behind you. Sounds could probably be culled by a simple radius from the player or camera. This could be checked by the entity. When the entity wants to play a sound, it would have to check if the radius was within range (radius would be dependant upon intensity of the sound). If the radius was in range, the sound would play at a volume proportional to the distance from the camera/player. This way far away sounds would play quietly, and as they got further they'd fade to nearly no volume and eventually not play at all.

This is just some thoughts off the top of my head.
Nov 13, 2007 at 8:25 AM
I really need to refresh my math skills :)

Should the dot product not be less or equal in order to intersect?

Also since Theta doesn't change over time (Well usually) you could do:
public bool Intersects( Vector3 TargetPosition )
    Vector3 tempVect = Vector3.Normalize(TargetPosition - this.Position);
    return Vector3.Dot(this.Forward, tempVect) <= this.cosTheta;
Nov 13, 2007 at 4:09 PM
Edited Nov 13, 2007 at 4:09 PM
I believe that if something was directly in front of you, the dot product in the formula above would be 1. And the further to the left or right of your view an object is, the closer it reaches to 0. With a dot product, if the vectors are perpendicular then you get 0. This is why "greater than" works.

Yes, we could use this.cosTheta, and simply change the value only when FOV changes. Good idea.
Nov 13, 2007 at 8:35 PM
OK, I have to admit that I had to look it up, doing that I found this nice site which has some good informtion about geometrics
Nov 14, 2007 at 12:53 AM
Wow, good source for some of the difficult stuff. Hard to find really good information sometimes.
Dec 8, 2007 at 8:32 PM
I will lay out a very simple scene manager to get us started. I believe once it is layed out we should finalize at least a rough design so we can start to base the game off of it. Entity hierarchy, and interfaces will be connected to it, as well as the graphics system and possibly physics. Of course, all of those things I just listed may be controlled through interfaces, entity interface, graphics interface, physics interface. I'm not sure what we do and do not want as interfaces at this point. I should point out that when I say interface I do not mean the reserved keyword interface, I mean it in an OO sense.
Dec 8, 2007 at 8:53 PM
Edited Dec 8, 2007 at 10:48 PM
Are we going to want the ability to have multiple scenes? For example if you're leaving one area to enter another, you may want the skydome, weather, assets, and terrain to change. I would think having two scenes, and buffering the upcoming scene in would work. Once you're in a new scene you can buffer out an old one. With this ability the user could create many scenes, and the scene manager would take care of scene transistions.
Dec 8, 2007 at 10:56 PM
I'm not sure that having 2 scene graphs is a goos solution. It will allocate way too much data when transition from one scene to another. A better solution would be to have a streaming architecture which allows the map to be streamed and also other entities would be loaded/unloaded depending on certain conditions (such as distance).
Dec 8, 2007 at 11:42 PM
Well it depends on the size of a scene (memory wise). As a developer, you could make sure your scenes are small enough. Or, consider this.

SceneA = 250mb of memory.
SceneB = 50mb of memory.
SceneC = 50mb of memory.
SceneD = 250mb of memory.

You're in SceneA, using 250mb.
You enter SceneB from SceneA, you're now using 300mb.
You enter SceneC, you're now using 350mb. But you now unload SceneA, and you're down to 100mb of memory used.
You enter SceneD, you're now using 350mb. But you now unload SceneB, and you're down to 300mb of memory used.
We could also setup planes that when crossed will trigger loading or unloading of a scene to begin, this way you don't have to have 4 scenes to transistion like I demonstrated. This of course requires a level editor.

The other train of thought is yours, however we'd have to figure out equations to stream things in, or remove things based on distance. And what about weather and sky transistions, how would we determine when to transistion those?
Dec 9, 2007 at 12:17 AM
Streaming maps are certainlly possible, just look at WOW, and EVE.

The real issue isn't going for A to B but from D to A and then to Z which is 350mb, this get way to expensive to move all at the same time.
Dec 9, 2007 at 5:56 AM
What if we have 3 artists each creating their own "levels"/"scenes"/"zones", and they find they want to connect them together? Would this be possible with a single scene design? Or would it be easier with a multi-scene design? I really don't know, these are just questions that come to mind. I feel once we get a solid feel for how either system could be a solution then we can pick one.
Dec 9, 2007 at 8:10 AM
Maybe I didn't get teh question, but there is nothing in having only one SM that prevents multiple artists/levels/etc, I really doupt that WOW or EVE only have one artist.

Have a look at the racing or some of the other Xna templates, they only have one SM.
Dec 9, 2007 at 8:28 AM
Edited Dec 9, 2007 at 8:29 AM
I guess its 12 of 1, a dozen of another, or however that saying goes.

Let me put it discreetly and legally as possible. I know that specific things I'm saying work, and work very well, unfortunately I cannot use that knowledge towards things I'm working on in this engine....

That being said....

I can imagine that having each artist, from different physical areas in the world, work on their own separate scenes, and then one person could simply take the 3 scenes, plop them into the world, and create transisitions between them.

I'm not saying the way I describe is the only way, I can only say that I am 99% certain that it is one way that works well.

If you could give some details into how a single scene system could transistion things like a sky, and weather, and unload and buffer/load things dependant on distance, with a decent performance, I'm all ears. I'm certain open to either way, I just know nothing about the way you're describing.

I should add that I am fairly certain that WoW uses a multi-scene system.
Dec 9, 2007 at 12:00 PM
There are a number of issues you need to consider before moving into the multiple SM, as you need to determine what should happen with those object outside the current world space. Once a entity has been loaded should it just "die" when it get too far away?

But some things you can do is to would be:
  • Create a sorted list of the entities, sorted by position, or rather distance.
  • Every object which are farther away than sqrt(higth^2*width^2) would be removed
  • The world would be sections with the center being 0,0 then as you move around other sectors would be loaded, if your view distance is 300 units the next section should be loaded when you are about 300 + X away (X is used to make sure you can load the content before reacing 299 units away), the X value would increase for sections having many objects.
  • You will need to handle loading multiple sections at the same time, going diagonal would result in 3 section having to be loaded.
Dec 9, 2007 at 4:26 PM
You have planes that when crossed call a load/unload of a specific area.

To have a good transistion between two scenes you'd need at least 3 scenes.

SceneA, SceneB, SceneC

SceneA connects to SceneB which connects to SceneC.

You have a plane between each Scene.

While in a scene all adjacent scenes must be loaded as well. So while in SceneA, sceneB is also loaded. As you cross the plane over to sceneB, it tells sceneC to begin loading. As you cross the plane from sceneB over to sceneC you call the unloading of sceneA.

The requirements are that scenes that act as transistions between two main scenes should be smaller.
Dec 9, 2007 at 5:51 PM
Just realize that this is completely dependent on the kind of game being developed. This is only valid for games that require vast outdoor terrains, like Oblivion, Gothic 3, and many MMORPGs. Any game that is level-based and has discreet, separate maps will only ever have one scene manager.
Dec 9, 2007 at 7:14 PM
Well we should be able to run off only a single scene. Currently that is the case. Although currently what is put into the render queue, and the camera are both outside of the scene.