I'm working on a three.js scene in which it would be hugely beneficial to be able to determine the subset of all faces (among all geometries) that are visible to the camera at a given time.
I understand one can determine whether a vertex is visible to the camera by doing something like:
camera.updateMatrix();
camera.updateMatrixWorld();
var frustum = new THREE.Frustum();
frustum.setFromMatrix(new THREE.Matrix4().multiplyMatrices(camera.projectionMatrix, camera.matrixWorldInverse));
// The 3d point to check
var pos = new THREE.Vector3(x, y, z);
if (frustum.containsPoint(pos)) {
// Do something crazy...
}
My geometry has tens of thousands of 2d plane faces, all sitting on a larger plane, and I'd like to determine the set of of their faces that are visible to the camera fairly often (each time the camera zooms past a certain hyperplane, if possible).
I know one can do scene.children[childIndex].visible to see if a mesh is visible, but I have many faces on a mesh and want to determine which of the faces are visible. (All of my meshes are always rendered unless the user zooms wildly). I also know one can adapt this approach:
var frustum = new THREE.Frustum();
var cameraViewProjectionMatrix = new THREE.Matrix4();
// every time the camera or objects change position (or every frame)
camera.updateMatrixWorld(); // make sure the camera matrix is updated
camera.matrixWorldInverse.getInverse( camera.matrixWorld );
cameraViewProjectionMatrix.multiplyMatrices( camera.projectionMatrix, camera.matrixWorldInverse );
frustum.setFromMatrix( cameraViewProjectionMatrix );
console.log( frustum.intersectsBox( meshes[0].geometry.vertices[0] ) );
Is there a shortcut one can take to find the set of all faces visible to the camera at a given time? In my case, I could precompute the geometric mean of each planar face then use the code above to determine which of the faces is visible, but is there anything better than O(n) in this case?
I'd be very grateful for any ideas others can offer on this question!
Better than O(n)?
Given a sorted array of integers I believe one can determine the subset of those integers that line between an upper and lower bound in ~O(log(n)). Each face's geometric mean is a 3d point, so it seems possible to determine the set of points within the frustum with 3*O(log(n)), i.e. better than O(n) complexity.
Better than O(log(n))
An approximation better than O(log(n)) after some precomputing. Suppose we're dealing with only 1D (then we can generalize to 3D). Quantize the space of each axis then create a hash table with the following structure. For each unit in the quantized space, store the index position of the first point in the sorted array with that unit +- error value. Then given an upper and lower bound, round each to the nearest quantized unit and look up the values for those keys to identify the range of index positions within the span. This returns a list. Repeat for the other two dimensions and take the set intersection. [The frustum provides the upper and lower bounds for each dimension.]
