src/game/vmap/WorldModel.cpp

   1 /*
   2  * Copyright (C) 2005-2013 MaNGOS <http://getmangos.com/>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (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 General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19 #include "WorldModel.h"
  20 #include "VMapDefinitions.h"
  21 #include "MapTree.h"
  22
  23 using G3D::Vector3;
  24 using G3D::Ray;
  25
  26 template<> struct BoundsTrait<VMAP::GroupModel>
  27 {
  28     static void getBounds(const VMAP::GroupModel& obj, G3D::AABox& out) { out = obj.GetBound(); }
  29 };
  30
  31 namespace VMAP
  32 {
  33     bool IntersectTriangle(const MeshTriangle& tri, std::vector<Vector3>::const_iterator points, const G3D::Ray& ray, float& distance)
  34     {
  35         static const float EPS = 1e-5f;
  36
  37         // See RTR2 ch. 13.7 for the algorithm.
  38
  39         const Vector3 e1 = points[tri.idx1] - points[tri.idx0];
  40         const Vector3 e2 = points[tri.idx2] - points[tri.idx0];
  41         const Vector3 p(ray.direction().cross(e2));
  42         const float a = e1.dot(p);
  43
  44         if (fabs(a) < EPS)
  45         {
  46             // Determinant is ill-conditioned; abort early
  47             return false;
  48         }
  49
  50         const float f = 1.0f / a;
  51         const Vector3 s(ray.origin() - points[tri.idx0]);
  52         const float u = f * s.dot(p);
  53
  54         if ((u < 0.0f) || (u > 1.0f))
  55         {
  56             // We hit the plane of the m_geometry, but outside the m_geometry
  57             return false;
  58         }
  59
  60         const Vector3 q(s.cross(e1));
  61         const float v = f * ray.direction().dot(q);
  62
  63         if ((v < 0.0f) || ((u + v) > 1.0f))
  64         {
  65             // We hit the plane of the triangle, but outside the triangle
  66             return false;
  67         }
  68
  69         const float t = f * e2.dot(q);
  70
  71         if ((t > 0.0f) && (t < distance))
  72         {
  73             // This is a new hit, closer than the previous one
  74             distance = t;
  75
  76             /* baryCoord[0] = 1.0 - u - v;
  77             baryCoord[1] = u;
  78             baryCoord[2] = v; */
  79
  80             return true;
  81         }
  82         // This hit is after the previous hit, so ignore it
  83         return false;
  84     }
  85
  86     class TriBoundFunc
  87     {
  88         public:
  89             TriBoundFunc(std::vector<Vector3>& vert): vertices(vert.begin()) {}
  90             void operator()(const MeshTriangle& tri, G3D::AABox& out) const
  91             {
  92                 G3D::Vector3 lo = vertices[tri.idx0];
  93                 G3D::Vector3 hi = lo;
  94
  95                 lo = (lo.min(vertices[tri.idx1])).min(vertices[tri.idx2]);
  96                 hi = (hi.max(vertices[tri.idx1])).max(vertices[tri.idx2]);
  97
  98                 out = G3D::AABox(lo, hi);
  99             }
 100         protected:
 101             const std::vector<Vector3>::const_iterator vertices;
 102     };
 103
 104     // ===================== WmoLiquid ==================================
 105
 106     WmoLiquid::WmoLiquid(uint32 width, uint32 height, const Vector3& corner, uint32 type):
 107         iTilesX(width), iTilesY(height), iCorner(corner), iType(type)
 108     {
 109         iHeight = new float[(width + 1) * (height + 1)];
 110         iFlags = new uint8[width * height];
 111     }
 112
 113     WmoLiquid::WmoLiquid(const WmoLiquid& other): iHeight(0), iFlags(0)
 114     {
 115         *this = other; // use assignment operator...
 116     }
 117
 118     WmoLiquid::~WmoLiquid()
 119     {
 120         delete[] iHeight;
 121         delete[] iFlags;
 122     }
 123
 124     WmoLiquid& WmoLiquid::operator=(const WmoLiquid& other)
 125     {
 126         if (this == &other)
 127             return *this;
 128         iTilesX = other.iTilesX;
 129         iTilesY = other.iTilesY;
 130         iCorner = other.iCorner;
 131         iType = other.iType;
 132         delete iHeight;
 133         delete iFlags;
 134         if (other.iHeight)
 135         {
 136             iHeight = new float[(iTilesX + 1) * (iTilesY + 1)];
 137             memcpy(iHeight, other.iHeight, (iTilesX + 1) * (iTilesY + 1)*sizeof(float));
 138         }
 139         else
 140             iHeight = 0;
 141         if (other.iFlags)
 142         {
 143             iFlags = new uint8[iTilesX * iTilesY];
 144             memcpy(iFlags, other.iFlags, iTilesX * iTilesY);
 145         }
 146         else
 147             iFlags = 0;
 148         return *this;
 149     }
 150
 151     bool WmoLiquid::GetLiquidHeight(const Vector3& pos, float& liqHeight) const
 152     {
 153         float tx_f = (pos.x - iCorner.x) / LIQUID_TILE_SIZE;
 154         uint32 tx = uint32(tx_f);
 155         if (tx_f < 0.0f || tx >= iTilesX)
 156             return false;
 157         float ty_f = (pos.y - iCorner.y) / LIQUID_TILE_SIZE;
 158         uint32 ty = uint32(ty_f);
 159         if (ty_f < 0.0f || ty >= iTilesY)
 160             return false;
 161
 162         // check if tile shall be used for liquid level
 163         // checking for 0x08 *might* be enough, but disabled tiles always are 0x?F:
 164         if ((iFlags[tx + ty * iTilesX] & 0x0F) == 0x0F)
 165             return false;
 166
 167         // (dx, dy) coordinates inside tile, in [0,1]^2
 168         float dx = tx_f - (float)tx;
 169         float dy = ty_f - (float)ty;
 170
 171         /* Tesselate tile to two triangles (not sure if client does it exactly like this)
 172
 173             ^ dy
 174             |
 175           1 x---------x (1,1)
 176             | (b)   / |
 177             |     /   |
 178             |   /     |
 179             | /   (a) |
 180             x---------x---> dx
 181           0           1
 182         */
 183         const uint32 rowOffset = iTilesX + 1;
 184         if (dx > dy) // case (a)
 185         {
 186             float sx = iHeight[tx + 1 +  ty    * rowOffset] - iHeight[tx   + ty * rowOffset];
 187             float sy = iHeight[tx + 1 + (ty + 1) * rowOffset] - iHeight[tx + 1 + ty * rowOffset];
 188             liqHeight = iHeight[tx + ty * rowOffset] + dx * sx + dy * sy;
 189         }
 190         else // case (b)
 191         {
 192             float sx = iHeight[tx + 1 + (ty + 1) * rowOffset] - iHeight[tx + (ty + 1) * rowOffset];
 193             float sy = iHeight[tx   + (ty + 1) * rowOffset] - iHeight[tx +  ty    * rowOffset];
 194             liqHeight = iHeight[tx + ty * rowOffset] + dx * sx + dy * sy;
 195         }
 196         return true;
 197     }
 198
 199     uint32 WmoLiquid::GetFileSize()
 200     {
 201         return 2 * sizeof(uint32) +
 202                sizeof(Vector3) +
 203                (iTilesX + 1) * (iTilesY + 1) * sizeof(float) +
 204                iTilesX * iTilesY;
 205     }
 206
 207     bool WmoLiquid::writeToFile(FILE* wf)
 208     {
 209         bool result = true;
 210         if (result && fwrite(&iTilesX, sizeof(uint32), 1, wf) != 1) result = false;
 211         if (result && fwrite(&iTilesY, sizeof(uint32), 1, wf) != 1) result = false;
 212         if (result && fwrite(&iCorner, sizeof(Vector3), 1, wf) != 1) result = false;
 213         if (result && fwrite(&iType, sizeof(uint32), 1, wf) != 1) result = false;
 214         uint32 size = (iTilesX + 1) * (iTilesY + 1);
 215         if (result && fwrite(iHeight, sizeof(float), size, wf) != size) result = false;
 216         size = iTilesX * iTilesY;
 217         if (result && fwrite(iFlags, sizeof(uint8), size, wf) != size) result = false;
 218         return result;
 219     }
 220
 221     bool WmoLiquid::readFromFile(FILE* rf, WmoLiquid*& out)
 222     {
 223         bool result = true;
 224         WmoLiquid* liquid = new WmoLiquid();
 225         if (result && fread(&liquid->iTilesX, sizeof(uint32), 1, rf) != 1) result = false;
 226         if (result && fread(&liquid->iTilesY, sizeof(uint32), 1, rf) != 1) result = false;
 227         if (result && fread(&liquid->iCorner, sizeof(Vector3), 1, rf) != 1) result = false;
 228         if (result && fread(&liquid->iType, sizeof(uint32), 1, rf) != 1) result = false;
 229         uint32 size = (liquid->iTilesX + 1) * (liquid->iTilesY + 1);
 230         liquid->iHeight = new float[size];
 231         if (result && fread(liquid->iHeight, sizeof(float), size, rf) != size) result = false;
 232         size = liquid->iTilesX * liquid->iTilesY;
 233         liquid->iFlags = new uint8[size];
 234         if (result && fread(liquid->iFlags, sizeof(uint8), size, rf) != size) result = false;
 235         if (!result)
 236             delete liquid;
 237         out = liquid;
 238         return result;
 239     }
 240
 241     // ===================== GroupModel ==================================
 242
 243     GroupModel::GroupModel(const GroupModel& other):
 244         iBound(other.iBound), iMogpFlags(other.iMogpFlags), iGroupWMOID(other.iGroupWMOID),
 245         vertices(other.vertices), triangles(other.triangles), meshTree(other.meshTree), iLiquid(0)
 246     {
 247         if (other.iLiquid)
 248             iLiquid = new WmoLiquid(*other.iLiquid);
 249     }
 250
 251     void GroupModel::setMeshData(std::vector<Vector3>& vert, std::vector<MeshTriangle>& tri)
 252     {
 253         vertices.swap(vert);
 254         triangles.swap(tri);
 255         TriBoundFunc bFunc(vertices);
 256         meshTree.build(triangles, bFunc);
 257     }
 258
 259     bool GroupModel::writeToFile(FILE* wf)
 260     {
 261         bool result = true;
 262         uint32 chunkSize, count;
 263
 264         if (result && fwrite(&iBound, sizeof(G3D::AABox), 1, wf) != 1) result = false;
 265         if (result && fwrite(&iMogpFlags, sizeof(uint32), 1, wf) != 1) result = false;
 266         if (result && fwrite(&iGroupWMOID, sizeof(uint32), 1, wf) != 1) result = false;
 267
 268         // write vertices
 269         if (result && fwrite("VERT", 1, 4, wf) != 4) result = false;
 270         count = vertices.size();
 271         chunkSize = sizeof(uint32) + sizeof(Vector3) * count;
 272         if (result && fwrite(&chunkSize, sizeof(uint32), 1, wf) != 1) result = false;
 273         if (result && fwrite(&count, sizeof(uint32), 1, wf) != 1) result = false;
 274         if (!count) // models without (collision) geometry end here, unsure if they are useful
 275             return result;
 276         if (result && fwrite(&vertices[0], sizeof(Vector3), count, wf) != count) result = false;
 277
 278         // write triangle mesh
 279         if (result && fwrite("TRIM", 1, 4, wf) != 4) result = false;
 280         count = triangles.size();
 281         chunkSize = sizeof(uint32) + sizeof(MeshTriangle) * count;
 282         if (result && fwrite(&chunkSize, sizeof(uint32), 1, wf) != 1) result = false;
 283         if (result && fwrite(&count, sizeof(uint32), 1, wf) != 1) result = false;
 284         if (result && fwrite(&triangles[0], sizeof(MeshTriangle), count, wf) != count) result = false;
 285
 286         // write mesh BIH
 287         if (result && fwrite("MBIH", 1, 4, wf) != 4) result = false;
 288         if (result) result = meshTree.writeToFile(wf);
 289
 290         // write liquid data
 291         if (result && fwrite("LIQU", 1, 4, wf) != 4) result = false;
 292         if (!iLiquid)
 293         {
 294             chunkSize = 0;
 295             if (result && fwrite(&chunkSize, sizeof(uint32), 1, wf) != 1) result = false;
 296             return result;
 297         }
 298         chunkSize = iLiquid->GetFileSize();
 299         if (result && fwrite(&chunkSize, sizeof(uint32), 1, wf) != 1) result = false;
 300         if (result) result = iLiquid->writeToFile(wf);
 301
 302         return result;
 303     }
 304
 305     bool GroupModel::readFromFile(FILE* rf)
 306     {
 307         char chunk[8];
 308         bool result = true;
 309         uint32 chunkSize, count;
 310         triangles.clear();
 311         vertices.clear();
 312         delete iLiquid;
 313         iLiquid = 0;
 314
 315         if (result && fread(&iBound, sizeof(G3D::AABox), 1, rf) != 1) result = false;
 316         if (result && fread(&iMogpFlags, sizeof(uint32), 1, rf) != 1) result = false;
 317         if (result && fread(&iGroupWMOID, sizeof(uint32), 1, rf) != 1) result = false;
 318
 319         // read vertices
 320         if (result && !readChunk(rf, chunk, "VERT", 4)) result = false;
 321         if (result && fread(&chunkSize, sizeof(uint32), 1, rf) != 1) result = false;
 322         if (result && fread(&count, sizeof(uint32), 1, rf) != 1) result = false;
 323         if (!count) // models without (collision) geometry end here, unsure if they are useful
 324             return result;
 325         if (result) vertices.resize(count);
 326         if (result && fread(&vertices[0], sizeof(Vector3), count, rf) != count) result = false;
 327
 328         // read triangle mesh
 329         if (result && !readChunk(rf, chunk, "TRIM", 4)) result = false;
 330         if (result && fread(&chunkSize, sizeof(uint32), 1, rf) != 1) result = false;
 331         if (result && fread(&count, sizeof(uint32), 1, rf) != 1) result = false;
 332         if (result) triangles.resize(count);
 333         if (result && fread(&triangles[0], sizeof(MeshTriangle), count, rf) != count) result = false;
 334
 335         // read mesh BIH
 336         if (result && !readChunk(rf, chunk, "MBIH", 4)) result = false;
 337         if (result) result = meshTree.readFromFile(rf);
 338
 339         // write liquid data
 340         if (result && !readChunk(rf, chunk, "LIQU", 4)) result = false;
 341         if (result && fread(&chunkSize, sizeof(uint32), 1, rf) != 1) result = false;
 342         if (result && chunkSize > 0)
 343             result = WmoLiquid::readFromFile(rf, iLiquid);
 344         return result;
 345     }
 346
 347     struct GModelRayCallback
 348     {
 349         GModelRayCallback(const std::vector<MeshTriangle>& tris, const std::vector<Vector3>& vert):
 350             vertices(vert.begin()), triangles(tris.begin()), hit(false) {}
 351         bool operator()(const G3D::Ray& ray, uint32 entry, float& distance, bool pStopAtFirstHit)
 352         {
 353             bool result = IntersectTriangle(triangles[entry], vertices, ray, distance);
 354             if (result)  hit = true;
 355             return hit;
 356         }
 357         std::vector<Vector3>::const_iterator vertices;
 358         std::vector<MeshTriangle>::const_iterator triangles;
 359         bool hit;
 360     };
 361
 362     bool GroupModel::IntersectRay(const G3D::Ray& ray, float& distance, bool stopAtFirstHit) const
 363     {
 364         if (!triangles.size())
 365             return false;
 366         GModelRayCallback callback(triangles, vertices);
 367         meshTree.intersectRay(ray, callback, distance, stopAtFirstHit);
 368         return callback.hit;
 369     }
 370
 371     bool GroupModel::IsInsideObject(const Vector3& pos, const Vector3& down, float& z_dist) const
 372     {
 373         if (!triangles.size() || !iBound.contains(pos))
 374             return false;
 375         GModelRayCallback callback(triangles, vertices);
 376         Vector3 rPos = pos - 0.1f * down;
 377         float dist = G3D::inf();
 378         G3D::Ray ray(rPos, down);
 379         bool hit = IntersectRay(ray, dist, false);
 380         if (hit)
 381             z_dist = dist - 0.1f;
 382         return hit;
 383     }
 384
 385     bool GroupModel::GetLiquidLevel(const Vector3& pos, float& liqHeight) const
 386     {
 387         if (iLiquid)
 388             return iLiquid->GetLiquidHeight(pos, liqHeight);
 389         return false;
 390     }
 391
 392     uint32 GroupModel::GetLiquidType() const
 393     {
 394         // convert to type mask, matching MAP_LIQUID_TYPE_* defines in Map.h
 395         if (iLiquid)
 396             return (1 << iLiquid->GetType());
 397         return 0;
 398     }
 399
 400     // ===================== WorldModel ==================================
 401
 402     void WorldModel::setGroupModels(std::vector<GroupModel>& models)
 403     {
 404         groupModels.swap(models);
 405         groupTree.build(groupModels, BoundsTrait<GroupModel>::getBounds, 1);
 406     }
 407
 408     struct WModelRayCallBack
 409     {
 410         WModelRayCallBack(const std::vector<GroupModel>& mod): models(mod.begin()), hit(false) {}
 411         bool operator()(const G3D::Ray& ray, uint32 entry, float& distance, bool pStopAtFirstHit)
 412         {
 413             bool result = models[entry].IntersectRay(ray, distance, pStopAtFirstHit);
 414             if (result)  hit = true;
 415             return hit;
 416         }
 417         std::vector<GroupModel>::const_iterator models;
 418         bool hit;
 419     };
 420
 421     bool WorldModel::IntersectRay(const G3D::Ray& ray, float& distance, bool stopAtFirstHit) const
 422     {
 423         // small M2 workaround, maybe better make separate class with virtual intersection funcs
 424         // in any case, there's no need to use a bound tree if we only have one submodel
 425         if (groupModels.size() == 1)
 426             return groupModels[0].IntersectRay(ray, distance, stopAtFirstHit);
 427
 428         WModelRayCallBack isc(groupModels);
 429         groupTree.intersectRay(ray, isc, distance, stopAtFirstHit);
 430         return isc.hit;
 431     }
 432
 433     class WModelAreaCallback
 434     {
 435         public:
 436             WModelAreaCallback(const std::vector<GroupModel>& vals, const Vector3& down):
 437                 prims(vals.begin()), hit(vals.end()), minVol(G3D::inf()), zDist(G3D::inf()), zVec(down) {}
 438             std::vector<GroupModel>::const_iterator prims;
 439             std::vector<GroupModel>::const_iterator hit;
 440             float minVol;
 441             float zDist;
 442             Vector3 zVec;
 443             void operator()(const Vector3& point, uint32 entry)
 444             {
 445                 float group_Z;
 446                 // float pVol = prims[entry].GetBound().volume();
 447                 // if(pVol < minVol)
 448                 //{
 449                 /* if (prims[entry].iBound.contains(point)) */
 450                 if (prims[entry].IsInsideObject(point, zVec, group_Z))
 451                 {
 452                     // minVol = pVol;
 453                     // hit = prims + entry;
 454                     if (group_Z < zDist)
 455                     {
 456                         zDist = group_Z;
 457                         hit = prims + entry;
 458                     }
 459 #ifdef VMAP_DEBUG
 460                     const GroupModel& gm = prims[entry];
 461                     printf("%10u %8X %7.3f,%7.3f,%7.3f | %7.3f,%7.3f,%7.3f | z=%f, p_z=%f\n", gm.GetWmoID(), gm.GetMogpFlags(),
 462                            gm.GetBound().low().x, gm.GetBound().low().y, gm.GetBound().low().z,
 463                            gm.GetBound().high().x, gm.GetBound().high().y, gm.GetBound().high().z, group_Z, point.z);
 464 #endif
 465                 }
 466                 //}
 467                 // std::cout << "trying to intersect '" << prims[entry].name << "'\n";
 468             }
 469     };
 470
 471     bool WorldModel::IntersectPoint(const G3D::Vector3& p, const G3D::Vector3& down, float& dist, AreaInfo& info) const
 472     {
 473         if (!groupModels.size())
 474             return false;
 475         WModelAreaCallback callback(groupModels, down);
 476         groupTree.intersectPoint(p, callback);
 477         if (callback.hit != groupModels.end())
 478         {
 479             info.rootId = RootWMOID;
 480             info.groupId = callback.hit->GetWmoID();
 481             info.flags = callback.hit->GetMogpFlags();
 482             info.result = true;
 483             dist = callback.zDist;
 484             return true;
 485         }
 486         return false;
 487     }
 488
 489     bool WorldModel::GetLocationInfo(const G3D::Vector3& p, const G3D::Vector3& down, float& dist, LocationInfo& info) const
 490     {
 491         if (!groupModels.size())
 492             return false;
 493         WModelAreaCallback callback(groupModels, down);
 494         groupTree.intersectPoint(p, callback);
 495         if (callback.hit != groupModels.end())
 496         {
 497             info.hitModel = &(*callback.hit);
 498             dist = callback.zDist;
 499             return true;
 500         }
 501         return false;
 502     }
 503
 504     bool WorldModel::writeFile(const std::string& filename)
 505     {
 506         FILE* wf = fopen(filename.c_str(), "wb");
 507         if (!wf)
 508             return false;
 509
 510         uint32 chunkSize, count;
 511         bool result = fwrite(VMAP_MAGIC, 1, 8, wf) == 8;
 512         if (result && fwrite("WMOD", 1, 4, wf) != 4) result = false;
 513         chunkSize = sizeof(uint32) + sizeof(uint32);
 514         if (result && fwrite(&chunkSize, sizeof(uint32), 1, wf) != 1) result = false;
 515         if (result && fwrite(&RootWMOID, sizeof(uint32), 1, wf) != 1) result = false;
 516
 517         // write group models
 518         count = groupModels.size();
 519         if (count)
 520         {
 521             if (result && fwrite("GMOD", 1, 4, wf) != 4) result = false;
 522             // chunkSize = sizeof(uint32)+ sizeof(GroupModel)*count;
 523             // if (result && fwrite(&chunkSize, sizeof(uint32), 1, wf) != 1) result = false;
 524             if (result && fwrite(&count, sizeof(uint32), 1, wf) != 1) result = false;
 525             for (uint32 i = 0; i < groupModels.size() && result; ++i)
 526                 result = groupModels[i].writeToFile(wf);
 527
 528             // write group BIH
 529             if (result && fwrite("GBIH", 1, 4, wf) != 4) result = false;
 530             if (result) result = groupTree.writeToFile(wf);
 531         }
 532
 533         fclose(wf);
 534         return result;
 535     }
 536
 537     bool WorldModel::readFile(const std::string& filename)
 538     {
 539         FILE* rf = fopen(filename.c_str(), "rb");
 540         if (!rf)
 541             return false;
 542
 543         bool result = true;
 544         uint32 chunkSize, count;
 545         char chunk[8];                          // Ignore the added magic header
 546         if (!readChunk(rf, chunk, VMAP_MAGIC, 8)) result = false;
 547
 548         if (result && !readChunk(rf, chunk, "WMOD", 4)) result = false;
 549         if (result && fread(&chunkSize, sizeof(uint32), 1, rf) != 1) result = false;
 550         if (result && fread(&RootWMOID, sizeof(uint32), 1, rf) != 1) result = false;
 551
 552         // read group models
 553         if (result && readChunk(rf, chunk, "GMOD", 4))
 554         {
 555             // if (fread(&chunkSize, sizeof(uint32), 1, rf) != 1) result = false;
 556
 557             if (result && fread(&count, sizeof(uint32), 1, rf) != 1) result = false;
 558             if (result) groupModels.resize(count);
 559             // if (result && fread(&groupModels[0], sizeof(GroupModel), count, rf) != count) result = false;
 560             for (uint32 i = 0; i < count && result; ++i)
 561                 result = groupModels[i].readFromFile(rf);
 562
 563             // read group BIH
 564             if (result && !readChunk(rf, chunk, "GBIH", 4)) result = false;
 565             if (result) result = groupTree.readFromFile(rf);
 566         }
 567
 568         fclose(rf);
 569         return result;
 570     }
 571 }