- Home /
Collapsing Nodes in Quad Tree LOD System
I have a quad tree system set up where I have a root node that has four children and those children have children, etc. like any other quad tree, but the quad tree set up also mirrors what I have in my scene's hierarchy in that each quad tree node represents an actual game object. Fairly simple. Basically what I am working on is a terrain level of detail system that subdivides nodes once the camera breaks a distance threshold, getting nearer to the terrain quad, and collapse the nodes, while breaking the threshold going in the other direction. So far I got the subdivision part down and it works very well but I can't for the life of me figure out how to recursively collapse the nodes. I won't post my code here because unless I post almost my entire project so far, it won't make much sense, but I'll explain how it works in as much detail as possible.
I have a "node" class which stores various data, most importantly the children of it and the gameObject it is attached to. These nodes are stored in a root array as the terrain consists of multiple trees. The children are stored in a list, this way the code can check the count of the list to determine if the node is a leaf node or not.
I also store all of the nodes in a separate list that can be linearly iterated through to call functions on the nodes that update distances.
After the distances are updated then the root array is iterated through to determine if a distance threshold has been broken on that node. Simultaneously another function begins recursively iterating through the children of the roots. The recursive function basically starts with the root, adds it to a tempNode list then checks its children and determines if any of them need subdividing. If so then it will be subdivided and then added to a tempNode2 list. If not then it is simply ignored. Once the children of all of the nodes in the tempNode list are checked then the tempNode2 list becomes the tempNode list and the function is called again.
In the subdivide function all that happens is the actual terrain mesh is subdivided then split into four separate objects which become that node's children and gameObject's children. The parent node's mesh is disabled along with it's collider. The node class also has a boolean that stores whether or not it has been subdivided. This boolean is set to true when a node is subdivided.
After I got all of this working it occurred to me that collapsing nodes would be trivial and just using the same recursive function, but instead checking if the threshold was being broken in the other direction. However, I have had no success. On that note I do have a function that can collapse a single node just by deactivating its children's meshes and colliders and reactivating its own, that does work as long as all of the node's children are leaf nodes. I figured that I would just check all of the nodes and if I broke the threshold in the other direction then I would just need to iterate through all of the descendant nodes and start collapsing from the leaves up until the node that initially needed collapsing. All of my attempts at doing this have failed miserably.
I also tried simply deleting all of the descendants but this also didn't work and also needs some sort of recursive function to do it. Ideally I would be able to have the meshes and colliders stored already whenever the code has to display them again. Anyone know how I can write a function that recursively collapse nodes?
Is a description of my problem sufficient or should I post my code as well?
Your answer
Follow this Question
Related Questions
Distant terrain level of detail question. 0 Answers
Low FPS any ideas ? 1 Answer
How to control Terrain Texture Blur at Distance (pics) 1 Answer
Spherical Terraing LOD 0 Answers
Reduce terrain verts 1 Answer