1 /**
  2  * @author qiao / https://github.com/qiao
  3  * @fileoverview This is a convex hull generator using the incremental method. 
  4  * The complexity is O(n^2) where n is the number of vertices.
  5  * O(nlogn) algorithms do exist, but they are much more complicated.
  6  *
  7  * Benchmark: 
  8  *
  9  *  Platform: CPU: P7350 @2.00GHz Engine: V8
 10  *
 11  *  Num Vertices	Time(ms)
 12  *
 13  *     10           1
 14  *     20           3
 15  *     30           19
 16  *     40           48
 17  *     50           107
 18  */
 19 
 20 /**@constructor*/
 21 THREE.ConvexGeometry = function( vertices ) {
 22 
 23 	THREE.Geometry.call( this );
 24 
 25 	var faces = [ [ 0, 1, 2 ], [ 0, 2, 1 ] ]; 
 26 
 27 	for ( var i = 3; i < vertices.length; i++ ) {
 28 
 29 		addPoint( i );
 30 
 31 	}
 32 
 33 
 34 	function addPoint( vertexId ) {
 35 
 36 		var vertex = vertices[ vertexId ].clone();
 37 
 38 		var mag = vertex.length();
 39 		vertex.x += mag * randomOffset();
 40 		vertex.y += mag * randomOffset();
 41 		vertex.z += mag * randomOffset();
 42 
 43 		var hole = [];
 44 
 45 		for ( var f = 0; f < faces.length; ) {
 46 
 47 			var face = faces[ f ];
 48 
 49 			// for each face, if the vertex can see it,
 50 			// then we try to add the face's edges into the hole.
 51 			if ( visible( face, vertex ) ) {
 52 
 53 				for ( var e = 0; e < 3; e++ ) {
 54 
 55 					var edge = [ face[ e ], face[ ( e + 1 ) % 3 ] ];
 56 					var boundary = true;
 57 
 58 					// remove duplicated edges.
 59 					for ( var h = 0; h < hole.length; h++ ) {
 60 
 61 						if ( equalEdge( hole[ h ], edge ) ) {
 62 
 63 							hole[ h ] = hole[ hole.length - 1 ];
 64 							hole.pop();
 65 							boundary = false;
 66 							break;
 67 
 68 						}
 69 
 70 					}
 71 
 72 					if ( boundary ) {
 73 
 74 						hole.push( edge );
 75 
 76 					}
 77 
 78 				}
 79 
 80 				// remove faces[ f ]
 81 				faces[ f ] = faces[ faces.length - 1 ];
 82 				faces.pop();
 83 
 84 			} else { // not visible
 85 
 86 				f++;
 87 
 88 			}
 89 		}
 90 
 91 		// construct the new faces formed by the edges of the hole and the vertex
 92 		for ( var h = 0; h < hole.length; h++ ) {
 93 
 94 			faces.push( [ 
 95 				hole[ h ][ 0 ],
 96 				hole[ h ][ 1 ],
 97 				vertexId
 98 			] );
 99 
100 		}
101 	}
102 
103 	/**
104 	 * Whether the face is visible from the vertex
105 	 */
106 	function visible( face, vertex ) {
107 
108 		var va = vertices[ face[ 0 ] ];
109 		var vb = vertices[ face[ 1 ] ];
110 		var vc = vertices[ face[ 2 ] ];
111 
112 		var n = normal( va, vb, vc );
113 
114 		// distance from face to origin
115 		var dist = n.dot( va );
116 
117 		return n.dot( vertex ) >= dist; 
118 
119 	}
120 
121 	/**
122 	 * Face normal
123 	 */
124 	function normal( va, vb, vc ) {
125 
126 		var cb = new THREE.Vector3();
127 		var ab = new THREE.Vector3();
128 
129 		cb.sub( vc, vb );
130 		ab.sub( va, vb );
131 		cb.crossSelf( ab );
132 
133 		cb.normalize();
134 
135 		return cb;
136 
137 	}
138 
139 	/**
140 	 * Detect whether two edges are equal.
141 	 * Note that when constructing the convex hull, two same edges can only
142 	 * be of the negative direction.
143 	 */
144 	function equalEdge( ea, eb ) {
145 
146 		return ea[ 0 ] === eb[ 1 ] && ea[ 1 ] === eb[ 0 ]; 
147 
148 	}
149 
150 	/**
151 	 * Create a random offset between -1e-6 and 1e-6.
152 	 */
153 	function randomOffset() {
154 
155 		return ( Math.random() - 0.5 ) * 2 * 1e-6;
156 
157 	}
158 
159 
160 	/**
161 	 * XXX: Not sure if this is the correct approach. Need someone to review.
162 	 */
163 	function vertexUv( vertex ) {
164 
165 		var mag = vertex.length();
166 		return new THREE.UV( vertex.x / mag, vertex.y / mag );
167 
168 	}
169 
170 	// Push vertices into `this.vertices`, skipping those inside the hull
171 	var id = 0;
172 	var newId = new Array( vertices.length ); // map from old vertex id to new id
173 
174 	for ( var i = 0; i < faces.length; i++ ) {
175 
176 		 var face = faces[ i ];
177 
178 		 for ( var j = 0; j < 3; j++ ) {
179 
180 				if ( newId[ face[ j ] ] === undefined ) {
181 
182 						newId[ face[ j ] ] = id++;
183 						this.vertices.push( vertices[ face[ j ] ] );
184 
185 				}
186 
187 				face[ j ] = newId[ face[ j ] ];
188 
189 		 }
190 
191 	}
192 
193 	// Convert faces into instances of THREE.Face3
194 	for ( var i = 0; i < faces.length; i++ ) {
195 
196 		this.faces.push( new THREE.Face3( 
197 				faces[ i ][ 0 ],
198 				faces[ i ][ 1 ],
199 				faces[ i ][ 2 ]
200 		) );
201 
202 	}
203 
204 	// Compute UVs
205 	for ( var i = 0; i < this.faces.length; i++ ) {
206 
207 		var face = this.faces[ i ];
208 
209 		this.faceVertexUvs[ 0 ].push( [
210 			vertexUv( this.vertices[ face.a ] ),
211 			vertexUv( this.vertices[ face.b ] ),
212 			vertexUv( this.vertices[ face.c ])
213 		] );
214 
215 	}
216 
217 
218 	this.computeCentroids();
219 	this.computeFaceNormals();
220 	this.computeVertexNormals();
221 
222 };
223 
224 THREE.ConvexGeometry.prototype = Object.create( THREE.Geometry.prototype );
225 

nike free rn new balance hombre baratas cinturones gucci ugg rebajas cinturon gucci ray ban baratas nike cortez peuterey mujer christian louboutin madrid mbt zapatos gafas ray ban baratas mbt ofertas air max blancas mbt barcelona nike air max 90 woolrich barcelona nike mujer botas ugg gafas de sol carrera aratas air max 2016 baratas oakley baratas nike air max 2016