prj/cam/src/sim/wrbsp.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/wrbsp.cpp,v 1.11 2000/02/19 13:27:49 toml Exp $
   8 //
   9 // Run-time worldrep bsp tree
  10 //
  11
  12 #include <lg.h>
  13 #include <math.h>
  14 #include <allocapi.h>
  15 #include <hashpp.h>
  16 #include <hshpptem.h>
  17 #include <dynarray.h>
  18 #include <wr.h>
  19 #include <portal.h>
  20
  21 #include <media.h>
  22 #include <bspdata.h>
  23 #include <wrbsp.h>
  24
  25 #include <mprintf.h>
  26 #include <memall.h>
  27 #include <dbmem.h>   // must be last header!
  28
  29 ////////////////////////////////////////////////////////////////////////////////
  30
  31 cDynArray<wrBspNode> wrBspTree;
  32
  33 wrBspNode *g_wrBspTree = NULL;
  34 int g_wrBspTreeSize = 0;
  35
  36 struct sPostSplit
  37 {
  38    int cell_id;
  39    BspNode *n;
  40 };
  41
  42 cDynArray<sPostSplit> gPostSplitList;
  43
  44 ////////////////////////////////////////////////////////////////////////////////
  45
  46 cDynArray<PortalPlane *> gExtraPlaneList;
  47
  48 void ClearExtraPlanes()
  49 {
  50    for (int i=0; i<gExtraPlaneList.Size(); i++)
  51    {
  52       if (gExtraPlaneList[i] != NULL)
  53       {
  54          delete gExtraPlaneList[i];
  55          gExtraPlaneList[i] = NULL;
  56       }
  57    }
  58    gExtraPlaneList.SetSize(0);
  59 }
  60
  61 PortalPlane *AddExtraPlane(mxs_vector plane_norm, mxs_real plane_const)
  62 {
  63    PortalPlane *pNewPlane = new PortalPlane;
  64
  65    pNewPlane->normal = plane_norm;
  66    pNewPlane->plane_constant = plane_const;
  67
  68    LGALLOC_PUSH_CREDIT();
  69    gExtraPlaneList.Append(pNewPlane);
  70    LGALLOC_POP_CREDIT();
  71
  72    return pNewPlane;
  73 }
  74
  75 ////////////////////////////////////////////////////////////////////////////////
  76
  77 PortalPlane *FindPlaneInCell(mxs_vector *plane_norm, mxs_real plane_const, int cell_id)
  78 {
  79    PortalCell *pCell = WR_CELL(cell_id);
  80    Assert_(pCell);
  81
  82    mxs_vector norm_delta;
  83
  84    for (int i=0; i<pCell->num_planes; i++)
  85    {
  86       if (fabs(plane_const - pCell->plane_list[i].plane_constant) < 0.00001)
  87       {
  88          mx_sub_vec(&norm_delta, &pCell->plane_list[i].normal, plane_norm);
  89
  90          if (mx_mag2_vec(&norm_delta) < 0.00001)
  91             return &pCell->plane_list[i];
  92       }
  93    }
  94
  95    return NULL;
  96 }
  97
  98 BOOL FindPortalPlaneRec(mxs_vector *plane_norm, mxs_real plane_const, BspNode *n, PortalPlane **pPlane, BOOL *reversed)
  99 {
 100    if (n->leaf)
 101    {
 102       if (n->cell_id > 0)
 103       {
 104
 105          if ((*pPlane = FindPlaneInCell(plane_norm, plane_const, n->cell_id - 1)) != NULL)
 106          {
 107             *reversed = FALSE;
 108             return TRUE;
 109          }
 110
 111          mxs_vector pnorm;
 112          mxs_real pconst;
 113
 114          mx_scale_vec(&pnorm, plane_norm, -1.0);
 115          pconst = plane_const * -1.0;
 116
 117          if ((*pPlane = FindPlaneInCell(&pnorm, pconst, n->cell_id - 1)) != NULL)
 118          {
 119             *reversed = TRUE;
 120             return TRUE;
 121          }
 122
 123          return FALSE;
 124       }
 125       else
 126          return FALSE;
 127    }
 128    else
 129    {
 130       if (FindPortalPlaneRec(plane_norm, plane_const, n->inside, pPlane, reversed))
 131          return TRUE;
 132
 133       return FindPortalPlaneRec(plane_norm, plane_const, n->outside, pPlane, reversed);
 134    }
 135 }
 136
 137 BOOL FindPortalPlane(BspNode *n, PortalPlane **pPlane, int *reversed)
 138 {
 139    BOOL found = FALSE;
 140
 141    mxs_vector plane_norm;
 142    mxs_vector rev_plane_norm;
 143    mxs_real   plane_const =  n->split_plane.d;
 144    mxs_real   rev_plane_const = -n->split_plane.d;
 145
 146    mx_mk_vec(&plane_norm, n->split_plane.a, n->split_plane.b, n->split_plane.c);
 147    mx_mk_vec(&rev_plane_norm, -n->split_plane.a, -n->split_plane.b, -n->split_plane.c);
 148
 149    if (!FindPortalPlaneRec(&plane_norm, plane_const, n, pPlane, reversed))
 150    {
 151       for (int i=0; i<wr_num_cells; i++)
 152       {
 153          if ((*pPlane = FindPlaneInCell(&plane_norm, plane_const, i)) != NULL)
 154          {
 155             *reversed = FALSE;
 156             found = TRUE;
 157             break;
 158          }
 159
 160          if ((*pPlane = FindPlaneInCell(&rev_plane_norm, rev_plane_const, i)) != NULL)
 161          {
 162             *reversed = TRUE;
 163             found = TRUE;
 164             break;
 165          }
 166       }
 167    }
 168    else
 169       found = TRUE;
 170
 171    // Add to our own plane list, if it wasn't found in the world
 172    if (!found)
 173    {
 174       *pPlane = AddExtraPlane(plane_norm, plane_const);
 175       *reversed = FALSE;
 176
 177       found = TRUE;
 178    }
 179
 180    return found;
 181 }
 182
 183 ////////////////////////////////////////////////////////////////////////////////
 184
 185 //
 186 // Allocate a new leaf and initialize it
 187 //
 188 uint wrBspLeafCreate(uint parent_index, int cell_id)
 189 {
 190    wrBspNode new_node;
 191
 192    new_node.flags = 0;
 193
 194    wrBspSetLeaf(&new_node);
 195    wrBspUnmark(&new_node);
 196    wrBspSetNormal(&new_node);
 197
 198    wrSetParent(&new_node, parent_index);
 199    new_node.plane = NULL;
 200
 201    new_node.cell_id = cell_id;
 202
 203    LGALLOC_AUTO_CREDIT();
 204    return wrBspTree.Append(new_node);
 205 }
 206
 207 //
 208 // Allocate a new node and initialize it
 209 //
 210 uint wrBspNodeCreate(BspNode *n, int cell_id, uint parent_index)
 211 {
 212    wrBspNode new_node;
 213
 214    new_node.flags = 0;
 215
 216    wrBspSetNode(&new_node);
 217    wrBspUnmark(&new_node);
 218
 219    wrSetParent(&new_node, parent_index);
 220
 221    BOOL reversed;
 222    FindPortalPlane(n, &new_node.plane, &reversed);
 223
 224    AssertMsg(new_node.plane, "Unable to find matching splitplane!\n");
 225
 226    if (reversed)
 227       wrBspSetReversed(&new_node);
 228    else
 229       wrBspSetNormal(&new_node);
 230
 231    LGALLOC_AUTO_CREDIT();
 232    return wrBspTree.Append(new_node);
 233 }
 234
 235 //
 236 // Search the tree for a leaf with the specified cell_id
 237 // and return a pointer to the leaf
 238 //
 239 uint wrBspFindLeaf(int cell_id)
 240 {
 241    for (int i=0; i<wrBspTree.Size(); i++)
 242    {
 243       if (wrBspIsLeaf(&wrBspTree[i]) && (wrBspTree[i].cell_id == cell_id))
 244          return i;
 245    }
 246
 247    return WRBSP_INVALID;
 248 }
 249
 250 //
 251 // Point each cell at its leaf in the worldrep BSP
 252 //
 253 void wrBspTreeRefCells(uint node_index)
 254 {
 255    if (node_index == WRBSP_INVALID)
 256       return;
 257
 258    if (wrBspTree.Size() == 0)
 259       return;
 260
 261    wrBspNode *pCurNode = &wrBspTree[node_index];
 262
 263    if (wrBspIsLeaf(pCurNode))
 264    {
 265       if (pCurNode->cell_id != -1)
 266          WR_CELL(pCurNode->cell_id)->leaf_index = node_index;
 267    }
 268    else
 269    {
 270       wrBspTreeRefCells(pCurNode->inside_index);
 271       wrBspTreeRefCells(pCurNode->outside_index);
 272    }
 273 }
 274
 275 //
 276 // Recursively copies the CSG's BSP tree.  At each recursion it
 277 // allocates the appropriate structure and copies it.  Returned
 278 // from each level of recursion is a pointer to the element
 279 // created from the returning level of recursion.  Note that a
 280 // pointer from the current level of recursion is passed to the
 281 // next level of recursion so that children can have links to
 282 // their parents.
 283 //
 284 // When first calling, parent should be passed in as NULL.
 285 //
 286 // Also note that when this copy is taking place the cells
 287 // have not yet been numbered or emitted.  I am assuming that
 288 // they will be numbered according to the existing CSG BSP
 289 // tree (inorder traversal). Additional splits due to high-
 290 // poly-count-cells will go to dummy nodes, whose numbers
 291 // come *after* the original CSG BSP's cell's numbers.
 292 //
 293 // Of course, for this BSP tree, there will be no dummy
 294 // nodes -- splits will actually create nodes in the tree.
 295 // But that's handled later.
 296 //
 297 uint wrBspTreeCopy(BspNode *node, uint parent_id)
 298 {
 299    uint new_node_index;
 300
 301    // If it's the first recursion, initialize the BSP tree
 302    if (parent_id == WRBSP_INVALID)
 303    {
 304       wrBspTree.SetSize(0);
 305       g_wrBspTree = NULL;
 306       g_wrBspTreeSize = 0;
 307
 308       ClearExtraPlanes();
 309    }
 310
 311    if (node->ph)
 312    {
 313       // Create leaf, but only assign a cell number if it's
 314       // a non-solid (marked) leaf
 315       if (IS_MARKED(node))
 316          new_node_index = wrBspLeafCreate(parent_id, node->cell_id - 1);
 317       else
 318          new_node_index = WRBSP_INVALID;
 319    }
 320    else
 321    {
 322       uint ret_index; // to enforce order of evaulation of assignment
 323
 324       new_node_index = wrBspNodeCreate(node, node->cell_id, parent_id);
 325
 326       AssertMsg(new_node_index != WRBSP_INVALID, "Invalid cration node index");
 327
 328       ret_index = wrBspTreeCopy(node->inside, new_node_index);
 329       wrBspTree[new_node_index].inside_index = ret_index;
 330
 331       ret_index = wrBspTreeCopy(node->outside, new_node_index);
 332       wrBspTree[new_node_index].outside_index = ret_index;
 333    }
 334
 335    if (parent_id == WRBSP_INVALID)
 336    {
 337       wrBspTreeApplyPostSplits();
 338
 339       if (wrBspTree.Size() > 0)
 340          g_wrBspTree = &wrBspTree[0];
 341       else
 342          g_wrBspTree = NULL;
 343
 344       g_wrBspTreeSize = wrBspTree.Size();
 345
 346       mprintf("  %d extra bsp planes created\n", gExtraPlaneList.Size());
 347    }
 348
 349    return new_node_index;
 350 }
 351
 352 //
 353 // Deallocates a worldrep BSP tree
 354 //
 355 void wrBspTreeDeallocate()
 356 {
 357    wrBspTree.SetSize(0);
 358    g_wrBspTree = NULL;
 359    g_wrBspTreeSize = 0;
 360    ClearExtraPlanes();
 361 }
 362
 363 //
 364 // Dumps the tree ever-so-ineligantly to the mono
 365 //
 366 void wrBspTreeDumpRec(uint node_index)
 367 {
 368    if (node_index == WRBSP_INVALID)
 369       return;
 370
 371    wrBspNode *pCurNode = &wrBspTree[node_index];
 372
 373    if (wrBspIsLeaf(pCurNode))
 374    {
 375       mprintf("  LEAF  (%d)  %c\n", node_index, wrBspIsMarked(pCurNode) ? '*' : ' ');
 376       mprintf("    parent_id = %d\n", wrParentIndex(pCurNode));
 377       mprintf("    cell_id = %d\n", pCurNode->cell_id);
 378    }
 379    else
 380    {
 381       mprintf("  NODE  (%d)  %s\n", node_index, wrBspIsReversed(pCurNode) ? "rev" : "   ");
 382       mprintf("    %gx + %gy + %gz + %g\n", pCurNode->plane->normal.x,
 383                                             pCurNode->plane->normal.y,
 384                                             pCurNode->plane->normal.z,
 385                                             pCurNode->plane->plane_constant);
 386       wrBspTreeDumpRec(pCurNode->inside_index);
 387       wrBspTreeDumpRec(pCurNode->outside_index);
 388    }
 389 }
 390
 391 void wrBspTreeDump()
 392 {
 393    wrBspTreeDumpRec(WRBSP_HEAD);
 394 }
 395
 396
 397 ////////////////////////////////////////////////////////////////////////////////
 398
 399 void wrBspTreeAddPostSplit(BspNode *n, int cell_id)
 400 {
 401    sPostSplit postSplit;
 402
 403    postSplit.cell_id = cell_id;
 404    postSplit.n = n;
 405
 406    LGALLOC_AUTO_CREDIT();
 407    gPostSplitList.Append(postSplit);
 408 }
 409
 410 void wrBspTreeApplyPostSplits()
 411 {
 412    for (int i=0; i<gPostSplitList.Size(); i++)
 413    {
 414       uint split_index = wrBspFindLeaf(gPostSplitList[i].cell_id);
 415
 416       AssertMsg1(split_index != WRBSP_INVALID, "Unable to find cell %d to split!\n", gPostSplitList[i].cell_id);
 417
 418       wrBspNode *pSplitLeaf = &wrBspTree[split_index];
 419
 420       BOOL reversed;
 421       FindPortalPlane(gPostSplitList[i].n, &pSplitLeaf->plane, &reversed);
 422
 423       if (reversed)
 424          wrBspSetReversed(pSplitLeaf);
 425       else
 426          wrBspSetNormal(pSplitLeaf);
 427
 428       // Convert to a node
 429       wrBspSetNode(pSplitLeaf);
 430       wrBspUnmark(pSplitLeaf);
 431
 432       uint ret_index;
 433
 434       ret_index = wrBspLeafCreate(split_index, gPostSplitList[i].cell_id);
 435       wrBspTree[split_index].inside_index = ret_index;
 436
 437       ret_index = wrBspLeafCreate(split_index, gPostSplitList[i].n->cell_id - 1);
 438       wrBspTree[split_index].outside_index = ret_index;
 439    }
 440
 441    gPostSplitList.SetSize(0);
 442 }
 443
 444
 445 ////////////////////////////////////////////////////////////////////////////////
 446
 447 typedef struct
 448 {
 449    int cell_id;
 450    int plane_id;
 451 } sCellPlane;
 452
 453 typedef cHashTableFunctions<long> LongHashFunctions;
 454 typedef cHashTable<long, sCellPlane, LongHashFunctions> cCellPlaneTable;
 455
 456 cCellPlaneTable gCellPlaneTable;
 457
 458 #ifdef _MSC_VER
 459 template cCellPlaneTable;
 460 #endif
 461
 462 void wrBspTreeWrite(PortalReadWrite write)
 463 {
 464    int i, j;
 465    sCellPlane cellplane;
 466
 467    gCellPlaneTable.Clear();
 468
 469    // First build a table of plane pointers to cell-plane ids
 470    for (i=0; i<wr_num_cells; i++)
 471    {
 472       PortalCell *pCell = WR_CELL(i);
 473       Assert_(pCell);
 474
 475       for (j=0; j<pCell->num_planes; j++)
 476       {
 477          cellplane.cell_id = i;
 478          cellplane.plane_id = j;
 479
 480          gCellPlaneTable.Set((long)(&pCell->plane_list[j]), cellplane);
 481       }
 482    }
 483
 484    // Write out our extra planes
 485    int size = gExtraPlaneList.Size();
 486
 487    write(&size, sizeof(int), 1);
 488    for (i=0; i<size; i++)
 489    {
 490       PortalPlane* plane = gExtraPlaneList[i];
 491       // You kids are so cute, writing out each field like this
 492       write(&plane->normal,sizeof(plane->normal),1);
 493       write(&plane->plane_constant,sizeof(plane->plane_constant),1);
 494    }
 495
 496    // Then write out our array, replacing plane pointers will cellplanes
 497    write(&g_wrBspTreeSize, sizeof(int), 1);
 498
 499    for (i=0; i<g_wrBspTreeSize; i++)
 500    {
 501       write(&g_wrBspTree[i].parent_index, sizeof(uint), 1);
 502
 503       cellplane.cell_id = -1;
 504       cellplane.plane_id = -1;
 505
 506       if (g_wrBspTree[i].plane)
 507       {
 508          if (!gCellPlaneTable.Lookup((long)g_wrBspTree[i].plane, &cellplane))
 509          {
 510             // Must be an extra plane
 511             for (int j=0; j<gExtraPlaneList.Size(); j++)
 512             {
 513                if (g_wrBspTree[i].plane == gExtraPlaneList[j])
 514                {
 515                   cellplane.plane_id = j;
 516                   break;
 517                }
 518             }
 519          }
 520
 521          AssertMsg(cellplane.plane_id != -1, "Unable to match plane pointer in BSP save");
 522       }
 523
 524       write(&cellplane, sizeof(sCellPlane), 1);
 525
 526       write(&g_wrBspTree[i].inside_index, sizeof(uint), 1);
 527       write(&g_wrBspTree[i].outside_index, sizeof(uint), 1);
 528    }
 529
 530    // And clean up
 531
 532    gCellPlaneTable.Clear();
 533 }
 534
 535
 536 void wrBspTreeRead(PortalReadWrite read)
 537 {
 538    sCellPlane cellplane;
 539    int i;
 540
 541    int size;
 542
 543    read(&size, sizeof(int), 1);
 544
 545    gExtraPlaneList.SetSize(size);
 546    for (i=0; i<size; i++)
 547    {
 548       PortalPlane* plane = new PortalPlane;
 549       read(&plane->normal,sizeof(plane->normal),1);
 550       read(&plane->plane_constant,sizeof(plane->plane_constant),1);
 551
 552       gExtraPlaneList[i] = plane;
 553    }
 554
 555    read(&g_wrBspTreeSize, sizeof(int), 1);
 556
 557    LGALLOC_PUSH_CREDIT();
 558    wrBspTree.SetSize(g_wrBspTreeSize);
 559    LGALLOC_POP_CREDIT();
 560
 561    if (g_wrBspTreeSize > 0)
 562       g_wrBspTree = &wrBspTree[0];
 563    else
 564       g_wrBspTree = NULL;
 565
 566    for (i=0; i<g_wrBspTreeSize; i++)
 567    {
 568       read(&g_wrBspTree[i].parent_index, sizeof(uint), 1);
 569
 570       read(&cellplane, sizeof(sCellPlane), 1);
 571
 572       if (cellplane.cell_id == -1)
 573       {
 574          if (cellplane.plane_id == -1)
 575             g_wrBspTree[i].plane = NULL;
 576          else
 577             g_wrBspTree[i].plane = gExtraPlaneList[cellplane.plane_id];
 578       }
 579       else
 580          g_wrBspTree[i].plane = &WR_CELL(cellplane.cell_id)->plane_list[cellplane.plane_id];
 581
 582       read(&g_wrBspTree[i].inside_index, sizeof(uint), 1);
 583       read(&g_wrBspTree[i].outside_index, sizeof(uint),1);
 584    }
 585
 586 }
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603