raytrace.cpp
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:39k
源码类别:

游戏引擎

开发平台:

C++ Builder

  1. /** 
  2.  * @file raytrace.cpp
  3.  * @brief Functions called by box object scripts.
  4.  *
  5.  * $LicenseInfo:firstyear=2001&license=viewergpl$
  6.  * 
  7.  * Copyright (c) 2001-2010, Linden Research, Inc.
  8.  * 
  9.  * Second Life Viewer Source Code
  10.  * The source code in this file ("Source Code") is provided by Linden Lab
  11.  * to you under the terms of the GNU General Public License, version 2.0
  12.  * ("GPL"), unless you have obtained a separate licensing agreement
  13.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  14.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  15.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  16.  * 
  17.  * There are special exceptions to the terms and conditions of the GPL as
  18.  * it is applied to this Source Code. View the full text of the exception
  19.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  20.  * online at
  21.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  22.  * 
  23.  * By copying, modifying or distributing this software, you acknowledge
  24.  * that you have read and understood your obligations described above,
  25.  * and agree to abide by those obligations.
  26.  * 
  27.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  28.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  29.  * COMPLETENESS OR PERFORMANCE.
  30.  * $/LicenseInfo$
  31.  */
  32. #include "linden_common.h"
  33. #include "math.h"
  34. //#include "vmath.h"
  35. #include "v3math.h"
  36. #include "llquaternion.h"
  37. #include "m3math.h"
  38. #include "raytrace.h"
  39. BOOL line_plane(const LLVector3 &line_point, const LLVector3 &line_direction,
  40. const LLVector3 &plane_point, const LLVector3 plane_normal, 
  41. LLVector3 &intersection)
  42. {
  43. F32 N = line_direction * plane_normal;
  44. if (0.0f == N)
  45. {
  46. // line is perpendicular to plane normal
  47. // so it is either entirely on plane, or not on plane at all
  48. return FALSE;
  49. }
  50. // Ax + By, + Cz + D = 0
  51. // D = - (plane_point * plane_normal)
  52. // N = line_direction * plane_normal
  53. // intersection = line_point - ((D + plane_normal * line_point) / N) * line_direction
  54. intersection = line_point - ((plane_normal * line_point - plane_point * plane_normal) / N) * line_direction;
  55. return TRUE;
  56. }
  57. BOOL ray_plane(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  58.    const LLVector3 &plane_point, const LLVector3 plane_normal, 
  59.    LLVector3 &intersection)
  60. {
  61. F32 N = ray_direction * plane_normal;
  62. if (0.0f == N)
  63. {
  64. // ray is perpendicular to plane normal
  65. // so it is either entirely on plane, or not on plane at all
  66. return FALSE;
  67. }
  68. // Ax + By, + Cz + D = 0
  69. // D = - (plane_point * plane_normal)
  70. // N = ray_direction * plane_normal
  71. // intersection = ray_point - ((D + plane_normal * ray_point) / N) * ray_direction
  72. F32 alpha = -(plane_normal * ray_point - plane_point * plane_normal) / N;
  73. if (alpha < 0.0f)
  74. {
  75. // ray points away from plane
  76. return FALSE;
  77. }
  78. intersection = ray_point + alpha * ray_direction;
  79. return TRUE;
  80. }
  81. BOOL ray_circle(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  82. const LLVector3 &circle_center, const LLVector3 plane_normal, F32 circle_radius,
  83. LLVector3 &intersection)
  84. {
  85. if (ray_plane(ray_point, ray_direction, circle_center, plane_normal, intersection))
  86. {
  87. if (circle_radius >= (intersection - circle_center).magVec())
  88. {
  89. return TRUE;
  90. }
  91. }
  92. return FALSE;
  93. }
  94. BOOL ray_triangle(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  95.   const LLVector3 &point_0, const LLVector3 &point_1, const LLVector3 &point_2, 
  96.   LLVector3 &intersection, LLVector3 &intersection_normal)
  97. {
  98. LLVector3 side_01 = point_1 - point_0;
  99. LLVector3 side_12 = point_2 - point_1;
  100. intersection_normal = side_01 % side_12;
  101. intersection_normal.normVec();
  102. if (ray_plane(ray_point, ray_direction, point_0, intersection_normal, intersection))
  103. {
  104. LLVector3 side_20 = point_0 - point_2;
  105. if (intersection_normal * (side_01 % (intersection - point_0)) >= 0.0f  &&
  106. intersection_normal * (side_12 % (intersection - point_1)) >= 0.0f  &&
  107. intersection_normal * (side_20 % (intersection - point_2)) >= 0.0f)
  108. {
  109. return TRUE;
  110. }
  111. }
  112. return FALSE;
  113. }
  114. // assumes a parallelogram
  115. BOOL ray_quadrangle(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  116. const LLVector3 &point_0, const LLVector3 &point_1, const LLVector3 &point_2,
  117. LLVector3 &intersection, LLVector3 &intersection_normal)
  118. {
  119. LLVector3 side_01 = point_1 - point_0;
  120. LLVector3 side_12 = point_2 - point_1;
  121. intersection_normal = side_01 % side_12;
  122. intersection_normal.normVec();
  123. if (ray_plane(ray_point, ray_direction, point_0, intersection_normal, intersection))
  124. {
  125. LLVector3 point_3 = point_0 + (side_12);
  126. LLVector3 side_23 = point_3 - point_2;
  127. LLVector3 side_30 = point_0 - point_3;
  128. if (intersection_normal * (side_01 % (intersection - point_0)) >= 0.0f  &&
  129. intersection_normal * (side_12 % (intersection - point_1)) >= 0.0f  &&
  130. intersection_normal * (side_23 % (intersection - point_2)) >= 0.0f  &&
  131. intersection_normal * (side_30 % (intersection - point_3)) >= 0.0f)
  132. {
  133. return TRUE;
  134. }
  135. }
  136. return FALSE;
  137. }
  138. BOOL ray_sphere(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  139. const LLVector3 &sphere_center, F32 sphere_radius,
  140. LLVector3 &intersection, LLVector3 &intersection_normal)
  141. {
  142. LLVector3 ray_to_sphere = sphere_center - ray_point;
  143. F32 dot = ray_to_sphere * ray_direction;
  144. LLVector3 closest_approach = dot * ray_direction - ray_to_sphere;
  145. F32 shortest_distance = closest_approach.magVecSquared();
  146. F32 radius_squared = sphere_radius * sphere_radius;
  147. if (shortest_distance > radius_squared)
  148. {
  149. return FALSE;
  150. }
  151. F32 half_chord = (F32) sqrt(radius_squared - shortest_distance);
  152. closest_approach = sphere_center + closest_approach; // closest_approach now in absolute coordinates
  153. intersection = closest_approach + half_chord * ray_direction;
  154. dot = ray_direction * (intersection - ray_point);
  155. if (dot < 0.0f)
  156. {
  157. // ray shoots away from sphere and is not inside it
  158. return FALSE;
  159. }
  160. shortest_distance = ray_direction * ((closest_approach - half_chord * ray_direction) - ray_point);
  161. if (shortest_distance > 0.0f)
  162. {
  163. // ray enters sphere 
  164. intersection = intersection - (2.0f * half_chord) * ray_direction;
  165. }
  166. else
  167. {
  168. // do nothing
  169. // ray starts inside sphere and intersects as it leaves the sphere
  170. }
  171. intersection_normal = intersection - sphere_center;
  172. if (sphere_radius > 0.0f)
  173. {
  174. intersection_normal *= 1.0f / sphere_radius;
  175. }
  176. else
  177. {
  178. intersection_normal.setVec(0.0f, 0.0f, 0.0f);
  179. }
  180. return TRUE;
  181. }
  182. BOOL ray_cylinder(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  183.   const LLVector3 &cyl_center, const LLVector3 &cyl_scale, const LLQuaternion &cyl_rotation,
  184.   LLVector3 &intersection, LLVector3 &intersection_normal)
  185. {
  186. // calculate the centers of the cylinder caps in the absolute frame
  187. LLVector3 cyl_top(0.0f, 0.0f, 0.5f * cyl_scale.mV[VZ]);
  188. LLVector3 cyl_bottom(0.0f, 0.0f, -cyl_top.mV[VZ]);
  189. cyl_top = (cyl_top * cyl_rotation) + cyl_center;
  190. cyl_bottom = (cyl_bottom * cyl_rotation) + cyl_center;
  191. // we only handle cylinders with circular cross-sections at the moment
  192. F32 cyl_radius = 0.5f * llmax(cyl_scale.mV[VX], cyl_scale.mV[VY]); // HACK until scaled cylinders are supported
  193. // This implementation is based on the intcyl() function from Graphics_Gems_IV, page 361
  194. LLVector3   cyl_axis; // axis direction (bottom toward top)
  195. LLVector3  ray_to_cyl; // ray_point to cyl_top
  196. F32  shortest_distance; // shortest distance from ray to axis
  197. F32  cyl_length;
  198. LLVector3 shortest_direction;
  199. LLVector3 temp_vector;
  200. cyl_axis = cyl_bottom - cyl_top;
  201. cyl_length = cyl_axis.normVec();
  202. ray_to_cyl = ray_point - cyl_bottom;
  203. shortest_direction = ray_direction % cyl_axis;
  204. shortest_distance = shortest_direction.normVec(); // recycle shortest_distance
  205. // check for ray parallel to cylinder axis
  206. if (0.0f == shortest_distance)
  207. {
  208. // ray is parallel to cylinder axis
  209. temp_vector = ray_to_cyl - (ray_to_cyl * cyl_axis) * cyl_axis;
  210. shortest_distance = temp_vector.magVec();
  211. if (shortest_distance <= cyl_radius)
  212. {
  213. shortest_distance = ray_to_cyl * cyl_axis;
  214. F32 dot = ray_direction * cyl_axis;
  215. if (shortest_distance > 0.0)
  216. {
  217.     if (dot > 0.0f)
  218. {
  219. // ray points away from cylinder bottom
  220. return FALSE;
  221. }
  222. // ray hit bottom of cylinder from outside 
  223. intersection = ray_point - shortest_distance * cyl_axis;
  224. intersection_normal = cyl_axis;
  225. }
  226. else if (shortest_distance > -cyl_length)
  227. {
  228. // ray starts inside cylinder
  229. if (dot < 0.0f)
  230. {
  231. // ray hit top from inside
  232. intersection = ray_point - (cyl_length + shortest_distance) * cyl_axis;
  233. intersection_normal = -cyl_axis;
  234. }
  235. else
  236. {
  237. // ray hit bottom from inside
  238. intersection = ray_point - shortest_distance * cyl_axis;
  239. intersection_normal = cyl_axis;
  240. }
  241. }
  242. else
  243. {
  244. if (dot < 0.0f)
  245. {
  246. // ray points away from cylinder bottom
  247. return FALSE;
  248. }
  249. // ray hit top from outside
  250. intersection = ray_point - (shortest_distance + cyl_length) * cyl_axis;
  251. intersection_normal = -cyl_axis;
  252. }
  253. return TRUE;
  254. }
  255. return FALSE;
  256. }
  257. // check for intersection with infinite cylinder
  258. shortest_distance = (F32) fabs(ray_to_cyl * shortest_direction);
  259. if (shortest_distance <= cyl_radius)
  260. {
  261. F32  dist_to_closest_point; // dist from ray_point to closest_point
  262. F32  half_chord_length; // half length of intersection chord
  263. F32  in, out; // distances to entering/exiting points
  264. temp_vector = ray_to_cyl % cyl_axis;
  265. dist_to_closest_point = - (temp_vector * shortest_direction);
  266. temp_vector = shortest_direction % cyl_axis;
  267. temp_vector.normVec();
  268. half_chord_length = (F32) fabs( sqrt(cyl_radius*cyl_radius - shortest_distance * shortest_distance) /
  269. (ray_direction * temp_vector) );
  270. out = dist_to_closest_point + half_chord_length; // dist to exiting point
  271. if (out < 0.0f)
  272. {
  273. // cylinder is behind the ray, so we return FALSE
  274. return FALSE;
  275. }
  276. in = dist_to_closest_point - half_chord_length; // dist to entering point
  277. if (in < 0.0f)
  278. {
  279. // ray_point is inside the cylinder
  280. // so we store the exiting intersection
  281. intersection = ray_point + out * ray_direction;
  282. shortest_distance = out;
  283. }
  284. else
  285. {
  286. // ray hit cylinder from outside
  287. // so we store the entering intersection
  288. intersection = ray_point + in * ray_direction;
  289. shortest_distance = in;
  290. }
  291. // calculate the normal at intersection
  292. if (0.0f == cyl_radius)
  293. {
  294. intersection_normal.setVec(0.0f, 0.0f, 0.0f);
  295. }
  296. else
  297. {
  298. temp_vector = intersection - cyl_bottom;
  299. intersection_normal = temp_vector - (temp_vector * cyl_axis) * cyl_axis;
  300. intersection_normal.normVec();
  301. }
  302. // check for intersection with end caps
  303. // calculate intersection of ray and top plane
  304. if (line_plane(ray_point, ray_direction, cyl_top, -cyl_axis, temp_vector)) // NOTE side-effect: changing temp_vector
  305. {
  306. shortest_distance = (temp_vector - ray_point).magVec();
  307. if ( (ray_direction * cyl_axis) > 0.0f)
  308. {
  309. // ray potentially enters the cylinder at top
  310. if (shortest_distance > out)
  311. {
  312. // ray missed the finite cylinder
  313. return FALSE;
  314. }
  315. if (shortest_distance > in)
  316. {
  317. // ray intersects cylinder at top plane
  318. intersection = temp_vector;
  319. intersection_normal = -cyl_axis;
  320. return TRUE;
  321. }
  322. }
  323. else
  324. {
  325. // ray potentially exits the cylinder at top
  326. if (shortest_distance < in)
  327. {
  328. // missed the finite cylinder
  329. return FALSE;
  330. }
  331. }
  332. // calculate intersection of ray and bottom plane
  333. line_plane(ray_point, ray_direction, cyl_bottom, cyl_axis, temp_vector); // NOTE side-effect: changing temp_vector
  334. shortest_distance = (temp_vector - ray_point).magVec();
  335. if ( (ray_direction * cyl_axis) < 0.0)
  336. {
  337. // ray potentially enters the cylinder at bottom
  338. if (shortest_distance > out)
  339. {
  340. // ray missed the finite cylinder
  341. return FALSE;
  342. }
  343. if (shortest_distance > in)
  344. {
  345. // ray intersects cylinder at bottom plane
  346. intersection = temp_vector;
  347. intersection_normal = cyl_axis;
  348. return TRUE;
  349. }
  350. }
  351. else
  352. {
  353. // ray potentially exits the cylinder at bottom
  354. if (shortest_distance < in)
  355. {
  356. // ray missed the finite cylinder
  357. return FALSE;
  358. }
  359. }
  360. }
  361. else
  362. {
  363. // ray is parallel to end cap planes
  364. temp_vector = cyl_bottom - ray_point;
  365. shortest_distance = temp_vector * cyl_axis;
  366. if (shortest_distance < 0.0f  ||  shortest_distance > cyl_length)
  367. {
  368. // ray missed finite cylinder
  369. return FALSE;
  370. }
  371. }
  372. return TRUE;
  373. }
  374. return FALSE;
  375. }
  376. U32 ray_box(const LLVector3 &ray_point, const LLVector3 &ray_direction, 
  377. const LLVector3 &box_center, const LLVector3 &box_scale, const LLQuaternion &box_rotation,
  378. LLVector3 &intersection, LLVector3 &intersection_normal)
  379. {
  380. // Need to rotate into box frame
  381. LLQuaternion into_box_frame(box_rotation); // rotates things from box frame to absolute
  382. into_box_frame.conjQuat(); // now rotates things into box frame
  383. LLVector3 line_point = (ray_point - box_center) * into_box_frame;
  384. LLVector3 line_direction = ray_direction * into_box_frame;
  385. // Suppose we have a plane:  Ax + By + Cz + D = 0
  386. // then, assuming [A, B, C] is a unit vector:
  387. //
  388. //    plane_normal = [A, B, C] 
  389. //    D = - (plane_normal * plane_point)
  390. // 
  391. // Suppose we have a line:  X = line_point + alpha * line_direction
  392. //
  393. // the intersection of the plane and line determines alpha
  394. //
  395. //    alpha = - (D + plane_normal * line_point) / (plane_normal * line_direction)
  396. LLVector3 line_plane_intersection;
  397. F32 pointX = line_point.mV[VX];
  398. F32 pointY = line_point.mV[VY];
  399. F32 pointZ = line_point.mV[VZ];
  400. F32 dirX = line_direction.mV[VX];
  401. F32 dirY = line_direction.mV[VY];
  402. F32 dirZ = line_direction.mV[VZ];
  403. // we'll be using the half-scales of the box
  404. F32 boxX = 0.5f * box_scale.mV[VX];
  405. F32 boxY = 0.5f * box_scale.mV[VY];
  406. F32 boxZ = 0.5f * box_scale.mV[VZ];
  407. // check to see if line_point is OUTSIDE the box
  408. if (pointX < -boxX ||
  409. pointX >  boxX ||
  410. pointY < -boxY ||
  411. pointY >  boxY ||
  412. pointZ < -boxZ ||
  413. pointZ >  boxZ) 
  414. {
  415. // -------------- point is OUTSIDE the box ----------------
  416. // front
  417. if (pointX > 0.0f  &&  dirX < 0.0f)
  418. {
  419. // plane_normal                = [ 1, 0, 0]
  420. // plane_normal*line_point     = pointX
  421. // plane_normal*line_direction = dirX
  422. // D                           = -boxX
  423. // alpha                       = - (-boxX + pointX) / dirX
  424. line_plane_intersection = line_point - ((pointX - boxX) / dirX) * line_direction;
  425. if (line_plane_intersection.mV[VY] <  boxY &&
  426. line_plane_intersection.mV[VY] > -boxY &&
  427. line_plane_intersection.mV[VZ] <  boxZ &&
  428. line_plane_intersection.mV[VZ] > -boxZ )
  429. {
  430. intersection = (line_plane_intersection * box_rotation) + box_center;
  431. intersection_normal = LLVector3(1.0f, 0.0f, 0.0f) * box_rotation;
  432. return FRONT_SIDE;
  433. }
  434. }
  435. // back
  436. if (pointX < 0.0f  &&  dirX > 0.0f)
  437. {
  438. // plane_normal                = [ -1, 0, 0]
  439. // plane_normal*line_point     = -pX 
  440. // plane_normal*line_direction = -direction.mV[VX]
  441. // D                           = -bX
  442. // alpha                       = - (-bX - pX) / (-dirX)
  443. line_plane_intersection = line_point - ((boxX + pointX)/ dirX) * line_direction;
  444. if (line_plane_intersection.mV[VY] <  boxY &&
  445. line_plane_intersection.mV[VY] > -boxY &&
  446. line_plane_intersection.mV[VZ] <  boxZ &&
  447. line_plane_intersection.mV[VZ] > -boxZ )
  448. {
  449. intersection = (line_plane_intersection * box_rotation) + box_center;
  450. intersection_normal = LLVector3(-1.0f, 0.0f, 0.0f) * box_rotation;
  451. return BACK_SIDE;
  452. }
  453. }
  454. // left
  455. if (pointY > 0.0f  &&  dirY < 0.0f)
  456. {
  457. // plane_normal                = [0, 1, 0]
  458. // plane_normal*line_point     = pointY 
  459. // plane_normal*line_direction = dirY
  460. // D                           = -boxY
  461. // alpha                       = - (-boxY + pointY) / dirY
  462. line_plane_intersection = line_point + ((boxY - pointY)/dirY) * line_direction;
  463. if (line_plane_intersection.mV[VX] <  boxX &&
  464. line_plane_intersection.mV[VX] > -boxX &&
  465. line_plane_intersection.mV[VZ] <  boxZ &&
  466. line_plane_intersection.mV[VZ] > -boxZ )
  467. {
  468. intersection = (line_plane_intersection * box_rotation) + box_center;
  469. intersection_normal = LLVector3(0.0f, 1.0f, 0.0f) * box_rotation;
  470. return LEFT_SIDE;
  471. }
  472. }
  473. // right
  474. if (pointY < 0.0f  &&  dirY > 0.0f)
  475. {
  476. // plane_normal                = [0, -1, 0]
  477. // plane_normal*line_point     = -pointY 
  478. // plane_normal*line_direction = -dirY
  479. // D                           = -boxY
  480. // alpha                       = - (-boxY - pointY) / (-dirY)
  481. line_plane_intersection = line_point - ((boxY + pointY)/dirY) * line_direction;
  482. if (line_plane_intersection.mV[VX] <  boxX &&
  483. line_plane_intersection.mV[VX] > -boxX &&
  484. line_plane_intersection.mV[VZ] <  boxZ &&
  485. line_plane_intersection.mV[VZ] > -boxZ )
  486. {
  487. intersection = (line_plane_intersection * box_rotation) + box_center;
  488. intersection_normal = LLVector3(0.0f, -1.0f, 0.0f) * box_rotation;
  489. return RIGHT_SIDE;
  490. }
  491. }
  492. // top
  493. if (pointZ > 0.0f  &&  dirZ < 0.0f)
  494. {
  495. // plane_normal                = [0, 0, 1]
  496. // plane_normal*line_point     = pointZ 
  497. // plane_normal*line_direction = dirZ
  498. // D                           = -boxZ
  499. // alpha                       = - (-boxZ + pointZ) / dirZ
  500. line_plane_intersection = line_point - ((pointZ - boxZ)/dirZ) * line_direction;
  501. if (line_plane_intersection.mV[VX] <  boxX &&
  502. line_plane_intersection.mV[VX] > -boxX &&
  503. line_plane_intersection.mV[VY] <  boxY &&
  504. line_plane_intersection.mV[VY] > -boxY )
  505. {
  506. intersection = (line_plane_intersection * box_rotation) + box_center;
  507. intersection_normal = LLVector3(0.0f, 0.0f, 1.0f) * box_rotation;
  508. return TOP_SIDE;
  509. }
  510. }
  511. // bottom
  512. if (pointZ < 0.0f  &&  dirZ > 0.0f)
  513. {
  514. // plane_normal                = [0, 0, -1]
  515. // plane_normal*line_point     = -pointZ 
  516. // plane_normal*line_direction = -dirZ
  517. // D                           = -boxZ
  518. // alpha                       = - (-boxZ - pointZ) / (-dirZ)
  519. line_plane_intersection = line_point - ((boxZ + pointZ)/dirZ) * line_direction;
  520. if (line_plane_intersection.mV[VX] <  boxX &&
  521. line_plane_intersection.mV[VX] > -boxX &&
  522. line_plane_intersection.mV[VY] <  boxY &&
  523. line_plane_intersection.mV[VY] > -boxY )
  524. {
  525. intersection = (line_plane_intersection * box_rotation) + box_center;
  526. intersection_normal = LLVector3(0.0f, 0.0f, -1.0f) * box_rotation;
  527. return BOTTOM_SIDE;
  528. }
  529. }
  530. return NO_SIDE;
  531. }
  532. // -------------- point is INSIDE the box ----------------
  533. // front
  534. if (dirX > 0.0f)
  535. {
  536. // plane_normal                = [ 1, 0, 0]
  537. // plane_normal*line_point     = pointX
  538. // plane_normal*line_direction = dirX
  539. // D                           = -boxX
  540. // alpha                       = - (-boxX + pointX) / dirX
  541. line_plane_intersection = line_point - ((pointX - boxX) / dirX) * line_direction;
  542. if (line_plane_intersection.mV[VY] <  boxY &&
  543. line_plane_intersection.mV[VY] > -boxY &&
  544. line_plane_intersection.mV[VZ] <  boxZ &&
  545. line_plane_intersection.mV[VZ] > -boxZ )
  546. {
  547. intersection = (line_plane_intersection * box_rotation) + box_center;
  548. intersection_normal = LLVector3(1.0f, 0.0f, 0.0f) * box_rotation;
  549. return FRONT_SIDE;
  550. }
  551. }
  552. // back
  553. if (dirX < 0.0f)
  554. {
  555. // plane_normal                = [ -1, 0, 0]
  556. // plane_normal*line_point     = -pX 
  557. // plane_normal*line_direction = -direction.mV[VX]
  558. // D                           = -bX
  559. // alpha                       = - (-bX - pX) / (-dirX)
  560. line_plane_intersection = line_point - ((boxX + pointX)/ dirX) * line_direction;
  561. if (line_plane_intersection.mV[VY] <  boxY &&
  562. line_plane_intersection.mV[VY] > -boxY &&
  563. line_plane_intersection.mV[VZ] <  boxZ &&
  564. line_plane_intersection.mV[VZ] > -boxZ )
  565. {
  566. intersection = (line_plane_intersection * box_rotation) + box_center;
  567. intersection_normal = LLVector3(-1.0f, 0.0f, 0.0f) * box_rotation;
  568. return BACK_SIDE;
  569. }
  570. }
  571. // left
  572. if (dirY > 0.0f)
  573. {
  574. // plane_normal                = [0, 1, 0]
  575. // plane_normal*line_point     = pointY 
  576. // plane_normal*line_direction = dirY
  577. // D                           = -boxY
  578. // alpha                       = - (-boxY + pointY) / dirY
  579. line_plane_intersection = line_point + ((boxY - pointY)/dirY) * line_direction;
  580. if (line_plane_intersection.mV[VX] <  boxX &&
  581. line_plane_intersection.mV[VX] > -boxX &&
  582. line_plane_intersection.mV[VZ] <  boxZ &&
  583. line_plane_intersection.mV[VZ] > -boxZ )
  584. {
  585. intersection = (line_plane_intersection * box_rotation) + box_center;
  586. intersection_normal = LLVector3(0.0f, 1.0f, 0.0f) * box_rotation;
  587. return LEFT_SIDE;
  588. }
  589. }
  590. // right
  591. if (dirY < 0.0f)
  592. {
  593. // plane_normal                = [0, -1, 0]
  594. // plane_normal*line_point     = -pointY 
  595. // plane_normal*line_direction = -dirY
  596. // D                           = -boxY
  597. // alpha                       = - (-boxY - pointY) / (-dirY)
  598. line_plane_intersection = line_point - ((boxY + pointY)/dirY) * line_direction;
  599. if (line_plane_intersection.mV[VX] <  boxX &&
  600. line_plane_intersection.mV[VX] > -boxX &&
  601. line_plane_intersection.mV[VZ] <  boxZ &&
  602. line_plane_intersection.mV[VZ] > -boxZ )
  603. {
  604. intersection = (line_plane_intersection * box_rotation) + box_center;
  605. intersection_normal = LLVector3(0.0f, -1.0f, 0.0f) * box_rotation;
  606. return RIGHT_SIDE;
  607. }
  608. }
  609. // top
  610. if (dirZ > 0.0f)
  611. {
  612. // plane_normal                = [0, 0, 1]
  613. // plane_normal*line_point     = pointZ 
  614. // plane_normal*line_direction = dirZ
  615. // D                           = -boxZ
  616. // alpha                       = - (-boxZ + pointZ) / dirZ
  617. line_plane_intersection = line_point - ((pointZ - boxZ)/dirZ) * line_direction;
  618. if (line_plane_intersection.mV[VX] <  boxX &&
  619. line_plane_intersection.mV[VX] > -boxX &&
  620. line_plane_intersection.mV[VY] <  boxY &&
  621. line_plane_intersection.mV[VY] > -boxY )
  622. {
  623. intersection = (line_plane_intersection * box_rotation) + box_center;
  624. intersection_normal = LLVector3(0.0f, 0.0f, 1.0f) * box_rotation;
  625. return TOP_SIDE;
  626. }
  627. }
  628. // bottom
  629. if (dirZ < 0.0f)
  630. {
  631. // plane_normal                = [0, 0, -1]
  632. // plane_normal*line_point     = -pointZ 
  633. // plane_normal*line_direction = -dirZ
  634. // D                           = -boxZ
  635. // alpha                       = - (-boxZ - pointZ) / (-dirZ)
  636. line_plane_intersection = line_point - ((boxZ + pointZ)/dirZ) * line_direction;
  637. if (line_plane_intersection.mV[VX] <  boxX &&
  638. line_plane_intersection.mV[VX] > -boxX &&
  639. line_plane_intersection.mV[VY] <  boxY &&
  640. line_plane_intersection.mV[VY] > -boxY )
  641. {
  642. intersection = (line_plane_intersection * box_rotation) + box_center;
  643. intersection_normal = LLVector3(0.0f, 0.0f, -1.0f) * box_rotation;
  644. return BOTTOM_SIDE;
  645. }
  646. }
  647. // should never get here unless line instersects at tangent point on edge or corner
  648. // however such cases will be EXTREMELY rare
  649. return NO_SIDE;
  650. }
  651. BOOL ray_prism(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  652.    const LLVector3 &prism_center, const LLVector3 &prism_scale, const LLQuaternion &prism_rotation,
  653.    LLVector3 &intersection, LLVector3 &intersection_normal)
  654. {
  655. //      (0)              Z  
  656. //      /|              .  
  657. //    (1)|             /|  _.Y
  658. //     |               |   /|
  659. //     | |             |  /
  660. //     | | (0)         | / 
  661. //     | |             |/
  662. //     | |            (*)----> X  
  663. //     |(3)------(2)      
  664. //     |/        /        
  665. //    (4)-------(5)        
  666. // need to calculate the points of the prism so we can run ray tests with each face
  667. F32 x = prism_scale.mV[VX];
  668. F32 y = prism_scale.mV[VY];
  669. F32 z = prism_scale.mV[VZ];
  670. F32 tx = x * 2.0f / 3.0f;
  671. F32 ty = y * 0.5f;
  672. F32 tz = z * 2.0f / 3.0f;
  673. LLVector3 point0(tx-x,  ty, tz);
  674. LLVector3 point1(tx-x, -ty, tz);
  675. LLVector3 point2(tx,    ty, tz-z);
  676. LLVector3 point3(tx-x,  ty, tz-z);
  677. LLVector3 point4(tx-x, -ty, tz-z);
  678. LLVector3 point5(tx,   -ty, tz-z);
  679. // transform these points into absolute frame
  680. point0 = (point0 * prism_rotation) + prism_center;
  681. point1 = (point1 * prism_rotation) + prism_center;
  682. point2 = (point2 * prism_rotation) + prism_center;
  683. point3 = (point3 * prism_rotation) + prism_center;
  684. point4 = (point4 * prism_rotation) + prism_center;
  685. point5 = (point5 * prism_rotation) + prism_center;
  686. // test ray intersection for each face
  687. BOOL b_hit = FALSE;
  688. LLVector3 face_intersection, face_normal;
  689. F32 distance_squared = 0.0f;
  690. F32 temp;
  691. // face 0
  692. if (ray_direction * ( (point0 - point2) % (point5 - point2)) < 0.0f  && 
  693. ray_quadrangle(ray_point, ray_direction, point5, point2, point0, intersection, intersection_normal))
  694. {
  695. distance_squared = (ray_point - intersection).magVecSquared();
  696. b_hit = TRUE;
  697. }
  698. // face 1
  699. if (ray_direction * ( (point0 - point3) % (point2 - point3)) < 0.0f  &&
  700. ray_triangle(ray_point, ray_direction, point2, point3, point0, face_intersection, face_normal))
  701. {
  702. if (TRUE == b_hit)
  703. {
  704. temp = (ray_point - face_intersection).magVecSquared();
  705. if (temp < distance_squared)
  706. {
  707. distance_squared = temp;
  708. intersection = face_intersection;
  709. intersection_normal = face_normal;
  710. }
  711. }
  712. else 
  713. {
  714. distance_squared = (ray_point - face_intersection).magVecSquared();
  715. intersection = face_intersection;
  716. intersection_normal = face_normal;
  717. b_hit = TRUE;
  718. }
  719. }
  720. // face 2
  721. if (ray_direction * ( (point1 - point4) % (point3 - point4)) < 0.0f  &&
  722. ray_quadrangle(ray_point, ray_direction, point3, point4, point1, face_intersection, face_normal))
  723. {
  724. if (TRUE == b_hit)
  725. {
  726. temp = (ray_point - face_intersection).magVecSquared();
  727. if (temp < distance_squared)
  728. {
  729. distance_squared = temp;
  730. intersection = face_intersection;
  731. intersection_normal = face_normal;
  732. }
  733. }
  734. else 
  735. {
  736. distance_squared = (ray_point - face_intersection).magVecSquared();
  737. intersection = face_intersection;
  738. intersection_normal = face_normal;
  739. b_hit = TRUE;
  740. }
  741. }
  742. // face 3
  743. if (ray_direction * ( (point5 - point4) % (point1 - point4)) < 0.0f  &&
  744. ray_triangle(ray_point, ray_direction, point1, point4, point5, face_intersection, face_normal))
  745. {
  746. if (TRUE == b_hit)
  747. {
  748. temp = (ray_point - face_intersection).magVecSquared();
  749. if (temp < distance_squared)
  750. {
  751. distance_squared = temp;
  752. intersection = face_intersection;
  753. intersection_normal = face_normal;
  754. }
  755. }
  756. else 
  757. {
  758. distance_squared = (ray_point - face_intersection).magVecSquared();
  759. intersection = face_intersection;
  760. intersection_normal = face_normal;
  761. b_hit = TRUE;
  762. }
  763. }
  764. // face 4
  765. if (ray_direction * ( (point4 - point5) % (point2 - point5)) < 0.0f  &&
  766. ray_quadrangle(ray_point, ray_direction, point2, point5, point4, face_intersection, face_normal))
  767. {
  768. if (TRUE == b_hit)
  769. {
  770. temp = (ray_point - face_intersection).magVecSquared();
  771. if (temp < distance_squared)
  772. {
  773. distance_squared = temp;
  774. intersection = face_intersection;
  775. intersection_normal = face_normal;
  776. }
  777. }
  778. else 
  779. {
  780. distance_squared = (ray_point - face_intersection).magVecSquared();
  781. intersection = face_intersection;
  782. intersection_normal = face_normal;
  783. b_hit = TRUE;
  784. }
  785. }
  786. return b_hit;
  787. }
  788. BOOL ray_tetrahedron(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  789.  const LLVector3 &t_center, const LLVector3 &t_scale, const LLQuaternion &t_rotation,
  790.  LLVector3 &intersection, LLVector3 &intersection_normal)
  791. {
  792. F32 a = 0.5f * F_SQRT3; // height of unit triangle
  793. F32 b = 1.0f / F_SQRT3; // distance of center of unit triangle to each point
  794. F32 c = F_SQRT2 / F_SQRT3; // height of unit tetrahedron
  795. F32 d = 0.5f * F_SQRT3 / F_SQRT2; // distance of center of tetrahedron to each point
  796. // if we want the tetrahedron to have unit height (c = 1.0) then we need to divide
  797. // each constant by hieght of a unit tetrahedron
  798. F32 oo_c = 1.0f / c;
  799. a = a * oo_c;
  800. b = b * oo_c;
  801. c = 1.0f;
  802. d = d * oo_c;
  803. F32 e = 0.5f * oo_c;
  804. LLVector3 point0(    0.0f, 0.0f,  t_scale.mV[VZ] * d);
  805. LLVector3 point1(t_scale.mV[VX] * b, 0.0f,  t_scale.mV[VZ] * (d-c));
  806. LLVector3 point2(t_scale.mV[VX] * (b-a),  e * t_scale.mV[VY],  t_scale.mV[VZ] * (d-c));
  807. LLVector3 point3(t_scale.mV[VX] * (b-a), -e * t_scale.mV[VY],  t_scale.mV[VZ] * (d-c));
  808. // transform these points into absolute frame
  809. point0 = (point0 * t_rotation) + t_center;
  810. point1 = (point1 * t_rotation) + t_center;
  811. point2 = (point2 * t_rotation) + t_center;
  812. point3 = (point3 * t_rotation) + t_center;
  813. // test ray intersection for each face
  814. BOOL b_hit = FALSE;
  815. LLVector3 face_intersection, face_normal;
  816. F32 distance_squared = 1.0e12f;
  817. F32 temp;
  818. // face 0
  819. if (ray_direction * ( (point2 - point1) % (point0 - point1)) < 0.0f  && 
  820. ray_triangle(ray_point, ray_direction, point1, point2, point0, intersection, intersection_normal))
  821. {
  822. distance_squared = (ray_point - intersection).magVecSquared();
  823. b_hit = TRUE;
  824. }
  825. // face 1
  826. if (ray_direction * ( (point3 - point2) % (point0 - point2)) < 0.0f  &&
  827. ray_triangle(ray_point, ray_direction, point2, point3, point0, face_intersection, face_normal))
  828. {
  829. if (TRUE == b_hit)
  830. {
  831. temp = (ray_point - face_intersection).magVecSquared();
  832. if (temp < distance_squared)
  833. {
  834. distance_squared = temp;
  835. intersection = face_intersection;
  836. intersection_normal = face_normal;
  837. }
  838. }
  839. else 
  840. {
  841. distance_squared = (ray_point - face_intersection).magVecSquared();
  842. intersection = face_intersection;
  843. intersection_normal = face_normal;
  844. b_hit = TRUE;
  845. }
  846. }
  847. // face 2
  848. if (ray_direction * ( (point1 - point3) % (point0 - point3)) < 0.0f  &&
  849. ray_triangle(ray_point, ray_direction, point3, point1, point0, face_intersection, face_normal))
  850. {
  851. if (TRUE == b_hit)
  852. {
  853. temp = (ray_point - face_intersection).magVecSquared();
  854. if (temp < distance_squared)
  855. {
  856. distance_squared = temp;
  857. intersection = face_intersection;
  858. intersection_normal = face_normal;
  859. }
  860. }
  861. else 
  862. {
  863. distance_squared = (ray_point - face_intersection).magVecSquared();
  864. intersection = face_intersection;
  865. intersection_normal = face_normal;
  866. b_hit = TRUE;
  867. }
  868. }
  869. // face 3
  870. if (ray_direction * ( (point2 - point3) % (point1 - point3)) < 0.0f  &&
  871. ray_triangle(ray_point, ray_direction, point3, point2, point1, face_intersection, face_normal))
  872. {
  873. if (TRUE == b_hit)
  874. {
  875. temp = (ray_point - face_intersection).magVecSquared();
  876. if (temp < distance_squared)
  877. {
  878. intersection = face_intersection;
  879. intersection_normal = face_normal;
  880. }
  881. }
  882. else 
  883. {
  884. intersection = face_intersection;
  885. intersection_normal = face_normal;
  886. b_hit = TRUE;
  887. }
  888. }
  889. return b_hit;
  890. }
  891. BOOL ray_pyramid(const LLVector3 &ray_point, const LLVector3 &ray_direction,
  892.  const LLVector3 &p_center, const LLVector3 &p_scale, const LLQuaternion &p_rotation,
  893.  LLVector3 &intersection, LLVector3 &intersection_normal)
  894. {
  895. // center of mass of pyramid is located 1/4 its height from the base
  896. F32 x = 0.5f * p_scale.mV[VX];
  897. F32 y = 0.5f * p_scale.mV[VY];
  898. F32 z = 0.25f * p_scale.mV[VZ];
  899. LLVector3 point0(0.0f, 0.0f,  p_scale.mV[VZ] - z);
  900. LLVector3 point1( x,  y, -z);
  901. LLVector3 point2(-x,  y, -z);
  902. LLVector3 point3(-x, -y, -z);
  903. LLVector3 point4( x, -y, -z);
  904. // transform these points into absolute frame
  905. point0 = (point0 * p_rotation) + p_center;
  906. point1 = (point1 * p_rotation) + p_center;
  907. point2 = (point2 * p_rotation) + p_center;
  908. point3 = (point3 * p_rotation) + p_center;
  909. point4 = (point4 * p_rotation) + p_center;
  910. // test ray intersection for each face
  911. BOOL b_hit = FALSE;
  912. LLVector3 face_intersection, face_normal;
  913. F32 distance_squared = 1.0e12f;
  914. F32 temp;
  915. // face 0
  916. if (ray_direction * ( (point1 - point4) % (point0 - point4)) < 0.0f  && 
  917. ray_triangle(ray_point, ray_direction, point4, point1, point0, intersection, intersection_normal))
  918. {
  919. distance_squared = (ray_point - intersection).magVecSquared();
  920. b_hit = TRUE;
  921. }
  922. // face 1
  923. if (ray_direction * ( (point2 - point1) % (point0 - point1)) < 0.0f  &&
  924. ray_triangle(ray_point, ray_direction, point1, point2, point0, face_intersection, face_normal))
  925. {
  926. if (TRUE == b_hit)
  927. {
  928. temp = (ray_point - face_intersection).magVecSquared();
  929. if (temp < distance_squared)
  930. {
  931. distance_squared = temp;
  932. intersection = face_intersection;
  933. intersection_normal = face_normal;
  934. }
  935. }
  936. else 
  937. {
  938. distance_squared = (ray_point - face_intersection).magVecSquared();
  939. intersection = face_intersection;
  940. intersection_normal = face_normal;
  941. b_hit = TRUE;
  942. }
  943. }
  944. // face 2
  945. if (ray_direction * ( (point3 - point2) % (point0 - point2)) < 0.0f  &&
  946. ray_triangle(ray_point, ray_direction, point2, point3, point0, face_intersection, face_normal))
  947. {
  948. if (TRUE == b_hit)
  949. {
  950. temp = (ray_point - face_intersection).magVecSquared();
  951. if (temp < distance_squared)
  952. {
  953. distance_squared = temp;
  954. intersection = face_intersection;
  955. intersection_normal = face_normal;
  956. }
  957. }
  958. else 
  959. {
  960. distance_squared = (ray_point - face_intersection).magVecSquared();
  961. intersection = face_intersection;
  962. intersection_normal = face_normal;
  963. b_hit = TRUE;
  964. }
  965. }
  966. // face 3
  967. if (ray_direction * ( (point4 - point3) % (point0 - point3)) < 0.0f  &&
  968. ray_triangle(ray_point, ray_direction, point3, point4, point0, face_intersection, face_normal))
  969. {
  970. if (TRUE == b_hit)
  971. {
  972. temp = (ray_point - face_intersection).magVecSquared();
  973. if (temp < distance_squared)
  974. {
  975. distance_squared = temp;
  976. intersection = face_intersection;
  977. intersection_normal = face_normal;
  978. }
  979. }
  980. else 
  981. {
  982. distance_squared = (ray_point - face_intersection).magVecSquared();
  983. intersection = face_intersection;
  984. intersection_normal = face_normal;
  985. b_hit = TRUE;
  986. }
  987. }
  988. // face 4
  989. if (ray_direction * ( (point3 - point4) % (point2 - point4)) < 0.0f  &&
  990. ray_quadrangle(ray_point, ray_direction, point4, point3, point2, face_intersection, face_normal))
  991. {
  992. if (TRUE == b_hit)
  993. {
  994. temp = (ray_point - face_intersection).magVecSquared();
  995. if (temp < distance_squared)
  996. {
  997. intersection = face_intersection;
  998. intersection_normal = face_normal;
  999. }
  1000. }
  1001. else 
  1002. {
  1003. intersection = face_intersection;
  1004. intersection_normal = face_normal;
  1005. b_hit = TRUE;
  1006. }
  1007. }
  1008. return b_hit;
  1009. }
  1010. BOOL linesegment_circle(const LLVector3 &point_a, const LLVector3 &point_b,
  1011. const LLVector3 &circle_center, const LLVector3 plane_normal, F32 circle_radius,
  1012. LLVector3 &intersection)
  1013. {
  1014. LLVector3 ray_direction = point_b - point_a;
  1015. F32 segment_length = ray_direction.normVec();
  1016. if (ray_circle(point_a, ray_direction, circle_center, plane_normal, circle_radius, intersection))
  1017. {
  1018. if (segment_length >= (point_a - intersection).magVec())
  1019. {
  1020. return TRUE;
  1021. }
  1022. }
  1023. return FALSE;
  1024. }
  1025. BOOL linesegment_triangle(const LLVector3 &point_a, const LLVector3 &point_b,
  1026.   const LLVector3 &point_0, const LLVector3 &point_1, const LLVector3 &point_2,
  1027.   LLVector3 &intersection, LLVector3 &intersection_normal)
  1028. {
  1029. LLVector3 ray_direction = point_b - point_a;
  1030. F32 segment_length = ray_direction.normVec();
  1031. if (ray_triangle(point_a, ray_direction, point_0, point_1, point_2, intersection, intersection_normal))
  1032. {
  1033. if (segment_length >= (point_a - intersection).magVec())
  1034. {
  1035. return TRUE;
  1036. }
  1037. }
  1038. return FALSE;
  1039. }
  1040. BOOL linesegment_quadrangle(const LLVector3 &point_a, const LLVector3 &point_b,
  1041. const LLVector3 &point_0, const LLVector3 &point_1, const LLVector3 &point_2,
  1042. LLVector3 &intersection, LLVector3 &intersection_normal)
  1043. {
  1044. LLVector3 ray_direction = point_b - point_a;
  1045. F32 segment_length = ray_direction.normVec();
  1046. if (ray_quadrangle(point_a, ray_direction, point_0, point_1, point_2, intersection, intersection_normal))
  1047. {
  1048. if (segment_length >= (point_a - intersection).magVec())
  1049. {
  1050. return TRUE;
  1051. }
  1052. }
  1053. return FALSE;
  1054. }
  1055. BOOL linesegment_sphere(const LLVector3 &point_a, const LLVector3 &point_b,
  1056. const LLVector3 &sphere_center, F32 sphere_radius,
  1057. LLVector3 &intersection, LLVector3 &intersection_normal)
  1058. {
  1059. LLVector3 ray_direction = point_b - point_a;
  1060. F32 segment_length = ray_direction.normVec();
  1061. if (ray_sphere(point_a, ray_direction, sphere_center, sphere_radius, intersection, intersection_normal))
  1062. {
  1063. if (segment_length >= (point_a - intersection).magVec())
  1064. {
  1065. return TRUE;
  1066. }
  1067. }
  1068. return FALSE;
  1069. }
  1070. BOOL linesegment_cylinder(const LLVector3 &point_a, const LLVector3 &point_b,
  1071.   const LLVector3 &cyl_center, const LLVector3 &cyl_scale, const LLQuaternion &cyl_rotation,
  1072.   LLVector3 &intersection, LLVector3 &intersection_normal)
  1073. {
  1074. LLVector3 ray_direction = point_b - point_a;
  1075. F32 segment_length = ray_direction.normVec();
  1076. if (ray_cylinder(point_a, ray_direction, cyl_center, cyl_scale, cyl_rotation, intersection, intersection_normal))
  1077. {
  1078. if (segment_length >= (point_a - intersection).magVec())
  1079. {
  1080. return TRUE;
  1081. }
  1082. }
  1083. return FALSE;
  1084. }
  1085. U32 linesegment_box(const LLVector3 &point_a, const LLVector3 &point_b, 
  1086. const LLVector3 &box_center, const LLVector3 &box_scale, const LLQuaternion &box_rotation,
  1087. LLVector3 &intersection, LLVector3 &intersection_normal)
  1088. {
  1089. LLVector3 direction = point_b - point_a;
  1090. if (direction.isNull())
  1091. {
  1092. return NO_SIDE;
  1093. }
  1094. F32 segment_length = direction.normVec();
  1095. U32 box_side = ray_box(point_a, direction, box_center, box_scale, box_rotation, intersection, intersection_normal);
  1096. if (NO_SIDE == box_side  ||  segment_length < (intersection - point_a).magVec())
  1097. {
  1098. return NO_SIDE;
  1099. }
  1100. return box_side;
  1101. }
  1102. BOOL linesegment_prism(const LLVector3 &point_a, const LLVector3 &point_b,
  1103.    const LLVector3 &prism_center, const LLVector3 &prism_scale, const LLQuaternion &prism_rotation,
  1104.    LLVector3 &intersection, LLVector3 &intersection_normal)
  1105. {
  1106. LLVector3 ray_direction = point_b - point_a;
  1107. F32 segment_length = ray_direction.normVec();
  1108. if (ray_prism(point_a, ray_direction, prism_center, prism_scale, prism_rotation, intersection, intersection_normal))
  1109. {
  1110. if (segment_length >= (point_a - intersection).magVec())
  1111. {
  1112. return TRUE;
  1113. }
  1114. }
  1115. return FALSE;
  1116. }
  1117. BOOL linesegment_tetrahedron(const LLVector3 &point_a, const LLVector3 &point_b,
  1118.  const LLVector3 &t_center, const LLVector3 &t_scale, const LLQuaternion &t_rotation,
  1119.  LLVector3 &intersection, LLVector3 &intersection_normal)
  1120. {
  1121. LLVector3 ray_direction = point_b - point_a;
  1122. F32 segment_length = ray_direction.normVec();
  1123. if (ray_tetrahedron(point_a, ray_direction, t_center, t_scale, t_rotation, intersection, intersection_normal))
  1124. {
  1125. if (segment_length >= (point_a - intersection).magVec())
  1126. {
  1127. return TRUE;
  1128. }
  1129. }
  1130. return FALSE;
  1131. }
  1132. BOOL linesegment_pyramid(const LLVector3 &point_a, const LLVector3 &point_b,
  1133.  const LLVector3 &p_center, const LLVector3 &p_scale, const LLQuaternion &p_rotation,
  1134.  LLVector3 &intersection, LLVector3 &intersection_normal)
  1135. {
  1136. LLVector3 ray_direction = point_b - point_a;
  1137. F32 segment_length = ray_direction.normVec();
  1138. if (ray_pyramid(point_a, ray_direction, p_center, p_scale, p_rotation, intersection, intersection_normal))
  1139. {
  1140. if (segment_length >= (point_a - intersection).magVec())
  1141. {
  1142. return TRUE;
  1143. }
  1144. }
  1145. return FALSE;
  1146. }