Object3D / Raycaster: Provide way to stop raycast intersection traversal

[gkjohnson]

Description

When rendering the Google Photorealistic Tiles data set - in common cases this can result in a loaded, rendered set of data amounting to thousands of objects and hundreds or thousands of meshes. Without any custom implementation even a single raycast can take an extremely long time.

To help alleviate this the 3DTilesRendererJS implementation overrides the root "Group.raycast" function to use intrinsic tile set bounding volume hierarchy to accelerate intersections and an option to only return the first intersection, which requires setting all child "raycast" functions to an empty no-op function since there's no way to stop traversal at the root object. These optimizations alone bring the amount of time to perform a single raycast down from ~25-35ms to ~2-5ms. 2-5ms is still fairly slow, though.

Performing more performance investigation, the the additional traversal of the children with no-op raycast functions is accounting for 40-80% of the intersectObject function. Here are a couple examples from moving the cursor across the image at this camera position. Generally it's contributing to well over 1ms in overhead:

Recursive Intersect	Non-Recursive Intersect	Overhead ms	Overhead %
2.79 ms	1.3991 ms	1.3909 ms	~50%
1.9221 ms	0.3820 ms	1.54 ms	~81.16%
4.8901 ms	3.0359 ms	1.8542 ms	~37.92%

An additional note is that because the optimization requires overwriting the raycast functions on all child objects to a no-op it's not possible for end users to set a custom raycast override.

Solution

Provide some kind of an API for Raycaster and / or Object3D.raycast that allows for the ability to stop raycast traversal. A flag on the Object3D or a function like Raycaster.preventDefault or Raycaster.stopTraversal similar to events to call to stop traversal in the "raycast" callback would suffice.

Alternatives

Maintain a custom raycaster solution in 3d tiles renderer but this would be unnecessarily confusing for new users and lead to fragmentation when different libraries build and require different solutions for something similar.

Additional context

Raycasting is required for user interaction, camera positioning, and more. It wouldn't be unusual to have half a dozen to dozens or more raycasts performed in a single frame.

[IRobot1]

Can't this be accomplished using layers? Just add a layers and the layer the raycaster should test against. Any mesh that should be skipped (including all its children) are not included in the layer.

I think the current problem is that raycaster doesn't skip the children if the parent layer test fails. You have to explicitly set recursive to false.

I've successfully used this technique to skip in-scene user interface elements that are not visible or not interactive. The traversal went from 1000+ objects to <100 per frame. Much faster.

[gkjohnson]

Currently layers does not solve this issue because, as you mention, the all children are all still traversed and layers are checked.

But either way I don't feel layers are good solution for this since it will affect rendering and require configuration from the end user to use what should be basic features. The goal is to make raycasting "just work" without having to fuss with anything.

[IRobot1]

Unreal engine trace channels have three options, ignore, overlap and block. Ignore and overlap are covered by layers. Perhaps the flag you are suggesting is block. It prevents any further intersections being computed. It would be nice if block could be added when enabling a layer.

[RemusMar]

@gkjohnson The goal is to make raycasting "just work" without having to fuss with anything.

@IRobot1 Unreal engine trace channels have three options, ignore, overlap and block. Ignore and overlap are covered by layers.

+1 In my opinion, UE has the best implementation on this chapter. It might be a very good source of inspiration here.