nel/tools/pacs/build_rbank/build_surf.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) 2010-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 <math.h>
  21 #include <float.h>
  22
  23 #include "nel/misc/types_nl.h"
  24 #include "nel/misc/debug.h"
  25 #include "nel/misc/path.h"
  26 #include "nel/misc/file.h"
  27
  28 #include "nel/misc/plane.h"
  29 #include "nel/misc/triangle.h"
  30 #include "nel/misc/polygon.h"
  31
  32 #include "nel/3d/landscape.h"
  33 #include "nel/3d/zone.h"
  34 #include "nel/3d/mesh.h"
  35 #include "nel/3d/quad_grid.h"
  36
  37 #include "nel/pacs/vector_2s.h"
  38
  39 #include "build_surf.h"
  40
  41 #include <deque>
  42
  43 using namespace std;
  44 using namespace NLMISC;
  45 using namespace NL3D;
  46
  47
  48 // Misc functions...
  49
  50 uint16  getZoneIdByPos(CVector &pos)
  51 {
  52         uint            x, y;
  53         const float     zdim = 160.0f;
  54
  55         x = (uint)(pos.x/zdim);
  56         y = (uint)(-pos.y/zdim);
  57
  58         return x+y*256;
  59 }
  60
  61 string getZoneNameById(uint16 id)
  62 {
  63         uint    x = id%256;
  64         uint    y = id/256;
  65
  66         char ych[32];
  67         sprintf(ych,"%d_%c%c", y+1, 'A'+x/26, 'A'+x%26);
  68         return string(ych);
  69 }
  70
  71 uint16 getZoneIdByName(string &name)
  72 {
  73         string upperName = strupr (name);
  74         sint            y = 0, x = 0;
  75         const char      *str = upperName.c_str();
  76
  77         while (*str != '_')
  78                 y = y*10 + *(str++)-'0';
  79
  80         ++str;
  81
  82         x = (str[0]-'A')*26+(str[1]-'A');
  83
  84         return (y-1)*256+x;
  85 }
  86
  87 CAABBox getZoneBBoxById(uint16 id)
  88 {
  89         CAABBox         bbox;
  90         uint            x, y;
  91         const float     zdim = 160.0f;
  92
  93         x = id%256;
  94         y = id/256;
  95         bbox.setMinMax(CVector(zdim*x,          -zdim*(y+1),    -10000.0f),
  96                                    CVector(zdim*(x+1),  -zdim*y,                +10000.0f));
  97
  98
  99         return bbox;
 100 }
 101
 102
 103 bool    relativeEquals(CVector &a, CVector &b, float epsilon)
 104 {
 105         float   n = (a-b).norm();
 106         float   r = a.norm();
 107
 108
 109         return (n/r <= epsilon);
 110 }
 111
 112 bool    absoluteEquals(CVector &a, CVector &b, float epsilon)
 113 {
 114         float   n = (a-b).norm();
 115         return n <= epsilon;
 116 }
 117
 118 inline CVector  vmin(const CVector &a, const CVector &b, const CVector &c)
 119 {
 120         return CVector(std::min(a.x, std::min(b.x, c.x)),
 121                                    std::min(a.y, std::min(b.y, c.y)),
 122                                    std::min(a.z, std::min(b.z, c.z)));
 123 }
 124
 125 inline CVector  vmax(const CVector &a, const CVector &b, const CVector &c)
 126 {
 127         return CVector(std::max(a.x, std::max(b.x, c.x)),
 128                                    std::max(a.y, std::max(b.y, c.y)),
 129                                    std::max(a.z, std::max(b.z, c.z)));
 130 }
 131
 132 inline CVector  vmin(const CVector &a, const CVector &b)
 133 {
 134         return CVector(std::min(a.x, b.x),
 135                                    std::min(a.y, b.y),
 136                                    std::min(a.z, b.z));
 137 }
 138
 139 inline CVector  vmax(const CVector &a, const CVector &b)
 140 {
 141         return CVector(std::max(a.x, b.x),
 142                                    std::max(a.y, b.y),
 143                                    std::max(a.z, b.z));
 144 }
 145
 146 static sint64   float2Fixed(float f)
 147 {
 148         return (sint64)(floor(f*NLPACS::Vector2sAccuracy));
 149 }
 150
 151 static float    fixed2Float(sint64 s)
 152 {
 153         return ((float)s)/NLPACS::Vector2sAccuracy;
 154 }
 155
 156 static void             snapAccuracyBit(float &f)
 157 {
 158         f = fixed2Float(float2Fixed(f));
 159 }
 160
 161 static void             snapAccuracyBit(CVector &v)
 162 {
 163         snapAccuracyBit(v.x);
 164         snapAccuracyBit(v.y);
 165         snapAccuracyBit(v.z);
 166 }
 167
 168 static CAABBox  getSnappedBBox(CVector v0, CVector v1, CVector v2, const CAABBox &bbox)
 169 {
 170         snapAccuracyBit(v0);
 171         snapAccuracyBit(v1);
 172         snapAccuracyBit(v2);
 173
 174         CAABBox box;
 175
 176         box.setCenter(v0);
 177         box.extend(v1);
 178         box.extend(v2);
 179
 180         return box;
 181 }
 182
 183 static float    alg2dArea(const CVector &v0, const CVector &v1, const CVector &v2)
 184 {
 185         float   ux = v1.x-v0.x,
 186                         uy = v1.y-v0.y,
 187                         vx = v2.x-v0.x,
 188                         vy = v2.y-v0.y;
 189
 190         return ux*vy - uy*vx;
 191 }
 192
 193 static double   alg2dArea(const CVectorD &v0, const CVectorD &v1, const CVectorD &v2)
 194 {
 195         double  ux = v1.x-v0.x,
 196                         uy = v1.y-v0.y,
 197                         vx = v2.x-v0.x,
 198                         vy = v2.y-v0.y;
 199
 200         return ux*vy - uy*vx;
 201 }
 202
 203 template<class A>
 204 class CHashPtr
 205 {
 206 public:
 207         enum { bucket_size = 4, min_buckets = 8, };
 208
 209         typedef A       *ptrA;
 210         size_t  operator() (const ptrA &a) const
 211         {
 212                 return ((uintptr_t)a)/sizeof(A);
 213         }
 214
 215         bool operator() (const ptrA &a, const ptrA &b) const
 216         {
 217                 return (uintptr_t)a < (uintptr_t)b;
 218         }
 219 };
 220
 221 bool    isInside(const CPolygon &poly, const NLPACS::CSurfElement &elem)
 222 {
 223         uint    i, j;
 224
 225         if (poly.getNumVertices() <= 2)
 226                 return false;
 227
 228         CVector         pnorm = (poly.Vertices[0]-poly.Vertices[1])^(poly.Vertices[2]-poly.Vertices[1]);
 229         pnorm.normalize();
 230
 231         for (i=0; i<3; ++i)
 232         {
 233                 const CVector   &v = (*elem.Vertices)[elem.Tri[i]];
 234                 bool                    inside = true;
 235
 236                 for (j=0; j<poly.Vertices.size(); ++j)
 237                 {
 238                         const CVector   &v0 = poly.Vertices[j],
 239                                                         &v1 = (j == poly.Vertices.size()-1) ? poly.Vertices[0] : poly.Vertices[j+1];
 240
 241                         if ((pnorm^(v1-v0)) * (v-v1) > 0.0f)
 242                         {
 243                                 inside = false;
 244                                 break;
 245                         }
 246                 }
 247
 248                 if (inside)
 249                         return true;
 250         }
 251         return false;
 252 }
 253
 254
 255 /*
 256  */
 257 class CAABBoxPred
 258 {
 259 public:
 260         bool    operator () (const CAABBox &a, const CAABBox &b) const
 261         {
 262                 return a.getCenter().z < b.getCenter().z;
 263         }
 264 };
 265
 266
 267
 268
 269
 270
 271
 272
 273 /*
 274  * CSurfElement methods
 275  *
 276  */
 277
 278
 279 void    NLPACS::CSurfElement::computeQuantas(CZoneTessellation *zoneTessel)
 280 {
 281         CVector         v0 = (*Vertices)[Tri[0]],
 282                                 v1 = (*Vertices)[Tri[1]],
 283                                 v2 = (*Vertices)[Tri[2]];
 284
 285         CVector         nv0 = v0,
 286                                 nv1 = v1,
 287                                 nv2 = v2;
 288
 289         nv0.z = 0.0f;
 290         nv1.z = 0.0f;
 291         nv2.z = 0.0f;
 292
 293         CVector n = (nv1-nv0) ^ (nv2-nv0);
 294
 295         double  hmin = std::min(v0.z, std::min(v1.z, v2.z));
 296         //QuantHeight = ((uint8)(floor((v0.z+v1.z+v2.z)/6.0f)))%255;
 297         QuantHeight = ((uint8)floor(hmin/2.0))%255;
 298
 299         Area = 0.5f*n.norm();
 300
 301         IsValid = (Normal.z > 0.707f);
 302
 303         uint8   bits0 = PrimChecker.get((uint)v0.x, (uint)v0.y);
 304         uint8   bits1 = PrimChecker.get((uint)v1.x, (uint)v1.y);
 305         uint8   bits2 = PrimChecker.get((uint)v2.x, (uint)v2.y);
 306
 307         uint16  ws0 = PrimChecker.index((uint)v0.x, (uint)v0.y);
 308         uint16  ws1 = PrimChecker.index((uint)v1.x, (uint)v1.y);
 309         uint16  ws2 = PrimChecker.index((uint)v2.x, (uint)v2.y);
 310
 311         uint8   bits = bits0|bits1|bits2;
 312
 313         if (bits & CPrimChecker::Include)
 314         {
 315                 IsValid = true;
 316         }
 317
 318         if (bits & CPrimChecker::Exclude)
 319         {
 320                 ForceInvalid = true;
 321                 IsValid = false;
 322         }
 323
 324         if (bits & CPrimChecker::ClusterHint && IsValid)
 325         {
 326                 ClusterHint = true;
 327         }
 328
 329 //      if ((bits & CPrimChecker::Cliff) && (bits & CPrimChecker::Water))
 330 //              IsValid = false;
 331
 332         if (Normal.z <= 0.30f)
 333         {
 334                 ForceInvalid = true;
 335                 IsValid = false;
 336         }
 337         else if ((bits & CPrimChecker::Water) != 0 && !ForceInvalid)
 338         {
 339                 bool    w0 = ((bits0&CPrimChecker::Water) != 0);
 340                 bool    w1 = ((bits1&CPrimChecker::Water) != 0);
 341                 bool    w2 = ((bits2&CPrimChecker::Water) != 0);
 342
 343                 uint    ws = 0xff;
 344
 345                 if ((w0 && w1 && ws0 == ws1) || (w0 && w2 && ws0 == ws2))
 346                         ws = ws0;
 347                 else if (w1 && w2 && ws1 == ws2)
 348                         ws = ws1;
 349                 else if (w0)
 350                         ws = ws0;
 351                 else if (w1)
 352                         ws = ws1;
 353                 else if (w2)
 354                         ws = ws2;
 355                 else
 356                 {
 357                         nlwarning("No WaterShape found for element %d, whereas water detected...", ElemId);
 358                 }
 359
 360                 WaterShape = ws;
 361
 362                 bool    exists;
 363                 float   wh = PrimChecker.waterHeight(ws, exists);
 364                 if (exists && ((*Vertices)[Tri[0]].z < wh || (*Vertices)[Tri[1]].z < wh || (*Vertices)[Tri[2]].z < wh))
 365                 {
 366                         if (bits & CPrimChecker::Cliff)
 367                         {
 368                                 ForceInvalid = true;
 369                                 IsValid = false;
 370                                 return;
 371                         }
 372
 373                         IsValid = true;
 374                         WaterShape = ws;
 375                         IsUnderWater = true;
 376                 }
 377 /*
 378                 else
 379                 {
 380                         ForceInvalid = true;
 381                         IsValid = false;
 382                 }
 383 */
 384         }
 385
 386         if (ForceInvalid)
 387                 IsValid = false;
 388 }
 389
 390 CAABBox NLPACS::CSurfElement::getBBox() const
 391 {
 392         CAABBox box;
 393         box.setCenter((*Vertices)[Tri[0]]);
 394         box.extend((*Vertices)[Tri[1]]);
 395         box.extend((*Vertices)[Tri[2]]);
 396         return box;
 397 }
 398
 399 /*
 400  * CComputableSurfaceBorder methods implementation
 401  *
 402  */
 403
 404 void    NLPACS::CComputableSurfaceBorder::dump()
 405 {
 406         sint    i;
 407
 408         nldebug("dump border between %d and %d", Left, Right);
 409         for (i=0; i<(sint)Vertices.size(); ++i)
 410         {
 411                 nldebug("  v[%d]={%g,%g,%g}", i, Vertices[i].x, Vertices[i].y, Vertices[i].z);
 412         }
 413 }
 414
 415 void    NLPACS::CComputableSurfaceBorder::smooth(float val)
 416 {
 417         float                                           minArea;
 418         vector<CVector>::iterator       it, minIt;
 419         uint                                            i;
 420
 421         uint                                            before, after;
 422
 423         bool                                            allowMoveLeft = (Left != -1);
 424         bool                                            allowMoveRight = (Right != -1);
 425
 426         // filtering passes
 427         uint    numPass = 3;
 428         for (; numPass>0 && Vertices.size()>3; --numPass)
 429         {
 430                 CVector previous = Vertices[0];
 431                 for (i=1; i<Vertices.size()-1; ++i)
 432                 {
 433                         CVector newVert = (Vertices[i]*2.0+previous+Vertices[i+1])/4.0f;
 434
 435                         if (!allowMoveLeft || !allowMoveRight)
 436                         {
 437                                 float   area1 = alg2dArea(previous, Vertices[i], Vertices[i+1]);
 438                                 float   area2 = alg2dArea(previous, newVert, Vertices[i+1]);
 439
 440                                 previous = Vertices[i];
 441
 442                                 if ((!allowMoveLeft && area2 > area1) || (!allowMoveRight && area2 < area1))
 443                                         Vertices[i] = newVert;
 444                         }
 445                         else
 446                         {
 447                                 previous = Vertices[i];
 448                                 Vertices[i] = newVert;
 449                         }
 450                 }
 451         }
 452
 453         before = (uint)Vertices.size();
 454         while (Vertices.size()>3)       // don't smooth blow 3 vertices to avoid degenrated surfaces
 455         {
 456                 minArea = val;
 457                 minIt = Vertices.end();
 458                 it = Vertices.begin();
 459                 ++it;
 460
 461                 for (i=1; i<Vertices.size()-1; ++i, ++it)
 462                 {
 463                         float   area;
 464
 465                         area = 0.5f*((Vertices[i+1]-Vertices[i])^(Vertices[i-1]-Vertices[i])).norm();
 466                         if (area < minArea)
 467                         {
 468                                 minArea = area;
 469                                 minIt = it;
 470                         }
 471                 }
 472
 473                 if (minIt != Vertices.end())
 474                 {
 475                         Vertices.erase(minIt);
 476                 }
 477                 else
 478                 {
 479                         break;
 480                 }
 481         }
 482         after = (uint)Vertices.size();
 483
 484         if (Verbose)
 485                 nlinfo("smoothed border %d-%d: %d -> %d", Left, Right, before, after);
 486 }
 487
 488 /*
 489  * CComputableSurface methods implementation
 490  *
 491  */
 492 void    NLPACS::CComputableSurface::followBorder(CZoneTessellation *zoneTessel, CSurfElement *first, uint edge, uint sens, vector<CVector> &vstore, bool &loop)
 493 {
 494         CSurfElement    *current = first;
 495         CSurfElement    *next = current->EdgeLinks[edge];
 496         current->EdgeFlag[edge] = true;
 497
 498         const sint32    currentSurfId = current->SurfaceId;
 499         const sint32    oppositeSurfId = (next != NULL) ? next->SurfaceId : UnaffectedSurfaceId;
 500         const sint32    oppositeZid = current->getZoneIdOnEdge(edge);
 501         sint                    oedge;
 502
 503         sint                    pivot = (edge+sens)%3;
 504         sint                    nextEdge = edge;
 505
 506         bool                    allowThis = true;
 507
 508         // adds the pivot to the border and its normal
 509         vstore.push_back((*current->Vertices)[current->Tri[pivot]]);
 510
 511         uint    loopCount = 0;
 512
 513         while (true)
 514         {
 515                 ++loopCount;
 516
 517                 current->IsBorder = true;
 518
 519                 if (((oppositeSurfId != UnaffectedSurfaceId) && (next == NULL || (next->SurfaceId != oppositeSurfId && next->SurfaceId != currentSurfId))) ||
 520                         ((oppositeSurfId == UnaffectedSurfaceId) && ((next != NULL && next->SurfaceId != currentSurfId) || (next == NULL && current->getZoneIdOnEdge(nextEdge) != oppositeZid))) ||
 521                         ((current->EdgeFlag[nextEdge] || (zoneTessel->VerticesFlags[current->Tri[pivot]]!=0)) && !allowThis))
 522                 {
 523                         // if reaches the end of the border, then quits.
 524                         loop = (absoluteEquals(vstore.front(), vstore.back(), 1e-2f) && loopCount != 1);
 525                         break;
 526                 }
 527                 else if ((oppositeSurfId != UnaffectedSurfaceId && next->SurfaceId == oppositeSurfId) ||
 528                                  (oppositeSurfId == UnaffectedSurfaceId && next == NULL))
 529                 {
 530                         // if the next edge belongs to the border, then go on the same element
 531                         current->EdgeFlag[nextEdge] = true;
 532                         if (oppositeSurfId != UnaffectedSurfaceId)
 533                         {
 534                                 for (oedge=0; oedge<3 && next->EdgeLinks[oedge]!=current; ++oedge)
 535                                         ;
 536                                 nlassert(oedge != 3);
 537                                 nlassert(allowThis || !next->EdgeFlag[oedge]);
 538                                 next->EdgeFlag[oedge] = true;
 539                         }
 540                         pivot = (pivot+sens)%3;
 541                         nextEdge = (nextEdge+sens)%3;
 542                         next = current->EdgeLinks[nextEdge];
 543                         vstore.push_back((*current->Vertices)[current->Tri[pivot]]);
 544                 }
 545                 else
 546                 {
 547                         // if the next element is inside the surface, then go to the next element
 548                         nlassert(next->SurfaceId == currentSurfId);
 549
 550                         for (oedge=0; oedge<3 && next->EdgeLinks[oedge]!=current; ++oedge)
 551                                 ;
 552                         nlassert(oedge != 3);
 553                         current = next;
 554                         pivot = (oedge+3-sens)%3;
 555                         nextEdge = (oedge+sens)%3;
 556                         next = current->EdgeLinks[nextEdge];
 557                 }
 558
 559                 allowThis = false;
 560         }
 561 }
 562
 563 void    NLPACS::CComputableSurface::buildBorders(CZoneTessellation *zoneTessel)
 564 {
 565         sint    elem, edge;
 566
 567         if (Verbose)
 568                 nlinfo("generate borders for the surface %d (%d elements) - water=%d", SurfaceId, Elements.size(), (IsUnderWater ? 1 : 0));
 569
 570         for (elem=0; elem<(sint)Elements.size(); ++elem)
 571         {
 572                 // for each element,
 573                 // scan for a edge that points to a different surface
 574
 575                 nlassert(Elements[elem]->SurfaceId == SurfaceId);
 576
 577                 for (edge=0; edge<3; ++edge)
 578                 {
 579
 580                         if ((Elements[elem]->EdgeLinks[edge] == NULL || Elements[elem]->EdgeLinks[edge]->SurfaceId != SurfaceId) &&
 581                                 !Elements[elem]->EdgeFlag[edge])
 582                         {
 583                                 BorderIds.push_back((uint16)BorderKeeper->size());
 584
 585                                 BorderKeeper->resize(BorderKeeper->size()+1);
 586                                 CComputableSurfaceBorder        &border = BorderKeeper->back();
 587
 588                                 border.Left = Elements[elem]->SurfaceId;
 589
 590                                 // ????
 591                                 //border.DontSmooth = (Elements[elem]->EdgeLinks[edge] != NULL && Elements[elem]->NoLevelSurfaceId == Elements[elem]->EdgeLinks[edge]->SurfaceId);
 592
 593                                 if (Elements[elem]->EdgeLinks[edge] != NULL && Elements[elem]->EdgeLinks[edge]->ZoneId != Elements[elem]->ZoneId)
 594                                 {
 595                                         // link on a neighbor zone
 596                                         border.Right = -2;
 597                                 }
 598                                 if (Elements[elem]->EdgeLinks[edge] == NULL || Elements[elem]->EdgeLinks[edge]->SurfaceId == UnaffectedSurfaceId)
 599                                 {
 600                                         // no link at all
 601                                         border.Right = -1;
 602                                 }
 603                                 else
 604                                 {
 605                                         border.Right = Elements[elem]->EdgeLinks[edge]->SurfaceId;
 606                                 }
 607
 608                                 if (Verbose)
 609                                         nlinfo("generate border %d (%d-%d)", BorderKeeper->size()-1, border.Left, border.Right);
 610
 611                                 bool                            loop;
 612                                 vector<CVector>         bwdVerts;
 613                                 vector<CVector>         &fwdVerts = border.Vertices;
 614
 615                                 followBorder(zoneTessel, Elements[elem], edge, 2, bwdVerts, loop);
 616
 617                                 sint    i;
 618
 619                                 fwdVerts.reserve(bwdVerts.size());
 620                                 fwdVerts.clear();
 621
 622                                 for (i=(sint)(bwdVerts.size()-1); i>=0; --i)
 623                                 {
 624                                         fwdVerts.push_back(bwdVerts[i]);
 625                                 }
 626
 627                                 if (loop)
 628                                 {
 629                                         fwdVerts.push_back(fwdVerts.front());
 630                                 }
 631                                 else
 632                                 {
 633                                         fwdVerts.resize(fwdVerts.size()-2);
 634                                         followBorder(zoneTessel, Elements[elem], edge, 1, fwdVerts, loop);
 635                                 }
 636                         }
 637                 }
 638         }
 639 }
 640
 641 bool    intersect(const CVectorD& a0, const CVectorD& a1, const CVectorD& b0, const CVectorD& b1, double& pa, double& pb)
 642 {
 643         double          ax = +(a1.x-a0.x);
 644         double          ay = +(a1.y-a0.y);
 645         double          bx = +(b1.x-b0.x);
 646         double          by = +(b1.y-b0.y);
 647         double          cx = +(b0.x-a0.x);
 648         double          cy = +(b0.y-a0.y);
 649
 650         double          d = -ax*by + ay*bx;
 651
 652         if (d == 0.0)
 653                 return false;
 654
 655         double          a = (bx*cy - by*cx) / d;
 656         double          b = (ax*cy - ay*cx) / d;
 657
 658         pa = a;
 659         pb = b;
 660
 661         return d != 0.0 && a >= 0.0 && a <= 1.0 && b >= 0.0 && b <= 1.0;
 662 }
 663
 664 // Check Surface Consistency
 665 bool    NLPACS::CComputableSurface::checkConsistency()
 666 {
 667         bool    success = true;
 668
 669         std::vector<std::pair<NLMISC::CVectorD, NLMISC::CVectorD> >     edges;
 670
 671         uint    i, j;
 672         for (i=0; i<BorderIds.size(); ++i)
 673         {
 674                 CComputableSurfaceBorder&       border = (*BorderKeeper)[BorderIds[i]];
 675
 676                 for (j=0; j+1<border.Vertices.size(); ++j)
 677                         edges.push_back(std::make_pair(border.Vertices[j], border.Vertices[j+1]));
 678         }
 679
 680         for (i=0; i+1<edges.size(); ++i)
 681         {
 682                 for (j=i+1; j<edges.size(); ++j)
 683                 {
 684                         CVectorD        a0 = edges[i].first,
 685                                                 a1 = edges[i].second;
 686                         CVectorD        b0 = edges[j].first,
 687                                                 b1 = edges[j].second;
 688
 689                         double          a, b;
 690                         bool            inters = intersect(a0, a1, b0, b1, a, b);
 691
 692                         if (!inters)
 693                                 continue;
 694
 695                         double          da = (a1-a0).norm();
 696                         double          db = (b1-b0).norm();
 697
 698                         bool            tipa = (fabs(a)*da < 4.0e-2 || fabs(1.0-a)*da < 4.0e-2);
 699                         bool            tipb = (fabs(b)*db < 4.0e-2 || fabs(1.0-b)*db < 4.0e-2);
 700
 701                         if (tipa && tipb)
 702                                 continue;
 703
 704                         success = false;
 705                 }
 706         }
 707
 708         return success;
 709 }
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722 /*
 723  * CZoneTessellation constructors and methods implementation
 724  *
 725  *
 726  *
 727  *
 728  *
 729  *
 730  *
 731  *
 732  *
 733  *
 734  */
 735
 736 bool    NLPACS::CZoneTessellation::setup(uint16 zoneId, sint16 refinement, const CVector &translation)
 737 {
 738         CentralZoneId = zoneId;
 739         Refinement = refinement;
 740 //      Translation = translation;
 741
 742         // the zone bbox is hard coded for accuracy improvement...
 743         OriginalBBox = getZoneBBoxById(zoneId);
 744         BBox = OriginalBBox;
 745         Translation = -BBox.getCenter();
 746         Translation.x = (float)floor(Translation.x+0.5f);
 747         Translation.y = (float)floor(Translation.y+0.5f);
 748         Translation.z = (float)floor(Translation.z+0.5f);
 749         BBox.setCenter(CVector::Null);
 750         BBox.setHalfSize(CVector(80.0f, 80.0f, BBox.getHalfSize().z));
 751
 752         // if zone doesn't exist, don't even setup tessellation
 753         try
 754         {
 755                 if (CPath::lookup(getZoneNameById(zoneId)+ZoneExt, false, false) == "")
 756                         return false;
 757         }
 758         catch (const EPathNotFound &)
 759         {
 760                 return false;
 761         }
 762
 763         // setup the square of 9 zones...
 764         if (Verbose)
 765                 nlinfo("setup zone tessellation %d %s", zoneId, getZoneNameById(zoneId).c_str());
 766         {
 767                 sint    zx = zoneId%256, zy = zoneId/256;
 768
 769                 for (zy=(zoneId/256)-1; zy<=(zoneId/256)+1; ++zy)
 770                 {
 771                         for (zx=(zoneId%256)-1; zx<=(zoneId%256)+1; ++zx)
 772                         {
 773                                 if (zx >= 0 && zx <= 255 && zy >= 0 && zy <= 255)
 774                                 {
 775                                         uint    zid = (zy<<8) + (zx);
 776                                         string  filename = getZoneNameById(zid)+ZoneExt;
 777                                         if (CPath::lookup(filename, false, false) != "")
 778                                         {
 779                                                 _ZoneIds.push_back(zid);
 780                                         }
 781                                 }
 782                         }
 783                 }
 784         }
 785
 786         // sort zones
 787         sort(_ZoneIds.begin(), _ZoneIds.end());
 788
 789         return true;
 790 }
 791
 792
 793
 794 // ***************************************************************************
 795 void    NLPACS::CZoneTessellation::checkSameLandscapeHmBinds(const NL3D::CLandscape &landscape, const NL3D::CLandscape &landscapeNoHm)
 796 {
 797         // For all zones
 798         for (uint i=0; i<_ZoneIds.size(); ++i)
 799         {
 800                 uint16  zoneId= _ZoneIds[i];
 801                 string zoneName;
 802                 CLandscape::buildZoneName(zoneId, zoneName);
 803
 804                 // Get the zones
 805                 const CZone *zone= landscape.getZone(zoneId);
 806                 const CZone *zoneNoHm= landscapeNoHm.getZone(zoneId);
 807                 // Check that both are valid, or both are not
 808                 if( (zone==NULL) != (zoneNoHm==NULL) )
 809                 {
 810                         nlwarning("ERROR: The zone %s is %s in the landscape while it is %s in the landscape_with_No_Heightmap",
 811                                 zoneName.c_str(), zone==NULL?"not present":"present", zoneNoHm==NULL?"not present":"present");
 812                         exit(0);
 813                 }
 814                 // else if both are valid
 815                 else if(zone && zoneNoHm)
 816                 {
 817                         // check same number of patches
 818                         uint    numPatchs= zone->getNumPatchs();
 819                         uint    numPatchsNoHm= zoneNoHm->getNumPatchs();
 820                         if(numPatchs!=numPatchsNoHm)
 821                         {
 822                                 nlwarning("ERROR: The zone %s has %d Patchs in the landscape while it has %d Patchs in the landscape_with_No_Heightmap",
 823                                         zoneName.c_str(), numPatchs, numPatchsNoHm);
 824                                 exit(0);
 825                         }
 826                         else
 827                         {
 828                                 // Check all binds of all patches
 829                                 std::vector<string>             errors;
 830                                 errors.reserve(100);
 831                                 for(uint j=0;j<numPatchs;j++)
 832                                 {
 833                                         const CZone::CPatchConnect *patch= zone->getPatchConnect(j);
 834                                         const CZone::CPatchConnect *patchNoHm= zoneNoHm->getPatchConnect(j);
 835
 836                                         // Check BaseVertices
 837                                         for(uint v=0;v<4;v++)
 838                                         {
 839                                                 if(patch->BaseVertices[v] != patchNoHm->BaseVertices[v])
 840                                                 {
 841                                                         errors.push_back(toString("    The Patch %d has not the same %dth vertex: %d/%d",
 842                                                                 j, v, patch->BaseVertices[v], patchNoHm->BaseVertices[v]));
 843                                                 }
 844                                         }
 845
 846                                         // Check BindEdges
 847                                         for(uint b=0;b<4;b++)
 848                                         {
 849                                                 CPatchInfo::CBindInfo   bind= patch->BindEdges[b];
 850                                                 CPatchInfo::CBindInfo   bindNoHm= patchNoHm->BindEdges[b];
 851                                                 bool    ok= true;
 852                                                 // verify all valid properties only
 853                                                 ok= ok && bind.NPatchs == bindNoHm.NPatchs;
 854                                                 ok= ok && bind.ZoneId == bindNoHm.ZoneId;
 855                                                 uint    validNbBinds= min(bind.NPatchs,uint8(4));
 856                                                 for(uint nb=0;nb<validNbBinds;nb++)
 857                                                 {
 858                                                         ok= ok && bind.Next[nb] == bindNoHm.Next[nb];
 859                                                         ok= ok && bind.Edge[nb] == bindNoHm.Edge[nb];
 860                                                 }
 861                                                 // if not ok
 862                                                 if(!ok)
 863                                                 {
 864                                                         // add the error
 865                                                         string  error;
 866                                                         error=  toString("    The Patch %d that has not the same %dth bindEdge: NumPatchs: %d/%d; ZoneId: %d/%d",
 867                                                                 j, b, bind.NPatchs, bindNoHm.NPatchs, bind.ZoneId, bindNoHm.ZoneId);
 868                                                         for(uint nb=0;nb<validNbBinds;nb++)
 869                                                         {
 870                                                                 error+= toString("; Edge (%d,%d)/(%d,%d)", bind.Next[nb], bind.Edge[nb], bindNoHm.Next[nb], bindNoHm.Edge[nb]);
 871                                                         }
 872
 873                                                         errors.push_back(error);
 874                                                 }
 875                                         }
 876
 877                                 }
 878
 879                                 // if some error found
 880                                 if(!errors.empty())
 881                                 {
 882                                         // todo: change the way the landscape with heightmap is applied: it should be applied after welding!
 883                                         // or at least the welding of zones should just keep the same welding as the non heightmapped one
 884                                         nlwarning("ERROR: The zone %s has a different bind strucutre in the landscape and in the landscape_with_No_Heightmap", zoneName.c_str());
 885                                         nlwarning("ERROR: Hint: Check your heightmap: it may be too precise or has too much noise, causing the zonewelder to behav differently...");
 886                                         nlwarning("TIP: Use the 'zone_elevation' tool on the welded no-heightmap zones to resolve this!");
 887                                         nlwarning("More Details (information landscape / information landscape_with_No_Heightmap):");
 888                                         for(uint j=0;j<errors.size();j++)
 889                                         {
 890                                                 nlwarning("%s", errors[j].c_str());
 891                                         }
 892                                         exit(0);
 893                                 }
 894                         }
 895                 }
 896         }
 897 }
 898
 899
 900 // ***************************************************************************
 901 void    NLPACS::CZoneTessellation::build()
 902 {
 903         sint    el;
 904         uint    i, j;
 905
 906         NL3D::CLandscape        landscape;
 907         landscape.init();
 908
 909         vector<CVector>                         normals;
 910
 911         vector<CVector>                         vectorCheck;
 912         bool                                            useNoHmZones = true;
 913
 914         {
 915                 NL3D::CLandscape        landscapeNoHm;
 916                 landscapeNoHm.init();
 917
 918                 //
 919                 // load the 9 landscape zones
 920                 //
 921                 for (i=0; i<_ZoneIds.size(); ++i)
 922                 {
 923                         string  filename = getZoneNameById(_ZoneIds[i])+ZoneExt;
 924                         CIFile  file(CPath::lookup(filename));
 925                         CZone   zone;
 926                         zone.serial(file);
 927                         file.close();
 928
 929                         if (Verbose)
 930                                 nlinfo("use zone %s %d", filename.c_str(), zone.getZoneId());
 931
 932                         if (zone.getZoneId() != _ZoneIds[i])
 933                         {
 934                                 nlwarning ("Zone %s ID is wrong. Abort.", filename.c_str());
 935                                 return;
 936                         }
 937                         landscape.addZone(zone);
 938
 939                         if (useNoHmZones)
 940                         {
 941                                 string  filenameNH = getZoneNameById(_ZoneIds[i])+ZoneNHExt;
 942                                 string  loadZ = CPath::lookup(filenameNH, false, false);
 943                                 if (!loadZ.empty())
 944                                 {
 945                                         CIFile  fileNH(loadZ);
 946                                         CZone   zoneNH;
 947                                         zoneNH.serial(fileNH);
 948                                         fileNH.close();
 949                                         if (zoneNH.getZoneId() != _ZoneIds[i])
 950                                         {
 951                                                 nlwarning ("Zone %s ID is wrong. Abort.", filenameNH.c_str());
 952                                                 return;
 953                                         }
 954                                         landscapeNoHm.addZone(zoneNH);
 955                                 }
 956                                 else
 957                                 {
 958                                         useNoHmZones = false;
 959                                 }
 960                         }
 961
 962                         _ZonePtrs.push_back(landscape.getZone(_ZoneIds[i]));
 963                 }
 964
 965                 landscape.setNoiseMode(false);
 966                 landscape.checkBinds();
 967
 968                 if (useNoHmZones)
 969                 {
 970                         landscapeNoHm.setNoiseMode(false);
 971                         landscapeNoHm.checkBinds();
 972                 }
 973
 974                 BestFittingBBox.setCenter(CVector::Null);
 975                 BestFittingBBox.setHalfSize(CVector::Null);
 976                 BestFittingBBoxSetuped= false;
 977
 978                 // Compute best fitting bbox
 979                 for (i=0; i<_ZoneIds.size(); ++i)
 980                 {
 981                         if (_ZoneIds[i] == CentralZoneId)
 982                         {
 983                                 if(_ZonePtrs[i]->getNumPatchs()>0)
 984                                 {
 985                                         BestFittingBBox = _ZonePtrs[i]->getZoneBB().getAABBox();
 986                                         BestFittingBBoxSetuped= true;
 987                                 }
 988                         }
 989                 }
 990
 991                 CAABBox enlBBox = BestFittingBBox;
 992                 enlBBox.setHalfSize(enlBBox.getHalfSize()+CVector(8.0f, 8.0f, 1000.0f));
 993
 994                 // Add neighbor patch
 995                 for (i=0; i<_ZoneIds.size(); ++i)
 996                 {
 997                         if (_ZoneIds[i] == CentralZoneId)
 998                         {
 999                                 for (j=0; (sint)j<_ZonePtrs[i]->getNumPatchs(); ++j)
1000                                 {
1001                                         landscape.excludePatchFromRefineAll(_ZoneIds[i], j, false);
1002                                         if (useNoHmZones)
1003                                                 landscapeNoHm.excludePatchFromRefineAll(_ZoneIds[i], j, false);
1004                                 }
1005                                 if (Verbose)
1006                                         nlinfo(" - selected %d/%d patches for zone %d", _ZonePtrs[i]->getNumPatchs(), _ZonePtrs[i]->getNumPatchs(), _ZoneIds[i]);
1007                         }
1008                         else
1009                         {
1010                                 uint    nump = 0;
1011                                 for (j=0; (sint)j<_ZonePtrs[i]->getNumPatchs(); ++j)
1012                                 {
1013                                         CAABBox pbox = _ZonePtrs[i]->getPatch(j)->buildBBox();
1014                                         bool    inters = enlBBox.intersect(pbox);
1015
1016                                         if (inters)
1017                                         {
1018                                                 landscape.excludePatchFromRefineAll(_ZoneIds[i], j, false);
1019                                                 if (useNoHmZones)
1020                                                         landscapeNoHm.excludePatchFromRefineAll(_ZoneIds[i], j, false);
1021                                                 ++nump;
1022                                         }
1023                                         else
1024                                         {
1025                                                 landscape.excludePatchFromRefineAll(_ZoneIds[i], j, true);
1026                                                 if (useNoHmZones)
1027                                                         landscapeNoHm.excludePatchFromRefineAll(_ZoneIds[i], j, true);
1028                                         }
1029                                 }
1030                                 if (Verbose)
1031                                         nlinfo(" - selected %d/%d patches for zone %d", nump, _ZonePtrs[i]->getNumPatchs(), _ZoneIds[i]);
1032                         }
1033                 }
1034
1035                 // tessellate the landscape, get the leaves (the tessellation faces), and convert them
1036                 // into surf elements
1037                 if (Verbose)
1038                         nlinfo("Compute landscape tessellation");
1039
1040                 if (Verbose)
1041                         nlinfo("   - tessellate landscape");
1042
1043                 if (useNoHmZones)
1044                 {
1045                         // Before tesselate, verify that the 2 landscape zones have at least the same binds!
1046                         // Else there will be errors because of not the same tesselation
1047                         checkSameLandscapeHmBinds(landscape, landscapeNoHm);
1048
1049                         // Tesselate
1050                         landscapeNoHm.setThreshold(0.0f);
1051                         landscapeNoHm.setTileMaxSubdivision(TessellateLevel);
1052                         landscapeNoHm.refineAll(CVector::Null);
1053                         landscapeNoHm.averageTesselationVertices();
1054
1055                         // get the faces
1056                         vector<const CTessFace *>       leavesNoHm;
1057                         landscapeNoHm.getTessellationLeaves(leavesNoHm);
1058
1059                         for (el=0; el<(sint)leavesNoHm.size(); ++el)
1060                         {
1061                                 const CTessFace *face = leavesNoHm[el];
1062                                 const CVector   *v[3];
1063
1064                                 // get the vertices of the face
1065                                 v[0] = &(face->VBase->EndPos);
1066                                 v[1] = &(face->VLeft->EndPos);
1067                                 v[2] = &(face->VRight->EndPos);
1068
1069                                 normals.push_back( ((*(v[1])-*(v[0])) ^ (*(v[2])-*(v[0]))).normed() );
1070
1071                                 vectorCheck.push_back(*(v[0]));
1072                                 vectorCheck.push_back(*(v[1]));
1073                                 vectorCheck.push_back(*(v[2]));
1074                         }
1075                 }
1076         }
1077
1078         // Build the lanscape with heightmap
1079         landscape.setThreshold(0.0f);
1080         landscape.setTileMaxSubdivision(TessellateLevel);
1081         landscape.refineAll(CVector::Null);
1082         landscape.averageTesselationVertices();
1083
1084         vector<const CTessFace *>       leaves;
1085         landscape.getTessellationLeaves(leaves);
1086         if (Verbose)
1087         {
1088                 if (useNoHmZones)
1089                         nlinfo("      - used no height map zones");
1090                 nlinfo("      - generated %d leaves", leaves.size());
1091         }
1092
1093         // If don't use NoHm zones, build normals and vectorCheck directly from std landscape
1094         if (!useNoHmZones)
1095         {
1096                 for (el=0; el<(sint)leaves.size(); ++el)
1097                 {
1098                         const CTessFace *face = leaves[el];
1099                         const CVector   *v[3];
1100
1101                         // get the vertices of the face
1102                         v[0] = &(face->VBase->EndPos);
1103                         v[1] = &(face->VLeft->EndPos);
1104                         v[2] = &(face->VRight->EndPos);
1105
1106                         normals.push_back( ((*(v[1])-*(v[0])) ^ (*(v[2])-*(v[0]))).normed() );
1107
1108                         vectorCheck.push_back(*(v[0]));
1109                         vectorCheck.push_back(*(v[1]));
1110                         vectorCheck.push_back(*(v[2]));
1111                 }
1112         }
1113
1114         // check that there is the same number of faces from landscape with and without heightmap
1115         if (normals.size() != leaves.size())
1116         {
1117                 nlwarning ("ERROR : The heightmaped landscape has not the same number of polygon than the nonheightmaped landscape: %d/%d.",
1118                         normals.size(), leaves.size());
1119                 exit (0);
1120         }
1121
1122         // generate a vector of vertices and of surf element
1123         CHashMap<const CVector *, uint32, CHashPtr<const CVector> >                             vremap;
1124         CHashMap<const CVector *, uint32, CHashPtr<const CVector> >::iterator   vremapit;
1125         CHashMap<const CTessFace *, CSurfElement *, CHashPtr<const CTessFace> > fremap;
1126         CHashMap<const CTessFace *, CSurfElement *, CHashPtr<const CTessFace> >::iterator       fremapit;
1127         _Vertices.clear();
1128         _Tessellation.resize(leaves.size());
1129
1130         if (Verbose)
1131                 nlinfo("   - make and remap surface elements");
1132
1133         for (el=0; el<(sint)leaves.size(); ++el)
1134                 fremap[leaves[el]] = &(_Tessellation[el]);
1135
1136         uint    check = 0;
1137
1138         float   dist, maxdist = 0.0f;
1139
1140         for (el=0; el<(sint)leaves.size(); ++el)
1141         {
1142                 const CTessFace *face = leaves[el];
1143                 const CVector   *v[3];
1144
1145                 CSurfElement    &element = _Tessellation[el];
1146
1147                 // setup zone id
1148                 element.ZoneId = face->Patch->getZone()->getZoneId();
1149
1150                 // get the vertices of the face
1151                 v[0] = &(face->VBase->EndPos);
1152                 v[1] = &(face->VLeft->EndPos);
1153                 v[2] = &(face->VRight->EndPos);
1154
1155                 {
1156                         CVector vcheck;
1157
1158                         vcheck = vectorCheck[check++] - *(v[0]);
1159                         vcheck.z = 0;
1160                         dist = vcheck.norm();
1161                         if (dist > maxdist)     maxdist = dist;
1162                         //nlassert(vcheck.norm() < 0.1f);
1163
1164                         vcheck = vectorCheck[check++] - *(v[1]);
1165                         vcheck.z = 0;
1166                         dist = vcheck.norm();
1167                         if (dist > maxdist)     maxdist = dist;
1168                         //nlassert(vcheck.norm() < 0.1f);
1169
1170                         vcheck = vectorCheck[check++] - *(v[2]);
1171                         vcheck.z = 0;
1172                         dist = vcheck.norm();
1173                         if (dist > maxdist)     maxdist = dist;
1174                         //nlassert(vcheck.norm() < 0.1f);
1175                 }
1176
1177                 //element.Normal = ((*(v[1])-*(v[0])) ^ (*(v[2])-*(v[0]))).normed();
1178                 element.Normal = normals[el];
1179
1180
1181                 // search the vertices in the map
1182                 for (i=0; i<3; ++i)
1183                 {
1184                         // if doesn't exist, create a new vertex
1185                         if ((vremapit = vremap.find(v[i])) == vremap.end())
1186                         {
1187                                 element.Tri[i] = (uint32)_Vertices.size();
1188                                 _Vertices.push_back(*(v[i]));
1189                                 vremap.insert(make_pair(v[i], element.Tri[i]));
1190                         }
1191                         // else use previous
1192                         else
1193                         {
1194                                 element.Tri[i] = vremapit->second;
1195                         }
1196                 }
1197
1198                 // setup the vertices pointer
1199                 element.Vertices = &_Vertices;
1200
1201                 CTessFace               *edge[3];
1202
1203                 edge[0] = face->FBase;
1204                 edge[1] = face->FRight;
1205                 edge[2] = face->FLeft;
1206
1207                 for (i=0; i<3; ++i)
1208                 {
1209                         fremapit = fremap.find(edge[i]);
1210                         element.EdgeLinks[i] = (fremapit != fremap.end() ? fremapit->second : NULL);
1211                 }
1212         }
1213
1214         for (el=0; el<(sint)_Tessellation.size(); ++el)
1215         {
1216                 // add the element to the list of valid elements
1217                 Elements.push_back(&(_Tessellation[el]));
1218         }
1219
1220         landscape.clear();
1221 }
1222
1223
1224
1225
1226
1227 void    NLPACS::CZoneTessellation::compile()
1228 {
1229         sint    el;
1230         uint    i;
1231
1232         CAABBox tbox = computeBBox();
1233
1234         bool    HasInvertedUnderWater = false;
1235
1236         // setup cliffs
1237         for (el=0; el<(sint)Elements.size(); ++el)
1238         {
1239                 CSurfElement    &element = *(Elements[el]);
1240
1241                 // a cliff ?
1242                 if (element.Normal.z < 0.0)
1243                 {
1244                         CVector         &v0 = _Vertices[element.Tri[0]],
1245                                                 &v1 = _Vertices[element.Tri[1]],
1246                                                 &v2 = _Vertices[element.Tri[2]];
1247
1248                         uint8           bits0 = PrimChecker.get((uint)v0.x, (uint)v0.y);
1249                         uint8           bits1 = PrimChecker.get((uint)v1.x, (uint)v1.y);
1250                         uint8           bits2 = PrimChecker.get((uint)v2.x, (uint)v2.y);
1251
1252                         bool            w0 = ((bits0&CPrimChecker::Water) != 0);
1253                         bool            w1 = ((bits1&CPrimChecker::Water) != 0);
1254                         bool            w2 = ((bits2&CPrimChecker::Water) != 0);
1255
1256                         if ((bits0 & CPrimChecker::Water)!=0 || (bits1 & CPrimChecker::Water)!=0 || (bits2 & CPrimChecker::Water)!=0)
1257                         {
1258                                 uint            ws = 0;
1259
1260                                 uint16          ws0 = PrimChecker.index((uint)v0.x, (uint)v0.y);
1261                                 uint16          ws1 = PrimChecker.index((uint)v1.x, (uint)v1.y);
1262                                 uint16          ws2 = PrimChecker.index((uint)v2.x, (uint)v2.y);
1263
1264                                 if ((w0 && w1 && ws0 == ws1) || (w0 && w2 && ws0 == ws2))
1265                                         ws = ws0;
1266                                 else if (w1 && w2 && ws1 == ws2)
1267                                         ws = ws1;
1268                                 else if (w0)
1269                                         ws = ws0;
1270                                 else if (w1)
1271                                         ws = ws1;
1272                                 else if (w2)
1273                                         ws = ws2;
1274
1275                                 float           minz = std::min(_Vertices[element.Tri[0]].z,
1276                                                                    std::min(_Vertices[element.Tri[1]].z,
1277                                                                                         _Vertices[element.Tri[2]].z));
1278
1279                                 bool            exists;
1280                                 float           wh = PrimChecker.waterHeight(ws, exists)+WaterThreshold;
1281
1282                                 //
1283                                 if (minz <= wh)
1284                                 {
1285                                         CPolygon        p(v0, v1, v2);
1286                                         PrimChecker.renderBits(p, CPrimChecker::Cliff);
1287
1288                                         HasInvertedUnderWater = true;
1289                                 }
1290                         }
1291                 }
1292         }
1293
1294         if (HasInvertedUnderWater)
1295         {
1296                 nlwarning("zone '%s' has reversed landscape under water", (getZoneNameById((uint16)CentralZoneId)+ZoneExt).c_str());
1297         }
1298
1299
1300         // compute elements features
1301         if (Verbose)
1302                 nlinfo("compute elements quantas");
1303         for (el=0; el<(sint)Elements.size(); ++el)
1304         {
1305                 CSurfElement    &element = *(Elements[el]);
1306
1307                 element.ElemId = el;
1308                 element.computeQuantas(this);
1309         }
1310
1311         if (ReduceSurfaces)
1312         {
1313                 // optimizes the number of generated segments
1314                 // it also smoothes a bit the surface border
1315                 // it seems that 3 consecutive passes are optimal to reduce
1316                 // nasty granularity
1317                 if (Verbose)
1318                         nlinfo("reduce surfaces");
1319                 uint    i;
1320                 sint    p;
1321
1322                 for (i=0; i<3; ++i)
1323                 {
1324                         for (p=0; p<(sint)Elements.size(); ++p)
1325                         {
1326                                 CSurfElement    &e = *(Elements[p]);
1327                                 CSurfElement    &e0 = *e.EdgeLinks[0],
1328                                                                 &e1 = *e.EdgeLinks[1],
1329                                                                 &e2 = *e.EdgeLinks[2];
1330
1331                                 if (e.IsMergable && &e0 != NULL && &e1 != NULL && &e2 != NULL &&
1332                                         e.ZoneId == e0.ZoneId &&
1333                                         e.ZoneId == e1.ZoneId &&
1334                                         e.ZoneId == e2.ZoneId &&
1335                                         !e.ForceInvalid)
1336                                 {
1337                                         // Strong optimization
1338                                         // merge the element quantas to the neighbors' quantas which are the most numerous
1339                                         // quantas are evaluated individually
1340                                         if (e0.IsValid && e1.IsValid)                                           e.IsValid = true;
1341                                         if (e1.IsValid && e2.IsValid)                                           e.IsValid = true;
1342                                         if (e0.IsValid && e2.IsValid)                                           e.IsValid = true;
1343
1344                                         if (e0.QuantHeight == e1.QuantHeight)                           e.QuantHeight = e0.QuantHeight;
1345                                         if (e1.QuantHeight == e2.QuantHeight)                           e.QuantHeight = e1.QuantHeight;
1346                                         if (e0.QuantHeight == e2.QuantHeight)                           e.QuantHeight = e2.QuantHeight;
1347
1348                                         if (e0.IsValid && e1.IsValid && e0.WaterShape == e1.WaterShape && e0.IsUnderWater == e1.IsUnderWater)
1349                                         {
1350                                                 e.WaterShape = e0.WaterShape;
1351                                                 e.IsUnderWater = e0.IsUnderWater;
1352                                         }
1353                                         if (e1.IsValid && e2.IsValid && e1.WaterShape == e2.WaterShape && e1.IsUnderWater == e2.IsUnderWater)
1354                                         {
1355                                                 e.WaterShape = e1.WaterShape;
1356                                                 e.IsUnderWater = e1.IsUnderWater;
1357                                         }
1358                                         if (e0.IsValid && e2.IsValid && e0.WaterShape == e2.WaterShape && e0.IsUnderWater == e2.IsUnderWater)
1359                                         {
1360                                                 e.WaterShape = e2.WaterShape;
1361                                                 e.IsUnderWater = e2.IsUnderWater;
1362                                         }
1363                                 }
1364                         }
1365                 }
1366
1367                 for (p=0; p<(sint)Elements.size(); ++p)
1368                 {
1369                         CSurfElement    &e = *(Elements[p]);
1370                         CSurfElement    &e0 = *e.EdgeLinks[0],
1371                                                         &e1 = *e.EdgeLinks[1],
1372                                                         &e2 = *e.EdgeLinks[2];
1373
1374                         if (&e != NULL && &e0 != NULL && &e1 != NULL && &e2 != NULL &&
1375                                 e.IsValid && e0.IsValid && e1.IsValid && e2.IsValid &&
1376                                 !e.IsUnderWater && e0.IsUnderWater && e1.IsUnderWater && e2.IsUnderWater)
1377                         {
1378                                 nlwarning("isolated submerged element '%d' !", p);
1379                         }
1380                 }
1381         }
1382
1383         // translates vertices to the local axis
1384         sint64  vx, vy, vz, tx, ty, tz;
1385         tx = float2Fixed(Translation.x);
1386         ty = float2Fixed(Translation.y);
1387         tz = float2Fixed(Translation.z);
1388
1389         uint    p;
1390         for (i=0; i<_Vertices.size(); ++i)
1391         {
1392                 vx = float2Fixed(_Vertices[i].x) + tx;
1393                 vy = float2Fixed(_Vertices[i].y) + ty;
1394                 vz = float2Fixed(_Vertices[i].z) + tz;
1395                 _Vertices[i] = CVector(fixed2Float(vx), fixed2Float(vy), fixed2Float(vz));
1396         }
1397
1398         if(BestFittingBBoxSetuped)
1399                 BestFittingBBox.setCenter(BestFittingBBox.getCenter()+Translation);
1400
1401
1402         //
1403         //if (false)
1404         {
1405                 //
1406                 // first pass of flood fill
1407                 // allow detecting landscape irregularities
1408                 //
1409
1410                 if (Verbose)
1411                         nlinfo("build and flood fill surfaces -- pass 1");
1412                 uint32  surfId = 0; // + (ZoneId<<16);
1413
1414                 for (p=0; p<Elements.size(); ++p)
1415                 {
1416                         if (Elements[p]->SurfaceId == UnaffectedSurfaceId)
1417                         {
1418                                 Surfaces.push_back(CComputableSurface());
1419                                 CComputableSurface      &surf = Surfaces.back();
1420
1421                                 surf.BorderKeeper = &Borders;
1422                                 surf.floodFill(Elements[p], surfId++, CSurfElemCompareSimple(), this);
1423                                 surf.BBox = BestFittingBBox;
1424
1425                                 bool    force = false;
1426
1427                                 if (surf.Area < 30.0f && !surf.Elements.empty())
1428                                 {
1429                                         uint            i;
1430                                         CAABBox         aabbox;
1431
1432                                         aabbox.setCenter((*surf.Elements[0]->Vertices)[surf.Elements[0]->Tri[0]]);
1433
1434                                         for (i=0; i<surf.Elements.size(); ++i)
1435                                         {
1436                                                 aabbox.extend((*surf.Elements[i]->Vertices)[surf.Elements[i]->Tri[0]]);
1437                                                 aabbox.extend((*surf.Elements[i]->Vertices)[surf.Elements[i]->Tri[1]]);
1438                                                 aabbox.extend((*surf.Elements[i]->Vertices)[surf.Elements[i]->Tri[2]]);
1439                                         }
1440
1441                                         // swap all suface elements validity
1442                                         if (!surf.Elements[0]->ForceInvalid && aabbox.getHalfSize().z < 1.5f)
1443                                         {
1444                                                 for (i=0; i<surf.Elements.size(); ++i)
1445                                                 {
1446                                                         surf.Elements[i]->IsValid = !surf.Elements[i]->IsValid;
1447                                                 }
1448                                                 if (Verbose)
1449                                                         nlinfo("Reverted surface %d (%d elements, water=%d)", surfId-1, surf.Elements.size(), (surf.IsUnderWater ? 1 : 0));
1450                                         }
1451                                 }
1452                         }
1453                 }
1454
1455                 Surfaces.clear();
1456                 ExtSurfaces.clear();
1457         }
1458
1459         vector<CSurfElement*>   elDup;
1460         for (el=0; el<(sint)Elements.size(); ++el)
1461                 if (Elements[el]->IsValid)
1462                         elDup.push_back(Elements[el]);
1463         Elements = elDup;
1464         elDup.clear();
1465
1466         for (el=0; el<(sint)Elements.size(); ++el)
1467         {
1468                 CSurfElement    &element = *(Elements[el]);
1469                 element.SurfaceId = UnaffectedSurfaceId;
1470                 uint    i;
1471                 for (i=0; i<3; ++i)
1472                         if (element.EdgeLinks[i] != NULL && !element.EdgeLinks[i]->IsValid)
1473                                 element.EdgeLinks[i] = NULL;
1474         }
1475
1476         //
1477         {
1478                 if (Verbose)
1479                         nlinfo("build and flood fill surfaces");
1480                 uint32  surfId = 0; // + (ZoneId<<16);
1481                 uint    totalSurf = 0;
1482                 sint32  extSurf = -1024;
1483
1484                 for (p=0; p<Elements.size(); ++p)
1485                 {
1486                         if (Elements[p]->SurfaceId == UnaffectedSurfaceId)
1487                         {
1488                                 bool    elInCentral = (Elements[p]->ZoneId == CentralZoneId);
1489
1490                                 ++totalSurf;
1491                                 sint32  thisSurfId = (elInCentral) ? surfId++ : extSurf--;
1492                                 if (elInCentral)
1493                                         Surfaces.push_back(CComputableSurface());
1494                                 else
1495                                         ExtSurfaces.push_back(CComputableSurface());
1496
1497                                 CComputableSurface      &surf = (elInCentral) ? Surfaces.back() : ExtSurfaces.back();
1498
1499                                 surf.BorderKeeper = &Borders;
1500                                 surf.floodFill(Elements[p], thisSurfId, CSurfElemCompareNormal(), this);
1501                                 surf.BBox = BestFittingBBox;
1502                         }
1503                 }
1504
1505                 if (Verbose)
1506                 {
1507                         nlinfo("%d surfaces generated", totalSurf);
1508
1509                         for (p=0; p<Surfaces.size(); ++p)
1510                         {
1511                                 nlinfo("surf %d: %d elements", p, Surfaces[p].Elements.size());
1512
1513                                 if (Surfaces[p].Elements.size() == 1)
1514                                 {
1515                                         nlinfo("elm: %d", Surfaces[p].Elements[0]->ElemId);
1516                                 }
1517                         }
1518                 }
1519         }
1520
1521         // flag vertices that are pointed by more than 2 surfaces
1522         VerticesFlags.resize(_Vertices.size(), 0);
1523
1524         for (p=0; p<Elements.size(); ++p)
1525         {
1526                 CSurfElement    *elem = Elements[p];
1527
1528                 sint32          s = elem->SurfaceId;
1529                 sint32          s0 = (elem->EdgeLinks[0] != NULL ? elem->EdgeLinks[0]->SurfaceId : UnaffectedSurfaceId);
1530                 sint32          s1 = (elem->EdgeLinks[1] != NULL ? elem->EdgeLinks[1]->SurfaceId : UnaffectedSurfaceId);
1531                 sint32          s2 = (elem->EdgeLinks[2] != NULL ? elem->EdgeLinks[2]->SurfaceId : UnaffectedSurfaceId);
1532
1533                 if (s != s0 && s != s1 && s0 != s1)
1534                 {
1535                         VerticesFlags[elem->Tri[2]] = 1;
1536                 }
1537
1538                 if (s != s1 && s != s2 && s1 != s2)
1539                 {
1540                         VerticesFlags[elem->Tri[0]] = 1;
1541                 }
1542
1543                 if (s != s2 && s != s0 && s2 != s0)
1544                 {
1545                         VerticesFlags[elem->Tri[1]] = 1;
1546                 }
1547         }
1548 }
1549
1550
1551
1552
1553 void    NLPACS::CZoneTessellation::generateBorders(float smooth)
1554 {
1555         sint    surf;
1556
1557         if (Verbose)
1558                 nlinfo("generate tessellation borders");
1559         // for each surface, build its border
1560         for (surf=0; surf<(sint)Surfaces.size(); ++surf)
1561                 Surfaces[surf].buildBorders(this);
1562
1563         // then, for each border, link the related surfaces...
1564         if (Verbose)
1565                 nlinfo("smooth borders");
1566         sint    border;
1567         sint    totalBefore = 0,
1568                         totalAfter = 0;
1569         for (border=0; border<(sint)Borders.size(); ++border)
1570         {
1571                 CComputableSurfaceBorder&       cborder = Borders[border];
1572
1573                 sint    lsurf = cborder.Left;
1574                 sint    rsurf = cborder.Right;
1575
1576                 if (CheckConsistency)
1577                 {
1578                         if (lsurf >= 0)
1579                         {
1580                                 CComputableSurface&     surf = Surfaces[lsurf];
1581                                 if (!surf.checkConsistency())
1582                                 {
1583                                         nlwarning("Before smooth of border '%d', surface '%d' not consistent", border, lsurf);
1584                                 }
1585                         }
1586                         if (rsurf >= 0)
1587                         {
1588                                 CComputableSurface&     surf = Surfaces[rsurf];
1589                                 if (!surf.checkConsistency())
1590                                 {
1591                                         nlwarning("Before smooth of border '%d', surface '%d' not consistent", border, rsurf);
1592                                 }
1593                         }
1594                 }
1595
1596                 float   smScale = (Borders[border].Right < 0) ? 0.2f : 1.0f;
1597                 uint    before = (uint)Borders[border].Vertices.size();
1598                 if (SmoothBorders && !Borders[border].DontSmooth)
1599                 {
1600                         Borders[border].smooth(smooth*smScale);
1601                 }
1602                 Borders[border].computeLength();
1603                 uint    after = (uint)Borders[border].Vertices.size();
1604                 totalBefore += before;
1605                 totalAfter += after;
1606
1607                 if (CheckConsistency)
1608                 {
1609                         if (lsurf >= 0)
1610                         {
1611                                 CComputableSurface&     surf = Surfaces[lsurf];
1612                                 if (!surf.checkConsistency())
1613                                 {
1614                                         nlwarning("After smooth of border '%d', surface '%d' not consistent", border, lsurf);
1615                                 }
1616                         }
1617                         if (rsurf >= 0)
1618                         {
1619                                 CComputableSurface&     surf = Surfaces[rsurf];
1620                                 if (!surf.checkConsistency())
1621                                 {
1622                                         nlwarning("After smooth of border '%d', surface '%d' not consistent", border, rsurf);
1623                                 }
1624                         }
1625                 }
1626         }
1627         if (Verbose)
1628                 nlinfo("smooth process: %d -> %d (%.1f percent reduction)", totalBefore, totalAfter, 100.0*(1.0-(double)totalAfter/(double)totalBefore));
1629 }
1630
1631
1632
1633
1634
1635 void    NLPACS::CZoneTessellation::saveTessellation(COFile &output)
1636 {
1637         output.serialCont(_Vertices);
1638
1639         uint    i;
1640
1641         for (i=0; i<_Tessellation.size(); ++i)
1642                 _Tessellation[i].ElemId = i;
1643
1644         uint32  numTessel = (uint32)_Tessellation.size();
1645         output.serial(numTessel);
1646
1647         for (i=0; i<_Tessellation.size(); ++i)
1648         {
1649                 _Tessellation[i].serial(output, _Tessellation);
1650         }
1651 }
1652
1653
1654
1655
1656 void    NLPACS::CZoneTessellation::loadTessellation(CIFile &input)
1657 {
1658         input.serialCont(_Vertices);
1659
1660         uint    i;
1661
1662         uint32  numTessel;
1663         input.serial(numTessel);
1664         _Tessellation.resize(numTessel);
1665
1666         for (i=0; i<_Tessellation.size(); ++i)
1667         {
1668                 _Tessellation[i].serial(input, _Tessellation);
1669         }
1670
1671         Elements.resize(_Tessellation.size());
1672         for (i=0; i<_Tessellation.size(); ++i)
1673         {
1674                 Elements[i] = &_Tessellation[i];
1675         }
1676 }
1677
1678 void    NLPACS::CZoneTessellation::clear()
1679 {
1680         _ZoneIds.clear();
1681         _ZonePtrs.clear();
1682         _Tessellation.clear();
1683         _Vertices.clear();
1684         Elements.clear();
1685         Surfaces.clear();
1686         Borders.clear();
1687 }
1688
1689 CAABBox NLPACS::CZoneTessellation::computeBBox() const
1690 {
1691         CAABBox         zbox;
1692         bool            set = false;
1693         uint            i;
1694
1695         if (_Vertices.empty())
1696                 return zbox;
1697
1698         zbox.setCenter(_Vertices[0]);
1699
1700         for (i=1; i<_Vertices.size(); ++i)
1701                 zbox.extend(_Vertices[i]);
1702
1703         return zbox;
1704 }