bvh.js

const fs = require("fs");
const modelText = String(fs.readFileSync("Bunny.obj"));

const parseOBJ = function(modelText) {
	
	let lines = modelText.split("\n");
	let vertexes = [];
	let faces = [];
	
	for(let line of lines) {
		
		line = line.replace(/\s+/g, ' ').trim();
		
		if(line.length === 0 || line[0] === "#") {
				continue;
		}
		
		let parts = line.split(" ");
		if(parts.length === 0) {
			continue;
		}
		
		if(parts[0] === "v") {
			vertexes.push([
				parseFloat(parts[1]),
				parseFloat(parts[2]),
				parseFloat(parts[3])
			]);
		} else if(parts[0] === "f") {
			
			// Face indices start from 1, so subtract for a real index
			if(parts.length === 4) {
				faces.push([
					parseInt(parts[1].split("/")[0]) - 1,
					parseInt(parts[2].split("/")[0]) - 1,
					parseInt(parts[3].split("/")[0]) - 1
				]);
			} else if(parts.length === 5) {
				faces.push([
					parseInt(parts[1].split("/")[0]) - 1,
					parseInt(parts[2].split("/")[0]) - 1,
					parseInt(parts[3].split("/")[0]) - 1
				]);
				faces.push([
					parseInt(parts[1].split("/")[0]) - 1,
					parseInt(parts[3].split("/")[0]) - 1,
					parseInt(parts[4].split("/")[0]) - 1
				]);
			}
			
		}
		
	}
	
	return {
		vertexes: vertexes,
		faces: faces
	};
	
};

const minOf3 = (a, b, c) => Math.min(a, Math.min(b, c));
const maxOf3 = (a, b, c) => Math.max(a, Math.max(b, c));

const getBoundingBoxTri = function(v1, v2, v3) {
	
	let minX = minOf3(v1[0], v2[0], v3[0]);
	let minY = minOf3(v1[1], v2[1], v3[1]);
	let minZ = minOf3(v1[2], v2[2], v3[2]);
	
	let maxX = maxOf3(v1[0], v2[0], v3[0]);
	let maxY = maxOf3(v1[1], v2[1], v3[1]);
	let maxZ = maxOf3(v1[2], v2[2], v3[2]);
	
	return {
		min: [minX, minY, minZ],
		max: [maxX, maxY, maxZ]
	};
	
};

const getBoundingBoxOfBoxes = function(boxes) {

	let minX = Infinity, minY = Infinity, minZ = Infinity, maxX = -Infinity, maxY = -Infinity, maxZ = -Infinity;
	for(let boundingBox of boxes) {
		minX = Math.min(minX, boundingBox.min[0]);
		minY = Math.min(minY, boundingBox.min[1]);
		minZ = Math.min(minZ, boundingBox.min[2]);
		
		maxX = Math.max(maxX, boundingBox.max[0]);
		maxY = Math.max(maxY, boundingBox.max[1]);
		maxZ = Math.max(maxZ, boundingBox.max[2]);
	}

	return {
		min: [minX, minY, minZ],
		max: [maxX, maxY, maxZ]
	};

};

const areaOfBox = function(box) {

	let width = box.max[0] - box.min[0];
	let height = box.max[1] - box.min[1];
	let depth = box.max[2] - box.min[2];
	return 2 * (width * height + width * depth + height * depth);
	
};

const buildBVH = function(model) {
	
	let boundingBoxes = [];
	for(let face of model.faces) {
		
		boundingBoxes.push(getBoundingBoxTri(model.vertexes[face[0]], model.vertexes[face[1]], model.vertexes[face[2]]));
		
	}

	let box = getBoundingBoxOfBoxes(boundingBoxes);
	split(box, boundingBoxes, 0);
	
	return box;
	
};

const INTERSECT_PRIM_COST = 8;
const TRAVERSE_COST = 1;

// Find the optimal split for a set of bounding boxes
const split = function(boundingTotal, boundingBoxes, depth) {

	if(depth > 5) return;

	let minSplitCost = Infinity;
	let minSplitLeftBucket;
	let minSplitLeftBox;
	let minSplitRightBucket;
	let minSplitRightBox;
	
	// for each axis...
	for(let axis = 0; axis < 3; axis++) {
		
		// ...for each split...
		let numSplits = 16;
		for(let split = 1; split < numSplits - 1; split++) {
			
			let splitPos = [boundingTotal.min[0], boundingTotal.min[1], boundingTotal.min[2]][axis] + (split / numSplits) * [boundingTotal.max[0] - boundingTotal.min[0], boundingTotal.max[1] - boundingTotal.min[1], boundingTotal.max[2] - boundingTotal.min[2]][axis];
			
			// split
			let left = [];
			let right = [];
			let noSplitCost = boundingBoxes.length * INTERSECT_PRIM_COST;
			
			for(let box of boundingBoxes) {

				if((box.max[axis] + box.min[axis]) / 2 < splitPos) {
					left.push(box);
				} else {
					right.push(box);
				}
				
			}
			
			let leftBox = getBoundingBoxOfBoxes(left);
			let rightBox = getBoundingBoxOfBoxes(right);
			
			let splitCost = TRAVERSE_COST +
				areaOfBox(leftBox) / areaOfBox(boundingTotal) * left.length * INTERSECT_PRIM_COST +
				areaOfBox(rightBox) / areaOfBox(boundingTotal) * right.length * INTERSECT_PRIM_COST;
			
			if(splitCost < noSplitCost && splitCost < minSplitCost) {
				minSplitCost = splitCost;
				minSplitLeftBucket = left;
				minSplitRightBucket = right;
				minSplitLeftBox = leftBox;
				minSplitRightBox = rightBox;
			}
			
		}
		
	}
	
	// Recurse
	if(minSplitCost < Infinity) {

		boundingTotal.left = minSplitLeftBox;
		boundingTotal.right = minSplitRightBox;	
		
		split(minSplitLeftBox, minSplitLeftBucket, depth + 1);
		split(minSplitRightBox, minSplitRightBucket, depth + 1);
		
	}
	
};

const encode = function(bvh) {

	let boxes = [];
	
	// recursively expand bvh
	expand(boxes, bvh);
	
	// convert boxes to mesh
	let vertexes = [];
	let faces = [];
	
	let offset = 1;
	for(let box of boxes) {
		
		// tedious code...
		vertexes.push([box.min[0], box.min[1], box.min[2]]);
		vertexes.push([box.min[0], box.min[1], box.max[2]]);
		vertexes.push([box.min[0], box.max[1], box.min[2]]);
		vertexes.push([box.min[0], box.max[1], box.max[2]]);
		vertexes.push([box.max[0], box.min[1], box.min[2]]);
		vertexes.push([box.max[0], box.min[1], box.max[2]]);
		vertexes.push([box.max[0], box.max[1], box.min[2]]);
		vertexes.push([box.max[0], box.max[1], box.max[2]]);
		
		faces.push([offset, offset + 1, offset + 3]);
		faces.push([offset, offset + 2, offset + 3]);
		
		faces.push([offset + 4, offset + 5, offset + 7]);
		faces.push([offset + 4, offset + 6, offset + 7]);
		
		faces.push([offset + 3, offset + 2, offset + 6]);
		faces.push([offset + 3, offset + 7, offset + 6]);
		
		faces.push([offset + 1, offset + 0, offset + 4]);
		faces.push([offset + 1, offset + 5, offset + 4]);
		
		faces.push([offset + 1, offset + 3, offset + 7]);
		faces.push([offset + 1, offset + 5, offset + 7]);
		
		faces.push([offset + 0, offset + 2, offset + 6]);
		faces.push([offset + 0, offset + 4, offset + 6]);
		
		offset += 8;
		
	}
	
	return {
		vertexes: vertexes,
		faces: faces
	};

};

const toOBJ = function(mesh) {

	let result = "";
	for(let vertex of mesh.vertexes) result += `v ${vertex[0]} ${vertex[1]} ${vertex[2]}\n`;
	for(let face of mesh.faces) result += `f ${face[0]} ${face[1]} ${face[2]}\n`;
	return result;
	
};

const expand = function(boxes, bvh) {
	if(bvh.left === undefined && bvh.right === undefined) {
		boxes.push({min: bvh.min, max: bvh.max});
	}
	if(bvh.left !== undefined && bvh.right !== undefined) {
		expand(boxes, bvh.left);
		expand(boxes, bvh.right);
	}
};

let mesh = parseOBJ(modelText);
console.log(mesh);
let bvh = buildBVH(mesh);
console.log(bvh);


fs.writeFileSync("AfterBVH.obj", toOBJ(encode(bvh)));