g
/
g
1
0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
61 MiB
 
 
Branch: master
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'master'
${ noResults }
g/grafos/js/Octree.js

2137 lines
45 KiB
Raw Permalink Blame History

/*!
*
* threeoctree.js (r60) / https://github.com/collinhover/threeoctree
* (sparse) dynamic 3D spatial representation structure for fast searches.
*
* @author Collin Hover / http://collinhover.com/
* based on Dynamic Octree by Piko3D @ http://www.piko3d.com/ and Octree by Marek Pawlowski @ pawlowski.it
*
*/
( function ( THREE ) {
"use strict";
/*===================================================
utility
=====================================================*/
function isNumber ( n ) {
return ! isNaN( n ) && isFinite( n );
}
function isArray ( target ) {
return Object.prototype.toString.call( target ) === '[object Array]';
}
function toArray ( target ) {
return target ? ( isArray ( target ) !== true ? [ target ] : target ) : [];
}
function indexOfValue( array, value ) {
for ( var i = 0, il = array.length; i < il; i ++ ) {
if ( array[ i ] === value ) {
return i;
}
}
return - 1;
}
function indexOfPropertyWithValue( array, property, value ) {
for ( var i = 0, il = array.length; i < il; i ++ ) {
if ( array[ i ][ property ] === value ) {
return i;
}
}
return - 1;
}
/*===================================================
octree
=====================================================*/
THREE.Octree = function ( parameters ) {
// handle parameters
parameters = parameters || {};
parameters.tree = this;
// static properties ( modification is not recommended )
this.nodeCount = 0;
this.INDEX_INSIDE_CROSS = - 1;
this.INDEX_OUTSIDE_OFFSET = 2;
this.INDEX_OUTSIDE_POS_X = isNumber( parameters.INDEX_OUTSIDE_POS_X ) ? parameters.INDEX_OUTSIDE_POS_X : 0;
this.INDEX_OUTSIDE_NEG_X = isNumber( parameters.INDEX_OUTSIDE_NEG_X ) ? parameters.INDEX_OUTSIDE_NEG_X : 1;
this.INDEX_OUTSIDE_POS_Y = isNumber( parameters.INDEX_OUTSIDE_POS_Y ) ? parameters.INDEX_OUTSIDE_POS_Y : 2;
this.INDEX_OUTSIDE_NEG_Y = isNumber( parameters.INDEX_OUTSIDE_NEG_Y ) ? parameters.INDEX_OUTSIDE_NEG_Y : 3;
this.INDEX_OUTSIDE_POS_Z = isNumber( parameters.INDEX_OUTSIDE_POS_Z ) ? parameters.INDEX_OUTSIDE_POS_Z : 4;
this.INDEX_OUTSIDE_NEG_Z = isNumber( parameters.INDEX_OUTSIDE_NEG_Z ) ? parameters.INDEX_OUTSIDE_NEG_Z : 5;
this.INDEX_OUTSIDE_MAP = [];
this.INDEX_OUTSIDE_MAP[ this.INDEX_OUTSIDE_POS_X ] = { index: this.INDEX_OUTSIDE_POS_X, count: 0, x: 1, y: 0, z: 0 };
this.INDEX_OUTSIDE_MAP[ this.INDEX_OUTSIDE_NEG_X ] = { index: this.INDEX_OUTSIDE_NEG_X, count: 0, x: - 1, y: 0, z: 0 };
this.INDEX_OUTSIDE_MAP[ this.INDEX_OUTSIDE_POS_Y ] = { index: this.INDEX_OUTSIDE_POS_Y, count: 0, x: 0, y: 1, z: 0 };
this.INDEX_OUTSIDE_MAP[ this.INDEX_OUTSIDE_NEG_Y ] = { index: this.INDEX_OUTSIDE_NEG_Y, count: 0, x: 0, y: - 1, z: 0 };
this.INDEX_OUTSIDE_MAP[ this.INDEX_OUTSIDE_POS_Z ] = { index: this.INDEX_OUTSIDE_POS_Z, count: 0, x: 0, y: 0, z: 1 };
this.INDEX_OUTSIDE_MAP[ this.INDEX_OUTSIDE_NEG_Z ] = { index: this.INDEX_OUTSIDE_NEG_Z, count: 0, x: 0, y: 0, z: - 1 };
this.FLAG_POS_X = 1 << ( this.INDEX_OUTSIDE_POS_X + 1 );
this.FLAG_NEG_X = 1 << ( this.INDEX_OUTSIDE_NEG_X + 1 );
this.FLAG_POS_Y = 1 << ( this.INDEX_OUTSIDE_POS_Y + 1 );
this.FLAG_NEG_Y = 1 << ( this.INDEX_OUTSIDE_NEG_Y + 1 );
this.FLAG_POS_Z = 1 << ( this.INDEX_OUTSIDE_POS_Z + 1 );
this.FLAG_NEG_Z = 1 << ( this.INDEX_OUTSIDE_NEG_Z + 1 );
this.utilVec31Search = new THREE.Vector3();
this.utilVec32Search = new THREE.Vector3();
// pass scene to see octree structure
this.scene = parameters.scene;
if ( this.scene ) {
this.visualGeometry = new THREE.BoxGeometry( 1, 1, 1 );
this.visualMaterial = new THREE.MeshBasicMaterial( { color: 0xFF0066, wireframe: true, wireframeLinewidth: 1 } );
}
// properties
this.objects = [];
this.objectsMap = {};
this.objectsData = [];
this.objectsDeferred = [];
this.depthMax = isNumber( parameters.depthMax ) ? parameters.depthMax : Infinity;
this.objectsThreshold = isNumber( parameters.objectsThreshold ) ? parameters.objectsThreshold : 8;
this.overlapPct = isNumber( parameters.overlapPct ) ? parameters.overlapPct : 0.15;
this.undeferred = parameters.undeferred || false;
this.root = parameters.root instanceof THREE.OctreeNode ? parameters.root : new THREE.OctreeNode( parameters );
};
THREE.Octree.prototype = {
update: function () {
// add any deferred objects that were waiting for render cycle
if ( this.objectsDeferred.length > 0 ) {
for ( var i = 0, il = this.objectsDeferred.length; i < il; i ++ ) {
var deferred = this.objectsDeferred[ i ];
this.addDeferred( deferred.object, deferred.options );
}
this.objectsDeferred.length = 0;
}
},
add: function ( object, options ) {
// add immediately
if ( this.undeferred ) {
this.updateObject( object );
this.addDeferred( object, options );
} else {
// defer add until update called
this.objectsDeferred.push( { object: object, options: options } );
}
},
addDeferred: function ( object, options ) {
var i, l,
geometry,
faces,
useFaces,
vertices,
useVertices,
objectData;
// ensure object is not object data
if ( object instanceof THREE.OctreeObjectData ) {
object = object.object;
}
// check uuid to avoid duplicates
if ( ! object.uuid ) {
object.uuid = THREE.Math.generateUUID();
}
if ( ! this.objectsMap[ object.uuid ] ) {
// store
this.objects.push( object );
this.objectsMap[ object.uuid ] = object;
// check options
if ( options ) {
useFaces = options.useFaces;
useVertices = options.useVertices;
}
if ( useVertices === true ) {
geometry = object.geometry;
vertices = geometry.vertices;
for ( i = 0, l = vertices.length; i < l; i ++ ) {
this.addObjectData( object, vertices[ i ] );
}
} else if ( useFaces === true ) {
geometry = object.geometry;
faces = geometry.faces;
for ( i = 0, l = faces.length; i < l; i ++ ) {
this.addObjectData( object, faces[ i ] );
}
} else {
this.addObjectData( object );
}
}
},
addObjectData: function ( object, part ) {
var objectData = new THREE.OctreeObjectData( object, part );
// add to tree objects data list
this.objectsData.push( objectData );
// add to nodes
this.root.addObject( objectData );
},
remove: function ( object ) {
var i, l,
objectData = object,
index,
objectsDataRemoved;
// ensure object is not object data for index search
if ( object instanceof THREE.OctreeObjectData ) {
object = object.object;
}
// check uuid
if ( this.objectsMap[ object.uuid ] ) {
this.objectsMap[ object.uuid ] = undefined;
// check and remove from objects, nodes, and data lists
index = indexOfValue( this.objects, object );
if ( index !== - 1 ) {
this.objects.splice( index, 1 );
// remove from nodes
objectsDataRemoved = this.root.removeObject( objectData );
// remove from objects data list
for ( i = 0, l = objectsDataRemoved.length; i < l; i ++ ) {
objectData = objectsDataRemoved[ i ];
index = indexOfValue( this.objectsData, objectData );
if ( index !== - 1 ) {
this.objectsData.splice( index, 1 );
}
}
}
} else if ( this.objectsDeferred.length > 0 ) {
// check and remove from deferred
index = indexOfPropertyWithValue( this.objectsDeferred, 'object', object );
if ( index !== - 1 ) {
this.objectsDeferred.splice( index, 1 );
}
}
},
extend: function ( octree ) {
var i, l,
objectsData,
objectData;
if ( octree instanceof THREE.Octree ) {
// for each object data
objectsData = octree.objectsData;
for ( i = 0, l = objectsData.length; i < l; i ++ ) {
objectData = objectsData[ i ];
this.add( objectData, { useFaces: objectData.faces, useVertices: objectData.vertices } );
}
}
},
rebuild: function () {
var i, l,
node,
object,
objectData,
indexOctant,
indexOctantLast,
objectsUpdate = [];
// check all object data for changes in position
// assumes all object matrices are up to date
for ( i = 0, l = this.objectsData.length; i < l; i ++ ) {
objectData = this.objectsData[ i ];
node = objectData.node;
// update object
objectData.update();
// if position has changed since last organization of object in tree
if ( node instanceof THREE.OctreeNode && ! objectData.positionLast.equals( objectData.position ) ) {
// get octant index of object within current node
indexOctantLast = objectData.indexOctant;
indexOctant = node.getOctantIndex( objectData );
// if object octant index has changed
if ( indexOctant !== indexOctantLast ) {
// add to update list
objectsUpdate.push( objectData );
}
}
}
// update changed objects
for ( i = 0, l = objectsUpdate.length; i < l; i ++ ) {
objectData = objectsUpdate[ i ];
// remove object from current node
objectData.node.removeObject( objectData );
// add object to tree root
this.root.addObject( objectData );
}
},
updateObject: function ( object ) {
var i, l,
parentCascade = [ object ],
parent,
parentUpdate;
// search all parents between object and root for world matrix update
parent = object.parent;
while ( parent ) {
parentCascade.push( parent );
parent = parent.parent;
}
for ( i = 0, l = parentCascade.length; i < l; i ++ ) {
parent = parentCascade[ i ];
if ( parent.matrixWorldNeedsUpdate === true ) {
parentUpdate = parent;
}
}
// update world matrix starting at uppermost parent that needs update
if ( typeof parentUpdate !== 'undefined' ) {
parentUpdate.updateMatrixWorld();
}
},
search: function ( position, radius, organizeByObject, direction ) {
var i, l,
node,
objects,
objectData,
object,
results,
resultData,
resultsObjectsIndices,
resultObjectIndex,
directionPct;
// add root objects
objects = [].concat( this.root.objects );
// ensure radius (i.e. distance of ray) is a number
if ( ! ( radius > 0 ) ) {
radius = Number.MAX_VALUE;
}
// if direction passed, normalize and find pct
if ( direction instanceof THREE.Vector3 ) {
direction = this.utilVec31Search.copy( direction ).normalize();
directionPct = this.utilVec32Search.set( 1, 1, 1 ).divide( direction );
}
// search each node of root
for ( i = 0, l = this.root.nodesIndices.length; i < l; i ++ ) {
node = this.root.nodesByIndex[ this.root.nodesIndices[ i ] ];
objects = node.search( position, radius, objects, direction, directionPct );
}
// if should organize results by object
if ( organizeByObject === true ) {
results = [];
resultsObjectsIndices = [];
// for each object data found
for ( i = 0, l = objects.length; i < l; i ++ ) {
objectData = objects[ i ];
object = objectData.object;
resultObjectIndex = indexOfValue( resultsObjectsIndices, object );
// if needed, create new result data
if ( resultObjectIndex === - 1 ) {
resultData = {
object: object,
faces: [],
vertices: []
};
results.push( resultData );
resultsObjectsIndices.push( object );
} else {
resultData = results[ resultObjectIndex ];
}
// object data has faces or vertices, add to list
if ( objectData.faces ) {
resultData.faces.push( objectData.faces );
} else if ( objectData.vertices ) {
resultData.vertices.push( objectData.vertices );
}
}
} else {
results = objects;
}
return results;
},
setRoot: function ( root ) {
if ( root instanceof THREE.OctreeNode ) {
// store new root
this.root = root;
// update properties
this.root.updateProperties();
}
},
getDepthEnd: function () {
return this.root.getDepthEnd();
},
getNodeCountEnd: function () {
return this.root.getNodeCountEnd();
},
getObjectCountEnd: function () {
return this.root.getObjectCountEnd();
},
toConsole: function () {
this.root.toConsole();
}
};
/*===================================================
object data
=====================================================*/
THREE.OctreeObjectData = function ( object, part ) {
// properties
this.object = object;
// handle part by type
if ( part instanceof THREE.Face3 ) {
this.faces = part;
this.face3 = true;
this.utilVec31FaceBounds = new THREE.Vector3();
} else if ( part instanceof THREE.Vector3 ) {
this.vertices = part;
}
this.radius = 0;
this.position = new THREE.Vector3();
// initial update
if ( this.object instanceof THREE.Object3D ) {
this.update();
}
this.positionLast = this.position.clone();
};
THREE.OctreeObjectData.prototype = {
update: function () {
if ( this.face3 ) {
this.radius = this.getFace3BoundingRadius( this.object, this.faces );
this.position.copy( this.faces.centroid ).applyMatrix4( this.object.matrixWorld );
} else if ( this.vertices ) {
this.radius = this.object.material.size || 1;
this.position.copy( this.vertices ).applyMatrix4( this.object.matrixWorld );
} else {
if ( this.object.geometry ) {
if ( this.object.geometry.boundingSphere === null ) {
this.object.geometry.computeBoundingSphere();
}
this.radius = this.object.geometry.boundingSphere.radius;
this.position.copy( this.object.geometry.boundingSphere.center ).applyMatrix4( this.object.matrixWorld );
} else {
this.radius = this.object.boundRadius;
this.position.setFromMatrixPosition( this.object.matrixWorld );
}
}
this.radius = this.radius * Math.max( this.object.scale.x, this.object.scale.y, this.object.scale.z );
},
getFace3BoundingRadius: function ( object, face ) {
if ( face.centroid === undefined ) face.centroid = new THREE.Vector3();
var geometry = object.geometry || object,
vertices = geometry.vertices,
centroid = face.centroid,
va = vertices[ face.a ], vb = vertices[ face.b ], vc = vertices[ face.c ],
centroidToVert = this.utilVec31FaceBounds,
radius;
centroid.addVectors( va, vb ).add( vc ).divideScalar( 3 );
radius = Math.max( centroidToVert.subVectors( centroid, va ).length(), centroidToVert.subVectors( centroid, vb ).length(), centroidToVert.subVectors( centroid, vc ).length() );
return radius;
}
};
/*===================================================
node
=====================================================*/
THREE.OctreeNode = function ( parameters ) {
// utility
this.utilVec31Branch = new THREE.Vector3();
this.utilVec31Expand = new THREE.Vector3();
this.utilVec31Ray = new THREE.Vector3();
// handle parameters
parameters = parameters || {};
// store or create tree
if ( parameters.tree instanceof THREE.Octree ) {
this.tree = parameters.tree;
} else if ( parameters.parent instanceof THREE.OctreeNode !== true ) {
parameters.root = this;
this.tree = new THREE.Octree( parameters );
}
// basic properties
this.id = this.tree.nodeCount ++;
this.position = parameters.position instanceof THREE.Vector3 ? parameters.position : new THREE.Vector3();
this.radius = parameters.radius > 0 ? parameters.radius : 1;
this.indexOctant = parameters.indexOctant;
this.depth = 0;
// reset and assign parent
this.reset();
this.setParent( parameters.parent );
// additional properties
this.overlap = this.radius * this.tree.overlapPct;
this.radiusOverlap = this.radius + this.overlap;
this.left = this.position.x - this.radiusOverlap;
this.right = this.position.x + this.radiusOverlap;
this.bottom = this.position.y - this.radiusOverlap;
this.top = this.position.y + this.radiusOverlap;
this.back = this.position.z - this.radiusOverlap;
this.front = this.position.z + this.radiusOverlap;
// visual
if ( this.tree.scene ) {
this.visual = new THREE.Mesh( this.tree.visualGeometry, this.tree.visualMaterial );
this.visual.scale.set( this.radiusOverlap * 2, this.radiusOverlap * 2, this.radiusOverlap * 2 );
this.visual.position.copy( this.position );
this.tree.scene.add( this.visual );
}
};
THREE.OctreeNode.prototype = {
setParent: function ( parent ) {
// store new parent
if ( parent !== this && this.parent !== parent ) {
this.parent = parent;
// update properties
this.updateProperties();
}
},
updateProperties: function () {
var i, l;
// properties
if ( this.parent instanceof THREE.OctreeNode ) {
this.tree = this.parent.tree;
this.depth = this.parent.depth + 1;
} else {
this.depth = 0;
}
// cascade
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
this.nodesByIndex[ this.nodesIndices[ i ] ].updateProperties();
}
},
reset: function ( cascade, removeVisual ) {
var i, l,
node,
nodesIndices = this.nodesIndices || [],
nodesByIndex = this.nodesByIndex;
this.objects = [];
this.nodesIndices = [];
this.nodesByIndex = {};
// unset parent in nodes
for ( i = 0, l = nodesIndices.length; i < l; i ++ ) {
node = nodesByIndex[ nodesIndices[ i ] ];
node.setParent( undefined );
if ( cascade === true ) {
node.reset( cascade, removeVisual );
}
}
// visual
if ( removeVisual === true && this.visual && this.visual.parent ) {
this.visual.parent.remove( this.visual );
}
},
addNode: function ( node, indexOctant ) {
node.indexOctant = indexOctant;
if ( indexOfValue( this.nodesIndices, indexOctant ) === - 1 ) {
this.nodesIndices.push( indexOctant );
}
this.nodesByIndex[ indexOctant ] = node;
if ( node.parent !== this ) {
node.setParent( this );
}
},
removeNode: function ( indexOctant ) {
var index,
node;
index = indexOfValue( this.nodesIndices, indexOctant );
this.nodesIndices.splice( index, 1 );
node = node || this.nodesByIndex[ indexOctant ];
delete this.nodesByIndex[ indexOctant ];
if ( node.parent === this ) {
node.setParent( undefined );
}
},
addObject: function ( object ) {
var index,
indexOctant,
node;
// get object octant index
indexOctant = this.getOctantIndex( object );
// if object fully contained by an octant, add to subtree
if ( indexOctant > - 1 && this.nodesIndices.length > 0 ) {
node = this.branch( indexOctant );
node.addObject( object );
} else if ( indexOctant < - 1 && this.parent instanceof THREE.OctreeNode ) {
// if object lies outside bounds, add to parent node
this.parent.addObject( object );
} else {
// add to this objects list
index = indexOfValue( this.objects, object );
if ( index === - 1 ) {
this.objects.push( object );
}
// node reference
object.node = this;
// check if need to expand, split, or both
this.checkGrow();
}
},
addObjectWithoutCheck: function ( objects ) {
var i, l,
object;
for ( i = 0, l = objects.length; i < l; i ++ ) {
object = objects[ i ];
this.objects.push( object );
object.node = this;
}
},
removeObject: function ( object ) {
var i, l,
nodesRemovedFrom,
removeData;
// cascade through tree to find and remove object
removeData = this.removeObjectRecursive( object, { searchComplete: false, nodesRemovedFrom: [], objectsDataRemoved: [] } );
// if object removed, try to shrink the nodes it was removed from
nodesRemovedFrom = removeData.nodesRemovedFrom;
if ( nodesRemovedFrom.length > 0 ) {
for ( i = 0, l = nodesRemovedFrom.length; i < l; i ++ ) {
nodesRemovedFrom[ i ].shrink();
}
}
return removeData.objectsDataRemoved;
},
removeObjectRecursive: function ( object, removeData ) {
var i, l,
index = - 1,
objectData,
node,
objectRemoved;
// find index of object in objects list
// search and remove object data (fast)
if ( object instanceof THREE.OctreeObjectData ) {
// remove from this objects list
index = indexOfValue( this.objects, object );
if ( index !== - 1 ) {
this.objects.splice( index, 1 );
object.node = undefined;
removeData.objectsDataRemoved.push( object );
removeData.searchComplete = objectRemoved = true;
}
} else {
// search each object data for object and remove (slow)
for ( i = this.objects.length - 1; i >= 0; i -- ) {
objectData = this.objects[ i ];
if ( objectData.object === object ) {
this.objects.splice( i, 1 );
objectData.node = undefined;
removeData.objectsDataRemoved.push( objectData );
objectRemoved = true;
if ( ! objectData.faces && ! objectData.vertices ) {
removeData.searchComplete = true;
break;
}
}
}
}
// if object data removed and this is not on nodes removed from
if ( objectRemoved === true ) {
removeData.nodesRemovedFrom.push( this );
}
// if search not complete, search nodes
if ( removeData.searchComplete !== true ) {
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
// try removing object from node
removeData = node.removeObjectRecursive( object, removeData );
if ( removeData.searchComplete === true ) {
break;
}
}
}
return removeData;
},
checkGrow: function () {
// if object count above max
if ( this.objects.length > this.tree.objectsThreshold && this.tree.objectsThreshold > 0 ) {
this.grow();
}
},
grow: function () {
var indexOctant,
object,
objectsExpand = [],
objectsExpandOctants = [],
objectsSplit = [],
objectsSplitOctants = [],
objectsRemaining = [],
i, l;
// for each object
for ( i = 0, l = this.objects.length; i < l; i ++ ) {
object = this.objects[ i ];
// get object octant index
indexOctant = this.getOctantIndex( object );
// if lies within octant
if ( indexOctant > - 1 ) {
objectsSplit.push( object );
objectsSplitOctants.push( indexOctant );
} else if ( indexOctant < - 1 ) {
// lies outside radius
objectsExpand.push( object );
objectsExpandOctants.push( indexOctant );
} else {
// lies across bounds between octants
objectsRemaining.push( object );
}
}
// if has objects to split
if ( objectsSplit.length > 0 ) {
objectsRemaining = objectsRemaining.concat( this.split( objectsSplit, objectsSplitOctants ) );
}
// if has objects to expand
if ( objectsExpand.length > 0 ) {
objectsRemaining = objectsRemaining.concat( this.expand( objectsExpand, objectsExpandOctants ) );
}
// store remaining
this.objects = objectsRemaining;
// merge check
this.checkMerge();
},
split: function ( objects, octants ) {
var i, l,
indexOctant,
object,
node,
objectsRemaining;
// if not at max depth
if ( this.depth < this.tree.depthMax ) {
objects = objects || this.objects;
octants = octants || [];
objectsRemaining = [];
// for each object
for ( i = 0, l = objects.length; i < l; i ++ ) {
object = objects[ i ];
// get object octant index
indexOctant = octants[ i ];
// if object contained by octant, branch this tree
if ( indexOctant > - 1 ) {
node = this.branch( indexOctant );
node.addObject( object );
} else {
objectsRemaining.push( object );
}
}
// if all objects, set remaining as new objects
if ( objects === this.objects ) {
this.objects = objectsRemaining;
}
} else {
objectsRemaining = this.objects;
}
return objectsRemaining;
},
branch: function ( indexOctant ) {
var node,
overlap,
radius,
radiusOffset,
offset,
position;
// node exists
if ( this.nodesByIndex[ indexOctant ] instanceof THREE.OctreeNode ) {
node = this.nodesByIndex[ indexOctant ];
} else {
// properties
radius = ( this.radiusOverlap ) * 0.5;
overlap = radius * this.tree.overlapPct;
radiusOffset = radius - overlap;
offset = this.utilVec31Branch.set( indexOctant & 1 ? radiusOffset : - radiusOffset, indexOctant & 2 ? radiusOffset : - radiusOffset, indexOctant & 4 ? radiusOffset : - radiusOffset );
position = new THREE.Vector3().addVectors( this.position, offset );
// node
node = new THREE.OctreeNode( {
tree: this.tree,
parent: this,
position: position,
radius: radius,
indexOctant: indexOctant
} );
// store
this.addNode( node, indexOctant );
}
return node;
},
expand: function ( objects, octants ) {
var i, l,
object,
objectsRemaining,
objectsExpand,
indexOctant,
flagsOutside,
indexOutside,
indexOctantInverse,
iom = this.tree.INDEX_OUTSIDE_MAP,
indexOutsideCounts,
infoIndexOutside1,
infoIndexOutside2,
infoIndexOutside3,
indexOutsideBitwise1,
indexOutsideBitwise2,
infoPotential1,
infoPotential2,
infoPotential3,
indexPotentialBitwise1,
indexPotentialBitwise2,
octantX, octantY, octantZ,
overlap,
radius,
radiusOffset,
radiusParent,
overlapParent,
offset = this.utilVec31Expand,
position,
parent;
// handle max depth down tree
if ( this.tree.root.getDepthEnd() < this.tree.depthMax ) {
objects = objects || this.objects;
octants = octants || [];
objectsRemaining = [];
objectsExpand = [];
// reset counts
for ( i = 0, l = iom.length; i < l; i ++ ) {
iom[ i ].count = 0;
}
// for all outside objects, find outside octants containing most objects
for ( i = 0, l = objects.length; i < l; i ++ ) {
object = objects[ i ];
// get object octant index
indexOctant = octants[ i ] ;
// if object outside this, include in calculations
if ( indexOctant < - 1 ) {
// convert octant index to outside flags
flagsOutside = - indexOctant - this.tree.INDEX_OUTSIDE_OFFSET;
// check against bitwise flags
// x
if ( flagsOutside & this.tree.FLAG_POS_X ) {
iom[ this.tree.INDEX_OUTSIDE_POS_X ].count ++;
} else if ( flagsOutside & this.tree.FLAG_NEG_X ) {
iom[ this.tree.INDEX_OUTSIDE_NEG_X ].count ++;
}
// y
if ( flagsOutside & this.tree.FLAG_POS_Y ) {
iom[ this.tree.INDEX_OUTSIDE_POS_Y ].count ++;
} else if ( flagsOutside & this.tree.FLAG_NEG_Y ) {
iom[ this.tree.INDEX_OUTSIDE_NEG_Y ].count ++;
}
// z
if ( flagsOutside & this.tree.FLAG_POS_Z ) {
iom[ this.tree.INDEX_OUTSIDE_POS_Z ].count ++;
} else if ( flagsOutside & this.tree.FLAG_NEG_Z ) {
iom[ this.tree.INDEX_OUTSIDE_NEG_Z ].count ++;
}
// store in expand list
objectsExpand.push( object );
} else {
objectsRemaining.push( object );
}
}
// if objects to expand
if ( objectsExpand.length > 0 ) {
// shallow copy index outside map
indexOutsideCounts = iom.slice( 0 );
// sort outside index count so highest is first
indexOutsideCounts.sort( function ( a, b ) {
return b.count - a.count;
} );
// get highest outside indices
// first is first
infoIndexOutside1 = indexOutsideCounts[ 0 ];
indexOutsideBitwise1 = infoIndexOutside1.index | 1;
// second is ( one of next two bitwise OR 1 ) that is not opposite of ( first bitwise OR 1 )
infoPotential1 = indexOutsideCounts[ 1 ];
infoPotential2 = indexOutsideCounts[ 2 ];
infoIndexOutside2 = ( infoPotential1.index | 1 ) !== indexOutsideBitwise1 ? infoPotential1 : infoPotential2;
indexOutsideBitwise2 = infoIndexOutside2.index | 1;
// third is ( one of next three bitwise OR 1 ) that is not opposite of ( first or second bitwise OR 1 )
infoPotential1 = indexOutsideCounts[ 2 ];
infoPotential2 = indexOutsideCounts[ 3 ];
infoPotential3 = indexOutsideCounts[ 4 ];
indexPotentialBitwise1 = infoPotential1.index | 1;
indexPotentialBitwise2 = infoPotential2.index | 1;
infoIndexOutside3 = indexPotentialBitwise1 !== indexOutsideBitwise1 && indexPotentialBitwise1 !== indexOutsideBitwise2 ? infoPotential1 : indexPotentialBitwise2 !== indexOutsideBitwise1 && indexPotentialBitwise2 !== indexOutsideBitwise2 ? infoPotential2 : infoPotential3;
// get this octant normal based on outside octant indices
octantX = infoIndexOutside1.x + infoIndexOutside2.x + infoIndexOutside3.x;
octantY = infoIndexOutside1.y + infoIndexOutside2.y + infoIndexOutside3.y;
octantZ = infoIndexOutside1.z + infoIndexOutside2.z + infoIndexOutside3.z;
// get this octant indices based on octant normal
indexOctant = this.getOctantIndexFromPosition( octantX, octantY, octantZ );
indexOctantInverse = this.getOctantIndexFromPosition( - octantX, - octantY, - octantZ );
// properties
overlap = this.overlap;
radius = this.radius;
// radius of parent comes from reversing overlap of this, unless overlap percent is 0
radiusParent = this.tree.overlapPct > 0 ? overlap / ( ( 0.5 * this.tree.overlapPct ) * ( 1 + this.tree.overlapPct ) ) : radius * 2;
overlapParent = radiusParent * this.tree.overlapPct;
// parent offset is difference between radius + overlap of parent and child
radiusOffset = ( radiusParent + overlapParent ) - ( radius + overlap );
offset.set( indexOctant & 1 ? radiusOffset : - radiusOffset, indexOctant & 2 ? radiusOffset : - radiusOffset, indexOctant & 4 ? radiusOffset : - radiusOffset );
position = new THREE.Vector3().addVectors( this.position, offset );
// parent
parent = new THREE.OctreeNode( {
tree: this.tree,
position: position,
radius: radiusParent
} );
// set self as node of parent
parent.addNode( this, indexOctantInverse );
// set parent as root
this.tree.setRoot( parent );
// add all expand objects to parent
for ( i = 0, l = objectsExpand.length; i < l; i ++ ) {
this.tree.root.addObject( objectsExpand[ i ] );
}
}
// if all objects, set remaining as new objects
if ( objects === this.objects ) {
this.objects = objectsRemaining;
}
} else {
objectsRemaining = objects;
}
return objectsRemaining;
},
shrink: function () {
// merge check
this.checkMerge();
// contract check
this.tree.root.checkContract();
},
checkMerge: function () {
var nodeParent = this,
nodeMerge;
// traverse up tree as long as node + entire subtree's object count is under minimum
while ( nodeParent.parent instanceof THREE.OctreeNode && nodeParent.getObjectCountEnd() < this.tree.objectsThreshold ) {
nodeMerge = nodeParent;
nodeParent = nodeParent.parent;
}
// if parent node is not this, merge entire subtree into merge node
if ( nodeParent !== this ) {
nodeParent.merge( nodeMerge );
}
},
merge: function ( nodes ) {
var i, l,
j, k,
node;
// handle nodes
nodes = toArray( nodes );
for ( i = 0, l = nodes.length; i < l; i ++ ) {
node = nodes[ i ];
// gather node + all subtree objects
this.addObjectWithoutCheck( node.getObjectsEnd() );
// reset node + entire subtree
node.reset( true, true );
// remove node
this.removeNode( node.indexOctant, node );
}
// merge check
this.checkMerge();
},
checkContract: function () {
var i, l,
node,
nodeObjectsCount,
nodeHeaviest,
nodeHeaviestObjectsCount,
outsideHeaviestObjectsCount;
// find node with highest object count
if ( this.nodesIndices.length > 0 ) {
nodeHeaviestObjectsCount = 0;
outsideHeaviestObjectsCount = this.objects.length;
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
nodeObjectsCount = node.getObjectCountEnd();
outsideHeaviestObjectsCount += nodeObjectsCount;
if ( nodeHeaviest instanceof THREE.OctreeNode === false || nodeObjectsCount > nodeHeaviestObjectsCount ) {
nodeHeaviest = node;
nodeHeaviestObjectsCount = nodeObjectsCount;
}
}
// subtract heaviest count from outside count
outsideHeaviestObjectsCount -= nodeHeaviestObjectsCount;
// if should contract
if ( outsideHeaviestObjectsCount < this.tree.objectsThreshold && nodeHeaviest instanceof THREE.OctreeNode ) {
this.contract( nodeHeaviest );
}
}
},
contract: function ( nodeRoot ) {
var i, l,
node;
// handle all nodes
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
// if node is not new root
if ( node !== nodeRoot ) {
// add node + all subtree objects to root
nodeRoot.addObjectWithoutCheck( node.getObjectsEnd() );
// reset node + entire subtree
node.reset( true, true );
}
}
// add own objects to root
nodeRoot.addObjectWithoutCheck( this.objects );
// reset self
this.reset( false, true );
// set new root
this.tree.setRoot( nodeRoot );
// contract check on new root
nodeRoot.checkContract();
},
getOctantIndex: function ( objectData ) {
var i, l,
positionObj,
radiusObj,
position = this.position,
radiusOverlap = this.radiusOverlap,
overlap = this.overlap,
deltaX, deltaY, deltaZ,
distX, distY, distZ,
distance,
indexOctant = 0;
// handle type
if ( objectData instanceof THREE.OctreeObjectData ) {
radiusObj = objectData.radius;
positionObj = objectData.position;
// update object data position last
objectData.positionLast.copy( positionObj );
} else if ( objectData instanceof THREE.OctreeNode ) {
positionObj = objectData.position;
radiusObj = 0;
}
// find delta and distance
deltaX = positionObj.x - position.x;
deltaY = positionObj.y - position.y;
deltaZ = positionObj.z - position.z;
distX = Math.abs( deltaX );
distY = Math.abs( deltaY );
distZ = Math.abs( deltaZ );
distance = Math.max( distX, distY, distZ );
// if outside, use bitwise flags to indicate on which sides object is outside of
if ( distance + radiusObj > radiusOverlap ) {
// x
if ( distX + radiusObj > radiusOverlap ) {
indexOctant = indexOctant ^ ( deltaX > 0 ? this.tree.FLAG_POS_X : this.tree.FLAG_NEG_X );
}
// y
if ( distY + radiusObj > radiusOverlap ) {
indexOctant = indexOctant ^ ( deltaY > 0 ? this.tree.FLAG_POS_Y : this.tree.FLAG_NEG_Y );
}
// z
if ( distZ + radiusObj > radiusOverlap ) {
indexOctant = indexOctant ^ ( deltaZ > 0 ? this.tree.FLAG_POS_Z : this.tree.FLAG_NEG_Z );
}
objectData.indexOctant = - indexOctant - this.tree.INDEX_OUTSIDE_OFFSET;
return objectData.indexOctant;
}
// return octant index from delta xyz
if ( deltaX - radiusObj > - overlap ) {
// x right
indexOctant = indexOctant | 1;
} else if ( ! ( deltaX + radiusObj < overlap ) ) {
// x left
objectData.indexOctant = this.tree.INDEX_INSIDE_CROSS;
return objectData.indexOctant;
}
if ( deltaY - radiusObj > - overlap ) {
// y right
indexOctant = indexOctant | 2;
} else if ( ! ( deltaY + radiusObj < overlap ) ) {
// y left
objectData.indexOctant = this.tree.INDEX_INSIDE_CROSS;
return objectData.indexOctant;
}
if ( deltaZ - radiusObj > - overlap ) {
// z right
indexOctant = indexOctant | 4;
} else if ( ! ( deltaZ + radiusObj < overlap ) ) {
// z left
objectData.indexOctant = this.tree.INDEX_INSIDE_CROSS;
return objectData.indexOctant;
}
objectData.indexOctant = indexOctant;
return objectData.indexOctant;
},
getOctantIndexFromPosition: function ( x, y, z ) {
var indexOctant = 0;
if ( x > 0 ) {
indexOctant = indexOctant | 1;
}
if ( y > 0 ) {
indexOctant = indexOctant | 2;
}
if ( z > 0 ) {
indexOctant = indexOctant | 4;
}
return indexOctant;
},
search: function ( position, radius, objects, direction, directionPct ) {
var i, l,
node,
intersects;
// test intersects by parameters
if ( direction ) {
intersects = this.intersectRay( position, direction, radius, directionPct );
} else {
intersects = this.intersectSphere( position, radius );
}
// if intersects
if ( intersects === true ) {
// gather objects
objects = objects.concat( this.objects );
// search subtree
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
objects = node.search( position, radius, objects, direction );
}
}
return objects;
},
intersectSphere: function ( position, radius ) {
var distance = radius * radius,
px = position.x,
py = position.y,
pz = position.z;
if ( px < this.left ) {
distance -= Math.pow( px - this.left, 2 );
} else if ( px > this.right ) {
distance -= Math.pow( px - this.right, 2 );
}
if ( py < this.bottom ) {
distance -= Math.pow( py - this.bottom, 2 );
} else if ( py > this.top ) {
distance -= Math.pow( py - this.top, 2 );
}
if ( pz < this.back ) {
distance -= Math.pow( pz - this.back, 2 );
} else if ( pz > this.front ) {
distance -= Math.pow( pz - this.front, 2 );
}
return distance >= 0;
},
intersectRay: function ( origin, direction, distance, directionPct ) {
if ( typeof directionPct === 'undefined' ) {
directionPct = this.utilVec31Ray.set( 1, 1, 1 ).divide( direction );
}
var t1 = ( this.left - origin.x ) * directionPct.x,
t2 = ( this.right - origin.x ) * directionPct.x,
t3 = ( this.bottom - origin.y ) * directionPct.y,
t4 = ( this.top - origin.y ) * directionPct.y,
t5 = ( this.back - origin.z ) * directionPct.z,
t6 = ( this.front - origin.z ) * directionPct.z,
tmax = Math.min( Math.min( Math.max( t1, t2 ), Math.max( t3, t4 ) ), Math.max( t5, t6 ) ),
tmin;
// ray would intersect in reverse direction, i.e. this is behind ray
if ( tmax < 0 ) {
return false;
}
tmin = Math.max( Math.max( Math.min( t1, t2 ), Math.min( t3, t4 ) ), Math.min( t5, t6 ) );
// if tmin > tmax or tmin > ray distance, ray doesn't intersect AABB
if ( tmin > tmax || tmin > distance ) {
return false;
}
return true;
},
getDepthEnd: function ( depth ) {
var i, l,
node;
if ( this.nodesIndices.length > 0 ) {
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
depth = node.getDepthEnd( depth );
}
} else {
depth = ! depth || this.depth > depth ? this.depth : depth;
}
return depth;
},
getNodeCountEnd: function () {
return this.tree.root.getNodeCountRecursive() + 1;
},
getNodeCountRecursive: function () {
var i, l,
count = this.nodesIndices.length;
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
count += this.nodesByIndex[ this.nodesIndices[ i ] ].getNodeCountRecursive();
}
return count;
},
getObjectsEnd: function ( objects ) {
var i, l,
node;
objects = ( objects || [] ).concat( this.objects );
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
objects = node.getObjectsEnd( objects );
}
return objects;
},
getObjectCountEnd: function () {
var i, l,
count = this.objects.length;
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
count += this.nodesByIndex[ this.nodesIndices[ i ] ].getObjectCountEnd();
}
return count;
},
getObjectCountStart: function () {
var count = this.objects.length,
parent = this.parent;
while ( parent instanceof THREE.OctreeNode ) {
count += parent.objects.length;
parent = parent.parent;
}
return count;
},
toConsole: function ( space ) {
var i, l,
node,
spaceAddition = ' ';
space = typeof space === 'string' ? space : spaceAddition;
console.log( ( this.parent ? space + ' octree NODE > ' : ' octree ROOT > ' ), this, ' // id: ', this.id, ' // indexOctant: ', this.indexOctant, ' // position: ', this.position.x, this.position.y, this.position.z, ' // radius: ', this.radius, ' // depth: ', this.depth );
console.log( ( this.parent ? space + ' ' : ' ' ), '+ objects ( ', this.objects.length, ' ) ', this.objects );
console.log( ( this.parent ? space + ' ' : ' ' ), '+ children ( ', this.nodesIndices.length, ' )', this.nodesIndices, this.nodesByIndex );
for ( i = 0, l = this.nodesIndices.length; i < l; i ++ ) {
node = this.nodesByIndex[ this.nodesIndices[ i ] ];
node.toConsole( space + spaceAddition );
}
}
};
/*===================================================
raycaster additional functionality
=====================================================*/
THREE.Raycaster.prototype.intersectOctreeObject = function ( object, recursive ) {
var intersects,
octreeObject,
facesAll,
facesSearch;
if ( object.object instanceof THREE.Object3D ) {
octreeObject = object;
object = octreeObject.object;
// temporarily replace object geometry's faces with octree object faces
facesSearch = octreeObject.faces;
facesAll = object.geometry.faces;
if ( facesSearch.length > 0 ) {
object.geometry.faces = facesSearch;
}
// intersect
intersects = this.intersectObject( object, recursive );
// revert object geometry's faces
if ( facesSearch.length > 0 ) {
object.geometry.faces = facesAll;
}
} else {
intersects = this.intersectObject( object, recursive );
}
return intersects;
};
THREE.Raycaster.prototype.intersectOctreeObjects = function ( objects, recursive ) {
var i, il,
intersects = [];
for ( i = 0, il = objects.length; i < il; i ++ ) {
intersects = intersects.concat( this.intersectOctreeObject( objects[ i ], recursive ) );
}
return intersects;
};
}( THREE ) );