split method

BVHNode split(double branchingFactor)

Splits the node and distributes node's primitives over child nodes.

Implementation

BVHNode split(double branchingFactor ) {
	final centroids = this.centroids;
	final primitives = this.primitives;

	// create (empty) child BVH nodes

	for ( int i = 0; i < branchingFactor; i ++ ) {
		children.add(BVHNode());
		children[ i ].parent = this;
	}

	// sort primitives along split axis

	final axis = computeSplitAxis();
	final sortedPrimitiveIndices = [];

	for ( int 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

		final p = _v1.dot( axis );
		final primitiveIndex = i ~/ 3;

		sortedPrimitiveIndices.add( { 'index': primitiveIndex, 'p': p } );
	}

	sortedPrimitiveIndices.sort( sortPrimitives );

	// distribute data

	final primitveCount = sortedPrimitiveIndices.length;
	final primitivesPerChild = ( primitveCount / branchingFactor ).floor();

	var childIndex = 0;
	var primitivesIndex = 0;

	for ( int 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
			}
		}

		final child = children[ childIndex ];

		// move data to the next level
		// 1. primitives
		final primitiveIndex = sortedPrimitiveIndices[ i ]['index'];
		final 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.addAll( [_v1.x, _v1.y, _v1.z] );
		child.primitives.addAll( [_v2.x, _v2.y, _v2.z] );
		child.primitives.addAll( [_v3.x, _v3.y, _v3.z] );

		// 2. centroid
		_v1.fromArray( centroids, primitiveIndex * 3 );
		child.centroids.addAll( [_v1.x, _v1.y, _v1.z] );
	}

	// remove centroids/primitives after split from this node

	this.centroids.length = 0;
	this.primitives.length = 0;

	return this;
}