Geometry.js 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666
  1. /**
  2. * @author mrdoob / http://mrdoob.com/
  3. * @author kile / http://kile.stravaganza.org/
  4. * @author alteredq / http://alteredqualia.com/
  5. * @author mikael emtinger / http://gomo.se/
  6. * @author zz85 / http://www.lab4games.net/zz85/blog
  7. * @author bhouston / http://exocortex.com
  8. */
  9. THREE.Geometry = function () {
  10. this.id = THREE.GeometryIdCount ++;
  11. this.uuid = THREE.Math.generateUUID();
  12. this.name = '';
  13. this.vertices = [];
  14. this.colors = []; // one-to-one vertex colors, used in ParticleSystem, Line and Ribbon
  15. this.normals = []; // one-to-one vertex normals, used in Ribbon
  16. this.faces = [];
  17. this.faceUvs = [[]];
  18. this.faceVertexUvs = [[]];
  19. this.morphTargets = [];
  20. this.morphColors = [];
  21. this.morphNormals = [];
  22. this.skinWeights = [];
  23. this.skinIndices = [];
  24. this.lineDistances = [];
  25. this.boundingBox = null;
  26. this.boundingSphere = null;
  27. this.hasTangents = false;
  28. this.dynamic = true; // the intermediate typed arrays will be deleted when set to false
  29. // update flags
  30. this.verticesNeedUpdate = false;
  31. this.elementsNeedUpdate = false;
  32. this.uvsNeedUpdate = false;
  33. this.normalsNeedUpdate = false;
  34. this.tangentsNeedUpdate = false;
  35. this.colorsNeedUpdate = false;
  36. this.lineDistancesNeedUpdate = false;
  37. this.buffersNeedUpdate = false;
  38. };
  39. THREE.Geometry.prototype = {
  40. constructor: THREE.Geometry,
  41. applyMatrix: function ( matrix ) {
  42. var normalMatrix = new THREE.Matrix3().getNormalMatrix( matrix );
  43. for ( var i = 0, il = this.vertices.length; i < il; i ++ ) {
  44. var vertex = this.vertices[ i ];
  45. vertex.applyMatrix4( matrix );
  46. }
  47. for ( var i = 0, il = this.faces.length; i < il; i ++ ) {
  48. var face = this.faces[ i ];
  49. face.normal.applyMatrix3( normalMatrix ).normalize();
  50. for ( var j = 0, jl = face.vertexNormals.length; j < jl; j ++ ) {
  51. face.vertexNormals[ j ].applyMatrix3( normalMatrix ).normalize();
  52. }
  53. face.centroid.applyMatrix4( matrix );
  54. }
  55. if ( this.boundingBox instanceof THREE.Box3 ) {
  56. this.computeBoundingBox();
  57. }
  58. if ( this.boundingSphere instanceof THREE.Sphere ) {
  59. this.computeBoundingSphere();
  60. }
  61. },
  62. computeCentroids: function () {
  63. var f, fl, face;
  64. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  65. face = this.faces[ f ];
  66. face.centroid.set( 0, 0, 0 );
  67. face.centroid.add( this.vertices[ face.a ] );
  68. face.centroid.add( this.vertices[ face.b ] );
  69. face.centroid.add( this.vertices[ face.c ] );
  70. face.centroid.divideScalar( 3 );
  71. }
  72. },
  73. computeFaceNormals: function () {
  74. var cb = new THREE.Vector3(), ab = new THREE.Vector3();
  75. for ( var f = 0, fl = this.faces.length; f < fl; f ++ ) {
  76. var face = this.faces[ f ];
  77. var vA = this.vertices[ face.a ];
  78. var vB = this.vertices[ face.b ];
  79. var vC = this.vertices[ face.c ];
  80. cb.subVectors( vC, vB );
  81. ab.subVectors( vA, vB );
  82. cb.cross( ab );
  83. cb.normalize();
  84. face.normal.copy( cb );
  85. }
  86. },
  87. computeVertexNormals: function ( areaWeighted ) {
  88. var v, vl, f, fl, face, vertices;
  89. // create internal buffers for reuse when calling this method repeatedly
  90. // (otherwise memory allocation / deallocation every frame is big resource hog)
  91. if ( this.__tmpVertices === undefined ) {
  92. this.__tmpVertices = new Array( this.vertices.length );
  93. vertices = this.__tmpVertices;
  94. for ( v = 0, vl = this.vertices.length; v < vl; v ++ ) {
  95. vertices[ v ] = new THREE.Vector3();
  96. }
  97. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  98. face = this.faces[ f ];
  99. face.vertexNormals = [ new THREE.Vector3(), new THREE.Vector3(), new THREE.Vector3() ];
  100. }
  101. } else {
  102. vertices = this.__tmpVertices;
  103. for ( v = 0, vl = this.vertices.length; v < vl; v ++ ) {
  104. vertices[ v ].set( 0, 0, 0 );
  105. }
  106. }
  107. if ( areaWeighted ) {
  108. // vertex normals weighted by triangle areas
  109. // http://www.iquilezles.org/www/articles/normals/normals.htm
  110. var vA, vB, vC, vD;
  111. var cb = new THREE.Vector3(), ab = new THREE.Vector3(),
  112. db = new THREE.Vector3(), dc = new THREE.Vector3(), bc = new THREE.Vector3();
  113. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  114. face = this.faces[ f ];
  115. vA = this.vertices[ face.a ];
  116. vB = this.vertices[ face.b ];
  117. vC = this.vertices[ face.c ];
  118. cb.subVectors( vC, vB );
  119. ab.subVectors( vA, vB );
  120. cb.cross( ab );
  121. vertices[ face.a ].add( cb );
  122. vertices[ face.b ].add( cb );
  123. vertices[ face.c ].add( cb );
  124. }
  125. } else {
  126. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  127. face = this.faces[ f ];
  128. vertices[ face.a ].add( face.normal );
  129. vertices[ face.b ].add( face.normal );
  130. vertices[ face.c ].add( face.normal );
  131. }
  132. }
  133. for ( v = 0, vl = this.vertices.length; v < vl; v ++ ) {
  134. vertices[ v ].normalize();
  135. }
  136. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  137. face = this.faces[ f ];
  138. face.vertexNormals[ 0 ].copy( vertices[ face.a ] );
  139. face.vertexNormals[ 1 ].copy( vertices[ face.b ] );
  140. face.vertexNormals[ 2 ].copy( vertices[ face.c ] );
  141. }
  142. },
  143. computeMorphNormals: function () {
  144. var i, il, f, fl, face;
  145. // save original normals
  146. // - create temp variables on first access
  147. // otherwise just copy (for faster repeated calls)
  148. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  149. face = this.faces[ f ];
  150. if ( ! face.__originalFaceNormal ) {
  151. face.__originalFaceNormal = face.normal.clone();
  152. } else {
  153. face.__originalFaceNormal.copy( face.normal );
  154. }
  155. if ( ! face.__originalVertexNormals ) face.__originalVertexNormals = [];
  156. for ( i = 0, il = face.vertexNormals.length; i < il; i ++ ) {
  157. if ( ! face.__originalVertexNormals[ i ] ) {
  158. face.__originalVertexNormals[ i ] = face.vertexNormals[ i ].clone();
  159. } else {
  160. face.__originalVertexNormals[ i ].copy( face.vertexNormals[ i ] );
  161. }
  162. }
  163. }
  164. // use temp geometry to compute face and vertex normals for each morph
  165. var tmpGeo = new THREE.Geometry();
  166. tmpGeo.faces = this.faces;
  167. for ( i = 0, il = this.morphTargets.length; i < il; i ++ ) {
  168. // create on first access
  169. if ( ! this.morphNormals[ i ] ) {
  170. this.morphNormals[ i ] = {};
  171. this.morphNormals[ i ].faceNormals = [];
  172. this.morphNormals[ i ].vertexNormals = [];
  173. var dstNormalsFace = this.morphNormals[ i ].faceNormals;
  174. var dstNormalsVertex = this.morphNormals[ i ].vertexNormals;
  175. var faceNormal, vertexNormals;
  176. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  177. face = this.faces[ f ];
  178. faceNormal = new THREE.Vector3();
  179. if ( face instanceof THREE.Face3 ) {
  180. vertexNormals = { a: new THREE.Vector3(), b: new THREE.Vector3(), c: new THREE.Vector3() };
  181. } else {
  182. vertexNormals = { a: new THREE.Vector3(), b: new THREE.Vector3(), c: new THREE.Vector3(), d: new THREE.Vector3() };
  183. }
  184. dstNormalsFace.push( faceNormal );
  185. dstNormalsVertex.push( vertexNormals );
  186. }
  187. }
  188. var morphNormals = this.morphNormals[ i ];
  189. // set vertices to morph target
  190. tmpGeo.vertices = this.morphTargets[ i ].vertices;
  191. // compute morph normals
  192. tmpGeo.computeFaceNormals();
  193. tmpGeo.computeVertexNormals();
  194. // store morph normals
  195. var faceNormal, vertexNormals;
  196. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  197. face = this.faces[ f ];
  198. faceNormal = morphNormals.faceNormals[ f ];
  199. vertexNormals = morphNormals.vertexNormals[ f ];
  200. faceNormal.copy( face.normal );
  201. if ( face instanceof THREE.Face3 ) {
  202. vertexNormals.a.copy( face.vertexNormals[ 0 ] );
  203. vertexNormals.b.copy( face.vertexNormals[ 1 ] );
  204. vertexNormals.c.copy( face.vertexNormals[ 2 ] );
  205. } else {
  206. vertexNormals.a.copy( face.vertexNormals[ 0 ] );
  207. vertexNormals.b.copy( face.vertexNormals[ 1 ] );
  208. vertexNormals.c.copy( face.vertexNormals[ 2 ] );
  209. vertexNormals.d.copy( face.vertexNormals[ 3 ] );
  210. }
  211. }
  212. }
  213. // restore original normals
  214. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  215. face = this.faces[ f ];
  216. face.normal = face.__originalFaceNormal;
  217. face.vertexNormals = face.__originalVertexNormals;
  218. }
  219. },
  220. computeTangents: function () {
  221. // based on http://www.terathon.com/code/tangent.html
  222. // tangents go to vertices
  223. var f, fl, v, vl, i, il, vertexIndex,
  224. face, uv, vA, vB, vC, uvA, uvB, uvC,
  225. x1, x2, y1, y2, z1, z2,
  226. s1, s2, t1, t2, r, t, test,
  227. tan1 = [], tan2 = [],
  228. sdir = new THREE.Vector3(), tdir = new THREE.Vector3(),
  229. tmp = new THREE.Vector3(), tmp2 = new THREE.Vector3(),
  230. n = new THREE.Vector3(), w;
  231. for ( v = 0, vl = this.vertices.length; v < vl; v ++ ) {
  232. tan1[ v ] = new THREE.Vector3();
  233. tan2[ v ] = new THREE.Vector3();
  234. }
  235. function handleTriangle( context, a, b, c, ua, ub, uc ) {
  236. vA = context.vertices[ a ];
  237. vB = context.vertices[ b ];
  238. vC = context.vertices[ c ];
  239. uvA = uv[ ua ];
  240. uvB = uv[ ub ];
  241. uvC = uv[ uc ];
  242. x1 = vB.x - vA.x;
  243. x2 = vC.x - vA.x;
  244. y1 = vB.y - vA.y;
  245. y2 = vC.y - vA.y;
  246. z1 = vB.z - vA.z;
  247. z2 = vC.z - vA.z;
  248. s1 = uvB.x - uvA.x;
  249. s2 = uvC.x - uvA.x;
  250. t1 = uvB.y - uvA.y;
  251. t2 = uvC.y - uvA.y;
  252. r = 1.0 / ( s1 * t2 - s2 * t1 );
  253. sdir.set( ( t2 * x1 - t1 * x2 ) * r,
  254. ( t2 * y1 - t1 * y2 ) * r,
  255. ( t2 * z1 - t1 * z2 ) * r );
  256. tdir.set( ( s1 * x2 - s2 * x1 ) * r,
  257. ( s1 * y2 - s2 * y1 ) * r,
  258. ( s1 * z2 - s2 * z1 ) * r );
  259. tan1[ a ].add( sdir );
  260. tan1[ b ].add( sdir );
  261. tan1[ c ].add( sdir );
  262. tan2[ a ].add( tdir );
  263. tan2[ b ].add( tdir );
  264. tan2[ c ].add( tdir );
  265. }
  266. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  267. face = this.faces[ f ];
  268. uv = this.faceVertexUvs[ 0 ][ f ]; // use UV layer 0 for tangents
  269. handleTriangle( this, face.a, face.b, face.c, 0, 1, 2 );
  270. }
  271. var faceIndex = [ 'a', 'b', 'c', 'd' ];
  272. for ( f = 0, fl = this.faces.length; f < fl; f ++ ) {
  273. face = this.faces[ f ];
  274. for ( i = 0; i < Math.min( face.vertexNormals.length, 3 ); i++ ) {
  275. n.copy( face.vertexNormals[ i ] );
  276. vertexIndex = face[ faceIndex[ i ] ];
  277. t = tan1[ vertexIndex ];
  278. // Gram-Schmidt orthogonalize
  279. tmp.copy( t );
  280. tmp.sub( n.multiplyScalar( n.dot( t ) ) ).normalize();
  281. // Calculate handedness
  282. tmp2.crossVectors( face.vertexNormals[ i ], t );
  283. test = tmp2.dot( tan2[ vertexIndex ] );
  284. w = (test < 0.0) ? -1.0 : 1.0;
  285. face.vertexTangents[ i ] = new THREE.Vector4( tmp.x, tmp.y, tmp.z, w );
  286. }
  287. }
  288. this.hasTangents = true;
  289. },
  290. computeLineDistances: function ( ) {
  291. var d = 0;
  292. var vertices = this.vertices;
  293. for ( var i = 0, il = vertices.length; i < il; i ++ ) {
  294. if ( i > 0 ) {
  295. d += vertices[ i ].distanceTo( vertices[ i - 1 ] );
  296. }
  297. this.lineDistances[ i ] = d;
  298. }
  299. },
  300. computeBoundingBox: function () {
  301. if ( this.boundingBox === null ) {
  302. this.boundingBox = new THREE.Box3();
  303. }
  304. this.boundingBox.setFromPoints( this.vertices );
  305. },
  306. computeBoundingSphere: function () {
  307. if ( this.boundingSphere === null ) {
  308. this.boundingSphere = new THREE.Sphere();
  309. }
  310. this.boundingSphere.setFromPoints( this.vertices );
  311. },
  312. /*
  313. * Checks for duplicate vertices with hashmap.
  314. * Duplicated vertices are removed
  315. * and faces' vertices are updated.
  316. */
  317. mergeVertices: function () {
  318. var verticesMap = {}; // Hashmap for looking up vertice by position coordinates (and making sure they are unique)
  319. var unique = [], changes = [];
  320. var v, key;
  321. var precisionPoints = 4; // number of decimal points, eg. 4 for epsilon of 0.0001
  322. var precision = Math.pow( 10, precisionPoints );
  323. var i,il, face;
  324. var indices, k, j, jl, u;
  325. // reset cache of vertices as it now will be changing.
  326. this.__tmpVertices = undefined;
  327. for ( i = 0, il = this.vertices.length; i < il; i ++ ) {
  328. v = this.vertices[ i ];
  329. key = Math.round( v.x * precision ) + '_' + Math.round( v.y * precision ) + '_' + Math.round( v.z * precision );
  330. if ( verticesMap[ key ] === undefined ) {
  331. verticesMap[ key ] = i;
  332. unique.push( this.vertices[ i ] );
  333. changes[ i ] = unique.length - 1;
  334. } else {
  335. //console.log('Duplicate vertex found. ', i, ' could be using ', verticesMap[key]);
  336. changes[ i ] = changes[ verticesMap[ key ] ];
  337. }
  338. };
  339. // if faces are completely degenerate after merging vertices, we
  340. // have to remove them from the geometry.
  341. var faceIndicesToRemove = [];
  342. for( i = 0, il = this.faces.length; i < il; i ++ ) {
  343. face = this.faces[ i ];
  344. face.a = changes[ face.a ];
  345. face.b = changes[ face.b ];
  346. face.c = changes[ face.c ];
  347. indices = [ face.a, face.b, face.c ];
  348. var dupIndex = -1;
  349. // if any duplicate vertices are found in a Face3
  350. // we have to remove the face as nothing can be saved
  351. for ( var n = 0; n < 3; n ++ ) {
  352. if ( indices[ n ] == indices[ ( n + 1 ) % 3 ] ) {
  353. dupIndex = n;
  354. faceIndicesToRemove.push( i );
  355. break;
  356. }
  357. }
  358. }
  359. for ( i = faceIndicesToRemove.length - 1; i >= 0; i -- ) {
  360. this.faces.splice( i, 1 );
  361. for ( j = 0, jl = this.faceVertexUvs.length; j < jl; j ++ ) {
  362. this.faceVertexUvs[ j ].splice( i, 1 );
  363. }
  364. }
  365. // Use unique set of vertices
  366. var diff = this.vertices.length - unique.length;
  367. this.vertices = unique;
  368. return diff;
  369. },
  370. clone: function () {
  371. var geometry = new THREE.Geometry();
  372. var vertices = this.vertices;
  373. for ( var i = 0, il = vertices.length; i < il; i ++ ) {
  374. geometry.vertices.push( vertices[ i ].clone() );
  375. }
  376. var faces = this.faces;
  377. for ( var i = 0, il = faces.length; i < il; i ++ ) {
  378. geometry.faces.push( faces[ i ].clone() );
  379. }
  380. var uvs = this.faceVertexUvs[ 0 ];
  381. for ( var i = 0, il = uvs.length; i < il; i ++ ) {
  382. var uv = uvs[ i ], uvCopy = [];
  383. for ( var j = 0, jl = uv.length; j < jl; j ++ ) {
  384. uvCopy.push( new THREE.Vector2( uv[ j ].x, uv[ j ].y ) );
  385. }
  386. geometry.faceVertexUvs[ 0 ].push( uvCopy );
  387. }
  388. return geometry;
  389. },
  390. dispose: function () {
  391. this.dispatchEvent( { type: 'dispose' } );
  392. }
  393. };
  394. THREE.EventDispatcher.prototype.apply( THREE.Geometry.prototype );
  395. THREE.GeometryIdCount = 0;