user script to redefine x3dom earclipping

x3domEarClippingFixer.user.js

// ==UserScript==
// @name        x3domEarClipFixer
// @namespace   aplesch
// @description fixes x3dom earclipping
// @version     2.1
// @grant       none
// ==/UserScript==

/*
 * X3DOM JavaScript Library
 * http://www.x3dom.org
 *
 * (C)2009 Fraunhofer IGD, Darmstadt, Germany
 * Dual licensed under the MIT and GPL
 *
 * Based on code originally provided by
 * Philip Taylor: http://philip.html5.org
 */


x3dom.EarClipping = {
	
	reversePointDirection: function (linklist, plane) {
			var l, k;
			var z = 0;
			var nodei, nodel, nodek;
			
			if (linklist.length < 3) {
				return false;
			}
			
			for (var i = 0; i < linklist.length; i++) {
				l = (i + 1) % linklist.length;
				
				nodei = linklist.getNode(i);
				nodel = linklist.getNode(l);
				// use standard shoelace			
				if(plane == 'YZ') {
					z  += (nodel.point.y - nodei.point.y) * (nodel.point.z + nodei.point.z);
				} else if(plane == 'XZ') {
					z  += (nodel.point.z - nodei.point.z) * (nodel.point.x + nodei.point.x);
				} else {
					z  += (nodel.point.x - nodei.point.x) * (nodel.point.y + nodei.point.y);
				}
			}
			//if counterclockwise
			if (z > 0) {
				linklist.invert();
				return true;
			}	
			return false;
	}, 

	getIndexes: function (linklist) {
		var node = linklist.first.next;
		var plane = this.identifyPlane(node.prev.point, node.point, node.next.point);
		
		var invers = this.reversePointDirection(linklist, plane);
		var indexes = [];
		node = linklist.first.next;
		var next = null;
		var timeout = 5000;
		var t0 = Date.now();
			
		var isEar = true;
		while(linklist.length >= 3)  {
			next = node.next;
			if(this.isKonvex(node.prev.point, node.point, node.next.point, plane)) {
				for(var i = 0; i < linklist.length; i++) {
					if(this.isNotEar(linklist.getNode(i).point, node.prev.point, node.point, node.next.point, plane)) {
						isEar = false;
						break; // one point in triangle suffices
					}
				}
				if(isEar) {
					indexes.push(node.prev.point_index, node.point_index, node.next.point_index);
					linklist.deleteNode(node);
				}
			}
			node = next;
			isEar = true;
			if (Date.now() - t0 > timeout) { x3dom.debug.logError("Ear clipping timed out."); break; }
		}
		if(invers){
			return indexes.reverse();
		} else {
			return indexes;
		}
	},

	getMultiIndexes: function (linklist) {
		var node = linklist.first.next;
		var plane = this.identifyPlane(node.prev.point, node.point, node.next.point);
		var invers = this.reversePointDirection(linklist, plane);
		
		var data = {};
		data.indices = [];
		data.point = [];
		data.normals = [];
		data.colors = [];
		data.texCoords = [];
		node = linklist.first.next;
		var next = null;
		var timeout = 5000;
		var t0 = Date.now();
		
		var isEar = true;
		while(linklist.length >= 3) {
			next = node.next;
			if(this.isKonvex(node.prev.point, node.point, node.next.point, plane)) {
				for(var i = 0; i < linklist.length; i++) {
					if(this.isNotEar(linklist.getNode(i).point, node.prev.point, node.point, node.next.point, plane)) {
						isEar = false;
						break;
					}
				}
				if(isEar) {
					data.indices.push(node.prev.point_index, node.point_index, node.next.point_index);
					data.point.push(node.prev.point, node.point, node.next.point);
					if(node.normals) {					
						data.normals.push(node.prev.normals, node.normals, node.next.normals);
					}
					if(node.colors){
						data.colors.push(node.prev.colors, node.colors,	node.next.colors);
					}
					if(node.texCoords){
						data.texCoords.push(node.prev.texCoords, node.texCoords, node.next.texCoords); 
					}
					linklist.deleteNode(node);
				}
			}
			node = next;
			isEar = true;
			//abort if too long
			if (Date.now() - t0 > timeout) { x3dom.debug.logError("Earclipping timed out."); break; }
		}
		if(invers){	
			data.indices = data.indices.reverse();
			data.point = data.point.reverse();
			data.normals = data.normals.reverse();
			data.colors = data.colors.reverse();
			data.texCoords = data.texCoords.reverse();
		}
		return data;
	}, 
	
	isNotEar: function (ap1, tp1, tp2, tp3, plane) {
		var b0, b1, b2, b3;
		var ap1a, ap1b, tp1a, tp1b, tp2a, tp2b, tp3a, tp3b;
		
		if(plane == 'YZ') {
			ap1a = ap1.y; ap1b = ap1.z;
			tp1a = tp1.y; tp1b = tp1.z;
			tp2a = tp2.y; tp2b = tp2.z;
			tp3a = tp3.y; tp3b = tp3.z;
		} else if(plane == 'XZ') {
			ap1a = ap1.z; ap1b = ap1.x;
			tp1a = tp1.z; tp1b = tp1.x;
			tp2a = tp2.z; tp2b = tp2.x;
			tp3a = tp3.z; tp3b = tp3.x;
		} else {
			ap1a = ap1.x; ap1b = ap1.y;
			tp1a = tp1.x; tp1b = tp1.y;
			tp2a = tp2.x; tp2b = tp2.y;
			tp3a = tp3.x; tp3b = tp3.y;
		}

        b0 = ((tp2a - tp1a) * (tp3b - tp1b) - (tp3a - tp1a) * (tp2b - tp1b));
        if (b0 != 0) {
            b1 = (((tp2a - ap1a) * (tp3b - ap1b) - (tp3a - ap1a) * (tp2b - ap1b)) / b0);
            b2 = (((tp3a - ap1a) * (tp1b - ap1b) - (tp1a - ap1a) * (tp3b - ap1b)) / b0);
            b3 = 1 - b1 - b2;

            return ((b1 > 0) && (b2 > 0) && (b3 > 0));
        }
        else {
            return false;
        }
    },

	isKonvex: function (p, p1, p2, plane) {
		var pa, pb, p1a, p1b, p2a, p2b;
		if(plane == 'YZ') {
			pa = p.y; pb = p.z;
			p1a = p1.y; p1b = p1.z;
			p2a = p2.y; p2b = p2.z;
		} else if(plane == 'XZ') {
			pa = p.z; pb = p.x;
			p1a = p1.z; p1b = p1.x;
			p2a = p2.z; p2b = p2.x;
		} else {
			pa = p.x; pb = p.y;
			p1a = p1.x; p1b = p1.y;
			p2a = p2.x; p2b = p2.y;
		}
		
		var l = ((p1a - pa) * (p2b - pb) - (p1b - pb) * (p2a - pa));
        return (l >= 0);
	},
	
	identifyPlane: function(p1, p2, p3) {
		var v1x, v1y, v1z;
		var v2x, v2y, v2z;
		var v3x, v3y, v3z;
	
		v1x = p2.x - p1.x; v1y = p2.y - p1.y; v1z = p2.z - p1.z;
		v2x = p3.x - p1.x; v2y = p3.y - p1.y; v2z = p3.z - p1.z;
		
		v3x = Math.abs(v1y*v2z - v1z*v2y);
		v3y = Math.abs(v1z*v2x - v1x*v2z);
		v3z = Math.abs(v1x*v2y - v1y*v2x);
		
		var angle = Math.max(v3x, v3y, v3z);
		
		if(angle == v3x) {
			return 'YZ';
		} else if(angle == v3y) {
			return 'XZ';
		} else if(angle == v3z) {
			return 'XY';
		} else {
			return 'XZ';    // error
		}
	}
};