Fast update of items

[m0ose]

This is a question about the proper way to handle an object that is moving around in an r-bush. Would one remove the object and add it every time it moves, or is there a more efficient way? In the documentation it said something about deleted items not actually being removed from the list.

[mourner]

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.

[mourner]

I'm thinking of the following simple algorithm:

1. Find the leaf node containing the item.
2. Update the item bbox.
3. If it's still within the leaf node bbox, return.
4. Remove the item.
5. Traverse upwards, find the closest parent node that fully contains the item.
6. Add the item to the parent node with the standard insertion routine.

[IvanSanchez]

1. Add the item to the parent node

Wait, shouldn't you delete the node before adding it again?

[mourner]

Right, updated the comment.

[photonstorm]

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?

[mourner]

@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.

[mourner]

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
});

[photonstorm]

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.

[mourner]

@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.

[photonstorm]

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.

[MaxGraey]

It would be nice to implement this bottom-up approach: http://net.pku.edu.cn/~cuibin/Papers/2003-vldb.pdf

[mourner]

@MaxGraey thanks for sharing, this looks like a good paper on the matter!

[ShimShamSam]

Any further work on this? I'm trying to optimize my broad-phase physics search.

[mreinstein]

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.

[MaxGraey]

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;
}

[thisredone]

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.

[tobinam]

Hi, I have the same use case. I will go ahead using remove() then insert() for now. Thanks for the library, much appreciated!

[VagneV]

De nada e nem o que eu não s, o //. //. 021 021 021 021 ---------- Mensagem encaminhada ---------- De: "tobinam" ***@***.***> Data: 19/04/2021 08:56 Assunto: Re: [mourner/rbush] Fast update of items (#28) Para: "mourner/rbush" ***@***.***> Cc: "Subscribed" ***@***.***>

Hi, I have the same use case. I will go ahead using remove() then

insert() for now. Thanks for the library, much appreciated!

…

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.