simgear/scene/tgdb/BucketBox.hxx

   1 // BucketBox.cxx -- Helper for on demand database paging.
   2 //
   3 // Copyright (C) 2010 - 2011  Mathias Froehlich
   4 //
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License as
   7 // published by the Free Software Foundation; either version 2 of the
   8 // License, or (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful, but
  11 // WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 // General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  18 //
  19
  20 #ifndef _BUCKETBOX_HXX
  21 #define _BUCKETBOX_HXX
  22
  23 #include <cassert>
  24 #include <istream>
  25 #include <ostream>
  26
  27 #include <simgear/bucket/newbucket.hxx>
  28 #include <simgear/math/SGGeometry.hxx>
  29
  30 namespace simgear {
  31
  32 #define Elements(x) (sizeof(x)/sizeof((x)[0]))
  33
  34 // 2*5*3*3 * 4 = 360
  35 static const unsigned _lonFactors[] = { 2, 5, 3, 3, 2, 2, /* sub degree */ 2, 2, 2 };
  36 // 3*3*5 * 4 = 180
  37 static const unsigned _latFactors[] = { 3, 5, 1, 3, 2, 2, /* sub degree */ 2, 2, 2 };
  38
  39 static unsigned product(const unsigned* factors, unsigned count)
  40 {
  41     unsigned index = 1;
  42     while (count--)
  43         index *= *factors++;
  44     return index;
  45 }
  46
  47 /// /Rectangular/ sub part of the earths surface.
  48 /// Stored with offset point in lon/lat and width and height.
  49 /// The values are stored in a fixed point format having 3 fractional
  50 /// bits which matches the SGBuckets maximum tile resolution.
  51 ///
  52 /// Notable /design/ decision:
  53 /// * The longitude maps to the interval [-180,180[.
  54 ///   The latitude maps to the interval [-90,90].
  55 ///   This works now that the tiles do no longer cut
  56 ///   neither the 180deg nor the 0deg boundary.
  57 /// * This is not meant to be an API class for simgear. This is
  58 ///   just an internal tool that I would like to keep in the SPT loader.
  59 ///   But I want to have coverage somehow tested with the usual unit
  60 ///   tests, which is the reason to have this file split out.
  61 ///
  62 class BucketBox {
  63 public:
  64     BucketBox()
  65     { _offset[0] = 0; _offset[1] = 0; _size[0] = 0; _size[1] = 0; }
  66     BucketBox(double lon, double lat, double width, double height)
  67     {
  68         _offset[0] = _longitudeDegToOffset(lon);
  69         _offset[1] = _latitudeDegToOffset(lat);
  70         _size[0] = _degToSize(width);
  71         _size[1] = _degToSize(height);
  72     }
  73     BucketBox(const BucketBox& bucketBox)
  74     {
  75         _offset[0] = bucketBox._offset[0];
  76         _offset[1] = bucketBox._offset[1];
  77         _size[0] = bucketBox._size[0];
  78         _size[1] = bucketBox._size[1];
  79     }
  80
  81     BucketBox& operator=(const BucketBox& bucketBox)
  82     {
  83         _offset[0] = bucketBox._offset[0];
  84         _offset[1] = bucketBox._offset[1];
  85         _size[0] = bucketBox._size[0];
  86         _size[1] = bucketBox._size[1];
  87         return *this;
  88     }
  89
  90     bool empty() const
  91     { return _size[0] == 0 || _size[1] == 0; }
  92
  93     unsigned getOffset(unsigned i) const
  94     { return _offset[i]; }
  95     void setOffset(unsigned i, unsigned offset)
  96     { _offset[i] = offset; }
  97
  98     unsigned getSize(unsigned i) const
  99     { return _size[i]; }
 100     void setSize(unsigned i, unsigned size)
 101     { _size[i] = size; }
 102
 103     double getLongitudeDeg() const
 104     { return _offsetToLongitudeDeg(_offset[0]); }
 105     void setLongitudeDeg(double lon)
 106     { _offset[0] = _longitudeDegToOffset(lon); }
 107
 108     double getLatitudeDeg() const
 109     { return _offsetToLatitudeDeg(_offset[1]); }
 110     void setLatitudeDeg(double lat)
 111     { _offset[1] = _latitudeDegToOffset(lat); }
 112
 113     double getWidthDeg() const
 114     { return _sizeToDeg(_size[0]); }
 115     void setWidthDeg(double width)
 116     { _size[0] = _degToSize(width); }
 117
 118     double getHeightDeg() const
 119     { return _sizeToDeg(_size[1]); }
 120     void setHeightDeg(double height)
 121     { _size[1] = _degToSize(height); }
 122
 123     bool getWidthIsBucketSize() const
 124     {
 125         if (_size[0] <= _bucketSpanAtOffset(_offset[1]))
 126             return true;
 127         return _size[0] <= _bucketSpanAtOffset(_offset[1] + _size[1] - 1);
 128     }
 129
 130     bool getHeightIsBucketSize() const
 131     { return _size[1] == 1; }
 132     bool getIsBucketSize() const
 133     { return getHeightIsBucketSize() && getWidthIsBucketSize(); }
 134
 135     SGBucket getBucket() const
 136     {
 137         // left align longitude offsets
 138         unsigned offset = _offset[0] - _offset[0] % _bucketSpanAtOffset(_offset[1]);
 139         return SGBucket(_offsetToLongitudeDeg(offset), _offsetToLatitudeDeg(_offset[1]));
 140     }
 141
 142     BucketBox getParentBox(unsigned level) const
 143     {
 144         BucketBox box;
 145         unsigned plon = product(_lonFactors + level, Elements(_lonFactors) - level);
 146         unsigned plat = product(_latFactors + level, Elements(_latFactors) - level);
 147         box._offset[0] = _offset[0] - _offset[0] % plon;
 148         box._offset[0] = _normalizeLongitude(box._offset[0]);
 149         box._offset[1] = _offset[1] - _offset[1] % plat;
 150         box._size[0] = plon;
 151         box._size[1] = plat;
 152
 153         return box;
 154     }
 155
 156     BucketBox getSubBoxHeight(unsigned j, unsigned level) const
 157     {
 158         assert(0 < level);
 159         BucketBox box;
 160         unsigned plat = product(_latFactors + level, Elements(_latFactors) - level);
 161         unsigned plat1 = plat*_latFactors[level - 1];
 162         box._offset[0] = _offset[0];
 163         box._offset[1] = _offset[1] - _offset[1] % plat1 + j*plat;
 164         box._size[0] = _size[0];
 165         box._size[1] = plat;
 166
 167         return box;
 168     }
 169
 170     BucketBox getSubBoxWidth(unsigned i, unsigned level) const
 171     {
 172         assert(0 < level);
 173         BucketBox box;
 174         unsigned plon = product(_lonFactors + level, Elements(_lonFactors) - level);
 175         unsigned plon1 = plon*_lonFactors[level - 1];
 176         box._offset[0] = _offset[0] - _offset[0] % plon1 + i*plon;
 177         box._offset[1] = _offset[1];
 178         box._size[0] = plon;
 179         box._size[1] = _size[1];
 180
 181         box._offset[0] = _normalizeLongitude(box._offset[0]);
 182
 183         return box;
 184     }
 185
 186     unsigned getWidthLevel() const
 187     { return _getLevel(_lonFactors, Elements(_lonFactors), _offset[0], _offset[0] + _size[0]); }
 188     unsigned getHeightLevel() const
 189     { return _getLevel(_latFactors, Elements(_latFactors), _offset[1], _offset[1] + _size[1]); }
 190
 191     unsigned getWidthIncrement(unsigned level) const
 192     {
 193         level = SGMisc<unsigned>::clip(level, 5, Elements(_lonFactors));
 194         return product(_lonFactors + level, Elements(_lonFactors) - level);
 195     }
 196     unsigned getHeightIncrement(unsigned level) const
 197     {
 198         level = SGMisc<unsigned>::clip(level, 5, Elements(_latFactors));
 199         return product(_latFactors + level, Elements(_latFactors) - level);
 200     }
 201
 202     unsigned getStartLevel() const
 203     {
 204         if (getWidthIsBucketSize())
 205             return getHeightLevel();
 206         return std::min(getWidthLevel(), getHeightLevel());
 207     }
 208
 209     SGSpheref getBoundingSphere() const
 210     {
 211         SGSpheref sphere;
 212         unsigned incx = 10*8;
 213         for (unsigned i = 0; incx != 0; i += incx) {
 214             unsigned incy = 10*8;
 215             for (unsigned j = 0; incy != 0; j += incy) {
 216                 sphere.expandBy(SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, -1000)));
 217                 sphere.expandBy(SGVec3f::fromGeod(_offsetToGeod(_offset[0] + i, _offset[1] + j, 10000)));
 218                 incy = std::min(incy, _size[1] - j);
 219             }
 220             incx = std::min(incx, _size[0] - i);
 221         }
 222         return SGSpheref(sphere.getCenter(), sphere.getRadius() + 5000);
 223     }
 224
 225     // Split the current box into up to two boxes that do not cross the 360 deg border.
 226     unsigned periodicSplit(BucketBox bucketBoxList[2]) const
 227     {
 228         if (empty())
 229             return 0;
 230
 231         bucketBoxList[0] = *this;
 232         bucketBoxList[0]._offset[0] = _normalizeLongitude(bucketBoxList[0]._offset[0]);
 233         if (bucketBoxList[0]._offset[0] + bucketBoxList[0]._size[0] <= 360*8)
 234             return 1;
 235
 236         bucketBoxList[1] = bucketBoxList[0];
 237         bucketBoxList[0]._size[0] = 360*8 - bucketBoxList[0]._offset[0];
 238
 239         bucketBoxList[1]._offset[0] = 0;
 240         bucketBoxList[1]._size[0] = _size[0] - bucketBoxList[0]._size[0];
 241
 242         return 2;
 243     }
 244
 245     unsigned getSubDivision(BucketBox bucketBoxList[], unsigned bucketBoxListSize) const
 246     {
 247         unsigned numTiles = 0;
 248
 249         // Quad tree like structure in x and y direction
 250         unsigned widthLevel = getWidthLevel();
 251         unsigned heightLevel = getHeightLevel();
 252
 253         unsigned level;
 254         if (getWidthIsBucketSize()) {
 255             level = heightLevel;
 256         } else {
 257             level = std::min(widthLevel, heightLevel);
 258         }
 259         for (unsigned j = 0; j < _latFactors[level]; ++j) {
 260             BucketBox heightSplitBox = getSubBoxHeight(j, level + 1);
 261
 262             heightSplitBox = _intersection(*this, heightSplitBox);
 263             if (heightSplitBox.empty())
 264                 continue;
 265
 266             if (heightSplitBox.getWidthIsBucketSize()) {
 267                 bucketBoxList[numTiles++] = heightSplitBox;
 268                 assert(numTiles <= bucketBoxListSize);
 269             } else {
 270                 for (unsigned i = 0; i < _lonFactors[widthLevel]; ++i) {
 271                     BucketBox childBox = _intersection(heightSplitBox, heightSplitBox.getSubBoxWidth(i, widthLevel + 1));
 272                     if (childBox.empty())
 273                         continue;
 274
 275                     bucketBoxList[numTiles++] = childBox;
 276                     assert(numTiles <= bucketBoxListSize);
 277                 }
 278             }
 279         }
 280         return numTiles;
 281     }
 282
 283     unsigned getTileTriangles(unsigned i, unsigned j, unsigned width, unsigned height,
 284                               SGVec3f points[6], SGVec3f normals[6], SGVec2f texCoords[6]) const
 285     {
 286         unsigned numPoints = 0;
 287
 288         unsigned x0 = _offset[0] + i;
 289         unsigned x1 = x0 + width;
 290
 291         unsigned y0 = _offset[1] + j;
 292         unsigned y1 = y0 + height;
 293
 294         SGGeod p00 = _offsetToGeod(x0, y0, 0);
 295         SGVec3f v00 = SGVec3f::fromGeod(p00);
 296         SGVec3f n00 = SGQuatf::fromLonLat(p00).backTransform(SGVec3f(0, 0, -1));
 297         SGVec2f t00(x0*1.0/(360*8), y0*1.0/(180*8));
 298
 299         SGGeod p10 = _offsetToGeod(x1, y0, 0);
 300         SGVec3f v10 = SGVec3f::fromGeod(p10);
 301         SGVec3f n10 = SGQuatf::fromLonLat(p10).backTransform(SGVec3f(0, 0, -1));
 302         SGVec2f t10(x1*1.0/(360*8), y0*1.0/(180*8));
 303
 304         SGGeod p11 = _offsetToGeod(x1, y1, 0);
 305         SGVec3f v11 = SGVec3f::fromGeod(p11);
 306         SGVec3f n11 = SGQuatf::fromLonLat(p11).backTransform(SGVec3f(0, 0, -1));
 307         SGVec2f t11(x1*1.0/(360*8), y1*1.0/(180*8));
 308
 309         SGGeod p01 = _offsetToGeod(x0, y1, 0);
 310         SGVec3f v01 = SGVec3f::fromGeod(p01);
 311         SGVec3f n01 = SGQuatf::fromLonLat(p01).backTransform(SGVec3f(0, 0, -1));
 312         SGVec2f t01(x0*1.0/(360*8), y1*1.0/(180*8));
 313
 314         if (y0 != 0) {
 315             points[numPoints] = v00;
 316             normals[numPoints] = n00;
 317             texCoords[numPoints] = t00;
 318             ++numPoints;
 319
 320             points[numPoints] = v10;
 321             normals[numPoints] = n10;
 322             texCoords[numPoints] = t10;
 323             ++numPoints;
 324
 325             points[numPoints] = v01;
 326             normals[numPoints] = n01;
 327             texCoords[numPoints] = t01;
 328             ++numPoints;
 329         }
 330         if (y1 != 180*8) {
 331             points[numPoints] = v11;
 332             normals[numPoints] = n11;
 333             texCoords[numPoints] = t11;
 334             ++numPoints;
 335
 336             points[numPoints] = v01;
 337             normals[numPoints] = n01;
 338             texCoords[numPoints] = t01;
 339             ++numPoints;
 340
 341             points[numPoints] = v10;
 342             normals[numPoints] = n10;
 343             texCoords[numPoints] = t10;
 344             ++numPoints;
 345         }
 346         return numPoints;
 347     }
 348
 349 private:
 350     static unsigned _normalizeLongitude(unsigned offset)
 351     { return offset - (360*8)*(offset/(360*8)); }
 352
 353     static unsigned _longitudeDegToOffset(double lon)
 354     {
 355         unsigned offset = (unsigned)(8*(lon + 180) + 0.5);
 356         return _normalizeLongitude(offset);
 357     }
 358     static double _offsetToLongitudeDeg(unsigned offset)
 359     { return offset*0.125 - 180; }
 360
 361     static unsigned _latitudeDegToOffset(double lat)
 362     {
 363         if (lat < -90)
 364             return 0;
 365         unsigned offset = (unsigned)(8*(lat + 90) + 0.5);
 366         if (8*180 < offset)
 367             return 8*180;
 368         return offset;
 369     }
 370     static double _offsetToLatitudeDeg(unsigned offset)
 371     { return offset*0.125 - 90; }
 372
 373     static unsigned _degToSize(double deg)
 374     {
 375         if (deg <= 0)
 376             return 0;
 377         return (unsigned)(8*deg + 0.5);
 378     }
 379     static double _sizeToDeg(unsigned size)
 380     { return size*0.125; }
 381
 382     static unsigned _bucketSpanAtOffset(unsigned offset)
 383     { return (unsigned)(8*sg_bucket_span(_offsetToLatitudeDeg(offset) + 0.0625) + 0.5); }
 384
 385     static SGGeod _offsetToGeod(unsigned offset0, unsigned offset1, double elev)
 386     { return SGGeod::fromDegM(_offsetToLongitudeDeg(offset0), _offsetToLatitudeDeg(offset1), elev); }
 387
 388     static unsigned _getLevel(const unsigned factors[], unsigned nFactors, unsigned begin, unsigned end)
 389     {
 390         unsigned rbegin = end - 1;
 391         for (; 0 < nFactors;) {
 392             if (begin == rbegin)
 393                 break;
 394             --nFactors;
 395             begin /= factors[nFactors];
 396             rbegin /= factors[nFactors];
 397         }
 398
 399         return nFactors;
 400     }
 401
 402     static BucketBox _intersection(const BucketBox& box0, const BucketBox& box1)
 403     {
 404         BucketBox box;
 405         for (unsigned i = 0; i < 2; ++i) {
 406             box._offset[i] = std::max(box0._offset[i], box1._offset[i]);
 407             unsigned m = std::min(box0._offset[i] + box0._size[i], box1._offset[i] + box1._size[i]);
 408             if (m <= box._offset[i])
 409                 box._size[i] = 0;
 410             else
 411                 box._size[i] = m - box._offset[i];
 412         }
 413
 414         box._offset[0] = _normalizeLongitude(box._offset[0]);
 415
 416         return box;
 417     }
 418
 419     unsigned _offset[2];
 420     unsigned _size[2];
 421 };
 422
 423 inline bool
 424 operator==(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 425 {
 426     if (bucketBox0.getOffset(0) != bucketBox1.getOffset(0))
 427         return false;
 428     if (bucketBox0.getOffset(1) != bucketBox1.getOffset(1))
 429         return false;
 430     if (bucketBox0.getSize(0) != bucketBox1.getSize(0))
 431         return false;
 432     if (bucketBox0.getSize(1) != bucketBox1.getSize(1))
 433         return false;
 434     return true;
 435 }
 436
 437 inline bool
 438 operator!=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 439 { return !operator==(bucketBox0, bucketBox1); }
 440
 441 inline bool
 442 operator<(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 443 {
 444     if (bucketBox0.getOffset(0) < bucketBox1.getOffset(0)) return true;
 445     else if (bucketBox1.getOffset(0) < bucketBox0.getOffset(0)) return false;
 446     else if (bucketBox0.getOffset(1) < bucketBox1.getOffset(1)) return true;
 447     else if (bucketBox1.getOffset(1) < bucketBox0.getOffset(1)) return false;
 448     else if (bucketBox0.getSize(0) < bucketBox1.getSize(0)) return true;
 449     else if (bucketBox1.getSize(0) < bucketBox0.getSize(0)) return false;
 450     else return bucketBox0.getSize(1) < bucketBox1.getSize(1);
 451 }
 452
 453 inline bool
 454 operator>(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 455 { return operator<(bucketBox1, bucketBox0); }
 456
 457 inline bool
 458 operator<=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 459 { return !operator>(bucketBox0, bucketBox1); }
 460
 461 inline bool
 462 operator>=(const BucketBox& bucketBox0, const BucketBox& bucketBox1)
 463 { return !operator<(bucketBox0, bucketBox1); }
 464
 465 /// Stream output operator.
 466 /// Note that this is not only used for pretty printing but also for
 467 /// generating the meta file names for on demand paging.
 468 /// So, don't modify unless you know where else this is used.
 469 template<typename char_type, typename traits_type>
 470 std::basic_ostream<char_type, traits_type>&
 471 operator<<(std::basic_ostream<char_type, traits_type>& os, const BucketBox& bucketBox)
 472 {
 473     double lon = bucketBox.getLongitudeDeg();
 474     if (lon < 0)
 475         os << "w" << -lon;
 476     else
 477         os << "e" << lon;
 478
 479     double lat = bucketBox.getLatitudeDeg();
 480     if (lat < -90)
 481         lat = -90;
 482     if (90 < lat)
 483         lat = 90;
 484     if (lat < 0)
 485         os << "s" << -lat;
 486     else
 487         os << "n" << lat;
 488
 489     os << "-" << bucketBox.getWidthDeg() << "x" << bucketBox.getHeightDeg();
 490     return os;
 491 }
 492
 493 /// Stream inout operator.
 494 /// Note that this is used for reading the meta file names for on demand paging.
 495 /// So, don't modify unless you know where else this is used.
 496 template<typename char_type, typename traits_type>
 497 std::basic_istream<char_type, traits_type>&
 498 operator>>(std::basic_istream<char_type, traits_type>& is, BucketBox& bucketBox)
 499 {
 500     char c;
 501     is >> c;
 502     if (is.fail())
 503         return is;
 504
 505     int sign = 0;
 506     if (c == 'w')
 507         sign = -1;
 508     else if (c == 'e')
 509         sign = 1;
 510     else {
 511         is.setstate(std::ios::failbit | is.rdstate());
 512         return is;
 513     }
 514
 515     double num;
 516     is >> num;
 517     if (is.fail()) {
 518         is.setstate(std::ios::failbit | is.rdstate());
 519         return is;
 520     }
 521     bucketBox.setLongitudeDeg(sign*num);
 522
 523     is >> c;
 524     if (is.fail())
 525         return is;
 526
 527     sign = 0;
 528     if (c == 's')
 529         sign = -1;
 530     else if (c == 'n')
 531         sign = 1;
 532     else {
 533         is.setstate(std::ios::failbit | is.rdstate());
 534         return is;
 535     }
 536
 537     is >> num;
 538     if (is.fail())
 539         return is;
 540     bucketBox.setLatitudeDeg(sign*num);
 541
 542     is >> c;
 543     if (is.fail())
 544         return is;
 545     if (c != '-'){
 546         is.setstate(std::ios::failbit | is.rdstate());
 547         return is;
 548     }
 549
 550     is >> num;
 551     if (is.fail())
 552         return is;
 553     bucketBox.setWidthDeg(SGMiscd::min(num, 360));
 554
 555     is >> c;
 556     if (is.fail())
 557         return is;
 558     if (c != 'x'){
 559         is.setstate(std::ios::failbit | is.rdstate());
 560         return is;
 561     }
 562
 563     is >> num;
 564     if (is.fail())
 565         return is;
 566     bucketBox.setHeightDeg(SGMiscd::min(num, 90 - bucketBox.getLatitudeDeg()));
 567
 568     return is;
 569 }
 570
 571 } // namespace simgear
 572
 573 #endif