function MultiResNode() {
	this.id              = 0;
	this.parentIndex     = -1;
	this.childrenIndices = [ -1, -1, -1, -1 ];
	this.projectedSize   = 1.0;
	this.zScale          = 1.0;
	this.box             = new SglBox3();
	this.priority        = { timestamp: -1, error: Number.MAX_VALUE };
	this.req             = null;
	this.data            = null;
	this.isLeaf          = true;
}

/*
MultiResNode.prototype = {
	get isLeaf() {
		for (var i=0; i<4; ++i) {
			if (this.childrenIndices[i] >= 0) return false;
		}
		return true;
	}
};
*/

function MultiResTree(url, onloadCallback) {
	this.ready      = true;
	this.nodesCount = 0;
	this.rootIndex  = -1;
	this.nodes      = null;
	this.url        = null;
	this.tileSize   = 0;
	this.scale      = [ 1.0, 1.0, 1.0 ];
	this.offset     = [ 0.0, 0.0, 0.0 ];

	if (url) {
		this.load(url, onloadCallback);
	}
}

MultiResTree.prototype = {
	_load : function(text) {
		this.ready = true;

		var lines = sglGetLines(text);
		var n = lines.length;
		var tokens = null;
		var i = 0;

		if (n <= i) return;
		tokens = lines[i++].split(" ");
		if (tokens.length < 1) return;
		var magic = tokens[0];
		if (magic != "MTERR") return;

		if (n <= i) return;
		tokens = lines[i++].split(" ");
		if (tokens.length < 2) return;
		var nodesCount = parseInt(tokens[0]);
		if (nodesCount <= 0) return;
		var rootIndex = parseInt(tokens[1]);
		if ((rootIndex < 0) || (rootIndex >= nodesCount)) return;

		if (n <= i) return;
		tokens = lines[i++].split(" ");
		if (tokens.length < 1) return;
		var tileSize = parseInt(tokens[0]);
		if (tileSize <= 0) return;

		if (n <= i) return;
		tokens = lines[i++].split(" ");
		if (tokens.length < 3) return;
		var scale = [ 1.0, 1.0, 1.0 ];
		scale[0] = parseFloat(tokens[0]);
		scale[1] = parseFloat(tokens[1]);
		scale[2] = parseFloat(tokens[2]);

		if (n <= i) return;
		tokens = lines[i++].split(" ");
		if (tokens.length < 3) return;
		var offset = [ 0.0, 0.0, 0.0 ];
		offset[0] = parseFloat(tokens[0]);
		offset[1] = parseFloat(tokens[1]);
		offset[2] = parseFloat(tokens[2]);

		var nodes = new Array(nodesCount);
		for (var k=0; k<nodesCount; ++k)
		{
			var node = new MultiResNode();

			if (n <= i) return;
			tokens = lines[i++].split(" ");
			if (tokens.length < 14) return;

			node.id = parseInt(tokens[0]);
			if (node.id <= 0) return;

			node.parentIndex = parseInt(tokens[1]);
			if ((node.parentIndex < -1) || (node.parentIndex >= nodesCount)) return;

			for (var c=0; c<4; ++c) {
				node.childrenIndices[c] = parseInt(tokens[c+2]);
				if ((node.childrenIndices[c] < -1) || (node.childrenIndices[c] >= nodesCount)) return;
			}

			node.projectedSize = parseFloat(tokens[6]);

			node.zScale = parseFloat(tokens[7]);

			node.box.min[0] = parseFloat(tokens[ 8]);
			node.box.min[1] = parseFloat(tokens[ 9]);
			node.box.min[2] = parseFloat(tokens[10]);
			node.box.max[0] = parseFloat(tokens[11]);
			node.box.max[1] = parseFloat(tokens[12]);
			node.box.max[2] = parseFloat(tokens[13]);

			node.isLeaf = true;
			for (var j=0; j<4; ++j) {
				if (node.childrenIndices[j] >= 0) {
					node.isLeaf = false;
					break;
				}
			}

			nodes[k] = node;
		}

		this.nodesCount = nodesCount;
		this.rootIndex  = rootIndex;
		this.tileSize   = tileSize;
		this.scale      = scale;
		this.offset     = offset;
		this.nodes      = nodes;
	},

	destroy : function() {
		var n = null;
		for (var i in this.nodes) {
			n = this.nodes[i];
			if (n.req) {
				n.req.onLoad = null;
				n.req = null;
			}
			if (n.data) {
				destroyData(n.data);
				n.data = null;
			}
		}

		this.ready      = true;
		this.nodesCount = 0;
		this.rootIndex  = -1;
		this.nodes      = null
		this.url        = null;
		this.tileSize   = 0;
		this.scale      = [ 1.0, 1.0, 1.0 ];
	},

	load : function(url, onloadCallback)
	{
		this.destroy();
		if (!url) return false;

		this.ready = false;
		this.url   = url;

		var cb = null;
		if (onloadCallback) {
			var that = this;
			cb = function (text) {
				that._load(text);
				onloadCallback(that);
			};
		}

		var txt = sglLoadFile(this.url, cb);
		if (txt) {
			this._load(txt);
		}

		return true;
	},

	get isEmpty() {
		return (this.nodesCount <= 0);
	},

	get root() {
		var idx = this.rootIndex;
		if (idx < 0) return null;
		return this.nodes[idx];
	},

	parent : function(n) {
		var idx = n.parentIndex;
		if (idx < 0) return null;
		return this.nodes[idx];
	},

	child: function(n, i) {
		var idx = n.childrenIndices[i];
		if (idx < 0) return null;
		return this.nodes[idx];
	}
};

function _MultiResAssert(cond) {
	if (cond) return;
	alert("MultiResAssert FAILED : " + cond);
}

function _MultiResCompareNodes(a, b) {
	// higher timestamp first
	if (a.priority.timestamp != b.priority.timestamp) {
		return (b.priority.timestamp - a.priority.timestamp);
	}

	// higher error first
	if (a.priority.error != b.priority.error) {
		return (b.priority.error - a.priority.error);
	}

	// lower id first
	return (a.id - b.id);
};

function MultiResRenderer(gl, url, cacheSizeInBytes, onLoad) {
	var cb = null;
	if (onLoad) {
		var that = this;
		cb = function(tree) {
			that._setupTree();
			onLoad(tree);
		};
	}

	this.gl    = gl;
	this._tree = new MultiResTree(url + "/tree.txt", cb);
	this._url  = url;
	this._timestamp = 0;
	this._frustum = new SglFrustum();
	this._maxError = 1.0;
	this._cache = [ ];
	this._cacheSizeInBytes = cacheSizeInBytes;
	this._maxCacheSize = 1;
	this._maxOngoingRequests = 2;
	this._currentOngoingRequests = 0;
	this._toRequest = [ ];
	this._toRenderFullRes = [ ];
	this._toRenderHalfRes = [ ];
	this._readyItems = [ ];

	this.renderData  = true;
	this.renderBoxes = false;
	this.lightPos    = [ 0.0, 0.0 ];

	// box mesh
	/******************************************************/
	var boxPositions = new Float32Array([
		-0.5, -0.5,  0.5,
		 0.5, -0.5,  0.5,
		-0.5,  0.5,  0.5,
		 0.5,  0.5,  0.5,
		-0.5, -0.5, -0.5,
		 0.5, -0.5, -0.5,
		-0.5,  0.5, -0.5,
		 0.5,  0.5, -0.5
	 ]);

	var trianglesIndices = new Uint16Array([
		0, 1, 2,  2, 1, 3,  // front
		5, 4, 7,  7, 4, 6,  // back
		4, 0, 6,  6, 0, 2,  // left
		1, 5, 3,  3, 5, 7,  // right
		2, 3, 6,  6, 3, 7,  // top
		4, 5, 0,  0, 5, 1   // bottom
	]);

	var edgesIndices = new Uint16Array([
		0, 1, 1, 3, 3, 2, 2, 0,  // front
		5, 4, 4, 6, 6, 7, 7, 5,  // back
		0, 4, 1, 5, 3, 7, 2, 6   // middle
	]);

	var box = new SglMeshGL(gl);

	box.addVertexAttribute("position", 3, boxPositions);
	box.addIndexedPrimitives("triangles", gl.TRIANGLES, trianglesIndices);
	box.addIndexedPrimitives("edges",     gl.LINES,     edgesIndices);

	this._boxMesh = box;
	/******************************************************/

	/******************************************************/
	this._tileFullMesh = null;
	this._tileHalfMesh = null;
	/******************************************************/

	// box rendering
	/******************************************************/
	var vs = sglLoadFile("examples/ptm.v.glsl");
	var fs = sglLoadFile("examples/ptm.f.glsl");
	var prg = new SglProgram(gl, [vs], [fs]);
	log(prg.log);

	this._program  = prg;
	this._renderer = new SglMeshGLRenderer(this._program);
	/******************************************************/

	// box rendering
	/******************************************************/
	var bvs = sglLoadFile("examples/box.v.glsl");
	var bfs = sglLoadFile("examples/box.f.glsl");
	var bprg = new SglProgram(gl, [bvs], [bfs]);
	log(bprg.log);

	this._boxProgram  = bprg;
	this._boxRenderer = new SglMeshGLRenderer(this._boxProgram);
	/******************************************************/

	this._treeTransform = sglIdentityM4();
	this._normalizedTreeTransform = sglIdentityM4();

	if (this._tree.ready) {
		this._setupTree();
	}
}

MultiResRenderer.prototype = {
	_createData : function(colorImgs) {
		var colorTexOpts = {
			/*
			minFilter : this.gl.LINEAR_MIPMAP_LINEAR,
			magFilter : this.gl.LINEAR,
			generateMipmap : true
			*/

			minFilter : this.gl.LINEAR,
			magFilter : this.gl.LINEAR,
			generateMipmap : false
		};

		var dataTextures = new Array(colorImgs.length);
		for (var i=0; i<colorImgs.length; ++i) {
			dataTextures[i] = new SglTexture2D(this.gl, colorImgs[i], colorTexOpts);
		}

		var data = {
			textures : dataTextures
		};

		return data;
	},

	_destroyData : function(data) {
		for (var i=0; i<data.textures.length; ++i) {
			data.textures[i].destroy();
		}
		data.textures = null;
	},

	_requestNode : function(n) {
		if (n.req) return;

		var that  = this;
		var url   = this._url + "/" + n.id;

		var requests = new Array();

		requests.push(new SglImageRequest(url + "_1.png"));
		requests.push(new SglImageRequest(url + "_2.png"));
		requests.push(new SglImageRequest(url + "_3.png"));

		var watcher = new SglRequestWatcher(requests, function(w) {
			that._currentOngoingRequests--;
			that._readyItems.push(n);
		});
		n.req = watcher;
		watcher.send();
	},

	_collectNodesRec : function(n, parentFullyVisible) {
		var result = {
			needed : false,
			usable : ((n.data) ? (true) : (false))
		};

		// test visibility only if parent is not completely inside frustum
		if (!parentFullyVisible) {
			var visStatus = this._frustum.boxVisibility(n.box.min, n.box.max);
			if (visStatus == SGL_OUTSIDE_FRUSTUM) return result;
			parentFullyVisible = (visStatus == SGL_INSIDE_FRUSTUM);
		}

		// node is visible and thus needed
		result.needed = true;

		// calculate error
		var prjSize = this._frustum.projectedSegmentSize(n.box.center, n.box.size[0]);
		var error   = prjSize / n.projectedSize;

		n.priority.timestamp = this._timestamp;
		n.priority.error     = error;

		// if node data is not available, request node and return
		if (!result.usable) {
			if (!n.req) {
				this._toRequest.push(n);
				//this._toRequest[n.id] = n;
			}
			return result;
		}

		// if node is below error, render it in full resolution and return
		if ((error < this._maxError) || n.isLeaf) {
			this._toRenderFullRes.push(n);
			//this._toRenderFullRes[n.id] = n;
			return result;
		}

		// recurse down to children
		var c = null;
		var neededCount = 0;
		var usableCount = 0;
		var cr = null;
		var missingChildren = [ ];

		for (var i=0; i<4; ++i) {
			c = this._tree.child(n, i);
			if (!c) continue;
			cr = this._collectNodesRec(c, parentFullyVisible);
			if (cr.usable) usableCount++;
			if (cr.needed) {
				neededCount++;
				if (!cr.usable) {
					missingChildren.push(i);
				}
			}
		}

		//_MultiResAssert(neededCount > 0);

		if (neededCount > 0) {
			if (usableCount <= 0) {
				// no needed child is available, render node in full resolution
				this._toRenderFullRes.push(n);
				//this._toRenderFullRes[n.id] = n;
			}
			else if (missingChildren.length > 0) {
				// some child is needed but not usable, render their sectors in half resolution (wrt this node)
				this._toRenderHalfRes.push({ n: n, children: missingChildren });
				//this._toRenderHalfRes[n.id] = { n: n, missingChildren: missingChildren };
			}
			// else all needed children can be rendered
		}

		// the node is needed and available
		return result;
	},

	_collectNodes : function() {
		this._toRequest = [ ];
		this._toRenderFullRes = [ ];
		this._toRenderHalfRes = [ ];

		var root = this._tree.root;
		if (!root) return;

		this._collectNodesRec(root, false);
	},

	_renderNodeFullRes : function(n) {
		var uniforms = {
			u_world_box_min : n.box.min,
			u_world_box_max : n.box.max
		};

		var samplers = {
			coeffH    : n.data.textures[0],
			coeffL    : n.data.textures[1],
			coeffRgb  : n.data.textures[2]
		};

		this._renderer.setUniforms(uniforms);
		this._renderer.setSamplers(samplers);
		this._renderer.render();
	},

	_renderNodesFullRes : function(mvp) {
		var mesh = null;
		var primitives = null;

		mesh = this._tileFullMesh;
		primitives = "tristrip";

		var uniforms = {
			u_model_view_projection_matrix : mvp,
			u_scale_bias                   : [ 1.0, 1.0, 0.0, 0.0 ],
			u_texcoord_scale_bias          : [ (this._tree.tileSize / (this._tree.tileSize + 2.0)), (1.0 / (this._tree.tileSize + 2.0)) ],
			lightPos                       : this.lightPos
		};

		this._renderer.begin();
			this._renderer.setUniforms(uniforms);
			this._renderer.beginMesh(mesh);
				this._renderer.beginPrimitives(primitives);
				var n = null;
				for (var i in this._toRenderFullRes) {
					n = this._toRenderFullRes[i];
					this._renderNodeFullRes(n);
				}
				this._renderer.endPrimitives();
			this._renderer.endMesh();
		this._renderer.end();
	},

	_renderNodeHalfRes : function(n, children) {
		var uniforms = {
			u_world_box_min : null,
			u_world_box_max : null,
			u_scale_bias    : null
		};

		var samplers = {
			coeffH    : n.data.textures[0],
			coeffL    : n.data.textures[1],
			coeffRgb  : n.data.textures[2]
		};

		this._renderer.setSamplers(samplers);

		var scaleBias = [
			[ 0.5, 0.5, 0.0, 0.0 ],
			[ 0.5, 0.5, 0.5, 0.0 ],
			[ 0.5, 0.5, 0.0, 0.5 ],
			[ 0.5, 0.5, 0.5, 0.5 ]
		];

		var c = null;
		for (var i in children) {
			c = this._tree.child(n, children[i]);
			uniforms.u_world_box_min = c.box.min;
			uniforms.u_world_box_max = c.box.max;
			uniforms.u_scale_bias    = scaleBias[children[i]];
			this._renderer.setUniforms(uniforms);
			this._renderer.render();
		}
	},

	_renderNodesHalfRes : function(mvp) {
		var mesh = null;
		var primitives = null;

		mesh = this._tileHalfMesh;
		primitives = "tristrip";

		var uniforms = {
			u_model_view_projection_matrix : mvp,
			u_texcoord_scale_bias          : [ (this._tree.tileSize / (this._tree.tileSize + 2.0)), (1.0 / (this._tree.tileSize + 2.0)) ],
			lightPos                       : this.lightPos
		};

		this._renderer.begin();
			this._renderer.setUniforms(uniforms);
			this._renderer.beginMesh(mesh);
				this._renderer.beginPrimitives(primitives);
				var nc = null;
				for (var i in this._toRenderHalfRes) {
					nc = this._toRenderHalfRes[i];
					this._renderNodeHalfRes(nc.n, nc.children);
				}
				this._renderer.endPrimitives();
			this._renderer.endMesh();
		this._renderer.end();
	},

	_renderNodes : function(mvp) {
		this._renderNodesFullRes(mvp);
		this._renderNodesHalfRes(mvp);
	},

	_renderNodeFullResBox : function(n) {
		var sz = n.box.size;

		var uniforms = {
			u_world_box_min : sglAddV3S(n.box.min, sz[0] * 0.05),
			u_world_box_max : sglSubV3S(n.box.max, sz[0] * 0.05),
			u_color         : ((n.isLeaf) ? ([1.0, 0.0, 1.0]) : ([0.0, 1.0, 0.0]))
		};

		this._boxRenderer.setUniforms(uniforms);
		this._boxRenderer.render();
	},

	_renderNodesFullResBoxes : function(mvp) {
		var uniforms = {
			u_model_view_projection_matrix : mvp
		};

		this._boxRenderer.begin();
			this._boxRenderer.setUniforms(uniforms);
			this._boxRenderer.beginMesh(this._boxMesh);
				this._boxRenderer.beginPrimitives("edges");
				var n = null;
				for (var i in this._toRenderFullRes) {
					n = this._toRenderFullRes[i];
					this._renderNodeFullResBox(n);
				}
				this._boxRenderer.endPrimitives();
			this._boxRenderer.endMesh();
		this._boxRenderer.end();
	},

	_renderNodeHalfResBox : function(n, children) {
		var uniforms = {
			u_world_box_min : null,
			u_world_box_max : null,
			u_color         : null
		};

		var c  = null;
		var sx = null;
		for (var i in children) {
			c = this._tree.child(n, children[i]);
			sz = c.box.size;
			uniforms.u_world_box_min = sglAddV3S(c.box.min, sz[0] * 0.05);
			uniforms.u_world_box_max = sglSubV3S(c.box.max, sz[0] * 0.05);
			uniforms.u_color         = ((c.isLeaf) ? ([1.0, 1.0, 0.0]) : ([1.0, 1.0, 1.0]));
			this._boxRenderer.setUniforms(uniforms);
			this._boxRenderer.render();
		}
	},

	_renderNodesHalfResBoxes : function(mvp) {
		var uniforms = {
			u_model_view_projection_matrix : mvp
		};

		this._boxRenderer.begin();
			this._boxRenderer.setUniforms(uniforms);
			this._boxRenderer.beginMesh(this._boxMesh);
				this._boxRenderer.beginPrimitives("edges");
				var nc = null;
				for (var i in this._toRenderHalfRes) {
					nc = this._toRenderHalfRes[i];
					this._renderNodeHalfResBox(nc.n, nc.children);
				}
				this._boxRenderer.endPrimitives();
			this._boxRenderer.endMesh();
		this._boxRenderer.end();
	},

	_renderNodesBoxes : function(mvp) {
		this.gl.lineWidth(2.0);
		this.gl.depthFunc(this.gl.LEQUAL);
		this._renderNodesFullResBoxes(mvp);
		this._renderNodesHalfResBoxes(mvp);
		this.gl.depthFunc(this.gl.LESS);
		this.gl.lineWidth(1.0);
	},

	_doRender : function(projectionMatrix, modelViewMatrix, viewport) {
		var mv = sglMulM4(modelViewMatrix, this._treeTransform);
		//var mv = modelViewMatrix;

		this._timestamp++;
		this._frustum.setup(projectionMatrix, mv, viewport);

		this._collectNodes();
		var mvp = sglMulM4(projectionMatrix, mv);

		if (this.renderData) {
			this._renderNodes(mvp);
		}

		if (this.renderBoxes) {
			this._renderNodesBoxes(mvp);
		}

		//this.gl.finish();
	},

	_updateCache : function() {
		var combined = this._cache.concat(this._readyItems);
		this._readyItems = [ ];
		combined.sort(_MultiResCompareNodes);

		var cl = combined.length;
		var k  = (this._maxCacheSize < cl) ? (this._maxCacheSize) : (cl);

		this._cache = combined.splice(0, k);
		var outOfCache = combined;

		var n = null;
		var r = null;
		var failed = [ ];

		for (var i=0; i<k; ++i) {
			n = this._cache[i];
			r = n.req;
			n.req = null;

			if (!r) continue;
			if (!r.succeeded) {
				failed.push(i);
				continue;
			}

			var cimgs = new Array(r.requests.length);
			for (var i=0; i<cimgs.length; ++i) {
				cimgs[i] = r.requests[i].image;
			}
			n.data = this._createData(cimgs);
		}

		var fc = failed.length;
		var reinsertedCount = 0;

		k = outOfCache.length;
		for (var i=0; i<k; ++i) {
			n = outOfCache[i];
			r = n.req;
			n.req = null;

			if (r) continue;

			if (reinsertedCount < fc) {
				this._cache[failed[reinsertedCount]] = n;
				reinsertedCount++;
			}
			else {
				this._destroyData(n.data);
				n.data = null;
			}
		}

		if (reinsertedCount > 0) {
			this._cache.sort(_MultiResCompareNodes);
		}
	},

	_requestNodes : function() {
		var cs = this._cache.length;
		var lastItem = (cs > 0) ? (this._cache[cs-1]) : (null);

		this._toRequest.sort(_MultiResCompareNodes);
		var requestableCount = this._maxOngoingRequests - this._currentOngoingRequests;

		var requested = 0;
		var k = this._toRequest.length;
		var n = null;
		var canRequest = false;

		for (var i=0; ((i<k) && (requested<requestableCount)); ++i) {
			n = this._toRequest[i];
			if (n.req) continue; // ongoing;

			canRequest = true;
			if ((lastItem != null) && (cs >= this._maxCacheSize)) {
				canRequest = (_MultiResCompareNodes(n, lastItem) < 0);
			}
			if (canRequest) {
				this._requestNode(n);
				requested++
			}
		}
	},

	_calculateNormalizedTreeTransform : function() {
		var root = this._tree.root;
		if (!root) return sglIdentityM4();

		var rbox = new SglBox3();
		rbox.min = sglAddV3(sglMulV3(root.box.min, this._tree.scale), this._tree.offset);
		rbox.max = sglAddV3(sglMulV3(root.box.max, this._tree.scale), this._tree.offset);
		//rbox = root.box;

		this._treeTransform = sglMulM4(sglTranslationM4V(this._tree.offset), sglScalingM4V(this._tree.scale));
		//this._treeTransform = sglIdentityM4();

		var bc = rbox.center;
		var bs = rbox.size;

		var maxDim = bs[0];
		if (maxDim < bs[1]) maxDim = bs[1];
		if (maxDim < bs[2]) maxDim = bs[2];

		var scale = (maxDim > 0.0) ? (1.0 / maxDim) : (1.0);

		var s = sglScalingM4C(scale, scale, scale);
		var t = sglTranslationM4C(-bc[0], -bc[1], -bc[2]);

		var xform = sglMulM4(s, t);
		this._normalizedTreeTransform = xform;
		/*
		//var r  = sglRotationAngleAxisM4C(sglDegToRad(-90.0), 1.0, 0.0, 0.0);
		var r  = sglIdentityM4();
		var t1 = sglTranslationM4C(0.0, 0.0, bs[2] / 2.0 * scale);
		var s  = sglScalingM4C(scale, scale, scale);
		var t2 = sglTranslationM4C(-bc[0], -bc[1], -bc[2]);
		this._normalizedTreeTransform = sglMulM4(r, sglMulM4(t1, sglMulM4(s, t2)));
		*/
	},

	_setupTree : function() {
		var root = this._tree.root;
		if (!root) return;

		var gl = this.gl;

		var csize = ((this._tree.tileSize + 2) * (this._tree.tileSize + 2)) * 4;

		this._maxCacheSize = sglFloor(this._cacheSizeInBytes / (csize));
		if (this._maxCacheSize <= 0) this._maxCacheSize = 1;

		var quadPositions = new Float32Array([
			-0.5,  0.5,
			-0.5, -0.5,
			 0.5,  0.5,
			 0.5, -0.5
		]);

		var quadMesh = new SglMeshGL(gl);
		quadMesh.addVertexAttribute("position", 2, quadPositions);
		quadMesh.addArrayPrimitives("tristrip", gl.TRIANGLE_STRIP, 0, 4);

		this._tileFullMesh = quadMesh;
		this._tileHalfMesh = quadMesh;

		this._calculateNormalizedTreeTransform();
	},

	render : function(projectionMatrix, modelViewMatrix, viewport) {
		if (!this._tree.root) return;

		this._doRender(projectionMatrix, modelViewMatrix, viewport);
		this._updateCache();
		this._requestNodes();
	},

	get normalizedTreeTransform() {
		return this._normalizedTreeTransform;
	}
};