ConvexObjectBreaker.js 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522
  1. /**
  2. * @fileoverview This class can be used to subdivide a convex Geometry object into pieces.
  3. *
  4. * Usage:
  5. *
  6. * Use the function prepareBreakableObject to prepare a Mesh object to be broken.
  7. *
  8. * Then, call the various functions to subdivide the object (subdivideByImpact, cutByPlane)
  9. *
  10. * Sub-objects that are product of subdivision don't need prepareBreakableObject to be called on them.
  11. *
  12. * Requisites for the object:
  13. *
  14. * - Mesh object must have a BufferGeometry (not Geometry) and a Material
  15. *
  16. * - Vertex normals must be planar (not smoothed)
  17. *
  18. * - The geometry must be convex (this is not checked in the library). You can create convex
  19. * geometries with THREE.ConvexGeometry. The BoxGeometry, SphereGeometry and other convex primitives
  20. * can also be used.
  21. *
  22. * Note: This lib adds member variables to object's userData member (see prepareBreakableObject function)
  23. * Use with caution and read the code when using with other libs.
  24. *
  25. * @param {double} minSizeForBreak Min size a debris can have to break.
  26. * @param {double} smallDelta Max distance to consider that a point belongs to a plane.
  27. *
  28. */
  29. THREE.ConvexObjectBreaker = function ( minSizeForBreak, smallDelta ) {
  30. this.minSizeForBreak = minSizeForBreak || 1.4;
  31. this.smallDelta = smallDelta || 0.0001;
  32. this.tempLine1 = new THREE.Line3();
  33. this.tempPlane1 = new THREE.Plane();
  34. this.tempPlane2 = new THREE.Plane();
  35. this.tempPlane_Cut = new THREE.Plane();
  36. this.tempCM1 = new THREE.Vector3();
  37. this.tempCM2 = new THREE.Vector3();
  38. this.tempVector3 = new THREE.Vector3();
  39. this.tempVector3_2 = new THREE.Vector3();
  40. this.tempVector3_3 = new THREE.Vector3();
  41. this.tempVector3_P0 = new THREE.Vector3();
  42. this.tempVector3_P1 = new THREE.Vector3();
  43. this.tempVector3_P2 = new THREE.Vector3();
  44. this.tempVector3_N0 = new THREE.Vector3();
  45. this.tempVector3_N1 = new THREE.Vector3();
  46. this.tempVector3_AB = new THREE.Vector3();
  47. this.tempVector3_CB = new THREE.Vector3();
  48. this.tempResultObjects = { object1: null, object2: null };
  49. this.segments = [];
  50. var n = 30 * 30;
  51. for ( var i = 0; i < n; i ++ ) this.segments[ i ] = false;
  52. };
  53. THREE.ConvexObjectBreaker.prototype = {
  54. constructor: THREE.ConvexObjectBreaker,
  55. prepareBreakableObject: function ( object, mass, velocity, angularVelocity, breakable ) {
  56. // object is a THREE.Object3d (normally a Mesh), must have a BufferGeometry, and it must be convex.
  57. // Its material property is propagated to its children (sub-pieces)
  58. // mass must be > 0
  59. if ( ! object.geometry.isBufferGeometry ) {
  60. console.error( 'THREE.ConvexObjectBreaker.prepareBreakableObject(): Parameter object must have a BufferGeometry.' );
  61. }
  62. var userData = object.userData;
  63. userData.mass = mass;
  64. userData.velocity = velocity.clone();
  65. userData.angularVelocity = angularVelocity.clone();
  66. userData.breakable = breakable;
  67. },
  68. /*
  69. * @param {int} maxRadialIterations Iterations for radial cuts.
  70. * @param {int} maxRandomIterations Max random iterations for not-radial cuts
  71. *
  72. * Returns the array of pieces
  73. */
  74. subdivideByImpact: function ( object, pointOfImpact, normal, maxRadialIterations, maxRandomIterations ) {
  75. var debris = [];
  76. var tempPlane1 = this.tempPlane1;
  77. var tempPlane2 = this.tempPlane2;
  78. this.tempVector3.addVectors( pointOfImpact, normal );
  79. tempPlane1.setFromCoplanarPoints( pointOfImpact, object.position, this.tempVector3 );
  80. var maxTotalIterations = maxRandomIterations + maxRadialIterations;
  81. var scope = this;
  82. function subdivideRadial( subObject, startAngle, endAngle, numIterations ) {
  83. if ( Math.random() < numIterations * 0.05 || numIterations > maxTotalIterations ) {
  84. debris.push( subObject );
  85. return;
  86. }
  87. var angle = Math.PI;
  88. if ( numIterations === 0 ) {
  89. tempPlane2.normal.copy( tempPlane1.normal );
  90. tempPlane2.constant = tempPlane1.constant;
  91. } else {
  92. if ( numIterations <= maxRadialIterations ) {
  93. angle = ( endAngle - startAngle ) * ( 0.2 + 0.6 * Math.random() ) + startAngle;
  94. // Rotate tempPlane2 at impact point around normal axis and the angle
  95. scope.tempVector3_2.copy( object.position ).sub( pointOfImpact ).applyAxisAngle( normal, angle ).add( pointOfImpact );
  96. tempPlane2.setFromCoplanarPoints( pointOfImpact, scope.tempVector3, scope.tempVector3_2 );
  97. } else {
  98. angle = ( ( 0.5 * ( numIterations & 1 ) ) + 0.2 * ( 2 - Math.random() ) ) * Math.PI;
  99. // Rotate tempPlane2 at object position around normal axis and the angle
  100. scope.tempVector3_2.copy( pointOfImpact ).sub( subObject.position ).applyAxisAngle( normal, angle ).add( subObject.position );
  101. scope.tempVector3_3.copy( normal ).add( subObject.position );
  102. tempPlane2.setFromCoplanarPoints( subObject.position, scope.tempVector3_3, scope.tempVector3_2 );
  103. }
  104. }
  105. // Perform the cut
  106. scope.cutByPlane( subObject, tempPlane2, scope.tempResultObjects );
  107. var obj1 = scope.tempResultObjects.object1;
  108. var obj2 = scope.tempResultObjects.object2;
  109. if ( obj1 ) {
  110. subdivideRadial( obj1, startAngle, angle, numIterations + 1 );
  111. }
  112. if ( obj2 ) {
  113. subdivideRadial( obj2, angle, endAngle, numIterations + 1 );
  114. }
  115. }
  116. subdivideRadial( object, 0, 2 * Math.PI, 0 );
  117. return debris;
  118. },
  119. cutByPlane: function ( object, plane, output ) {
  120. // Returns breakable objects in output.object1 and output.object2 members, the resulting 2 pieces of the cut.
  121. // object2 can be null if the plane doesn't cut the object.
  122. // object1 can be null only in case of internal error
  123. // Returned value is number of pieces, 0 for error.
  124. var geometry = object.geometry;
  125. var coords = geometry.attributes.position.array;
  126. var normals = geometry.attributes.normal.array;
  127. var numPoints = coords.length / 3;
  128. var numFaces = numPoints / 3;
  129. var indices = geometry.getIndex();
  130. if ( indices ) {
  131. indices = indices.array;
  132. numFaces = indices.length / 3;
  133. }
  134. function getVertexIndex( faceIdx, vert ) {
  135. // vert = 0, 1 or 2.
  136. var idx = faceIdx * 3 + vert;
  137. return indices ? indices[ idx ] : idx;
  138. }
  139. var points1 = [];
  140. var points2 = [];
  141. var delta = this.smallDelta;
  142. // Reset segments mark
  143. var numPointPairs = numPoints * numPoints;
  144. for ( var i = 0; i < numPointPairs; i ++ ) this.segments[ i ] = false;
  145. var p0 = this.tempVector3_P0;
  146. var p1 = this.tempVector3_P1;
  147. var n0 = this.tempVector3_N0;
  148. var n1 = this.tempVector3_N1;
  149. // Iterate through the faces to mark edges shared by coplanar faces
  150. for ( var i = 0; i < numFaces - 1; i ++ ) {
  151. var a1 = getVertexIndex( i, 0 );
  152. var b1 = getVertexIndex( i, 1 );
  153. var c1 = getVertexIndex( i, 2 );
  154. // Assuming all 3 vertices have the same normal
  155. n0.set( normals[ a1 ], normals[ a1 ] + 1, normals[ a1 ] + 2 );
  156. for ( var j = i + 1; j < numFaces; j ++ ) {
  157. var a2 = getVertexIndex( j, 0 );
  158. var b2 = getVertexIndex( j, 1 );
  159. var c2 = getVertexIndex( j, 2 );
  160. // Assuming all 3 vertices have the same normal
  161. n1.set( normals[ a2 ], normals[ a2 ] + 1, normals[ a2 ] + 2 );
  162. var coplanar = 1 - n0.dot( n1 ) < delta;
  163. if ( coplanar ) {
  164. if ( a1 === a2 || a1 === b2 || a1 === c2 ) {
  165. if ( b1 === a2 || b1 === b2 || b1 === c2 ) {
  166. this.segments[ a1 * numPoints + b1 ] = true;
  167. this.segments[ b1 * numPoints + a1 ] = true;
  168. } else {
  169. this.segments[ c1 * numPoints + a1 ] = true;
  170. this.segments[ a1 * numPoints + c1 ] = true;
  171. }
  172. } else if ( b1 === a2 || b1 === b2 || b1 === c2 ) {
  173. this.segments[ c1 * numPoints + b1 ] = true;
  174. this.segments[ b1 * numPoints + c1 ] = true;
  175. }
  176. }
  177. }
  178. }
  179. // Transform the plane to object local space
  180. var localPlane = this.tempPlane_Cut;
  181. object.updateMatrix();
  182. THREE.ConvexObjectBreaker.transformPlaneToLocalSpace( plane, object.matrix, localPlane );
  183. // Iterate through the faces adding points to both pieces
  184. for ( var i = 0; i < numFaces; i ++ ) {
  185. var va = getVertexIndex( i, 0 );
  186. var vb = getVertexIndex( i, 1 );
  187. var vc = getVertexIndex( i, 2 );
  188. for ( var segment = 0; segment < 3; segment ++ ) {
  189. var i0 = segment === 0 ? va : ( segment === 1 ? vb : vc );
  190. var i1 = segment === 0 ? vb : ( segment === 1 ? vc : va );
  191. var segmentState = this.segments[ i0 * numPoints + i1 ];
  192. if ( segmentState ) continue; // The segment already has been processed in another face
  193. // Mark segment as processed (also inverted segment)
  194. this.segments[ i0 * numPoints + i1 ] = true;
  195. this.segments[ i1 * numPoints + i0 ] = true;
  196. p0.set( coords[ 3 * i0 ], coords[ 3 * i0 + 1 ], coords[ 3 * i0 + 2 ] );
  197. p1.set( coords[ 3 * i1 ], coords[ 3 * i1 + 1 ], coords[ 3 * i1 + 2 ] );
  198. // mark: 1 for negative side, 2 for positive side, 3 for coplanar point
  199. var mark0 = 0;
  200. var d = localPlane.distanceToPoint( p0 );
  201. if ( d > delta ) {
  202. mark0 = 2;
  203. points2.push( p0.clone() );
  204. } else if ( d < - delta ) {
  205. mark0 = 1;
  206. points1.push( p0.clone() );
  207. } else {
  208. mark0 = 3;
  209. points1.push( p0.clone() );
  210. points2.push( p0.clone() );
  211. }
  212. // mark: 1 for negative side, 2 for positive side, 3 for coplanar point
  213. var mark1 = 0;
  214. var d = localPlane.distanceToPoint( p1 );
  215. if ( d > delta ) {
  216. mark1 = 2;
  217. points2.push( p1.clone() );
  218. } else if ( d < - delta ) {
  219. mark1 = 1;
  220. points1.push( p1.clone() );
  221. } else {
  222. mark1 = 3;
  223. points1.push( p1.clone() );
  224. points2.push( p1.clone() );
  225. }
  226. if ( ( mark0 === 1 && mark1 === 2 ) || ( mark0 === 2 && mark1 === 1 ) ) {
  227. // Intersection of segment with the plane
  228. this.tempLine1.start.copy( p0 );
  229. this.tempLine1.end.copy( p1 );
  230. var intersection = new THREE.Vector3();
  231. intersection = localPlane.intersectLine( this.tempLine1, intersection );
  232. if ( intersection === undefined ) {
  233. // Shouldn't happen
  234. console.error( 'Internal error: segment does not intersect plane.' );
  235. output.segmentedObject1 = null;
  236. output.segmentedObject2 = null;
  237. return 0;
  238. }
  239. points1.push( intersection );
  240. points2.push( intersection.clone() );
  241. }
  242. }
  243. }
  244. // Calculate debris mass (very fast and imprecise):
  245. var newMass = object.userData.mass * 0.5;
  246. // Calculate debris Center of Mass (again fast and imprecise)
  247. this.tempCM1.set( 0, 0, 0 );
  248. var radius1 = 0;
  249. var numPoints1 = points1.length;
  250. if ( numPoints1 > 0 ) {
  251. for ( var i = 0; i < numPoints1; i ++ ) this.tempCM1.add( points1[ i ] );
  252. this.tempCM1.divideScalar( numPoints1 );
  253. for ( var i = 0; i < numPoints1; i ++ ) {
  254. var p = points1[ i ];
  255. p.sub( this.tempCM1 );
  256. radius1 = Math.max( radius1, p.x, p.y, p.z );
  257. }
  258. this.tempCM1.add( object.position );
  259. }
  260. this.tempCM2.set( 0, 0, 0 );
  261. var radius2 = 0;
  262. var numPoints2 = points2.length;
  263. if ( numPoints2 > 0 ) {
  264. for ( var i = 0; i < numPoints2; i ++ ) this.tempCM2.add( points2[ i ] );
  265. this.tempCM2.divideScalar( numPoints2 );
  266. for ( var i = 0; i < numPoints2; i ++ ) {
  267. var p = points2[ i ];
  268. p.sub( this.tempCM2 );
  269. radius2 = Math.max( radius2, p.x, p.y, p.z );
  270. }
  271. this.tempCM2.add( object.position );
  272. }
  273. var object1 = null;
  274. var object2 = null;
  275. var numObjects = 0;
  276. if ( numPoints1 > 4 ) {
  277. object1 = new THREE.Mesh( new THREE.ConvexGeometry( points1 ), object.material );
  278. object1.position.copy( this.tempCM1 );
  279. object1.quaternion.copy( object.quaternion );
  280. this.prepareBreakableObject( object1, newMass, object.userData.velocity, object.userData.angularVelocity, 2 * radius1 > this.minSizeForBreak );
  281. numObjects ++;
  282. }
  283. if ( numPoints2 > 4 ) {
  284. object2 = new THREE.Mesh( new THREE.ConvexGeometry( points2 ), object.material );
  285. object2.position.copy( this.tempCM2 );
  286. object2.quaternion.copy( object.quaternion );
  287. this.prepareBreakableObject( object2, newMass, object.userData.velocity, object.userData.angularVelocity, 2 * radius2 > this.minSizeForBreak );
  288. numObjects ++;
  289. }
  290. output.object1 = object1;
  291. output.object2 = object2;
  292. return numObjects;
  293. }
  294. };
  295. THREE.ConvexObjectBreaker.transformFreeVector = function ( v, m ) {
  296. // input:
  297. // vector interpreted as a free vector
  298. // THREE.Matrix4 orthogonal matrix (matrix without scale)
  299. var x = v.x, y = v.y, z = v.z;
  300. var e = m.elements;
  301. v.x = e[ 0 ] * x + e[ 4 ] * y + e[ 8 ] * z;
  302. v.y = e[ 1 ] * x + e[ 5 ] * y + e[ 9 ] * z;
  303. v.z = e[ 2 ] * x + e[ 6 ] * y + e[ 10 ] * z;
  304. return v;
  305. };
  306. THREE.ConvexObjectBreaker.transformFreeVectorInverse = function ( v, m ) {
  307. // input:
  308. // vector interpreted as a free vector
  309. // THREE.Matrix4 orthogonal matrix (matrix without scale)
  310. var x = v.x, y = v.y, z = v.z;
  311. var e = m.elements;
  312. v.x = e[ 0 ] * x + e[ 1 ] * y + e[ 2 ] * z;
  313. v.y = e[ 4 ] * x + e[ 5 ] * y + e[ 6 ] * z;
  314. v.z = e[ 8 ] * x + e[ 9 ] * y + e[ 10 ] * z;
  315. return v;
  316. };
  317. THREE.ConvexObjectBreaker.transformTiedVectorInverse = function ( v, m ) {
  318. // input:
  319. // vector interpreted as a tied (ordinary) vector
  320. // THREE.Matrix4 orthogonal matrix (matrix without scale)
  321. var x = v.x, y = v.y, z = v.z;
  322. var e = m.elements;
  323. v.x = e[ 0 ] * x + e[ 1 ] * y + e[ 2 ] * z - e[ 12 ];
  324. v.y = e[ 4 ] * x + e[ 5 ] * y + e[ 6 ] * z - e[ 13 ];
  325. v.z = e[ 8 ] * x + e[ 9 ] * y + e[ 10 ] * z - e[ 14 ];
  326. return v;
  327. };
  328. THREE.ConvexObjectBreaker.transformPlaneToLocalSpace = function () {
  329. var v1 = new THREE.Vector3();
  330. return function transformPlaneToLocalSpace( plane, m, resultPlane ) {
  331. resultPlane.normal.copy( plane.normal );
  332. resultPlane.constant = plane.constant;
  333. var referencePoint = THREE.ConvexObjectBreaker.transformTiedVectorInverse( plane.coplanarPoint( v1 ), m );
  334. THREE.ConvexObjectBreaker.transformFreeVectorInverse( resultPlane.normal, m );
  335. // recalculate constant (like in setFromNormalAndCoplanarPoint)
  336. resultPlane.constant = - referencePoint.dot( resultPlane.normal );
  337. };
  338. }();