prj/cam/src/sim/roomutil.cpp

   1 /*
   2 @Copyright Looking Glass Studios, Inc.
   3 1996,1997,1998,1999,2000 Unpublished Work.
   4 */
   5
   6 ///////////////////////////////////////////////////////////////////////////////
   7 // $Header: r:/t2repos/thief2/src/sim/roomutil.cpp,v 1.8 1998/09/10 21:31:45 CCAROLLO Exp $
   8 //
   9 // Room System utilities
  10 //
  11
  12 #include <lg.h>
  13
  14 #include <matrixs.h>
  15 #include <matrix.h>
  16 #include <math.h>
  17
  18 #include <wrtype.h>
  19
  20 #include <roombase.h>
  21 #include <roomutil.h>
  22
  23 // Must be last header
  24 #include <dbmem.h>
  25
  26
  27 ////////////////////////////////////////////////////////////////////////////////
  28 //
  29 // Returns signed distance from the plane to the point
  30 //
  31 mxs_real PointPlaneDist(const tPlane &plane, const mxs_vector &point)
  32 {
  33    return mx_dot_vec((mxs_vector *)&plane.normal, (mxs_vector *)&point) + plane.d;
  34 }
  35
  36 ////////////////////////////////////////
  37 //
  38 // Finds intersection point of ray and plane.  Returns FALSE if no
  39 //  intersection.
  40 //
  41 BOOL RayPlaneIntersection(const tPlane &plane, const mxs_vector &from, const mxs_vector &dir, mxs_vector *intersection)
  42 {
  43    mxs_vector to;
  44    mxs_real   dir_on_norm;
  45    mxs_real   from_dist;
  46    mxs_real   to_dist;
  47
  48    dir_on_norm = fabs(mx_dot_vec(&dir, &plane.normal));
  49
  50    if (dir_on_norm == 0)
  51       return FALSE;
  52
  53    mx_add_vec(&to, &from, &dir);
  54
  55    from_dist = PointPlaneDist(plane, from);
  56    to_dist = PointPlaneDist(plane, to);
  57
  58    if ((from_dist * to_dist) > 0)
  59    {
  60       if (fabs(from_dist) < fabs(to_dist))
  61          mx_scale_add_vec(intersection, &from, &dir, -fabs(from_dist) / dir_on_norm);
  62       else
  63          mx_scale_add_vec(intersection, &to, &dir, fabs(to_dist) / dir_on_norm);
  64    }
  65    else
  66       return LinePlaneIntersection(plane, from, to, intersection);
  67
  68    return TRUE;
  69 }
  70
  71 ////////////////////////////////////////
  72 //
  73 // Finds intersection of line segment and plane.  Returns FALSE if no
  74 //  intersection.
  75 //
  76 BOOL LinePlaneIntersection(const tPlane &plane, const mxs_vector &from, const mxs_vector &to, mxs_vector *intersection)
  77 {
  78    mxs_vector slope;
  79    mxs_real   from_dist, to_dist;
  80
  81    from_dist = PointPlaneDist(plane, from);
  82    to_dist   = PointPlaneDist(plane, to);
  83
  84    if (from_dist * to_dist > 0)
  85       return FALSE;
  86
  87    from_dist = fabs(from_dist);
  88    to_dist   = fabs(to_dist);
  89
  90    if ((from_dist + to_dist) < ON_PLANE_EPSILON)
  91    {
  92       mx_add_vec(intersection, &from, &to);
  93       mx_scaleeq_vec(intersection, 0.5);
  94       return TRUE;
  95    }
  96
  97    mx_sub_vec(&slope, &to, &from);
  98    mx_scale_add_vec(intersection, (mxs_vector *)&from, &slope, (from_dist) / (from_dist + to_dist));
  99
 100    return TRUE;
 101 }
 102
 103 ////////////////////////////////////////////////////////////////////////////////
 104 //
 105 // Calculates the list of planes that make up the OBB
 106 //
 107 void GetOBBPlanes(const tOBB &obb, tPlane plane_list[])
 108 {
 109    mxs_matrix M;
 110    mxs_vector pt_on_plane;
 111
 112
 113    mx_ang2mat(&M, (mxs_angvec *)&obb.pos.fac);
 114
 115    for (int i=0; i<6; i++)
 116    {
 117       // Calc normal
 118       mx_copy_vec(&plane_list[i].normal, &M.vec[i%3]);
 119       if (i >= 3)
 120          mx_scaleeq_vec(&plane_list[i].normal, -1);
 121
 122       // Calc plane constant (dot of normal and any point on plane)
 123       mx_scale_vec(&pt_on_plane, &plane_list[i].normal, obb.scale.el[i%3]);
 124       mx_addeq_vec(&pt_on_plane, (mxs_vector *)&obb.pos.loc.vec);
 125
 126       plane_list[i].d = -mx_dot_vec(&plane_list[i].normal, &pt_on_plane);
 127    }
 128 }
 129
 130 ////////////////////////////////////////
 131 //
 132 // Calculates the vertices that make up the OBB
 133 //
 134 const int x_sign_table[4] = { 1, -1, -1, 1 };
 135
 136 void GetOBBVertices(const tOBB &obb, mxs_vector vertex_list[])
 137 {
 138    mxs_matrix M;
 139    mxs_vector obb_vertex;
 140
 141
 142    mx_ang2mat(&M, (mxs_angvec *)&obb.pos.fac);
 143
 144    for (int i=0; i<8; i++)
 145    {
 146       int x_sign = x_sign_table[(i & 3)];
 147       int y_sign = (i & 2) ? -1 : 1;
 148       int z_sign = (i & 4) ? -1 : 1;
 149
 150       // Generate object-space vertex locations
 151       mx_mk_vec(&obb_vertex, obb.scale.x * x_sign,
 152                              obb.scale.y * y_sign,
 153                              obb.scale.z * z_sign);
 154
 155       // Rotate into world space
 156       mx_mat_mul_vec(&vertex_list[i], &M, &obb_vertex);
 157
 158       // Translate into world space
 159       mx_addeq_vec(&vertex_list[i], (mxs_vector *)&obb.pos.loc.vec);
 160    }
 161 }
 162
 163 ////////////////////////////////////////
 164 //
 165 // Returns bitfield representing which planes in the plane list it is
 166 //  "in front" of.
 167 //
 168 short GetBits(const mxs_vector &pt, const tPlane plane_list[])
 169 {
 170    short bits;
 171
 172
 173    bits = 0x0000;
 174    for (int i=0; i<6; i++)
 175    {
 176       if (PointPlaneDist(plane_list[i], pt) > ON_PLANE_EPSILON)
 177          bits |= (0x0001 << i);
 178    }
 179
 180    return bits;
 181 }
 182
 183 ////////////////////////////////////////////////////////////////////////////////
 184 //
 185 // Adds an point to the list, but only if it is unique.
 186 //
 187 void AddIntersectionPoint(const mxs_vector &int_pt, mxs_vector pt_list[], int *num_in_list)
 188 {
 189    int        i;
 190    mxs_vector delta;
 191
 192    for (i=0; i<*num_in_list; i++)
 193    {
 194       mx_sub_vec(&delta, (mxs_vector *)&int_pt, &pt_list[i]);
 195       if (mx_mag2_vec(&delta) < SAME_POINT_EPSILON_2)
 196          return;
 197    }
 198
 199    mx_copy_vec(&pt_list[*num_in_list], (mxs_vector *)&int_pt);
 200    (*num_in_list)++;
 201 }
 202
 203 ////////////////////////////////////////
 204 //
 205 // Calculates intersection points of edges between an OBBs vertices and
 206 //  another OBBs list of planes.
 207 //
 208 void BuildIntersections(const short bits[], const mxs_vector vertices[], const tPlane planes[], mxs_vector int_list[], int *num_ints)
 209 {
 210    mxs_vector  intersection;
 211    short       clip_planes;
 212    int         i, j;
 213
 214    // Check each edge's intersection
 215    for (i=0; i<12; i++)
 216    {
 217       // If they have common bits, then they both lie on the same side of
 218       //  a plane and can be ignored
 219       if (bits[OBBEdge[i].from] & bits[OBBEdge[i].to])
 220          continue;
 221
 222       // Find all the clipping planes
 223       clip_planes = (bits[OBBEdge[i].from] | bits[OBBEdge[i].to]);
 224
 225       // If both are inside (no clipping planes), ignore them
 226       if (clip_planes == 0x0000)
 227          continue;
 228
 229       // Find the intersection point
 230       for (j=0; j<6; j++)
 231       {
 232          if (clip_planes & (0x0001 << j))
 233          {
 234             LinePlaneIntersection(planes[j], vertices[OBBEdge[i].from],
 235                                   vertices[OBBEdge[i].to], &intersection);
 236
 237             if (GetBits(intersection, planes) == 0x0000)
 238                AddIntersectionPoint(intersection, int_list, num_ints);
 239          }
 240       }
 241    }
 242 }
 243
 244 ////////////////////////////////////////
 245 //
 246 // Culls a list of points (based on distance) down to four.
 247 //
 248 void CullIntPts(const mxs_vector &center, mxs_vector int_pts[], int *num_ints)
 249 {
 250    mxs_vector closest[4];
 251    mxs_real   closest_dist[4];
 252    mxs_real   dist;
 253    int        next_out;
 254    int        i, j;
 255
 256    AssertMsg1(*num_ints > 4, "Attempting to cull %d points", *num_ints);
 257
 258    // Init with the first four
 259    for (i=0; i<4; i++)
 260    {
 261       mx_copy_vec(&closest[i], &int_pts[i]);
 262       closest_dist[i] = mx_dist2_vec((mxs_vector *)&center, &int_pts[i]);
 263    }
 264
 265    // Find the largest of the first four
 266    next_out = 0;
 267    for (i=1; i<4; i++)
 268    {
 269       if (closest_dist[i] > closest_dist[next_out])
 270          next_out = i;
 271    }
 272
 273    // Check each remaining against the first four
 274    for (i=4; i<*num_ints; i++)
 275    {
 276       dist = mx_dist2_vec((mxs_vector *)&center, &int_pts[i]);
 277       if (dist < closest_dist[next_out])
 278       {
 279          mx_copy_vec(&closest[next_out], &int_pts[i]);
 280          closest_dist[next_out] = dist;
 281          for (j=0; j<4; j++)
 282          {
 283             if (closest_dist[j] > closest_dist[next_out])
 284                next_out = j;
 285          }
 286       }
 287    }
 288
 289    // And copy closest 4 back into array
 290    for (i=0; i<4; i++)
 291       mx_copy_vec(&int_pts[i], &closest[i]);
 292
 293    *num_ints = 4;
 294 }
 295
 296 ////////////////////////////////////////////////////////////////////////////////
 297 //
 298 // Calculates the plane that a list of point lie in.  Returns FALSE if the
 299 //  points are not coplanar.
 300 //
 301 BOOL PlaneFromPoints(const mxs_vector points[], int numPoints, tPlane *newPlane)
 302 {
 303    mxs_vector v1, v2;
 304
 305    AssertMsg1(numPoints > 2, "Attempt to create plane from %d points", numPoints);
 306
 307    // Calc normal
 308    mx_sub_vec(&v1, (mxs_vector *)&points[1], (mxs_vector *)&points[0]);
 309    mx_sub_vec(&v2, (mxs_vector *)&points[2], (mxs_vector *)&points[0]);
 310
 311    mx_cross_vec(&newPlane->normal, &v1, &v2);
 312    mx_normeq_vec(&newPlane->normal);
 313
 314    // And plane constant
 315    newPlane->d = -mx_dot_vec(&newPlane->normal, (mxs_vector *)&points[0]);
 316
 317    // Now check any further points for coplanarity
 318    for (int i=3; i<numPoints; i++)
 319    {
 320       if (fabs(PointPlaneDist(*newPlane, points[i])) > ON_PLANE_EPSILON)
 321          return FALSE;
 322    }
 323
 324    return TRUE;
 325 }
 326
 327 ////////////////////////////////////////
 328 //
 329 // Calculates the outward-facing planes of a portal based on its plane and
 330 //  its (non-wound) vertex list.
 331 //
 332 void PortalEdgePlanes(const mxs_vector points[], int numPoints, const tPlane &portalPlane, tPlane portalEdges[])
 333 {
 334    mxs_vector  edge;
 335    int         num_edges;
 336    BOOL        first_test;
 337    BOOL        bad_edge;
 338    int  i, j, k;
 339
 340    // Make an edge plane from each point, pairwise
 341    num_edges = 0;
 342    for (i=0; i<numPoints; i++)
 343    {
 344       for (j=0; j<i; j++)
 345       {
 346         // Make the normal
 347         mx_sub_vec(&edge, (mxs_vector *)&points[i], (mxs_vector *)&points[j]);
 348         mx_cross_vec(&portalEdges[num_edges].normal, &edge, (mxs_vector *)&portalPlane.normal);
 349         mx_normeq_vec(&portalEdges[num_edges].normal);
 350
 351         // And the plane constant
 352         portalEdges[num_edges].d = -mx_dot_vec(&portalEdges[num_edges].normal, (mxs_vector *)&points[i]);
 353
 354         // Check that all remaining points are behind the new plane.  You are
 355         //  allowed to flip the plane for the first point tested (in case you
 356         //  guessed the normal incorrectly), but not after that because that
 357         //  means the plane is interior to the portal.
 358         first_test = TRUE;
 359         bad_edge = FALSE;
 360
 361         for (k=0; k<numPoints && !bad_edge; k++)
 362         {
 363            if ((k == i) || (k == j))
 364               continue;
 365
 366            if (PointPlaneDist(portalEdges[num_edges], points[k]) > ON_PLANE_EPSILON)
 367            {
 368               if (first_test)
 369               {
 370                  mx_scaleeq_vec(&portalEdges[num_edges].normal, -1.0);
 371                  portalEdges[num_edges].d *= -1.0;
 372               }
 373               else
 374                  bad_edge = TRUE;
 375            }
 376            first_test = FALSE;
 377         }
 378
 379         // If it's a valid edge, increment the number of edges so we keep it
 380         if (!bad_edge)
 381            num_edges++;
 382       }
 383    }
 384
 385    AssertMsg2(num_edges == numPoints, "Different number of portal edges (%d) than points (%d)", num_edges, numPoints);
 386 }
 387
 388 ////////////////////////////////////////
 389 //
 390 // Calculates the center point of a portal from its vertex list.
 391 //
 392 void PortalCenter(const mxs_vector portalPoints[], int numPortalPoints, mxs_vector *portalCenter)
 393 {
 394    AssertMsg(numPortalPoints != 0, "Attempt to find center of 0 points");
 395
 396    mx_zero_vec(portalCenter);
 397    for (int i=0; i<numPortalPoints; i++)
 398       mx_addeq_vec(portalCenter, (mxs_vector *)&portalPoints[i]);
 399    mx_scaleeq_vec(portalCenter, 1.0 / numPortalPoints);
 400 }
 401
 402 ////////////////////////////////////////////////////////////////////////////////
 403 //
 404 // Determines whether two OBBs intersect.  From "Fast Overlap Test for
 405 //  OBBs", by ???.  I got the paper excerpt from Doug.
 406 //
 407
 408 // First index removes an index, second index returns the other index
 409 const int index_lookup[3][3] =
 410 { { -1,  2,  1},
 411   {  2, -1,  0},
 412   {  1,  0, -1} };
 413
 414 BOOL OBBsIntersect(const tOBB &b1, const tOBB &b2)
 415 {
 416    mxs_vector T;           // Translation vector between brushes
 417    mxs_vector L;           // Sparating Axis
 418    mxs_real T_L;           // Length of projection of T onto L
 419    mxs_matrix M, M_abs;    // Rotation matrix between brushes, and
 420                            //  absolute value version
 421    mxs_matrix M_1, M_2;    // Rotation matrices for each brush
 422    mxs_real   sum;         // Accumulation of summation elements
 423    int i, j, k;
 424
 425    // Calculate T vector
 426    mx_sub_vec(&T, (mxs_vector *)&b2.pos.loc.vec, (mxs_vector *)&b1.pos.loc.vec);
 427
 428    // Calculate orientation matrices for each obb
 429    mx_ang2mat(&M_1, (mxs_angvec *)&(b1.pos.fac));
 430    mx_ang2mat(&M_2, (mxs_angvec *)&(b2.pos.fac));
 431
 432    // Transform to obb1-relative rotation
 433    mx_mul_mat(&M, &M_1, &M_2);
 434
 435    // Calculate absolute valued M matrix
 436    for (i=0; i<9; ++i)
 437       M_abs.el[i] = (M.el[i] > 0) ? M.el[i] : -M.el[i];
 438
 439    // Use first brush's normals for separating axis generation
 440    for (i=0; i<3; ++i)
 441    {
 442       // Calculate distance between projected centers
 443       T_L = fabs(mx_dot_vec(&T, &(M_1.vec[i])));
 444
 445       // Calculate length of maximum radius of brush, projected
 446       sum = b1.scale.el[i];
 447       for (j=0; j<3; ++j)
 448          sum += b2.scale.el[j] * fabs(mx_dot_vec(&M_2.vec[j], &M_1.vec[i]));
 449
 450       if (sum < T_L)
 451          return FALSE;
 452    }
 453
 454    // Use second brush's normals for separating axis generation
 455    for (i=0; i<3; ++i)
 456    {
 457       // Calculate distance between projected centers
 458       T_L = fabs(mx_dot_vec(&T, &(M_2.vec[i])));
 459
 460       // Calculate length of maximum radius of brush, projected
 461       sum = b2.scale.el[i];
 462       for (j=0; j<3; ++j)
 463          sum += b1.scale.el[j] * fabs(mx_dot_vec(&M_1.vec[j], &M_2.vec[i]));
 464
 465       if (sum < T_L)
 466          return FALSE;
 467    }
 468
 469    // Use edge-pairs for separating axis generation
 470    for (i=0; i<3; ++i)
 471    {
 472       for (j=0; j<3; ++j)
 473       {
 474          mx_cross_vec(&L, &(M_1.vec[i]), &(M_2.vec[j]));
 475          if (mx_mag2_vec(&L) > 0.0001)
 476             mx_normeq_vec(&L);
 477          T_L = fabs(mx_dot_vec(&T, &L));
 478
 479          // Do summations
 480          sum = 0;
 481
 482          for (k=0; k<3; k++)
 483             sum += b1.scale.el[k] * fabs(mx_dot_vec(&M_1.vec[k], &L));
 484
 485          for (k=0; k<3; k++)
 486             sum += b2.scale.el[k] * fabs(mx_dot_vec(&M_2.vec[k], &L));
 487
 488          // If radius is smaller than the distance from center to center,
 489          //  then they must not intersect
 490          if (sum < T_L)
 491             return FALSE;
 492       }
 493    }
 494
 495    // All separating axis tests fell through, must intersect
 496    return TRUE;
 497 }
 498
 499 ////////////////////////////////////////
 500 //
 501 // Determine if a point in inside an obb
 502 //
 503 BOOL PointInOBB(const tOBB &obb, const mxs_vector &pt)
 504 {
 505    static tPlane planes[6];
 506
 507    GetOBBPlanes(obb, planes);
 508    return (GetBits(pt, planes) == 0x0000);
 509 }
 510
 511
 512 ////////////////////////////////////////
 513 //
 514 // Given two OBBS, determines if they intersect and calculates the portal's
 515 //  plane, the planes of the portal's edges, and the center point of the
 516 //  portal.
 517 //
 518 void FindOBBPortal(const tOBB &b1, const tOBB &b2, tPlane *portalPlane, tPlane portalEdges[], int *portalEdgeSize, mxs_vector *center)
 519 {
 520    mxs_vector  b1_int_pt[24];
 521    mxs_vector  b2_int_pt[24];
 522    int         b1_num_int_pts;
 523    int         b2_num_int_pts;
 524
 525    tPlane      b1_planes[6];
 526    tPlane      b2_planes[6];
 527    mxs_vector  b1_vertices[8];
 528    mxs_vector  b2_vertices[8];
 529    short       b1_bits[8];
 530    short       b2_bits[8];
 531
 532    int         i;
 533
 534
 535    b1_num_int_pts = 0;
 536    b2_num_int_pts = 0;
 537
 538    // Find the planes of the OBBs
 539    GetOBBPlanes(b1, b1_planes);
 540    GetOBBPlanes(b2, b2_planes);
 541
 542    // Find the vertices of the OBBs
 543    GetOBBVertices(b1, b1_vertices);
 544    GetOBBVertices(b2, b2_vertices);
 545
 546    // Find relative octants of each point
 547    for (i=0; i<8; i++)
 548    {
 549       b1_bits[i] = GetBits(b1_vertices[i], b2_planes);
 550       b2_bits[i] = GetBits(b2_vertices[i], b1_planes);
 551    }
 552
 553    // Find the edge intersections
 554    BuildIntersections(b1_bits, b1_vertices, b2_planes, b1_int_pt, &b1_num_int_pts);
 555    BuildIntersections(b2_bits, b2_vertices, b1_planes, b2_int_pt, &b2_num_int_pts);
 556
 557    if (b1_num_int_pts > 4)
 558       CullIntPts(b1.pos.loc.vec, b1_int_pt, &b1_num_int_pts);
 559    if (b2_num_int_pts > 4)
 560       CullIntPts(b2.pos.loc.vec, b2_int_pt, &b2_num_int_pts);
 561
 562    // @TODO: Remove this when room brushes actually exist
 563    if ((b1_num_int_pts == 0) && (b2_num_int_pts == 0))
 564    {
 565       *portalEdgeSize = 0;
 566       return;
 567    }
 568
 569    // Try using b1 if it has 4 points
 570    if (b1_num_int_pts == 4)
 571    {
 572       if (PlaneFromPoints(b1_int_pt, b1_num_int_pts, portalPlane))
 573       {
 574          PortalEdgePlanes(b1_int_pt, b1_num_int_pts, *portalPlane, portalEdges);
 575          PortalCenter(b1_int_pt, b1_num_int_pts, center);
 576          *portalEdgeSize = b1_num_int_pts;
 577          return;
 578       }
 579    }
 580
 581    // Try using b2 if it has 4 points
 582    if (b2_num_int_pts == 4)
 583    {
 584       if (PlaneFromPoints(b2_int_pt, b2_num_int_pts, portalPlane))
 585       {
 586          PortalEdgePlanes(b2_int_pt, b2_num_int_pts, *portalPlane, portalEdges);
 587          PortalCenter(b2_int_pt, b2_num_int_pts, center);
 588          *portalEdgeSize = b2_num_int_pts;
 589          return;
 590       }
 591    }
 592
 593    if (b1_num_int_pts == 3)
 594    {
 595       PlaneFromPoints(b1_int_pt, b1_num_int_pts, portalPlane);
 596       PortalEdgePlanes(b1_int_pt, b1_num_int_pts, *portalPlane, portalEdges);
 597       PortalCenter(b1_int_pt, b1_num_int_pts, center);
 598       *portalEdgeSize = b1_num_int_pts;
 599       return;
 600    }
 601
 602    if (b2_num_int_pts == 3)
 603    {
 604       PlaneFromPoints(b2_int_pt, b2_num_int_pts, portalPlane);
 605       PortalEdgePlanes(b2_int_pt, b2_num_int_pts, *portalPlane, portalEdges);
 606       PortalCenter(b2_int_pt, b2_num_int_pts, center);
 607       *portalEdgeSize = b2_num_int_pts;
 608       return;
 609    }
 610
 611    *portalEdgeSize = 0;
 612 }
 613
 614
 615
 616
 617
 618