SceneManager with octree support?

[eis_os]

I changed the design and now have a static octree in a SceneNode,
if you want to create your own:

I made an pirvate octree class that get init by a box and the devides to a specific depth.
Overloaded addchild, removechild of the OctNode Class.


Some Pitfalls:
Currently I don't know how a Node can say the octree has moved,
if you try to attach an constructing node, it fails because the OctNode access not yet init data... Currently I work around this by attaching it to root node and then to the OctreeCulling Node.

If you have ideas I would be very glad to hear...

[Gorgon Zola]

Hi eis_os

I'm also interested in an octree scenenode.

For the position change You'd have to change the behaviour of the setPosition method of the scenenode to notify the parent of the position change. (most likely this means that you'll have to change some things in ISceneNode)
The parent that holds the octree would probably need a notification queue to rearrange the octree (or maybe you can do that just when the parent is notified. I'm not sure what will be faster, might depend on the actual programm?)

Anyway, I'm really interested in what you'll come up with, especially concerning performance. According to the books this should be a noticable performance gain if you have a lot of scenenodes (>1000 ???)

cheers
Tom

[eis_os]

Hi

You don't get any speed improvement when you look on all nodes,
or I don't get one.
Somehow using the autoculling only doesn't work right.
I don't know why, but when I look exactly from top to my landscape nodes (but only a portion can be seen) I tries to draw all nodes .
Niko, is this known?

OctNode:
If I only can see a 12x12 portion (a content of one octbox) of my nodes I will get ~40fps.
A full map will be drawn in 9fps... (as it does with autoculling and without using the octnode)

I loaded 100x100 Nodes currently and attached them to the octnode/or using autoculling.

I don't wanna change the ISceneNode internals because this would mean a recompile of the full engine every release...

[Gorgon Zola]

@eis_os:

You don't get any speed improvement when you look on all nodes,
or I don't get one.

OK, when You look on all nodes, but when you anly see some nodes at least some performance gain should be visible. *shrug* There are some articles about Octrees in the book "Game Programming Gems 1". I havent read them yet but I think I will now

I don't wanna change the ISceneNode internals because this would mean a recompile of the full engine every release...

Yeah, I see. For me repositioning isn't an issue because I only want to render some static vegetation like trees, grass, flowers etc. I'm not sure if an octree is the right datastructure if you have may moving nodes.

[eis_os]

I am open to other datastructures...

[Electron]

I am interested in this also, though I think the simplest solution, at least if on is including moving objects, would simply be a regular 3D grid. Whenever the position of a scene node is set (directly by the user,by an animator, by a parent moving, it doesn't matter) it's grid position is calculated. Something like (totally inclomplete code)

Code: Select all

GridManager grdman;
/*create the grid. The user should be bale to define the number of cells in each direction*/
CGridCell cells[MAX_X][MAX_Y][MAX_Z]

t
then when a scene node is moved it would be something like

Code: Select all

grdman.removeNode(this);
//make the changes to xyz position here
grdman.addNode(this)

Code: Select all

CGridManager::RemoveNode(ISceneNode *node)
{
 cells[position.x/GRID_SPACE][node.position.y/GRID_SPACE][node.position.z/GRID_SPACE].removeNode(this)
}

CGridManager::addNode(ISceneNode *node)
{
 cells[position.x/GRID_SPACE][node.position.y/GRID_SPACE][node.position.z/GRID_SPACE].addNode(this)
}

Then when rendering the engine must determine which cells are visible and render only those cells. For a greater performance increase some animators and other things might not need to be calculated for non-rendered nodes (some still might be, have to be careful with this and it's a seperate topic anyway)

I'm not sure how much of a speed increase a grid system would give over the engine's autoculling, but one place where it would certainly be a lifesaver is ray-casting which currently iterates through every single node O(N) (disregarding for a moment that a node not conforming to the bitmask takes little time). Raycasting is indespensible for shooting, line-of-sight testing and other functions being used constantly in FPS or similar games

Determining quickly which grid cells needed to be rendered (or which ones the ray interescted) would probably be the only real hard part of the thing

[Electron]

I was rethinking. A grid allows easier movement, but an octree is faster for weeding out areas that don't need to be rendered/don't intersect with a raycast. Therefore, what about a combination of two data structures? I'm not sure if thsi has been done before, and I have no clue how well it would work, but here's my data structure

1) It is like an octree except it goes to the same depth everywhere. This slows tree traversal somewhat, but all actual data (scene nodes) is stored in the lowest level, thus allowing easy repositioning.


2) Here's how it works for rendering:
A new function, CSceneManager::isCulled(core::aabbox3d<f32> box) is added (instead of CSceneManager::isCulled(ISceneNode* node) )
Each octree cell stores a bounding box. CSceneManager::drawAll() calls isCulled for the highest level 8 octree cells. Each cell that returns true than has the process repeated for it's 8 subcells. When one gets to the lowest level cells the scene nodes in all remaining lowest level cells are added to the rendering list. OnPreRender would only be called for those nodes that were actually going to be drawn and OnPreRender would not have to test culling, since we've already doen thta with the octree.

3) the optimal number of octree levels would depend on the size and density of the scene and should be able to be set by the user (CSceneManager::setSceneOctreeDepth(s32 depth)) or automatically calculated (CSceneManager::calculateSceneOctreeDepth()) based on the current distribution of scenenodes.

4) I believe this method would yield higher performance in certain situations, though I have not tested it at all and there are likely catches I haven't though of. For scenes with few nodes it would probably be less efficient than testing every node (if the total number of bounding box checks ever exceeds the total number of nodes we're definately getting a performance degradation). Therefore if I get around to testing this out I will probably put in a function to allow the user to choose whether or not to use the octree scene rendering. The simplest method migh simply to, instead of changing drawAll() to add drawAllOctree as an additional function. If the user wanted an octree it would have to be specifically created before rendering.

5) I've kinda been thinking this out as I type it so anyone who notices glaring problems please let me know.

[Electron]

Well it seems no one is paying attention to my ramblings, but that's just as well because I keep finding problems with my own ideas. I was trying to think of something that would work better for dynamic nodes than what eis_os had, but everything I can come up with has other problems. The problem with the fixed-depth octree I proposed yesterday is that going all the way down to the bottom layer in areas that are very sparse would have a prohibitive cost. You'd end up testing more aabb's after all. I sorta solution would be to have each cell of the octree, at each level, store a count of the total number of nodes in it. Then if any cell had below a minimum number of scenenodes (minimum dependent on level of octree), completely traversing that area of the octree would be forgotten and the normal bool CSceneManager::isCulled(ISceneNode*)
would be called for all nodes that there were.

A problem is that every time a node moves it's position in the octree would have to be updated AND higher levels would all have to increases their counts.

This would probably speed up rendering a little, but I'm not sure how much and it might not be enough to offset the performance decrease caused by having to change a node's position in the octree when it moved

[eis_os]

Hi


Currently I use a static octree for my static stuff.

The apps goes down the octree and see what cubes are inside the frustum,
normally it should do a speed increase, But my test showed it wasn't faster.

I have found out a very big speed problem, it's described here:
http://irrlicht.sourceforge.net/phpBB2/ ... php?t=3453
Cacheing could solve the problem, niko?

Some thoughts I made about moving objects:

Small moveing steps result only in a new place at the nearby cubes.
So you go two steps back in your octree and start there to find it's new place.


Irrlicht doesn't seem very good in handling alot of objects
And most parts need to be rewritten or replaced by more special and faster functions...

[Electron]

Looking at the engine, I realized that irrlicht's test for object culling is quite trivial. Setting up a more elaborate structure so we do not have to test culling for each node is probably not worth the very small amount os speed increase we might get. I replied to the thread about your other problem however, I think that one is an area where improvement will yield a greater speed increase.