Expose objects' frustum culled state

[trusktr]

Description of the problem

The WebGLRenderer already calculates whether an object is frustum culled, using an internal Frustum.

It'd be nice if this information was exposed so that we don't have to duplicate the Scene traversal and calculations with our own Frustum outside of the renderer.

A couple ideas:

• Maybe Mesh objects can have an onFrustumCullChange property that is undefined or null by default. If it is set to a function, then when the frustum culling for the object changes the function can be called with true or false.
• Another idea would be to just set a boolean flag on the Mesh objects, but this would make logic relying on it be one frame behind. In most cases it wouldn't be a problem. The user could make the property into a getter/setter to achieve the same feature as the onFrustumCullChange idea.

Any other ways to do it without requiring a second traversal and calculations?

Three.js version

• [x] Dev

Browser

• [x] All of them

OS

• [x] All of them

[Mugen87]

What is your use case for such a feature?

[easyfrog]

Yeeees! I need this feature tooooo. Check the object if it's in view. to do some stuff. It's very useful!

[WestLangley]

Beware that the frustum culling test is conservative, so there may be objects which pass the cull test, yet are not in view.

[Usnul]

What you are describing sounds an awful lot like a "visibility set". I have an explicit frustum-based visibility set in my engine for similar reasons - to avoid extra computation. When computation becomes a bottleneck - you should also look towards a different solution for building the visibility set in the first place, such as using a spatial index.

related: https://github.com/mrdoob/three.js/issues/5571 https://github.com/mrdoob/three.js/issues/13909

[trusktr]

What is your use case for such a feature?

@Mugen87 In my case I wanted to do some collision detection, and I wanted to start with objects in the view instead of all objects in the scene. I figured that if the renderer is already computing this and exposed it then it'd prevent me from computing it a second time outside of the renderer.

[Usnul]

@trusktr

I think you should just use some decent physics engine with a decent broad-phase. Just my opinion. Also, make sure you allow bodies to sleep - it reduces number of checks.

[trusktr]

@Usnul That may be a bit much for my case. I'm working on a 3D editing program (business-specific) where I simply want to snap some points to other points, and figured I could at least iterate only the points that are in view.

Code for finding the objects in view looks like follows (code ommited, but you get the idea):

    const frustum = new THREE.Frustum
    const projScreenMatrix = new THREE.Matrix4
    const {camera} = this.props
    projScreenMatrix.multiplyMatrices( camera!.projectionMatrix, camera!.matrixWorldInverse )
    frustum.setFromMatrix( projScreenMatrix )

    this.getMarkersInFrustum(frustum)

// ... 

  getMarkersInFrustum(frustum: THREE.Frustum): Marker[] {
    return this.markers
      .filter(marker =>
        marker.children.some(n => {
          let hasMeshInView = false

          const hasGeom = hasGeometry(n) // f.e. n.geometry

          if (hasGeom && frustum.intersectsObject(n))
            hasMeshInView = true

          n.traverse(n => {
            const hasGeom = hasGeometry(n)

            if (hasGeom && frustum.intersectsObject(n))
              hasMeshInView = true
          })

          return hasMeshInView
        })
      )
  }

then after that I'm checking to see which marker is closest by checking distance from the edited marker position to all the other marker positions.

It's not terribly complicated, but seems like Three.js could expose this information which it already has.

[trusktr]

In my current case I'm doing the in-view detection only once when the user stops dragging an object, and not every frame, so performance is not as important in my current case, but I could see this being important if the detection needs to happen every frame, especially if there's many objects in the scene.

[Usnul]

@trusktr If you want snapping, i think spatial index is your best bet. Projecting a narrow frustum into the scene around your mouse pointer - getting a set of objects (or points) back, and then picking one closest to the pointer.

I run tens of queries per frame on my spatial index in the game I'm working on and it amounts to a couple of milliseconds, that's considering that my dataset has about 20,000 objects.

I also run a picking ray query from the pointer every frame and most of the time it doesn't even register when i do profiling as it runs in trivial amount of time.

A decent spatial index gives you O(log(n)) complexity for most fixed-volume queries and similar for rays, compared to O(n) for naive traversal a-la array.filter( x => _ );

For the sake of completeness - i should also mention GC considerations. Most of my hot code generates little to no garbage, most of three.js is written in that way too, the reason being - garbage accumulates and collection cycles cause hick-ups in your frame-rate.

[mrdoob]

I guess you can currently do this hack:

object1.onBeforeRender = function () { this.userData.inView = true } );

// render loop
scene.traverse( function ( child ) { child.userData.inView = false } );
renderer.render( scene, camera );

But I agree with @Usnul. I would use cannon.js or something.

[kmturley]

Nice workaround, but doesn't seem to work on some GLTF files. It works on a scene I exported from Blender 2.8, but not firing onBeforeRender using this example:

const loader = new GLTFLoader();
const dracoLoader = new DRACOLoader();
dracoLoader.setDecoderPath('https://threejs.org/examples/js/libs/draco/gltf/');
loader.setDRACOLoader(dracoLoader);
loader.load('https://threejs.org/examples/models/gltf/LittlestTokyo.glb', (gltf) => {
    console.log('load', gltf);
    gltf.scene.onBeforeRender = function() {
      console.log('onBeforeRender', this.userData);
      this.userData.inView = true;
    };
    scene.add(gltf.scene);
});

However this code worked correctly as it doesn't rely on the onRender function and traverses the full GLTF children:

const frustum = new THREE.Frustum();
const projScreenMatrix = new THREE.Matrix4();
camera.updateMatrixWorld();
projScreenMatrix.multiplyMatrices(camera.projectionMatrix, camera.matrixWorldInverse);
frustum.setFromMatrix(projScreenMatrix);
scene.traverse((object) => {
  if (object.isMesh || object.isLine || object.isPoints) {
    object.userData.inView = frustum.intersectsObject(object);
  }
});

[Mugen87]

gltf.scene.onBeforeRender = function() {

I'm afraid this line does not work since onBeforeRender() is only called for renderable objects (related #14970).

[eZii-jester-data]

In case someone is interested:

I got a patch for gltf loader that works with the new js zip version.

[Mugen87]

A solution based on a spatial index like described in https://github.com/mrdoob/three.js/issues/15339#issuecomment-447965399 seems more appropriate for the OPs use case.

If for some reasons users need all objects inside the view frustum as a query, they have to implement this on app level. The code of https://github.com/mrdoob/three.js/issues/15339#issuecomment-448332571 is a good start. For a more precise solution, a stricter test is required anyway.

[gewesp]

Another use case here: Decide which tiles to subdivide in a web mercator map quadtree for level-of-detail control. Think Google Earth.

Simple approach with 4x - 10x overhead, depending on frustom: Subdivide all tiles 'close' to the camera Refined approach: Subdivide only tiles that are close to the camera and currently in view.

[mrdoob]

Have you tried creating your own Frustum instance for that case and traverse the scene with it?

I'm aware it would be 2x the amount of traverses, but should be as least faster than Simple approach?