Jump to content

  • Log In with Google      Sign In   
  • Create Account

Calling all IT Pros from Canada and Australia.. we need your help! Support our site by taking a quick sponsored surveyand win a chance at a $50 Amazon gift card. Click here to get started!


Octree Frustrum Culling

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

#1 asmodeus812   Members   -  Reputation: 108

Like
0Likes
Like

Posted 27 August 2015 - 03:38 AM

Hello, times came when i had to implement some culling into my engine. I started by reading some stuff and so far so good. I managed to create an octree which can effectivly divide my geometry's vertices (per mesh)  into an octree. But here i have some Questions:

 

Currently i am using immediate mode to test if the culling works. And it does work, i am recursivly traversing the tree's nodes and testing against the node's bounding box if the frustum intersects with it. Repeat untill leaf is found and render that leaf's geometry (with immediate mode for testing) But now i would like to use VBO/VAO's to render the geometry in the leaves and here i see two options:

- 1.Each time the i traverse the tree push the leaves that intersect with the frustrum into a list then get the vertices out of them and construct a VBO and send it to be rendered.

- 2.Pre build a VBO for each leaf then just rebind for each visible leaf and render.

 

Anyway, which is the better option rebuilding a new vbo each time the frustum changes, or just rebinding multiple vbos (which is also expensive).

Also is this even the right approach , maybe i am missing something.

 
bool view_Culling(CFrustum& frusrum, COctree *node)
{
if (!node)
return false;

if (frusrum.CubeInFrustum(node->GetCenter().x, node->GetCenter().y, node- >GetCenter().z,(node->GetWidth()/2.0f)))
{
if (node->IsSubDivided())
{
view_Culling(frusrum, node->OctreeNodes()[TOP_LEFT_FRONT]);
view_Culling(frusrum, node->OctreeNodes()[TOP_LEFT_BACK]);
view_Culling(frusrum, node->OctreeNodes()[TOP_RIGHT_BACK]);
view_Culling(frusrum, node->OctreeNodes()[TOP_RIGHT_FRONT]);
view_Culling(frusrum, node->OctreeNodes()[BOTTOM_LEFT_FRONT]);
view_Culling(frusrum, node->OctreeNodes()[BOTTOM_LEFT_BACK]);
view_Culling(frusrum, node->OctreeNodes()[BOTTOM_RIGHT_BACK]);
view_Culling(frusrum, node->OctreeNodes()[BOTTOM_RIGHT_FRONT]);
}
else
{
//use prebuilded vbo here
//or push these vertices here in a list later build a dynamic vbo
//from them
node->DrawOctree(node);
return true;
}
}
return false;
}

Edited by asmodeus812, 27 August 2015 - 04:00 AM.


Sponsor:

#2 Ashaman73   Crossbones+   -  Reputation: 11933

Like
0Likes
Like

Posted 27 August 2015 - 03:44 AM


- 2.Pre build a VBO for each leaf then just rebind for each visible leaf and render.

This, rebuilding a VBO all the time is not necessary (and slow). You need to save your mesh somewhere and a VBO means only that the mesh is (most properly) stored in videomemory. So, keep in there and rebind it, then render it.


Ashaman

 

Gnoblins: Website - Facebook - Twitter - Youtube - Steam Greenlit - IndieDB - Gamedev Log


#3 asmodeus812   Members   -  Reputation: 108

Like
0Likes
Like

Posted 27 August 2015 - 04:32 AM

Okay , but the mesh is devided between the leaves. so for each leaf of the octree i will have 1 VBO with some vertices which will represent part of the mesh. And ill only render the parts that are visible thus binding multiple vbos. And its better right ?



#4 L. Spiro   Crossbones+   -  Reputation: 21308

Like
3Likes
Like

Posted 27 August 2015 - 09:35 PM

Why do your objects need to be polygon-divided by the octree? This sounds like a less-efficient variation on a BSP tree.


L. Spiro

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
You have misunderstood how culling with an octree works with rendering.
VBO’s have nothing to do with the octree.

First you update all objects in the scene. If an object has not moved, you don’t need to update it inside the octree. If it has, you reposition it inside the octree.
Then you use the octree against your frustum to find nodes of the octree that are visible.
For each visible node, you then test each object in that node (AABB against the frustum).
For each visible object, add it to the list to be drawn.


The VBO’s are part of the objects. There is no relationship between the octree and the VBO(’s) used to draw the object. The octree is only there to accelerate the process of selecting objects to draw.


L. Spiro

#5 Hodgman   Moderators   -  Reputation: 42046

Like
3Likes
Like

Posted 27 August 2015 - 10:38 PM


but the mesh is devided between the leaves. so for each leaf of the octree i will have 1 VBO with some vertices
You can store multiple meshes within one VBO. A VBO is just a memory allocation -- like malloc or new char[].

You don't have to draw the entire contents of a VBO -- you can specify an offset to start reading triangles from, and how many triangles to draw.

 

Also, you can use an index buffer.

In your situation, you can have the entire mesh stored in one VBO, and then every frame you would produce a new index buffer, which only contains the indices of the triangles that you would like to draw, and then issue one draw-call using all of those indices.

Alternatively, you don't need to dynamically create any data each frame -- just put all the triangles into one VBO, and all the indices into one IBO -- but with each 'leaf' occupying a different sub-section of that IBO. You then issue one draw-call per leaf, which specifies the IBO offset for that leaf, and number of vertices in the leaf.



#6 asmodeus812   Members   -  Reputation: 108

Like
0Likes
Like

Posted Yesterday, 01:27 AM

@L. Spiro

I think you misunderstood what i meant. You are assuming that the octree is divided by AABB when its not.Even then if a Terrain AABB intersects the frustum i will have to draw the entire thing which can be humongus, still drawing invisible parts of it. Further more I dont want to determine if An object is visible i want to determine which parts of it are visible if its too big to render completely. Also I realize that the entire scene can be stuffed inside one octree and culled from there , but that adds rather complicated problems (with materials,textures,shaders etc). My idea and approach will be different

The idea is that i have some kind of a BVH(maybe octree of AABBs) which will contain the Bounding Volumes of each object in a given scene. Then i will perfrom frustum tests on that structure to determine the nodes (and respectivly the models in that node) that are visible or not. Those that are not visible are simply not drawn, Those that are visible have 2 options: 

- They are Partly visible (their bounding volume is bigger than the frusum but still visible - Terrains,Big Buildings etc...) - Here is where the Octree from above comes into play. They will be tested against an Octree to determine exaclty which parts of them are visible. I wont go deep into my implementation but to clarify i can say that each object has modeldata property , modeldata can be reused among many objects. Each modeldata contains - vbo,ibo, vertices. Now it will contain prebuilt octree from the vertices so i can use it when i need to determine what to draw when the model is partly visible. I will probably test in object space since the vertices are already there and i will need to translate the frustum also in object space.

- They are entirely visible (their bounding volume is smaller than the frusum) - Directly sent to be drawn

Currently that is going to be applied to static , non-moving objects.

 

 

@Hodgman 

I think thats what i am looking for. Using 1 VBO (which i already have prebuilt) and only extract the vertices i currently need at each test against the tree. Can you explain further , maybe with some codeblocks how would that work ? Thanks !

 

Edit: What structure should i use to store the bounding boxes of the objects . I assume i can group the boxes in huge chunks and test against that and discard the entire chunk if not visible . But how would one build that structure ?


Edited by asmodeus812, Yesterday, 03:37 AM.


#7 L. Spiro   Crossbones+   -  Reputation: 21308

Like
0Likes
Like

Posted Yesterday, 05:26 PM

I think you misunderstood what i meant.

With your further explanation it seems clearer that you are taking a wrong turn.
 

but that adds rather complicated problems (with materials,textures,shaders etc).

Materials (which includes textures and shaders) are no more a problem when using octrees than if you simply had a linear array of objects and rendered them naïvely. They have absolutely no relationship with the culling process.
 

Even then if a Terrain AABB intersects the frustum i will have to draw the entire thing which can be humongus, still drawing invisible parts of it.

Terrain is always divided into chunks (usually of, say, 257×257 vertices, smaller with LOD) and visible chunks are drawn.
 

Also I realize that the entire scene can be stuffed inside one octree and culled from there

This is the correct route to take. Your complications related to materials are fictional.
 

They are Partly visible (their bounding volume is bigger than the frusum but still visible - Terrains,Big Buildings etc...)

All large objects are subdivided. Terrain into chunks, buildings into rooms and halls, interiors and exteriors, each with LOD’s, etc. Further special-case culling takes place inside buildings to avoid drawing the exterior altogether (if you can’t see outside of the building then the sky, terrain, and all outdoor objects are immediately skipped and a second, smaller octree is used which spans only the inside of the building).
 

The idea is that i have some kind of a BVH(maybe octree of AABBs)

A BVH and an octree are separate structures—an octree is not a kind of BVH.



There is nothing wrong with how you plan to structure objects using multiple smaller objects. A model is made up of multiple meshes. Each can have its own AABB, plus the AABB for the entire model. And if the model’s AABB is entirely inside the frustum there is no need to test the smaller mesh AABB’s. This is standard.

But culling itself is not a free series of instructions. If your culling method is too complex then it becomes slower than not culling at all. It is better to check mesh AABB’s (the smaller parts of models) linearly one-by-one than to maintain, update, and traverse yet another octree.

There exists the scene octree (or BVH) and nothing more (unless you add the interior/exterior special case for being inside buildings mentioned above). There are not mini-octrees inside all of the models, as such a costly culling method for so few objects doesn’t make sense. They are however culled.  Just one-by-one, no secondary acceleration structures (a BVH here might make sense only for static objects, but again you would need to test that it actually helps, because you are entering a granularity where it becomes questionable).
 
And finally, none of this has anything to do with materials.  I don’t know why you even mentioned them.  Culling and rendering are disjointed and separate operations.  You build a list of renderables via the culling pass, then you sort them with a render queue, then you render them.  Culling uses an object’s AABB, and an AABB has no idea what materials are, it simply defines a geometric space.


 

I think thats what i am looking for. Using 1 VBO (which i already have prebuilt) and only extract the vertices i currently need at each test against the tree. Can you explain further , maybe with some codeblocks how would that work ? Thanks !

This is unrelated to culling, but a model has a single VBO and each mesh has an IBO which references vertices inside of it. This isn’t a culling issue, but simply a good idea to avoid rebinding VBO’s etc. Based on your explanation, it doesn’t seem worth it to rebuild the IBO(’s) in any way related to culling. Subdividing meshes at run-time is overkill and simply not worth the cost just to avoid drawing a few off-screen triangles.


 

Edit: What structure should i use to store the bounding boxes of the objects . I assume i can group the boxes in huge chunks and test against that and discard the entire chunk if not visible . But how would one build that structure ?

Models and meshes have AABB’s. The AABB’s inside the models (the mesh AABB’s) are too numerous and small and should be ignored for this part of the discussion, as including them in the scene’s octree or BVH would cause update hell (unless they are purely static).
The scene’s spacial-partitioning scheme can be either a BVH or an octree, but care must be taken in how either is implemented for there to be any benefit. In either case, the finest granularity is at the model level, not the mesh level.

In the case of octrees, the nodes in the tree must be linear in memory. Cache misses while traversing the tree will otherwise become so significant that the octree itself causes performance to drop overall, even if half the objects in the scene are ultimately culled.
Additionally, octrees are memory-consuming and in a naïve implementation you can only afford to have a few levels in the tree. This is why a hybrid approach is more common, using an Efficient Instant-Insertion Quadtrees for the X and Z (horizontal plane) and a stack for the Y (vertical plane).

In the case of BVH’s performance will depend heavily on your construction strategy, and they can’t be rebuilt at run-time efficiently (can only contain static objects).
https://en.wikipedia.org/wiki/Bounding_volume_hierarchy#BVH_design_issues


Note that it is perfectly acceptable to have terrain be a special case and be culled differently from the rest of the scene.  In fact terrain culling can be so wildly different that it can define the terrain itself.
http://research.microsoft.com/en-us/um/people/hoppe/gpugcm.pdf
http://www.flipcode.com/archives/article_geomipmaps.pdf
 
 
L. Spiro

#8 asmodeus812   Members   -  Reputation: 108

Like
0Likes
Like

Posted Today, 12:16 AM

Okay, well. Correct me if i am wrong your idea is to use each object's bounding box as a culling mechanism. And just yesterday i implemented something like tha. Using bullet physics (which i use in the engine for other purposes) i managed to implement frustum culling (it also supports occlusion culling but i wont dive into that just for now). So bullet maintains a dynamic AABB tree which contains the aabb of each model so i managed to make it cull the geometry on object basis.Bullet retuns a List of visible objects and the rest is just looping over them (here i may want to sort on some criteria to avoid state changes) Works nice and neat for about 6000 objects (about 2 500 000 triangles) , Also perfromed a profiling and the most expensive call is to DrawElements, cause they are all individual objects (not batched), guess that's ok.  

 

"Simply not worth the cost just to avoid drawing a few off-screen triangles"

 

I dont think that's very true. You consider only a terrain as a type of shape that can have dense amount of triangles , and that's just not true. Imagine i wanted to load a model type (for example the Sponza) it's heavy and huge and doesnt have "just a few off-screen triangles" (if you decide to use it as a building type). And sponza (and similarly huge geometry) is worth going deeper into some kind of spacial part. That was my itial idea , to keep another level of tree for models similar to that. 


Edited by asmodeus812, Today, 12:17 AM.






PARTNERS