threeoctree

(sparse + dynamic) 3D spatial representation structure for fast searches

Fully featured search tree for the three.js WebGL library.

See demo examples

Acknowledgement

The original library has been implemented by Collin Hover based on Dynamic Octree by Piko3D and Octree by Marek Pawlowski.

However, the original code hasn't been updated for years and has also been removed from the three.js repo (r100). There seems to be new Octree class, which is however not sparse and dynamic and serves only for simple hit tests.

Hence, the aim of this repo is to bring it up-to-date with the latest three.js release (r133). Support for Geometry was dropped, since it is deprecated and has been removed from three.js core (r125). Instead, Octree has been updated to only support BufferGeometry. Additionally, it adds type declarations.

Features

• handle complete objects ( i.e. 1 center position for entire geometry )
• handle object faces ( i.e. split a complex mesh's geometry into a series of pseudo-objects )
• handle both objects and faces together in a single octree
• overlapping nodes to help sort objects that overlap multiple nodes much more efficiently ( overlap is percentage based )
• split ( 1 larger octree node > up to 8 smaller octree nodes )
• merge ( up to 8 smaller octree nodes > 1 larger octree node )
• expand ( 1 smaller octree node > 1 larger octree node + original smaller octree node + up to 7 other smaller octree nodes )
• contract ( 1 larger octree node + entire subtree > 1 smaller octree node )
• rebuild ( account for moving objects, trade-off is performance and is not recommended )
• search by position and radius ( i.e. sphere search )
• search by ray using position, direction, and distance/far ( does not include specific collisions, only potential )
• raycast search results using THREE.OctreeRaycaster

Needs

• reworking / optimization of insert and removal ( currently we have to force a transform update in case the object is added before first three update )
• OctreeRaycaster: consider backface culling with respect to material.side ( FrontSide | BackSide | DoubleSide )

Usage

Download the latest script and include it in your html after three.js:

<script src="js/three.min.js"></script>
<script src="js/threeoctree.min.js"></script>
<script>
  const octree = new THREE.Octree();
</script>

Usage with npm and ES modules:

npm install @brakebein/threeoctree

import { Octree } from '@brakebein/threeoctree';

const octree = new Octree();

Initialize

const octree = new THREE.Octree({
    undeferred: false, // optional, default = false, octree will defer insertion until you call octree.update();
    depthMax: Infinity, // optional, default = Infinity, infinite depth
    objectsThreshold: 8, // optional, default = 8
    overlapPct: 0.15, // optional, default = 0.15 (15%), this helps sort objects that overlap nodes
    scene: scene // optional, pass scene as parameter only if you wish to visualize octree
});

Add/Remove Objects

Add mesh as single octree object:

octree.add( mesh );

Add mesh's faces as octree objects:

octree.add( mesh, { useFaces: true } );

Add mesh's vertices as octree objects:

octree.add( mesh, { useVertices: true } );

( note that only vertices OR faces can be used, and useVertices overrides useFaces )

Remove all octree objects associated with a mesh:

octree.remove( mesh );

Update

When octree.add( object ) is called and octree.undeferred !== true, insertion for that object is deferred until the octree is updated. Update octree to insert all deferred objects after render cycle to makes sure object matrices are up-to-date.

renderer.render( scene, camera );
octree.update();

Rebuild

To account for moving objects within the octree:

octree.rebuild();

Search

Search octree at a position in all directions for radius distance:

octree.search( position, radius );

Search octree and organize results by object (i.e. all faces/vertices belonging to three object in one list vs a result for each face/vertex):

octree.search( position, radius, true );

Search octree using a ray:

octree.search( ray.origin, ray.far, true, ray.direction );

Intersections

The OctreeRaycaster extends the THREE.Raycaster class by two methods to help use the search results: intersectOctreeObjects() and intersectOctreeObject(). In most cases you will use only the former:

const octreeResults = octree.search( raycaster.ray.origin, raycaster.ray.far, true, raycaster.ray.direction );
const intersections = raycaster.intersectOctreeObjects( octreeResults );

If you wish to get an intersection from a user's mouse click, this is easy enough:

function onClick ( event ) {
    
    const mouse = new THREE.Vector2(
        ( event.pageX / window.innerWidth ) * 2 - 1,
        -( event.pageY / window.innerHeight ) * 2 + 1
    );

    // set raycaster
  
    const raycaster = new THREE.OctreeRaycaster();
    raycaster.setFromCamera( mouse, camera );

    // now search octree and find intersections using method above
  
    const octreeResults = octree.search( raycaster.ray.origin, raycaster.ray.far, true, raycaster.ray.direction );
    const intersections = raycaster.intersectOctreeObjects( octreeResults );
    
    // ...
    
}

TypeScript usage

Make use of generics in TypeScript:

import { BoxGeometry, MeshBasicMaterial } from 'three';
import { Octree } from '@brakebein/threeoctree';

const octree = new Octree<Mesh<BoxGeometry, MeshBasicMaterial>>();

const mesh = new Mesh( new BoxGeometry(), new MeshBasicMaterial() );

octree.add( mesh );

// ...

const octreeResults = octree.search( position, radius, true );

octreeResults[0].object // -> Mesh<BoxGeometry, MeshBasicMaterial>