octree.js

/**
* @namespace GL
*/

/**
*   Octree generator for fast ray triangle collision with meshes
*	Dependencies: glmatrix.js (for vector and matrix operations)
* @class Octree
* @constructor
* @param {Mesh} mesh object containing vertices buffer (indices buffer optional)
*/

global.Octree = GL.Octree = function Octree( mesh )
{
	this.root = null;
	this.total_depth = 0;
	this.total_nodes = 0;
	if(mesh)
	{
		this.buildFromMesh(mesh);
		this.total_nodes = this.trim();
	}
}

Octree.MAX_NODE_TRIANGLES_RATIO = 0.1;
Octree.MAX_OCTREE_DEPTH = 8;
Octree.OCTREE_MARGIN_RATIO = 0.01;
Octree.OCTREE_MIN_MARGIN = 0.1;

var octree_tested_boxes = 0;
var octree_tested_triangles = 0;

Octree.prototype.buildFromMesh = function( mesh )
{
	this.total_depth = 0;
	this.total_nodes = 0;

	var vertices = mesh.getBuffer("vertices").data;
	var triangles = mesh.getIndexBuffer("triangles");
	if(triangles) 
		triangles = triangles.data; //get the internal data

	var root = this.computeAABB(vertices);
	this.root = root;
	this.total_nodes = 1;
	this.total_triangles = triangles ? triangles.length / 3 : vertices.length / 9;
	this.max_node_triangles = this.total_triangles * Octree.MAX_NODE_TRIANGLES_RATIO;

	var margin = vec3.create();
	vec3.scale( margin, root.size, Octree.OCTREE_MARGIN_RATIO );
	if(margin[0] < Octree.OCTREE_MIN_MARGIN) margin[0] = Octree.OCTREE_MIN_MARGIN;
	if(margin[1] < Octree.OCTREE_MIN_MARGIN) margin[1] = Octree.OCTREE_MIN_MARGIN;
	if(margin[2] < Octree.OCTREE_MIN_MARGIN) margin[2] = Octree.OCTREE_MIN_MARGIN;

	vec3.sub(root.min, root.min, margin);
	vec3.add(root.max, root.max, margin);

	root.faces = [];
	root.inside = 0;


	//indexed
	if(triangles)
	{
		for(var i = 0; i < triangles.length; i+=3)
		{
			var face = new Float32Array([vertices[triangles[i]*3], vertices[triangles[i]*3+1],vertices[triangles[i]*3+2],
						vertices[triangles[i+1]*3], vertices[triangles[i+1]*3+1],vertices[triangles[i+1]*3+2],
						vertices[triangles[i+2]*3], vertices[triangles[i+2]*3+1],vertices[triangles[i+2]*3+2],i/3]);
			this.addToNode( face,root,0);
		}
	}
	else
	{
		for(var i = 0; i < vertices.length; i+=9)
		{
			var face = new Float32Array( 10 );
			face.set( vertices.subarray(i,i+9) );
			face[9] = i/9;
			this.addToNode(face,root,0);
		}
	}

	return root;
}

Octree.prototype.addToNode = function( face, node, depth )
{
	node.inside += 1;

	//has children
	if(node.c)
	{
		var aabb = this.computeAABB(face);
		var added = false;
		for(var i in node.c)
		{
			var child = node.c[i];
			if (Octree.isInsideAABB(aabb,child))
			{
				this.addToNode(face,child, depth+1);
				added = true;
				break;
			}
		}
		if(!added)
		{
			if(node.faces == null)
				node.faces = [];
			node.faces.push(face);
		}
	}
	else //add till full, then split
	{
		if(node.faces == null)
			node.faces = [];
		node.faces.push(face);

		//split
		if(node.faces.length > this.max_node_triangles && depth < Octree.MAX_OCTREE_DEPTH)
		{
			this.splitNode(node);
			if(this.total_depth < depth + 1)
				this.total_depth = depth + 1;

			var faces = node.faces.concat();
			node.faces = null;

			//redistribute all nodes
			for(var i in faces)
			{
				var face = faces[i];
				var aabb = this.computeAABB(face);
				var added = false;
				for(var j in node.c)
				{
					var child = node.c[j];
					if (Octree.isInsideAABB(aabb,child))
					{
						this.addToNode(face,child, depth+1);
						added = true;
						break;
					}
				}
				if (!added)
				{
					if(node.faces == null)
						node.faces = [];
					node.faces.push(face);
				}
			}
		}
	}
};

Octree.prototype.octree_pos_ref = [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]];

Octree.prototype.splitNode = function(node)
{
	node.c = [];
	var half = [(node.max[0] - node.min[0]) * 0.5, (node.max[1] - node.min[1]) * 0.5, (node.max[2] - node.min[2]) * 0.5];

	for(var i in this.octree_pos_ref)
	{
		var ref = this.octree_pos_ref[i];

		var newnode = {};
		this.total_nodes += 1;

		newnode.min = [ node.min[0] + half[0] * ref[0],  node.min[1] + half[1] * ref[1],  node.min[2] + half[2] * ref[2]];
		newnode.max = [newnode.min[0] + half[0], newnode.min[1] + half[1], newnode.min[2] + half[2]];
		newnode.faces = null;
		newnode.inside = 0;
		node.c.push(newnode);
	}
}

Octree.prototype.computeAABB = function(vertices)
{
	var min = new Float32Array([ vertices[0], vertices[1], vertices[2] ]);
	var max = new Float32Array([ vertices[0], vertices[1], vertices[2] ]);

	for(var i = 0; i < vertices.length; i+=3)
	{
		for(var j = 0; j < 3; j++)
		{
			if(min[j] > vertices[i+j]) 
				min[j] = vertices[i+j];
			if(max[j] < vertices[i+j]) 
				max[j] = vertices[i+j];
		}
	}

	return {min: min, max: max, size: vec3.sub( vec3.create(), max, min) };
}

//remove empty nodes
Octree.prototype.trim = function(node)
{
	node = node || this.root;
	if(!node.c)
		return 1;

	var num = 1;
	var valid = [];
	var c = node.c;
	for(var i = 0; i < c.length; ++i)
	{
		if(c[i].inside)
		{
			valid.push(c[i]);
			num += this.trim(c[i]);
		}
	}
	node.c = valid;
	return num;
}

/**
* Test collision between ray and triangles in the octree
* @method testRay
* @param {vec3} origin ray origin position
* @param {vec3} direction ray direction position
* @param {number} dist_min
* @param {number} dist_max
* @return {HitTest} object containing pos and normal
*/
Octree.prototype.testRay = (function(){ 
	var origin_temp = vec3.create();
	var direction_temp = vec3.create();
	var min_temp = vec3.create();
	var max_temp = vec3.create();

	return function(origin, direction, dist_min, dist_max, test_backfaces )
	{
		octree_tested_boxes = 0;
		octree_tested_triangles = 0;

		if(!this.root)
		{
			throw("Error: octree not build");
		}

		origin_temp.set( origin );
		direction_temp.set( direction );
		min_temp.set( this.root.min );
		max_temp.set( this.root.max );

		var test = Octree.hitTestBox( origin_temp, direction_temp, min_temp, max_temp );
		if(!test) //no collision with mesh bounding box
			return null;

		var test = Octree.testRayInNode( this.root, origin_temp, direction_temp, test_backfaces );
		if(test != null)
		{
			var pos = vec3.scale( vec3.create(), direction, test.t );
			vec3.add( pos, pos, origin );
			test.pos = pos;
			return test;
		}

		return null;
	}
})();

/**
* test collision between sphere and the triangles in the octree (only test if there is any vertex inside the sphere)
* @method testSphere
* @param {vec3} origin sphere center
* @param {number} radius
* @return {Boolean} true if the sphere collided with the mesh
*/
Octree.prototype.testSphere = function( origin, radius )
{
	origin = vec3.clone(origin);
	octree_tested_boxes = 0;
	octree_tested_triangles = 0;

	if(!this.root)
		throw("Error: octree not build");

	//better to use always the radius squared, because all the calculations are going to do that
	var rr = radius * radius;

	if( !Octree.testSphereBox( origin, rr, vec3.clone(this.root.min), vec3.clone(this.root.max) ) )
		return false; //out of the box

	return Octree.testSphereInNode( this.root, origin, rr );
}

//WARNING: cannot use static here, it uses recursion
Octree.testRayInNode = function( node, origin, direction, test_backfaces )
{
	var test = null;
	var prev_test = null;
	octree_tested_boxes += 1;

	//test faces
	if(node.faces)
		for(var i = 0, l = node.faces.length; i < l; ++i)
		{
			var face = node.faces[i];
			octree_tested_triangles += 1;
			test = Octree.hitTestTriangle( origin, direction, face.subarray(0,3) , face.subarray(3,6), face.subarray(6,9), test_backfaces );
			if (test==null)
				continue;
			test.face = face;
			if(prev_test)
				prev_test.mergeWith( test );
			else
				prev_test = test;
		}

	//WARNING: cannot use statics here, this function uses recursion
	var child_min = vec3.create();
	var child_max = vec3.create();

	//test children nodes faces
	var child;
	if(node.c)
		for(var i = 0; i < node.c.length; ++i)
		{
			child = node.c[i];
			child_min.set( child.min );
			child_max.set( child.max );

			//test with node box
			test = Octree.hitTestBox( origin, direction, child_min, child_max );
			if( test == null )
				continue;

			//nodebox behind current collision, then ignore node
			if(prev_test && test.t > prev_test.t)
				continue;

			//test collision with node
			test = Octree.testRayInNode( child, origin, direction, test_backfaces );
			if(test == null)
				continue;

			if(prev_test)
				prev_test.mergeWith( test );
			else
				prev_test = test;
		}

	return prev_test;
}

//WARNING: cannot use static here, it uses recursion
Octree.testSphereInNode = function( node, origin, radius2 )
{
	var test = null;
	var prev_test = null;
	octree_tested_boxes += 1;

	//test faces
	if(node.faces)
		for(var i = 0, l = node.faces.length; i < l; ++i)
		{
			var face = node.faces[i];
			octree_tested_triangles += 1;
			if( Octree.testSphereTriangle( origin, radius2, face.subarray(0,3) , face.subarray(3,6), face.subarray(6,9) ) )
				return true;
		}

	//WARNING: cannot use statics here, this function uses recursion
	var child_min = vec3.create();
	var child_max = vec3.create();

	//test children nodes faces
	var child;
	if(node.c)
		for(var i = 0; i < node.c.length; ++i)
		{
			child = node.c[i];
			child_min.set( child.min );
			child_max.set( child.max );

			//test with node box
			if( !Octree.testSphereBox( origin, radius2, child_min, child_max ) )
				continue;

			//test collision with node content
			if( Octree.testSphereInNode( child, origin, radius2 ) )
				return true;
		}

	return false;
}

//test if one bounding is inside or overlapping another bounding
Octree.isInsideAABB = function(a,b)
{
	if(a.min[0] < b.min[0] || a.min[1] < b.min[1] || a.min[2] < b.min[2] ||
		a.max[0] > b.max[0] || a.max[1] > b.max[1] || a.max[2] > b.max[2])
		return false;
	return true;
}


Octree.hitTestBox = (function(){ 
	var tMin = vec3.create();
	var tMax = vec3.create();
	var inv = vec3.create();
	var t1 = vec3.create();
	var t2 = vec3.create();
	var tmp = vec3.create();
	var epsilon = 1.0e-6;
	var eps = vec3.fromValues( epsilon,epsilon,epsilon );
	
	return function( origin, ray, box_min, box_max ) {
		vec3.subtract( tMin, box_min, origin );
		vec3.subtract( tMax, box_max, origin );
		
		if(	vec3.maxValue(tMin) < 0 && vec3.minValue(tMax) > 0)
			return new HitTest(0,origin,ray);

		inv[0] = 1/ray[0];	inv[1] = 1/ray[1];	inv[2] = 1/ray[2];
		vec3.multiply(tMin, tMin, inv);
		vec3.multiply(tMax, tMax, inv);
		vec3.min(t1, tMin, tMax);
		vec3.max(t2, tMin, tMax);
		var tNear = vec3.maxValue(t1);
		var tFar = vec3.minValue(t2);

		if (tNear > 0 && tNear < tFar) {
			var hit = vec3.add( vec3.create(), vec3.scale(tmp, ray, tNear ), origin);
			vec3.add( box_min, box_min, eps);
			vec3.subtract(box_min, box_min, eps);
			return new HitTest(tNear, hit, vec3.fromValues(
			  (hit[0] > box_max[0]) - (hit[0] < box_min[0]),
			  (hit[1] > box_max[1]) - (hit[1] < box_min[1]),
			  (hit[2] > box_max[2]) - (hit[2] < box_min[2]) ));
		}

		return null;
	}
})();

Octree.hitTestTriangle = (function(){ 
	
	var AB = vec3.create();
	var AC = vec3.create();
	var toHit = vec3.create();
	var tmp = vec3.create();
	
	return function( origin, ray, A, B, C, test_backfaces ) {
		vec3.subtract( AB, B, A );
		vec3.subtract( AC, C, A );
		var normal = vec3.cross( vec3.create(), AB, AC ); //returned
		vec3.normalize( normal, normal );
		if( !test_backfaces && vec3.dot(normal,ray) > 0)
			return null; //ignore backface

		var t = vec3.dot(normal, vec3.subtract( tmp, A, origin )) / vec3.dot(normal,ray);

	    if (t > 0)
		{
			var hit = vec3.scale(vec3.create(), ray, t); //returned
			vec3.add(hit, hit, origin);
			vec3.subtract( toHit, hit, A );
			var dot00 = vec3.dot(AC,AC);
			var dot01 = vec3.dot(AC,AB);
			var dot02 = vec3.dot(AC,toHit);
			var dot11 = vec3.dot(AB,AB);
			var dot12 = vec3.dot(AB,toHit);
			var divide = dot00 * dot11 - dot01 * dot01;
			var u = (dot11 * dot02 - dot01 * dot12) / divide;
			var v = (dot00 * dot12 - dot01 * dot02) / divide;
			if (u >= 0 && v >= 0 && u + v <= 1)
				return new HitTest(t, hit, normal);
		}
	    return null;
	};
})();

//from http://realtimecollisiondetection.net/blog/?p=103
//radius must be squared
Octree.testSphereTriangle = (function(){ 
	
	var A = vec3.create();
	var B = vec3.create();
	var C = vec3.create();
	var AB = vec3.create();
	var AC = vec3.create();
	var BC = vec3.create();
	var CA = vec3.create();
	var V = vec3.create();
	
	return function( P, rr, A_, B_, C_ ) {
		vec3.sub( A, A_, P );
		vec3.sub( B, B_, P );
		vec3.sub( C, C_, P );

		vec3.sub( AB, B, A );
		vec3.sub( AC, C, A );

		vec3.cross( V, AB, AC );
		var d = vec3.dot( A, V );
		var e = vec3.dot( V, V );
		var sep1 = d * d > rr * e;
		var aa = vec3.dot(A, A);
		var ab = vec3.dot(A, B);
		var ac = vec3.dot(A, C);
		var bb = vec3.dot(B, B);
		var bc = vec3.dot(B, C);
		var cc = vec3.dot(C, C);
		var sep2 = (aa > rr) & (ab > aa) & (ac > aa);
		var sep3 = (bb > rr) & (ab > bb) & (bc > bb);
		var sep4 = (cc > rr) & (ac > cc) & (bc > cc);

		var d1 = ab - aa;
		var d2 = bc - bb;
		var d3 = ac - cc;

		vec3.sub( BC, C, B );
		vec3.sub( CA, A, C );

		var e1 = vec3.dot(AB, AB);
		var e2 = vec3.dot(BC, BC);
		var e3 = vec3.dot(CA, CA);

		var Q1 = vec3.scale(vec3.create(), A, e1); vec3.sub( Q1, Q1, vec3.scale(vec3.create(), AB, d1) );
		var Q2 = vec3.scale(vec3.create(), B, e2); vec3.sub( Q2, Q2, vec3.scale(vec3.create(), BC, d2) );
		var Q3 = vec3.scale(vec3.create(), C, e3); vec3.sub( Q3, Q3, vec3.scale(vec3.create(), CA, d3) );

		var QC = vec3.scale( vec3.create(), C, e1 ); QC = vec3.sub( QC, QC, Q1 );
		var QA = vec3.scale( vec3.create(), A, e2 ); QA = vec3.sub( QA, QA, Q2 );
		var QB = vec3.scale( vec3.create(), B, e3 ); QB = vec3.sub( QB, QB, Q3 );

		var sep5 = ( vec3.dot(Q1, Q1) > rr * e1 * e1) & (vec3.dot(Q1, QC) > 0 );
		var sep6 = ( vec3.dot(Q2, Q2) > rr * e2 * e2) & (vec3.dot(Q2, QA) > 0 );
		var sep7 = ( vec3.dot(Q3, Q3) > rr * e3 * e3) & (vec3.dot(Q3, QB) > 0 );

		var separated = sep1 | sep2 | sep3 | sep4 | sep5 | sep6 | sep7
		return !separated;
	};
})();

Octree.testSphereBox = function( center, radius2, box_min, box_max ) {

	// arvo's algorithm from gamasutra
	// http://www.gamasutra.com/features/19991018/Gomez_4.htm
	var s, d = 0.0;
	//find the square of the distance
	//from the sphere to the box
	for(var i = 0; i < 3; ++i) 
	{ 
		if( center[i] < box_min[i] )
		{
			s = center[i] - box_min[i];
			d += s*s; 
		}
		else if( center[i] > box_max[i] )
		{ 
			s = center[i] - box_max[i];
			d += s*s; 
		}
	}
	//return d <= r*r

	if (d <= radius2)
	{
		return true;
		/*
		// this is used just to know if it overlaps or is just inside, but I dont care
		// make an aabb aabb test with the sphere aabb to test inside state
		var halfsize = vec3.fromValues( radius, radius, radius );
		var sphere_bbox = BBox.fromCenterHalfsize( center, halfsize );
		if ( geo.testBBoxBBox(bbox, sphere_bbox) )
			return INSIDE;
		return OVERLAP;	
		*/
	}

	return false; //OUTSIDE;
};