threeoctree

$3

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

See demo examples

$3

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

$3

* 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:

``

html





Usage with npm and ES modules:



npm install @brakebein/threeoctree

javascript

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



const octree = new Octree();

$3

javascript

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

});





$3



Add mesh as single octree object:

javascript

octree.add( mesh );



  

Add mesh's faces as octree objects:

javascript

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



  

Add mesh's vertices as octree objects:

javascript

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:

javascript

octree.remove( mesh );





$3

  

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.

javascript

renderer.render( scene, camera );

octree.update();





$3



To account for moving objects within the octree:

javascript

octree.rebuild();



  

$3



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

javascript

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):

javascript

octree.search( position, radius, true );





Search octree using a ray:

javascript

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





$3



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:

javascript

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:

javascript

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 );

    

    // ...

    

}





$3



Make use of generics in TypeScript:

typescript

import { BoxGeometry, MeshBasicMaterial } from 'three';

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



const octree = new Octree>();



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



octree.add( mesh );



// ...



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



octreeResults[0].object // -> Mesh