Accueil / npm / three@0.186.1 / examples / jsm / math / Octree.js
Octree.js
import {
Box3,
Line3,
Plane,
Sphere,
Triangle,
Vector3,
Layers
} from 'three';
import { Capsule } from '../math/Capsule.js';
const _v1 = new Vector3();
const _v2 = new Vector3();
const _point1 = new Vector3();
const _point2 = new Vector3();
const _plane = new Plane();
const _line1 = new Line3();
const _line2 = new Line3();
const _box = new Box3();
const _sphere = new Sphere();
const _capsule = new Capsule();
const _center = new Vector3();
const _temp1 = new Vector3();
const _temp2 = new Vector3();
const _temp3 = new Vector3();
const EPS = 1e-10;
function lineToLineClosestPoints( line1, line2, target1 = null, target2 = null ) {
const r = _temp1.copy( line1.end ).sub( line1.start );
const s = _temp2.copy( line2.end ).sub( line2.start );
const w = _temp3.copy( line2.start ).sub( line1.start );
const a = r.dot( s ),
b = r.dot( r ),
c = s.dot( s ),
d = s.dot( w ),
e = r.dot( w );
let t1, t2;
const divisor = b * c - a * a;
if ( Math.abs( divisor ) < EPS ) {
const d1 = - d / c;
const d2 = ( a - d ) / c;
if ( Math.abs( d1 - 0.5 ) < Math.abs( d2 - 0.5 ) ) {
t1 = 0;
t2 = d1;
} else {
t1 = 1;
t2 = d2;
}
} else {
t1 = ( d * a + e * c ) / divisor;
t2 = ( t1 * a - d ) / c;
}
t2 = Math.max( 0, Math.min( 1, t2 ) );
t1 = Math.max( 0, Math.min( 1, t1 ) );
if ( target1 ) {
target1.copy( r ).multiplyScalar( t1 ).add( line1.start );
}
if ( target2 ) {
target2.copy( s ).multiplyScalar( t2 ).add( line2.start );
}
}
/**
* An octree is a hierarchical tree data structure used to partition a three-dimensional
* space by recursively subdividing it into eight octants.
*
* This particular implementation can have up to sixteen levels and stores up to eight triangles
* in leaf nodes.
*
* `Octree` can be used in games to compute collision between the game world and colliders from
* the player or other dynamic 3D objects.
*
*
* ```js
* const octree = new Octree().fromGraphNode( scene );
* const result = octree.capsuleIntersect( playerCollider ); // collision detection
* ```
*
* @three_import import { Octree } from 'three/addons/math/Octree.js';
*/
class Octree {
/**
* Constructs a new Octree.
*
* @param {Box3} [box] - The base box with enclose the entire Octree.
*/
constructor( box ) {
/**
* The base box with enclose the entire Octree.
*
* @type {Box3}
*/
this.box = box;
/**
* The bounds of the Octree. Compared to {@link Octree#box}, no
* margin is applied.
*
* @type {Box3}
*/
this.bounds = new Box3();
/**
* Can by used for layers configuration for refine testing.
*
* @type {Layers}
*/
this.layers = new Layers();
/**
* The number of triangles a leaf can store before it is split.
*
* @type {number}
* @default 8
*/
this.trianglesPerLeaf = 8;
/**
* The maximum level of the Octree. It defines the maximum
* hierarchical depth of the data structure.
*
* @type {number}
* @default 16
*/
this.maxLevel = 16;
// private
this.subTrees = [];
this.triangles = [];
}
/**
* Adds the given triangle to the Octree. The triangle vertices are clamped if they exceed
* the bounds of the Octree.
*
* @param {Triangle} triangle - The triangle to add.
* @return {Octree} A reference to this Octree.
*/
addTriangle( triangle ) {
this.bounds.min.x = Math.min( this.bounds.min.x, triangle.a.x, triangle.b.x, triangle.c.x );
this.bounds.min.y = Math.min( this.bounds.min.y, triangle.a.y, triangle.b.y, triangle.c.y );
this.bounds.min.z = Math.min( this.bounds.min.z, triangle.a.z, triangle.b.z, triangle.c.z );
this.bounds.max.x = Math.max( this.bounds.max.x, triangle.a.x, triangle.b.x, triangle.c.x );
this.bounds.max.y = Math.max( this.bounds.max.y, triangle.a.y, triangle.b.y, triangle.c.y );
this.bounds.max.z = Math.max( this.bounds.max.z, triangle.a.z, triangle.b.z, triangle.c.z );
this.triangles.push( triangle );
return this;
}
/**
* Prepares {@link Octree#box} for the build.
*
* @return {Octree} A reference to this Octree.
*/
calcBox() {
this.box = this.bounds.clone();
// offset small amount to account for regular grid
this.box.min.x -= 0.01;
this.box.min.y -= 0.01;
this.box.min.z -= 0.01;
return this;
}
/**
* Splits the Octree. This method is used recursively when
* building the Octree.
*
* @param {number} level - The current level.
* @return {Octree} A reference to this Octree.
*/
split( level ) {
if ( ! this.box ) return;
const subTrees = [];
const halfsize = _v2.copy( this.box.max ).sub( this.box.min ).multiplyScalar( 0.5 );
for ( let x = 0; x < 2; x ++ ) {
for ( let y = 0; y < 2; y ++ ) {
for ( let z = 0; z < 2; z ++ ) {
const box = new Box3();
const v = _v1.set( x, y, z );
box.min.copy( this.box.min ).add( v.multiply( halfsize ) );
box.max.copy( box.min ).add( halfsize );
subTrees.push( new Octree( box ) );
}
}
}
let triangle;
while ( triangle = this.triangles.pop() ) {
for ( let i = 0; i < subTrees.length; i ++ ) {
if ( subTrees[ i ].box.intersectsTriangle( triangle ) ) {
subTrees[ i ].triangles.push( triangle );
}
}
}
for ( let i = 0; i < subTrees.length; i ++ ) {
const len = subTrees[ i ].triangles.length;
if ( len > this.trianglesPerLeaf && level < this.maxLevel ) {
subTrees[ i ].split( level + 1 );
}
if ( len !== 0 ) {
this.subTrees.push( subTrees[ i ] );
}
}
return this;
}
/**
* Builds the Octree.
*
* @return {Octree} A reference to this Octree.
*/
build() {
this.calcBox();
this.split( 0 );
return this;
}
/**
* Computes the triangles that potentially intersect with the given ray.
*
* @param {Ray} ray - The ray to test.
* @param {Array<Triangle>} triangles - The target array that holds the triangles.
*/
getRayTriangles( ray, triangles ) {
for ( let i = 0; i < this.subTrees.length; i ++ ) {
const subTree = this.subTrees[ i ];
if ( ! ray.intersectsBox( subTree.box ) ) continue;
if ( subTree.triangles.length > 0 ) {
for ( let j = 0; j < subTree.triangles.length; j ++ ) {
if ( triangles.indexOf( subTree.triangles[ j ] ) === - 1 ) triangles.push( subTree.triangles[ j ] );
}
} else {
subTree.getRayTriangles( ray, triangles );
}
}
}
/**
* Computes the intersection between the given capsule and triangle.
*
* @param {Capsule} capsule - The capsule to test.
* @param {Triangle} triangle - The triangle to test.
* @return {Object|false} The intersection object. If no intersection
* is detected, the method returns `false`.
*/
triangleCapsuleIntersect( capsule, triangle ) {
triangle.getPlane( _plane );
const d1 = _plane.distanceToPoint( capsule.start ) - capsule.radius;
const d2 = _plane.distanceToPoint( capsule.end ) - capsule.radius;
if ( ( d1 > 0 && d2 > 0 ) || ( d1 < - capsule.radius && d2 < - capsule.radius ) ) {
return false;
}
const delta = Math.abs( d1 / ( Math.abs( d1 ) + Math.abs( d2 ) ) );
const intersectPoint = _v1.copy( capsule.start ).lerp( capsule.end, delta );
if ( triangle.containsPoint( intersectPoint ) ) {
return { normal: _plane.normal.clone(), point: intersectPoint.clone(), depth: Math.abs( Math.min( d1, d2 ) ) };
}
const r2 = capsule.radius * capsule.radius;
const line1 = _line1.set( capsule.start, capsule.end );
const lines = [
[ triangle.a, triangle.b ],
[ triangle.b, triangle.c ],
[ triangle.c, triangle.a ]
];
for ( let i = 0; i < lines.length; i ++ ) {
const line2 = _line2.set( lines[ i ][ 0 ], lines[ i ][ 1 ] );
lineToLineClosestPoints( line1, line2, _point1, _point2 );
if ( _point1.distanceToSquared( _point2 ) < r2 ) {
return {
normal: _point1.clone().sub( _point2 ).normalize(),
point: _point2.clone(),
depth: capsule.radius - _point1.distanceTo( _point2 )
};
}
}
return false;
}
/**
* Computes the intersection between the given bounding box and triangle.
*
* @param {Box3} box - The bounding box to test.
* @param {Triangle} triangle - The triangle to test.
* @return {Object|false} The intersection object. If no intersection
* is detected, the method returns `false`.
*/
triangleBoxIntersect( box, triangle ) {
// cheap check
if ( Math.max( triangle.a.x, triangle.b.x, triangle.c.x ) < box.min.x ||
Math.min( triangle.a.x, triangle.b.x, triangle.c.x ) > box.max.x ||
Math.max( triangle.a.y, triangle.b.y, triangle.c.y ) < box.min.y ||
Math.min( triangle.a.y, triangle.b.y, triangle.c.y ) > box.max.y ||
Math.max( triangle.a.z, triangle.b.z, triangle.c.z ) < box.min.z ||
Math.min( triangle.a.z, triangle.b.z, triangle.c.z ) > box.max.z ) {
return false;
}
// expensive check
if ( ! box.intersectsTriangle( triangle ) ) return false;
// there is an intersection, now compute collision data
triangle.getPlane( _plane );
// determine which corner of the box is "deepest" into the plane
_v1.x = ( _plane.normal.x > 0 ) ? box.min.x : box.max.x;
_v1.y = ( _plane.normal.y > 0 ) ? box.min.y : box.max.y;
_v1.z = ( _plane.normal.z > 0 ) ? box.min.z : box.max.z;
// Calculate the distance from the plane to that corner (the distance will be negative
// because of the intersection)
const distance = _plane.distanceToPoint( _v1 );
const intersection = {
depth: - distance, // Flip sign so depth is positive
normal: _plane.normal.clone(),
point: _v1.clone()
};
// project the point onto the triangle surface
intersection.point.addScaledVector( intersection.normal, distance );
return intersection;
}
/**
* Computes the intersection between the given sphere and triangle.
*
* @param {Sphere} sphere - The sphere to test.
* @param {Triangle} triangle - The triangle to test.
* @return {Object|false} The intersection object. If no intersection
* is detected, the method returns `false`.
*/
triangleSphereIntersect( sphere, triangle ) {
triangle.getPlane( _plane );
if ( ! sphere.intersectsPlane( _plane ) ) return false;
const depth = Math.abs( _plane.distanceToSphere( sphere ) );
const r2 = sphere.radius * sphere.radius - depth * depth;
const plainPoint = _plane.projectPoint( sphere.center, _v1 );
if ( triangle.containsPoint( sphere.center ) ) {
return { normal: _plane.normal.clone(), point: plainPoint.clone(), depth: Math.abs( _plane.distanceToSphere( sphere ) ) };
}
const lines = [
[ triangle.a, triangle.b ],
[ triangle.b, triangle.c ],
[ triangle.c, triangle.a ]
];
for ( let i = 0; i < lines.length; i ++ ) {
_line1.set( lines[ i ][ 0 ], lines[ i ][ 1 ] );
_line1.closestPointToPoint( plainPoint, true, _v2 );
const d = _v2.distanceToSquared( sphere.center );
if ( d < r2 ) {
return { normal: sphere.center.clone().sub( _v2 ).normalize(), point: _v2.clone(), depth: sphere.radius - Math.sqrt( d ) };
}
}
return false;
}
/**
* Computes the triangles that potentially intersect with the given bounding sphere.
*
* @param {Sphere} sphere - The sphere to test.
* @param {Array<Triangle>} triangles - The target array that holds the triangles.
*/
getSphereTriangles( sphere, triangles ) {
for ( let i = 0; i < this.subTrees.length; i ++ ) {
const subTree = this.subTrees[ i ];
if ( ! sphere.intersectsBox( subTree.box ) ) continue;
if ( subTree.triangles.length > 0 ) {
for ( let j = 0; j < subTree.triangles.length; j ++ ) {
if ( triangles.indexOf( subTree.triangles[ j ] ) === - 1 ) triangles.push( subTree.triangles[ j ] );
}
} else {
subTree.getSphereTriangles( sphere, triangles );
}
}
}
/**
* Computes the triangles that potentially intersect with the given bounding box.
*
* @param {Box3} box - The bounding box.
* @param {Array<Triangle>} triangles - The target array that holds the triangles.
*/
getBoxTriangles( box, triangles ) {
for ( let i = 0; i < this.subTrees.length; i ++ ) {
const subTree = this.subTrees[ i ];
if ( ! box.intersectsBox( subTree.box ) ) continue;
if ( subTree.triangles.length > 0 ) {
for ( let j = 0; j < subTree.triangles.length; j ++ ) {
if ( triangles.indexOf( subTree.triangles[ j ] ) === - 1 ) triangles.push( subTree.triangles[ j ] );
}
} else {
subTree.getBoxTriangles( box, triangles );
}
}
}
/**
* Computes the triangles that potentially intersect with the given capsule.
*
* @param {Capsule} capsule - The capsule to test.
* @param {Array<Triangle>} triangles - The target array that holds the triangles.
*/
getCapsuleTriangles( capsule, triangles ) {
for ( let i = 0; i < this.subTrees.length; i ++ ) {
const subTree = this.subTrees[ i ];
if ( ! capsule.intersectsBox( subTree.box ) ) continue;
if ( subTree.triangles.length > 0 ) {
for ( let j = 0; j < subTree.triangles.length; j ++ ) {
if ( triangles.indexOf( subTree.triangles[ j ] ) === - 1 ) triangles.push( subTree.triangles[ j ] );
}
} else {
subTree.getCapsuleTriangles( capsule, triangles );
}
}
}
/**
* Performs a bounding box intersection test with this Octree.
*
* @param {Box3} box - The bounding box to test.
* @return {Object|boolean} The intersection object. If no intersection
* is detected, the method returns `false`.
*/
boxIntersect( box ) {
_box.copy( box );
const triangles = [];
let result, hit = false;
this.getBoxTriangles( box, triangles );
for ( let i = 0; i < triangles.length; i ++ ) {
if ( result = this.triangleBoxIntersect( _box, triangles[ i ] ) ) {
hit = true;
_box.translate( result.normal.multiplyScalar( result.depth ) );
}
}
if ( hit ) {
const collisionVector = _box.getCenter( _center ).sub( box.getCenter( _v1 ) );
const depth = collisionVector.length();
return { normal: collisionVector.normalize(), depth: depth };
}
return false;
}
/**
* Performs a bounding sphere intersection test with this Octree.
*
* @param {Sphere} sphere - The bounding sphere to test.
* @return {Object|boolean} The intersection object. If no intersection
* is detected, the method returns `false`.
*/
sphereIntersect( sphere ) {
_sphere.copy( sphere );
const triangles = [];
let result, hit = false;
this.getSphereTriangles( sphere, triangles );
for ( let i = 0; i < triangles.length; i ++ ) {
if ( result = this.triangleSphereIntersect( _sphere, triangles[ i ] ) ) {
hit = true;
_sphere.center.add( result.normal.multiplyScalar( result.depth ) );
}
}
if ( hit ) {
const collisionVector = _sphere.center.clone().sub( sphere.center );
const depth = collisionVector.length();
return { normal: collisionVector.normalize(), depth: depth };
}
return false;
}
/**
* Performs a capsule intersection test with this Octree.
*
* @param {Capsule} capsule - The capsule to test.
* @return {Object|boolean} The intersection object. If no intersection
* is detected, the method returns `false`.
*/
capsuleIntersect( capsule ) {
_capsule.copy( capsule );
const triangles = [];
let result, hit = false;
this.getCapsuleTriangles( _capsule, triangles );
for ( let i = 0; i < triangles.length; i ++ ) {
if ( result = this.triangleCapsuleIntersect( _capsule, triangles[ i ] ) ) {
hit = true;
_capsule.translate( result.normal.multiplyScalar( result.depth ) );
}
}
if ( hit ) {
const collisionVector = _capsule.getCenter( _center ).sub( capsule.getCenter( _v1 ) );
const depth = collisionVector.length();
return { normal: collisionVector.normalize(), depth: depth };
}
return false;
}
/**
* Performs a ray intersection test with this Octree.
*
* @param {Ray} ray - The ray to test.
* @return {Object|boolean} The nearest intersection object. If no intersection
* is detected, the method returns `false`.
*/
rayIntersect( ray ) {
const triangles = [];
let triangle, position, distance = 1e100;
this.getRayTriangles( ray, triangles );
for ( let i = 0; i < triangles.length; i ++ ) {
const result = ray.intersectTriangle( triangles[ i ].a, triangles[ i ].b, triangles[ i ].c, true, _v1 );
if ( result ) {
const newdistance = result.sub( ray.origin ).length();
if ( distance > newdistance ) {
position = result.clone().add( ray.origin );
distance = newdistance;
triangle = triangles[ i ];
}
}
}
return distance < 1e100 ? { distance: distance, triangle: triangle, position: position } : false;
}
/**
* Constructs the Octree from the given 3D object.
*
* @param {Object3D} group - The scene graph node.
* @return {Octree} A reference to this Octree.
*/
fromGraphNode( group ) {
group.updateWorldMatrix( true, true );
group.traverse( ( obj ) => {
if ( obj.isMesh === true ) {
if ( this.layers.test( obj.layers ) ) {
let geometry, isTemp = false;
if ( obj.geometry.index !== null ) {
isTemp = true;
geometry = obj.geometry.toNonIndexed();
} else {
geometry = obj.geometry;
}
const positionAttribute = geometry.getAttribute( 'position' );
for ( let i = 0; i < positionAttribute.count; i += 3 ) {
const v1 = new Vector3().fromBufferAttribute( positionAttribute, i );
const v2 = new Vector3().fromBufferAttribute( positionAttribute, i + 1 );
const v3 = new Vector3().fromBufferAttribute( positionAttribute, i + 2 );
v1.applyMatrix4( obj.matrixWorld );
v2.applyMatrix4( obj.matrixWorld );
v3.applyMatrix4( obj.matrixWorld );
this.addTriangle( new Triangle( v1, v2, v3 ) );
}
if ( isTemp ) {
geometry.dispose();
}
}
}
} );
this.build();
return this;
}
/**
* Clears the Octree by making it empty.
*
* @return {Octree} A reference to this Octree.
*/
clear() {
this.box = null;
this.bounds.makeEmpty();
this.subTrees.length = 0;
this.triangles.length = 0;
return this;
}
}
export { Octree };