nel/src/3d/packed_world.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "std3d.h"
  18 //
  19 #include "nel/3d/packed_world.h"
  20 //
  21 #include "nel/misc/grid_traversal.h"
  22
  23
  24 using namespace NLMISC;
  25
  26 #ifdef DEBUG_NEW
  27 #define new DEBUG_NEW
  28 #endif
  29
  30 namespace NL3D
  31 {
  32
  33
  34 // *************************************************************************************************
  35 void CPackedWorld::build(std::vector<TPackedZoneBaseSPtr> &packedZones)
  36 {
  37         _ZoneGrid.clear();
  38         _Zones.clear();
  39         if (packedZones.empty()) return;
  40         CAABBox box;
  41         nlassert(packedZones[0]);
  42         box = packedZones[0]->Box;
  43         for(uint k = 1; k < packedZones.size(); ++k)
  44         {
  45                 nlassert(packedZones[k]);
  46                 box.extend(packedZones[k]->Box.getMin());
  47                 box.extend(packedZones[k]->Box.getMax());
  48         }
  49
  50         _ZoneMinX = (sint32) floorf(box.getMin().x / 160.f);
  51         _ZoneMinY = (sint32) floorf(box.getMin().y / 160.f);
  52         //
  53         sint32 zoneMaxX = (sint32) floorf(box.getMax().x / 160.f);
  54         sint32 zoneMaxY = (sint32) floorf(box.getMax().y / 160.f);
  55         //
  56         _ZoneGrid.init(zoneMaxX - _ZoneMinX + 1, zoneMaxY - _ZoneMinY + 1);
  57         _Zones.resize(packedZones.size());
  58         //
  59         for(uint k = 0; k < packedZones.size(); ++k)
  60         {
  61                 CZoneInfo zi;
  62                 zi.Zone = packedZones[k];
  63                 zi.RaytraceCounter = 0;
  64                 _Zones[k] = zi;
  65                 sint zoneMinX = (sint) floorf(packedZones[k]->Box.getMin().x / 160.f) - (sint) _ZoneMinX;
  66                 sint zoneMinY = (sint) floorf(packedZones[k]->Box.getMin().y / 160.f) - (sint) _ZoneMinY;
  67                 sint zoneMaxX = (sint) floorf(packedZones[k]->Box.getMax().x / 160.f)  - (sint) _ZoneMinX;
  68                 sint zoneMaxY = (sint) floorf(packedZones[k]->Box.getMax().y / 160.f)  - (sint) _ZoneMinY;
  69                 for (sint y = zoneMinY; y <= zoneMaxY; ++y)
  70                 {
  71                         if (y < 0) continue;
  72                         if (y >= (sint) _ZoneGrid.getHeight()) break;
  73                         for (sint x = zoneMinX; x <= zoneMaxX; ++x)
  74                         {
  75                                 if (x < 0) continue;
  76                                 if (x >= (sint) _ZoneGrid.getWidth()) break;
  77                                 _ZoneGrid(x, y).IDs.push_back((uint32) k);
  78                         }
  79                 }
  80         }
  81         _RaytraceCounter = std::numeric_limits<uint32>::max();
  82 }
  83
  84 // *************************************************************************************************
  85 bool CPackedWorld::raytrace(const NLMISC::CVector &start, const NLMISC::CVector &end, CVector &inter, std::vector<NLMISC::CTriangle> *testedTriangles /*= NULL*/, NLMISC::CVector *normal)
  86 {
  87         if (_ZoneGrid.empty()) return false;
  88         ++_RaytraceCounter;
  89         float bestDist = FLT_MAX;
  90         CVector bestNormal(CVector::Null);
  91         CVector currEnd = end;
  92         CVector currInter;
  93         if (_RaytraceCounter == std::numeric_limits<uint32>::max())
  94         {
  95                 for(uint k = 0; k < _Zones.size(); ++k)
  96                 {
  97                         _Zones[k].RaytraceCounter = 0;
  98                 }
  99         }
 100         sint currX, currY;
 101         CVector2f start2f(start.x / 160.f, start.y / 160.f);
 102         CVector2f dir2f((end.x - start.x) / 160.f, (end.y - start.y) / 160.f);
 103         CGridTraversal::startTraverse(start2f, currX, currY);
 104         do
 105         {
 106                 sint x = currX - (sint) _ZoneMinX;
 107                 sint y = currY - (sint) _ZoneMinY;
 108                 if (x < 0) continue;
 109                 if (y < 0) continue;
 110                 if (x >= (sint) _ZoneGrid.getWidth()) continue;
 111                 if (y >= (sint) _ZoneGrid.getHeight()) continue;
 112                 std::vector<uint32> &currZoneList = _ZoneGrid(x, y).IDs;
 113                 for(uint k = 0; k < currZoneList.size(); ++k)
 114                 {
 115                         if (_Zones[currZoneList[k]].RaytraceCounter != _RaytraceCounter) // already visited
 116                         {
 117                                 NLMISC::CVector normalTmp;
 118                                 if (_Zones[currZoneList[k]].Zone->raytrace(start, currEnd, currInter, testedTriangles, &normalTmp))
 119                                 {
 120                                         float dist = (currInter - start).norm();
 121                                         if (dist < bestDist)
 122                                         {
 123                                                 bestNormal = normalTmp;
 124                                                 bestDist = dist;
 125                                                 inter = currInter;
 126                                                 currEnd = currInter; // during search, just seek hit that are nearest
 127                                         }
 128                                 }
 129                                 _Zones[currZoneList[k]].RaytraceCounter = _RaytraceCounter;
 130                         }
 131                 }
 132                 if (bestDist != FLT_MAX)
 133                 {
 134                         if (normal)
 135                         {
 136                                 *normal = bestNormal;
 137                         }
 138                         return true;
 139                 }
 140         }
 141         while (CGridTraversal::traverse(start2f, dir2f, currX, currY));
 142         return false;
 143 }
 144
 145 // *************************************************************************************************
 146 void CPackedWorld::getZones(std::vector<TPackedZoneBaseSPtr> &zones)
 147 {
 148         zones.clear();
 149         for(uint k = 0; k < _Zones.size(); ++k)
 150         {
 151                 zones.push_back(_Zones[k].Zone);
 152         }
 153 }
 154
 155 // *************************************************************************************************
 156 void CPackedWorld::serialZoneNames(NLMISC::IStream &f)
 157 {
 158         f.serialVersion(1);
 159         f.serialCheck(NELID("OWPA"));
 160         f.serialCont(ZoneNames);
 161 }
 162
 163 // *************************************************************************************************
 164 void CPackedWorld::serial(NLMISC::IStream &f)
 165 {
 166         serialZoneNames(f);
 167         f.serialCont(_Zones);
 168         f.serial(_ZoneGrid);
 169         f.serial(_ZoneMinX);
 170         f.serial(_ZoneMinY);
 171 }
 172
 173 // *************************************************************************************************
 174 void CPackedWorld::select(const NLMISC::CPolygon2D &poly, std::vector<NLMISC::CTriangle> &selectedTriangles) const
 175 {
 176         selectedTriangles.clear();
 177         // compute covered zones
 178         NLMISC::CPolygon2D zonePoly = poly;
 179         for (uint k = 0; k < zonePoly.Vertices.size(); ++k)
 180         {
 181                 zonePoly.Vertices[k].x = zonePoly.Vertices[k].x / 160.f - (float) _ZoneMinX;
 182                 zonePoly.Vertices[k].y = zonePoly.Vertices[k].y / 160.f - (float) _ZoneMinY;
 183         }
 184         NLMISC::CPolygon2D::TRasterVect borders;
 185         sint minY;
 186         zonePoly.computeOuterBorders(borders, minY);
 187         for (sint y = minY; y < (sint) (minY + borders.size()); ++y)
 188         {
 189                 if (y < 0 || y >= (sint) _ZoneGrid.getHeight()) continue;
 190                 for (sint x = borders[y - minY].first; x <= borders[y - minY].second; ++x)
 191                 {
 192                         if (x < 0 || x >= (sint) _ZoneGrid.getWidth()) continue;
 193                         {
 194                                 const CZoneIndexList &zil = _ZoneGrid(x, y);
 195                                 for (uint k = 0; k < zil.IDs.size(); ++k)
 196                                 {
 197                                         _Zones[zil.IDs[k]].Zone->appendSelection(poly, selectedTriangles);
 198                                 }
 199                         }
 200                 }
 201         }
 202 }
 203
 204
 205 } // Nl3D