This topic is 3301 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Im looking into implementing a quad tree for my rendering. Where the camera frustum will be tested against the first node, and if an interesection occurs, it draws the objects linked to that node, and the does the same recurring process for that nodes 4 children. I have a few questions though. From my understanding, the general idea is to limit the amount of objects a single node can have. When the limit for a node is reached, you then divide the nodes space by 4 and instead add the new item to one of the 4 children depending on its location.
const UINT MAX_OBJECTS_PER_NODE = 8;
{
GameObjects  *m_Objects[MAX_OBJECTS_PER_NODE];
};


But what happens when the first nodes object list has become full, ie it has 8 objects, and the newly item to be added is too big to go into one of its children?

##### Share on other sites
Don't have a real max-size, but a preferred one. Use a dynamic vector to allow for any number of objects.
Also, don't store small objects in the large node at all. If you reach more than the max number of objects, and subdivide the node into 4 children, remove all the objects and re-add them, storing them in the children instead. This way they can be culled away.
Then when you draw, you can often do a check 'if the whole node is visible', and if that is true, draw all of its children without any more visibility checks. The same way, if the whole node is outside the view, don't check the children at all. Only if it's partly visible do you need to check the children, which can let you get away with drawing only a few of them. Storing objects higher up in the tree doesn't make sense, since it doesn't allow as aggressive culling. For large objects that doesn't fit it would make sense though, as you say.

##### Share on other sites
I don't think there's any one satisfactory answer to this, but this is one method you could use:

EDIT: Actually, what my rambling was trying to say is exactly what Erik managed so succinctly, so I'll leave you in his capable (and more literate) hands

[Edited by - webwraith on November 7, 2009 2:25:42 PM]

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633302
• Total Posts
3011275
• ### Who's Online (See full list)

There are no registered users currently online

×