• Advertisement
Sign in to follow this  

octree stackoverflow

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

I could not find good tutorial about octrees so tried to make one on my own.
I have a lot of non-moving/static objects in my scene so i thought i could speed up culling with octree instead with camera frustum-bbox check with all of these. Can you spot what am i doing wrong?

octree.h

class OcTree
{
private:
std::shared_ptr<OcTree> child[8];
sp_StaticMeshSceneNode sNode; // shared_ptr
bool leaf;
bounding_box3d bbox;
SceneManager* pSmgr;
enum OctreeParts
{
TOP_FRONT_LEFT = 0,
TOP_FRONT_RIGHT = 1,
TOP_BACK_LEFT = 2,
TOP_BACK_RIGHT = 3,
BOTTOM_FRONT_LEFT = 4,
BOTTOM_FRONT_RIGHT = 5,
BOTTOM_BACK_LEFT = 6,
BOTTOM_BACK_RIGHT = 7
};
public:
OcTree(SceneManager* _smgr, const bounding_box3d& _bbox);
void create(std::shared_ptr<OcTree> _tree);
bounding_box3d subdivide(std::shared_ptr<OcTree> _parent, int witchPart);
void cullChildren(std::shared_ptr<OcTree> _root);

static std::size_t levelCnt;
};


octree.cpp

std::size_t OcTree::levelCnt = 0;
OcTree::OcTree(SceneManager* _smgr, const bounding_box3d& _bbox)
{
bbox = _bbox;
pSmgr = _smgr;
for(std::size_t i = 0; i < 8; ++i)
{
child = nullptr;
}
leaf = false;
sNode = nullptr;
}
void OcTree::create(std::shared_ptr<OcTree> _tree)
{
++levelCnt;
std::size_t cnt = 0;
const auto& nodes = pSmgr->getNodes();
for(std::size_t i = 0; i < nodes.size(); ++i)
{
bool result = _tree->bbox.intersects(nodes->getBBox());
if(result)
{
sNode = nodes;
++cnt;
}
}
if(cnt <= 1)
{
_tree->leaf = true;
return;
}
else
{
sNode = nullptr;
for(std::size_t i = 0; i < 8; ++i)
{
child = std::shared_ptr<OcTree>(new OcTree(pSmgr, subdivide(_tree, i)));
create(child);
}
}
}
bounding_box3d OcTree::subdivide(std::shared_ptr<OcTree> _parent, int witchPart)
{
bounding_box3d outBB;
float3 ext = _parent->bbox.getExtent() * 0.5f; // (max - min) / 2
float3 cen = _parent->bbox.getCenter(); // (min + max) / 2
switch(witchPart)
{
case TOP_FRONT_LEFT:
{
float3 min = cen - float3(ext.x, 0.0f, 0.0f);
float3 max = cen + float3(0.0f, ext.y, ext.z);
outBB = oma::bounding_box3d(min, max);
}break;
case TOP_FRONT_RIGHT:
{
float3 min = cen;
float3 max = cen + float3(ext.x, ext.y, ext.z);
outBB = bounding_box3d(min, max);
}break;
case TOP_BACK_LEFT:
{
float3 min = cen - float3(ext.x, 0.0f, ext.z);
float3 max = cen + float3(0.0f, ext.y, 0.0f);
outBB = bounding_box3d(min, max);
}break;
case TOP_BACK_RIGHT:
{
float3 min = cen - float3(0.0f, 0.0f, ext.z);
float3 max = cen + float3(ext.x, ext.y, 0.0f);
outBB = bounding_box3d(min, max);
}break;
case BOTTOM_FRONT_LEFT:
{
float3 min = cen - float3(ext.x, ext.y, 0.0f);
float3 max = cen + float3(0.0f, 0.0f, ext.z);
outBB = bounding_box3d(min, max);
}break;
case BOTTOM_FRONT_RIGHT:
{
float3 min = cen - float3(0.0f, ext.y, 0.0f);
float3 max = cen + float3(ext.x, 0.0f, ext.z);
outBB = bounding_box3d(min, max);
}break;
case BOTTOM_BACK_LEFT:
{
float3 min = cen - float3(ext.x, ext.y, ext.z);
float3 max = cen;
outBB = bounding_box3d(min, max);
}break;
case BOTTOM_BACK_RIGHT:
{
float3 min = cen - float3(0.0f, ext.y, ext.z);
float3 max = cen + float3(ext.x, 0.0f, 0.0f);
outBB = bounding_box3d(min, max);
}break;
default:
{
assert(false);
}break;
};
return outBB;
}
void OcTree::cullChildren(std::shared_ptr<OcTree> _root)
{
if(nullptr == _root)
return;
sp_Camera cam = pSmgr->getPlayerCamera();
if(cam->getFrustum().isBoxInFrustum(_root->bbox))
{
if(_root->leaf)
{
if(nullptr != _root->sNode)
_root->sNode->visible = true;
}
else
{
for(std::size_t i = 0; i < 8; ++i)
{
cullChildren(_root->child);
}
}
}
}


Then i create octree:


bounding_box3d ocBB(float3(-8.1028748f, -10.665000f, -147.71899f), float3(270.58899f, 18.529583f, 98.760002f));
ocTree = std::shared_ptr<OcTree>(new OcTree(this, ocBB));
ocTree->create(ocTree); // stack overflow


Stack overflow is in create method.

Thank you for your time.

Share this post


Link to post
Share on other sites
Advertisement
Yes, he tries to stop the recursion. create will only create child nodes if the number of intersections (however they may be definied by bbox.intersects) is greater than 1.

But I still guess the abort criterion is wrong. If there are overlapping scene nodes, "create" will never reach its stop criterion.

Does it work if you use an empty scene graph or make sure there are only scene nodes that are far enough apart?

But passing the current depth recursively to create and adding a condition for this depth to be below a configurable value around line 27 of octree.cpp should solve the problem. Edited by rnlf

Share this post


Link to post
Share on other sites

A quick glance at your code shows no sign that you ever terminate the creation of the octree.
[/quote]
But i thought it will stop when there is a 1 or none of scene objects bbox intersecting with current octree bbox?

if(cnt <= 1)
{
_tree->leaf = true;
return;
}


I don't quite understand what should i do different?

But I still guess the abort criterion is wrong. If there are overlapping scene nodes, "create" will never reach its stop criterion.[/quote]
I don't know how to overcome that.


Does it work if you use an empty scene graph or make sure there are only scene nodes that are far enough apart?
[/quote]

Do you mean i should group nodes to have its own bbox?

How to correctly builld octree for static objects given my example above?

Thank you for your time.

Share this post


Link to post
Share on other sites
You will overcome this problem by adding a check for the level of your current node. Quick example (please put it together with the rest of your code yourself):

[source lang="c++"]void create(std::shared_ptr<OcTree> _tree, int level) {
... all the rest, test for intersections and stuff ...
if(cnt <= 1 || level > max_level) {
... all the stuff you do in your original code, except that you may have a list of nodes instead of only one ...
} else {
.... create(..., level + 1) ...
}
}[/source]

Hope this is understandable, don't really have the time to go more in depth at the moment. Edited by rnlf

Share this post


Link to post
Share on other sites
It got rid of overflow but i am doing something wrong in my create function (at least i suspect the problem is there) because i got only few objects displayed compared to what i can see with camera. Please help me further if you find time, thanks.

I can't think of right logic for this:

const std::size_t max_level = 5; // everything above 5 is to slow

void OcTree::create(std::shared_ptr<OcTree> _tree, std::size_t curr_level)
{

std::size_t cnt = 0;
const auto&amp; nodes = pSmgr->getNodes();
for(std::size_t i = 0; i < nodes.size(); ++i)
{
bool result = _tree->bbox.intersects(nodes->getBBox());
if(result)
{
_tree->vNode.push_back(nodes); // vNodes is vector of objects
++cnt;
}
}
if(cnt <= 1 || curr_level > max_level)
{
_tree->leaf = true;
return;
}
else
{
_tree->vNode.clear();
for(std::size_t i = 0; i < 8; ++i)
{
child = std::shared_ptr<OcTree>(new OcTree(_tree->pSmgr, subdivide(_tree, i)));
create(child, curr_level + 1);
}
}
}


If you need more info please tell. Edited by belfegor

Share this post


Link to post
Share on other sites
Hi there,
I can't read your code - too much stl :/
But i remember the pitfalls with octrees, so that might be helpful, if you don't know it:

The problem is: What to do with an object that is split by one or more grid planes?
Put it in each node and draw it multiple times?
Put it in one node and missing to draw it whaen the node is clipped? (guessing thats your problem)

Solution: Put each object to the node, where this condition is true:
objects bounding box center is inside node
AND the largest dimenson from the objects bounding box <= the dimenson of the node.
AND the largest dimenson from the objects bounding box > half the dimenson of the node.

... this results in large objects at the top levels, and small objects at the bottom levels of the tree.

While clipping extrude the nodes by one half of its dimension at each side (so it has 4 times its volume).
This is the volume that surely covers all objects.

I guess that is called 'loose octree', but i'm not sure. Edited by JoeJ

Share this post


Link to post
Share on other sites

What to do with an object that is split by one or more grid planes?
[/quote]

That is not a problem at all, I'll put it in both cubes, and then when i iterate over octree i just set a flag to visible for that object. No harm done doing it multiple times.

this:

octree->process(camera.frustum);
...// more work here
...
...
...
...
drawAll()
if(object.visible)
object.draw()

there is no redundant drawing only redundant copies of pointers.

The problem is that there is something wrong with my code for creating cubes. Edited by belfegor

Share this post


Link to post
Share on other sites
Ok, but with your design you'd get the same or better performace with a simpler grid approach, because most objects will be in the small max level nodes.
The result looks more like a sparse grid, that you could clip with large cubes containing smaller cubes without the need of an octree... where's the win from the octree?
If if you use dynamic objects in it, it's slow - too much recursion, shared pointers and dynamic memory allocation... slow.

However, i can't see a bug in the code. Are you sure the frustum check is right?

Share this post


Link to post
Share on other sites

where's the win from the octree?
If if you use dynamic objects in it, it's slow - too much recursion...
[/quote]
Its just for static objects since i have ~3000 in current scene. I am planing to mix this with hw occlusion query like in this article (someday if i can done coding right):
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter06.html

For now i want octree done right if possible.



However, i can't see a bug in the code. Are you sure the frustum check is right?
[/quote]
I am going thru code for hours now and can't spot what else is wrong.
If i use frustum check with all objects bboxes culling works, but not with octree bboxes.

Share this post


Link to post
Share on other sites

[quote name='SaurabhTorne' timestamp='1355753695' post='5011700']
Jim Adams book has a good octree sample. Might as well check it


What is the name of the book?
[/quote]

"Role playing games using directx". A very good book for starting with directx.

Share this post


Link to post
Share on other sites
I still believe its a geometirc issue.
Are the missing objects popping depending on camera or do the never appear?
Did you check after the creation, if each object ist at least in one node?
Did you visualize the node extends, maybe one of the 8 cases has a bug?

For occlusion query it's good to draw objects in raw front to back order, even without occ. test that saves pixel shader due to early z-test.
To achieve that you draw objects by traversing the octree bottom down drawing the near child first.
Here the loose octree has advantage too, because front back order is more precise and you draw large objects (good occluders) first.
but its easy to try that after you found the bug...


Some other things you may or may not end up with later, just to keep in mind:
Node extends and position can be calculated dynamically while traversal, no need to store them for each node.
If you align the grid at integer coords, you can use brachless integer bitmath for very fast searching in the tree.
Mostly it's a win to either point to an array of 8 children (some of them may end up unused), or there are no children.

Personally i use it for the same purpose, but i have not made any of those optimisations listed above :)
But i did it with a software-renderer that used quadtreecompressed lightmaps, so each scanline was clipping a line into the quadtree,
and there i saw a great speedup.

Share this post


Link to post
Share on other sites
Thank you very much for trying to help me. I am working on it today, and hopefully resolve this problem.

About cases, i think i got this right (i made a reference image in modeling editor showing one subdivision):
octree.jpg

each bbox min is in lower left and max in upper right corner like in the picture? I mean they are min a max possible coords for bbox.

Share this post


Link to post
Share on other sites
if(result)
{
sNode = nodes;
++cnt;
}

This adds the object to a vector, right? It looks like it replaces the current pointer with a new one, storing only one object at the end.
I'm noob with stl and c++11.



The image looks nice (min / max is good way to define axis aligned boxes),
but you need to visualize that inside your engine, to proof that its right.

I'd do this: Turn off Z-Test, traverse the entire tree, if a leaf is found, draw its slightly shrinked extends with a transparent color.
Build the color from the nodes memory adress, so you can see different nodes better.
For each object in the node, draw a line from node center to object center.

Afterwards draw all objects in wireframe. Navigate through the scene, and check if the objects are linked correctly to the nodes.
If an object has no line, or the line points to a node far away, you know more.

If still anything looks right, visualize the cameras viewing pyramid (to see that, you need two cameras, one to observe and one for yourself to fly around).
While traversing octree, draw nodes extends in white wireframe, if they fail the observeds cameras frustum check.

...that's some work, but you will surely see the bug - from another perspective - and then its easy to find it.
And its good for future bugs. Edited by JoeJ

Share this post


Link to post
Share on other sites
Found where the bug was. biggrin.png

In create function

_tree->vNode.clear();
for(std::size_t i = 0; i < 8; ++i)
{
child = std::shared_ptr<OcTree>(new OcTree(_tree->pSmgr, subdivide(_tree, i)));
create(child, curr_level + 1);
}


Should be:

_tree->vNode.clear();
for(std::size_t i = 0; i < 8; ++i)
{
_tree->child = std::shared_ptr<OcTree>(new OcTree(_tree->pSmgr, subdivide(_tree, i)));
create(_tree->child, curr_level + 1);
}


Damn recursive functions, should step back and learn again about them better. Edited by belfegor

Share this post


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

  • Advertisement