I want to just update the area which is going to be affected.
Say an agent is moving into an area, where he leaves, may be merged,
and where he lands on, will be subdivided.
The algorithm I am coming up now needs to update the tile id very quickly and
re-sort all the id all over again which is very time consuming.
Are there any good examples on how to quickly update a quadtree?
Thanks
Jack
What is the best way to update a Quadtree/Octree?
Author
You could use a 1D or 2D hash for the lowest level of detail and index a cache in which you've allocated you QT/OT nodes directly.
Not only does maintaining a semi-duplicate linear data structure (for each level) help with simple updates, it is much more ergonomic in terms of memory management and most updates/neighbor lookups are bound to be MUCH more cache friendly.
Personally I feel like linear grids are almost always the way to go. If you do need coarse control, it makes more sense to mentally adjust how you think about a quadtree and treat it as a set of tiered linear arrays instead.
Not only does maintaining a semi-duplicate linear data structure (for each level) help with simple updates, it is much more ergonomic in terms of memory management and most updates/neighbor lookups are bound to be MUCH more cache friendly.
Personally I feel like linear grids are almost always the way to go. If you do need coarse control, it makes more sense to mentally adjust how you think about a quadtree and treat it as a set of tiered linear arrays instead.
I believe rebuilding the entire Octree could prove faster then splitting/merging it's child nodes.
void MyEngine::Update()
{
m_WorldOSP->Clear();
for (int e = 0; e < getSceneEntityCount(); e ++) {
setEntityOctant(e, m_WorldOSP->Insert(getEntityBBox(e)));
}
}
Author
This guy is doing it well..... pity is didn't know how he did it...
To Christian:
I also tried to refresh the whole quadtree in realtime,
But as you know :), it is just too heavy operation...
The whole application grind to a halt.
Assuming each child has a reference to its parent, and each quad has a count of how many items it contains (cached for its children):
When an item leaves a quad subtract one from the quad's count, and request the quad's parent to check if it should merge (if the sum of all children's count is less than threshold). If it did merge the merged quad should again request its parent to check for merge, etc.
Likewise when en item enters a quad you just check if the node should split, if it did split, you check the new quad (the one you entered, not the other three) if it also needs to split, etc.
If moving one node from one quad to the other you should do the enter first, to avoid current quad and new quad being first merged and then split, if they have the same parent.
This is assuming each quad has a reference to its parent and all its children, not using some array to store quads in. If you do want to store quads in an array, to prevent garbage collection, you could have a stack with unused indexes in the array, so you don't ever need to move items in the array. If your children in the quadtree takes too long to sort through when merging or splitting a quad, you should use a smaller threshold.
Author
One more tiny question to ask,
I am wondering if say a tractor of a truck enters a warehouse,
and the floor of the tractor becomes part of the world,
the quad tree is to be extended, I don't really want to extrude
that part of the quad tree in advance and pretend it was there before the truck enters,
I want the new area to be stitched to the original quad tree.
The problem being is where should I seed the pivot point
of the new quads?
BTW, I decided not to store the ids in an array, I store them in a hash map
Anyways, the ids can be reused when required...
Thanks
Jack
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
