How to get other 3D objects in position radius in three.js

Question

I have a three-dimensional scene in three .js in which I need to get an array of objects that are within the X range of the original object. At the moment, the example I'm using uses raycasting inside a for loop, which iterates through an array of "collidable objects" that exist in the scene. I feel that there should be a better way to handle this, because this approach is exponentially more complex if every object in the array needs raycast from itself to every other object in the array. This has a significant impact on performance, as the array of collision capable objects grows.

//hold collidable objects var collidableObjects = []; var scene = new THREE.Scene(); var cubeGeo = new THREE.CubeGeometry( 10 , 10 , 10 ); var materialA = new THREE.MeshBasicMaterial( { color: 0xff0000 } ); var materialB = new THREE.MeshBasicMaterial( { color: 0x00ff00 } ); var cubeA = new THREE.Mesh( cubeGeo , materialA ); collidableObjects.push( cubeA ); scene.add( cubeA ); //Change this variable to a larger number to see the processing time explode var range = 100; for( var x = 0 ; x < range ; x += 20 ) { for( var z = 0; z < range ; z += 20 ) { if( x === 0 && z === 0 ) continue; var cube = new THREE.Mesh( cubeGeo , materialB ); scene.add( cube ); cube.position.x = x; cube.position.z = z; collidableObjects.push( cube ); var cube = cube.clone(); scene.add( cube ); cube.position.x = x * -1; cube.position.z = z; collidableObjects.push( cube ); var cube = cube.clone(); scene.add( cube ); cube.position.x = x; cube.position.z = z * -1; collidableObjects.push( cube ); var cube = cube.clone(); scene.add( cube ); cube.position.x = x * -1; cube.position.z = z * -1; collidableObjects.push( cube ); } } var camera = new THREE.PerspectiveCamera( 75, window.innerWidth / window.innerHeight, 0.1, 1000 ); var renderer = new THREE.WebGLRenderer(); renderer.setSize( window.innerWidth, window.innerHeight ); document.body.appendChild( renderer.domElement ); camera.position.y = 200; camera.lookAt( scene.position ); function render() { //requestAnimationFrame(render); renderer.render(scene, camera); console.log( getObjectsWithinRange( cubeA , 30 ) ); } function getObjectsWithinRange( source , range ) { var startTime = new Date().getTime(); var inRange = []; for( var i = 0; i < collidableObjects.length ; ++i ) { var ray = new THREE.Raycaster( source.position , collidableObjects[i].position , 0 , range ); if( ( obj = ray.intersectObject( collidableObjects[i] ) ) && obj.length ) { inRange.push( obj[0] ); } } var endTime = new Date().getTime(); console.log( 'Processing Time: ' , endTime - startTime ); return inRange; } render(); 

Here you can see the JSfiddle.

If you change the specified variable to a larger number, say 200, you will see that the processing time starts to get out of control. I feel that there should be an easier way to reduce the number of such actions so that I look at the documentation for Raycaster from three.js and I notice that both near and far attributes say: "This value indicates which objects can be dropped based on distance" . therefore, I assume there is some internal function that is used to refine the results down based on distance before throwing all the rays.

I worked a bit on this and came up with one function inside Ray.js

 distanceToPoint: function () { var v1 = new THREE.Vector3(); return function ( point ) { var directionDistance = v1.subVectors( point, this.origin ).dot( this.direction ); // point behind the ray if ( directionDistance < 0 ) { return this.origin.distanceTo( point ); } v1.copy( this.direction ).multiplyScalar( directionDistance ).add( this.origin ); return v1.distanceTo( point ); }; }(), 

I assume that I am looking for the best way to get all the objects in the scene that are within the radius X of the radius of the original object. I don’t even need to use Raycasting, because I am not interested in a grid collision, but just a list of objects in the radius X of the radius of the original object. I don’t even need to go back to the children of these objects because of how the scene is created. So I feel that there needs to be some kind of internal function or something that just uses THREE.Vector3 objects and math to refine them by distance. In this case, it should be much cheaper math than Raycasting. If there is already a function that processes this somewhere in the three.js file, I don't want to recreate it from scratch. I also understand that this can be a very long question about what can be a very definite answer, but I wanted to make sure that I have all the details and something else, if someone else is looking for it, he is looking for it later.

Answer 1

Conflict checking is a more general problem, and I think you will have more success if you think about it in a context outside of Three.js. There are many methods for managing a large number of objects that need to be checked for conflicts with each other. Here are a few optimizations that may make a difference to you:

The first optimization for each object has a logical property indicating whether it has been moved since the last physics update. If both objects that you are comparing are not moved, you do not need to recount the collision. This is mostly true if you have a large number of objects in a stable state (for example, boxes that you can click). There are a number of other optimizations you can build on top of this; for example, often, if two objects do not move, they will not collide, because if they collide, they will roll back (move).

The second optimization is that you usually only need to check for a collision at a certain distance. For example, if you know that all your objects are less than 100 units, you can simply check if (x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 > 100^2 . If the check is correct (indicating the distance between two objects is large), you do not need to calculate detailed collisions. This is actually more or less near / far optimization that Raycaster provides you, but you do not use it in your code, since you always call the intersectObject method.

The third optimization is that you highlight a bunch of new Raycaster and related objects in each physical update. Instead, you can save the Raycasters pool (or even one Raycaster) and simply update your properties. This will avoid a lot of garbage collection.

Finally, the most common generalized approach to solving a large number of colliding objects is called spatial partitioning. The idea basically is that you divide your world into a given number of spaces and keep track of which space objects are located. Then, when you need to calculate the collision, you only need to check other objects located in the same space. The most common approach for this is to use Octree (8-ary tree). As WestLangley mentioned, Three.js has an October implementation , starting with version r59, as well as example ( source ). Here is a reasonable introduction to the concept of spatial partitioning using 2D examples.

Outside of these optimizations, if you need to do something particularly complicated, you might want to use an external physics library that will manage optimizations like this for you. The most popular ones to use with Three.js at the moment are Physijs , Cannon.js , and Ammo.js.