nel/tools/pacs/build_indoor_rbank/mouline.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  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 <map>
  21 #include <vector>
  22 #include <sstream>
  23
  24 #include "nel/pacs/collision_mesh_build.h"
  25 #include "nel/pacs/local_retriever.h"
  26 #include "nel/pacs/exterior_mesh.h"
  27
  28 #include "mouline.h"
  29 #include "build_surfaces.h"
  30
  31 using namespace std;
  32 using namespace NLMISC;
  33 using namespace NLPACS;
  34
  35 /*
  36 // a reference on an edge
  37 struct CEdgeKey
  38 {
  39         uint32  V0;
  40         uint32  V1;
  41
  42         CEdgeKey() {}
  43         CEdgeKey(uint32 v0, uint32 v1) : V0(v0), V1(v1) {}
  44
  45         bool    operator() (const CEdgeKey &a, const CEdgeKey &b)
  46         {
  47                 return a.V0 < b.V0 || (a.V0 == b.V0 && a.V1 < b.V1);
  48         }
  49 };
  50
  51 // the info on an edge
  52 struct CEdgeInfo
  53 {
  54         sint32  Left, LeftEdge;
  55         sint32  Right, RightEdge;
  56
  57         CEdgeInfo(sint32 left=-1, sint32 leftEdge=-1, sint32 right=-1, sint32 rightEdge=-1) : Left(left), LeftEdge(leftEdge), Right(right), RightEdge(rightEdge) {}
  58 };
  59
  60 typedef map<CEdgeKey, CEdgeInfo, CEdgeKey>      TLinkRelloc;
  61 typedef TLinkRelloc::iterator                           ItTLinkRelloc;
  62
  63
  64 //
  65 void    linkMesh(CCollisionMeshBuild &cmb, bool linkInterior)
  66 {
  67         uint                    i, j;
  68         TLinkRelloc             relloc;
  69
  70         // check each edge of each face
  71         for (i=0; i<cmb.Faces.size(); ++i)
  72         {
  73                 if (cmb.Faces[i].Surface == CCollisionFace::ExteriorSurface && linkInterior ||
  74                         cmb.Faces[i].Surface >= CCollisionFace::InteriorSurfaceFirst && !linkInterior)
  75                         continue;
  76
  77                 for (j=0; j<3; ++j)
  78                 {
  79                         cmb.Faces[i].Edge[j] = -1;
  80
  81                         uint    edge = (j+2)%3;
  82                         uint32  va = cmb.Faces[i].V[j],
  83                                         vb = cmb.Faces[i].V[(j+1)%3];
  84
  85                         ItTLinkRelloc   it;
  86                         if ((it = relloc.find(CEdgeKey(va, vb))) != relloc.end())
  87                         {
  88                                 // in this case, the left triangle of the edge has already been found.
  89                                 // should throw an error
  90                                 nlerror("On face %d, edge %d: left side of edge (%d,%d) already linked to face %d",
  91                                                 i, edge, va, vb, (*it).second.Left);
  92                         }
  93                         else if ((it = relloc.find(CEdgeKey(vb, va))) != relloc.end())
  94                         {
  95                                 // in this case, we must check the right face has been set yet
  96                                 if ((*it).second.Right != -1)
  97                                 {
  98                                         nlerror("On face %d, edge %d: right side of edge (%d,%d) already linked to face %d",
  99                                                         i, edge, vb, va, (*it).second.Right);
 100                                 }
 101
 102                                 (*it).second.Right = i;
 103                                 (*it).second.RightEdge = edge;
 104                         }
 105                         else
 106                         {
 107                                 // if the edge wasn't present yet, create it and set it up.
 108                                 relloc.insert(make_pair(CEdgeKey(va, vb), CEdgeInfo(i, edge, -1, -1)));
 109                         }
 110                 }
 111         }
 112
 113         // for each checked edge, update the edge info inside the faces
 114         ItTLinkRelloc   it;
 115         for (it=relloc.begin(); it!=relloc.end(); ++it)
 116         {
 117                 sint32  left, leftEdge;
 118                 sint32  right, rightEdge;
 119
 120                 // get the link info on the edge
 121                 left = (*it).second.Left;
 122                 leftEdge = (*it).second.LeftEdge;
 123                 right = (*it).second.Right;
 124                 rightEdge = (*it).second.RightEdge;
 125
 126                 // update both faces
 127                 if (left != -1)
 128                         cmb.Faces[left].Edge[leftEdge] = right;
 129                 if (right != -1)
 130                         cmb.Faces[right].Edge[rightEdge] = left;
 131         }
 132 }
 133 */
 134
 135
 136
 137 void    buildExteriorMesh(CCollisionMeshBuild &cmb, CExteriorMesh &em)
 138 {
 139         uint                                                    startFace = 0;
 140         vector<CExteriorMesh::CEdge>    edges;
 141
 142         uint    i;
 143         for (i=0; i<cmb.Faces.size(); ++i)
 144         {
 145                 cmb.Faces[i].EdgeFlags[0] = false;
 146                 cmb.Faces[i].EdgeFlags[1] = false;
 147                 cmb.Faces[i].EdgeFlags[2] = false;
 148         }
 149
 150         while (true)
 151         {
 152                 // find the first non interior face
 153                 uint    i, edge;
 154                 bool    found = false;
 155                 for (i=startFace; i<cmb.Faces.size() && !found; ++i)
 156                 {
 157                         if (cmb.Faces[i].Surface != CCollisionFace::ExteriorSurface)
 158                                 continue;
 159
 160                         for (edge=0; edge<3 && !found; ++edge)
 161                                 if (cmb.Faces[i].Edge[edge] == -1 && !cmb.Faces[i].EdgeFlags[edge])
 162                                 {
 163 //                                      nlassert(cmb.Faces[i].Material != 0xdeadbeef);
 164                                         found = true;
 165                                         break;
 166                                 }
 167
 168                         if (found)
 169                                 break;
 170                 }
 171
 172                 //
 173                 if (!found)
 174                         break;
 175
 176 //              cmb.Faces[i].Material = 0xdeadbeef;
 177
 178                 startFace = i+1;
 179
 180                 sint32          current = i;
 181                 sint32          next = cmb.Faces[current].Edge[edge];
 182
 183                 sint            oedge;
 184                 sint            pivot = (edge+1)%3;
 185                 sint            nextEdge = edge;
 186                 bool            allowThis = true;
 187
 188                 uint            numLink = 0;
 189                 uint            firstEdge = (uint)edges.size();
 190
 191                 vector<CExteriorMesh::CEdge>    loop;
 192
 193                 while (true)
 194                 {
 195                         if (cmb.Faces[current].EdgeFlags[nextEdge])
 196                         {
 197                                 // if reaches the end of the border, then quits.
 198                                 break;
 199                         }
 200                         else if (next == -1)
 201                         {
 202                                 // if the next edge belongs to the border, then go on the same element
 203                                 cmb.Faces[current].EdgeFlags[nextEdge] = true;
 204                                 /// \todo get the real edge link
 205                                 sint    link = (cmb.Faces[current].Visibility[nextEdge]) ? -1 : 0;      //(numLink++);
 206
 207                                 //edges.push_back(CExteriorMesh::CEdge(cmb.Vertices[cmb.Faces[current].V[pivot]], link));
 208                                 loop.push_back(CExteriorMesh::CEdge(cmb.Vertices[cmb.Faces[current].V[pivot]], link));
 209
 210                                 pivot = (pivot+1)%3;
 211                                 nextEdge = (nextEdge+1)%3;
 212                                 next = cmb.Faces[current].Edge[nextEdge];
 213                         }
 214                         else
 215                         {
 216                                 // if the next element is inside the surface, then go to the next element
 217                                 for (oedge=0; oedge<3 && cmb.Faces[next].Edge[oedge]!=current; ++oedge)
 218                                         ;
 219                                 nlassert(oedge != 3);
 220                                 current = next;
 221                                 pivot = (oedge+2)%3;
 222                                 nextEdge = (oedge+1)%3;
 223                                 next = cmb.Faces[current].Edge[nextEdge];
 224                         }
 225                 }
 226
 227                 // mark the end of a ext mesh block
 228                 // this way, collisions won't be checked in the pacs engine
 229                 if (loop.size() >= 3)
 230                 {
 231                         uint    n = (uint)loop.size();
 232                         while (loop.front().Link >= 0 && loop.back().Link >= 0 && n > 0)
 233                         {
 234                                 loop.push_back(loop.front());
 235                                 loop.erase(loop.begin());
 236                                 --n;
 237                         }
 238                 }
 239                 loop.push_back(loop.front());
 240                 loop.back().Link = -2;
 241                 edges.insert(edges.end(), loop.begin(), loop.end());
 242                 //edges.push_back(edges[firstEdge]);
 243                 //edges.back().Link = -2;
 244         }
 245
 246         bool    previousWasLink = false;
 247         sint    previousLink = -1;
 248         for (i=0; i<edges.size(); ++i)
 249         {
 250 //              nldebug("ext-mesh: vertex=%d (%.2f,%.2f,%.2f) link=%d", i, edges[i].Start.x, edges[i].Start.y, edges[i].Start.z, edges[i].Link);
 251                 if (edges[i].Link >= 0)
 252                 {
 253                         if (!previousWasLink)
 254                                 ++previousLink;
 255                         edges[i].Link = previousLink;
 256                         previousWasLink = true;
 257                 }
 258                 else
 259                 {
 260                         previousWasLink = false;
 261                 }
 262         }
 263
 264         em.setEdges(edges);
 265 }
 266
 267
 268 //
 269 void    linkExteriorToInterior(CLocalRetriever &lr)
 270 {
 271         CExteriorMesh                                   em = lr.getExteriorMesh();
 272         vector<CExteriorMesh::CEdge>    edges = em.getEdges();
 273         vector<CExteriorMesh::CLink>    links;
 274         const vector<CChain>                    &chains = lr.getChains();
 275         const vector<COrderedChain3f>   &ochains = lr.getFullOrderedChains();
 276         const vector<uint16>                    &bchains = lr.getBorderChains();
 277
 278         {
 279                 uint    i;
 280
 281                 nlinfo("Border chains (to be linked) for this retriever:");
 282
 283                 for (i=0; i<bchains.size(); ++i)
 284                 {
 285                         char w[256];
 286                         std::stringstream ss;
 287                         const CChain    &chain = chains[bchains[i]];
 288                         sprintf(w, "Border chain %d: chain=%d ", i, bchains[i]);
 289                         ss << w;
 290                         uint    och;
 291                         for (och=0; och<chain.getSubChains().size(); ++och)
 292                         {
 293                                 const COrderedChain3f   &ochain = ochains[chain.getSubChain(och)];
 294                                 sprintf(w, "subchain=%d", chain.getSubChain(och));
 295                                 ss << w;
 296                                 uint    v;
 297                                 for (v=0; v<ochain.getVertices().size(); ++v)
 298                                 {
 299                                         sprintf(w, " (%.2f,%.2f)", ochain[v].x, ochain[v].y);
 300                                         ss << w;
 301                                 }
 302                         }
 303
 304                         nlinfo("%s", ss.str().c_str());
 305                 }
 306         }
 307
 308         uint    edge, ch;
 309         for (edge=0; edge+1<edges.size(); )
 310         {
 311                 if (edges[edge].Link == -1 || edges[edge].Link == -2)
 312                 {
 313                         ++edge;
 314                         continue;
 315                 }
 316
 317                 uint    startedge = edge;
 318                 uint    stopedge;
 319
 320                 for (stopedge=edge; stopedge+1<edges.size() && edges[stopedge+1].Link == edges[startedge].Link; ++stopedge)
 321                         ;
 322
 323                 edge = stopedge+1;
 324
 325                 CVector start = edges[startedge].Start, stop = edges[stopedge+1].Start;
 326                 bool    found = false;
 327
 328                 for (ch=0; ch<bchains.size() && !found; ++ch)
 329                 {
 330                         // get the border chain.
 331                         //const CChain  &chain = chains[bchains[ch]];
 332
 333                         const CVector   &cstart = lr.getStartVector(bchains[ch]),
 334                                                         &cstop = lr.getStopVector(bchains[ch]);
 335
 336                         float d = (start-cstart).norm()+(stop-cstop).norm();
 337                         if (d < 1.0e-1f)
 338                         {
 339                                 found = true;
 340                                 break;
 341                         }
 342                 }
 343
 344                 // create a link
 345                 CExteriorMesh::CLink    link;
 346
 347                 if (!found)
 348                 {
 349                         nlwarning("in linkInteriorToExterior():");
 350                         nlwarning("couldn't find any link to the exterior edge %d-%d!!", startedge, stopedge);
 351                 }
 352                 else
 353                 {
 354                         // set it up to point on the chain and surface
 355                         link.BorderChainId = ch;
 356                         link.ChainId = bchains[ch];
 357                         link.SurfaceId = (uint16)chains[link.ChainId].getLeft();
 358                 }
 359
 360                 // enlarge the links
 361                 if (edges[startedge].Link >= (sint)links.size())
 362                         links.resize(edges[startedge].Link+1);
 363
 364                 // if the link already exists, warning
 365                 if (links[edges[startedge].Link].BorderChainId != 0xFFFF ||
 366                         links[edges[startedge].Link].ChainId != 0xFFFF ||
 367                         links[edges[startedge].Link].SurfaceId != 0xFFFF)
 368                 {
 369                         nlwarning("in linkInteriorToExterior():");
 370                         nlwarning("link %d already set!!", edges[startedge].Link);
 371                 }
 372
 373                 // setup the link
 374                 links[edges[startedge].Link] = link;
 375         }
 376
 377 //      em.setEdges(edges);
 378         em.setLinks(links);
 379         lr.setExteriorMesh(em);
 380 }
 381
 382
 383
 384
 385
 386 //
 387 void    computeRetriever(CCollisionMeshBuild &cmb, CLocalRetriever &lr, CVector &translation, bool useCmbTrivialTranslation)
 388 {
 389         // set the retriever
 390         lr.setType(CLocalRetriever::Interior);
 391
 392         // if should use the own cmb bbox, then compute it
 393         if (useCmbTrivialTranslation)
 394         {
 395                 translation = cmb.computeTrivialTranslation();
 396                 // snap the translation vector to a meter wide grid
 397                 translation.x = (float)ceil(translation.x);
 398                 translation.y = (float)ceil(translation.y);
 399                 translation.z = 0.0f;
 400         }
 401
 402         uint    i, j;
 403
 404         for (i=0; i<cmb.Faces.size(); ++i)
 405         {
 406                 CVector         normal = ((cmb.Vertices[cmb.Faces[i].V[1]]-cmb.Vertices[cmb.Faces[i].V[0]])^(cmb.Vertices[cmb.Faces[i].V[2]]-cmb.Vertices[cmb.Faces[i].V[0]])).normed();
 407
 408                 if (normal.z < 0.0f)
 409                 {
 410                         nlwarning("Face %d in cmb (%s) has negative normal! -- face is flipped", i, cmb.Faces[i].Surface == CCollisionFace::InteriorSurfaceFirst ? "interior" : "exterior");
 411 /*
 412                         std::swap(cmb.Faces[i].V[1], cmb.Faces[i].V[2]);
 413                         std::swap(cmb.Faces[i].Visibility[1], cmb.Faces[i].Visibility[2]);
 414 */
 415                 }
 416         }
 417
 418         // first link faces
 419 /*
 420         linkMesh(cmb, false);
 421         linkMesh(cmb, true);
 422 */
 423         vector<string>  errors;
 424
 425         cmb.link(false, errors);
 426         cmb.link(true, errors);
 427
 428         if (!errors.empty())
 429         {
 430                 nlwarning("Edge issues reported !!");
 431                 uint    i;
 432                 for (i=0; i<errors.size(); ++i)
 433                         nlwarning("%s", errors[i].c_str());
 434                 nlerror("Can't continue.");
 435         }
 436
 437         // translate the meshbuild to the local axis
 438         cmb.translate(translation);
 439
 440         // find the exterior mesh border
 441         CExteriorMesh   extMesh;
 442         buildExteriorMesh(cmb, extMesh);
 443         lr.setExteriorMesh(extMesh);
 444
 445         // build the surfaces in the local retriever
 446         buildSurfaces(cmb, lr);
 447
 448         // create the snapping faces and vertices
 449         // after the build surfaces because the InternalSurfaceId is filled within buildSurfaces()...
 450         buildSnapping(cmb, lr);
 451
 452         //
 453         lr.computeLoopsAndTips();
 454
 455         lr.findBorderChains();
 456         lr.updateChainIds();
 457         lr.computeTopologies();
 458
 459         lr.unify();
 460
 461         lr.computeCollisionChainQuad();
 462 /*
 463         //
 464         for (i=0; i<lr.getSurfaces().size(); ++i)
 465                 lr.dumpSurface(i);
 466 */
 467         //
 468         linkExteriorToInterior(lr);
 469
 470         // compute the bbox of the retriever
 471         CAABBox bbox;
 472         bool    first = true;
 473
 474         for (i=0; i<extMesh.getEdges().size(); ++i)
 475                 if (!first)
 476                         bbox.extend(extMesh.getEdge(i).Start);
 477                 else
 478                         bbox.setCenter(extMesh.getEdge(i).Start), first=false;
 479
 480         for (i=0; i<lr.getOrderedChains().size(); ++i)
 481                 for (j=0; j<lr.getOrderedChain(i).getVertices().size(); ++j)
 482                         if (!first)
 483                                 bbox.extend(lr.getOrderedChain(i)[j].unpack3f());
 484                         else
 485                                 bbox.setCenter(lr.getOrderedChain(i)[j].unpack3f()), first=false;
 486
 487         CVector bboxhs = bbox.getHalfSize();
 488         bboxhs.z = 10000.0f;
 489         bbox.setHalfSize(bboxhs);
 490
 491         lr.setBBox(bbox);
 492 }