I was doing some optimization work on my engine recently and remembered various points being made about ray casting performance here on discourse as well as on GitHub, so I decided to share some numbers from an actual real-world usecase. Goal is to give you some perspective on what you can expect from a JS spatial index.
A decently implemented spatial index has fairly low impact on overall frame time in my experience. Here are some numbers for those who might be interested:
For clarity: traverseFrustumIntersections is a method used for extracting just about everything that’s within a frustum, such as checking if animated models should be animating or if they can be put to sleep, or particle emitters etc. as well as replacing Three.js frustum culling. As you can see with all the usage it amounts to only about 3% of the overall frame timing, that’s being written with a visitor pattern, if you write that in a dumber way - it could be a fair bit faster still. The dataset in question is my game, here’s the scene:
there are total of ~15,000 objects in the tree, so it’s not super huge.
I use another instance of that index just for representing terrain polygons, that’s just under ~ 200,000 polygons and doing a ray test every frame (from mouse pointer) amounts to being barely registered in the profile:
as you can see, it comes in with about 0.02% frame cost, which is practically nothing, you could do 50 of those casts and it would barely make a dent in your budget at ~1%. Again, it’s visitor based, so doing a dumb, array-filling, implementation would be a fair bit faster.
That profile is ~10s worth of recording, frustum testing amounted to total of 149ms. If 10s has 6000 frames, that’s around 25 microseconds per frame on frustum testing or 0.023ms. There are a few of those tests done each frame in different parts of the engine, such as animation system, rendering, particles.
For purposes of completeness, my index is BVH binary AABB tree. Here are signatures of 2 methods mentioned above:
/**
*
* @param {number} startX
* @param {number} startY
* @param {number} startZ
* @param {number} directionX
* @param {number} directionY
* @param {number} directionZ
* @param {function(node:LeafNode)} visitor
*/
BinaryNode.prototype.traverseRayLeafIntersections = function (startX, startY, startZ, directionX, directionY, directionZ, visitor) {
...
};
/**
*
* @param {Frustum[]} frustums Collection of THREE.js Frustums
* @param {function(node:LeafNode, boolean)} visitor
* @returns {number}
*/
BinaryNode.prototype.threeTraverseFrustumsIntersections = function (frustums, visitor) {
...
};
I’m curious to find out what are others’ experiences with spatial indices in terms of performance, am I the only one for whom it’s a non-issue? I’m struggling to come up with good practical examples where you would need more than a handful of rays per frame/simulation tick. 
