search

rossborchers / UnityBoundingVolumeHeirachy

Unity Bounding Volume Heirachy (BVH)
Apache License 2.0
119 stars 12 forks source link

Rebalancing the tree #1

Open EmmetOT opened 2 years ago

EmmetOT commented 2 years ago

Hety, I have a quick question about this - when objects move around, I call the 'MarkForUpdate' function for each of them and the 'Optimize' function once per frame. However, this only seems to affect the size of each cell. The tree never seems to change its structure, for example, if two objects start far apart but move closer together, I would expect the tree to change so that they share a common parent node.

The closest I can get to this behaviour is by removing and re-adding any changed nodes every time, but it's very unstable and obviously not optimal.

Is there any way to do this with the current implementation? Or maybe I've just misunderstood the purpose of a BVH in general?

zhanglingfeng911 commented 2 years ago

how use this code? can u give a example?

rossborchers commented 2 years ago

Hey @EmmetOT So the main addition I added to this was integrating GameObjects and some premade traversal tests via BVHHelper.

The underlying algorithm has not been changed from the original implementation. I can only guess that the heuristic determined it was not necessary to optimize the tree in this case.

The algorithm uses something called tree rotations, which swap out grandchildren and children nodes. So I don't think it works exactly as a naive BVH would operate. image http://www.sci.utah.edu/~thiago/papers/rotations.pdf

How did you test this? If it is not doing what the paper describes I'd really like to know - as I built upon the previous implementation in good faith. Its worked for my use case - but maybe not for all.