Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

transformation

which scene management technique to use?

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

Say I wanted to make an RPG. The game would have 3D "Towns" the town houses and markets and everything would have maybe 1-2 rooms. Very minimal. The towns could lead to wide open and forests. There will be a dungeon every now and then. The dungeons would be a mixture of outside/inside rendering. I wanted advice and opinions on what type of scene management scehems I should use while taking into account ease of detecting collisions and ease of inter object communication. Imagine a game with environments such as Final Fantasy X / Xenosaga, but with a little more freedom of movement. Also keep in mind that the scene management techinque would need to minimize the amount of "special" things the artists would hve to do with the level. And by special I mean things like marking areas as portal, and tagging areas as wall/floor/object, etc... It''d really be nice to get a discussion going on scene management systems for the above mentioned "type" of game. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Hmmm, I''d love to help but I''ve never played Final Fantasy X or Xenosaga so I have no idea what you are getting at...

But, anyway, you are very vague about what you mean by ''scene management'' It seems you are talkig about EVERYTHING in the game, so... That kinda depends on your engine and implementation doesn''t it?

Typically, you could have a list of objects and each object would be an entity in the game. Then each object could contain a reference to a ''scenenode'' in your rendering engine, a ''scenenode'' in your physics engine for collision detection, a reference to the scripting engine to handle scripted behavior, a list of child objects etc... The level would be an object in the case too.

Share this post


Link to post
Share on other sites
quote:
But, anyway, you are very vague about what you mean by ''scene management'' It seems you are talkig about EVERYTHING in the game, so... That kinda depends on your engine and implementation doesn''t it?


By scene management I mean a technique to divide the scene up that would allow for easy culling out of entire areas as well as give information on collision detection and where objects are relative to eachother.

I''d like the scene management technique to allow for as much diversity as possible and free up the artists as much as possible as well. Like portal rendering is technically for indoor scenes, while octrees can be used for hilly outdoor scenes and quadtrees for flat outdoor scenes, and then you''d need a bsp or an aabb tree to ease up collision detections as well. I figure there must be someway to handle all of these types of environment seamlessley as if they were the same.

Then we have the whole inter-object communication thig as well. But I suppose most of that boils down to collision and response anyways.

I hope that has made what Im looking for clear?

Share this post


Link to post
Share on other sites
if your towns are generally very flat (two floor buildings at most) you should probably look into using a quadtree

Share this post


Link to post
Share on other sites
You appear to be asking about spatial sorting (quad/oct/BSP trees) and not scene management (scengraphs), so I'll post an answer in that direction.

There's no one size fits-all, sorry. I know the Fly3D guys advocated (at least in their first book) using BSPs for everyting, including terrain. But that's not such a popular idea. The Cube engine takes the non-standard approach of rendering indoor scenes with a quad/octtree (can't recall which). What's really interesting about that project is that 1) they get great performance and 2) they are able to easily implement deformable indoor scenes, which you can't get with a static BSP. As BSP technique slowly dies, I think you'll see more engines using this approach (and I'm really not up to speed on the latest commercial tech, which may be doing things like this already).

Regardless of which technique or combination of techniques you use, there are bound to be tradeoffs (with regards to both features and hardware requirements). Also, you may find more benefit in thinking of your terrain and indoor environments separately. Even if you use the same technique to render both, each is a separate world entity. So rather than thinking of 5 dungeons as part of your terrain, think of one terrain scene node (in scengraph terms) and 5 indoor scene nodes.

And I forgot to add that I would go for the cube approach, and use a quad tree with geomipmapping for everything. If you intend to support lower spec machines, this may not be the best solution. In that case, perhaps combination Quad/Octtree ROAM terrain with BSP/PVS indoor scenes would be better. It's possible to transition smoothly between the two with the proper use of portals (which I know you want to avoid). That's old school stuff, but is more apt to give you better perormance on older hardware. But really, I like the Cube approach

[edited by - aldacron on May 8, 2004 7:08:38 AM]

Share this post


Link to post
Share on other sites
Ok, I''m tired, so if this doesn''t make any sense I apologise for wasting your time. It also might be wrong, so correct me nicely... Here goes.

My personal implementation would be to divide the world into a bunch of cells [assume I''m talking about outside here, my implementation for inside would probably be different]. The outside cells have a fixed single ground mesh. The artist places stock objects from a library onto this fixed ground mesh - or suspends them - I don''t care...

The graphics and physics systems use spherical bounding boxes on each of the objects to determine Object-Object, Object-World and Object-Pawn collisions.

I''d then have each of the systems I use consider only the 4 closest visible cells to the player. Then you worry about Player-Object and Object-Object collision through bounding spheres only. You don''t need to consider proper Player-World collision, because you assume that they can climb any type of ground. Then you calculate the slope of the ground and move them down in that direction according to their ability to climb... [note this means that you can''t have overhangs or walls as part of your actual ''ground mesh''...]

I''d tag objects and characters as either ''active'' or ''inactive''. When an object has stopped moving, you make it ''inactive'' and when it is moving, you make it ''active''. When an active object moves, you test it''s spherical bounding box against the world and all other objects. Once it lands on the world surface and does not slide [read slope comment earlier], you mark it as inactive. Then when any active object comes into the sphere of any other object, you have to worry about that collision only.

I would have cells which are regularly placed...
---------
|1|2|3|4|
---------
|5|6|7|8|
---------
rather than random cells
---------
|1 |2 |
---------
|3|4 |5|
---------

and then you have to worry only about the closest 4 cells. This assumes that your vision can only see a max of 1 cell''s height/width in distance.

When some character picks up an object, it would be moved from a list of contained objects to the character''s inventory, and then when they drop it, it would be added to whatever world cell they are currently in.

I think that this is sort of like the approach that Morrowind takes, but I''m not sure. I think that this implementation is actually quite slow depending on how smart your artists are though. Lots of closely spaced, tall yet not very wide objects which are moving are a recipe for disaster. But enough dwelling on the negative.

In more basic DirectXGraphics terms... I''d have a static vertex buffer for each cell''s ground [~1-3meg max]. Each cell''s ground would also have a dynamic index buffer. This index buffer would change whenever you change the ground shown, but I''d still throw the entire vertex buffer at the graphics card. Having the vertex buffer static means that you don''t waste too much AGP bandwidth changing it all the time? And TnL is quite cheap on modern cards anyways methinks. The index buffer means that only the visible triangles are rasterised [still expensive I think], even though all vertices are transformed. Of course, it goes without saying that all of the textures / shaders would be grouped, and rendered so that you have to change state only a few times. For this, I''d probably put in some sort of batching system, so that when multiple cells are actually drawn, the corresponding textures / shaders are matched...

I''d have a bunch of static vertex buffers, one for each object. By object, I mean things like houses, trees, pillows, weapons, plants, etc. These objects would exist in only one cell at any given time. When the player is carrying the object, it would be removed from the current cell, and placed on the player. When they drop it, it would be added to whatever cell it lands in. I figure that as long as your objects are relatively simple in their construction, you''re probably going to gain more speed simply by giving the graphics card the whole mesh and getting it to dump the bits it doesn''t need, rather than doing it in the CPU - which *IS* going to be much more expensive [I think].

Every second or so, I''d recalculate whether the 4 closest cells had changed. If they had, I''d run through a list of meshes that need loading for that cell. If they are already present, then that''s fine, but if they weren''t then I''d load / move from slow memory to fast memory. Then I''d run through the entire list of loaded meshes and find out what I don''t need, and either move that to slow memory, or delete it.

You''d suffer the same problem that morrowind suffers, not being able to set up ground that the player cannot attempt to climb [eg as walls], but you use objects for that. Thus, collisions are simpler, because you only need to test against object bounding spheres for NPC-World collision. You then test the slope of the ground, and see if the character can climb it. Objects are handled similarly, but on a per-face basis, with rejection of surfaces which are too steep to even consider.

Yeah, so I dunno if I''ve even answered your question, but that''s how I''d make that sort of rpg...

//end rant

CJM

Share this post


Link to post
Share on other sites
quote:
Also, you may find more benefit in thinking of your terrain and indoor environments separately. Even if you use the same technique to render both, each is a separate world entity. So rather than thinking of 5 dungeons as part of your terrain, think of one terrain scene node (in scengraph terms) and 5 indoor scene nodes.


If I understand you correctly, you are saying to make have the spatial partitioning structures within the scene graph nodes. So in essence, I''d have mode then one spatial partitioning structure around the place. One for the terrain, one for the dynamic objects (one for each kind??) once for semi-dynamic objects, one for any buildings that can be entered into, and etc... ?

quote:
And I forgot to add that I would go for the cube approach, and use a quad tree with geomipmapping for everything. If you intend to support lower spec machines, this may not be the best solution.


as well as indoor scenes? Or are you speaking stricly outdoor? You think it would be safe to say that in about 2.5 years (that''s the time my hit RPG will hit the interweb) I could just ignore todays "lower end" PCs?

CJM:

You definetly answered a lot of questions, but Im not sure exactly which ones It was a very informative post. IIt glimpsed over a lot of what has to be done. Could you please elaborate on how it would be done? Like which structures would you use to handle everything? One structure for all or different structures for different "objects"

Another thing that I got concerned with is how one would handle dynamic objects within these scene management techniques. I''d guess that any structure you used to keep your game objects in would need some major rebuilding every few minutes because dynamic objects could really intertwine the branches of any tree. Is this something I should be worried about or would the solution fit in naturally while handling the static objects?

thanks for replies so far.

Share this post


Link to post
Share on other sites
quote:
Original post by transformation
If I understand you correctly, you are saying to make have the spatial partitioning structures within the scene graph nodes. So in essence, I''d have mode then one spatial partitioning structure around the place. One for the terrain, one for the dynamic objects (one for each kind??) once for semi-dynamic objects, one for any buildings that can be entered into, and etc... ?



That''s not what I''m saying at all. Obviously you don''t need to do spatial sorting on individual objects such as trees, characters, etc... If it''s visible, you just render it. For the terrain and indoor *environments*, you need some mechanism to determine which parts of the enviroment are visible. You could use a single quadtree or an octtree for the whole world and render from it, but then you lock yourself into using that method exclusively. Switching to a different technique would require reworking large parts of engine. By keeping it at the node level (again, for enviroments and not objects) you can switch out different techniques to find the one that works best, or upgrade easily in the future.

quote:
Original post by transformation
quote:
And I forgot to add that I would go for the cube approach, and use a quad tree with geomipmapping for everything. If you intend to support lower spec machines, this may not be the best solution.


as well as indoor scenes? Or are you speaking stricly outdoor? You think it would be safe to say that in about 2.5 years (that''s the time my hit RPG will hit the interweb) I could just ignore todays "lower end" PCs?



I''m speaking of both indoor and outdoor scenes. And who knows what the market will look like in 2.5 years? If you are intending to sell the game as an indie, you will need to set your minimum system requirements before you start developing -- and they generally should not be the same specs EA will be targetting (if you want to reach the largest possible audience, but that''s your decision).

It seems to me that you need to get your head around the difference between managing and rendering the scene. The quadtree you use to render your terrain need not be the same data structure you use for collisions, or to determine object visibility. In FPS games it is common to use the same BSP tree to render the level and to determine collisions, but in terrain engines you might see separate structures for rendering, collision, and object visibility. THere''s more than one way to skin a cat.

Dropping the scengraph terminology for a moment, I''ll describe a simple approach. Store all world objects in a list. Each frame, iterate the list and determine which objects are in the current view frustum. Visible objects can then be sent to a render queue. Once that is done, render your enviroment using whatever technique you have decided (quadtree, BSP tree, etc..), then render all of the objects in the render queue. That''s a very basic system.

For small worlds, that should be sufficient. For larger worlds with many active objects, you could expand upon that idea and divide the world into zones. This can be done by using invisible polys to mark the zones, or by a quadtree or octree. Each frame, you find which zone the camera is in and only test objects in that zone for visibility (using the above technique). But again, this is *different* from actually rendering the environment. The data sructure you use here will likely not be the same you use to render the terrain/dungeon/whatever.

Collision is an entirely different matter altogether. Regardless of what type of collision system you use (bounding boxes, spheres, capsules...). you want to minimize the number of collision tests you do each frame. For effiecieny, your zone data structure could be used to determine which objects to test against (an object can''t collide with an object in another zone, of course), and that will limit the number of checks you make. Also, if you have several zones, you might implement a system that checks only a portion of the zones each frame. For instance, you might check for collisions in the active zone plus half of the remaining zones one frame and the active zone plus the other half of the zones next frame.

So you see, while it''s possible to share the same data structures for rendering, object visibility determination, and collision detection, they are three separate processes. Once you get your head around that things will become more clear. To break it down a bit, you might consider a system like this:

A. 1 quadtree or octree for object visibility determination and collision management

B. 1 quadtree or octree for each terrain "region" in your world (usually this will just be 1)

C. 1 quadtree or bsptree for each self contained indoor enviroment in your world (this doesn''t include small areas like houses, it''s pointless, but for a large mansion, a cave, a dungeon, you get the picture).

The data structure in A could be your scenegraph, or the scenegraph could be a separate data structure altogether. B and C would be nodes in the scenegraph, as those data structures would only be used in the rendering phase.

Share this post


Link to post
Share on other sites
I would use a scenegraph that is based on hierarchial structure. This can look like a spatial division but that shouldn''t be the base of the design.

Assuming your world is huge a 2D division could be made using the x and z coordinates.

So eg. you have a world map, that defines several regions with a bounding rectangle and filename of their map. Each submap can have regions like this too. A map can also include objects, static (buildings, trees and rocks) or dynamic (objects dropped by players, if you save those).

When you read in the map you build a quadtree using the bounding rectangle.

All wandering players and NPC''s are not stored in there, but in a separate list. This to prevent updating the tree all the time when NPC''s wander around town.

When you render you go into the tree, decide what to render. If a node is discarded you don''t have to go down into that branch. While doing this you build a render list of things to render.

Then you can sort the render list on texture/shader and start rendering.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!