Well, just for the fun of it i started to implement a simple quadtree into a little project of mine. Just to maybe speed up rendering and have at least some sort of culling for maps as they are made as basicly one huge mesh. But then there is the situation that triangles will cross borders of the childnodes if a node has to be splitted.

Pushing them into the parent node would be easier, but that means that there is the potential to draw more nodes than possible because of well, crossing triangles.
Then if they would get split so that i only have to render leaf nodes, means i get quite some more triangles to render.
As for now the quadtree will only be used for rendering so each triangle in the hughe mesh should only be present one time(to avoid possible overdraw/double rendering of triangles)

Now what i'm asking or where i need some input is, is it better to push the triangles which are in more than one childnode into the parent node or split them at the boundary, resuling in more triangles but they will only be in leaf nodes ?

regards Ryokeen

8 hours ago, Ryokeen said:

Now what i'm asking or where i need some input is, is it better to push the triangles which are in more than one childnode into the parent node or split them at the boundary, resuling in more triangles but they will only be in leaf nodes ?

Depends, but often a loose quadtree is best option.

Here you extend the bound of each node by one half, and you sort in the triangles in the lowest possible node that can bound it.

So you have large triangles near the root and small triangles near the leafs but all nodes have content.

There is no need to split any triangle, but the extruded bounds means more (neighboring) nodes to check.

Alternatively put the triangle in multiple nodes.

1 hour ago, David Lovegrove said:

Alternatively put the triangle in multiple nodes.

That is out of question, every triange should only be in one node max, as if it is in 2 childnodes from the same parent, it would get drawn multiple times(and since i don't know if a triangle ends up transparent or not at tree creation time, that is an issue).

About loose octrees..yeah that is something i could try out, guess i'll have to measure what is faster, drawing more nodes because of triangles covering multiple child nodes, or splitting them and get more smaller triangles but less nodes and less drawcalls.

What sort of mesh are you wanting to render that requires putting the triangles into a quad tree to increase performance?

How big is it in the world and how many triangles does it have?

What's the maximum triangles you are having for your leaf nodes?

These days for hobbyist stuff you may as well just draw the whole model in most cases and use a bounding volume hierarchy to cull whole objects.

It's far simpler and gets you most of the way there.

BVH might be better in any case. My experience is MBVH > loose octree > octree in general. I'd use octrees mainly on grid aligned geometry.

1 hour ago, David Lovegrove said:

What sort of mesh are you wanting to render that requires putting the triangles into a quad tree to increase performance?

How big is it in the world and how many triangles does it have?

What's the maximum triangles you are having for your leaf nodes?

These days for hobbyist stuff you may as well just draw the whole model in most cases and use a bounding volume hierarchy to cull whole objects.

It's far simpler and gets you most of the way there.

That is one problem, due to the whole map/level being one fbx file/mesh i can't rly cull whole objects. The instanced ones ok, but the rest of the map..is basicly one object.
Atm it's in the range of approx 1million triangles, but since i render serveral passes(shadowmap, gbuffer, env cubemaps and some others) speeding up the rendering might be a good idea. And since that game is atm quite gpu bound..i wanted to give it a go.
Sure one could say i can cull by material/submesh, but..they are like all over the place so computing bounding geometry is a pain and won't give me much.

The reason why i was looking into a quadtree is, the maps are quite flat, players can run and fly and i have one big mesh without actual seperate objects i could cull. And it's just the map itself, stuff like vegetation, ocean and dynamic objects allready use some sort of culling scheme.

BVH..need to look into that, havn't done much with partition algorithms

Maybe i'm wrong but my main concern with not splitting triangles is this: The map can have quite big triangles and sometimes quite a lot of them. So if i have a collection of triangles in a bounding volume that might result in the case that the bounding volume gets quite big..collecting more triangles in it.
Then if one node is visible but it's neightbour is not..and the big triangles go through both of them i need to render them if one of the nodes is visible, but doesn't want to render the triangle twice if both are visible. So where to put it ? In the parent node ? works but means i draw a lot more nodes

2 hours ago, Ryokeen said:

So where to put it ? In the parent node ? works but means i draw a lot more nodes

With a quad tree (or MBVH with 4 children) the node count increases by 1/3th.

You could also use a multi level grid with similar extended bounds than loose quadtree to avoid splitting or sharing triangles. This way you would see where you get with less work.

I assume you do not want to cull individual triangles. You likely want to make clusters by stopping further subdivision at some number. This is an opportunity to do something better: You could cluster nearby triangles with similar normals. This allows also efficient backface culling using the resulting cone bounding the normals. Those clusters could then form the input to your hierarchy generation, or maybe just brute force culling the clusters binned to a single coarse grid is good enough.