Jump to content
  • Advertisement
Sign in to follow this  
John Stuart

Scene graph and Spatial Partitioning Confusion

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

After many months of work, I'm here again and will continue working again on scene managements.

IIRC, scene graphs are there to simplify the spacial relationship between objects. (If I move a car, the man inside the car will also move. )

Spatial partitioning on the other hand is the process of dividing space into smaller chunks so you can know which one is visible or not on the screen which will help performance.

Now my problem is, are these two have different data structures? I've read somewhere that there are engines that combined these two. Does combining the scene graph and spatial good?

I have a Octree right now that divides a terrain then draw only those visible nodes. Now, where should I put the movable objects I want to draw? Who manage them? Should I include it on the Octree? I'm really confused with the engine design. Hope someone enlighten me.

Thank you
John Stuart

Share this post


Link to post
Share on other sites
Advertisement
Actually, you might also need some other queries to make besides those, like occlusion culling, then you can have animation and so on. Putting everything in the same graph might work, but it can lead you into big trouble. By query I understand parsing the graph in a specific order for obtaining specific information.

The best approach is to first enumerate all your queries for the scene, then try to design a structure that accommodates them all. If you can't find a good design for it, don't push it, better make multiple structures, one for each individual query, and all of them referring the same data. A data structure that accommodates occlusion culling, frustum culling, forward animation (including skeleton) and so on might be very difficult to design.

I am sorry if I didn't answer your question directly but it really depends on your needs, and it is not something that is set in stone. If you find it suitable to place them in the same scene partitioning structure, go for it, if you find it more helpful to put them in a separate structure, go for that too. The only advice I can give you is to keep things simple, don't go for super structures that quickly become so cluttered that you experience difficulty in using them.

Share this post


Link to post
Share on other sites
Thank you meeshoo. What I'm thinking is this.

If I have a movable object somewhere on a certain space. I just connect it to the terrain node it is on right now. (hope you get it. lol).

But, I found this thread and saw this scene graph design.

Quote:
ROOT
|
|--- terrain node (geomipmapped quadtree)
|
|--- geometry of the village (static, octtree)
|
|--- Player (deformable skinned mesh)
| |
| |--- Torch (solid 3D object)
| |
| |--- Flame (volume renderer)
| | |
| | |--- Smoke (particle system)
| |
| |--- torch Lightsource
| |
| |--- torch shadow projector
|
|--- Big bad guy behind the player (skinned mesh)
|
|--- Big battle axe in the hand of the bad guy
|
|--- Dripping blood from the axe (particle system)


If understand it correctly, scene graphs are n-tree. And the Octree I made was just a node there. So in short, a scene graph is a manager for all the objects in the world? So all the queries are on that class? Hmmm... hope I hit the spot. lol

Thank you
John

Share this post


Link to post
Share on other sites
I have similar questions which don't really merit a separate thread so if you don't mind I'll tag onto this one. :) Hopefully they'll help you as well.

I'm also developing a scene graph, and I'm having problems with the coding side. I use a single graph for every query. Currently in each scene node I have a vector of pointers to all directly contained objects (apart from sub nodes). The vectors are of type SceneNode* so I can only access general functions belonging to the base class.

1) This becomes a problem when I try to integrate collision detection, as insignificant objects such as feathers or leaves (for example) have different behaviour on collision compared with characters, and terrain is different again. Do I hard-code the type of collision directly into the class when it's constructed, and call a different function depending on the type? This seems bad practice to me, but the only other solution is to hold a different vector of each type, which defeats the object of OOD.

2) The objects are all stored in the same vector, irrespective of whether they can move or not. This meas when I do collision I'll have to call the collision function on every pair of objects before determining whether they can actually possibly collide. To avoid this, is it a good idea to store moving and non-moving objects in separate vectors, and only do (nonmoving/moving) and (moving/moving) tests?

3) I'm using a heightmap for terrain. I've read that the best plan when it comes to terrain is to insert it into the scene graph like any other scene object, and divide it into chunks so that it fits neatly within each leaf node. However, doesn't this defeat the purpose of a heightmap, which is optimised so that all you have to do is pass in the position of the character and you'll get a height? Would there be any problems with keeping it whole and just storing it on the top level of the graph?

Share this post


Link to post
Share on other sites
I'm designing such a feature myself for my own engine now and I decided I will go for many data structures instead of one. Again, I don't think there is any rule or pattern to follow. I mean everybody speak about scene graphs and when you start developing your own engine you get this (wrong) idea that your engine MUST have a scene graph too somewhere. Well, this is not true.

@Sappharos

1) I think you should separate here the concepts. Collision detection is one, and collision response is another. Collision detection means you query objects to see if they collide, and the collision response may be a physical based one, or just some animation or a blend between the two. The collision detection is common to all objects. I think all objects capable of collision must implement a common collision response (behavior) interface and implement it as they see fit. Then somone will send them the collisions and call these response methods which will do what they must for each collider type.

2) I don't think array separation is needed, you can have a flag indicating an object is moving or not. Then if you are using some graph for collision, you can check if two objects are contained completely in different nodes, there is no need to check one against the other. The first optimization in collision detection is to avoid checking collision between objects that have no chance of colliding. Then you can check between the ones that could collide. You can have a completely separate graph here, used only for collision detection and nothing else.

3)Well, you can store it like that, but then, how would you implement frustum culling for example?

@John Stuart

No, a scene graph is not a manager, that is a resource manager. You have to make a difference between the actual object and a reference to it. A resource manager contains all objects (only once) and these objects are referenced in one ore more nodes of a scene graph. If you don't have a scene graph, you can still render your scene, but it will be unoptimized to send everything to the renderer, and also animations would be hard to track. That is why you can make structures that when you parse them in some way you can perform scene level operations like culling for objects that are not in the view frustum, occlusion culling, forward animation, collision checking etc. However, it is hard to find a single tree structure that will fit all these purposes, so it is a good idea to make as many graphs as you need, each of them with the functionality they need to perform their task well and clean. You could have a tree for animation, where each parent node's transformation applies also to it's leaves, you could have a tree for collision detection, one for culling, etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by meeshoo
1) I think you should separate here the concepts. Collision detection is one, and collision response is another. Collision detection means you query objects to see if they collide, and the collision response may be a physical based one, or just some animation or a blend between the two. The collision detection is common to all objects. I think all objects capable of collision must implement a common collision response (behavior) interface and implement it as they see fit. Then somone will send them the collisions and call these response methods which will do what they must for each collider type.


Thanks meeshoo, that's clarified things greatly. The way I'm planning it now, all objects provide a 'simple' collision test function in their interface, and if this is positive then the object's specific collision behaviour is invoked depending on an internal variable. Am I on the right track?

Share this post


Link to post
Share on other sites
How do you plan to detect collisions? Let's say you have a character model on one side and a tree model on the other side, how do you test the collision between them?

Share this post


Link to post
Share on other sites
Hi,

For the specific case of a character and tree there are several approaches but the most common one is to use some sort of bounding volume hierarchy (for both objects) in order to localize where they collide, assuming that they collide (if not, hopefully a cheaper test reveals that and skips the BVH stuff).

Now, that's not the only method of course.

Regarding the larger design issues - I really think that its important to decouple things such as collision detection and physics-based response from the scene graph. Yes, a good design will allow the game's specific code to hook into the process of the detection/response and do whatever it needs, but that's the general design IMO.

It would help make the scene graph simpler, allow you to create separate data structures and use algorithms solely intended to solve the collision problem, which makes it much easier and probably faster.

There is no real reason for that code to be a part of the general scene graph. If it can be decoupled from a design perspective, its a win. And yes, it can be decoupled, after all, every physics engine out there is basically an independent library.

Share this post


Link to post
Share on other sites
Quote:
Original post by meeshoo
How do you plan to detect collisions? Let's say you have a character model on one side and a tree model on the other side, how do you test the collision between them?


Well, I'm not sure now. It gets complicated fast. I had a few plans but then remembered I wanted to do a priori collision tests, which throws it all up in the air. This would mean:

1) Query the scene graph for the time of the first collision, or change of parent node.
2) Update all active nodes up to that point without processing any collisions.
3) Process the effects of the collision, including changes in parent node.

Repeat 1 to 3 until the end of the frame is reached.

To respond to collisions, at the moment my plan is to put a variable in the base SceneObject class which is set when the constructor is called, and determines what type of scene object it is. Then I'd use a series of 'if' statements, or nested 'switch' statements to determine which two types of object have collided. When a conditional is true, I tell each object what kind of collision to react to, as well as passing it the position/velocity data of its collision partner.

I have a gut feeling the system I just described is a really bad idea, or else it just makes no sense..! Here's a bit of incomplete code to illustrate it anyway.

void SceneObj::Collide (SceneObj *o)
{
if (type == CHARACTER && obj2->type == TREE_TRUNK)
{

{
if (type == CHARACTER && obj2->type == CHARACTER)
{

{
if (type == CHARACTER && obj2->type == LEAF)
{

{
}

Share this post


Link to post
Share on other sites
You're best off using different structures to handle different tasks. Octrees work well with view frustum culling and intersections between moving objects and the static scene. This is because you can generate the octree to be a near optimal fit with the geometry by increasing the node depth in more detailed areas.

For intersecting pairs of moving objects, it's not efficient to just rebuild the octree to handle dynamic changes in spatial locality. Instead you can use a sparse grid combined with bounding volume hierarchies. This method assumes that the density of intersecting objects is very low. If you had dozens or hundreds of objects bounding against each other, then resizing the octree on a per frame basis would be faster.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!