nel/src/pacs/build_indoor.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This source file has been modified by the following contributors:
   5 // Copyright (C) 2019-2020  Jan BOON (Kaetemi) <jan.boon@kaetemi.be>
   6 //
   7 // This program is free software: you can redistribute it and/or modify
   8 // it under the terms of the GNU Affero General Public License as
   9 // published by the Free Software Foundation, either version 3 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU Affero General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Affero General Public License
  18 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19
  20 #include "stdpacs.h"
  21 #include "nel/pacs/build_indoor.h"
  22
  23 #include <sstream>
  24
  25 #include "nel/pacs/collision_mesh_build.h"
  26 #include "nel/pacs/local_retriever.h"
  27 #include "nel/pacs/exterior_mesh.h"
  28
  29 using namespace std;
  30 using namespace NLMISC;
  31
  32 namespace NLPACS
  33 {
  34
  35 /**
  36  * The interior surface class. Intermediate to compute real retriever surfaces
  37  * \author Benjamin Legros
  38  * \author Nevrax France
  39  * \date 2001
  40  */
  41 class CInteriorSurface
  42 {
  43 public:
  44         /// The collision mesh root object
  45         CCollisionMeshBuild                             *CollisionMeshBuild;
  46
  47         /// The faces that compose the surface
  48         std::vector<uint32>                             Faces;
  49
  50         /// The Id of the surface
  51         sint32                                                  Id;
  52
  53         /// The center of the surface
  54         NLMISC::CVector                                 Center;
  55
  56         /// The material of the surface
  57         sint32                                                  Material;
  58
  59 public:
  60         CCollisionFace                                  &getFace(uint face) { return CollisionMeshBuild->Faces[Faces[face]]; }
  61         CCollisionFace                                  &getNeighbor(uint face, uint edge)
  62         {
  63                 return CollisionMeshBuild->Faces[getFace(face).Edge[edge]];
  64         }
  65 };
  66
  67
  68 /**
  69  * The border of interior surfaces.
  70  * \author Benjamin Legros
  71  * \author Nevrax France
  72  * \date 2001
  73  */
  74 class CInteriorBorder
  75 {
  76 public:
  77         /// The vertices that compose the border
  78         std::vector<NLMISC::CVector>    Vertices;
  79
  80         /// The left and right surfaces
  81         sint32                                                  Left, Right;
  82
  83 public:
  84 };
  85
  86
  87 // how to build interior snapping data
  88 void    buildSnapping(CCollisionMeshBuild &cmb, CLocalRetriever &lr);
  89
  90
  91 // how to build surfaces
  92 void    buildSurfaces(CCollisionMeshBuild &cmb, CLocalRetriever &lr);
  93
  94
  95
  96 //
  97 // functions to build interior surfaces and borders from mesh
  98 //
  99
 100 // how to generate connex surfaces
 101 void    floodFillSurfaces(CCollisionMeshBuild &cmb, vector<CInteriorSurface> &surfaces)
 102 {
 103         sint32  currentId = 0;
 104
 105         uint    i;
 106
 107         for (i=0; i<cmb.Faces.size(); ++i)
 108                 cmb.Faces[i].InternalSurface = -1;
 109
 110         for (i=0; i<cmb.Faces.size(); ++i)
 111         {
 112                 CCollisionFace  &face = cmb.Faces[i];
 113                 if (face.Surface == CCollisionFace::ExteriorSurface || face.InternalSurface != -1)
 114                         continue;
 115
 116                 vector<sint32>  stack;
 117                 stack.push_back(sint32(i));
 118                 face.InternalSurface = currentId;
 119
 120                 surfaces.resize(surfaces.size()+1);
 121                 surfaces.back().Id = currentId;
 122                 surfaces.back().CollisionMeshBuild = &cmb;
 123                 surfaces.back().Material = face.Material;
 124
 125                 while (!stack.empty())
 126                 {
 127                         uint    pop = stack.back();
 128                         stack.pop_back();
 129
 130                         surfaces.back().Faces.push_back(pop);
 131                         CCollisionFace  &popFace = cmb.Faces[pop];
 132
 133                         sint32  edge, neighb;
 134                         for (edge=0; edge<3; ++edge)
 135                         {
 136                                 if ((neighb = popFace.Edge[edge]) != -1 &&
 137                                         cmb.Faces[neighb].InternalSurface == -1 &&
 138                                         cmb.Faces[neighb].Surface == popFace.Surface)
 139                                 {
 140                                         cmb.Faces[neighb].InternalSurface = currentId;
 141                                         stack.push_back(neighb);
 142                                 }
 143                         }
 144                 }
 145
 146                 ++currentId;
 147         }
 148 }
 149
 150
 151 // reset the edge flags of the whole collision mesh build
 152 void    resetEdgeFlags(CCollisionMeshBuild &cmb)
 153 {
 154         uint    face, edge;
 155
 156         for (face=0; face<cmb.Faces.size(); ++face)
 157                 for (edge=0; edge<3; ++edge)
 158                         cmb.Faces[face].EdgeFlags[edge] = false;
 159 }
 160
 161
 162
 163 // how to generate the borders of a given surface
 164
 165 void    followBorder(CInteriorSurface &surface, uint first, uint edge, uint sens, vector<CVector> &vstore, bool &loop)
 166 {
 167         CCollisionFace  *current = &surface.getFace(first);
 168         CCollisionFace  *next = (current->Edge[edge] == -1) ? NULL : &surface.CollisionMeshBuild->Faces[current->Edge[edge]];
 169         current->EdgeFlags[edge] = true;
 170         sint32                  currentFace = surface.Faces[first];
 171
 172         const sint32    currentSurfId = current->InternalSurface;
 173         const sint32    oppositeSurfId = (next != NULL) ? next->InternalSurface : (current->Visibility[edge] ? -1 : -2);
 174         sint                    oedge;
 175
 176         sint                    pivot = (edge+sens)%3;
 177         sint                    nextEdge = edge;
 178
 179         bool                    allowThis = true;
 180
 181         // adds the pivot to the border and its normal
 182         vstore.push_back(surface.CollisionMeshBuild->Vertices[current->V[pivot]]);
 183
 184         for(;;)
 185         {
 186                 loop = false;
 187                 // -1 means no neighbor at all, -2 means a neighbor that is not available yet
 188                 sint32  thisOpposite = (next != NULL) ? next->InternalSurface : (current->Visibility[nextEdge] ? -1 : -2);
 189                 if ((thisOpposite != currentSurfId && thisOpposite != oppositeSurfId) ||
 190                         (loop = (current->EdgeFlags[nextEdge] && !allowThis)))
 191                 {
 192                         // if reaches the end of the border, then quits.
 193                         break;
 194                 }
 195                 else if (thisOpposite == oppositeSurfId)
 196                 {
 197                         // if the next edge belongs to the border, then go on the same element
 198                         current->EdgeFlags[nextEdge] = true;
 199                         if (oppositeSurfId >= 0)
 200                         {
 201                                 for (oedge=0; oedge<3 && next->Edge[oedge]!=currentFace; ++oedge)
 202                                         ;
 203                                 nlassert(oedge != 3);
 204                                 nlassert(allowThis || !next->EdgeFlags[oedge]);
 205                                 next->EdgeFlags[oedge] = true;
 206                         }
 207                         pivot = (pivot+sens)%3;
 208                         nextEdge = (nextEdge+sens)%3;
 209                         next = (current->Edge[nextEdge] == -1) ? NULL : &surface.CollisionMeshBuild->Faces[current->Edge[nextEdge]];
 210                         vstore.push_back(surface.CollisionMeshBuild->Vertices[current->V[pivot]]);
 211                 }
 212                 else
 213                 {
 214                         // if the next element is inside the surface, then go to the next element
 215                         nlassert(next);
 216                         nlassert(next->InternalSurface == currentSurfId);
 217
 218                         for (oedge=0; oedge<3 && next->Edge[oedge]!=currentFace; ++oedge)
 219                                 ;
 220                         nlassert(oedge != 3);
 221                         currentFace = current->Edge[nextEdge];
 222                         current = next;
 223                         pivot = (oedge+3-sens)%3;
 224                         nextEdge = (oedge+sens)%3;
 225                         next = (current->Edge[nextEdge] == -1) ? NULL : &surface.CollisionMeshBuild->Faces[current->Edge[nextEdge]];
 226                 }
 227
 228                 allowThis = false;
 229         }
 230 }
 231
 232
 233 void    computeSurfaceBorders(CInteriorSurface &surface, vector<CInteriorBorder> &borders)
 234 {
 235         uint    face, edge;
 236
 237         for (face=0; face<surface.Faces.size(); ++face)
 238         {
 239                 // for each element,
 240                 // scan for a edge that points to a different surface
 241                 CCollisionFace  &cf = surface.getFace(face);
 242
 243                 for (edge=0; edge<3; ++edge)
 244                 {
 245                         if ((cf.Edge[edge] == -1 || surface.getNeighbor(face, edge).InternalSurface != surface.Id) &&
 246                                 !cf.EdgeFlags[edge])
 247                         {
 248                                 borders.resize(borders.size()+1);
 249                                 CInteriorBorder &border = borders.back();
 250
 251                                 border.Left = cf.InternalSurface;
 252
 253                                 if (cf.Edge[edge] == -1)
 254                                 {
 255                                         // link on a neighbor retriever or not at all
 256                                         border.Right = cf.Visibility[edge] ? -1 : -2;
 257                                 }
 258                                 else
 259                                 {
 260                                         // link on the neighbor surface
 261                                         border.Right = surface.CollisionMeshBuild->Faces[cf.Edge[edge]].InternalSurface;
 262                                 }
 263
 264                                 nldebug("generate border %d (%d-%d)", borders.size()-1, border.Left, border.Right);
 265
 266                                 bool                            loop;
 267                                 vector<CVector>         bwdVerts;
 268                                 vector<CVector>         &fwdVerts = border.Vertices;
 269
 270                                 followBorder(surface, face, edge, 2, bwdVerts, loop);
 271
 272                                 sint    i;
 273
 274                                 fwdVerts.reserve(bwdVerts.size());
 275                                 fwdVerts.clear();
 276
 277                                 for (i=(sint)(bwdVerts.size()-1); i>=0; --i)
 278                                 {
 279                                         fwdVerts.push_back(bwdVerts[i]);
 280                                 }
 281
 282                                 if (loop)
 283                                 {
 284                                         fwdVerts.push_back(fwdVerts.front());
 285                                 }
 286                                 else
 287                                 {
 288                                         fwdVerts.resize(fwdVerts.size()-2);
 289                                         followBorder(surface, face, edge, 1, fwdVerts, loop);
 290                                 }
 291                         }
 292                 }
 293         }
 294 }
 295
 296
 297 void    computeSurfaceCenter(CInteriorSurface &surface)
 298 {
 299         CCollisionMeshBuild     &cmb = *(surface.CollisionMeshBuild);
 300
 301         CVector         center = CVector::Null;
 302         float           totalWeight = 0.0f;
 303
 304         uint    i, j;
 305
 306         for (i=0; i<surface.Faces.size(); ++i)
 307         {
 308                 CCollisionFace  &face = surface.getFace(i);
 309                 CVector                 v[3];
 310
 311                 for (j=0; j<3; ++j)
 312                         v[j] = cmb.Vertices[face.V[j]];
 313
 314                 float   weight = ((v[2]-v[0])^(v[1]-v[0])).norm();
 315
 316                 center += (v[0]+v[1]+v[2])*(weight/3.0f);
 317                 totalWeight += weight;
 318         }
 319
 320         surface.Center = center/totalWeight;
 321 }
 322
 323
 324 void    computeSurfaceQuadTree(CInteriorSurface &surface, CSurfaceQuadTree &quad)
 325 {
 326         uint    i, j;
 327
 328         CAABBox box;
 329         bool    first = true;
 330         for (i=0; i<surface.Faces.size(); ++i)
 331         {
 332                 for (j=0; j<3; ++j)
 333                 {
 334                         const CVector   &v = surface.CollisionMeshBuild->Vertices[surface.CollisionMeshBuild->Faces[surface.Faces[i]].V[j]];
 335                         if (first)
 336                                 box.setCenter(v), first=false;
 337                         else
 338                                 box.extend(v);
 339                 }
 340         }
 341
 342         quad.clear();
 343         quad.init(4.0f, 6, box.getCenter(), std::max(box.getHalfSize().x, box.getHalfSize().y));
 344
 345         for (i=0; i<surface.Faces.size(); ++i)
 346         {
 347                 for (j=0; j<3; ++j)
 348                 {
 349                         const CVector   &v = surface.CollisionMeshBuild->Vertices[surface.CollisionMeshBuild->Faces[surface.Faces[i]].V[j]];
 350                         quad.addVertex(v);
 351                 }
 352         }
 353
 354         quad.compile();
 355 }
 356
 357
 358 void    buildSurfaces(CCollisionMeshBuild &cmb, CLocalRetriever &lr)
 359 {
 360         vector<CInteriorSurface>        surfaces;
 361         vector<CInteriorBorder>         borders;
 362
 363         floodFillSurfaces(cmb, surfaces);
 364
 365         resetEdgeFlags(cmb);
 366
 367         uint    surf, bord;
 368
 369         for (surf=0; surf<surfaces.size(); ++surf)
 370         {
 371                 CSurfaceQuadTree        quad;
 372                 computeSurfaceBorders(surfaces[surf], borders);
 373                 computeSurfaceCenter(surfaces[surf]);
 374                 computeSurfaceQuadTree(surfaces[surf], quad);
 375                 lr.addSurface(0, 0, (uint8)surfaces[surf].Material, 0, 0, false, 0.0f, false, surfaces[surf].Center, quad);
 376                 //lr.addSurface(0, 0, (uint8)surfaces[surf].Material, 0, 0, false, 0.0f, /*false,*/ surfaces[surf].Center, quad);
 377         }
 378
 379         sint    numBorderChains = 0;
 380
 381         for (bord=0; bord<borders.size(); ++bord)
 382         {
 383                 sint32  left = borders[bord].Left;
 384                 sint32  right = (borders[bord].Right == -2) ? CChain::convertBorderChainId(numBorderChains++) : borders[bord].Right;
 385
 386                 if (left<0 || left>=(sint)surfaces.size() ||
 387                         right>(sint)surfaces.size())
 388                         nlstop;
 389
 390                 lr.addChain(borders[bord].Vertices, left, right);
 391         }
 392 }
 393
 394
 395 //
 396
 397 void    buildSnapping(CCollisionMeshBuild &cmb, CLocalRetriever &lr)
 398 {
 399         // copy the vertices
 400         lr.getInteriorVertices() = cmb.Vertices;
 401
 402         // create the faces
 403         uint    i;
 404         vector<CLocalRetriever::CInteriorFace>  &faces = lr.getInteriorFaces();
 405         for (i=0; i<cmb.Faces.size(); ++i)
 406         {
 407                 faces.push_back(CLocalRetriever::CInteriorFace());
 408                 faces.back().Verts[0] = cmb.Faces[i].V[0];
 409                 faces.back().Verts[1] = cmb.Faces[i].V[1];
 410                 faces.back().Verts[2] = cmb.Faces[i].V[2];
 411                 faces.back().Surface = cmb.Faces[i].InternalSurface;
 412         }
 413
 414         // create the face grid
 415         lr.initFaceGrid();
 416 }
 417
 418
 419 //
 420 // functions to build local retrievers
 421 //
 422
 423 void    buildExteriorMesh(CCollisionMeshBuild &cmb, CExteriorMesh &em)
 424 {
 425         // find the first non interior face
 426         uint                                                    i,
 427                                                                         edge = 0;
 428
 429         vector<CExteriorMesh::CEdge>    edges;
 430         uint                                                    numLink = 0;
 431
 432         for (i=0; i<cmb.Faces.size(); ++i)
 433         {
 434                 cmb.Faces[i].EdgeFlags[0] = false;
 435                 cmb.Faces[i].EdgeFlags[1] = false;
 436                 cmb.Faces[i].EdgeFlags[2] = false;
 437         }
 438
 439         i = 0;
 440
 441         for(;;)
 442         {
 443                 bool    found = false;
 444                 for (; i<cmb.Faces.size() && !found; ++i)
 445                 {
 446                         if (cmb.Faces[i].Surface != CCollisionFace::ExteriorSurface)
 447                                 continue;
 448
 449                         for (edge=0; edge<3 && !found; ++edge)
 450                                 if (cmb.Faces[i].Edge[edge] == -1 && !cmb.Faces[i].EdgeFlags[edge])
 451                                 {
 452                                         found = true;
 453                                         break;
 454                                 }
 455
 456                         if (found)
 457                                 break;
 458                 }
 459
 460                 //
 461                 if (!found)
 462                         break;
 463
 464                 sint32                  current = i;
 465                 sint32                  next = cmb.Faces[current].Edge[edge];
 466
 467                 sint                    oedge;
 468                 sint                    pivot = (edge+1)%3;
 469                 sint                    nextEdge = edge;
 470
 471                 uint                    firstExtEdge = (uint)edges.size();
 472
 473                 for(;;)
 474                 {
 475                         if (cmb.Faces[current].EdgeFlags[nextEdge])
 476                         {
 477                                 // if reaches the end of the border, then quits.
 478                                 break;
 479                         }
 480                         else if (next == -1)
 481                         {
 482                                 // if the next edge belongs to the border, then go on the same element
 483                                 cmb.Faces[current].EdgeFlags[nextEdge] = true;
 484                                 sint    link = (cmb.Faces[current].Visibility[nextEdge]) ? -1 : sint((numLink++));
 485                                 edges.push_back(CExteriorMesh::CEdge(cmb.Vertices[cmb.Faces[current].V[pivot]], link));
 486                                 nldebug("border: vertex=%d (%.2f,%.2f,%.2f) link=%d", cmb.Faces[current].V[pivot], cmb.Vertices[cmb.Faces[current].V[pivot]].x, cmb.Vertices[cmb.Faces[current].V[pivot]].y, cmb.Vertices[cmb.Faces[current].V[pivot]].z, link);
 487                                 pivot = (pivot+1)%3;
 488                                 nextEdge = (nextEdge+1)%3;
 489                                 next = cmb.Faces[current].Edge[nextEdge];
 490                         }
 491                         else
 492                         {
 493                                 // if the next element is inside the surface, then go to the next element
 494                                 for (oedge=0; oedge<3 && cmb.Faces[next].Edge[oedge]!=current; ++oedge)
 495                                         ;
 496                                 nlassert(oedge != 3);
 497                                 current = next;
 498                                 pivot = (oedge+2)%3;
 499                                 nextEdge = (oedge+1)%3;
 500                                 next = cmb.Faces[current].Edge[nextEdge];
 501                         }
 502                 }
 503
 504                 edges.push_back(edges[firstExtEdge]);
 505                 edges.back().Link = -2;
 506         }
 507
 508         em.setEdges(edges);
 509 }
 510
 511
 512 //
 513 void    linkExteriorToInterior(CLocalRetriever &lr)
 514 {
 515         CExteriorMesh                                   em = lr.getExteriorMesh();
 516         vector<CExteriorMesh::CEdge>    edges = em.getEdges();
 517         vector<CExteriorMesh::CLink>    links;
 518         const vector<CChain>                    &chains = lr.getChains();
 519         const vector<COrderedChain3f>   &ochains = lr.getFullOrderedChains();
 520         const vector<uint16>                    &bchains = lr.getBorderChains();
 521
 522         {
 523                 uint    i;
 524
 525                 for (i=0; i<bchains.size(); ++i)
 526                 {
 527                         char    w[256];
 528                         std::stringstream ss;
 529                         const CChain    &chain = chains[bchains[i]];
 530                         sprintf(w, "chain=%d ", bchains[i]);
 531                         ss << w;
 532                         uint    och;
 533                         for (och=0; och<chain.getSubChains().size(); ++och)
 534                         {
 535                                 const COrderedChain3f   &ochain = ochains[chain.getSubChain(och)];
 536                                 sprintf(w, "subchain=%d", chain.getSubChain(och));
 537                                 ss << w;
 538                                 uint    v;
 539                                 for (v=0; v<ochain.getVertices().size(); ++v)
 540                                 {
 541                                         sprintf(w, " (%.2f,%.2f)", ochain[v].x, ochain[v].y);
 542                                         ss << w;
 543                                 }
 544                         }
 545
 546                         nlinfo("%s", ss.str().c_str());
 547                 }
 548         }
 549
 550         uint    edge, ch;
 551         for (edge=0; edge+1<edges.size(); ++edge)
 552         {
 553                 if (edges[edge].Link == -1)
 554                         continue;
 555
 556                 CVector start = edges[edge].Start, stop = edges[edge+1].Start;
 557                 bool    found = false;
 558
 559                 for (ch=0; ch<bchains.size() && !found; ++ch)
 560                 {
 561                         // get the border chain.
 562                         //const CChain  &chain = chains[bchains[ch]];
 563
 564                         const CVector   &cstart = lr.getStartVector(bchains[ch]),
 565                                                         &cstop = lr.getStopVector(bchains[ch]);
 566
 567                         float d = (start-cstart).norm()+(stop-cstop).norm();
 568                         if (d < 1.0e-1f)
 569                         {
 570                                 found = true;
 571                                 break;
 572                         }
 573                 }
 574
 575                 // create a link
 576                 CExteriorMesh::CLink    link;
 577
 578                 if (!found)
 579                 {
 580                         nlwarning("in linkInteriorToExterior():");
 581                         nlwarning("couldn't find any link to the exterior edge %d!!", edge);
 582                 }
 583                 else
 584                 {
 585                         // set it up to point on the chain and surface
 586                         link.BorderChainId = uint16(ch);
 587                         link.ChainId = bchains[ch];
 588                         link.SurfaceId = (uint16)chains[link.ChainId].getLeft();
 589                 }
 590
 591                 // enlarge the links
 592                 if (edges[edge].Link >= (sint)links.size())
 593                         links.resize(edges[edge].Link+1);
 594
 595                 // if the link already exists, warning
 596                 if (links[edges[edge].Link].BorderChainId != 0xFFFF ||
 597                         links[edges[edge].Link].ChainId != 0xFFFF ||
 598                         links[edges[edge].Link].SurfaceId != 0xFFFF)
 599                 {
 600                         nlwarning("in linkInteriorToExterior():");
 601                         nlwarning("link %d already set!!", edges[edge].Link);
 602                 }
 603
 604                 // setup the link
 605                 links[edges[edge].Link] = link;
 606         }
 607
 608         em.setEdges(edges);
 609         em.setLinks(links);
 610         lr.setExteriorMesh(em);
 611 }
 612
 613
 614
 615
 616
 617 //
 618 bool    computeRetriever(CCollisionMeshBuild &cmb, CLocalRetriever &lr, CVector &translation, string &error, bool useCmbTrivialTranslation)
 619 {
 620         // set the retriever
 621         lr.setType(CLocalRetriever::Interior);
 622
 623         // if should use the own cmb bbox, then compute it
 624         if (useCmbTrivialTranslation)
 625         {
 626                 translation = cmb.computeTrivialTranslation();
 627                 // snap the translation vector to a meter wide grid
 628                 translation.x = (float)ceil(translation.x);
 629                 translation.y = (float)ceil(translation.y);
 630                 translation.z = 0.0f;
 631         }
 632
 633         vector<string>  errors;
 634
 635         cmb.link(false, errors);
 636         cmb.link(true, errors);
 637
 638         if (!errors.empty())
 639         {
 640                 nlwarning("Edge issues reported !!");
 641                 uint    i;
 642                 error.clear();
 643                 for (i=0; i<errors.size(); ++i)
 644                         error += errors[i]+"\n";
 645                 return false;
 646         }
 647
 648         // translate the meshbuild to the local axis
 649         cmb.translate(translation);
 650
 651         // find the exterior mesh border
 652         CExteriorMesh   extMesh;
 653         buildExteriorMesh(cmb, extMesh);
 654         lr.setExteriorMesh(extMesh);
 655
 656         // build the surfaces in the local retriever
 657         buildSurfaces(cmb, lr);
 658
 659         // create the snapping faces and vertices
 660         // after the build surfaces because the InternalSurfaceId is filled within buildSurfaces()...
 661         buildSnapping(cmb, lr);
 662
 663         //
 664         lr.computeLoopsAndTips();
 665
 666         lr.findBorderChains();
 667         lr.updateChainIds();
 668         lr.computeTopologies();
 669
 670         lr.unify();
 671
 672         lr.computeCollisionChainQuad();
 673 /*
 674         //
 675         for (i=0; i<lr.getSurfaces().size(); ++i)
 676                 lr.dumpSurface(i);
 677 */
 678         //
 679         linkExteriorToInterior(lr);
 680
 681         // compute the bbox of the retriever
 682         uint    i, j;
 683         CAABBox bbox;
 684         bool    first = true;
 685
 686         for (i=0; i<extMesh.getEdges().size(); ++i)
 687                 if (!first)
 688                         bbox.extend(extMesh.getEdge(i).Start);
 689                 else
 690                         bbox.setCenter(extMesh.getEdge(i).Start), first=false;
 691
 692         for (i=0; i<lr.getOrderedChains().size(); ++i)
 693                 for (j=0; j<lr.getOrderedChain(i).getVertices().size(); ++j)
 694                         if (!first)
 695                                 bbox.extend(lr.getOrderedChain(i)[j].unpack3f());
 696                         else
 697                                 bbox.setCenter(lr.getOrderedChain(i)[j].unpack3f()), first=false;
 698
 699         CVector bboxhs = bbox.getHalfSize();
 700         bboxhs.z = 10000.0f;
 701         bbox.setHalfSize(bboxhs);
 702
 703         lr.setBBox(bbox);
 704
 705         return true;
 706 }
 707
 708 } // NLPACS
 709