import { Box3 } from "../math/box3" ; import { Vector3 } from "../math/vector3" ; const DEFAULT_ROOT_NODE_SIZE = 1 ; const MIN_DEPTH = - 32 ; const MAX_DEPTH = 8 ; let v1 = new Vector3 ( ) ; let v2 = new Vector3 ( ) ; let b1 = new Box3 ( ) ; /** Specifies an object that an octree can index. */ export interface OctreeObject { boundingBox : Box3 ; } export interface OctreeIntersection { object : OctreeObject ; point : Vector3 ; distance : number ; } /** A dynamic, loose octree of bounding boxes for efficient spatial operations such as raytracing. Implemented without any cringe. */ export class Octree { root : OctreeNode ; /** A map of each object in the octree to the node that it's in. This accelerates removal drastically, as the lookup step can be skipped. */ objectToNode : WeakMap < OctreeObject , OctreeNode > ; beforeOperation : ( ) => void = null ; constructor ( ) { this . root = new OctreeNode ( this , 0 ) ; this . root . min . set ( 0 , 0 , 0 ) ; this . root . size = DEFAULT_ROOT_NODE_SIZE ; this . objectToNode = new WeakMap ( ) ; } insert ( object ) { let node = this . objectToNode . get ( object ) ; if ( node ) return ; while ( ! this . root . largerThan ( object ) || ! this . root . containsCenter ( object ) ) { if ( this . root . depth === MIN_DEPTH ) { console . log ( object ) ; console . warn ( `Can't insert ${ this . root . largerThan ( object ) ? 'distant' : 'large' } object into octree; the octree has already expanded to its maximum size.` ) ; return ; } this . grow ( object ) ; } let emptyBefore = this . root . count === 0 ; this . root . insert ( object ) ; if ( emptyBefore ) this . shrink ( ) ; } remove ( object ) { let node = this . objectToNode . get ( object ) ; if ( ! node ) return ; node . remove ( object ) ; this . objectToNode . delete ( object ) ; this . shrink ( ) ; } /** Updates an object in the tree whose bounding box has changed. */ update ( object ) { let node = this . objectToNode . get ( object ) ; if ( ! node ) { this . insert ( object ) ; return ; } let success = node . update ( object ) ; if ( ! success ) { this . objectToNode . delete ( object ) ; this . insert ( object ) ; } } /** Expand the octree towards an object that doesn't fit in it. */ grow ( towards ) { let averagePoint = v1 . set ( 0 , 0 , 0 ) ; let count = 0 ; for ( let i = 0 ; i < 8 ; i ++ ) { let vec = v2 ; vec . setComponent ( 0 , ( i & 0b001 ) ? towards . boundingBox . min . x : towards . boundingBox . max . x ) ; vec . setComponent ( 1 , ( i & 0b010 ) ? towards . boundingBox . min . y : towards . boundingBox . max . y ) ; vec . setComponent ( 2 , ( i & 0b100 ) ? towards . boundingBox . min . z : towards . boundingBox . max . z ) ; if ( ! this . root . containsPoint ( vec ) ) { averagePoint . add ( vec ) ; count ++ ; } } averagePoint . multiplyScalar ( 1 / count ) ; let rootCenter = v2 . copy ( this . root . min ) . addScalar ( this . root . size / 2 ) ; let direction = averagePoint . sub ( rootCenter ) ; let newRoot = new OctreeNode ( this , this . root . depth - 1 ) ; newRoot . min . copy ( this . root . min ) ; newRoot . size = this . root . size * 2 ; if ( direction . x < 0 ) newRoot . min . x -= this . root . size ; if ( direction . y < 0 ) newRoot . min . y -= this . root . size ; if ( direction . z < 0 ) newRoot . min . z -= this . root . size ; if ( this . root . count > 0 ) { let octantIndex = ( ( direction . x < 0 ) ? 1 : 0 ) + ( ( direction . y < 0 ) ? 2 : 0 ) + ( ( direction . z < 0 ) ? 4 : 0 ) ; newRoot . createOctants ( ) ; newRoot . octants [ octantIndex ] = this . root ; this . root . parent = newRoot ; newRoot . count = this . root . count ; newRoot . merge ( ) ; } this . root = newRoot ; } /** Tries to shrink the octree if large parts of the octree are empty. */ shrink ( ) { if ( this . root . size < DEFAULT_ROOT_NODE_SIZE || this . root . objects . size > 0 ) return ; if ( this . root . count === 0 ) { this . root . min . set ( 0 , 0 , 0 ) ; this . root . size = DEFAULT_ROOT_NODE_SIZE ; this . root . depth = 0 ; return ; } if ( ! this . root . octants ) return ; let nonEmptyOctant ; for ( let i = 0 ; i < 8 ; i ++ ) { let octant = this . root . octants [ i ] ; if ( octant . count > 0 ) { if ( nonEmptyOctant ) return ; else nonEmptyOctant = octant ; } } this . root = nonEmptyOctant ; nonEmptyOctant . parent = null ; this . shrink ( ) ; } intersectAabb ( aabb ) { this . beforeOperation ?. ( ) ; let intersections = [ ] ; this . root . intersectAabb ( aabb , intersections ) ; return intersections ; } } class OctreeNode { octree : Octree ; parent : OctreeNode = null ; /** The min corner of the bounding box. */ min = new Vector3 ( ) ; /** The size of the bounding box on all three axes. This forces the bounding box to be a cube. */ size : number ; octants : OctreeNode [ ] = null ; /** A list of objects contained in this node. Note that the node doesn't need to be a leaf node for this set to be non-empty; since this is an octree of bounding boxes, some volumes cannot fit into an octant and therefore need to be stored in the node itself. */ objects = new Set < OctreeObject > ( ) ; /** The total number of objects in the subtree with this node as its root. */ count = 0 ; depth : number ; constructor ( octree , depth ) { this . octree = octree ; this . depth = depth ; } insert ( object ) { this . count ++ ; if ( this . octants ) { if ( this . octants [ 0 ] . largerThan ( object ) ) { for ( let i = 0 ; i < 8 ; i ++ ) { let octant = this . octants [ i ] ; if ( octant . containsCenter ( object ) ) { octant . insert ( object ) ; return ; } } } this . objects . add ( object ) ; this . octree . objectToNode . set ( object , this ) ; } else { this . objects . add ( object ) ; this . octree . objectToNode . set ( object , this ) ; this . split ( ) ; } } split ( ) { if ( this . objects . size <= 8 || this . depth === MAX_DEPTH ) return ; this . createOctants ( ) ; for ( let object of this . objects ) { if ( this . octants [ 0 ] . largerThan ( object ) ) { for ( let j = 0 ; j < 8 ; j ++ ) { let octant = this . octants [ j ] ; if ( octant . containsCenter ( object ) ) { octant . insert ( object ) ; this . objects . delete ( object ) ; } } } } for ( let i = 0 ; i < 8 ; i ++ ) { this . octants [ i ] . split ( ) ; } } createOctants ( ) { this . octants = [ ] ; for ( let i = 0 ; i < 8 ; i ++ ) { let newNode = new OctreeNode ( this . octree , this . depth + 1 ) ; newNode . parent = this ; newNode . size = this . size / 2 ; newNode . min . set ( this . min . x + newNode . size * ( ( i & 0b001 ) >> 0 ) , this . min . y + newNode . size * ( ( i & 0b010 ) >> 1 ) , this . min . z + newNode . size * ( ( i & 0b100 ) >> 2 ) ) ; this . octants . push ( newNode ) ; } } remove ( object ) { this . objects . delete ( object ) ; this . count -- ; this . merge ( ) ; let node = this . parent ; while ( node ) { node . count -- ; node . merge ( ) ; node = node . parent ; } } update ( object ) { this . objects . delete ( object ) ; let node = this ; while ( node ) { node . count -- ; node . merge ( ) ; if ( node . largerThan ( object ) && node . containsCenter ( object ) ) { node . insert ( object ) ; return true ; } node = node . parent ; } return false ; } merge ( ) { if ( this . count > 8 || ! this . octants ) return ; for ( let i = 0 ; i < 8 ; i ++ ) { let octant = this . octants [ i ] ; for ( let object of octant . objects ) { this . objects . add ( object ) ; this . octree . objectToNode . set ( object , this ) ; } } this . octants = null ; } largerThan ( object ) { let box = object . boundingBox ; return this . size > ( box . max . x - box . min . x ) && this . size > ( box . max . y - box . min . y ) && this . size > ( box . max . z - box . min . z ) ; } containsCenter ( object ) { let box = object . boundingBox ; let x = box . min . x + ( box . max . x - box . min . x ) / 2 ; let y = box . min . y + ( box . max . y - box . min . y ) / 2 ; let z = box . min . z + ( box . max . z - box . min . z ) / 2 ; return this . min . x <= x && x < ( this . min . x + this . size ) && this . min . y <= y && y < ( this . min . y + this . size ) && this . min . z <= z && z < ( this . min . z + this . size ) ; } containsPoint ( point ) { let { x , y , z } = point ; return this . min . x <= x && x < ( this . min . x + this . size ) && this . min . y <= y && y < ( this . min . y + this . size ) && this . min . z <= z && z < ( this . min . z + this . size ) ; } intersectAabb ( aabb , intersections ) { let looseBoundingBox = b1 ; looseBoundingBox . min . copy ( this . min ) . addScalar ( - this . size / 2 ) ; looseBoundingBox . max . copy ( this . min ) . addScalar ( this . size * 3 / 2 ) ; if ( ! aabb . intersectsBox ( looseBoundingBox ) ) return ; if ( this . objects . size > 0 ) for ( let object of this . objects ) { if ( aabb . intersectsBox ( object . boundingBox ) ) intersections . push ( object ) ; } if ( this . octants ) for ( let i = 0 ; i < 8 ; i ++ ) { let octant = this . octants [ i ] ; if ( octant . count === 0 ) continue ; octant . intersectAabb ( aabb , intersections ) ; } } }