src/Terrain/RasterBuffer.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/RasterBuffer.hpp"
  25 #include "Math/FastMath.h"
  26
  27 #include <algorithm>
  28 #include <assert.h>
  29
  30 void
  31 RasterBuffer::Resize(unsigned _width, unsigned _height)
  32 {
  33   assert(_width > 0 && _height > 0);
  34
  35   data.GrowDiscard(_width, _height);
  36 }
  37
  38 short
  39 RasterBuffer::GetInterpolated(unsigned lx, unsigned ly,
  40                                unsigned ix, unsigned iy) const
  41 {
  42   assert(IsDefined());
  43   assert(lx < GetWidth());
  44   assert(ly < GetHeight());
  45   assert(ix < 0x100);
  46   assert(iy < 0x100);
  47
  48   // perform piecewise linear interpolation
  49   const unsigned int dx = (lx == GetWidth() - 1) ? 0 : 1;
  50   const unsigned int dy = (ly == GetHeight() - 1) ? 0 : GetWidth();
  51   const short *tm = GetDataAt(lx, ly);
  52
  53   if (IsSpecial(*tm) || IsSpecial(tm[dx]) ||
  54       IsSpecial(tm[dy]) || IsSpecial(tm[dx + dy]))
  55     return *tm;
  56
  57   unsigned kx = 0x100 - ix;
  58   unsigned ky = 0x100 - iy;
  59
  60   return (*tm * kx * ky + tm[dx] * ix * ky + tm[dy] * kx * iy + tm[dx + dy] * ix * iy) >> 16;
  61 }
  62
  63 short
  64 RasterBuffer::GetInterpolated(unsigned lx, unsigned ly) const
  65 {
  66   // check x in range, and decompose fraction part
  67   const unsigned int ix = CombinedDivAndMod(lx);
  68   if (lx >= GetWidth())
  69     return TERRAIN_INVALID;
  70
  71   // check y in range, and decompose fraction part
  72   const unsigned int iy = CombinedDivAndMod(ly);
  73   if (ly >= GetHeight())
  74     return TERRAIN_INVALID;
  75
  76   return GetInterpolated(lx, ly, ix, iy);
  77 }
  78
  79 /**
  80  * This class implements an algorithm to traverse pixels quickly with
  81  * only integer addition, no multiplication and division.
  82  */
  83 class PixelIterator
  84 {
  85   unsigned src_increment, src_counter;
  86   unsigned dest_increment, dest_counter;
  87
  88 public:
  89   PixelIterator(unsigned src_size, unsigned dest_size)
  90     :src_increment(dest_size), src_counter(0),
  91      dest_increment(src_size), dest_counter(0) {}
  92
  93   /**
  94    * @return the number of source pixels to skip
  95    */
  96   unsigned Next() {
  97     if (dest_counter < src_counter) {
  98       dest_counter += dest_increment;
  99       return 0;
 100     }
 101
 102     dest_counter += dest_increment;
 103
 104     unsigned n = 0;
 105
 106     /* this loop is inefficient with large dest_increment values */
 107     while (src_counter + src_increment <= dest_counter) {
 108       src_counter += src_increment;
 109       ++n;
 110     }
 111
 112     return n;
 113   }
 114 };
 115
 116 void
 117 RasterBuffer::ScanHorizontalLine(unsigned ax, unsigned bx, unsigned y,
 118                                  short *gcc_restrict buffer, unsigned size,
 119                                  bool interpolate) const
 120 {
 121   assert(ax < GetFineWidth());
 122   assert(bx < GetFineWidth());
 123   assert(y < GetFineHeight());
 124   assert(buffer != NULL);
 125   assert(size > 0);
 126
 127   if (size == 1) {
 128     *buffer = Get(ax >> 8, y >> 8);
 129     return;
 130   }
 131
 132   const int dx = bx - ax;
 133   /* disable interpolation when an output pixel is larger than two
 134      pixels in our buffer; the factor of two should account for the Y
 135      axis, which can have a different scale, making the factor some
 136      sort of ugly kludge to avoid horizontal shading stripes */
 137   if (interpolate && (unsigned)abs(dx) < (2 * size << 8u)) {
 138     /* interpolate */
 139
 140     unsigned cy = y;
 141     const unsigned int iy = CombinedDivAndMod(cy);
 142
 143     --size;
 144     for (int i = 0; (unsigned)i <= size; ++i) {
 145       unsigned cx = ax + (i * dx) / (int)size;
 146       const unsigned int ix = CombinedDivAndMod(cx);
 147
 148       *buffer++ = GetInterpolated(cx, cy, ix, iy);
 149     }
 150   } else if (gcc_likely(dx > 0)) {
 151     /* no interpolation needed, forward scan */
 152
 153     const short *gcc_restrict src = GetDataAt(ax >> 8, y >> 8);
 154
 155     PixelIterator iterator(dx >> 8, size);
 156     short *gcc_restrict end = buffer + size;
 157     while (true) {
 158       *buffer++ = *src;
 159       if (buffer >= end)
 160         break;
 161       src += iterator.Next();
 162     }
 163   } else {
 164     /* no interpolation needed */
 165
 166     const short *gcc_restrict src = GetDataAt(0, y >> 8);
 167
 168     --size;
 169     for (int i = 0; (unsigned)i <= size; ++i) {
 170       unsigned cx = ax + (i * dx) / (int)size;
 171
 172       *buffer++ = src[cx >> 8];
 173     }
 174   }
 175 }
 176
 177 void
 178 RasterBuffer::ScanLine(unsigned ax, unsigned ay, unsigned bx, unsigned by,
 179                        short *gcc_restrict buffer,
 180                        unsigned size, bool interpolate) const
 181 {
 182   assert(ax < GetFineWidth());
 183   assert(ay < GetFineHeight());
 184   assert(bx < GetFineWidth());
 185   assert(by < GetFineHeight());
 186   assert(buffer != NULL);
 187   assert(size > 0);
 188
 189   if (ay == by) {
 190     ScanHorizontalLine(ax, bx, ay, buffer, size, interpolate);
 191     return;
 192   }
 193
 194   if (size == 1) {
 195     *buffer = Get(ax >> 8, ay >> 8);
 196     return;
 197   }
 198
 199   --size;
 200   const int dx = bx - ax, dy = by - ay;
 201   /* disable interpolation when an output pixel is larger than two
 202      pixels in our buffer; the factor of two should account for the Y
 203      axis, which can have a different scale, making the factor some
 204      sort of ugly kludge to avoid horizontal shading stripes */
 205   if (interpolate && (unsigned)(abs(dx) + abs(dy)) < (2 * size << 8u)) {
 206     /* interpolate */
 207
 208     for (int i = 0; (unsigned)i <= size; ++i) {
 209       unsigned cx = ax + (i * dx) / (int)size;
 210       unsigned cy = ay + (i * dy) / (int)size;
 211
 212       const unsigned int ix = CombinedDivAndMod(cx);
 213       const unsigned int iy = CombinedDivAndMod(cy);
 214
 215       *buffer++ = GetInterpolated(cx, cy, ix, iy);
 216     }
 217   } else {
 218     /* no interpolation needed */
 219
 220     for (int i = 0; (unsigned)i <= size; ++i) {
 221       unsigned cx = ax + (i * dx) / (int)size;
 222       unsigned cy = ay + (i * dy) / (int)size;
 223
 224       *buffer++ = Get(cx >> 8, cy >> 8);
 225     }
 226   }
 227 }
 228
 229 void
 230 RasterBuffer::ScanLineChecked(unsigned ax, unsigned ay,
 231                               unsigned bx, unsigned by,
 232                               short *buffer, unsigned size,
 233                               bool interpolate) const
 234 {
 235   if (ax >= GetFineWidth())
 236     ax = GetFineWidth() - 1;
 237
 238   if (ay >= GetFineHeight())
 239     ay = GetFineHeight() - 1;
 240
 241   if (bx >= GetFineWidth())
 242     bx = GetFineWidth() - 1;
 243
 244   if (by >= GetFineHeight())
 245     by = GetFineHeight() - 1;
 246
 247   ScanLine(ax, ay, bx, by, buffer, size, interpolate);
 248 }
 249
 250 short
 251 RasterBuffer::GetMaximum() const
 252 {
 253   return IsDefined() ? *std::max_element(data.begin(), data.end()) : 0;
 254 }