#### Archived

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

# Need some help with scenegraph/octree concept

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

## Recommended Posts

Hello, I am currently working on my final project for school. We are building our own engine and out attempting to produce a gta clone.I need some help understanding how a scenegraph and an octree work together. As i understand from several tutorials and what teacher have told me, is that a scene graph has groups inherted from nodes in which object with transformation of geometry is derived. The way i understand it each object is a node with children. What i am having trouble understanding is how the octree ties into all this. Can anyone point me to a tutorial on scenegraphcs other then the one at Gamedev.net. My main concern is that if each node is an actual object in the scene with bounds . How does the world geometry get put into the scene. Would the world have to be subdivided into nodes aswell? If so would each contain a pointer to objects in it or would the objects be seperate.

##### Share on other sites
Hum...
You''re correct on your definition and assumption on scene graphs. They create a heirachy of the world, based upon a certain criteria. Like, grouping objects together, based upon what light effects them. So each node would be a light, containing pointers to each of the objects it points too. Other than that, it''s not that difficult of a concept.

As far as tieing a scene graph / octree together, i''m not sure exactially what your asking. An octree divides up the world based upon a certain number of polygons / objects per node. If that node bounces over a poly_max, then it''s subdivided. So, to answer one of your questions, Yes, the world would have to be subdivided.

I think something that can answer your question is the following process?
Ie, load up the data into whatever ordering you choose. Mostly, I''ll load all the objects/brushes/lights/textures all into their own global list. Now, based upon the type of input you recieve, different objects will point to different items in other lists. Through that, you could render the world as you see fit.

After that, you can divide up your world via Octree. Now, once that''s done however, it becomes more effecient for you to render based upon the octree heirchy, than the scene graph that you loaded into. Mainly because it''s more effecient.

Now, once you divide things up into octree nodes, you COULD organize the data of that node into a seperate scene graph. However in my experience, tha''s quite a hassle/ overkill, as a light in one node, can effect polygons in another.

So basicly, I''d have to suggest dropping the idea of a scene graph (?) and just sticking to a Spacial subdivision algorithm like Octree.

hope that helpd.
~Main

==
Colt "MainRoach" McAnlis
Programmer

##### Share on other sites
Use scenegraphs only for transform hierarchies! Do not mess with lights/material/bla-bla things in the scenegraph! Only transform matrices. By the way that is doubtfull too, why one should need such a thing...
AFAIK geometry in single octree is transformed together, so it is only one node in a hypotethical scene graph... Of course if you want to store each octree node in ''local space'' and then create a real scene graph from the octree, but it is pointless, unless you have precision problems with the size of your world.

##### Share on other sites
I had an interesting discussion about that topic with JimH and ZenoGD a few months ago, some interesting ideas were tossed around. You might want to take a look at it (click)

##### Share on other sites
Octree is kinda scene graph (for objects that have position+size properties), but scene graph i far more abstract.

Yann L:
interesting thread, from which one should learn: SG are just useless used in classical fashion (having lights,materials,etc. inside them mixed). On 3d algorithms the result from similar discussion was that usually ppl use many SG-s, never single one. And those SG-s are so specialized for their respective purposes one would call them SG only for fun (nobody think about BSP as SG when writing it down ...
I worked with SG-s implemented in one popular engine, and it is usable, though it limits you in some ways and sometimes it is pure pain to keep things in their SG format.
Just one more: keeping terrain as a *single* SG node is just hillarious, sorry, can''t resist it
Those SG you guys talked about in that thread just fights for what to manage - BVs, HSRs and so on. It is hard to make one structure to handle that, and terrain isn''t one node nor in BV-way, nor in HSR...
Closing HSR&render behind interfaces for such different things like terrain (heighfield) and indoor is not very wise - terrain will need completely different (1d buffer?) HSR cache compared to indoor (SVBSP, MOBSP?).
One must just drop the idea of abstracting its game engine. It is about game, not the engine in the end!

duhroach:
Completely agree. All I can say that after some time working with OOP ppl I am totally bored with ideas of ''abstracting'', making general interfaces and the idea that this saves time!
Maybe it is just me...

##### Share on other sites
quote:

Octree is kinda scene graph (for objects that have position+size properties), but scene graph i far more abstract.

An octtree is not a scenegraph. It's a hierarchical clustering structure. I think, you don't understand what a scenegraph actually is. A purely abstract scenegraph does not even contain object positions and sizes.

quote:

Maybe it is just me...

Yes, I think it's just you. From years of experience in the domain, I can just say one thing: if you don't abstract your engine, it will backfire at you sooner or later. Esp. if you want to keep it manageable and expandable. But discussing abstraction is not the purpose of this thread. I just linked to the thread above, because it contained some ideas about merging scenegraphs and octtrees.

quote:

Those SG you guys talked about in that thread just fights for what to manage - BVs, HSRs and so on. It is hard to make one structure to handle that, and terrain isn't one node nor in BV-way, nor in HSR...

A pure scenegraph shoud *never* be used for HSR. If you do that, then there is something extremely wrong with your engine design. Representing a terrain as a single scenegraph node (containing eg. an octree or quadtree) is actually the optimal way, in terms of performance and hierarchical organisation.

[edited by - Yann L on December 18, 2002 3:57:00 PM]

##### Share on other sites
Yann L:
OT: Abstraction is good where necessary, abstracting HSR+BV+Collision in single structure is doubtfull. As I said - it is unclear how to find ''least common divisor'' for things like HSR/collision/render for in/outdoor, and BV as single-noded terrain is just useless...

>>A pure scenegraph shoud *never* be used for HSR. If you do that, then there is something extremely wrong with your engine design...

I never was, is or will use pure SG for anything! It is just too abstract...

Terrain - one node.
It is stupid to even debate that one, since I just do not get the idea of using SGs.
What I mean?
Setup one optimal CD for terrain and for indoor together and use it.
Setup one render hierarchy for terrain and indoor together and... yes, use it.
For terrain I subdivide it with octree, for indoor - with portalized graphs. There is no way a call for IObject->Render() will render anything, it will do HSR, will bach primitives, will sort things and there will be PostRender pass after all that. But to use that scheme without exploiting specific knowledge about underlying objects will tend to create one unified buffer they''ll comunicate - HSR cache maybe or something like that, and it''ll be abstract enough to handle their requirements and *that* I think is ill-designed in that system.
I clearly know how to cull my terrain. So with my indoor.
And knowing that I can design clear & robust system for them, without any abstractions.
Hope you understand me now.

##### Share on other sites
Hmm, no offense, but did you actually read the thread linked above ? Or have you just skimmed it ? Because judging by your comments, you have absolutely no idea what has been discussed in that thread (ie: all the points you brought up here, were answered in it)

Oh well, enough abstraction talk, back to the original topic.

##### Share on other sites
What offence - this is discussion forum, right?

##### Share on other sites
quote:

although skimmed some parts

See, that's the problem: Never attempt to discuss something, without having the entire picture

OK, let's get back to your points. That's pretty offtopic, so rebelcoder, if you think this talk messes up your thread, let me know and we'll stop it.

quote:

Setup one optimal CD for terrain and for indoor together and use it.

You can't get an optimal collision detection algorithm for both indoor and outdoor. Lots of people use different geometric representations for both.

quote:

Setup one render hierarchy for terrain and indoor together and... yes, use it.

Yes and no. If you have two distinct geometric representations, then setup an individual hierarchy for each one (eg. a heightfield has a different organisation as portal based trimeshes). Put both together into a scenegraph.

quote:

There is no way a call for IObject->Render() will render anything, it will do HSR, will bach primitives, will sort things and there will be PostRender pass after all that.

OK, I do the same. The ->Render() method was just an example, replace it by ->Process() if you want. But that was mentioned in the other thread...

quote:

But to use that scheme without exploiting specific knowledge about underlying objects will tend to create one unified buffer they'll comunicate - HSR cache maybe or something like that, and it'll be abstract enough to handle their requirements and *that* I think is ill-designed in that system.

quote:

And knowing that I can design clear & robust system for them, without any abstractions.

OK, I don't believe you You cannot code an engine without any abstractions. An object by itself is already an abstraction. It's just a question how far you want to go. And believe me, abstracting everything in such a way, that every possible entity in your 3D world can be represented in a common tree is a very useful feature.

Let's take an exmaple, why abstraction can be so useful: say you have a typical 3D engine. Now, you read about a cool new pixelshader effect. You want to implement it. This is what I do in my engine:

// I define a new shader type class, which is derived from the general abstracted shader baseclass:class CCoolNewShader : protected CShaderBase {   // define ctor and dtor for shader environment creation here    // (new shader class will be autoregistered by a private static instance)   // define a unique shader name here (eg. "CoolNewShader")   // overload virtual methods for render, init and update   // and define some private shader data};

Done. That's it. Now my engine knows the new shader, and can directly use it. No other modifications required. Not even an engine recompile, just a relink. That's the bliss of OOP abstraction. Now the example was for a shader, but it's the same principle for a hierarchical object. Eg, with an abstract system, I can include a fractal procedural object (something totally different to a normal mesh object) with a few lines of code, without needing any changes in the HSR/collision code.

[edited by - Yann L on December 18, 2002 4:50:10 PM]

• 10
• 15
• 12
• 9