Source: math/Intersection.js

  1. /**
  2. * @namespace Intersection
  3. * @memberof SQR
  4. *
  5. * @description Utility to perform intersection tests of rays against colliders. It is a static singleton, no need to instantiate. Just use: SQR.Intersection.rayTest(...)
  6. */
  7. SQR.Intersection = {};
  8. /**
  9. * Performs an intersection test of a ray against a transform that has a collider. J3D supports three types of colliders: sphere, box and mesh. This method will check what type of collider the transform has and call the apropriate method to make the intersection tests.
  10. *
  11. * WARNING. For meshes that have lots of polys, the ray/mesh intersection test can be very slow! It's better to wrap it into a box or sphere collider or have a simpler version of the mesh to make intersection tests against.
  12. *
  13. * @param {SQR.Ray} r an instance of J3D.Ray
  14. * @param {SQR.Transform} t a transform to test against.
  15. *
  16. * @returns True if ray intersects with the collider, false otherwise. If the transform doesn't have a collider the method returns false.
  17. */
  18. SQR.Intersection.rayTest = function(r, t) {
  19. if (!t.collider) {
  20. console.log("Intersection test failed. " + t.name + " has no collider.");
  21. return false;
  22. }
  23. if (!SQR.Intersection.__tv1) {
  24. SQR.Intersection.__tv1 = new SQR.V3();
  25. SQR.Intersection.__tv2 = new SQR.V3();
  26. SQR.Intersection.__tv3 = new SQR.V3();
  27. SQR.Intersection.__tv4 = new SQR.V3();
  28. SQR.Intersection.__tv5 = new SQR.V3();
  29. SQR.Intersection.__tv6 = new SQR.V3();
  30. SQR.Intersection.__tv7 = new SQR.V3();
  31. }
  32. switch (t.collider.type) {
  33. case SQR.Collider.SPHERE:
  34. return SQR.Intersection.raySphere(r, t);
  35. case SQR.Collider.BOX:
  36. return SQR.Intersection.rayBox(r, t);
  37. case SQR.Collider.MESH:
  38. return SQR.Intersection.rayMesh(r, t);
  39. default:
  40. console.log(t.collider);
  41. throw "> SQR.Intersection > unknown collider type on " + t.name;
  42. return false;
  43. }
  44. }
  45. /**
  46. * Performs an intersection test of a ray against a transform that has a mesh collider.
  47. *
  48. * WARNING. For meshes that have lots of polys, the ray/mesh intersection test can be very slow! It's better to wrap it into a box or sphere collider or have a simpler version of the mesh to make intersection tests against.
  49. *
  50. * @param {J3D.Ray} r an instance of J3D.Ray
  51. * @param {J3D.Transform} t a transform to test against.
  52. *
  53. * @returns True if ray intersects with the collider, false otherwise. If the transform doesn't have a geometry the method returns false.
  54. */
  55. SQR.Intersection.rayMesh = function(r, t) {
  56. if (t.collider.box) {
  57. if (!SQR.Intersection.rayBox(r, t)) {
  58. return false;
  59. }
  60. } else {
  61. r.makeLocal(t);
  62. }
  63. var v = t.buffer.getDataArray();
  64. var d = t.buffer.getIndexArray();
  65. var op = t.buffer.attributes['aPosition'].offset;
  66. var c = false;
  67. var p0 = SQR.Intersection.__tv1;
  68. var p1 = SQR.Intersection.__tv2;
  69. var p2 = SQR.Intersection.__tv3;
  70. for (var i = 0; i < d.length; i += 3) {
  71. var i0 = d[i + 0] * t.buffer.strideSize + op;
  72. var i1 = d[i + 1] * t.buffer.strideSize + op;
  73. var i2 = d[i + 2] * t.buffer.strideSize + op;
  74. p0.set(v[ i0 ], v[ i0 + 1 ], v[ i0 + 2 ]);
  75. p1.set(v[ i1 ], v[ i1 + 1 ], v[ i1 + 2 ]);
  76. p2.set(v[ i2 ], v[ i2 + 1 ], v[ i2 + 2 ]);
  77. c = c || SQR.Intersection.rayTriangle(r, p0, p1, p2);
  78. if (c) break;
  79. }
  80. return c;
  81. }
  82. /**
  83. * Performs an intersection test of a ray against a single triangle.
  84. * You should not have to call this method directly, unless you have specific needs, like ex. doing intersection tests for particles.
  85. */
  86. SQR.Intersection.rayTriangle = function(r, p0, p1, p2, n) {
  87. var p = SQR.Intersection.__tv4;
  88. var n = SQR.Intersection.__tv5;
  89. var t1 = SQR.Intersection.__tv6;
  90. var t2 = SQR.Intersection.__tv7;
  91. t1.sub(p0, p1);
  92. t2.sub(p2, p0);
  93. n.cross(t1, t2).norm();
  94. var dot = SQR.V3.dot(n, r.localDirection);
  95. if (!( dot < 0 )) {
  96. return false;
  97. }
  98. var d = SQR.V3.dot(n, p0);
  99. var t = d - SQR.V3.dot(n, r.localOrigin);
  100. if (!( t <= 0 )) {
  101. return false;
  102. }
  103. t = t / dot;
  104. p.copyFrom(r.localDirection);
  105. p = p.norm().mul(t);
  106. p.add(r.localOrigin);
  107. var u0, u1, u2, v0, v1, v2;
  108. if (Math.abs(n.x) > Math.abs(n.y)) {
  109. if (Math.abs(n.x) > Math.abs(n.z)) {
  110. u0 = p.y - p0.y;
  111. u1 = p1.y - p0.y;
  112. u2 = p2.y - p0.y;
  113. v0 = p.z - p0.z;
  114. v1 = p1.z - p0.z;
  115. v2 = p2.z - p0.z;
  116. } else {
  117. u0 = p.x - p0.x;
  118. u1 = p1.x - p0.x;
  119. u2 = p2.x - p0.x;
  120. v0 = p.y - p0.y;
  121. v1 = p1.y - p0.y;
  122. v2 = p2.y - p0.y;
  123. }
  124. } else {
  125. if (Math.abs(n.y) > Math.abs(n.z)) {
  126. u0 = p.x - p0.x;
  127. u1 = p1.x - p0.x;
  128. u2 = p2.x - p0.x;
  129. v0 = p.z - p0.z;
  130. v1 = p1.z - p0.z;
  131. v2 = p2.z - p0.z;
  132. } else {
  133. u0 = p.x - p0.x;
  134. u1 = p1.x - p0.x;
  135. u2 = p2.x - p0.x;
  136. v0 = p.y - p0.y;
  137. v1 = p1.y - p0.y;
  138. v2 = p2.y - p0.y;
  139. }
  140. }
  141. var temp = u1 * v2 - v1 * u2;
  142. if (!(temp != 0)) {
  143. return false;
  144. }
  145. temp = 1 / temp;
  146. var alpha = ( u0 * v2 - v0 * u2 ) * temp;
  147. if (!(alpha >= 0)) {
  148. return false;
  149. }
  150. var beta = ( u1 * v0 - v1 * u0 ) * temp;
  151. if (!(beta >= 0)) {
  152. return false;
  153. }
  154. var gamma = 1 - alpha - beta;
  155. if (!(gamma >= 0)) {
  156. return false;
  157. }
  158. return t;
  159. }
  160. /**
  161. * Performs an intersection test of a ray against a transform that has a sphere collider.
  162. *
  163. * @param {J3D.Ray} r an instance of J3D.Ray
  164. * @param {J3D.Transform} t a transform to test against.
  165. *
  166. * @returns True if ray intersects with the collider, false otherwise. If the transform doesn't have a sphere collider the method returns false.
  167. */
  168. SQR.Intersection.raySphere = function(r, t) {
  169. var e = SQR.Intersection.__tv1;
  170. var radius = t.collider.radius;
  171. var radiusSq = radius * radius;
  172. r.makeLocal(t);
  173. e.sub(t.collider.center, r.localOrigin);
  174. if (e.lengthSq < radiusSq) return false;
  175. var a = SQR.V3.dot(e, r.localDirection);
  176. if (a <= 0) return false;
  177. var t = radiusSq - ( e.magsq() - a * a );
  178. if (t >= 0) return Math.abs(a) - Math.sqrt(t);
  179. return false;
  180. };
  181. /**
  182. * Performs an intersection test of a ray against a transform that has a box collider.
  183. *
  184. * @param {J3D.Ray} r an instance of J3D.Ray
  185. * @param {J3D.Transform} t a transform to test against.
  186. *
  187. * @returns True if ray intersects with the collider, false otherwise. If the transform doesn't have a box collider the method returns false.
  188. */
  189. SQR.Intersection.rayBox = function(r, t) {
  190. var b = t.collider.box;
  191. r.makeLocal(t);
  192. var xt = 0, yt = 0, zt = 0;
  193. var xn = 0, yn = 0, zn = 0;
  194. var ins = true;
  195. if (r.localOrigin.x < b.minX) {
  196. xt = b.minX - r.localOrigin.x;
  197. //if(xt > r.localDirection.x) return return Number.MAX_VALUE;
  198. xt /= r.localDirection.x;
  199. ins = false;
  200. xn = -1;
  201. } else if (r.localOrigin.x > b.maxX) {
  202. xt = b.maxX - r.localOrigin.x;
  203. //if(xt < r.localDirection.x) return return Number.MAX_VALUE;
  204. xt /= r.localDirection.x;
  205. ins = false;
  206. xn = 1;
  207. }
  208. if (r.localOrigin.y < b.minY) {
  209. yt = b.minY - r.localOrigin.y;
  210. //if(yt > r.localDirection.y) return return Number.MAX_VALUE;
  211. yt /= r.localDirection.y;
  212. ins = false;
  213. yn = -1;
  214. } else if (r.localOrigin.y > b.maxY) {
  215. yt = b.maxY - r.localOrigin.y;
  216. //if(yt < r.localDirection.y) return return Number.MAX_VALUE;
  217. yt /= r.localDirection.y;
  218. ins = false;
  219. yn = 1;
  220. }
  221. if (r.localOrigin.z < b.minZ) {
  222. zt = b.minZ - r.localOrigin.z;
  223. //if(zt > r.direction.z) return return Number.MAX_VALUE;
  224. zt /= r.localDirection.z;
  225. ins = false;
  226. zn = -1;
  227. } else if (r.localOrigin.z > b.maxZ) {
  228. zt = b.maxZ - r.localOrigin.z;
  229. //if(zt < r.direction.z) return return Number.MAX_VALUE;
  230. zt /= r.localDirection.z;
  231. ins = false;
  232. zn = 1;
  233. }
  234. if (ins) return -1;
  235. var which = 0;
  236. var td = xt;
  237. if (yt > td) {
  238. which = 1;
  239. td = yt;
  240. }
  241. if (zt > td) {
  242. which = 2;
  243. td = zt;
  244. }
  245. switch (which) {
  246. case 0:
  247. var y = r.localOrigin.y + r.localDirection.y * td;
  248. if (y < b.minY || y > b.maxY) return false;
  249. var z = r.localOrigin.z + r.localDirection.z * td;
  250. if (z < b.minZ || z > b.maxZ) return false;
  251. //ab.normal = v3(xn, 0, 0);
  252. break;
  253. case 1:
  254. var x = r.localOrigin.x + r.localDirection.x * td;
  255. if (x < b.minX || x > b.maxX) return false;
  256. var z = r.localOrigin.z + r.localDirection.z * td;
  257. if (z < b.minZ || z > b.maxZ) return false;
  258. //ab.normal = v3(0, yn, 0);
  259. break;
  260. case 2:
  261. var x = r.localOrigin.x + r.localDirection.x * td;
  262. if (x < b.minX || x > b.maxX) return false;
  263. var y = r.localOrigin.y + r.localDirection.y * td;
  264. if (y < b.minY || y > b.maxY) return false;
  265. //ab.normal = new v3(0, 0, zn);
  266. break;
  267. }
  268. return td;
  269. }