This library helps to find nearby objects in constant time O(1) instead of naive approaches that run on O(n) thanks to a binning algorithm. Ideal for collision tests (do not perform test on every object but only check with nearby objects), physics engines and AI engines (for steering behaviours such as obstacle avoidance)
I hope you find it useful! I’ve been using that algorithm in my engine ROYGBIV for a long time and am very satisfied with the results : )
In the repo there’s a performance test for 1M objects, it takes 1.3 ms to find the closest object to the point (0, 0, 0). Feel free to check it out/play with it : )
Very interesting indeed.
I’m still curious if I may ask. Do you need any processing time to create any cache to prepare the binning ?
Does this handle the case where objects dynamically change position, or do you have to run any other computation to update the binning algo each time ?
This reminds me of the ANN = Approximate Nearest Neighbor algorithm
It also runs well for dynamic scenes, with minimal GC activity. I’m using some three dimensional Map to hold object representations. The first implementation was done with JS Object, then I switched to Maps, which for some reason made it much faster. So you may insert/delete objects on the run.
For instance, in this demo the cubes are being updated in the Nearby world as you shoot them.
Thanks for the hint about maps and objects, I can believe that, lot of articles comment on that. After all when it comes to large scale performance where development cost doesn’t matter, I start to see lots of wasm projects out there.
Thanks for sharing a useful tool with the community.
Unless I’m forgetting my algorithmic complexity knowledge, O(1) is constant complexity. Your table on the repo doesn’t reflect that, it reflects some kind of O(log(n)) complexity perhaps.
I mean, if you solve the spatial locality search problem like that - i think it would be awesome.
If you split the whole space into small boxes (bins), then unless you assume uniform distribution as well as constant relationtionship between number of boxes and number of objects - your O(1) claim is… a bit off
I’m all for new things and for trying out various approaches. Though.
About GC, my engine meep is super GC-aware, and the spatial index in there has 0 GC overhead, not “little” but 0, when it comes to moving things around.
You make claims that put work of others in the negative light. Personally, I don’t think that my spatial index is overall better than yours, they serve different purposes and have their advantages and disadvantages. I like your stuff, and I hope this doesn’t come off as overly negative.
The benchmarking is performed on “finding the closest object”, which is not what Nearby does.
Nearby finds nearby objects (objects within given radius) in constant time -> just a hash lookup. Since it’s open source, you can have a look at here. I indeed split the scene into uniform bins, that’s why the users specify world limit and bin size when they construct a Nearby world. The bin size also defines what is considered “nearby”.
The benchmarking does not represent the constant time, since after finding the nearby objects, you still need to iterate over them to find the closest one.
You claim that my claims put work of others in negative light. I don’t see how that’s possible. I don’t know about your work, I’ve never mentioned about other works in my README.md, or in this thread. I don’t claim it is better than others. I’ve never in fact talked about any other library. I implemented this lightweight library, I released demos and benchmarking that demonstrate its capabilities.
I feel it’s a bit missleading. If you have a collections of points in 1d, say:
1,2,3,4,5,6
and you split them into bins of size 10. Then ask the question "give me points in the closest bin to coordinate 5.3. Well, technically - it will be correct that you can just return the bin contents, and as long as you don’t do any copying or allocation for each object - it would be O(1). However, I question usefulness of such a system.
What you have created is not O(1) as soon as you started copying contents from the bin to query result.
When you say “hash lookup”, you’re also “technically” correct, in the sense that you use a Map object as a 3-d bin container and you “hash” each coordinate axis of the query. Correct term here is “fingerprint”, because hash is assumed to be constant size and allows collisions, but that’s also just an aside. The important part is - “Map” is not necessarily implemented as a “Hash Map”, which means that your “Map.get” may or may not be O(1). Incidentally, hash map is O(1) in best-case scenario, which assumes no collisions, in the worst case where all hashes collide it devolves into O(n).
Hope that’s useful.
By the way, this line here creates a new iterator.
That’s potentially… what, like 3*3*3 = 27 iterators per query? All of which are going to be garbage once you exit the function.
A tree needs to be reconstructed in that case, which triggers GC activity
If you had qualified and said “some game engines” - that would be true, sure. But you didn’t.
A tree does not, in fact, need to be reconstructed for all of the operations. You can have an expanded octree down to a certain level that would basically be a hierarchical binning structure, just like yours, except it permits object sizes greater than the bottom-level bin size. Such an approach requires no reconstruction.
If a tree does need to be reconstructed, based on your chosen implementation - you could always use a custom memory management scheme, such as an object pool, in which case you can avoid GC altogether.
So, let’s say I use an Octree in my work. Your statements say that my work is deficient in pretty serious ways, which is not necessarily true. You did not say “engine X is bad”, but you said “technology Y is deficient”, if engine X uses Y, by proxy it has a deficiency in that.
The library is lightweight, and I do think that it is pretty neat.
The inner for loops you pointed out does not make the algorithm non-O(1) since BIN_SIZE there is constant and in terms of complexity it’s negligable. As you can imagine, each loop runs 3 times, since it starts from -BIN_SIZE and goes till BIN_SIZE, increasing BIN_SIZE each time. Usually when we talk in terms of complexity, n refers the size of the data set. Since the execution time of this algorithm do not depend on the data set, it is constant time -> O(1) (it finds nearby objects in X ms. no matter if your world contains 1M objects or 100 objects, or the difference is negligable in terms of complexity).
I’m not sure if res.keys() create a new object, I don’t develop browsers myself. It could be that it returns an already created iterator too (or a cached one?). Thanks for pointing this out though. I also stated minimum amount of GC activity, not 0 GC. As declaring an integer could also trigger GC activity. 0 GC activity is quite a strong statement, and I have no internal browser knowledge to back that up. I can only guarentee the library reuses as much as it can.
I’m aware the worst case&best case implementations of a Map. However I’ll stick with the term O(1) here as benchmarking proves so. It’s browsers responsibility to come up with smart hashing algorithms.
Thanks for stating it’s neat! Maybe fix the README with a PR then : ) I’m open to contributions.
Good luck.
PS: map.keys() === map.keys() returns false, so it probably does not return a reusable iterator. Thanks again for pointing that out. Maybe I’ll improve that in the future.
Hi there! I’m bumping this to know if there is any chance to apply rotation to the bounding boxes of the objects to collide? Right now I have the boxes like this ( they are the orange boxes, while the white ones are the actual Three meshes):
How can I apply rotation? On the createBox method there is no rotation parameter but I have seen that you have rotation applied to some objects in your demos like this one: blaster?
Is there anything that I’m missing with this library?
Since this was brought up to the surface a little while ago. I thought that the benchmark was interesting, so I copied that benchmark for myself to see how well BVH implementation I use works with respect to this type of a query.
Here are the results:
1,000,000 queries in 1515ms.
or 1 query taking up ~1.51µs
It’s a fun coincidence that the actual numeric value is close to what @oguzeroglu , even if the scale is different.
Micro-benchmarks are not super-accurate, but it’s interesting to have a rough performance figure for such things. Thanks again @oguzeroglu for sharing your benchmark code.
In the spirit of sharing, here’s my adapted benchmark, using jest
test("performance, 1M random boxes, 1M queries", () => {
const random = seededRandom(1);
const bvh = new BVH();
const min_bound = -1000;
const max_bound = 1000;
const OBJECT_COUNT = 1000000;
for (let i = 0; i < OBJECT_COUNT; i++) {
const node = bvh.allocate_node();
const x = randomFloatBetween(random, min_bound, max_bound);
const y = randomFloatBetween(random, min_bound, max_bound);
const z = randomFloatBetween(random, min_bound, max_bound);
bvh.node_set_aabb_primitive(
node,
x - 25, y - 25, z - 25,
x + 25, y + 25, z + 25
);
}
const SAMPLE_POINT_COUNT = 1000000;
const sample_points = new Float32Array(SAMPLE_POINT_COUNT * 3)
for (let i = 0; i < SAMPLE_POINT_COUNT; i++) {
const i3 = i * 3;
sample_points[i3] = randomFloatBetween(random, min_bound, max_bound);
sample_points[i3 + 1] = randomFloatBetween(random, min_bound, max_bound);
sample_points[i3 + 2] = randomFloatBetween(random, min_bound, max_bound);
}
const t0 = performance.now();
for (let i = 0; i < SAMPLE_POINT_COUNT; i++) {
const i3 = i * 3;
const x = sample_points[i3];
const y = sample_points[i3 + 1];
const z = sample_points[i3 + 2];
const node = bvh_query_user_data_nearest_to_point(
bvh, x, y, z
);
}
const t1 = performance.now();
const duration = (t1 - t0) / max_bound;
console.log(`${duration / SAMPLE_POINT_COUNT}s/query`);
});
notable changes are:
using multiple queries to get a more accurate amortized result
using seeded random to make the test stable (same random numbers for each run)
Hi, it’s been couple of years since I’ve worked on this library but I can still help you out with this. The thing is that the bounding box concept used in this library is inherently rotation-less. You can still use this library to find the potential nearby objects and run your custom intersection detection function (considering the quaternions/rotations) only on the nearby objects. So this library is not an intersection detection library but a tool to help you find the nearby objects so that you’ll have much less objects to check for intersection. Hope this helps!
Hi @oguzeroglu .I ended up figuring this out and all I needed is use the OBB class from native Three.js instead. Thanks a lot for your detailed response!
In case anyone is curious, I ran the same benchmark with a linear scan. That is - instead of using a “clever” data structure, I dump boxes into a single massive array and just loop over every element when searching for the closest element.
The result is a little surprising to me. On my machine it takes ~12.4ms per query. That is, if you just loop over all elements you’re about 10 times slower than if you use a Nearby.
Make of that what you will, but to me it suggests that if you have less than, say, 10,000 elements - it’s probably not worth introducing a fancy data structure for any kind of search and just brute-force it instead.
Re-running the same benchmark with 10,000 objects, query time is ~0.12ms, so pretty decent.
Benchmark code
test('naive search, 1m random boxes, 10k queries', () => {
const random = seededRandom(1);
const OBJECT_COUNT = 1000000;
const boxes = new Float32Array(OBJECT_COUNT * 6);
const min_bound = -1000;
const max_bound = 1000;
const extents = 25;
for (let i = 0; i < OBJECT_COUNT; i++) {
const address = i * 6;
const x = randomFloatBetween(random, min_bound, max_bound);
const y = randomFloatBetween(random, min_bound, max_bound);
const z = randomFloatBetween(random, min_bound, max_bound);
boxes[address] = x - extents;
boxes[address + 1] = y - extents;
boxes[address + 2] = z - extents;
boxes[address + 3] = x + extents;
boxes[address + 4] = y + extents;
boxes[address + 5] = z + extents;
}
function naive_query(boxes, count, x, y, z) {
let best_distance_sqr = Infinity;
let best_index = 0;
const limit = count * 6;
for (let i = 0; i < limit; i += 6) {
const distance_sqr = aabb3_unsigned_distance_sqr_to_point(
boxes[i], boxes[i + 1], boxes[i + 2],
boxes[i + 3], boxes[i + 4], boxes[i + 5],
x, y, z
)
if (distance_sqr < best_distance_sqr) {
best_index = i;
best_distance_sqr = distance_sqr;
}
}
return best_index;
}
const SAMPLE_POINT_COUNT = 10000;
const t0 = performance.now();
for (let i = 0; i < SAMPLE_POINT_COUNT; i++) {
const x = randomFloatBetween(random, min_bound, max_bound);
const y = randomFloatBetween(random, min_bound, max_bound);
const z = randomFloatBetween(random, min_bound, max_bound);
naive_query(boxes,OBJECT_COUNT,x,y,z);
}
const t1 = performance.now();
const duration = (t1 - t0);
console.log(`${duration / SAMPLE_POINT_COUNT}ms/query`);
});
My belief is that with these pretty large data sets, memory access is what slows everything down, that is - the CPU spends most of the time just waiting for data to be loaded.
Even in that toy naive implementation, object bounds storage, the Float32Array requires 1,000,000*6*4 bytes, or ~24Mb, that’s more than what most CPU caches can hold. Especially on mobile.
