201909 - a look into threejs raycaster

201909 - a look into threejs raycaster.md

A look into threejs raycaster

I've been looking at the current master source code, not a specific version : github commit b3ce68b4 on sept. 2019.

The source code is located in src/core/Raycaster.js, and the doc is online.

A Raycaster instance is constructed given a ray (origin point + direction vector) and a range on this ray (near, far distances), and offers the following API :

• intersectObject( object, recursive, optionalTarget ) : Array
• intersectObjects( objectsArray, recursive, optionalTarget ) : Array

The doc is fairly explicit :

• recursive — If true, it also checks all descendants. Otherwise it only checks intersection with the object. Default is false.
• optionalTarget — (optional) target to set the result. Otherwise a new Array is instantiated. If set, you must clear this array prior to each call (i.e., array.length = 0;).

Checks all intersection between the ray and the object with or without the descendants. Intersections are returned sorted by distance, closest first. An array of intersections is returned...

[ { distance, point, face, faceIndex, object }, ... ]

• distance – distance between the origin of the ray and the intersection
• point – point of intersection, in world coordinates
• face – intersected face
• faceIndex – index of the intersected face
• object – the intersected object
• uv - U,V coordinates at point of intersection
• uv2 - Second set of U,V coordinates at point of intersection

Raycaster delegates to the raycast method of the passed object, when evaluating whether the ray intersects the object or not. This allows meshes to respond differently to ray casting than lines and pointclouds.

Note that for meshes, faces must be pointed towards the origin of the ray in order to be detected; intersections of the ray passing through the back of a face will not be detected. To raycast against both faces of an object, you'll want to set the material's side property to THREE.DoubleSide.

TLDR

• The code is clean, simple, and easy to follow
• The implementation is based on linear loops on every objects/triangles
• This is, thus, very naïve and not performance oriented/optimized

Some thoughts about the API

Its fairly common in raytracing (as in image rendering) to find two types of ray queries :

• nearestHit which returns only one intersection
• anyHit which returns only a form of boolean, to know if something was hit (used for shadow rays)
• those hints are used to improve performance in ray-intersection search
• threejs does not seem to provide those kind of hints

I also would have expected to get triangle barycentric coordinates from the intersections, as they can be used to interpolate attributes (such as uv, uv2 for exemple).

How it works

In Raycaster code,

• intersectObjects is a simple linear loop over the objects array.
• all intersections are sorted once (by distance), before returning the result array
• a helper intersectObject free function does the recursive traversal of objects children
  • skipping the !visible onces
  • looping the children and making intersectObject recursive calls
  • the actual intersection for an object is delegated to object.raycast method

The raycast method is available for different primitives :

• Sprite, by transforming the sprite vertices to face the raycaster.camera, and intersecting the 2 triangles formed by the sprite
• LOD, by selecting the LOD object from the ray origin and raycasting it
  • note the LOD is not related to the raycaster.camera
• Line
  • check the lines bounding sphere first, for early exit
  • linear loop for all lines, check for ray intersection against fattened lines
  • push every intersection found in result array
• Points
  • much like the lines, but checking every point/vertex
• Mesh
  • more complex, detailed below

For Mesh primitives, the code is more big :

• check the bounding sphere first, for early exit
• the search ray is transformed in object-space
  • using the matrix given by inverse(object.matrixWorld)
  • allowing to save on performance later on, the object does not have to be transformed using its matrixWorld
• intersect the object's optional boundingBox for early exit
• linearly loop every triangle of the mesh
  • evaluate morphing for the triangle if needed
    • note that skinning and bones seem not to be considered
  • check intersection with the triangle, considering the applied material sidedness
    • the intersection distance is carefully computed using the world-space ray, not using object-space ray, to prevent problems with scale transforms.
  • compute intersection UVs if appropriate
    • note the barycentric coordinates are completely recomputed using the intersection point, not reused from any intersection calculations
  • push intersection in result array

Some thoughts on behaviour

The overall intersect behaviour seem simple and complete, but is a very expensive process.

One must be careful about the number of intersections done in a frame, and carefully select the objects to consider for intersection - or risk a big performance hit.

Performance could be improved using acceleration structures, such as Bounding Volume Hierarchies. Of course, in such a large community, some work have been done on github, e.g. mrdoob/three.js#12857 or https://github.com/gkjohnson/three-mesh-bvh

Another, simple, performance helper would be to add hints to raycaster, allowing to get :

• all intersections, the current behaviour
• the nearest intersection, adjusting the ray far limit during the search would allow to discard irrelevent raycast calls
• any 'one' intersection, stopping the objects traversale as soon as an intersection is found

I guess most uses of intersection are related to picking objects, 'nearest' intersection could perhaps help, without much more complicated code.