Are there any general guidelines for raycasting? How many is too expensive for one update loop?
1 Like
This expensive, if youād want exact answer.
As for general guides - as few as possible? The exact amount depends on devices / performance you aim for, so thereās no one number - just use as many as youād need, and if itās too much, optimise.
4 Likes
I would qualify this, raycasting is not very expensive, but only if youāre willing to make it so. The default three.js implementation is O(n) complex, with n being number of faces in the mesh. You can get it down to O(log(n)) via a spatial index though, which suddenly makes it almost free.
I often run a 100 or so raycasts per frame with no noticeable performance impact. So the answer is - it depends. 
6 Likes
To keep it cheap, try to ensure the bounding box (or sphere) checks are as effective as possible. Raycasting into a single large world mesh with 100K vertices will be expensive, if the ray always intersects the mesh somewhere. Raycasting against 100 meshes with 1K vertices each would be much cheaper, because most of the meshes will be eliminated with a simple bounding box check.
5 Likes
Could you go into the spatial index thing a bit more? Is it like a lookup table in a static scene?
Not quite, it is that too, but more.
hereās the most common type:
If you ever played a game with more than a handful number of objects - you probably witnessed a spatial index being used.
How can you tell where the user clicks in a top-down game? Well, if itās a flat-plane game - thatās easy, but if there is any kind of verticality in the level - it requires ray-casting against level geometry, which can be quite large.
Have you seen how in most modern games characterās feet donāt penetrate the ground and align to the surface? That requires at least 1 ray-cast per foot to achieve, typically 2. Ray-casting is everywhere, and if it was done in a naive way in production - it would not meet the performance budgets of many games. As such, spatial indices are part of most rendering engines as well as most game engines.
When you come to the world of physics - spatial index becomes not only āniceā, but essential, without a spatial index you would basically have to check if each object interacts with each other object in the scene, that would become impractical very quickly and you would have to say goodbye to any kind of simulation with more than 50 objects in it or so.
Special abilities in many games are implemented using spatial queries, like ādamage in square zone over hereā or āapply effect to characters in a cone over thereā. When you have lots of characters and lots of abilities being used - you want to quickly figure out which ones are affected. Same kind of story.
So: spatial indices. Itās spatial indices all the way down. 
5 Likes
thanks for your answers. my head explode now.
5 Likes
An octree can be used to create a spatial index. There are similar techniques like kd trees - the spatial index article on wiki lists a few more variants.
Thereās also bounding volume hierarchy (BVH) which is similar to octree. I think the main difference is that you can choose the number of branches at each level and in BVH the final boxes donāt overlap, while with octree they can. Also, the boxes in a BVH are different sizes, while an octree they are fixed sizes. This means a BVH will probably be more efficient for dividing up complex geometry. However, Iāve seen people recommend using an octree to divide up large scenes consisting of lots of geometry - say, a solar system, and a quadtree for large mostly 2D scenes like an isometric game level. I donāt have enough experience to comment on that, however.
This article goes into the difference between BVH/octree. You can see from the screenshots that BVH ends up with fewer final boxes.
BVH
Octree
@gkjohnson has a BVH implementation here:
Iām not aware of a good octree implementation. There used to be one on the repo but it got removed a few months back due to being unmaintained.
8 Likes
Thatās an interesting article. I donāt suggest to anyone trying to get a spatial index working in their project to read it though. It will likely not answer questions that you have and only make the matter more complex in your mind.
Spatial indices are different, their differences are a lot more complex than this. The implications of choosing one over another also depend largely on your implementation. There is a way to implement octree with 0 overlap, there is a way to implement BVH with a ton of overlap. There are ways to use more memory, ways to use less, ways to build the tree fast, ways to build the tree well. There are just too many variables.
At the end though, if youāre not building a rendering engine - it doesnāt matter. You will see that perhaps instead of taking 10 microseconds on a particular query, your implementation takes 11 microseconds. If you started with 500000 microseconds initially, do you care? The answer should be ānoā.
This is my recommendation as someone who has travelled this path - donāt worry about it, pick something with least amount of pain to include into your project. Chances are - you will be completely satisfied with it.
4 Likes
thanks for taking that much time, makes perfekt sense now!
2 Likes
If anyone is looking for a BVH implementation for three.js, thereās one in most raytracing libraries like https://github.com/hoverinc/ray-tracing-renderer or https://github.com/erichlof/THREE.js-PathTracing-Renderer
I personally use ammo.js for raycasting as the physics engine has a spatial index already.
Hi all
Working with earth representation, I confirm raycasting takes about 1 second for a 1440 x 1440 spherebuffer geometry, this 1440 geometry being not even enough to get very precise position of a place on earth. (building such geometry also takes 0,5 to 1 sec). So I am also searching for a workaround to this issue. Like, for example, dividing the sphere into dozens of sub-spheres of 4 vertices per degree (1440 corresponds to 4 * 360) and then raycastng subsphere. I had to do this division because of the texture tiles : three cannot tile sub-textures on a sphere.
Kind regards,
Raycasting is not the right solution for that ā if the objectās bounding box crosses the ray at all, then a Raycaster will loop over every triangle in the mesh. If you want to know where a ray intersects a sphere, it will be much faster to use Ray.intersectSphere to get the intersection coordinates.
If you need a specific triangle, rather than specific coordinates, then youāll probably need some kind of spatial data structure instead of raycasting.
5 Likes
Thanks, it looks very fine, so I tried it the following way
What worked fine but slowly (mouse is normalized, camera is orthographic, earth is the big mesh of 1440x1440 vertices ) :
function mouseTogxgy (mouse) {
let gx, gy, x, y , gx2, gy2, x2, y2 ;
raycaster.setFromCamera( mouse, camera );
let intersects = raycaster.intersectObject( earth );
if(intersects.length) { // clicked on earth, get the coordinates)
bla bla ok
// So I added just after :
let point2=new THREE.Vector3(0,0,0);
intersects=raycaster.ray.intersectSphere(sphereE,point2);
console.log(āpoint2:ā);
console.log(point2);
It returns correct values for earth objet (but slow)
It returns Nan values for sphereE object
For more complete information, how main objects were built :
const R=3600;
let geometry = new THREE.SphereBufferGeometry( R, 1440, 1440); // async
earth=new THREE.Mesh( geometry, earthmaterial );
ā¦
sphereE = new THREE.Sphere( { radius:R } );
Damned this editor drives me crazy, I sincerely would like to present correctly this postā¦
So now, do you have a clue about the reason why this ray.intersectSphere pushes nan in point2 while its parent raycaster returns good values intersecting with the mesh earth ?
Thanks by advance
You may need to double-check the documentation for intersectSphere. It returns a single Vector3 for the intersection point (or null if no intersection is found), and not an intersects array as the Raycaster would do.
Many thank, @ donmccurdy
Well the syntax was correct, I just did not create the sphere correctly (debug shown a radius of -1 etc)
Solution was simply to create sphere like this :
sphereE = new THREE.Sphere( new THREE.Vector3(0,0,0), R );
and not like this :
sphereE = new THREE.Sphere( { radius:R } );
I have to become a bracket lover or hater ā¦
Now it works perfectly with even better precision. Your help will make me progress to a much faster system : no more need to create a triangles geometry of 1440*1440, Iāll separate for always the sowh part (meshs) and the calculation part (maths).
With best regards,
1 Like
Realize that ābracketsā result in a new object being created every time you call that constructor function, thus itās extra garbage for you garbage collector which will come to collect and cause an FPS hickup at some point down the line. Not using ābracketsā for potentially performance critical parts of the library and for that matter any code you write is just smart choice. Nothing to do with syntax preference here.
Hope that helps. Also, documentation should be your first place to check, then the source code on github and debugger. Sadly weāre not at the point where you can write ādrAw pReTtY piCtUrE pLxā and see the library produce expected result.
That said, a lot of the points in this discussion seem to go off-track. If you want cheap ray-casting, you should probably invest into a spatial index, this would simplify your user-side code significantly. Trying to mess with sphere here, or breaking your models into 1000 pieces manually is equivalent of using a text file instead of a database, reading it line-by-line instead of using any of the numerous SQL and other types of databases on the market. Youāre just inviting bugs and headache, and in the end your solution is probably going to be inferior in terms of performance too.
I have advocated for having spatial index inside three.js in the past, at this point I donāt really care, since there are clear drawbacks to doing that as well as obvious benefits. In my engine I use spatial indices extensively and the projects I work on would be frankly impossible without that.
On the subject of bounding spheres, I would note that bounding spheres in three.js are severely overestimated, bounding sphere is computed from bounding box, which guarantees that the sphere will be an overestimation except the case where your geometry is literally an axis-aligned box. I use an alternative mechanism for computing bounding spheres that results in spheres with roughly 50% or smaller volume compared to those created with three.js.