SceneGraphs are a relatively new concept in the GameDev world, and seem to have been adopted from those high-end 3D modelling tools which are based apon them.
In simple terms, a SceneGraph is just some kind of tree or hierarchy which contains all the objects that can be rendered in a Scene.
The implementations are as many and as varied as the people who write them, but in all cases are geared toward those characteristics deemed most important by their Author for a given application.
For example, a SceneGraph could be as simple as a list of stuff to draw... but when applied as the basis of a 3D Game Rendering Engine, we're mostly interested in Culling of stuff that is not currently visible, so we'd want some kind of space partitioning scheme (bsptree, octree, or something else), and we'd want to store our renderable objects in the nodes of that 'space tree'.

So far we haven't introduced anything 'new' in terms of data storage mechanisms - for games or otherwise. Let's fix that.

SceneGraphs are MORE than just a frame hierarchy representing a scene, because in a SceneGraph, we can have many 'SPECIAL NODES' which rather than (or in addition to) just 'storing stuff', can also 'DO stuff' (to any/all descendant nodes further down that branch of the tree).
Furthermore, Special Nodes can be used to associate arbitrary attributes of arbitrary Nodes, possibly via Script / Braced Formula.
This can be used to create any number of physical constraints which are automatically maintained by the Engine - this allows the game developer to describe complex interactive behaviours between the world's entities, and to otherwise fine-tune any in-game behaviours in a way that is external to the hard code of the engine - the developer can softwire the game without rebuilding the engine.
Posted on 2007-03-25 19:43:23 by Homer

I've begun to roll together several of the projects I've posted here previously : animated skinmeshes, octrees, frustum culling etc.
My goal is to produce a more useful demo from the components I've developed, and to develop them further but in a more global context.
It'll give me a chance to see them work together, and to address any issues that arise.
Posted on 2007-03-26 02:52:21 by Homer

My OctTree refuses to render.
I have just been investigating this. The problem turned out to be invalid INDICES.

When I generate an OctTree from a (potentially huge) X File, the geometry is distributed among N OctNodes.

Each OctNode is a container for 0 to N Faces.
Each Face is comprised of three Indices, which are 32bit during the Generation phase, but are renumbered to 16bits....

I collect the unique Vertices referenced by all the Faces in a given Node, and store them in that Node.
I'm MEANT to renumber the Indices to suit my new node-local VertexBuffer, replacing the 'global 32bit index' with a 'local 16bit index' but apparently I stuffed up there.
At first glance, the Index values which I loaded from my custom OctTree file seem incorrect.

I'll confirm this problem in the Octree Generator code later today, and probably fix it on the spot.

Posted on 2007-03-26 23:35:40 by Homer
The Octree Generator was writing junk index values to the output file, due to a trashed register.
I added a push and pop to protect that register, and I also added some code to detect illegal output indices (>65535)..

That problem solved, still my faces did not get rendered.
I checked the values of some Vertices, they seemed sane.
I stared at the render states.
I tried generating an octree from tiger.x instead of my own xfile, so that it for sure has a texture etc, and I changed the Generator settings to make a very shallow tree (forcing many original triangles to appear in the output).
Still no luck.
I created some simple democode for an indexed textured Cube, and that worked just fine.
I checked that I was setting material, texture, fvf, vertexstream, indexbuffer, etc, and I see nothing different.
What the heck is happening?
Next I will try to walk thru the faces in my own IB's, manually look up the three vertices for each face, and draw it using DrawPrimitive.
If that doesn't work, I'll try the demo fvf... I should see 'something', even if it's not correct :|

Posted on 2007-03-27 00:34:01 by Homer
Fortunately, the Tiger.x uses the exact same FVF as my demo cube, so I was able to fairly quickly get stuff rendering.

I'm now able to render all the faces distributed in the (mostly leaf) nodes of my OctTree, although I'm not currently applying Culling, and I haven't tested it on UNTEXTURED materials since I just got it working.

I'll now confirm that untextured materials are working by reverting to my homemade xfile, and once that's done, I'll import my Frustum code for culling the OctTree nodes in realtime via the View Matrix (current camera view), and implement it within the OctTree rendering code.

It's worth mentioning that my OctTreeGenerator currently does not calculate Vertex Normals for any 'new' Vertices generated during the partitioning process. I'll worry about that when I have Lighting.

Posted on 2007-03-27 02:18:05 by Homer
You're going to have to play around with the LEAF_OCTANT_FACE_LIMIT constant when generating your octrees.
Example results from Tiger.x :

Limit=300, outputfile = 20kb
Limit=150, outputfile = 970kb

Dramatic difference?
Posted on 2007-03-27 03:45:40 by Homer
How is that difference possible :| ?
Posted on 2007-03-27 06:57:52 by Ultrano
The answer lies in the way the subdivision of faces is performed.
My octree generator finds the centroid of the imported xfile, and uses three virtual planes passing through that centroid to cut the model into 8 subsets. It then repeats this process for each subset, until some threshhold is reached, thus building the spacetree.
Whenever a plane passes through a triangular face, that triangle is cut into either 2 or 3 pieces, and those pieces are then fed back into the equation and tested against other planes,thus several planes may cut the same triangle, generating even more output triangles from the single input triangle.
My generator suppresses any splitting operations which would create unreasonable output 'fragments', which helps a little, but the triangle count can still be quite high.

Two factors affect the output facecount in my generator, one we can control, and one we cannot control.
The factor we can control is the 'maximum faces per leafnode' threshold which is used to terminate the recursion during tree-building when the working facecount is sufficiently low.
The factor we cannot control is the geometry of the model, which directly affects the number of triangles that are cut by a virtual plane or planes.
The reason that the 'maximum faces per leafnode' threshold affects the output facecount is not immediately obvious... think of it this way: the octants get smaller as the tree gets deeper, and smaller octants means less distance between the axial position of the cuttingplanes, thus as we go down the tree, more triangles are going to get cut, and produce more output faces... so conversely, a more shallow tree means less potential for cuts (but larger facecounts at the leaves)

The output facecount is going to depend a lot on the geometry, and we'd have to go to an 'adaptive tree' to try to reduce the split count further, which would make the Generator so slow as to preclude the possibility of using it at runtime for blowing holes in things..and without the promise of actually reducing the #splits, since there is no guarantee that an optimal centroid position actually exists for an arbitrary set of input faces.

The best we can hope for without a heuristical best-case search is to find through trial and error the lowest value for the 'maximum faces per leafnode' constant which still produces an acceptable outcome...
Posted on 2007-03-27 08:12:13 by Homer
But isn't subdivision something to avoid in octrees??
AFAIK, octrees are fast and small when:
a) a polygon/object that is entirely inside the current cube-node, is kept there
b) a polygon that isn't entirely inside the cube, is moved to the parent node.
This way, you don't bring even more burden to the cpu and VGA card when drawing, and cpu when performing collision-detection.
Posted on 2007-03-27 08:57:14 by Ultrano
Generator App:
Here what I'm doing is taking an input xfile which would presumably contain the static World geometry for a Game Level, importing its data, stripping it of duplications, and generating an 'MX Octree' from it, then saving that data to a custom file.
The potentially massive input file is subdivided into octants and suboctants according to our heuristic, and for each node that contains faces after processing is completed, the REFERENCED subset of vertices are stripped of duplicates, and suitable 16-bit indices are generated, leaving a neat little package of vertices and indices at the appropriate nodes, each suitable for shoving directly into D3D buffers.
The distribution/renumbering scheme allows us to have more than 64k vertices, which is reasonable for a modern game.
Basically, we can make bigger levels, without being forced to use 32bit indices, or using relative vertices (ugly), so our file and runtime memory requirements are reduced for a larger model.

Demo App:
Here I'm reloading the custom file, rebuilding the Octree, and presumably applying frustum culling to the octree in order to cull the World surfaces and presumably also to cull any object instances that have been attached to any Octree nodes.
The goal is to create a SceneGraph that contains space partitioning data as well as the objects which inhabit the subspaces, and is thus geared toward view-dependant culling.
Each octree node may contain a list of faces, a list of entities, both, or neither.. the entity list might end up being a subtree or list of subtrees (of Frames) for the purpose of object relativity (eg relative position/rotation of subobjects).

I don't attempt to subdivide objects in general, just the World itself.
The example I gave for Tiger.x was a bad example, giving the wrong impression.

Attaching of objects to the Octree nodes is outside the scope of my thread (so far).
Posted on 2007-03-27 09:13:04 by Homer
My Octree is actually already a hybrid MX Octree / SphereTree.
Each Node has a 'HyperBox' (ie the infinite inverse BoundingBox implied by a Centroid which intersects three Axial Planes), but the nodes that contain geometry ALSO have a BoundingSphere.

The HyperBox cuts space into 8 equal subspaces.
The BoundingSphere  encloses a node's Faces.
Both of them offer extremely fast point-based testing.
The Spheres are ONLY to be used for Visibility Testing.
When we want to Render, we walk the Octree looking for Nodes which contain Faces, and thus a BoundingSphere... when we find one, we test the Sphere against the Frustum, and if we fail, we return from recursion.. elseif we succeed, we draw that node's faces, AND if the node is non-leaf, we continue recursing until we reach a Leaf.
Thus, we're only visibility-testing on a subset of the octree nodes, rather than all of them, and using a geometry which is potentially a better fit around the PVS than the hyper or regular cube is, and using  tests which are quite a bit faster than any box test.

The Spheres in the SphereTree may overlap one another etc, they're not meant to be accurate, they're meant to be fast (they are 'hungry', and never return a false negative but can return false positive) - I believe in using Sphere tests to check the 'proximity' of two test entities, and then using a more accurate secondary test if the result of the first test is positive - in this case, I'm merely extending that logical premise and applying it to the World itself in order to improve apon the performance offered by conventional frustum/octree schemes.

The octree's node-box hierarchy accurately subdivides space, but does not care much about the distribution of geometry within it.
Once we have such a Tree, we can easily generate a SphereTree WITHIN the Octree, which better describes the NON-EMPTY SUBSPACES within the Octree that contain POTENTIALLY VISIBLE GEOMETRY of the static world surface variety :)

Posted on 2007-03-27 09:38:30 by Homer
The first implementation of the hybrid octree/spheretree with frustum culling is complete and tested.

I decided to create a boundingsphere for each and every Node during the tree generation.
Whenever we create a new OctNode and shove its input subset of Faces into it, we calculate the boundingsphere (origin and size) of that subset of faces.
The sphere may not completely enclose the BoundingBox of the Octant, but it does not have to.
It completely encloses the INPUT subset of faces, which includes all the faces that belong to that Octant AND any child octants that are at that stage yet to be created.

So - each Octant has a Sphere that bounds 'any faces in that octant, plus those in any child octants'.

I now perform a sphere/frustum intersection test at each OctNode.

Here is the code for my Sphere/Frustum test,

;Tests a Sphere against a set of Frustum Planes, return values are:
;-1 = totally outside the frustum
; 0 = intersecting one or more frustum planes
;+1 = totally inside the frustum
SphereInFrustum proc uses esi ecx pvSphereOrigin,fSphereRadius,pFrustumPlanes
LOCAL fDistance:real4
LOCAL fRad:real4
; calculate our distances to each of the planes
xor ecx,ecx
mov esi,pFrustumPlanes
.while ecx<6

;Calculate : fDistance = (PlaneNormal . vSphere) + PlaneD
mov eax,pvSphereOrigin
fld  .Vec4.x
fmul .Vec3.x
fld  .Vec4.y
fmul .Vec3.y
fld  .Vec4.z
fmul .Vec3.z
fadd .Vec4.w
fstp fDistance

; if this distance is < -sphere.radius, we are outside
;if(fDistance < -refSphere.Radius())
; return(OUT);
fld fSphereRadius
fstp fRad
fMin fDistance, fRad
fstpReg eax
.if eax==fDistance
return -1

; else if the distance is between +- radius, then we intersect
fAbsMin fDistance, fRad
;if((float)fabs(fDistance) < refSphere.Radius())
; return(INTERSECT);
.if eax==fDistance
return 0
add esi,sizeof Plane
inc ecx

; otherwise we are fully in view
return 1
SphereInFrustum endp

and my culled octant drawing code:

;Draw the entire OctTree with Frustum Culling
Method OctTree.DrawCulled,uses esi,pnode, pFrustumPlanes
.if pnode!=0
SetObject esi
ICall pD3DDevice::IDirect3DDevice9.SetFVF,.dFVF
mov edi,pnode
invoke SphereInFrustum,addr .OctNode.vSphereCenter,.OctNode.fSphereRadius,pFrustumPlanes
.if eax!=-1
OCall pnode::OctNode.Draw
mov edi,pnode
lea edi,.OctNode.pPPP
xor ecx,ecx
.while ecx<8
.if dword ptr!=0
push ecx
push edi
OCall DrawCulled,  dword ptr,pFrustumPlanes
pop edi
pop ecx
inc ecx

Note that the SphereFrustum test returns 'visible' if the sphere is totally inside the frustum, OR if the frustum is totally inside the sphere.. that's quite handy!

Note that the culled render function will draw both partially and fully visible nodes.

Posted on 2007-03-28 02:55:43 by Homer
I've extended my Frustum code.
It can now return one or more of the following:
-Frustum Planes (x6)
-Frustum Vertices (x8)
-Frustum BoundingSphere (vOrigin and fRadius)

I then wrote a proc that tests for the intersection of two Spheres.
If the distance between their Origins is greater than the sum of their radii, then they do not intersect.

Finally, I modified the 'render-with-culling' method in my Octree code to use the new Sphere/Sphere test as the primary test.
In my previous post, I wrongly asserted that the Sphere/Frustum test would detect the case of 'frustum inside sphere'.
It doesn't, but this new test handles the the case of 'frustumsphere inside octantsphere' perfectly.

Still, I did say PRIMARY test, we must think of the sphere/sphere test as a 'proximity' test.. it can give false positives, but not false negatives.

Extracting the Frustum BoundingSphere every time the View changes isn't cheap, but I think it will be worth the cost considering the savings we can obtain from using sphere/sphere as the primary test.

Let's assume we tested sphere/sphere and detected intersection.
How do we know it's not a false result?
For the special case of the frustumsphere, first we'll make sure that the testsphere could fit inside the frustumsphere (has smaller radius).
A>If it won't fit inside the frustum, then the frustum is 'inside it', and so we ASSUME its partially visible, since part of it is inside our frustum!!
B>If it WILL fit inside the frustum, we'll perform our crapworthy frustum/sphere secondary test, which will now return reliable results, ie whether there is a full or partial visibility involved with respect to the frustum planes.

Just because the testsphere T intersects the Frustumsphere F, we cannot conclude that testsphere T ALSO intersects the Frustum PlaneSpace.. we need to perform that second check, which MAY FAIL, indicating that the testsphere is PROXIMATE to the Frustum, but is NOT VISIBLE.

I think that is sufficiently accurate for visibility culling purposes.
Anyone have comments or ideas?
Posted on 2007-03-28 06:18:59 by Homer
I know that some frustum culling implementations remember the plane that gives the last positive result to check for that plane first, when the next frame is rendered.


Posted on 2007-03-28 09:07:39 by Biterider
That's a great idea for accelerated walking of trees in general, and one I've used in another component of this project already (SkinMesh).
I'll bear it in mind as I go.

Last night I slapped myself a few times, and then changed the way I calculate octnode boundingspheres.
Now I simply calculate and store the sphere which bounds the NODEBOX, so the Sphere and Box share the same Origin.
Our spheres are now large enough to contain ALL the space owned by an octnode, and therefore, anything WITHIN an octnode, which is consistant with typical spacepartitioning schemes.

We still need to perform secondary testing to check for false positives, what we've achieved is to ensure that any entities which are later attached to octnodes fall completely within the bounds of the proximity hull, guaranteeing that we don't accidentally cull them.

Here's my current visibility-culling nodewalk function.
I'm not currently drawing entities that are attached to Octnodes, because this project currently doesn't support that.. that'll be addressed in due course.
Note that the Child octnodes of the current node are only recursed if the current node is not culled (is partly or fully visible) - of course, if a node isn't visible, then none of its children are either.

;Draw the entire OctTree with Frustum Culling
Method OctTree.DrawCulled,uses esi,pnode, pFrustumPlanes
.if pnode!=0
SetObject esi
mov edi,pnode
invoke Sphere_x_Sphere,addr .OctNode.vBBCenter,.OctNode.fSphereRadius,addr myFrustSpherePos,myFrustSphereRad
.if eax!=-1
;The primary 'proximity test' returned a Positive result..
;Check if nodesphere could fit inside frustumsphere
mov edi,pnode
fAbsMax .OctNode.fSphereRadius, myFrustSphereRad
fstReg eax
.if eax==myFrustSphereRad
;The nodesphere is smaller than the frustumsphere,
;so we will perform a secondary and more accurate test
;using the nodesphere and the 6 frustum Planes
mov edi,pnode
invoke SphereInFrustum,addr .OctNode.vBBCenter,.OctNode.fSphereRadius,pFrustumPlanes
.if eax==-1
;failed secondary test - no intersection, but is 'proximate', if that matters to us..
;We've decided the Node is partially or fully visible
ICall pD3DDevice::IDirect3DDevice9.SetFVF,.dFVF
OCall pnode::OctNode.Draw
mov edi,pnode
lea edi,.OctNode.pPPP
xor ecx,ecx
.while ecx<8
.if dword ptr!=0
push ecx
push edi
OCall DrawCulled,  dword ptr, pFrustumPlanes
pop edi
pop ecx
inc ecx

ps : I just added a couple of params so that the function no longer relies on static variables eg myFrustumSpherexxx
Posted on 2007-03-29 01:39:48 by Homer
I've added a pEntities field to my OctNode.
It's a 'DataCollection' object which contains a list of 'Entity' structs.

Here's the Entity struct.

;This container is used to represent one Node in a SceneGraph of arbitrary entities.
;Each OctNode contains a list of N Entity structs, representing individual entities.
;Each Entity struct is the rootnode of a Frame Hierarchy, which means that
;we are supporting 'compound entities' ie CSG, and also support 'relativity'.
;Please NOTE this is a Derived Frame Struct, which D3D likes to work with,
;and that we're able to implement our specific entities as Object Classes
;since this struct acts as a container for arbitrary objects.
;We use the Frame.pMeshContainer field to point to the actual object.
Entity struct
matCombined D3DXMATRIX <> ;not sure if I really want this here
EntityType db ?
EntityState db ?
Entity ends

I think the comments cover everything important regarding the Entity struct.

The OctNodes in our OctTree are our main SceneGraph nodes.
They represent 'non-empty subspaces' in our World.
Any NULL OctNode Pointers refer to 'empty subspaces'.
Think of the Game World without any movable objects or creatures.
Just the immutable World itself.
Normally, we'll be attaching uor entities to nodes that already contain some world surfaces.
Will we ever wish to attach entities to 'empty nodes'?
We might wish to place a bird in the sky.
The sky is a region that contains no World faces, so we didn't bother to create an OctNode to represent it.
Instead, there's a NULL pointer somewhere that WOULD lead to this sky node, if it existed..

I am going to alter the Loader function to create dummy nodes to represent the empty subspaces. This means that we will never find any NULLs in any OctNode's 8 childpointers, unless they are ALL NULL, which would indicate either a Dummy Node (which contains no faces), or a Terminal Node (which contains Faces).
Altering the Loader means that Dummy nodes are not stored in my custom file.

Having done that, we can make the following statements:
Non-Leaf Nodes contain 8 VALID ChildPointers, while LeafNodes contains 8 NULL ChildPointers.
Dummy Nodes are LeafNodes which contain No Faces.

Oh, just one more thing to say.
It's about the entity lists.

I won't attempt to store entities in multiple nodes, thats just messy and painful, what I'll do is store them in the first node that completely bounds them... if object X won't fit totally in a given node, I'll just try its parents until I find one it fits into.
The octree's rootnode bounds the entire World, so we're sure to find a happy home for any entity unless it's large enough to swallow the World :P
Posted on 2007-03-29 08:47:19 by Homer
I haven't modified the Loader for DUMMY octnodes yet, I got carried away with three new Methods:

Compares given Point to octnode's centroid, and returns the index of the child octant (0-7) which that Point would exist in. This is quite a fast operation.

Uses the previous method to explore the octree looking for the deepest node which bounds the given point.

Same as the previous method, but for Spheres, via a Sphere/NodeSphere test.

Now, assuming that I've created the Dummy Nodes as mentioned earlier, I can now find the deepest octnode into which arbitrary entity X's boundingsphere will fit... useful eh?

Posted on 2007-03-29 11:51:55 by Homer
Because I've opted to go for a FrustumSphere-based primary cull, the frustum-related code has become more critical in terms of performance.
I'm just spending some time working over the existing code before extending it further.
I'll be designing a master class representing an instance of some renderable object, from which I'll derive classes for all the kinds of stuff we'd like to attach to the world('s octree nodes).
This master class will define some abstract methods for performing common tasks such as rendering, positioning and orienting.

Posted on 2007-04-04 06:13:06 by Homer

Because I've opted to go for a FrustumSphere-based primary cull, the frustum-related code has become more critical in terms of performance.

isnt that a perfect case to speedup with help of SSE?, because squareroots are pretty fast, because they are highly parallelizable, could cull several coordinates at once, radius and center of sphere and each coordinate x,y,z relative center of sphere
busy modelling, just made an outfit, interesting in make use of a lowpoly model and RTRT it in a hall of mirrors

Posted on 2007-04-23 03:26:45 by daydreamer
anything new?
Posted on 2007-07-07 13:43:23 by daydreamer