nel/tools/pacs/build_rbank/surface_splitter.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "surface_splitter.h"
  18
  19 using namespace std;
  20 using namespace NLMISC;
  21 using namespace NLPACS;
  22
  23 // -----------------------
  24 //
  25
  26 // Constructor
  27 CSurfaceSplitter::CSurfaceSplitter()
  28 {
  29 }
  30
  31
  32 //
  33 void    CSurfaceSplitter::build(CLocalRetriever &lr)
  34 {
  35         nlinfo("--- Build SurfaceSplitter...");
  36         nlinfo("------------------------------------------");
  37         uint    i;
  38
  39         initEdgeGrid();
  40
  41         _NumChains = 0;
  42         _NumSurfaces = 0;
  43         _NumTips = 0;
  44
  45         for (i=0; i<lr.getChains().size(); ++i)
  46                 buildChain(lr, i);
  47
  48         for (i=0; i<lr.getSurfaces().size(); ++i)
  49                 buildSurface(lr, i);
  50
  51         nlinfo("converted %d chains & %d surfaces", lr.getChains().size(), lr.getSurfaces().size());
  52         _NumSurfaces = (uint)lr.getSurfaces().size();
  53         _NumChains = (uint)lr.getChains().size();
  54
  55         //splitChains();
  56
  57         dump();
  58
  59         nlinfo("------------------------------------------");
  60 }
  61
  62 //
  63 void    CSurfaceSplitter::buildChain(CLocalRetriever &lr, uint chain)
  64 {
  65         const NLPACS::CChain    &pacsChain = lr.getChain(chain);
  66
  67         CSurfaceId                              left = pacsChain.getLeft() >= 0 ? CSurfaceId(0, (uint16)pacsChain.getLeft()) : CSurfaceId();
  68         CSurfaceId                              right = pacsChain.getRight() >= 0 ? CSurfaceId(0, (uint16)pacsChain.getRight()) : CSurfaceId();
  69         vector<CVector2s64>             vertices;
  70
  71         uint    i;
  72         // walk through all subchains
  73         for (i=0; i<pacsChain.getSubChains().size(); ++i)
  74         {
  75                 uint    ochain = pacsChain.getSubChain(i);
  76                 const NLPACS::COrderedChain     &pacsOChain = lr.getOrderedChain(ochain);
  77
  78                 sint    j;
  79                 // walk through subchain, forward or backward
  80                 if (pacsOChain.isForward())
  81                 {
  82                         for (j=0; j<(sint)pacsOChain.getVertices().size()-1; ++j)
  83                                 vertices.push_back(CVector2s64(pacsOChain[j]));
  84                 }
  85                 else
  86                 {
  87                         for (j=(sint)pacsOChain.getVertices().size()-1; j>0; --j)
  88                                 vertices.push_back(CVector2s64(pacsOChain[j]));
  89                 }
  90
  91                 // add final chain point
  92                 if (i == pacsChain.getSubChains().size()-1)
  93                         vertices.push_back(CVector2s64(pacsOChain[j]));
  94         }
  95
  96         addChain(left,right, vertices);
  97 }
  98
  99 //
 100 void    CSurfaceSplitter::buildSurface(CLocalRetriever &lr, uint surface)
 101 {
 102         const NLPACS::CRetrievableSurface       &pacsSurface = lr.getSurface(surface);
 103         CSurface                                                        newSurface;
 104
 105         newSurface.Id = CSurfaceId(0, surface);
 106
 107         uint    i;
 108         // walk through all loops
 109         for (i=0; i<pacsSurface.getLoops().size(); ++i)
 110         {
 111                 const NLPACS::CRetrievableSurface::TLoop        &pacsLoop = pacsSurface.getLoop(i);
 112                 newSurface.Loops.push_back(CSurfaceSplitter::CLoop());
 113                 newSurface.Loops.back().Surface = newSurface.Id;
 114
 115                 uint    j;
 116                 // walk through loop
 117                 for (j=0; j<pacsLoop.size(); ++j)
 118                 {
 119                         uint    chainIndex = pacsLoop[j];
 120                         uint    chain = pacsSurface.getChain(chainIndex).Chain;
 121
 122                         newSurface.Loops.back().Chains.push_back(CChainId(chain));
 123                 }
 124         }
 125
 126         _Surfaces.insert(make_pair(newSurface.Id, newSurface));
 127 }
 128
 129
 130
 131 //
 132 void    CSurfaceSplitter::initEdgeGrid()
 133 {
 134         _Edges.create(256, 2.0f);
 135 }
 136
 137
 138 //
 139 void    CSurfaceSplitter::splitChains()
 140 {
 141         nlinfo("Split chains...");
 142
 143         uint    numInters = 0;
 144         uint    i;
 145
 146         for (i=0; i<_NumChains; ++i)
 147         {
 148                 TChainMap::iterator     it = _Chains.find(CChainId(i));
 149                 if (it != _Chains.end())
 150                         splitChain(it, numInters);
 151         }
 152
 153         nlinfo("%d intersections found", numInters);
 154 }
 155
 156 //
 157 void    CSurfaceSplitter::splitChain(TChainMap::iterator it, uint &numInters)
 158 {
 159         CChain  &chain = (*it).second;
 160
 161         if (chain.DontSplit)
 162                 return;
 163
 164         uint    edge;
 165         // for each edge of the chain, test for other edges collision
 166         for (edge=0; edge<chain.Vertices.size()-1; ++edge)
 167         {
 168                 CVector p0 = chain.Vertices[edge].asVector();
 169                 CVector p1 = chain.Vertices[edge+1].asVector();
 170                 CVector pmin, pmax;
 171                 pmin.minof(p0, p1);
 172                 pmax.maxof(p0, p1);
 173
 174                 _Edges.select(pmin, pmax);
 175
 176                 CFixed64        closerDist(10.0);
 177                 bool            collisionFound = false;
 178                 CEdgeId         collidingEdge;
 179                 CVector2s64     collision;
 180
 181                 TEdgeGrid::CIterator    it;
 182                 for (it=_Edges.begin(); it!=_Edges.end(); ++it)
 183                 {
 184                         CEdgeId         iedge = *it;
 185
 186                         //
 187                         if (chain.Id == iedge.Chain && (edge == iedge.Edge || edge+1 == iedge.Edge || edge-1 == iedge.Edge))
 188                                 continue;
 189
 190                         CChain          *ichain = getChain(iedge.Chain);
 191
 192                         if (ichain == NULL)
 193                         {
 194                                 nlwarning("Couldn't find referenced chain %d", iedge.Chain.Id);
 195                                 continue;
 196                         }
 197
 198                         if (ichain->DontSplit)
 199                                 continue;
 200
 201                         CVector2s64     inters;
 202                         CFixed64        ndist;
 203
 204                         if (intersect(chain.Vertices[edge], chain.Vertices[edge+1], ichain->Vertices[iedge.Edge], ichain->Vertices[iedge.Edge+1], inters, ndist))
 205                         {
 206                                 if (inters != chain.Vertices[edge+1] || edge != chain.Vertices.size()-2)
 207                                 {
 208                                         ++numInters;
 209                                         nlinfo("Intersection: %d:%d[%.3f,%.3f-%.3f,%.3f]-%d:%d[%.3f,%.3f-%.3f,%.3f] : [%.3f,%.3f]", chain.Id.Id, edge, p0.x, p0.y, p1.x, p1.y, iedge.Chain.Id, iedge.Edge, ichain->Vertices[iedge.Edge].asVector().x, ichain->Vertices[iedge.Edge].asVector().y, ichain->Vertices[iedge.Edge+1].asVector().x, ichain->Vertices[iedge.Edge+1].asVector().y, inters.asVector().x, inters.asVector().y);
 210
 211                                         if (closerDist > ndist)
 212                                         {
 213                                                 collisionFound = true;
 214                                                 collidingEdge = iedge;
 215                                                 collision = inters;
 216                                         }
 217                                 }
 218                                 else
 219                                 {
 220                                         nlinfo("Intersection: %d:%d[%.3f,%.3f-%.3f,%.3f]-%d:%d[%.3f,%.3f-%.3f,%.3f] : [%.3f,%.3f] -- SKIPPED", chain.Id.Id, edge, p0.x, p0.y, p1.x, p1.y, iedge.Chain.Id, iedge.Edge, ichain->Vertices[iedge.Edge].asVector().x, ichain->Vertices[iedge.Edge].asVector().y, ichain->Vertices[iedge.Edge+1].asVector().x, ichain->Vertices[iedge.Edge+1].asVector().y, inters.asVector().x, inters.asVector().y);
 221                                 }
 222                         }
 223                 }
 224
 225                 // split chain
 226                 if (collisionFound)
 227                 {
 228                         if (chain.Id == collidingEdge.Chain)
 229                         {
 230                                 // self colliding chain
 231
 232                                 // check order
 233                                 //nlassert(edge >= 0); // always true for unsigned
 234                                 nlassert(edge < collidingEdge.Edge);
 235                                 nlassert(collidingEdge.Edge < chain.Vertices.size()-1);
 236
 237                                 // must split the chain in 3 parts
 238                                 uint                            e;
 239                                 vector<CVector2s64>     begin;
 240                                 vector<CVector2s64>     middle;
 241                                 vector<CVector2s64>     end;
 242                                 vector<CChainId>        v;
 243                                 CChainId                        beginId;
 244                                 CChainId                        middleId;
 245                                 CChainId                        endId;
 246
 247                                 for (e=0; e<=edge; ++e)
 248                                         begin.push_back(chain.Vertices[e]);
 249
 250                                 begin.push_back(collision);
 251
 252                                 if (collision != chain.Vertices[e])
 253                                         middle.push_back(collision);
 254
 255                                 for (; e<=collidingEdge.Edge; ++e)
 256                                         middle.push_back(chain.Vertices[e]);
 257
 258                                 middle.push_back(collision);
 259
 260                                 if (collision != chain.Vertices[e])
 261                                         end.push_back(collision);
 262
 263                                 for (; e<chain.Vertices.size(); ++e)
 264                                         end.push_back(chain.Vertices[e]);
 265
 266                                 beginId = addChain(chain.Left, chain.Right, begin, true);
 267                                 middleId = addChain(chain.Left, chain.Right, middle);
 268                                 endId = addChain(chain.Left, chain.Right, end);
 269
 270                                 v.push_back(beginId);
 271                                 v.push_back(middleId);
 272                                 v.push_back(endId);
 273
 274                                 replaceChain(chain.Id, v);
 275                         }
 276                         else
 277                         {
 278                                 //nlassert(edge >= 0); // always true for unsigned
 279                                 nlassert(edge < chain.Vertices.size()-1);
 280
 281                                 // split the chain
 282                                 uint                            e;
 283                                 vector<CVector2s64>     begin;
 284                                 vector<CVector2s64>     end;
 285                                 vector<CChainId>        v;
 286                                 CChainId                        beginId;
 287                                 CChainId                        endId;
 288
 289                                 // split the first chain
 290                                 for (e=0; e<=edge; ++e)
 291                                         begin.push_back(chain.Vertices[e]);
 292
 293                                 begin.push_back(collision);
 294
 295                                 if (collision != chain.Vertices[e])
 296                                         end.push_back(collision);
 297
 298                                 for (; e<chain.Vertices.size(); ++e)
 299                                         end.push_back(chain.Vertices[e]);
 300
 301                                 beginId = addChain(chain.Left, chain.Right, begin, true);
 302                                 endId = addChain(chain.Left, chain.Right, end);
 303
 304                                 v.push_back(beginId);
 305                                 v.push_back(endId);
 306
 307                                 replaceChain(chain.Id, v);
 308
 309                                 // reset for second chain
 310                                 begin.clear();
 311                                 end.clear();
 312                                 v.clear();
 313
 314                                 // split the second chain
 315                                 CChain  *collide = getChain(collidingEdge.Chain);
 316
 317                                 for (e=0; e<=collidingEdge.Edge; ++e)
 318                                         begin.push_back(collide->Vertices[e]);
 319
 320                                 begin.push_back(collision);
 321
 322                                 if (collision != collide->Vertices[e])
 323                                         end.push_back(collision);
 324
 325                                 for (; e<collide->Vertices.size(); ++e)
 326                                         end.push_back(collide->Vertices[e]);
 327
 328                                 beginId = addChain(collide->Left, collide->Right, begin);
 329                                 endId = addChain(collide->Left, collide->Right, end);
 330
 331                                 v.push_back(beginId);
 332                                 v.push_back(endId);
 333
 334                                 replaceChain(collide->Id, v);
 335                         }
 336
 337                         return;
 338                 }
 339         }
 340 }
 341
 342 //
 343 bool    CSurfaceSplitter::intersect(const CVector2s64 &v0, const CVector2s64 &v1,
 344                                                                         const CVector2s64 &c0, const CVector2s64 &c1,
 345                                                                         CVector2s64 &intersect,
 346                                                                         CFixed64 &ndist)
 347 {
 348         if (v0 == c0 || v0 == c1)
 349                 return false;
 350
 351         if (v1 == c0 || v1 == c1)
 352         {
 353                 intersect = v1;
 354                 ndist = CFixed64(1.0);
 355                 return true;
 356         }
 357
 358         CVector2s64             nnc(c0.y-c1.y, c1.x-c0.x),
 359                                         nnv(v0.y-v1.y, v1.x-v0.x);
 360
 361         CFixed64                dv = (v1-v0)*nnc;
 362
 363         // vectors are colinears ?
 364         if ((sint64)dv == 0)
 365                 return false;
 366
 367         CFixed64                nv = (c0-v0)*nnc;
 368
 369         if ((sint64)dv < 0)
 370                 dv=-dv, nv=-nv;
 371         // intersection outside main edge ? (or at first point ?)
 372         if ((sint64)nv<=0 || nv>dv)
 373                 return false;
 374
 375         CFixed64                dc = (c1-c0)*(c1-c0);
 376         // second edge null ?
 377         if ((sint64)dc == 0)
 378                 return false;
 379
 380         CFixed64                lv = nv/dv;
 381
 382         if ((sint64)lv == 0)
 383                 return false;
 384
 385         CFixed64                nc = (v0-c0 + (v1-v0)*lv)*(c1-c0);
 386         // intersection outside colliding edge ?
 387         if ((sint64)nc<0 || nc>dc)
 388                 return false;
 389
 390         // treat each singular case
 391         if (nv == dv)
 392                 intersect = v1;
 393         else if ((sint64)nc == 0)
 394                 intersect = c0;
 395         else if (nc == dc)
 396                 intersect = c1;
 397         else
 398                 // compute intersecting point
 399                 intersect = v0 + (v1-v0)*lv;
 400
 401         ndist = lv;
 402
 403         return true;
 404 }
 405
 406
 407
 408 //
 409 CSurfaceSplitter::CChainId      CSurfaceSplitter::addChain(const CSurfaceId &left, const CSurfaceId &right, const vector<CVector2s64> &points, bool dontSplit)
 410 {
 411         pair<TChainMap::iterator, bool> res = _Chains.insert(make_pair(CChainId(_NumChains++), CChain()));
 412
 413         CChain  &chain = (*(res.first)).second;
 414
 415         chain.Id = (*(res.first)).first;
 416         chain.Left = left;
 417         chain.Right = right;
 418
 419         uint    i;
 420         for (i=0; i<points.size()-1; ++i)
 421         {
 422                 if (points[i] == points[i+1])
 423                 {
 424                         nlwarning("--- !! points are together !! ---");
 425                         nlstop;
 426                 }
 427         }
 428
 429         chain.Vertices = points;
 430         chain.DontSplit = dontSplit;
 431
 432         uint    edge;
 433         for (edge=0; edge<chain.Vertices.size()-1; ++edge)
 434         {
 435                 CVector p0 = chain.Vertices[edge].asVector();
 436                 CVector p1 = chain.Vertices[edge+1].asVector();
 437
 438                 p0.z = -100.0f;
 439                 p1.z = +100.0f;
 440
 441                 CVector pmin, pmax;
 442                 pmin.minof(p0, p1);
 443                 pmax.maxof(p0, p1);
 444
 445                 chain.Iterators.push_back(_Edges.insert(pmin, pmax, CEdgeId(chain.Id, edge)));
 446         }
 447
 448         return chain.Id;
 449 }
 450
 451 //
 452 void    CSurfaceSplitter::removeChain(CChainId chainId)
 453 {
 454         // get chain it
 455         TChainMap::iterator     it = _Chains.find(chainId);
 456
 457         if (it == _Chains.end())
 458                 return;
 459
 460         CChain  &chain = (*it).second;
 461
 462         CSurface        *surf;
 463
 464         if ((surf = getSurface(chain.Left)))
 465                 surf->removeChain(chainId);
 466
 467         if ((surf = getSurface(chain.Right)))
 468                 surf->removeChain(chainId);
 469 }
 470
 471 //
 472 void    CSurfaceSplitter::replaceChain(CChainId chainId, const vector<CChainId> &chains)
 473 {
 474         // get chain it
 475         TChainMap::iterator     it = _Chains.find(chainId);
 476
 477         if ((it == _Chains.end()))
 478                 return;
 479
 480         CChain  &chain = (*it).second;
 481
 482         CSurface        *surf;
 483
 484         nlinfo("-- Replace --");
 485         dumpChain(chainId);
 486         nlinfo("-- By --");
 487         uint    c;
 488         for (c=0; c<chains.size(); ++c)
 489                 dumpChain(chains[c]);
 490         nlinfo("-- End Replace --");
 491
 492         if ((surf = getSurface(chain.Left)))
 493         {
 494                 uint    loop;
 495                 for (loop=0; loop<surf->Loops.size(); ++loop)
 496                 {
 497                         CLoop   &ploop = surf->Loops[loop];
 498                         vector<CChainId>::iterator      it;
 499                         for (it=ploop.Chains.begin(); it!=ploop.Chains.end(); ++it)
 500                         {
 501                                 if (*it == chainId)
 502                                 {
 503                                         it = ploop.Chains.erase(it);
 504                                         sint    i;
 505                                         for (i=(sint)chains.size()-1; i>=0; --i)
 506                                         {
 507                                                 it = ploop.Chains.insert(it, chains[i]);
 508                                         }
 509                                 }
 510                         }
 511                 }
 512         }
 513
 514         if ((surf = getSurface(chain.Right)))
 515         {
 516                 uint    loop;
 517                 for (loop=0; loop<surf->Loops.size(); ++loop)
 518                 {
 519                         CLoop   &ploop = surf->Loops[loop];
 520                         vector<CChainId>::iterator      it;
 521                         for (it=ploop.Chains.begin(); it!=ploop.Chains.end(); ++it)
 522                         {
 523                                 if (*it == chainId)
 524                                 {
 525                                         it = ploop.Chains.erase(it);
 526                                         uint    i;
 527                                         for (i=0; i<chains.size(); ++i)
 528                                         {
 529                                                 it = ploop.Chains.insert(it, chains[i]);
 530                                         }
 531                                 }
 532                         }
 533                 }
 534         }
 535
 536         uint    i;
 537         for (i=0; i<chain.Iterators.size(); ++i)
 538                 _Edges.erase(chain.Iterators[i]);
 539
 540         _Chains.erase(it);
 541 }