Jump to content

  • Log In with Google      Sign In   
  • Create Account

octree stackoverflow


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 17 December 2012 - 07:12 AM

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[i] = 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[i]->getBBox());
  if(result)
  {
   sNode = nodes[i];
   ++cnt;
  }
}
if(cnt <= 1)
{
  _tree->leaf = true;
  return;
}
else
{
  sNode = nullptr;
  for(std::size_t i = 0; i < 8; ++i)
  {
   child[i] = std::shared_ptr<OcTree>(new OcTree(pSmgr, subdivide(_tree, i)));
   create(child[i]);
  }
}
}
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[i]);
   }
  }
}
}

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.

Sponsor:

#2 L. Spiro   Crossbones+   -  Reputation: 13617

Like
4Likes
Like

Posted 17 December 2012 - 07:40 AM

Stack overflow means you have too many recursive functions (among other unrelated things).
You need to check the depth at which you stop generating nodes within the octree. Usually 8 nodes deep, including the head node, is the maximum depth for an octree.

A quick glance at your code shows no sign that you ever terminate the creation of the octree. You just keep creating more and more nodes infinitely deep until it overflows the stack. levelCnt is being incremented but never used.
Additionally, it is “used” incorrectly. The depth of the tree must be passed as a parameter to the function that recursively creates nodes.


L. Spiro

Edited by L. Spiro, 17 December 2012 - 07:42 AM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#3 rnlf   Members   -  Reputation: 1145

Like
3Likes
Like

Posted 17 December 2012 - 07:54 AM

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, 17 December 2012 - 07:55 AM.

my blog (German)


#4 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 17 December 2012 - 08:00 AM

A quick glance at your code shows no sign that you ever terminate the creation of the octree.

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.

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?


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.

#5 SaurabhTorne   Members   -  Reputation: 259

Like
1Likes
Like

Posted 17 December 2012 - 08:14 AM

Jim Adams book has a good octree sample. Might as well check it

#6 rnlf   Members   -  Reputation: 1145

Like
3Likes
Like

Posted 17 December 2012 - 08:28 AM

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, 17 December 2012 - 08:28 AM.

my blog (German)


#7 Scourage   Members   -  Reputation: 742

Like
0Likes
Like

Posted 17 December 2012 - 09:30 AM

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


Octree puns...So funny!

Halfway down the trail to Hell...

#8 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 17 December 2012 - 10:47 AM

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[i]->getBBox());
  if(result)
  {
   _tree->vNode.push_back(nodes[i]); // 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[i] = std::shared_ptr<OcTree>(new OcTree(_tree->pSmgr, subdivide(_tree, i)));
   create(child[i], curr_level + 1);
  }
}
}

If you need more info please tell.

Edited by belfegor, 17 December 2012 - 10:51 AM.


#9 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 17 December 2012 - 12:21 PM

Jim Adams book has a good octree sample. Might as well check it


What is the name of the book?

#10 JoeJ   Members   -  Reputation: 219

Like
1Likes
Like

Posted 17 December 2012 - 03:54 PM

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, 17 December 2012 - 04:26 PM.


#11 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 17 December 2012 - 04:25 PM

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


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[i].visible)
		 object[i].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, 17 December 2012 - 04:26 PM.


#12 JoeJ   Members   -  Reputation: 219

Like
0Likes
Like

Posted 17 December 2012 - 04:58 PM

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?

#13 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 17 December 2012 - 05:10 PM

where's the win from the octree?
If if you use dynamic objects in it, it's slow - too much recursion...

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?

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.

#14 SaurabhTorne   Members   -  Reputation: 259

Like
1Likes
Like

Posted 17 December 2012 - 09:06 PM


Jim Adams book has a good octree sample. Might as well check it


What is the name of the book?


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

#15 JoeJ   Members   -  Reputation: 219

Like
1Likes
Like

Posted 18 December 2012 - 04:17 AM

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.

#16 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 18 December 2012 - 06:19 AM

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):
Posted Image

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.

#17 JoeJ   Members   -  Reputation: 219

Like
1Likes
Like

Posted 18 December 2012 - 08:50 AM

if(result)
{
sNode = nodes[i];
++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, 18 December 2012 - 08:53 AM.


#18 belfegor   Crossbones+   -  Reputation: 2623

Like
0Likes
Like

Posted 18 December 2012 - 12:25 PM

Found where the bug was. Posted Image

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

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

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

Edited by belfegor, 18 December 2012 - 12:25 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS