src/Terrain/RasterTileCache.cpp

   1 /*
   2 Copyright_License {
   3
   4   XCSoar Glide Computer - http://www.xcsoar.org/
   5   Copyright (C) 2000-2013 The XCSoar Project
   6   A detailed list of copyright holders can be found in the file "AUTHORS".
   7
   8   This program is free software; you can redistribute it and/or
   9   modify it under the terms of the GNU General Public License
  10   as published by the Free Software Foundation; either version 2
  11   of the License, or (at your option) any later version.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18   You should have received a copy of the GNU General Public License
  19   along with this program; if not, write to the Free Software
  20   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  21 }
  22 */
  23
  24 #include "Terrain/RasterTileCache.hpp"
  25 #include "Terrain/RasterLocation.hpp"
  26 #include "jasper/jas_image.h"
  27 #include "Math/Angle.hpp"
  28 #include "IO/ZipLineReader.hpp"
  29 #include "Operation/Operation.hpp"
  30 #include "Math/FastMath.h"
  31
  32 #include <string.h>
  33 #include <algorithm>
  34
  35 short*
  36 RasterTileCache::GetImageBuffer(unsigned index)
  37 {
  38   if (TileRequest(index))
  39     return tiles.GetLinear(index).GetImageBuffer();
  40
  41   return NULL;
  42 }
  43
  44 void
  45 RasterTileCache::SetTile(unsigned index,
  46                          int xstart, int ystart, int xend, int yend)
  47 {
  48   if (!segments.empty() && !segments.last().IsTileSegment())
  49     /* link current marker segment with this tile */
  50     segments.last().tile = index;
  51
  52   tiles.GetLinear(index).Set(xstart, ystart, xend, yend);
  53 }
  54
  55 struct RTDistanceSort {
  56   const RasterTileCache &rtc;
  57
  58   RTDistanceSort(RasterTileCache &_rtc):rtc(_rtc) {}
  59
  60   bool operator()(unsigned short ai, unsigned short bi) const {
  61     const RasterTile &a = rtc.tiles.GetLinear(ai);
  62     const RasterTile &b = rtc.tiles.GetLinear(bi);
  63
  64     return a.GetDistance() < b.GetDistance();
  65   }
  66 };
  67
  68 bool
  69 RasterTileCache::PollTiles(int x, int y, unsigned radius)
  70 {
  71   if (scan_overview)
  72     return false;
  73
  74   /* tiles are usually 256 pixels wide; with a radius smaller than
  75      that, the (optimized) tile distance calculations may fail;
  76      additionally, this ensures that tiles which are slightly out of
  77      the screen will be loaded in advance */
  78   radius += 256;
  79
  80   enum {
  81     /**
  82      * Maximum number of tiles loaded at a time, to reduce system load
  83      * peaks.
  84     */
  85     MAX_ACTIVATE = MAX_ACTIVE_TILES > 32 ? 16 : MAX_ACTIVE_TILES / 2,
  86   };
  87
  88   /* query all tiles; all tiles which are either in range or already
  89      loaded are added to RequestTiles */
  90
  91   request_tiles.clear();
  92   for (int i = tiles.GetSize() - 1; i >= 0 && !request_tiles.full(); --i)
  93     if (tiles.GetLinear(i).VisibilityChanged(x, y, radius))
  94       request_tiles.append(i);
  95
  96   /* reduce if there are too many */
  97
  98   if (request_tiles.size() > MAX_ACTIVE_TILES) {
  99     /* sort by distance */
 100     const RTDistanceSort sort(*this);
 101     std::sort(request_tiles.begin(), request_tiles.end(), sort);
 102
 103     /* dispose all tiles which are out of range */
 104     for (unsigned i = MAX_ACTIVE_TILES; i < request_tiles.size(); ++i) {
 105       RasterTile &tile = tiles.GetLinear(request_tiles[i]);
 106       tile.Disable();
 107     }
 108
 109     request_tiles.shrink(MAX_ACTIVE_TILES);
 110   }
 111
 112   /* fill ActiveTiles and request new tiles */
 113
 114   dirty = false;
 115
 116   unsigned num_activate = 0;
 117   for (unsigned i = 0; i < request_tiles.size(); ++i) {
 118     RasterTile &tile = tiles.GetLinear(request_tiles[i]);
 119     if (tile.IsEnabled())
 120       continue;
 121
 122     if (++num_activate <= MAX_ACTIVATE)
 123       /* request the tile in the current iteration */
 124       tile.SetRequest();
 125     else
 126       /* this tile will be loaded in the next iteration */
 127       dirty = true;
 128   }
 129
 130   return num_activate > 0;
 131 }
 132
 133 bool
 134 RasterTileCache::TileRequest(unsigned index)
 135 {
 136   RasterTile &tile = tiles.GetLinear(index);
 137
 138   if (!tile.IsRequested())
 139     return false;
 140
 141   tile.Enable();
 142   return true; // want to load this one!
 143 }
 144
 145 short
 146 RasterTileCache::GetHeight(unsigned px, unsigned py) const
 147 {
 148   if (px >= width || py >= height)
 149     // outside overall bounds
 150     return RasterBuffer::TERRAIN_INVALID;
 151
 152   const RasterTile &tile = tiles.Get(px / tile_width, py / tile_height);
 153   if (tile.IsEnabled())
 154     return tile.GetHeight(px, py);
 155
 156   // still not found, so go to overview
 157   return overview.GetInterpolated(px << (SUBPIXEL_BITS - OVERVIEW_BITS),
 158                                    py << (SUBPIXEL_BITS - OVERVIEW_BITS));
 159 }
 160
 161 short
 162 RasterTileCache::GetInterpolatedHeight(unsigned int lx, unsigned int ly) const
 163 {
 164   if ((lx >= overview_width_fine) || (ly >= overview_height_fine))
 165     // outside overall bounds
 166     return RasterBuffer::TERRAIN_INVALID;
 167
 168   unsigned px = lx, py = ly;
 169   const unsigned int ix = CombinedDivAndMod(px);
 170   const unsigned int iy = CombinedDivAndMod(py);
 171
 172   const RasterTile &tile = tiles.Get(px / tile_width, py / tile_height);
 173   if (tile.IsEnabled())
 174     return tile.GetInterpolatedHeight(px, py, ix, iy);
 175
 176   // still not found, so go to overview
 177   return overview.GetInterpolated(lx >> OVERVIEW_BITS,
 178                                    ly >> OVERVIEW_BITS);
 179 }
 180
 181 void
 182 RasterTileCache::SetSize(unsigned _width, unsigned _height,
 183                          unsigned _tile_width, unsigned _tile_height,
 184                          unsigned tile_columns, unsigned tile_rows)
 185 {
 186   width = _width;
 187   height = _height;
 188   tile_width = _tile_width;
 189   tile_height = _tile_height;
 190
 191   overview.Resize(width >> OVERVIEW_BITS, height >> OVERVIEW_BITS);
 192   overview_width_fine = width << SUBPIXEL_BITS;
 193   overview_height_fine = height << SUBPIXEL_BITS;
 194
 195   tiles.GrowDiscard(tile_columns, tile_rows);
 196 }
 197
 198 void
 199 RasterTileCache::SetLatLonBounds(double _lon_min, double _lon_max,
 200                                  double _lat_min, double _lat_max)
 201 {
 202   const Angle lon_min(Angle::Degrees(_lon_min));
 203   const Angle lon_max(Angle::Degrees(_lon_max));
 204   const Angle lat_min(Angle::Degrees(_lat_min));
 205   const Angle lat_max(Angle::Degrees(_lat_max));
 206
 207   bounds = GeoBounds(GeoPoint(std::min(lon_min, lon_max),
 208                               std::max(lat_min, lat_max)),
 209                      GeoPoint(std::max(lon_min, lon_max),
 210                               std::min(lat_min, lat_max)));
 211   bounds_initialised = true;
 212 }
 213
 214 void
 215 RasterTileCache::Reset()
 216 {
 217   width = 0;
 218   height = 0;
 219   initialised = false;
 220   bounds_initialised = false;
 221   segments.clear();
 222   scan_overview = true;
 223
 224   overview.Reset();
 225
 226   for (auto it = tiles.begin(), end = tiles.end(); it != end; ++it)
 227     it->Disable();
 228 }
 229
 230 gcc_pure
 231 const RasterTileCache::MarkerSegmentInfo *
 232 RasterTileCache::FindMarkerSegment(uint32_t file_offset) const
 233 {
 234   for (const MarkerSegmentInfo *p = segments.begin(); p < segments.end(); ++p)
 235     if (p->file_offset >= file_offset)
 236       return p;
 237
 238   return NULL;
 239 }
 240
 241 long
 242 RasterTileCache::SkipMarkerSegment(long file_offset) const
 243 {
 244   if (scan_overview)
 245     /* use all segments when loading the overview */
 246     return 0;
 247
 248   if (remaining_segments > 0) {
 249     /* enable the follow-up segment */
 250     --remaining_segments;
 251     return 0;
 252   }
 253
 254   const MarkerSegmentInfo *segment = FindMarkerSegment(file_offset);
 255   if (segment == NULL)
 256     /* past the end of the recorded segment list; shouldn't happen */
 257     return 0;
 258
 259   long skip_to = segment->file_offset;
 260   while (segment->IsTileSegment() &&
 261          !tiles.GetLinear(segment->tile).IsRequested()) {
 262     ++segment;
 263     if (segment >= segments.end())
 264       /* last segment is hidden; shouldn't happen either, because we
 265          expect EOC there */
 266       break;
 267
 268     skip_to = segment->file_offset;
 269   }
 270
 271   remaining_segments = segment->count;
 272   return skip_to - file_offset;
 273 }
 274
 275 /**
 276  * Does this segment belong to the preceding tile?  If yes, then it
 277  * inherits the tile number.
 278  */
 279 static bool
 280 is_tile_segment(unsigned id)
 281 {
 282   return id == 0xff93 /* SOD */ ||
 283     id == 0xff52 /* COD */ ||
 284     id == 0xff53 /* COC */ ||
 285     id == 0xff5c /* QCD */ ||
 286     id == 0xff5d /* QCC */ ||
 287     id == 0xff5e /* RGN */ ||
 288     id == 0xff5f /* POC */ ||
 289     id == 0xff61 /* PPT */ ||
 290     id == 0xff58 /* PLT */ ||
 291     id == 0xff64 /* COM */;
 292 }
 293
 294 void
 295 RasterTileCache::MarkerSegment(long file_offset, unsigned id)
 296 {
 297   if (!scan_overview || segments.full())
 298     return;
 299
 300   if (operation != NULL)
 301     operation->SetProgressPosition(file_offset / 65536);
 302
 303   if (is_tile_segment(id) && !segments.empty() &&
 304       segments.last().IsTileSegment()) {
 305     /* this segment belongs to the same tile as the preceding SOT
 306        segment */
 307     ++segments.last().count;
 308     return;
 309   }
 310
 311   if (segments.size() >= 2 && !segments.last().IsTileSegment() &&
 312       !segments[segments.size() - 2].IsTileSegment()) {
 313     /* the last two segments are both "generic" segments and can be merged*/
 314     assert(segments.last().count == 0);
 315
 316     ++segments[segments.size() - 2].count;
 317
 318     /* reuse the second segment */
 319     segments.last().file_offset = file_offset;
 320   } else
 321     segments.append(MarkerSegmentInfo(file_offset,
 322                                       MarkerSegmentInfo::NO_TILE));
 323 }
 324
 325 extern RasterTileCache *raster_tile_current;
 326
 327 void
 328 RasterTileCache::LoadJPG2000(const char *jp2_filename)
 329 {
 330   jas_stream_t *in;
 331
 332   raster_tile_current = this;
 333
 334   in = jas_stream_fopen(jp2_filename, "rb");
 335   if (!in) {
 336     Reset();
 337     return;
 338   }
 339
 340   if (operation != NULL)
 341     operation->SetProgressRange(jas_stream_length(in) / 65536);
 342
 343   jp2_decode(in, scan_overview ? "xcsoar=2" : "xcsoar=1");
 344   jas_stream_close(in);
 345 }
 346
 347 bool
 348 RasterTileCache::LoadWorldFile(const TCHAR *path)
 349 {
 350   ZipLineReaderA reader(path);
 351   if (reader.error())
 352     return false;
 353
 354   char *endptr;
 355   const char *line = reader.ReadLine(); // x scale
 356   double x_scale = strtod(line, &endptr);
 357   if (endptr == line)
 358     return false;
 359
 360   line = reader.ReadLine(); // y rotation
 361   if (line == NULL)
 362     return false;
 363
 364   double y_rotation = strtod(line, &endptr);
 365   if (endptr == line || y_rotation < -0.01 || y_rotation > 0.01)
 366     /* we don't support rotation */
 367     return false;
 368
 369   line = reader.ReadLine(); // x rotation
 370   if (line == NULL)
 371     return false;
 372
 373   double x_rotation = strtod(line, &endptr);
 374   if (endptr == line || x_rotation < -0.01 || x_rotation > 0.01)
 375     /* we don't support rotation */
 376     return false;
 377
 378   line = reader.ReadLine(); // y scale
 379   if (line == NULL)
 380     return false;
 381
 382   double y_scale = strtod(line, &endptr);
 383   if (endptr == line)
 384     return false;
 385
 386   line = reader.ReadLine(); // x origin
 387   if (line == NULL)
 388     return false;
 389
 390   double x_origin = strtod(line, &endptr);
 391   if (endptr == line)
 392     return false;
 393
 394   line = reader.ReadLine(); // y origin
 395   if (line == NULL)
 396     return false;
 397
 398   double y_origin = strtod(line, &endptr);
 399   if (endptr == line)
 400     return false;
 401
 402   SetLatLonBounds(x_origin, x_origin + GetWidth() * x_scale,
 403                   y_origin, y_origin + GetHeight() * y_scale);
 404   return true;
 405 }
 406
 407 bool
 408 RasterTileCache::LoadOverview(const char *path, const TCHAR *world_file,
 409                               OperationEnvironment &_operation)
 410 {
 411   assert(operation == NULL);
 412   operation = &_operation;
 413
 414   Reset();
 415
 416   LoadJPG2000(path);
 417   scan_overview = false;
 418
 419   if (initialised && world_file != NULL)
 420     LoadWorldFile(world_file);
 421
 422   if (initialised && !bounds_initialised)
 423     initialised = false;
 424
 425   if (!initialised)
 426     Reset();
 427
 428   operation = NULL;
 429   return initialised;
 430 }
 431
 432 void
 433 RasterTileCache::UpdateTiles(const char *path, int x, int y, unsigned radius)
 434 {
 435   if (!PollTiles(x, y, radius))
 436     return;
 437
 438   remaining_segments = 0;
 439
 440   LoadJPG2000(path);
 441
 442   /* permanently disable the requested tiles which are still not
 443      loaded, to prevent trying to reload them over and over in a busy
 444      loop */
 445   for (auto it = request_tiles.begin(), end = request_tiles.end();
 446       it != end; ++it) {
 447     RasterTile &tile = tiles.GetLinear(*it);
 448     if (tile.IsRequested() && !tile.IsEnabled())
 449       tile.Clear();
 450   }
 451
 452   ++serial;
 453 }
 454
 455 bool
 456 RasterTileCache::SaveCache(FILE *file) const
 457 {
 458   if (!initialised)
 459     return false;
 460
 461   assert(bounds_initialised);
 462
 463   /* save metadata */
 464   CacheHeader header;
 465
 466   /* zero-fill all implicit padding bytes (to make valgrind happy) */
 467   memset(&header, 0, sizeof(header));
 468
 469   header.version = CacheHeader::VERSION;
 470   header.width = width;
 471   header.height = height;
 472   header.tile_width = tile_width;
 473   header.tile_height = tile_height;
 474   header.tile_columns = tiles.GetWidth();
 475   header.tile_rows = tiles.GetHeight();
 476   header.num_marker_segments = segments.size();
 477   header.bounds = bounds;
 478
 479   if (fwrite(&header, sizeof(header), 1, file) != 1 ||
 480       /* .. and segments */
 481       fwrite(segments.begin(), sizeof(*segments.begin()), segments.size(), file) != segments.size())
 482     return false;
 483
 484   /* save tiles */
 485   unsigned i;
 486   for (i = 0; i < tiles.GetSize(); ++i)
 487     if (tiles.GetLinear(i).IsDefined() &&
 488         (fwrite(&i, sizeof(i), 1, file) != 1 ||
 489          !tiles.GetLinear(i).SaveCache(file)))
 490       return false;
 491
 492   i = -1;
 493   if (fwrite(&i, sizeof(i), 1, file) != 1)
 494     return false;
 495
 496   /* save overview */
 497   size_t overview_size = overview.GetWidth() * overview.GetHeight();
 498   if (fwrite(overview.GetData(), sizeof(*overview.GetData()),
 499              overview_size, file) != overview_size)
 500     return false;
 501
 502   /* done */
 503   return true;
 504 }
 505
 506 bool
 507 RasterTileCache::LoadCache(FILE *file)
 508 {
 509   Reset();
 510
 511   /* load metadata */
 512   CacheHeader header;
 513   if (fread(&header, sizeof(header), 1, file) != 1 ||
 514       header.version != CacheHeader::VERSION ||
 515       header.width < 1024 || header.width > 1024 * 1024 ||
 516       header.height < 1024 || header.height > 1024 * 1024 ||
 517       header.num_marker_segments < 4 ||
 518       header.num_marker_segments > segments.capacity() ||
 519       header.bounds.IsEmpty())
 520     return false;
 521
 522   SetSize(header.width, header.height,
 523           header.tile_width, header.tile_height,
 524           header.tile_columns, header.tile_rows);
 525   bounds = header.bounds;
 526   bounds_initialised = true;
 527
 528   /* load segments */
 529   for (unsigned i = 0; i < header.num_marker_segments; ++i) {
 530     MarkerSegmentInfo &segment = segments.append();
 531     if (fread(&segment, sizeof(segment), 1, file) != 1)
 532       return false;
 533   }
 534
 535   /* load tiles */
 536   unsigned i;
 537   while (true) {
 538     if (fread(&i, sizeof(i), 1, file) != 1)
 539       return false;
 540
 541     if (i == (unsigned)-1)
 542       break;
 543
 544     if (i >= tiles.GetSize())
 545       return false;
 546
 547     if (!tiles.GetLinear(i).LoadCache(file))
 548       return false;
 549   }
 550
 551   /* load overview */
 552   size_t overview_size = overview.GetWidth() * overview.GetHeight();
 553   if (fread(overview.GetData(), sizeof(*overview.GetData()),
 554             overview_size, file) != overview_size)
 555     return false;
 556
 557   initialised = true;
 558   scan_overview = false;
 559   return true;
 560 }