Comments (18)
I'm thinking of two potential new methods for this:
// we're passing a function because we need to do some work both before and after the update
tree.update(item, function (item) {
// change item's bbox
});
// iterates through all items — e.g. useful when you update everything once per frame
tree.updateAll(function (item) {
// change item's bbox
});
from rbush.
If you don't mind I've got a further question relating to this - what would you recommend if all of the items are moving? (for example a typical game) - in most games the total quantity of items is lower, but they generally all move every frame. Is it better to just create a brand new tree each frame and bulk insert everything, or would you still advise some kind of search and move sweep?
from rbush.
Removing and adding again is fine. There's probably an algorithm for fast move in case the item isn't moving too much at once (such as when doing continuous movement) — could be a nice optimization to think about for future.
The docs says that nodes are not reorganized when the number of items drop below threshold, but in practice this doesn't affect tree efficiency much.
from rbush.
I'm thinking of the following simple algorithm:
- Find the leaf node containing the item.
- Update the item bbox.
- If it's still within the leaf node bbox, return.
- Remove the item.
- Traverse upwards, find the closest parent node that fully contains the item.
- Add the item to the parent node with the standard insertion routine.
from rbush.
- Add the item to the parent node
Wait, shouldn't you delete the node before adding it again?
from rbush.
Right, updated the comment.
from rbush.
@photonstorm that probably depends on how much the points move, but my bet is that specialized algorithm would be faster, since most of the points won't move out from their node bbox.
from rbush.
I wonder if there might be another potential way of handling updates: some kind of dirty
flag on the node. For example, from my perspective, I would have a game-level object (i.e. a Sprite), that had a bbox property - which was the object inserted into the tree.
If the Sprite moved during play, then it'd be handy to either just call tree.update
, passing in the updated item, or even better, flag the item as dirty
somehow - and then at a point suitable to the game, call tree.updateDirty
and have it sweep all dirty nodes and updated the min / max values.
Of course I fully appreciate that rbush wasn't built with games in mind at all, and this may be bending it to try and do something it was never meant to. However if you think it'd work, and be fast enough, this could be an awesome solution for things like camera culling, or a broad phase sweep for further physics checks.
from rbush.
@photonstorm on a second thought, global tree.update()
could work without dirty flags — we can just go through every item in the tree with iterative depth-first search and match each item's bbox against its parent, and reinsert it from the first fully containing grand-parent if it doesn't match. Could this be fast enough?
I also wonder how RBush performs in your case if you just manually remove
- update
- insert
.
from rbush.
I don't know if it would be fast enough, but I'm happy to make some tests to find out. I guess the issue will be not so much 'is it fast', but 'could it be better?' :)
By way of comparison we currently empty and re-populate our quad tree every single frame, which isn't ideal, but works. However our quadtree is limited to physics entities only, where-as I was hoping this would be fast enough to use for culling as well, an action that impacts every object in the game, not just those with physics.
from rbush.
It would be nice to implement this bottom-up approach: http://net.pku.edu.cn/~cuibin/Papers/2003-vldb.pdf
from rbush.
@MaxGraey thanks for sharing, this looks like a good paper on the matter!
from rbush.
Any further work on this? I'm trying to optimize my broad-phase physics search.
from rbush.
Any further work on this? I'm trying to optimize my broad-phase physics search
I'm in the same situation, would find an efficient update mechanism very helpful.
from rbush.
I'm using this approach, but I'm not happy with it performance
public update(item: RNode, bounds: BBox): this {
const parent: RNode = item.parentNode;
if (
bounds.minX < parent.minX || bounds.maxX > parent.maxX ||
bounds.minY < parent.minY || bounds.maxY > parent.maxY
) {
this.remove(item);
item.minX = bounds.minX;
item.maxX = bounds.maxX;
item.minY = bounds.minY;
item.maxY = bounds.maxY;
this.insert(item);
} else {
item.minX = bounds.minX;
item.maxX = bounds.maxX;
item.minY = bounds.minY;
item.maxY = bounds.maxY;
}
return this;
}
from rbush.
I noticed that when you add references to parent nodes (like above) then you can greatly simplify the implementation of remove()
thus making remove()
and insert()
strategy of updating items very viable. Checking if the element perhaps still fits in the parent AABB reduced the amount of operations required significantly - based on my simulation of a game-like environment where part of the AABB's is constantly on the move. The majority of small updates didn't need to perform the reinsertion.
There's also the possibility of enlarging the AABB slightly and when that fails checking the siblings like described in the "bottom-up approach" paper.
There's also quite an interesting talk at GDC Vault: R-Trees -- Adapting out-of-core techniques to modern memory architectures. The guy pitches the idea that we don't necessarily have to reinsert. We can just keep enlarging the AABB and the topology stays valid. Then we either reinsert every now and then - maybe based on how much the object has moved - or implement an incremental refinement algorithm which optimizes the tree little by little.
from rbush.
Hi, I have the same use case. I will go ahead using remove() then insert() for now. Thanks for the library, much appreciated!
from rbush.
from rbush.
Related Issues (20)
- Can you provide a browserify distribution? HOT 1
- How to limit the result count from the query? HOT 11
- how to search by id ? HOT 2
- tree.getById(id) how to get by id? HOT 2
- Why "RTree" is geographically even distribution while "RBush" is NOT? HOT 1
- About evenly geographic distribution when limit the result size HOT 2
- Invalid collision on maxX/Y (pixel-perfect collision false positive) HOT 3
- Does RBUSH supports to use Latitude and Longitude? HOT 5
- Hi i can't figure out how to use this library can anyone help? HOT 3
- Typescript attempts to use missing default constructor HOT 4
- How to search when usiong the extended class for points
- is there any quick way to return the bounding box of tree itself? HOT 1
- Questions: Performance Remove + Moving item HOT 1
- Definition of "intersection" could be made more explicit in the readme HOT 2
- Returns all items when bounds provided to search contains center 0,0 HOT 3
- Support esm
- search & collides support custom intersects & contains
- Balancing? HOT 1
- Unable to resolve dependency tree
- Performance benchmark vs other libraries HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rbush.