collision-rs takes 6 seconds to create a DBVT with 16,000 entries

[KeyboardDanni]

Using collision crate 0.20.1

I just started integrating this crate into my game engine for accelerating collision detection, and I noticed that building the initial tree seems to be taking a very long time. I am trying to create 16,000 collidable objects, which seems to be taking about 6 seconds. I would expect 100ms, or maybe even 600ms, but 6 seconds is too long.

Building with [profile.dev] opt-level = 2. Callgrind reports that 99% of time is spent in DynamicBoundingVolumeTree::tick(), and 96% of that time is spent doing a memcpy (specifically __memcpy_avx_unaligned_erms).

You can find the source of my current attempt here: https://gitlab.com/cosmicchipsocket/keeshond/-/blob/master/keeshond_treats/src/collision.rs

Am I using the library wrong? Or is DBVT not a good match for what I want to do? And why is it doing so many copies? I don't think my CollisionLeaf struct is particularly heavy - it's an Entity (which has a usize and u64), and two Aabb<f64>s.

Thanks in advance!

[KeyboardDanni]

I would like to add that all the collidable objects I am creating are lined up in a grid, spaced 16px apart, so there shouldn't be any overlapping bounding boxes. Why does it take so long then?

[KeyboardDanni]

An update on this: I looked in this crate's DBVT bench, and it's calling tick() after every insert(). I went ahead and did this and found that the initial tree build was much faster, and only took maybe 100ms. Worst case scenario with giving all the objects the exact same bounding box, and it only took 1-2 seconds, which is still faster than the 6 seconds I had previously (and honestly I don't mind this worst case. After all, what is a collision algorithm supposed to even do in such a case?).

But I was also under the initial impression that tick() should be called as infrequently as possible, beyond the required "once per frame". Seems like that's not the case here, and having it maintain the tree between each insert is actually much faster than doing all the inserts at once. This seems like a rather counter-intuitive API to me, but it should probably be documented. Right now the docs only mention how you will need to call do_refit() once after all modifications to the tree for a given frame.

I'm also curious about how update() and do_refit() are separate functions, since I know they are grouped together in tick() for convenience. Is there any particular scenario where you would want to call one and not the other?