import { AABB } from './AABB.js';
import { Vector3 } from './Vector3.js';
const v1 = new Vector3();
const v2 = new Vector3();
const v3 = new Vector3();
const xAxis = new Vector3( 1, 0, 0 );
const yAxis = new Vector3( 0, 1, 0 );
const zAxis = new Vector3( 0, 0, 1 );
const triangle = { a: new Vector3(), b: new Vector3(), c: new Vector3() };
const intersection = new Vector3();
const intersections = new Array();
/**
* Class representing a bounding volume hierarchy. The current implementation
* represents single BVH nodes as AABBs. It accepts arbitrary branching factors
* and can subdivide the given geometry until a defined hierarchy depth has been reached.
* Besides, the hierarchy construction is performed top-down and the algorithm only
* performs splits along the cardinal axes.
*
* Reference: Bounding Volume Hierarchies in Real-Time Collision Detection
* by Christer Ericson (chapter 6).
*
* @author {@link https://github.com/robp94|robp94}
* @author {@link https://github.com/Mugen87|Mugen87}
*/
class BVH {
/**
* Constructs a new BVH.
*
* @param {Number} branchingFactor - The branching factor.
* @param {Number} primitivesPerNode - The minimum amount of primitives per BVH node.
* @param {Number} depth - The maximum hierarchical depth.
*/
constructor( branchingFactor = 2, primitivesPerNode = 1, depth = 10 ) {
/**
* The branching factor (how many nodes per level).
* @type {Number}
* @default 2
*/
this.branchingFactor = branchingFactor;
/**
* The minimum amount of primitives per BVH node.
* @type {Number}
* @default 10
*/
this.primitivesPerNode = primitivesPerNode;
/**
* The maximum hierarchical depth.
* @type {Number}
* @default 10
*/
this.depth = depth;
/**
* The root BVH node.
* @type {BVHNode}
* @default null
*/
this.root = null;
}
/**
* Computes a BVH for the given mesh geometry.
*
* @param {MeshGeometry} geometry - The mesh geometry.
* @return {BVH} A reference to this BVH.
*/
fromMeshGeometry( geometry ) {
this.root = new BVHNode();
// primitives
if ( geometry.indices !== null ) geometry = geometry.toTriangleSoup();
const vertices = geometry.vertices;
for ( let i = 0, l = vertices.length; i < l; i ++ ) {
this.root.primitives.push( vertices[ i ] );
}
// centroids
const primitives = this.root.primitives;
for ( let i = 0, l = primitives.length; i < l; i += 9 ) {
v1.fromArray( primitives, i );
v2.fromArray( primitives, i + 3 );
v3.fromArray( primitives, i + 6 );
v1.add( v2 ).add( v3 ).divideScalar( 3 );
this.root.centroids.push( v1.x, v1.y, v1.z );
}
// build
this.root.build( this.branchingFactor, this.primitivesPerNode, this.depth, 1 );
return this;
}
/**
* Executes the given callback for each node of the BVH.
*
* @param {Function} callback - The callback to execute.
* @return {BVH} A reference to this BVH.
*/
traverse( callback ) {
this.root.traverse( callback );
return this;
}
}
/**
* A single node in a bounding volume hierarchy (BVH).
*
* @author {@link https://github.com/robp94|robp94}
* @author {@link https://github.com/Mugen87|Mugen87}
*/
class BVHNode {
/**
* Constructs a BVH node.
*/
constructor() {
/**
* The parent BVH node.
* @type {BVHNode}
* @default null
*/
this.parent = null;
/**
* The child BVH nodes.
* @type {Array<BVHNode>}
*/
this.children = new Array();
/**
* The bounding volume of this BVH node.
* @type {AABB}
*/
this.boundingVolume = new AABB();
/**
* The primitives (triangles) of this BVH node.
* Only filled for leaf nodes.
* @type {Array<Number>}
*/
this.primitives = new Array();
/**
* The centroids of the node's triangles.
* Only filled for leaf nodes.
* @type {Array<Number>}
*/
this.centroids = new Array();
}
/**
* Returns true if this BVH node is a root node.
*
* @return {Boolean} Whether this BVH node is a root node or not.
*/
root() {
return this.parent === null;
}
/**
* Returns true if this BVH node is a leaf node.
*
* @return {Boolean} Whether this BVH node is a leaf node or not.
*/
leaf() {
return this.children.length === 0;
}
/**
* Returns the depth of this BVH node in its hierarchy.
*
* @return {Number} The hierarchical depth of this BVH node.
*/
getDepth() {
let depth = 0;
let parent = this.parent;
while ( parent !== null ) {
parent = parent.parent;
depth ++;
}
return depth;
}
/**
* Executes the given callback for this BVH node and its ancestors.
*
* @param {Function} callback - The callback to execute.
* @return {BVHNode} A reference to this BVH node.
*/
traverse( callback ) {
callback( this );
for ( let i = 0, l = this.children.length; i < l; i ++ ) {
this.children[ i ].traverse( callback );
}
return this;
}
/**
* Builds this BVH node. That means the respective bounding volume
* is computed and the node's primitives are distributed under new child nodes.
* This only happens if the maximum hierarchical depth is not yet reached and
* the node does contain enough primitives required for a split.
*
* @param {Number} branchingFactor - The branching factor.
* @param {Number} primitivesPerNode - The minimum amount of primitives per BVH node.
* @param {Number} maxDepth - The maximum hierarchical depth.
* @param {Number} currentDepth - The current hierarchical depth.
* @return {BVHNode} A reference to this BVH node.
*/
build( branchingFactor, primitivesPerNode, maxDepth, currentDepth ) {
this.computeBoundingVolume();
// check depth and primitive count
const primitiveCount = this.primitives.length / 9;
const newPrimitiveCount = Math.floor( primitiveCount / branchingFactor );
if ( ( currentDepth <= maxDepth ) && ( newPrimitiveCount >= primitivesPerNode ) ) {
// split (distribute primitives on new child BVH nodes)
this.split( branchingFactor );
// proceed with build on the next hierarchy level
for ( let i = 0; i < branchingFactor; i ++ ) {
this.children[ i ].build( branchingFactor, primitivesPerNode, maxDepth, currentDepth + 1 );
}
}
return this;
}
/**
* Computes the AABB for this BVH node.
*
* @return {BVHNode} A reference to this BVH node.
*/
computeBoundingVolume() {
const primitives = this.primitives;
const aabb = this.boundingVolume;
// compute AABB
aabb.min.set( Infinity, Infinity, Infinity );
aabb.max.set( - Infinity, - Infinity, - Infinity );
for ( let i = 0, l = primitives.length; i < l; i += 3 ) {
v1.x = primitives[ i ];
v1.y = primitives[ i + 1 ];
v1.z = primitives[ i + 2 ];
aabb.expand( v1 );
}
return this;
}
/**
* Computes the split axis. Right now, only the cardinal axes
* are potential split axes.
*
* @return {Vector3} The split axis.
*/
computeSplitAxis() {
let maxX, maxY, maxZ = maxY = maxX = - Infinity;
let minX, minY, minZ = minY = minX = Infinity;
const centroids = this.centroids;
for ( let i = 0, l = centroids.length; i < l; i += 3 ) {
const x = centroids[ i ];
const y = centroids[ i + 1 ];
const z = centroids[ i + 2 ];
if ( x > maxX ) {
maxX = x;
}
if ( y > maxY ) {
maxY = y;
}
if ( z > maxZ ) {
maxZ = z;
}
if ( x < minX ) {
minX = x;
}
if ( y < minY ) {
minY = y;
}
if ( z < minZ ) {
minZ = z;
}
}
const rangeX = maxX - minX;
const rangeY = maxY - minY;
const rangeZ = maxZ - minZ;
if ( rangeX > rangeY && rangeX > rangeZ ) {
return xAxis;
} else if ( rangeY > rangeZ ) {
return yAxis;
} else {
return zAxis;
}
}
/**
* Splits the node and distributes node's primitives over new child nodes.
*
* @param {Number} branchingFactor - The branching factor.
* @return {BVHNode} A reference to this BVH node.
*/
split( branchingFactor ) {
const centroids = this.centroids;
const primitives = this.primitives;
// create (empty) child BVH nodes
for ( let i = 0; i < branchingFactor; i ++ ) {
this.children[ i ] = new BVHNode();
this.children[ i ].parent = this;
}
// sort primitives along split axis
const axis = this.computeSplitAxis();
const sortedPrimitiveIndices = new Array();
for ( let i = 0, l = centroids.length; i < l; i += 3 ) {
v1.fromArray( centroids, i );
// the result from the dot product is our sort criterion.
// it represents the projection of the centroid on the split axis
const p = v1.dot( axis );
const primitiveIndex = i / 3;
sortedPrimitiveIndices.push( { index: primitiveIndex, p: p } );
}
sortedPrimitiveIndices.sort( sortPrimitives );
// distribute data
const primitveCount = sortedPrimitiveIndices.length;
const primitivesPerChild = Math.floor( primitveCount / branchingFactor );
var childIndex = 0;
var primitivesIndex = 0;
for ( let i = 0; i < primitveCount; i ++ ) {
// selected child
primitivesIndex ++;
// check if we try to add more primitives to a child than "primitivesPerChild" defines.
// move primitives to the next child
if ( primitivesIndex > primitivesPerChild ) {
// ensure "childIndex" does not overflow (meaning the last child takes all remaining primitives)
if ( childIndex < ( branchingFactor - 1 ) ) {
primitivesIndex = 1; // reset primitive index
childIndex ++; // raise child index
}
}
const child = this.children[ childIndex ];
// move data to the next level
// 1. primitives
const primitiveIndex = sortedPrimitiveIndices[ i ].index;
const stride = primitiveIndex * 9; // remember the "primitives" array holds raw vertex data defining triangles
v1.fromArray( primitives, stride );
v2.fromArray( primitives, stride + 3 );
v3.fromArray( primitives, stride + 6 );
child.primitives.push( v1.x, v1.y, v1.z );
child.primitives.push( v2.x, v2.y, v2.z );
child.primitives.push( v3.x, v3.y, v3.z );
// 2. centroid
v1.fromArray( centroids, primitiveIndex * 3 );
child.centroids.push( v1.x, v1.y, v1.z );
}
// remove centroids/primitives after split from this node
this.centroids.length = 0;
this.primitives.length = 0;
return this;
}
/**
* Performs a ray/BVH node intersection test and stores the closest intersection point
* to the given 3D vector. If no intersection is detected, *null* is returned.
*
* @param {Ray} ray - The ray.
* @param {Vector3} result - The result vector.
* @return {Vector3} The result vector.
*/
intersectRay( ray, result ) {
// gather all intersection points along the hierarchy
if ( ray.intersectAABB( this.boundingVolume, result ) !== null ) {
if ( this.leaf() === true ) {
const vertices = this.primitives;
for ( let i = 0, l = vertices.length; i < l; i += 9 ) {
// remember: we assume primitives are triangles
triangle.a.fromArray( vertices, i );
triangle.b.fromArray( vertices, i + 3 );
triangle.c.fromArray( vertices, i + 6 );
if ( ray.intersectTriangle( triangle, true, result ) !== null ) {
intersections.push( result.clone() );
}
}
} else {
// process childs
for ( let i = 0, l = this.children.length; i < l; i ++ ) {
this.children[ i ].intersectRay( ray, result );
}
}
}
// determine the closest intersection point in the root node (so after
// the hierarchy was processed)
if ( this.root() === true ) {
if ( intersections.length > 0 ) {
let minDistance = Infinity;
for ( let i = 0, l = intersections.length; i < l; i ++ ) {
const squaredDistance = ray.origin.squaredDistanceTo( intersections[ i ] );
if ( squaredDistance < minDistance ) {
minDistance = squaredDistance;
result.copy( intersections[ i ] );
}
}
// reset array
intersections.length = 0;
// return closest intersection point
return result;
} else {
// no intersection detected
return null;
}
} else {
// always return null for non-root nodes
return null;
}
}
/**
* Performs a ray/BVH node intersection test. Returns either true or false if
* there is a intersection or not.
*
* @param {Ray} ray - The ray.
* @return {boolean} Whether there is an intersection or not.
*/
intersectsRay( ray ) {
if ( ray.intersectAABB( this.boundingVolume, intersection ) !== null ) {
if ( this.leaf() === true ) {
const vertices = this.primitives;
for ( let i = 0, l = vertices.length; i < l; i += 9 ) {
// remember: we assume primitives are triangles
triangle.a.fromArray( vertices, i );
triangle.b.fromArray( vertices, i + 3 );
triangle.c.fromArray( vertices, i + 6 );
if ( ray.intersectTriangle( triangle, true, intersection ) !== null ) {
return true;
}
}
return false;
} else {
// process child BVH nodes
for ( let i = 0, l = this.children.length; i < l; i ++ ) {
if ( this.children[ i ].intersectsRay( ray ) === true ) {
return true;
}
}
return false;
}
} else {
return false;
}
}
}
//
function sortPrimitives( a, b ) {
return a.p - b.p;
}
export { BVH, BVHNode };