I use quad/octree for outdoor rendering.
But there’s one problem. Many triangles
are shared between nodes of quad/octree.
What to do whitch this triangles ?
Split them by edges of node - not a best way for newest hardware(there’s about 300 000 triangles on terrain) ? Re-render them from ech node (i think it’s too slow) ?
What do you think about this problem ?
How you slove this problem?
My lastest idea - i do not need i quadtree.
Just render all terrain whitchout any visibility ???
Do a search on a technique called “loose octrees”. (I’ve found it in the Game Programming Gems 1).
If you put objects in the biggest bounding box they can fit into, the trick of loose octrees is to enlarge each bounding box by a factor of 2 while maintaining the same centerpoint to get overlapping regions between neighbour boxes. The result is that objects fall more often completely into one or the other bounding box, theirby moving deeper into the tree without splitting them.
ERh… It’s quite simple, just give each tri an index. When u add the triangle to your renderer that index = currentFrameIndex. Before adding a triangle check if the triangle’s index == currentFrameIndex, if so, don’t add it. Increase currentFrameIndex each frame.
That would assume you deal with each triangle individually on a per-frame basis. That’s horrible from a hardware efficiency standpoint, and certainly a bad idea if you have better things for your CPU (and memory subsystem) to be doing while the graphics card is working.
Look for “geomipmapping” for a fast, simple, reasonably good solution to the problem.
Well, this is how I cut out all stuff before doing dirty work in my terrain engine…
I partition my terrain into chunks of size X specified at compile time. This chunks (squares) have stored the coordinates for their corners, the middle point of the square itself, and a radius. Before my mesh is created from these chucnks, I iterate through them, and weed out those chunks that are outside of my viewing frustum with a sphere test passing the mid point and the radius. Right there, I get rid of a ton processing you go through when testing for independent triangles and other types of occlusion tests.
Miguel
[This message has been edited by mancha (edited 03-27-2003).]
It’s more simple.
I’ve deduced than your engine render the same triangle many times when it traverse the octree/quadtree.
For avoid this you must put a marker on each triangle or primitive, just the framecount or a bitset for all primitives.
Before rendering you must clear all the marks.
Then, when you traverse the octtree, check if the mark is on; if not, render the object and set on the mark.
I’m wrong?
Originally posted by leoptimus:
[b]It’s more simple.
I’ve deduced than your engine render the same triangle many times when it traverse the octree/quadtree.
For avoid this you must put a marker on each triangle or primitive, just the framecount or a bitset for all primitives.
Before rendering you must clear all the marks.
Then, when you traverse the octtree, check if the mark is on; if not, render the object and set on the mark.
I’m wrong? [/b]
As jwatte said, that would involve processing all of your triangles each frame.
Another simple cull mechanism with slightly better fit (bit slightly more expensive per-block test) would be to store min, max in each of the X, Y and Z directions, and then test the six frustum planes against each of the 8 corners of the block contained within these corners.
First cull test would be to cull out the block if any one of the six planes have all eight corners on the outside of it (but it has to be the same plane for all 8). This fits relatively tightly, except for diagonal quadrants close to the frustum.
Note that Separating Axes Theorem may be used (google for that to be able to cull out blocks that are diagonal across multiple outside quadrants, but don’t actually intersect the frustum.
Running 48 dot products per block might seem more expensive than 6 (for the bounding sphere) but it’s usually worth it, especially if you have high-detail blocks.
Also, the radius from center to “flat” corners is not enough, because a very tall spike in a corner will fall significantly outside the sphere described by center + “flat” radius.
Running 48 dot products per block might seem more expensive than 6 (for the bounding sphere) but it’s usually worth it, especially if you have high-detail blocks.
True, this why I chose shperes…
Also, the radius from center to “flat” corners is not enough, because a very tall spike in a corner will fall significantly outside the sphere described by center + “flat” radius.
It depends how you compute the radius…
The way I do it by adding the corners with the longest distances from the mid point. Mind you that I take into concideration the height as well, and only the x,z coordinates, so that tall picks will affect the size of the radius…
And the blocks are small enough that they do not contain huge difference in topology.
If you are using quadtrees, or bintrees to “store” your detail, with big blocks you will end up with huge depths in the trees, making it slower to traverse when rendering. So, that is why you want to keep the blocks as small as you can so that you have shallower trees, hence less traversal and more accurate culling.
But, using boxes definately have their use if you want to spend the extra 42 dot products.
[This message has been edited by mancha (edited 03-28-2003).]
to be able to cull out blocks that are diagonal across multiple outside quadrants, but don’t actually intersect the frustum.