viewport.cpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */


 
#include "stdafx.h"
#include "core/backup_type.hpp"
#include "landscape.h"
#include "viewport_func.h"
#include "station_base.h"
#include "waypoint_base.h"
#include "town.h"
#include "signs_base.h"
#include "signs_func.h"
#include "vehicle_base.h"
#include "vehicle_gui.h"
#include "blitter/factory.hpp"
#include "strings_func.h"
#include "zoom_func.h"
#include "vehicle_func.h"
#include "company_func.h"
#include "waypoint_func.h"
#include "window_func.h"
#include "tilehighlight_func.h"
#include "window_gui.h"
#include "linkgraph/linkgraph_gui.h"
#include "viewport_kdtree.h"
#include "town_kdtree.h"
#include "viewport_sprite_sorter.h"
#include "bridge_map.h"
#include "company_base.h"
#include "command_func.h"
#include "network/network_func.h"
#include "framerate_type.h"
#include "viewport_cmd.h"
 
#include <forward_list>
#include <stack>
 
#include "widgets/vehicle_widget.h"
 
#include "table/strings.h"
#include "table/string_colours.h"
 
#include "safeguards.h"
 
Point _tile_fract_coords;
 
 
ViewportSignKdtree _viewport_sign_kdtree{};
static int _viewport_sign_maxwidth = 0;
 
 
static const int MAX_TILE_EXTENT_LEFT   = ZOOM_BASE * TILE_PIXELS;                     
static const int MAX_TILE_EXTENT_RIGHT  = ZOOM_BASE * TILE_PIXELS;                     
static const int MAX_TILE_EXTENT_TOP    = ZOOM_BASE * MAX_BUILDING_PIXELS;             
static const int MAX_TILE_EXTENT_BOTTOM = ZOOM_BASE * (TILE_PIXELS + 2 * TILE_HEIGHT); 
 
struct StringSpriteToDraw {
  std::string string;
  uint16_t width;
  Colours colour;
  ViewportStringFlags flags;
  int32_t x;
  int32_t y;
};
 
struct TileSpriteToDraw {
  SpriteID image;
  PaletteID pal;
  const SubSprite *sub;           
  int32_t x;                        
  int32_t y;                        
};
 
struct ChildScreenSpriteToDraw {
  SpriteID image;
  PaletteID pal;
  const SubSprite *sub;           
  int32_t x;
  int32_t y;
  bool relative;
  int next;                       
};

enum FoundationPart : uint8_t {
  FOUNDATION_PART_NONE     = 0xFF,  
  FOUNDATION_PART_NORMAL   = 0,     
  FOUNDATION_PART_HALFTILE = 1,     
  FOUNDATION_PART_END
};

enum SpriteCombineMode : uint8_t {
  SPRITE_COMBINE_NONE,     
  SPRITE_COMBINE_PENDING,  
  SPRITE_COMBINE_ACTIVE,   
};
 
typedef std::vector<TileSpriteToDraw> TileSpriteToDrawVector;
typedef std::vector<StringSpriteToDraw> StringSpriteToDrawVector;
typedef std::vector<ParentSpriteToDraw> ParentSpriteToDrawVector;
typedef std::vector<ChildScreenSpriteToDraw> ChildScreenSpriteToDrawVector;
 
constexpr int LAST_CHILD_NONE = -1; 
constexpr int LAST_CHILD_PARENT = -2; 

struct ViewportDrawer {
  DrawPixelInfo dpi;
 
  StringSpriteToDrawVector string_sprites_to_draw;
  TileSpriteToDrawVector tile_sprites_to_draw;
  ParentSpriteToDrawVector parent_sprites_to_draw;
  ParentSpriteToSortVector parent_sprites_to_sort; 
  ChildScreenSpriteToDrawVector child_screen_sprites_to_draw;
 
  int last_child;
 
  SpriteCombineMode combine_sprites;               
 
  int foundation[FOUNDATION_PART_END];             
  FoundationPart foundation_part;                  
  int last_foundation_child[FOUNDATION_PART_END];  
  Point foundation_offset[FOUNDATION_PART_END];    
};
 
static bool MarkViewportDirty(const Viewport &vp, int left, int top, int right, int bottom);
 
static ViewportDrawer _vd;
 
TileHighlightData _thd;
static TileInfo _cur_ti;
bool _draw_bounding_boxes = false;
bool _draw_dirty_blocks = false;
uint _dirty_block_colour = 0;
static VpSpriteSorter _vp_sprite_sorter = nullptr;
 
static Point MapXYZToViewport(const Viewport &vp, int x, int y, int z)
{
  Point p = RemapCoords(x, y, z);
  p.x -= vp.virtual_width / 2;
  p.y -= vp.virtual_height / 2;
  return p;
}

void InitializeWindowViewport(Window *w, int x, int y,
  int width, int height, std::variant<TileIndex, VehicleID> focus, ZoomLevel zoom)
{
  assert(w->viewport == nullptr);
 
  auto vp = std::make_unique<ViewportData>();
 
  vp->left = x + w->left;
  vp->top = y + w->top;
  vp->width = width;
  vp->height = height;
 
  vp->zoom = Clamp(zoom, _settings_client.gui.zoom_min, _settings_client.gui.zoom_max);
 
  vp->virtual_width = ScaleByZoom(width, zoom);
  vp->virtual_height = ScaleByZoom(height, zoom);
 
  Point pt;
 
  if (std::holds_alternative<VehicleID>(focus)) {
    const Vehicle *veh;
 
    vp->follow_vehicle = std::get<VehicleID>(focus);
    veh = Vehicle::Get(vp->follow_vehicle)->GetMovingFront();
    pt = MapXYZToViewport(*vp, veh->x_pos, veh->y_pos, veh->z_pos);
  } else {
    TileIndex tile = std::get<TileIndex>(focus);
    if (tile == INVALID_TILE) {
      /* No tile? Use center of main viewport. */
      const Window *mw = GetMainWindow();
 
      /* center on same place as main window (zoom is maximum, no adjustment needed) */
      pt.x = mw->viewport->scrollpos_x + mw->viewport->virtual_width / 2;
      pt.x -= vp->virtual_width / 2;
      pt.y = mw->viewport->scrollpos_y + mw->viewport->virtual_height / 2;
      pt.y -= vp->virtual_height / 2;
    } else {
      x = TileX(tile) * TILE_SIZE;
      y = TileY(tile) * TILE_SIZE;
      pt = MapXYZToViewport(*vp, x, y, GetSlopePixelZ(x, y));
    }
    vp->follow_vehicle = VehicleID::Invalid();
  }
 
  vp->scrollpos_x = pt.x;
  vp->scrollpos_y = pt.y;
  vp->dest_scrollpos_x = pt.x;
  vp->dest_scrollpos_y = pt.y;
 
  vp->overlay = nullptr;
 
  vp->virtual_left = 0;
  vp->virtual_top = 0;
 
  w->viewport = std::move(vp);
}
 
static Point _vp_move_offs;
 
static void DoSetViewportPosition(Window::IteratorToFront it, int left, int top, int width, int height)
{
  for (; !it.IsEnd(); ++it) {
    const Window *w = *it;
    if (left + width > w->left &&
        w->left + w->width > left &&
        top + height > w->top &&
        w->top + w->height > top) {
 
      if (left < w->left) {
        DoSetViewportPosition(it, left, top, w->left - left, height);
        DoSetViewportPosition(it, left + (w->left - left), top, width - (w->left - left), height);
        return;
      }
 
      if (left + width > w->left + w->width) {
        DoSetViewportPosition(it, left, top, (w->left + w->width - left), height);
        DoSetViewportPosition(it, left + (w->left + w->width - left), top, width - (w->left + w->width - left), height);
        return;
      }
 
      if (top < w->top) {
        DoSetViewportPosition(it, left, top, width, (w->top - top));
        DoSetViewportPosition(it, left, top + (w->top - top), width, height - (w->top - top));
        return;
      }
 
      if (top + height > w->top + w->height) {
        DoSetViewportPosition(it, left, top, width, (w->top + w->height - top));
        DoSetViewportPosition(it, left, top + (w->top + w->height - top), width, height - (w->top + w->height - top));
        return;
      }
 
      return;
    }
  }
 
  {
    int xo = _vp_move_offs.x;
    int yo = _vp_move_offs.y;
 
    if (abs(xo) >= width || abs(yo) >= height) {
      /* fully_outside */
      RedrawScreenRect(left, top, left + width, top + height);
      return;
    }
 
    GfxScroll(left, top, width, height, xo, yo);
 
    if (xo > 0) {
      RedrawScreenRect(left, top, xo + left, top + height);
      left += xo;
      width -= xo;
    } else if (xo < 0) {
      RedrawScreenRect(left + width + xo, top, left + width, top + height);
      width += xo;
    }
 
    if (yo > 0) {
      RedrawScreenRect(left, top, width + left, top + yo);
    } else if (yo < 0) {
      RedrawScreenRect(left, top + height + yo, width + left, top + height);
    }
  }
}
 
static void SetViewportPosition(Window *w, int x, int y)
{
  Viewport &vp = *w->viewport;
  int old_left = vp.virtual_left;
  int old_top = vp.virtual_top;
  int i;
  int left, top, width, height;
 
  vp.virtual_left = x;
  vp.virtual_top = y;
 
  /* Viewport is bound to its left top corner, so it must be rounded down (UnScaleByZoomLower)
   * else glitch described in FS#1412 will happen (offset by 1 pixel with zoom level > NORMAL)
   */
  old_left = UnScaleByZoomLower(old_left, vp.zoom);
  old_top = UnScaleByZoomLower(old_top, vp.zoom);
  x = UnScaleByZoomLower(x, vp.zoom);
  y = UnScaleByZoomLower(y, vp.zoom);
 
  old_left -= x;
  old_top -= y;
 
  if (old_top == 0 && old_left == 0) return;
 
  _vp_move_offs.x = old_left;
  _vp_move_offs.y = old_top;
 
  left = vp.left;
  top = vp.top;
  width = vp.width;
  height = vp.height;
 
  if (left < 0) {
    width += left;
    left = 0;
  }
 
  i = left + width - _screen.width;
  if (i >= 0) width -= i;
 
  if (width > 0) {
    if (top < 0) {
      height += top;
      top = 0;
    }
 
    i = top + height - _screen.height;
    if (i >= 0) height -= i;
 
    if (height > 0) {
      Window::IteratorToFront it(w);
      ++it;
      DoSetViewportPosition(it, left, top, width, height);
    }
  }
}

Viewport *IsPtInWindowViewport(const Window *w, int x, int y)
{
  if (w->viewport == nullptr) return nullptr;
 
  const Viewport &vp = *w->viewport;
  if (IsInsideMM(x, vp.left, vp.left + vp.width) && IsInsideMM(y, vp.top, vp.top + vp.height)) return w->viewport.get();
 
  return nullptr;
}

Point TranslateXYToTileCoord(const Viewport &vp, int x, int y, bool clamp_to_map)
{
  if (!IsInsideBS(x, vp.left, vp.width) || !IsInsideBS(y, vp.top, vp.height)) {
    Point pt = { -1, -1 };
    return pt;
  }
 
  return InverseRemapCoords2(
      ScaleByZoom(x - vp.left, vp.zoom) + vp.virtual_left,
      ScaleByZoom(y - vp.top, vp.zoom) + vp.virtual_top, clamp_to_map);
}
 
/* When used for zooming, check area below current coordinates (x,y)
 * and return the tile of the zoomed out/in position (zoom_x, zoom_y)
 * when you just want the tile, make x = zoom_x and y = zoom_y */
static Point GetTileFromScreenXY(int x, int y, int zoom_x, int zoom_y)
{
  if (Window *w = FindWindowFromPt(x, y); w != nullptr) {
    if (Viewport *vp = IsPtInWindowViewport(w, x, y); vp != nullptr) {
      return TranslateXYToTileCoord(*vp, zoom_x, zoom_y);
    }
  }
 
  return {-1, -1};
}
 
Point GetTileBelowCursor()
{
  return GetTileFromScreenXY(_cursor.pos.x, _cursor.pos.y, _cursor.pos.x, _cursor.pos.y);
}
 
 
Point GetTileZoomCenterWindow(bool in, Window * w)
{
  int x, y;
  const Viewport &vp = *w->viewport;
 
  if (in) {
    x = ((_cursor.pos.x - vp.left) >> 1) + (vp.width >> 2);
    y = ((_cursor.pos.y - vp.top) >> 1) + (vp.height >> 2);
  } else {
    x = vp.width - (_cursor.pos.x - vp.left);
    y = vp.height - (_cursor.pos.y - vp.top);
  }
  /* Get the tile below the cursor and center on the zoomed-out center */
  return GetTileFromScreenXY(_cursor.pos.x, _cursor.pos.y, x + vp.left, y + vp.top);
}

void HandleZoomMessage(Window *w, const Viewport &vp, WidgetID widget_zoom_in, WidgetID widget_zoom_out)
{
  w->SetWidgetDisabledState(widget_zoom_in, vp.zoom <= _settings_client.gui.zoom_min);
  w->SetWidgetDirty(widget_zoom_in);
 
  w->SetWidgetDisabledState(widget_zoom_out, vp.zoom >= _settings_client.gui.zoom_max);
  w->SetWidgetDirty(widget_zoom_out);
}

static void AddTileSpriteToDraw(SpriteID image, PaletteID pal, int32_t x, int32_t y, int z, const SubSprite *sub = nullptr, int extra_offs_x = 0, int extra_offs_y = 0)
{
  assert((image & SPRITE_MASK) < MAX_SPRITES);
 
  TileSpriteToDraw &ts = _vd.tile_sprites_to_draw.emplace_back();
  ts.image = image;
  ts.pal = pal;
  ts.sub = sub;
  Point pt = RemapCoords(x, y, z);
  ts.x = pt.x + extra_offs_x;
  ts.y = pt.y + extra_offs_y;
}

static void AddChildSpriteToFoundation(SpriteID image, PaletteID pal, const SubSprite *sub, FoundationPart foundation_part, int extra_offs_x, int extra_offs_y)
{
  assert(IsInsideMM(foundation_part, 0, FOUNDATION_PART_END));
  assert(_vd.foundation[foundation_part] != -1);
  Point offs = _vd.foundation_offset[foundation_part];
 
  /* Change the active ChildSprite list to the one of the foundation */
  AutoRestoreBackup backup(_vd.last_child, _vd.last_foundation_child[foundation_part]);
  AddChildSpriteScreen(image, pal, offs.x + extra_offs_x, offs.y + extra_offs_y, false, sub, false, false);
}

void DrawGroundSpriteAt(SpriteID image, PaletteID pal, int32_t x, int32_t y, int z, const SubSprite *sub, int extra_offs_x, int extra_offs_y)
{
  /* Switch to first foundation part, if no foundation was drawn */
  if (_vd.foundation_part == FOUNDATION_PART_NONE) _vd.foundation_part = FOUNDATION_PART_NORMAL;
 
  if (_vd.foundation[_vd.foundation_part] != -1) {
    Point pt = RemapCoords(x, y, z);
    AddChildSpriteToFoundation(image, pal, sub, _vd.foundation_part, pt.x + extra_offs_x * ZOOM_BASE, pt.y + extra_offs_y * ZOOM_BASE);
  } else {
    AddTileSpriteToDraw(image, pal, _cur_ti.x + x, _cur_ti.y + y, _cur_ti.z + z, sub, extra_offs_x * ZOOM_BASE, extra_offs_y * ZOOM_BASE);
  }
}

void DrawGroundSprite(SpriteID image, PaletteID pal, const SubSprite *sub, int extra_offs_x, int extra_offs_y)
{
  DrawGroundSpriteAt(image, pal, 0, 0, 0, sub, extra_offs_x, extra_offs_y);
}

void OffsetGroundSprite(int x, int y)
{
  /* Switch to next foundation part */
  switch (_vd.foundation_part) {
    case FOUNDATION_PART_NONE:
      _vd.foundation_part = FOUNDATION_PART_NORMAL;
      break;
    case FOUNDATION_PART_NORMAL:
      _vd.foundation_part = FOUNDATION_PART_HALFTILE;
      break;
    default: NOT_REACHED();
  }
 
  /* _vd.last_child is LAST_CHILD_NONE if foundation sprite was clipped by the viewport bounds */
  if (_vd.last_child != LAST_CHILD_NONE) _vd.foundation[_vd.foundation_part] = static_cast<uint>(_vd.parent_sprites_to_draw.size()) - 1;
 
  _vd.foundation_offset[_vd.foundation_part].x = x * ZOOM_BASE;
  _vd.foundation_offset[_vd.foundation_part].y = y * ZOOM_BASE;
  _vd.last_foundation_child[_vd.foundation_part] = _vd.last_child;
}

static void AddCombinedSprite(SpriteID image, PaletteID pal, int x, int y, int z, const SubSprite *sub)
{
  Point pt = RemapCoords(x, y, z);
  const Sprite *spr = GetSprite(image & SPRITE_MASK, SpriteType::Normal);
 
  if (pt.x + spr->x_offs >= _vd.dpi.left + _vd.dpi.width ||
      pt.x + spr->x_offs + spr->width <= _vd.dpi.left ||
      pt.y + spr->y_offs >= _vd.dpi.top + _vd.dpi.height ||
      pt.y + spr->y_offs + spr->height <= _vd.dpi.top)
    return;
 
  const ParentSpriteToDraw &pstd = _vd.parent_sprites_to_draw.back();
  AddChildSpriteScreen(image, pal, pt.x - pstd.left, pt.y - pstd.top, false, sub, false);
}

void AddSortableSpriteToDraw(SpriteID image, PaletteID pal, int x, int y, int z, const SpriteBounds &bounds, bool transparent, const SubSprite *sub)
{
  int32_t left, right, top, bottom;
 
  assert((image & SPRITE_MASK) < MAX_SPRITES);
 
  /* Move to bounding box. */
  x += bounds.origin.x;
  y += bounds.origin.y;
  z += bounds.origin.z;
 
  /* make the sprites transparent with the right palette */
  if (transparent) {
    SetBit(image, PALETTE_MODIFIER_TRANSPARENT);
    pal = PALETTE_TO_TRANSPARENT;
  }
 
  if (_vd.combine_sprites == SPRITE_COMBINE_ACTIVE) {
    AddCombinedSprite(image, pal, x + bounds.offset.x, y + bounds.offset.y, z + bounds.offset.z, sub);
    return;
  }
 
  _vd.last_child = LAST_CHILD_NONE;
 
  Point pt = RemapCoords(x + bounds.offset.x, y + bounds.offset.y, z + bounds.offset.z);
  int tmp_left, tmp_top, tmp_x = pt.x, tmp_y = pt.y;
 
  /* Compute screen extents of sprite */
  if (image == SPR_EMPTY_BOUNDING_BOX) {
    left = tmp_left = RemapCoords(x + bounds.extent.x, y, z).x;
    right           = RemapCoords(x, y + bounds.extent.y, z).x + 1;
    top  = tmp_top  = RemapCoords(x, y, z + bounds.extent.z).y;
    bottom          = RemapCoords(x + bounds.extent.x, y + bounds.extent.y, z).y + 1;
  } else {
    const Sprite *spr = GetSprite(image & SPRITE_MASK, SpriteType::Normal);
    left = tmp_left = (pt.x += spr->x_offs);
    right           = (pt.x +  spr->width );
    top  = tmp_top  = (pt.y += spr->y_offs);
    bottom          = (pt.y +  spr->height);
  }
 
  if (_draw_bounding_boxes && (image != SPR_EMPTY_BOUNDING_BOX)) {
    /* Compute maximal extents of sprite and its bounding box */
    left   = std::min(left  , RemapCoords(x + bounds.extent.x, y, z).x);
    right  = std::max(right , RemapCoords(x, y + bounds.extent.y, z).x + 1);
    top    = std::min(top   , RemapCoords(x, y, z + bounds.extent.z).y);
    bottom = std::max(bottom, RemapCoords(x + bounds.extent.x, y + bounds.extent.y, z).y + 1);
  }
 
  /* Do not add the sprite to the viewport, if it is outside */
  if (left   >= _vd.dpi.left + _vd.dpi.width ||
      right  <= _vd.dpi.left                 ||
      top    >= _vd.dpi.top + _vd.dpi.height ||
      bottom <= _vd.dpi.top) {
    return;
  }
 
  ParentSpriteToDraw &ps = _vd.parent_sprites_to_draw.emplace_back();
  ps.x = tmp_x;
  ps.y = tmp_y;
 
  ps.left = tmp_left;
  ps.top  = tmp_top;
 
  ps.image = image;
  ps.pal = pal;
  ps.sub = sub;
  ps.xmin = x;
  ps.xmax = x + bounds.extent.x - 1;
 
  ps.ymin = y;
  ps.ymax = y + bounds.extent.y - 1;
 
  ps.zmin = z;
  ps.zmax = z + bounds.extent.z - 1;
 
  ps.first_child = LAST_CHILD_NONE;
 
  _vd.last_child = LAST_CHILD_PARENT;
 
  if (_vd.combine_sprites == SPRITE_COMBINE_PENDING) _vd.combine_sprites = SPRITE_COMBINE_ACTIVE;
}

void StartSpriteCombine()
{
  assert(_vd.combine_sprites == SPRITE_COMBINE_NONE);
  _vd.combine_sprites = SPRITE_COMBINE_PENDING;
}

void EndSpriteCombine()
{
  assert(_vd.combine_sprites != SPRITE_COMBINE_NONE);
  _vd.combine_sprites = SPRITE_COMBINE_NONE;
}

static bool IsInRangeInclusive(int begin, int end, int check)
{
  if (begin > end) std::swap(begin, end);
  return begin <= check && check <= end;
}

bool IsInsideRotatedRectangle(int x, int y)
{
  int dist_a = (_thd.size.x + _thd.size.y);      // Rotated coordinate system for selected rectangle.
  int dist_b = (_thd.size.x - _thd.size.y);      // We don't have to divide by 2. It's all relative!
  int a = ((x - _thd.pos.x) + (y - _thd.pos.y)); // Rotated coordinate system for the point under scrutiny.
  int b = ((x - _thd.pos.x) - (y - _thd.pos.y));
 
  /* Check if a and b are between 0 and dist_a or dist_b respectively. */
  return IsInRangeInclusive(dist_a, 0, a) && IsInRangeInclusive(dist_b, 0, b);
}

void AddChildSpriteScreen(SpriteID image, PaletteID pal, int x, int y, bool transparent, const SubSprite *sub, bool scale, bool relative)
{
  assert((image & SPRITE_MASK) < MAX_SPRITES);
 
  /* If the ParentSprite was clipped by the viewport bounds, do not draw the ChildSprites either */
  if (_vd.last_child == LAST_CHILD_NONE) return;
 
  /* make the sprites transparent with the right palette */
  if (transparent) {
    SetBit(image, PALETTE_MODIFIER_TRANSPARENT);
    pal = PALETTE_TO_TRANSPARENT;
  }
 
  int32_t child_id = static_cast<int32_t>(_vd.child_screen_sprites_to_draw.size());
  if (_vd.last_child != LAST_CHILD_PARENT) {
    _vd.child_screen_sprites_to_draw[_vd.last_child].next = child_id;
  } else {
    _vd.parent_sprites_to_draw.back().first_child = child_id;
  }
 
  ChildScreenSpriteToDraw &cs = _vd.child_screen_sprites_to_draw.emplace_back();
  cs.image = image;
  cs.pal = pal;
  cs.sub = sub;
  cs.x = scale ? x * ZOOM_BASE : x;
  cs.y = scale ? y * ZOOM_BASE : y;
  cs.relative = relative;
  cs.next = LAST_CHILD_NONE;
 
  /* Append the sprite to the active ChildSprite list.
   * If the active ParentSprite is a foundation, update last_foundation_child as well.
   * Note: ChildSprites of foundations are NOT sequential in the vector, as selection sprites are added at last. */
  if (_vd.last_foundation_child[0] == _vd.last_child) _vd.last_foundation_child[0] = child_id;
  if (_vd.last_foundation_child[1] == _vd.last_child) _vd.last_foundation_child[1] = child_id;
  _vd.last_child = child_id;
}

static std::string &AddStringToDraw(int x, int y, Colours colour, ViewportStringFlags flags, uint16_t width)
{
  assert(width != 0);
  StringSpriteToDraw &ss = _vd.string_sprites_to_draw.emplace_back();
  ss.colour = colour;
  ss.flags = flags;
  ss.x = x;
  ss.y = y;
  ss.width = width;
 
  return ss.string;
}
 

static void DrawSelectionSprite(SpriteID image, PaletteID pal, const TileInfo *ti, int z_offset, FoundationPart foundation_part, int extra_offs_x = 0, int extra_offs_y = 0)
{
  if (_vd.foundation[foundation_part] == -1) {
    /* draw on real ground */
    AddTileSpriteToDraw(image, pal, ti->x, ti->y, ti->z + z_offset, nullptr, extra_offs_x, extra_offs_y);
  } else {
    /* draw on top of foundation */
    AddChildSpriteToFoundation(image, pal, nullptr, foundation_part, extra_offs_x, extra_offs_y - z_offset * ZOOM_BASE);
  }
}

static void DrawTileSelectionRect(const TileInfo *ti, PaletteID pal)
{
  if (!IsValidTile(ti->tile)) return;
 
  SpriteID sel;
  if (IsHalftileSlope(ti->tileh)) {
    Corner halftile_corner = GetHalftileSlopeCorner(ti->tileh);
    SpriteID sel2 = SPR_HALFTILE_SELECTION_FLAT + halftile_corner;
    DrawSelectionSprite(sel2, pal, ti, 7 + TILE_HEIGHT, FOUNDATION_PART_HALFTILE);
 
    Corner opposite_corner = OppositeCorner(halftile_corner);
    if (IsSteepSlope(ti->tileh)) {
      sel = SPR_HALFTILE_SELECTION_DOWN;
    } else {
      sel = ((ti->tileh & SlopeWithOneCornerRaised(opposite_corner)) != 0 ? SPR_HALFTILE_SELECTION_UP : SPR_HALFTILE_SELECTION_FLAT);
    }
    sel += opposite_corner;
  } else {
    sel = SPR_SELECT_TILE + SlopeToSpriteOffset(ti->tileh);
  }
  DrawSelectionSprite(sel, pal, ti, 7, FOUNDATION_PART_NORMAL);
}
 
static bool IsPartOfAutoLine(int px, int py)
{
  px -= _thd.selstart.x;
  py -= _thd.selstart.y;
 
  if ((_thd.drawstyle & HT_DRAG_MASK) != HT_LINE) return false;
 
  switch (_thd.drawstyle & HT_DIR_MASK) {
    case HT_DIR_X:  return py == 0; // x direction
    case HT_DIR_Y:  return px == 0; // y direction
    case HT_DIR_HU: return px == -py || px == -py - 16; // horizontal upper
    case HT_DIR_HL: return px == -py || px == -py + 16; // horizontal lower
    case HT_DIR_VL: return px == py || px == py + 16; // vertical left
    case HT_DIR_VR: return px == py || px == py - 16; // vertical right
    default:
      NOT_REACHED();
  }
}
 
/* [direction][side] */
static const HighLightStyle _autorail_type[6][2] = {
  { HT_DIR_X,  HT_DIR_X },
  { HT_DIR_Y,  HT_DIR_Y },
  { HT_DIR_HU, HT_DIR_HL },
  { HT_DIR_HL, HT_DIR_HU },
  { HT_DIR_VL, HT_DIR_VR },
  { HT_DIR_VR, HT_DIR_VL }
};
 
#include "table/autorail.h"

static void DrawAutorailSelection(const TileInfo *ti, uint autorail_type)
{
  SpriteID image;
  PaletteID pal;
  int offset;
 
  FoundationPart foundation_part = FOUNDATION_PART_NORMAL;
  Slope autorail_tileh = RemoveHalftileSlope(ti->tileh);
  if (IsHalftileSlope(ti->tileh)) {
    static const uint _lower_rail[4] = { 5U, 2U, 4U, 3U };
    Corner halftile_corner = GetHalftileSlopeCorner(ti->tileh);
    if (autorail_type != _lower_rail[halftile_corner]) {
      foundation_part = FOUNDATION_PART_HALFTILE;
      /* Here we draw the highlights of the "three-corners-raised"-slope. That looks ok to me. */
      autorail_tileh = SlopeWithThreeCornersRaised(OppositeCorner(halftile_corner));
    }
  }
 
  offset = _AutorailTilehSprite[autorail_tileh][autorail_type];
  if (offset >= 0) {
    image = SPR_AUTORAIL_BASE + offset;
    pal = PAL_NONE;
  } else {
    image = SPR_AUTORAIL_BASE - offset;
    pal = PALETTE_SEL_TILE_RED;
  }
 
  DrawSelectionSprite(image, _thd.make_square_red ? PALETTE_SEL_TILE_RED : pal, ti, 7, foundation_part);
}
 
enum TileHighlightType : uint8_t {
  THT_NONE,
  THT_WHITE,
  THT_BLUE,
  THT_RED,
};
 
const Station *_viewport_highlight_station; 
const Station *_viewport_highlight_station_rect; 
const Waypoint *_viewport_highlight_waypoint; 
const Waypoint *_viewport_highlight_waypoint_rect; 
const Town *_viewport_highlight_town; 

static TileHighlightType GetTileHighlightType(TileIndex t)
{
  if (_viewport_highlight_station != nullptr) {
    if (IsTileType(t, TileType::Station) && GetStationIndex(t) == _viewport_highlight_station->index) return THT_WHITE;
    if (_viewport_highlight_station->TileIsInCatchment(t)) return THT_BLUE;
  }
 
  if (_viewport_highlight_station_rect != nullptr) {
    if (IsTileType(t, TileType::Station) && GetStationIndex(t) == _viewport_highlight_station_rect->index) return THT_WHITE;
    const StationRect *r = &_viewport_highlight_station_rect->rect;
    if (r->PtInExtendedRect(TileX(t), TileY(t))) return THT_BLUE;
  }
 
  if (_viewport_highlight_waypoint != nullptr) {
    if (IsTileType(t, TileType::Station) && GetStationIndex(t) == _viewport_highlight_waypoint->index) return THT_BLUE;
  }
 
  if (_viewport_highlight_waypoint_rect != nullptr) {
    if (IsTileType(t, TileType::Station) && GetStationIndex(t) == _viewport_highlight_waypoint_rect->index) return THT_WHITE;
    const StationRect *r = &_viewport_highlight_waypoint_rect->rect;
    if (r->PtInExtendedRect(TileX(t), TileY(t))) return THT_BLUE;
  }
 
  if (_viewport_highlight_town != nullptr) {
    if (IsTileType(t, TileType::House)) {
      if (GetTownIndex(t) == _viewport_highlight_town->index) {
        TileHighlightType type = THT_RED;
        for (const Station *st : _viewport_highlight_town->stations_near) {
          if (st->owner != _current_company) continue;
          if (st->TileIsInCatchment(t)) return THT_BLUE;
        }
        return type;
      }
    } else if (IsTileType(t, TileType::Station)) {
      for (const Station *st : _viewport_highlight_town->stations_near) {
        if (st->owner != _current_company) continue;
        if (GetStationIndex(t) == st->index) return THT_WHITE;
      }
    }
  }
 
  return THT_NONE;
}

static void DrawTileHighlightType(const TileInfo *ti, TileHighlightType tht)
{
  switch (tht) {
    default:
    case THT_NONE: break;
    case THT_WHITE: DrawTileSelectionRect(ti, PAL_NONE); break;
    case THT_BLUE:  DrawTileSelectionRect(ti, PALETTE_SEL_TILE_BLUE); break;
    case THT_RED:   DrawTileSelectionRect(ti, PALETTE_SEL_TILE_RED); break;
  }
}

static void HighlightTownLocalAuthorityTiles(const TileInfo *ti)
{
  /* Going through cases in order of computational time. */
 
  if (_town_local_authority_kdtree.Count() == 0) return;
 
  /* Tile belongs to town regardless of distance from town. */
  if (GetTileType(ti->tile) == TileType::House) {
    if (!Town::GetByTile(ti->tile)->show_zone) return;
 
    DrawTileSelectionRect(ti, PALETTE_CRASH);
    return;
  }
 
  /* If the closest town in the highlighted list is far, we can stop searching. */
  TownID tid = _town_local_authority_kdtree.FindNearest(TileX(ti->tile), TileY(ti->tile));
  Town *closest_highlighted_town = Town::Get(tid);
 
  if (DistanceManhattan(ti->tile, closest_highlighted_town->xy) >= _settings_game.economy.dist_local_authority) return;
 
  /* Tile is inside of the local autrhority distance of a highlighted town,
     but it is possible that a non-highlighted town is even closer. */
  Town *closest_town = ClosestTownFromTile(ti->tile, _settings_game.economy.dist_local_authority);
 
  if (closest_town->show_zone) {
    DrawTileSelectionRect(ti, PALETTE_CRASH);
  }
 
}

static void DrawTileSelection(const TileInfo *ti)
{
  /* Highlight tiles inside local authority of selected towns. */
  HighlightTownLocalAuthorityTiles(ti);
 
  /* Draw a red error square? */
  bool is_redsq = _thd.redsq == ti->tile;
  if (is_redsq) DrawTileSelectionRect(ti, PALETTE_TILE_RED_PULSATING);
 
  TileHighlightType tht = GetTileHighlightType(ti->tile);
  DrawTileHighlightType(ti, tht);
 
  /* No tile selection active? */
  if ((_thd.drawstyle & HT_DRAG_MASK) == HT_NONE) return;
 
  if (_thd.diagonal) { // We're drawing a 45 degrees rotated (diagonal) rectangle
    if (IsInsideRotatedRectangle((int)ti->x, (int)ti->y)) goto draw_inner;
    return;
  }
 
  /* Inside the inner area? */
  if (IsInsideBS(ti->x, _thd.pos.x, _thd.size.x) &&
      IsInsideBS(ti->y, _thd.pos.y, _thd.size.y)) {
draw_inner:
    if (_thd.drawstyle & HT_RECT) {
      if (!is_redsq) DrawTileSelectionRect(ti, _thd.make_square_red ? PALETTE_SEL_TILE_RED : PAL_NONE);
    } else if (_thd.drawstyle & HT_POINT) {
      /* Figure out the Z coordinate for the single dot. */
      int z = 0;
      FoundationPart foundation_part = FOUNDATION_PART_NORMAL;
      if (ti->tileh & SLOPE_N) {
        z += TILE_HEIGHT;
        if (RemoveHalftileSlope(ti->tileh) == SLOPE_STEEP_N) z += TILE_HEIGHT;
      }
      if (IsHalftileSlope(ti->tileh)) {
        Corner halftile_corner = GetHalftileSlopeCorner(ti->tileh);
        if ((halftile_corner == CORNER_W) || (halftile_corner == CORNER_E)) z += TILE_HEIGHT;
        if (halftile_corner != CORNER_S) {
          foundation_part = FOUNDATION_PART_HALFTILE;
          if (IsSteepSlope(ti->tileh)) z -= TILE_HEIGHT;
        }
      }
      DrawSelectionSprite(SPR_DOT, PAL_NONE, ti, z, foundation_part);
    } else if (_thd.drawstyle & HT_RAIL) {
      /* autorail highlight piece under cursor */
      HighLightStyle type = _thd.drawstyle & HT_DIR_MASK;
      assert(type < HT_DIR_END);
      DrawAutorailSelection(ti, _autorail_type[type][0]);
    } else if (IsPartOfAutoLine(ti->x, ti->y)) {
      /* autorail highlighting long line */
      HighLightStyle dir = _thd.drawstyle & HT_DIR_MASK;
      uint side;
 
      if (dir == HT_DIR_X || dir == HT_DIR_Y) {
        side = 0;
      } else {
        TileIndex start = TileVirtXY(_thd.selstart.x, _thd.selstart.y);
        side = Delta(Delta(TileX(start), TileX(ti->tile)), Delta(TileY(start), TileY(ti->tile)));
      }
 
      DrawAutorailSelection(ti, _autorail_type[dir][side]);
    }
    return;
  }
 
  /* Check if it's inside the outer area? */
  if (!is_redsq && (tht == THT_NONE || tht == THT_RED) && _thd.outersize.x > 0 &&
      IsInsideBS(ti->x, _thd.pos.x + _thd.offs.x, _thd.size.x + _thd.outersize.x) &&
      IsInsideBS(ti->y, _thd.pos.y + _thd.offs.y, _thd.size.y + _thd.outersize.y)) {
    /* Draw a blue rect. */
    DrawTileSelectionRect(ti, PALETTE_SEL_TILE_BLUE);
    return;
  }
}

static int GetViewportY(Point tile)
{
  /* Each increment in X or Y direction moves down by half a tile, i.e. TILE_PIXELS / 2. */
  return (tile.y * (int)(TILE_PIXELS / 2) + tile.x * (int)(TILE_PIXELS / 2) - TilePixelHeightOutsideMap(tile.x, tile.y)) << ZOOM_BASE_SHIFT;
}

static void ViewportAddLandscape()
{
  assert(_vd.dpi.top <= _vd.dpi.top + _vd.dpi.height);
  assert(_vd.dpi.left <= _vd.dpi.left + _vd.dpi.width);
 
  Point upper_left = InverseRemapCoords(_vd.dpi.left, _vd.dpi.top);
  Point upper_right = InverseRemapCoords(_vd.dpi.left + _vd.dpi.width, _vd.dpi.top);
 
  /* Transformations between tile coordinates and viewport rows/columns: See vp_column_row
   *   column = y - x
   *   row    = x + y
   *   x      = (row - column) / 2
   *   y      = (row + column) / 2
   * Note: (row, columns) pairs are only valid, if they are both even or both odd.
   */
 
  /* Columns overlap with neighbouring columns by a half tile.
   *  - Left column is column of upper_left (rounded down) and one column to the left.
   *  - Right column is column of upper_right (rounded up) and one column to the right.
   * Note: Integer-division does not round down for negative numbers, so ensure rounding with another increment/decrement.
   */
  int left_column = (upper_left.y - upper_left.x) / (int)TILE_SIZE - 2;
  int right_column = (upper_right.y - upper_right.x) / (int)TILE_SIZE + 2;
 
  int potential_bridge_height = ZOOM_BASE * TILE_HEIGHT * _settings_game.construction.max_bridge_height;
 
  /* Rows overlap with neighbouring rows by a half tile.
   * The first row that could possibly be visible is the row above upper_left (if it is at height 0).
   * Due to integer-division not rounding down for negative numbers, we need another decrement.
   */
  int row = (upper_left.x + upper_left.y) / (int)TILE_SIZE - 2;
  bool last_row = false;
  for (; !last_row; row++) {
    last_row = true;
    for (int column = left_column; column <= right_column; column++) {
      /* Valid row/column? */
      if ((row + column) % 2 != 0) continue;
 
      Point tilecoord;
      tilecoord.x = (row - column) / 2;
      tilecoord.y = (row + column) / 2;
      assert(column == tilecoord.y - tilecoord.x);
      assert(row == tilecoord.y + tilecoord.x);
 
      TileType tile_type;
      _cur_ti.x = tilecoord.x * TILE_SIZE;
      _cur_ti.y = tilecoord.y * TILE_SIZE;
 
      if (IsInsideBS(tilecoord.x, 0, Map::SizeX()) && IsInsideBS(tilecoord.y, 0, Map::SizeY())) {
        /* This includes the south border at Map::MaxX / Map::MaxY. When terraforming we still draw tile selections there. */
        _cur_ti.tile = TileXY(tilecoord.x, tilecoord.y);
        tile_type = GetTileType(_cur_ti.tile);
      } else {
        _cur_ti.tile = INVALID_TILE;
        tile_type = TileType::Void;
      }
 
      if (tile_type != TileType::Void) {
        /* We are inside the map => paint landscape. */
        std::tie(_cur_ti.tileh, _cur_ti.z) = GetTilePixelSlope(_cur_ti.tile);
      } else {
        /* We are outside the map => paint black. */
        std::tie(_cur_ti.tileh, _cur_ti.z) = GetTilePixelSlopeOutsideMap(tilecoord.x, tilecoord.y);
      }
 
      int viewport_y = GetViewportY(tilecoord);
 
      if (viewport_y + MAX_TILE_EXTENT_BOTTOM < _vd.dpi.top) {
        /* The tile in this column is not visible yet.
         * Tiles in other columns may be visible, but we need more rows in any case. */
        last_row = false;
        continue;
      }
 
      int min_visible_height = viewport_y - (_vd.dpi.top + _vd.dpi.height);
      bool tile_visible = min_visible_height <= 0;
 
      if (tile_type != TileType::Void) {
        /* Is tile with buildings visible? */
        if (min_visible_height < MAX_TILE_EXTENT_TOP) tile_visible = true;
 
        if (IsBridgeAbove(_cur_ti.tile)) {
          /* Is the bridge visible? */
          TileIndex bridge_tile = GetNorthernBridgeEnd(_cur_ti.tile);
          int bridge_height = ZOOM_BASE * (GetBridgePixelHeight(bridge_tile) - TilePixelHeight(_cur_ti.tile));
          if (min_visible_height < bridge_height + MAX_TILE_EXTENT_TOP) tile_visible = true;
        }
 
        /* Would a higher bridge on a more southern tile be visible?
         * If yes, we need to loop over more rows to possibly find one. */
        if (min_visible_height < potential_bridge_height + MAX_TILE_EXTENT_TOP) last_row = false;
      } else {
        /* Outside of map. If we are on the north border of the map, there may still be a bridge visible,
         * so we need to loop over more rows to possibly find one. */
        if ((tilecoord.x <= 0 || tilecoord.y <= 0) && min_visible_height < potential_bridge_height + MAX_TILE_EXTENT_TOP) last_row = false;
      }
 
      if (tile_visible) {
        last_row = false;
        _vd.foundation_part = FOUNDATION_PART_NONE;
        _vd.foundation[0] = -1;
        _vd.foundation[1] = -1;
        _vd.last_foundation_child[0] = LAST_CHILD_NONE;
        _vd.last_foundation_child[1] = LAST_CHILD_NONE;
 
        _tile_type_procs[tile_type]->draw_tile_proc(&_cur_ti);
        if (_cur_ti.tile != INVALID_TILE) DrawTileSelection(&_cur_ti);
      }
    }
  }
}

std::string *ViewportAddString(const DrawPixelInfo *dpi, const ViewportSign *sign, ViewportStringFlags flags, Colours colour)
{
  int left   = dpi->left;
  int top    = dpi->top;
  int right  = left + dpi->width;
  int bottom = top + dpi->height;
 
  bool small = flags.Test(ViewportStringFlag::Small);
  int sign_height     = ScaleByZoom(WidgetDimensions::scaled.fullbevel.top + GetCharacterHeight(small ? FontSize::Small : FontSize::Normal) + WidgetDimensions::scaled.fullbevel.bottom, dpi->zoom);
  int sign_half_width = ScaleByZoom((small ? sign->width_small : sign->width_normal) / 2, dpi->zoom);
 
  if (bottom < sign->top ||
      top   > sign->top + sign_height ||
      right < sign->center - sign_half_width ||
      left  > sign->center + sign_half_width) {
    return nullptr;
  }
 
  return &AddStringToDraw(sign->center - sign_half_width, sign->top, colour, flags, small ? sign->width_small : sign->width_normal);
}
 
static Rect ExpandRectWithViewportSignMargins(Rect r, ZoomLevel zoom)
{
  const int fh = std::max(GetCharacterHeight(FontSize::Normal), GetCharacterHeight(FontSize::Small));
  const int max_tw = _viewport_sign_maxwidth / 2 + 1;
  const int expand_y = ScaleByZoom(WidgetDimensions::scaled.fullbevel.top + fh + WidgetDimensions::scaled.fullbevel.bottom, zoom);
  const int expand_x = ScaleByZoom(WidgetDimensions::scaled.fullbevel.left + max_tw + WidgetDimensions::scaled.fullbevel.right, zoom);
 
  r.left -= expand_x;
  r.right += expand_x;
  r.top -= expand_y;
  r.bottom += expand_y;
 
  return r;
}

static void ViewportAddTownStrings(DrawPixelInfo *dpi, const std::vector<const Town *> &towns, bool small)
{
  ViewportStringFlags flags{};
  if (small) flags.Set({ViewportStringFlag::Small, ViewportStringFlag::Shadow});
 
  StringID stringid_town = !small && _settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_POP : STR_TOWN_NAME;
  StringID stringid_town_city = stringid_town;
  if (!small) {
    stringid_town_city = _settings_client.gui.population_in_label ? STR_VIEWPORT_TOWN_CITY_POP : STR_VIEWPORT_TOWN_CITY;
  }
 
  for (const Town *t : towns) {
    std::string *str = ViewportAddString(dpi, &t->cache.sign, flags, Colours::Invalid);
    if (str == nullptr) continue;
 
    if (t->larger_town) {
      *str = GetString(stringid_town_city, t->index, t->cache.population);
    } else {
      *str = GetString(stringid_town, t->index, t->cache.population);
    }
  }
}

static void ViewportAddSignStrings(DrawPixelInfo *dpi, const std::vector<const Sign *> &signs, bool small)
{
  ViewportStringFlags flags{};
  if (small) flags.Set(ViewportStringFlag::Small);
 
  /* Signs placed by a game script don't have a frame. */
  ViewportStringFlags deity_flags{ flags };
  deity_flags.Set(ViewportStringFlag::TextColour);
 
  flags.Set(IsTransparencySet(TO_SIGNS) ? ViewportStringFlag::TransparentRect : ViewportStringFlag::ColourRect);
 
  for (const Sign *si : signs) {
    /* Workaround to make sure white is actually white. The string drawing logic changes all
     * colours that are not Colours::Invalid slightly, turning white into a light gray. */
    const Colours deity_colour = si->text_colour == Colours::White ? Colours::Invalid : si->text_colour;
 
    std::string *str = ViewportAddString(dpi, &si->sign, (si->owner == OWNER_DEITY) ? deity_flags : flags,
      (si->owner == OWNER_NONE) ? Colours::Grey : (si->owner == OWNER_DEITY ? deity_colour : _company_colours[si->owner]));
    if (str == nullptr) continue;
 
    *str = GetString(STR_SIGN_NAME, si->index);
  }
}

static void ViewportAddStationStrings(DrawPixelInfo *dpi, const std::vector<const BaseStation *> &stations, bool small)
{
  /* Transparent station signs have colour text instead of a colour panel. */
  ViewportStringFlags flags{IsTransparencySet(TO_SIGNS) ? ViewportStringFlag::TextColour : ViewportStringFlag::ColourRect};
  if (small) flags.Set(ViewportStringFlag::Small);
 
  for (const BaseStation *st : stations) {
    std::string *str = ViewportAddString(dpi, &st->sign, flags, (st->owner == OWNER_NONE || !st->IsInUse()) ? Colours::Grey : _company_colours[st->owner]);
    if (str == nullptr) continue;
 
    if (Station::IsExpected(st)) { /* Station */
      *str = GetString(small ? STR_STATION_NAME : STR_VIEWPORT_STATION, st->index, st->facilities);
    } else { /* Waypoint */
      *str = GetString(STR_WAYPOINT_NAME, st->index);
    }
  }
}
 
static void ViewportAddKdtreeSigns(DrawPixelInfo *dpi)
{
  Rect search_rect{ dpi->left, dpi->top, dpi->left + dpi->width, dpi->top + dpi->height };
  search_rect = ExpandRectWithViewportSignMargins(search_rect, dpi->zoom);
 
  bool show_stations = HasBit(_display_opt, DO_SHOW_STATION_NAMES) && _game_mode != GM_MENU;
  bool show_waypoints = HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES) && _game_mode != GM_MENU;
  bool show_towns = HasBit(_display_opt, DO_SHOW_TOWN_NAMES) && _game_mode != GM_MENU;
  bool show_signs = HasBit(_display_opt, DO_SHOW_SIGNS) && !IsInvisibilitySet(TO_SIGNS);
  bool show_competitors = HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS);
 
  /* Collect all the items first and draw afterwards, to ensure layering */
  std::vector<const BaseStation *> stations;
  std::vector<const Town *> towns;
  std::vector<const Sign *> signs;
 
  _viewport_sign_kdtree.FindContained(search_rect.left, search_rect.top, search_rect.right, search_rect.bottom, [&](const ViewportSignKdtreeItem & item) {
    switch (item.type) {
      case ViewportSignKdtreeItem::VKI_STATION: {
        if (!show_stations) break;
        const BaseStation *st = BaseStation::Get(std::get<StationID>(item.id));
 
        /* If no facilities are present the station is a ghost station. */
        StationFacilities facilities = st->facilities;
        if (facilities.None()) facilities = STATION_FACILITY_GHOST;
 
        if (!facilities.Any(_facility_display_opt)) break;
 
        /* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
        if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
 
        stations.push_back(st);
        break;
      }
 
      case ViewportSignKdtreeItem::VKI_WAYPOINT: {
        if (!show_waypoints) break;
        const BaseStation *st = BaseStation::Get(std::get<StationID>(item.id));
 
        /* Don't draw if station is owned by another company and competitor station names are hidden. Stations owned by none are never ignored. */
        if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
 
        stations.push_back(st);
        break;
      }
 
      case ViewportSignKdtreeItem::VKI_TOWN:
        if (!show_towns) break;
        towns.push_back(Town::Get(std::get<TownID>(item.id)));
        break;
 
      case ViewportSignKdtreeItem::VKI_SIGN: {
        if (!show_signs) break;
        const Sign *si = Sign::Get(std::get<SignID>(item.id));
 
        /* Don't draw if sign is owned by another company and competitor signs should be hidden.
         * Note: It is intentional that also signs owned by OWNER_NONE are hidden. Bankrupt
         * companies can leave OWNER_NONE signs after them. */
        if (!show_competitors && _local_company != si->owner && si->owner != OWNER_DEITY) break;
 
        signs.push_back(si);
        break;
      }
 
      default:
        NOT_REACHED();
    }
  });
 
  /* Small versions of signs are used zoom level 4X and higher. */
  bool small = dpi->zoom >= ZoomLevel::Out4x;
 
  /* Layering order (bottom to top): Town names, signs, stations */
  ViewportAddTownStrings(dpi, towns, small);
 
  /* Do not draw signs nor station names if they are set invisible */
  if (IsInvisibilitySet(TO_SIGNS)) return;
 
  ViewportAddSignStrings(dpi, signs, small);
  ViewportAddStationStrings(dpi, stations, small);
}
 

void ViewportSign::UpdatePosition(int center, int top, std::string_view str, std::string_view str_small)
{
  if (this->width_normal != 0) this->MarkDirty();
 
  this->top = top;
 
  this->width_normal = WidgetDimensions::scaled.fullbevel.left + Align(GetStringBoundingBox(str).width, 2) + WidgetDimensions::scaled.fullbevel.right;
  this->center = center;
 
  /* zoomed out version */
  if (str_small.empty()) str_small = str;
  this->width_small = WidgetDimensions::scaled.fullbevel.left + Align(GetStringBoundingBox(str_small, FontSize::Small).width, 2) + WidgetDimensions::scaled.fullbevel.right;
 
  this->MarkDirty();
}

void ViewportSign::MarkDirty(ZoomLevel maxzoom) const
{
  Rect zoomlevels[to_underlying(ZoomLevel::End)];
 
  /* We don't know which size will be drawn, so mark the largest area dirty. */
  const uint half_width = std::max(this->width_normal, this->width_small) / 2 + 1;
  const uint height = WidgetDimensions::scaled.fullbevel.top + std::max(GetCharacterHeight(FontSize::Normal), GetCharacterHeight(FontSize::Small)) + WidgetDimensions::scaled.fullbevel.bottom + 1;
 
  for (ZoomLevel zoom = ZoomLevel::Begin; zoom != ZoomLevel::End; zoom++) {
    zoomlevels[to_underlying(zoom)].left = this->center - ScaleByZoom(half_width, zoom);
    zoomlevels[to_underlying(zoom)].top = this->top - ScaleByZoom(1, zoom);
    zoomlevels[to_underlying(zoom)].right = this->center + ScaleByZoom(half_width, zoom);
    zoomlevels[to_underlying(zoom)].bottom = this->top + ScaleByZoom(height, zoom);
  }
 
  for (const Window *w : Window::Iterate()) {
    if (w->viewport == nullptr) continue;
 
    Viewport &vp = *w->viewport;
    if (vp.zoom <= maxzoom) {
      assert(vp.width != 0);
      Rect &zl = zoomlevels[to_underlying(vp.zoom)];
      MarkViewportDirty(vp, zl.left, zl.top, zl.right, zl.bottom);
    }
  }
}
 
static void ViewportDrawTileSprites(const TileSpriteToDrawVector *tstdv)
{
  for (const TileSpriteToDraw &ts : *tstdv) {
    DrawSpriteViewport(ts.image, ts.pal, ts.x, ts.y, ts.sub);
  }
}

static void ViewportSortParentSprites(ParentSpriteToSortVector *psdv)
{
  if (psdv->size() < 2) return;
 
  /* We rely on sprites being, for the most part, already ordered.
   * So we don't need to move many of them and can keep track of their
   * order efficiently by using stack. We always move sprites to the front
   * of the current position, i.e. to the top of the stack.
   * Also use special constants to indicate sorting state without
   * adding extra fields to ParentSpriteToDraw structure.
   */
  const uint32_t ORDER_COMPARED = UINT32_MAX; // Sprite was compared but we still need to compare the ones preceding it
  const uint32_t ORDER_RETURNED = UINT32_MAX - 1; // Mark sorted sprite in case there are other occurrences of it in the stack
  std::stack<ParentSpriteToDraw *> sprite_order;
  uint32_t next_order = 0;
 
  std::forward_list<std::pair<int64_t, ParentSpriteToDraw *>> sprite_list;  // We store sprites in a list sorted by xmin+ymin
 
  /* Initialize sprite list and order. */
  for (auto p = psdv->rbegin(); p != psdv->rend(); p++) {
    sprite_list.emplace_front((*p)->xmin + (*p)->ymin, *p);
    sprite_order.push(*p);
    (*p)->order = next_order++;
  }
 
  sprite_list.sort();
 
  std::vector<ParentSpriteToDraw *> preceding;  // Temporarily stores sprites that precede current and their position in the list
  auto preceding_prev = sprite_list.begin(); // Store iterator in case we need to delete a single preceding sprite
  auto out = psdv->begin();  // Iterator to output sorted sprites
 
  while (!sprite_order.empty()) {
 
    auto s = sprite_order.top();
    sprite_order.pop();
 
    /* Sprite is already sorted, ignore it. */
    if (s->order == ORDER_RETURNED) continue;
 
    /* Sprite was already compared, just need to output it. */
    if (s->order == ORDER_COMPARED) {
      *(out++) = s;
      s->order = ORDER_RETURNED;
      continue;
    }
 
    preceding.clear();
 
    /* We only need sprites with xmin <= s->xmax && ymin <= s->ymax && zmin <= s->zmax
     * So by iterating sprites with xmin + ymin <= s->xmax + s->ymax
     * we get all we need and some more that we filter out later.
     * We don't include zmin into the sum as there are usually more neighbours on x and y than z
     * so including it will actually increase the amount of false positives.
     * Also min coordinates can be > max so using max(xmin, xmax) + max(ymin, ymax)
     * to ensure that we iterate the current sprite as we need to remove it from the list.
     */
    auto ssum = std::max(s->xmax, s->xmin) + std::max(s->ymax, s->ymin);
    auto prev = sprite_list.before_begin();
    auto x = sprite_list.begin();
    while (x != sprite_list.end() && x->first <= ssum) {
      auto p = x->second;
      if (p == s) {
        /* We found the current sprite, remove it and move on. */
        x = sprite_list.erase_after(prev);
        continue;
      }
 
      auto p_prev = prev;
      prev = x++;
 
      if (s->xmax < p->xmin || s->ymax < p->ymin || s->zmax < p->zmin) continue;
      if (s->xmin <= p->xmax && // overlap in X?
          s->ymin <= p->ymax && // overlap in Y?
          s->zmin <= p->zmax) { // overlap in Z?
        if (s->xmin + s->xmax + s->ymin + s->ymax + s->zmin + s->zmax <=
            p->xmin + p->xmax + p->ymin + p->ymax + p->zmin + p->zmax) {
          continue;
        }
      }
      preceding.push_back(p);
      preceding_prev = p_prev;
    }
 
    if (preceding.empty()) {
      /* No preceding sprites, add current one to the output */
      *(out++) = s;
      s->order = ORDER_RETURNED;
      continue;
    }
 
    /* Optimization for the case when we only have 1 sprite to move. */
    if (preceding.size() == 1) {
      auto p = preceding[0];
      /* We can only output the preceding sprite if there can't be any other sprites preceding it. */
      if (p->xmax <= s->xmax && p->ymax <= s->ymax && p->zmax <= s->zmax) {
        p->order = ORDER_RETURNED;
        s->order = ORDER_RETURNED;
        sprite_list.erase_after(preceding_prev);
        *(out++) = p;
        *(out++) = s;
        continue;
      }
    }
 
    /* Sort all preceding sprites by order and assign new orders in reverse (as original sorter did). */
    std::sort(preceding.begin(), preceding.end(), [](const ParentSpriteToDraw *a, const ParentSpriteToDraw *b) {
      return a->order > b->order;
    });
 
    s->order = ORDER_COMPARED;
    sprite_order.push(s);  // Still need to output so push it back for now
 
    for (auto p: preceding) {
      p->order = next_order++;
      sprite_order.push(p);
    }
  }
}
 
 
static void ViewportDrawParentSprites(const ParentSpriteToSortVector *psd, const ChildScreenSpriteToDrawVector *csstdv)
{
  for (const ParentSpriteToDraw *ps : *psd) {
    if (ps->image != SPR_EMPTY_BOUNDING_BOX) DrawSpriteViewport(ps->image, ps->pal, ps->x, ps->y, ps->sub);
 
    int child_idx = ps->first_child;
    while (child_idx >= 0) {
      const ChildScreenSpriteToDraw *cs = &(*csstdv)[child_idx];
      child_idx = cs->next;
      if (cs->relative) {
        DrawSpriteViewport(cs->image, cs->pal, ps->left + cs->x, ps->top + cs->y, cs->sub);
      } else {
        DrawSpriteViewport(cs->image, cs->pal, ps->x + cs->x, ps->y + cs->y, cs->sub);
      }
    }
  }
}

static void ViewportDrawBoundingBoxes(const ParentSpriteToSortVector *psd)
{
  for (const ParentSpriteToDraw *ps : *psd) {
    Point pt1 = RemapCoords(ps->xmax + 1, ps->ymax + 1, ps->zmax + 1); // top front corner
    Point pt2 = RemapCoords(ps->xmin    , ps->ymax + 1, ps->zmax + 1); // top left corner
    Point pt3 = RemapCoords(ps->xmax + 1, ps->ymin    , ps->zmax + 1); // top right corner
    Point pt4 = RemapCoords(ps->xmax + 1, ps->ymax + 1, ps->zmin    ); // bottom front corner
 
    DrawBox(        pt1.x,         pt1.y,
            pt2.x - pt1.x, pt2.y - pt1.y,
            pt3.x - pt1.x, pt3.y - pt1.y,
            pt4.x - pt1.x, pt4.y - pt1.y);
  }
}

static void ViewportDrawDirtyBlocks()
{
  Blitter *blitter = BlitterFactory::GetCurrentBlitter();
  const DrawPixelInfo *dpi = _cur_dpi;
  void *dst;
  int right =  UnScaleByZoom(dpi->width,  dpi->zoom);
  int bottom = UnScaleByZoom(dpi->height, dpi->zoom);
 
  PixelColour colour = _string_colourmap[_dirty_block_colour & 0xF];
 
  dst = dpi->dst_ptr;
 
  uint8_t bo = UnScaleByZoom(dpi->left + dpi->top, dpi->zoom) & 1;
  do {
    for (int i = (bo ^= 1); i < right; i += 2) blitter->SetPixel(dst, i, 0, colour);
    dst = blitter->MoveTo(dst, 0, 1);
  } while (--bottom > 0);
}
 
static void ViewportDrawStrings(ZoomLevel zoom, const StringSpriteToDrawVector *sstdv)
{
  for (const StringSpriteToDraw &ss : *sstdv) {
    bool small = ss.flags.Test(ViewportStringFlag::Small);
    int w = ss.width;
    int x = UnScaleByZoom(ss.x, zoom);
    int y = UnScaleByZoom(ss.y, zoom);
    int h = WidgetDimensions::scaled.fullbevel.top + GetCharacterHeight(small ? FontSize::Small : FontSize::Normal) + WidgetDimensions::scaled.fullbevel.bottom;
 
    TextColour colour = TC_WHITE;
    if (ss.flags.Test(ViewportStringFlag::ColourRect)) {
      if (ss.colour != Colours::Invalid) DrawFrameRect(x, y, x + w - 1, y + h - 1, ss.colour, {});
      colour = TC_BLACK;
    } else if (ss.flags.Test(ViewportStringFlag::TransparentRect)) {
      DrawFrameRect(x, y, x + w - 1, y + h - 1, ss.colour, FrameFlag::Transparent);
    }
 
    if (ss.flags.Test(ViewportStringFlag::TextColour)) {
      if (ss.colour != Colours::Invalid) colour = GetColourGradient(ss.colour, SHADE_LIGHTER).ToTextColour();
    }
 
    int left = x + WidgetDimensions::scaled.fullbevel.left;
    int right = x + w - 1 - WidgetDimensions::scaled.fullbevel.right;
    int top = y + WidgetDimensions::scaled.fullbevel.top;
 
    int shadow_offset = 0;
    if (small && ss.flags.Test(ViewportStringFlag::Shadow)) {
      /* Shadow needs to be shifted 1 pixel. */
      shadow_offset = WidgetDimensions::scaled.fullbevel.top;
      DrawString(left + shadow_offset, right + shadow_offset, top, ss.string, TC_BLACK, SA_HOR_CENTER, false, FontSize::Small);
    }
 
    DrawString(left, right, top - shadow_offset, ss.string, colour, SA_HOR_CENTER, false, small ? FontSize::Small : FontSize::Normal);
  }
}
 
void ViewportDoDraw(const Viewport &vp, int left, int top, int right, int bottom)
{
  _vd.dpi.zoom = vp.zoom;
  int mask = ScaleByZoom(-1, vp.zoom);
 
  _vd.combine_sprites = SPRITE_COMBINE_NONE;
 
  _vd.dpi.width = (right - left) & mask;
  _vd.dpi.height = (bottom - top) & mask;
  _vd.dpi.left = left & mask;
  _vd.dpi.top = top & mask;
  _vd.dpi.pitch = _cur_dpi->pitch;
  _vd.last_child = LAST_CHILD_NONE;
 
  int x = UnScaleByZoom(_vd.dpi.left - (vp.virtual_left & mask), vp.zoom) + vp.left;
  int y = UnScaleByZoom(_vd.dpi.top - (vp.virtual_top & mask), vp.zoom) + vp.top;
 
  _vd.dpi.dst_ptr = BlitterFactory::GetCurrentBlitter()->MoveTo(_cur_dpi->dst_ptr, x - _cur_dpi->left, y - _cur_dpi->top);
  AutoRestoreBackup dpi_backup(_cur_dpi, &_vd.dpi);
 
  ViewportAddLandscape();
  ViewportAddVehicles(&_vd.dpi);
 
  ViewportAddKdtreeSigns(&_vd.dpi);
 
  DrawTextEffects(&_vd.dpi);
 
  if (!_vd.tile_sprites_to_draw.empty()) ViewportDrawTileSprites(&_vd.tile_sprites_to_draw);
 
  for (auto &psd : _vd.parent_sprites_to_draw) {
    _vd.parent_sprites_to_sort.push_back(&psd);
  }
 
  _vp_sprite_sorter(&_vd.parent_sprites_to_sort);
  ViewportDrawParentSprites(&_vd.parent_sprites_to_sort, &_vd.child_screen_sprites_to_draw);
 
  if (_draw_bounding_boxes) ViewportDrawBoundingBoxes(&_vd.parent_sprites_to_sort);
  if (_draw_dirty_blocks) ViewportDrawDirtyBlocks();
 
  DrawPixelInfo dp = _vd.dpi;
  ZoomLevel zoom = _vd.dpi.zoom;
  dp.zoom = ZoomLevel::Min;
  dp.width = UnScaleByZoom(dp.width, zoom);
  dp.height = UnScaleByZoom(dp.height, zoom);
  AutoRestoreBackup cur_dpi(_cur_dpi, &dp);
 
  if (vp.overlay != nullptr && vp.overlay->GetCargoMask() != 0 && vp.overlay->GetCompanyMask().Any()) {
    /* translate to window coordinates */
    dp.left = x;
    dp.top = y;
    vp.overlay->Draw(&dp);
  }
 
  if (!_vd.string_sprites_to_draw.empty()) {
    /* translate to world coordinates */
    dp.left = UnScaleByZoom(_vd.dpi.left, zoom);
    dp.top = UnScaleByZoom(_vd.dpi.top, zoom);
    ViewportDrawStrings(zoom, &_vd.string_sprites_to_draw);
  }
 
  _vd.string_sprites_to_draw.clear();
  _vd.tile_sprites_to_draw.clear();
  _vd.parent_sprites_to_draw.clear();
  _vd.parent_sprites_to_sort.clear();
  _vd.child_screen_sprites_to_draw.clear();
}
 
static inline void ViewportDraw(const Viewport &vp, int left, int top, int right, int bottom)
{
  if (right <= vp.left || bottom <= vp.top) return;
 
  if (left >= vp.left + vp.width) return;
 
  if (left < vp.left) left = vp.left;
  if (right > vp.left + vp.width) right = vp.left + vp.width;
 
  if (top >= vp.top + vp.height) return;
 
  if (top < vp.top) top = vp.top;
  if (bottom > vp.top + vp.height) bottom = vp.top + vp.height;
 
  ViewportDoDraw(vp,
    ScaleByZoom(left - vp.left, vp.zoom) + vp.virtual_left,
    ScaleByZoom(top - vp.top, vp.zoom) + vp.virtual_top,
    ScaleByZoom(right - vp.left, vp.zoom) + vp.virtual_left,
    ScaleByZoom(bottom - vp.top, vp.zoom) + vp.virtual_top
  );
}

void Window::DrawViewport() const
{
  PerformanceAccumulator framerate(PFE_DRAWWORLD);
 
  DrawPixelInfo *dpi = _cur_dpi;
 
  dpi->left += this->left;
  dpi->top += this->top;
 
  ViewportDraw(*this->viewport, dpi->left, dpi->top, dpi->left + dpi->width, dpi->top + dpi->height);
 
  dpi->left -= this->left;
  dpi->top -= this->top;
}

static inline void ClampViewportToMap(const Viewport &vp, int *scroll_x, int *scroll_y)
{
  /* Centre of the viewport is hot spot. */
  Point pt = {
    *scroll_x + vp.virtual_width / 2,
    *scroll_y + vp.virtual_height / 2
  };
 
  /* Find nearest tile that is within borders of the map. */
  bool clamped;
  pt = InverseRemapCoords2(pt.x, pt.y, true, &clamped);
 
  if (clamped) {
    /* Convert back to viewport coordinates and remove centering. */
    pt = RemapCoords2(pt.x, pt.y);
    *scroll_x = pt.x - vp.virtual_width / 2;
    *scroll_y = pt.y - vp.virtual_height / 2;
  }
}

static void ClampSmoothScroll(uint32_t delta_ms, int64_t delta_hi, int64_t delta_lo, int &delta_hi_clamped, int &delta_lo_clamped)
{
  constexpr int PIXELS_PER_TILE = TILE_PIXELS * 2 * ZOOM_BASE;
 
  assert(delta_hi != 0);
 
  /* Move at most 75% of the distance every 30ms, for a smooth experience */
  int64_t delta_left = delta_hi * std::pow(0.75, delta_ms / 30.0);
  /* Move never more than 16 tiles per 30ms. */
  int max_scroll = Map::ScaleBySize1D(16 * PIXELS_PER_TILE * delta_ms / 30);
 
  /* We never go over the max_scroll speed. */
  delta_hi_clamped = Clamp(delta_hi - delta_left, -max_scroll, max_scroll);
  /* The lower delta is in ratio of the higher delta, so we keep going straight at the destination. */
  delta_lo_clamped = delta_lo * delta_hi_clamped / delta_hi;
 
  /* Ensure we always move (delta_hi can't be zero). */
  if (delta_hi_clamped == 0) {
    delta_hi_clamped = delta_hi > 0 ? 1 : -1;
  }
}

void UpdateViewportPosition(Window *w, uint32_t delta_ms)
{
  ViewportData &vp = *w->viewport;
 
  if (vp.follow_vehicle != VehicleID::Invalid()) {
    const Vehicle *veh = Vehicle::Get(vp.follow_vehicle)->GetMovingFront();
    Point pt = MapXYZToViewport(vp, veh->x_pos, veh->y_pos, veh->z_pos);
 
    vp.scrollpos_x = pt.x;
    vp.scrollpos_y = pt.y;
    SetViewportPosition(w, pt.x, pt.y);
  } else {
    /* Ensure the destination location is within the map */
    ClampViewportToMap(vp, &vp.dest_scrollpos_x, &vp.dest_scrollpos_y);
 
    int delta_x = vp.dest_scrollpos_x - vp.scrollpos_x;
    int delta_y = vp.dest_scrollpos_y - vp.scrollpos_y;
 
    int current_x = vp.scrollpos_x;
    int current_y = vp.scrollpos_y;
 
    bool update_overlay = false;
    if (delta_x != 0 || delta_y != 0) {
      if (_settings_client.gui.smooth_scroll) {
        int delta_x_clamped;
        int delta_y_clamped;
 
        if (abs(delta_x) > abs(delta_y)) {
          ClampSmoothScroll(delta_ms, delta_x, delta_y, delta_x_clamped, delta_y_clamped);
        } else {
          ClampSmoothScroll(delta_ms, delta_y, delta_x, delta_y_clamped, delta_x_clamped);
        }
 
        vp.scrollpos_x += delta_x_clamped;
        vp.scrollpos_y += delta_y_clamped;
      } else {
        vp.scrollpos_x = vp.dest_scrollpos_x;
        vp.scrollpos_y = vp.dest_scrollpos_y;
      }
      update_overlay = (vp.scrollpos_x == vp.dest_scrollpos_x &&
                vp.scrollpos_y == vp.dest_scrollpos_y);
    }
 
    ClampViewportToMap(vp, &vp.scrollpos_x, &vp.scrollpos_y);
 
    /* When moving small amounts around the border we can get stuck, and
     * not actually move. In those cases, teleport to the destination. */
    if ((delta_x != 0 || delta_y != 0) && current_x == vp.scrollpos_x && current_y == vp.scrollpos_y) {
      vp.scrollpos_x = vp.dest_scrollpos_x;
      vp.scrollpos_y = vp.dest_scrollpos_y;
    }
 
    SetViewportPosition(w, vp.scrollpos_x, vp.scrollpos_y);
    if (update_overlay) RebuildViewportOverlay(w);
  }
}

static bool MarkViewportDirty(const Viewport &vp, int left, int top, int right, int bottom)
{
  /* Rounding wrt. zoom-out level */
  right += (1 << to_underlying(vp.zoom)) - 1;
  bottom += (1 << to_underlying(vp.zoom)) - 1;
 
  right -= vp.virtual_left;
  if (right <= 0) return false;
 
  bottom -= vp.virtual_top;
  if (bottom <= 0) return false;
 
  left = std::max(0, left - vp.virtual_left);
 
  if (left >= vp.virtual_width) return false;
 
  top = std::max(0, top - vp.virtual_top);
 
  if (top >= vp.virtual_height) return false;
 
  AddDirtyBlock(
    UnScaleByZoomLower(left, vp.zoom) + vp.left,
    UnScaleByZoomLower(top, vp.zoom) + vp.top,
    UnScaleByZoom(right, vp.zoom) + vp.left + 1,
    UnScaleByZoom(bottom, vp.zoom) + vp.top + 1
  );
 
  return true;
}

bool MarkAllViewportsDirty(int left, int top, int right, int bottom)
{
  bool dirty = false;
 
  for (const Window *w : Window::Iterate()) {
    if (w->viewport != nullptr) {
      assert(w->viewport->width != 0);
      if (MarkViewportDirty(*w->viewport, left, top, right, bottom)) dirty = true;
    }
  }
 
  return dirty;
}
 
void ConstrainAllViewportsZoom()
{
  for (Window *w : Window::Iterate()) {
    if (w->viewport == nullptr) continue;
 
    ZoomLevel zoom = Clamp(w->viewport->zoom, _settings_client.gui.zoom_min, _settings_client.gui.zoom_max);
    if (zoom != w->viewport->zoom) {
      while (w->viewport->zoom < zoom) DoZoomInOutWindow(ZOOM_OUT, w);
      while (w->viewport->zoom > zoom) DoZoomInOutWindow(ZOOM_IN, w);
    }
  }
}

void MarkTileDirtyByTile(TileIndex tile, int bridge_level_offset, int tile_height_override)
{
  Point pt = RemapCoords(TileX(tile) * TILE_SIZE, TileY(tile) * TILE_SIZE, tile_height_override * TILE_HEIGHT);
  MarkAllViewportsDirty(
      pt.x - MAX_TILE_EXTENT_LEFT,
      pt.y - MAX_TILE_EXTENT_TOP - ZOOM_BASE * TILE_HEIGHT * bridge_level_offset,
      pt.x + MAX_TILE_EXTENT_RIGHT,
      pt.y + MAX_TILE_EXTENT_BOTTOM);
}

static void SetSelectionTilesDirty()
{
  int x_size = _thd.size.x;
  int y_size = _thd.size.y;
 
  if (!_thd.diagonal) { // Selecting in a straight rectangle (or a single square)
    int x_start = _thd.pos.x;
    int y_start = _thd.pos.y;
 
    if (_thd.outersize.x != 0) {
      x_size  += _thd.outersize.x;
      x_start += _thd.offs.x;
      y_size  += _thd.outersize.y;
      y_start += _thd.offs.y;
    }
 
    x_size -= TILE_SIZE;
    y_size -= TILE_SIZE;
 
    assert(x_size >= 0);
    assert(y_size >= 0);
 
    int x_end = Clamp(x_start + x_size, 0, Map::SizeX() * TILE_SIZE - TILE_SIZE);
    int y_end = Clamp(y_start + y_size, 0, Map::SizeY() * TILE_SIZE - TILE_SIZE);
 
    x_start = Clamp(x_start, 0, Map::SizeX() * TILE_SIZE - TILE_SIZE);
    y_start = Clamp(y_start, 0, Map::SizeY() * TILE_SIZE - TILE_SIZE);
 
    /* make sure everything is multiple of TILE_SIZE */
    assert((x_end | y_end | x_start | y_start) % TILE_SIZE == 0);
 
    /* How it works:
     * Suppose we have to mark dirty rectangle of 3x4 tiles:
     *   x
     *  xxx
     * xxxxx
     *  xxxxx
     *   xxx
     *    x
     * This algorithm marks dirty columns of tiles, so it is done in 3+4-1 steps:
     * 1)  x     2)  x
     *    xxx       Oxx
     *   Oxxxx     xOxxx
     *    xxxxx     Oxxxx
     *     xxx       xxx
     *      x         x
     * And so forth...
     */
 
    int top_x = x_end; // coordinates of top dirty tile
    int top_y = y_start;
    int bot_x = top_x; // coordinates of bottom dirty tile
    int bot_y = top_y;
 
    do {
      /* topmost dirty point */
      TileIndex top_tile = TileVirtXY(top_x, top_y);
      Point top = RemapCoords(top_x, top_y, GetTileMaxPixelZ(top_tile));
 
      /* bottommost point */
      TileIndex bottom_tile = TileVirtXY(bot_x, bot_y);
      Point bot = RemapCoords(bot_x + TILE_SIZE, bot_y + TILE_SIZE, GetTilePixelZ(bottom_tile)); // bottommost point
 
      /* the 'x' coordinate of 'top' and 'bot' is the same (and always in the same distance from tile middle),
       * tile height/slope affects only the 'y' on-screen coordinate! */
 
      int l = top.x - TILE_PIXELS * ZOOM_BASE; // 'x' coordinate of left   side of the dirty rectangle
      int t = top.y;                               // 'y' coordinate of top    side of the dirty rectangle
      int r = top.x + TILE_PIXELS * ZOOM_BASE; // 'x' coordinate of right  side of the dirty rectangle
      int b = bot.y;                               // 'y' coordinate of bottom side of the dirty rectangle
 
      static const int OVERLAY_WIDTH = 4 * ZOOM_BASE; // part of selection sprites is drawn outside the selected area (in particular: terraforming)
 
      /* For halftile foundations on SLOPE_STEEP_S the sprite extents some more towards the top */
      MarkAllViewportsDirty(l - OVERLAY_WIDTH, t - OVERLAY_WIDTH - TILE_HEIGHT * ZOOM_BASE, r + OVERLAY_WIDTH, b + OVERLAY_WIDTH);
 
      /* haven't we reached the topmost tile yet? */
      if (top_x != x_start) {
        top_x -= TILE_SIZE;
      } else {
        top_y += TILE_SIZE;
      }
 
      /* the way the bottom tile changes is different when we reach the bottommost tile */
      if (bot_y != y_end) {
        bot_y += TILE_SIZE;
      } else {
        bot_x -= TILE_SIZE;
      }
    } while (bot_x >= top_x);
  } else { // Selecting in a 45 degrees rotated (diagonal) rectangle.
    /* a_size, b_size describe a rectangle with rotated coordinates */
    int a_size = x_size + y_size, b_size = x_size - y_size;
 
    int interval_a = a_size < 0 ? -(int)TILE_SIZE : (int)TILE_SIZE;
    int interval_b = b_size < 0 ? -(int)TILE_SIZE : (int)TILE_SIZE;
 
    for (int a = -interval_a; a != a_size + interval_a; a += interval_a) {
      for (int b = -interval_b; b != b_size + interval_b; b += interval_b) {
        uint x = (_thd.pos.x + (a + b) / 2) / TILE_SIZE;
        uint y = (_thd.pos.y + (a - b) / 2) / TILE_SIZE;
 
        if (x < Map::MaxX() && y < Map::MaxY()) {
          MarkTileDirtyByTile(TileXY(x, y));
        }
      }
    }
  }
}
 
 
void SetSelectionRed(bool b)
{
  _thd.make_square_red = b;
  SetSelectionTilesDirty();
}

static bool CheckClickOnViewportSign(const Viewport &vp, int x, int y, const ViewportSign *sign)
{
  bool small = (vp.zoom >= ZoomLevel::Out4x);
  int sign_half_width = ScaleByZoom((small ? sign->width_small : sign->width_normal) / 2, vp.zoom);
  int sign_height = ScaleByZoom(WidgetDimensions::scaled.fullbevel.top + GetCharacterHeight(small ? FontSize::Small : FontSize::Normal) + WidgetDimensions::scaled.fullbevel.bottom, vp.zoom);
 
  return y >= sign->top && y < sign->top + sign_height &&
      x >= sign->center - sign_half_width && x < sign->center + sign_half_width;
}
 

static bool CheckClickOnViewportSign(const Viewport &vp, int x, int y)
{
  if (_game_mode == GM_MENU) return false;
 
  x = ScaleByZoom(x - vp.left, vp.zoom) + vp.virtual_left;
  y = ScaleByZoom(y - vp.top, vp.zoom) + vp.virtual_top;
 
  Rect search_rect{ x - 1, y - 1, x + 1, y + 1 };
  search_rect = ExpandRectWithViewportSignMargins(search_rect, vp.zoom);
 
  bool show_stations = HasBit(_display_opt, DO_SHOW_STATION_NAMES) && !IsInvisibilitySet(TO_SIGNS);
  bool show_waypoints = HasBit(_display_opt, DO_SHOW_WAYPOINT_NAMES) && !IsInvisibilitySet(TO_SIGNS);
  bool show_towns = HasBit(_display_opt, DO_SHOW_TOWN_NAMES);
  bool show_signs = HasBit(_display_opt, DO_SHOW_SIGNS) && !IsInvisibilitySet(TO_SIGNS);
  bool show_competitors = HasBit(_display_opt, DO_SHOW_COMPETITOR_SIGNS);
 
  /* Topmost of each type that was hit */
  BaseStation *st = nullptr, *last_st = nullptr;
  Town *t = nullptr, *last_t = nullptr;
  Sign *si = nullptr, *last_si = nullptr;
 
  /* See ViewportAddKdtreeSigns() for details on the search logic */
  _viewport_sign_kdtree.FindContained(search_rect.left, search_rect.top, search_rect.right, search_rect.bottom, [&](const ViewportSignKdtreeItem & item) {
    switch (item.type) {
      case ViewportSignKdtreeItem::VKI_STATION: {
        if (!show_stations) break;
        st = BaseStation::Get(std::get<StationID>(item.id));
        if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
 
        StationFacilities facilities = st->facilities;
        if (facilities.None()) facilities = STATION_FACILITY_GHOST;
        if (!facilities.Any(_facility_display_opt)) break;
 
        if (CheckClickOnViewportSign(vp, x, y, &st->sign)) last_st = st;
        break;
      }
 
      case ViewportSignKdtreeItem::VKI_WAYPOINT:
        if (!show_waypoints) break;
        st = BaseStation::Get(std::get<StationID>(item.id));
        if (!show_competitors && _local_company != st->owner && st->owner != OWNER_NONE) break;
        if (CheckClickOnViewportSign(vp, x, y, &st->sign)) last_st = st;
        break;
 
      case ViewportSignKdtreeItem::VKI_TOWN:
        if (!show_towns) break;
        t = Town::Get(std::get<TownID>(item.id));
        if (CheckClickOnViewportSign(vp, x, y, &t->cache.sign)) last_t = t;
        break;
 
      case ViewportSignKdtreeItem::VKI_SIGN:
        if (!show_signs) break;
        si = Sign::Get(std::get<SignID>(item.id));
        if (!show_competitors && _local_company != si->owner && si->owner != OWNER_DEITY) break;
        if (CheckClickOnViewportSign(vp, x, y, &si->sign)) last_si = si;
        break;
 
      default:
        NOT_REACHED();
    }
  });
 
  /* Select which hit to handle based on priority */
  if (last_st != nullptr) {
    if (Station::IsExpected(last_st)) {
      ShowStationViewWindow(last_st->index);
    } else {
      ShowWaypointWindow(Waypoint::From(last_st));
    }
    return true;
  } else if (last_t != nullptr) {
    ShowTownViewWindow(last_t->index);
    return true;
  } else if (last_si != nullptr) {
    HandleClickOnSign(last_si);
    return true;
  } else {
    return false;
  }
}
 
 
ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeStation(StationID id)
{
  ViewportSignKdtreeItem item;
  item.type = VKI_STATION;
  item.id = id;
 
  const Station *st = Station::Get(id);
  assert(st->sign.kdtree_valid);
  item.center = st->sign.center;
  item.top = st->sign.top;
 
  /* Assume the sign can be a candidate for drawing, so measure its width */
  _viewport_sign_maxwidth = std::max<int>({_viewport_sign_maxwidth, st->sign.width_normal, st->sign.width_small});
 
  return item;
}
 
ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeWaypoint(StationID id)
{
  ViewportSignKdtreeItem item;
  item.type = VKI_WAYPOINT;
  item.id = id;
 
  const Waypoint *st = Waypoint::Get(id);
  assert(st->sign.kdtree_valid);
  item.center = st->sign.center;
  item.top = st->sign.top;
 
  /* Assume the sign can be a candidate for drawing, so measure its width */
  _viewport_sign_maxwidth = std::max<int>({_viewport_sign_maxwidth, st->sign.width_normal, st->sign.width_small});
 
  return item;
}
 
ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeTown(TownID id)
{
  ViewportSignKdtreeItem item;
  item.type = VKI_TOWN;
  item.id = id;
 
  const Town *town = Town::Get(id);
  assert(town->cache.sign.kdtree_valid);
  item.center = town->cache.sign.center;
  item.top = town->cache.sign.top;
 
  /* Assume the sign can be a candidate for drawing, so measure its width */
  _viewport_sign_maxwidth = std::max<int>({_viewport_sign_maxwidth, town->cache.sign.width_normal, town->cache.sign.width_small});
 
  return item;
}
 
ViewportSignKdtreeItem ViewportSignKdtreeItem::MakeSign(SignID id)
{
  ViewportSignKdtreeItem item;
  item.type = VKI_SIGN;
  item.id = id;
 
  const Sign *sign = Sign::Get(id);
  assert(sign->sign.kdtree_valid);
  item.center = sign->sign.center;
  item.top = sign->sign.top;
 
  /* Assume the sign can be a candidate for drawing, so measure its width */
  _viewport_sign_maxwidth = std::max<int>({_viewport_sign_maxwidth, sign->sign.width_normal, sign->sign.width_small});
 
  return item;
}
 
void RebuildViewportKdtree()
{
  /* Reset biggest size sign seen */
  _viewport_sign_maxwidth = 0;
 
  std::vector<ViewportSignKdtreeItem> items;
  items.reserve(BaseStation::GetNumItems() + Town::GetNumItems() + Sign::GetNumItems());
 
  for (const Station *st : Station::Iterate()) {
    if (st->sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeStation(st->index));
  }
 
  for (const Waypoint *wp : Waypoint::Iterate()) {
    if (wp->sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeWaypoint(wp->index));
  }
 
  for (const Town *town : Town::Iterate()) {
    if (town->cache.sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeTown(town->index));
  }
 
  for (const Sign *sign : Sign::Iterate()) {
    if (sign->sign.kdtree_valid) items.push_back(ViewportSignKdtreeItem::MakeSign(sign->index));
  }
 
  _viewport_sign_kdtree.Build(items.begin(), items.end());
}
 
 
static bool CheckClickOnLandscape(const Viewport &vp, int x, int y)
{
  Point pt = TranslateXYToTileCoord(vp, x, y);
 
  if (pt.x != -1) return ClickTile(TileVirtXY(pt.x, pt.y));
  return true;
}
 
static void PlaceObject()
{
  Point pt;
  Window *w;
 
  pt = GetTileBelowCursor();
  if (pt.x == -1) return;
 
  if ((_thd.place_mode & HT_DRAG_MASK) == HT_POINT) {
    pt.x += TILE_SIZE / 2;
    pt.y += TILE_SIZE / 2;
  }
 
  _tile_fract_coords.x = pt.x & TILE_UNIT_MASK;
  _tile_fract_coords.y = pt.y & TILE_UNIT_MASK;
 
  w = _thd.GetCallbackWnd();
  if (w != nullptr) w->OnPlaceObject(pt, TileVirtXY(pt.x, pt.y));
}
 
 
bool HandleViewportClicked(const Viewport &vp, int x, int y)
{
  const Vehicle *v = CheckClickOnVehicle(vp, x, y);
 
  if (_thd.place_mode & HT_VEHICLE) {
    if (v != nullptr && VehicleClicked(v)) return true;
  }
 
  /* Vehicle placement mode already handled above. */
  if ((_thd.place_mode & HT_DRAG_MASK) != HT_NONE) {
    PlaceObject();
    return true;
  }
 
  if (CheckClickOnViewportSign(vp, x, y)) return true;
  bool result = CheckClickOnLandscape(vp, x, y);
 
  if (v != nullptr) {
    Debug(misc, 2, "Vehicle {} (index {}) at {}", v->unitnumber, v->index, fmt::ptr(v));
    if (IsCompanyBuildableVehicleType(v)) {
      v = v->First();
      if (_ctrl_pressed && v->owner == _local_company) {
        StartStopVehicle(v, true);
      } else {
        ShowVehicleViewWindow(v);
      }
    }
    return true;
  }
  return result;
}
 
void RebuildViewportOverlay(Window *w)
{
  if (w->viewport->overlay != nullptr &&
      w->viewport->overlay->GetCompanyMask().Any() &&
      w->viewport->overlay->GetCargoMask() != 0) {
    w->viewport->overlay->SetDirty();
    w->SetDirty();
  }
}

bool ScrollWindowTo(int x, int y, int z, Window *w, bool instant)
{
  /* The slope cannot be acquired outside of the map, so make sure we are always within the map. */
  if (z == -1) {
    if ( x >= 0 && x <= (int)Map::SizeX() * (int)TILE_SIZE - 1
        && y >= 0 && y <= (int)Map::SizeY() * (int)TILE_SIZE - 1) {
      z = GetSlopePixelZ(x, y);
    } else {
      z = TileHeightOutsideMap(x / (int)TILE_SIZE, y / (int)TILE_SIZE);
    }
  }
 
  Point pt = MapXYZToViewport(*w->viewport, x, y, z);
  w->viewport->CancelFollow(*w);
 
  if (w->viewport->dest_scrollpos_x == pt.x && w->viewport->dest_scrollpos_y == pt.y) return false;
 
  if (instant) {
    w->viewport->scrollpos_x = pt.x;
    w->viewport->scrollpos_y = pt.y;
    RebuildViewportOverlay(w);
  }
 
  w->viewport->dest_scrollpos_x = pt.x;
  w->viewport->dest_scrollpos_y = pt.y;
  return true;
}

bool ScrollWindowToTile(TileIndex tile, Window *w, bool instant)
{
  return ScrollWindowTo(TileX(tile) * TILE_SIZE, TileY(tile) * TILE_SIZE, -1, w, instant);
}

bool ScrollMainWindowToTile(TileIndex tile, bool instant)
{
  return ScrollMainWindowTo(TileX(tile) * TILE_SIZE + TILE_SIZE / 2, TileY(tile) * TILE_SIZE + TILE_SIZE / 2, -1, instant);
}

void SetRedErrorSquare(TileIndex tile)
{
  TileIndex old;
 
  old = _thd.redsq;
  _thd.redsq = tile;
 
  if (tile != old) {
    if (tile != INVALID_TILE) MarkTileDirtyByTile(tile);
    if (old  != INVALID_TILE) MarkTileDirtyByTile(old);
  }
}

void SetTileSelectSize(int w, int h)
{
  _thd.new_size.x = w * TILE_SIZE;
  _thd.new_size.y = h * TILE_SIZE;
  _thd.new_outersize.x = 0;
  _thd.new_outersize.y = 0;
}
 
void SetTileSelectBigSize(int ox, int oy, int sx, int sy)
{
  _thd.offs.x = ox * TILE_SIZE;
  _thd.offs.y = oy * TILE_SIZE;
  _thd.new_outersize.x = sx * TILE_SIZE;
  _thd.new_outersize.y = sy * TILE_SIZE;
}

static HighLightStyle GetAutorailHT(int x, int y)
{
  return HT_RAIL | _autorail_piece[x & TILE_UNIT_MASK][y & TILE_UNIT_MASK];
}

void TileHighlightData::Reset()
{
  this->pos.x = 0;
  this->pos.y = 0;
  this->new_pos.x = 0;
  this->new_pos.y = 0;
}

bool TileHighlightData::IsDraggingDiagonal()
{
  return (this->place_mode & HT_DIAGONAL) != 0 && _ctrl_pressed && _left_button_down;
}

Window *TileHighlightData::GetCallbackWnd()
{
  return FindWindowById(this->window_class, this->window_number);
}
 
 

void UpdateTileSelection()
{
  int x1;
  int y1;
 
  if (_thd.freeze) return;
 
  HighLightStyle new_drawstyle = HT_NONE;
  bool new_diagonal = false;
 
  if ((_thd.place_mode & HT_DRAG_MASK) == HT_SPECIAL) {
    x1 = _thd.selend.x;
    y1 = _thd.selend.y;
    if (x1 != -1) {
      int x2 = _thd.selstart.x & ~TILE_UNIT_MASK;
      int y2 = _thd.selstart.y & ~TILE_UNIT_MASK;
      x1 &= ~TILE_UNIT_MASK;
      y1 &= ~TILE_UNIT_MASK;
 
      if (_thd.IsDraggingDiagonal()) {
        new_diagonal = true;
      } else {
        if (x1 >= x2) std::swap(x1, x2);
        if (y1 >= y2) std::swap(y1, y2);
      }
      _thd.new_pos.x = x1;
      _thd.new_pos.y = y1;
      _thd.new_size.x = x2 - x1;
      _thd.new_size.y = y2 - y1;
      if (!new_diagonal) {
        _thd.new_size.x += TILE_SIZE;
        _thd.new_size.y += TILE_SIZE;
      }
      new_drawstyle = _thd.next_drawstyle;
    }
  } else if ((_thd.place_mode & HT_DRAG_MASK) != HT_NONE) {
    Point pt = GetTileBelowCursor();
    x1 = pt.x;
    y1 = pt.y;
    if (x1 != -1) {
      switch (_thd.place_mode & HT_DRAG_MASK) {
        case HT_RECT:
          new_drawstyle = HT_RECT;
          break;
        case HT_POINT:
          new_drawstyle = HT_POINT;
          x1 += TILE_SIZE / 2;
          y1 += TILE_SIZE / 2;
          break;
        case HT_RAIL:
          /* Draw one highlighted tile in any direction */
          new_drawstyle = GetAutorailHT(pt.x, pt.y);
          break;
        case HT_LINE:
          switch (_thd.place_mode & HT_DIR_MASK) {
            case HT_DIR_X: new_drawstyle = HT_LINE | HT_DIR_X; break;
            case HT_DIR_Y: new_drawstyle = HT_LINE | HT_DIR_Y; break;
 
            case HT_DIR_HU:
            case HT_DIR_HL:
              new_drawstyle = (pt.x & TILE_UNIT_MASK) + (pt.y & TILE_UNIT_MASK) <= TILE_SIZE ? HT_LINE | HT_DIR_HU : HT_LINE | HT_DIR_HL;
              break;
 
            case HT_DIR_VL:
            case HT_DIR_VR:
              new_drawstyle = (pt.x & TILE_UNIT_MASK) > (pt.y & TILE_UNIT_MASK) ? HT_LINE | HT_DIR_VL : HT_LINE | HT_DIR_VR;
              break;
 
            default: NOT_REACHED();
          }
          _thd.selstart.x = x1 & ~TILE_UNIT_MASK;
          _thd.selstart.y = y1 & ~TILE_UNIT_MASK;
          break;
        default:
          NOT_REACHED();
      }
      _thd.new_pos.x = x1 & ~TILE_UNIT_MASK;
      _thd.new_pos.y = y1 & ~TILE_UNIT_MASK;
    }
  }
 
  /* redraw selection */
  if (_thd.drawstyle != new_drawstyle ||
      _thd.pos.x != _thd.new_pos.x || _thd.pos.y != _thd.new_pos.y ||
      _thd.size.x != _thd.new_size.x || _thd.size.y != _thd.new_size.y ||
      _thd.outersize.x != _thd.new_outersize.x ||
      _thd.outersize.y != _thd.new_outersize.y ||
      _thd.diagonal    != new_diagonal) {
    /* Clear the old tile selection? */
    if ((_thd.drawstyle & HT_DRAG_MASK) != HT_NONE) SetSelectionTilesDirty();
 
    _thd.drawstyle = new_drawstyle;
    _thd.pos = _thd.new_pos;
    _thd.size = _thd.new_size;
    _thd.outersize = _thd.new_outersize;
    _thd.diagonal = new_diagonal;
    _thd.dirty = 0xff;
 
    /* Draw the new tile selection? */
    if ((new_drawstyle & HT_DRAG_MASK) != HT_NONE) SetSelectionTilesDirty();
  }
}

static inline void ShowMeasurementTooltips(EncodedString &&text)
{
  if (!_settings_client.gui.measure_tooltip) return;
  GuiShowTooltips(_thd.GetCallbackWnd(), std::move(text), TCC_EXIT_VIEWPORT);
}
 
static void HideMeasurementTooltips()
{
  CloseWindowById(WC_TOOLTIPS, 0);
}

void VpStartPlaceSizing(TileIndex tile, ViewportPlaceMethod method, ViewportDragDropSelectionProcess process)
{
  _thd.select_method = method;
  _thd.select_proc   = process;
  _thd.selend.x = TileX(tile) * TILE_SIZE;
  _thd.selstart.x = TileX(tile) * TILE_SIZE;
  _thd.selend.y = TileY(tile) * TILE_SIZE;
  _thd.selstart.y = TileY(tile) * TILE_SIZE;
 
  /* Needed so several things (road, autoroad, bridges, ...) are placed correctly.
   * In effect, placement starts from the centre of a tile
   */
  if (method == VPM_X_OR_Y || method == VPM_FIX_X || method == VPM_FIX_Y) {
    _thd.selend.x += TILE_SIZE / 2;
    _thd.selend.y += TILE_SIZE / 2;
    _thd.selstart.x += TILE_SIZE / 2;
    _thd.selstart.y += TILE_SIZE / 2;
  }
 
  HighLightStyle others = _thd.place_mode & ~(HT_DRAG_MASK | HT_DIR_MASK);
  if ((_thd.place_mode & HT_DRAG_MASK) == HT_RECT) {
    _thd.place_mode = HT_SPECIAL | others;
    _thd.next_drawstyle = HT_RECT | others;
  } else if (_thd.place_mode & (HT_RAIL | HT_LINE)) {
    _thd.place_mode = HT_SPECIAL | others;
    _thd.next_drawstyle = _thd.drawstyle | others;
  } else {
    _thd.place_mode = HT_SPECIAL | others;
    _thd.next_drawstyle = HT_POINT | others;
  }
  _special_mouse_mode = WSM_SIZING;
}

void VpStartDragging(ViewportDragDropSelectionProcess process)
{
  _thd.select_method = VPM_X_AND_Y;
  _thd.select_proc = process;
  _thd.selstart.x = 0;
  _thd.selstart.y = 0;
  _thd.next_drawstyle = HT_RECT;
 
  _special_mouse_mode = WSM_DRAGGING;
}
 
void VpSetPlaceSizingLimit(int limit)
{
  _thd.sizelimit = limit;
}

void VpSetPresizeRange(TileIndex from, TileIndex to)
{
  uint64_t distance = DistanceManhattan(from, to) + 1;
 
  _thd.selend.x = TileX(to) * TILE_SIZE;
  _thd.selend.y = TileY(to) * TILE_SIZE;
  _thd.selstart.x = TileX(from) * TILE_SIZE;
  _thd.selstart.y = TileY(from) * TILE_SIZE;
  _thd.next_drawstyle = HT_RECT;
 
  /* show measurement only if there is any length to speak of */
  if (distance > 1) {
    ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_LENGTH, distance));
  } else {
    HideMeasurementTooltips();
  }
}
 
static void VpStartPreSizing()
{
  _thd.selend.x = -1;
  _special_mouse_mode = WSM_PRESIZE;
}

static HighLightStyle Check2x1AutoRail(DiagDirection direction)
{
  int fxpy = _tile_fract_coords.x + _tile_fract_coords.y;
  int sxpy = (_thd.selend.x & TILE_UNIT_MASK) + (_thd.selend.y & TILE_UNIT_MASK);
  int fxmy = _tile_fract_coords.x - _tile_fract_coords.y;
  int sxmy = (_thd.selend.x & TILE_UNIT_MASK) - (_thd.selend.y & TILE_UNIT_MASK);
 
  switch (direction) {
    default: NOT_REACHED();
    case DIAGDIR_SE: // end piece is lower right
      if (fxpy >= 20 && sxpy <= 12) return HT_DIR_HL;
      if (fxmy < -3 && sxmy > 3) return HT_DIR_VR;
      return HT_DIR_Y;
 
    case DIAGDIR_NW:
      if (fxmy > 3 && sxmy < -3) return HT_DIR_VL;
      if (fxpy <= 12 && sxpy >= 20) return HT_DIR_HU;
      return HT_DIR_Y;
 
    case DIAGDIR_SW:
      if (fxmy > 3 && sxmy < -3) return HT_DIR_VL;
      if (fxpy >= 20 && sxpy <= 12) return HT_DIR_HL;
      return HT_DIR_X;
 
    case DIAGDIR_NE:
      if (fxmy < -3 && sxmy > 3) return HT_DIR_VR;
      if (fxpy <= 12 && sxpy >= 20) return HT_DIR_HU;
      return HT_DIR_X;
  }
}

static bool SwapDirection(HighLightStyle style, TileIndex start_tile, TileIndex end_tile)
{
  uint start_x = TileX(start_tile);
  uint start_y = TileY(start_tile);
  uint end_x = TileX(end_tile);
  uint end_y = TileY(end_tile);
 
  switch (style & HT_DRAG_MASK) {
    case HT_RAIL:
    case HT_LINE: return (end_x > start_x || (end_x == start_x && end_y > start_y));
 
    case HT_RECT:
    case HT_POINT: return (end_x != start_x && end_y < start_y);
    default: NOT_REACHED();
  }
 
  return false;
}

static int CalcHeightdiff(HighLightStyle style, uint distance, TileIndex start_tile, TileIndex end_tile)
{
  bool swap = SwapDirection(style, start_tile, end_tile);
  uint h0, h1; // Start height and end height.
 
  if (start_tile == end_tile) return 0;
  if (swap) std::swap(start_tile, end_tile);
 
  switch (style & HT_DRAG_MASK) {
    case HT_RECT:
      /* In the case of an area we can determine whether we were dragging south or
       * east by checking the X-coordinates of the tiles */
      if (TileX(end_tile) > TileX(start_tile)) {
        /* Dragging south does not need to change the start tile. */
        end_tile = TileAddByDir(end_tile, DIR_S);
      } else {
        /* Dragging east. */
        start_tile = TileAddByDir(start_tile, DIR_SW);
        end_tile = TileAddByDir(end_tile, DIR_SE);
      }
      [[fallthrough]];
 
    case HT_POINT:
      h0 = TileHeight(start_tile);
      h1 = TileHeight(end_tile);
      break;
    default: { // All other types, this is mostly only line/autorail
      static const HighLightStyle flip_style_direction[] = {
        HT_DIR_X, HT_DIR_Y, HT_DIR_HL, HT_DIR_HU, HT_DIR_VR, HT_DIR_VL
      };
      static const std::pair<TileIndexDiffC, TileIndexDiffC> start_heightdiff_line_by_dir[] = {
        { {1, 0}, {1, 1} }, // HT_DIR_X
        { {0, 1}, {1, 1} }, // HT_DIR_Y
        { {1, 0}, {0, 0} }, // HT_DIR_HU
        { {1, 0}, {1, 1} }, // HT_DIR_HL
        { {1, 0}, {1, 1} }, // HT_DIR_VL
        { {0, 1}, {1, 1} }, // HT_DIR_VR
      };
      static const std::pair<TileIndexDiffC, TileIndexDiffC> end_heightdiff_line_by_dir[] = {
        { {0, 1}, {0, 0} }, // HT_DIR_X
        { {1, 0}, {0, 0} }, // HT_DIR_Y
        { {0, 1}, {0, 0} }, // HT_DIR_HU
        { {1, 1}, {0, 1} }, // HT_DIR_HL
        { {1, 0}, {0, 0} }, // HT_DIR_VL
        { {0, 0}, {0, 1} }, // HT_DIR_VR
      };
      static_assert(std::size(start_heightdiff_line_by_dir) == HT_DIR_END);
      static_assert(std::size(end_heightdiff_line_by_dir) == HT_DIR_END);
 
      distance %= 2; // we're only interested if the distance is even or uneven
      style &= HT_DIR_MASK;
      assert(style < HT_DIR_END);
 
      /* To handle autorail, we do some magic to be able to use a lookup table.
       * Firstly if we drag the other way around, we switch start&end, and if needed
       * also flip the drag-position. Eg if it was on the left, and the distance is even
       * that means the end, which is now the start is on the right */
      if (swap && distance == 0) style = flip_style_direction[style];
 
      /* Lambda to help calculating the height at one side of the line. */
      auto get_height = [](auto &tile, auto &heightdiffs) {
        return std::max(
          TileHeight(TileAdd(tile, ToTileIndexDiff(heightdiffs.first))),
          TileHeight(TileAdd(tile, ToTileIndexDiff(heightdiffs.second))));
      };
 
      /* Use lookup table for start-tile based on HighLightStyle direction */
      h0 = get_height(start_tile, start_heightdiff_line_by_dir[style]);
 
      /* Use lookup table for end-tile based on HighLightStyle direction
       * flip around side (lower/upper, left/right) based on distance */
      if (distance == 0) style = flip_style_direction[style];
      h1 = get_height(end_tile, end_heightdiff_line_by_dir[style]);
      break;
    }
  }
 
  if (swap) std::swap(h0, h1);
  return (int)(h1 - h0) * TILE_HEIGHT_STEP;
}

static void CheckUnderflow(int &test, int &other, int mult)
{
  if (test >= 0) return;
 
  other += mult * test;
  test = 0;
}

static void CheckOverflow(int &test, int &other, int max, int mult)
{
  if (test <= max) return;
 
  other += mult * (test - max);
  test = max;
}

static void CalcRaildirsDrawstyle(int x, int y, int method)
{
  HighLightStyle b;
 
  int dx = _thd.selstart.x - (_thd.selend.x & ~TILE_UNIT_MASK);
  int dy = _thd.selstart.y - (_thd.selend.y & ~TILE_UNIT_MASK);
  uint w = abs(dx) + TILE_SIZE;
  uint h = abs(dy) + TILE_SIZE;
 
  if (method & ~(VPM_RAILDIRS | VPM_SIGNALDIRS)) {
    /* We 'force' a selection direction; first four rail buttons. */
    method &= ~(VPM_RAILDIRS | VPM_SIGNALDIRS);
    int raw_dx = _thd.selstart.x - _thd.selend.x;
    int raw_dy = _thd.selstart.y - _thd.selend.y;
    switch (method) {
      case VPM_FIX_X:
        b = HT_LINE | HT_DIR_Y;
        x = _thd.selstart.x;
        break;
 
      case VPM_FIX_Y:
        b = HT_LINE | HT_DIR_X;
        y = _thd.selstart.y;
        break;
 
      case VPM_FIX_HORIZONTAL:
        if (dx == -dy) {
          /* We are on a straight horizontal line. Determine the 'rail'
           * to build based the sub tile location. */
          b = (x & TILE_UNIT_MASK) + (y & TILE_UNIT_MASK) >= TILE_SIZE ? HT_LINE | HT_DIR_HL : HT_LINE | HT_DIR_HU;
        } else {
          /* We are not on a straight line. Determine the rail to build
           * based on whether we are above or below it. */
          b = dx + dy >= (int)TILE_SIZE ? HT_LINE | HT_DIR_HU : HT_LINE | HT_DIR_HL;
 
          /* Calculate where a horizontal line through the start point and
           * a vertical line from the selected end point intersect and
           * use that point as the end point. */
          int offset = (raw_dx - raw_dy) / 2;
          x = _thd.selstart.x - (offset & ~TILE_UNIT_MASK);
          y = _thd.selstart.y + (offset & ~TILE_UNIT_MASK);
 
          /* 'Build' the last half rail tile if needed */
          if ((offset & TILE_UNIT_MASK) > (TILE_SIZE / 2)) {
            if (dx + dy >= (int)TILE_SIZE) {
              x -= (int)TILE_SIZE;
            } else {
              y += (int)TILE_SIZE;
            }
          }
 
          /* Make sure we do not overflow the map! */
          CheckUnderflow(x, y, 1);
          CheckUnderflow(y, x, 1);
          CheckOverflow(x, y, (Map::MaxX() - 1) * TILE_SIZE, 1);
          CheckOverflow(y, x, (Map::MaxY() - 1) * TILE_SIZE, 1);
          assert(x >= 0 && y >= 0 && x <= (int)(Map::MaxX() * TILE_SIZE) && y <= (int)(Map::MaxY() * TILE_SIZE));
        }
        break;
 
      case VPM_FIX_VERTICAL:
        if (dx == dy) {
          /* We are on a straight vertical line. Determine the 'rail'
           * to build based the sub tile location. */
          b = (x & TILE_UNIT_MASK) > (y & TILE_UNIT_MASK) ? HT_LINE | HT_DIR_VL : HT_LINE | HT_DIR_VR;
        } else {
          /* We are not on a straight line. Determine the rail to build
           * based on whether we are left or right from it. */
          b = dx < dy ? HT_LINE | HT_DIR_VL : HT_LINE | HT_DIR_VR;
 
          /* Calculate where a vertical line through the start point and
           * a horizontal line from the selected end point intersect and
           * use that point as the end point. */
          int offset = (raw_dx + raw_dy + (int)TILE_SIZE) / 2;
          x = _thd.selstart.x - (offset & ~TILE_UNIT_MASK);
          y = _thd.selstart.y - (offset & ~TILE_UNIT_MASK);
 
          /* 'Build' the last half rail tile if needed */
          if ((offset & TILE_UNIT_MASK) > (TILE_SIZE / 2)) {
            if (dx < dy) {
              y -= (int)TILE_SIZE;
            } else {
              x -= (int)TILE_SIZE;
            }
          }
 
          /* Make sure we do not overflow the map! */
          CheckUnderflow(x, y, -1);
          CheckUnderflow(y, x, -1);
          CheckOverflow(x, y, (Map::MaxX() - 1) * TILE_SIZE, -1);
          CheckOverflow(y, x, (Map::MaxY() - 1) * TILE_SIZE, -1);
          assert(x >= 0 && y >= 0 && x <= (int)(Map::MaxX() * TILE_SIZE) && y <= (int)(Map::MaxY() * TILE_SIZE));
        }
        break;
 
      default:
        NOT_REACHED();
    }
  } else if (TileVirtXY(_thd.selstart.x, _thd.selstart.y) == TileVirtXY(x, y)) { // check if we're only within one tile
    if (method & VPM_RAILDIRS) {
      b = GetAutorailHT(x, y);
    } else { // rect for autosignals on one tile
      b = HT_RECT;
    }
  } else if (h == TILE_SIZE) { // Is this in X direction?
    if (dx == (int)TILE_SIZE) { // 2x1 special handling
      b = Check2x1AutoRail(DIAGDIR_NE) | HT_LINE;
    } else if (dx == -(int)TILE_SIZE) {
      b = Check2x1AutoRail(DIAGDIR_SW) | HT_LINE;
    } else {
      b = HT_LINE | HT_DIR_X;
    }
    y = _thd.selstart.y;
  } else if (w == TILE_SIZE) { // Or Y direction?
    if (dy == (int)TILE_SIZE) { // 2x1 special handling
      b = Check2x1AutoRail(DIAGDIR_NW) | HT_LINE;
    } else if (dy == -(int)TILE_SIZE) { // 2x1 other direction
      b = Check2x1AutoRail(DIAGDIR_SE) | HT_LINE;
    } else {
      b = HT_LINE | HT_DIR_Y;
    }
    x = _thd.selstart.x;
  } else if (w > h * 2) { // still count as x dir?
    b = HT_LINE | HT_DIR_X;
    y = _thd.selstart.y;
  } else if (h > w * 2) { // still count as y dir?
    b = HT_LINE | HT_DIR_Y;
    x = _thd.selstart.x;
  } else { // complicated direction
    int d = w - h;
    _thd.selend.x = _thd.selend.x & ~TILE_UNIT_MASK;
    _thd.selend.y = _thd.selend.y & ~TILE_UNIT_MASK;
 
    /* four cases. */
    if (x > _thd.selstart.x) {
      if (y > _thd.selstart.y) {
        /* south */
        if (d == 0) {
          b = (x & TILE_UNIT_MASK) > (y & TILE_UNIT_MASK) ? HT_LINE | HT_DIR_VL : HT_LINE | HT_DIR_VR;
        } else if (d >= 0) {
          x = _thd.selstart.x + h;
          b = HT_LINE | HT_DIR_VL;
        } else {
          y = _thd.selstart.y + w;
          b = HT_LINE | HT_DIR_VR;
        }
      } else {
        /* west */
        if (d == 0) {
          b = (x & TILE_UNIT_MASK) + (y & TILE_UNIT_MASK) >= TILE_SIZE ? HT_LINE | HT_DIR_HL : HT_LINE | HT_DIR_HU;
        } else if (d >= 0) {
          x = _thd.selstart.x + h;
          b = HT_LINE | HT_DIR_HL;
        } else {
          y = _thd.selstart.y - w;
          b = HT_LINE | HT_DIR_HU;
        }
      }
    } else {
      if (y > _thd.selstart.y) {
        /* east */
        if (d == 0) {
          b = (x & TILE_UNIT_MASK) + (y & TILE_UNIT_MASK) >= TILE_SIZE ? HT_LINE | HT_DIR_HL : HT_LINE | HT_DIR_HU;
        } else if (d >= 0) {
          x = _thd.selstart.x - h;
          b = HT_LINE | HT_DIR_HU;
        } else {
          y = _thd.selstart.y + w;
          b = HT_LINE | HT_DIR_HL;
        }
      } else {
        /* north */
        if (d == 0) {
          b = (x & TILE_UNIT_MASK) > (y & TILE_UNIT_MASK) ? HT_LINE | HT_DIR_VL : HT_LINE | HT_DIR_VR;
        } else if (d >= 0) {
          x = _thd.selstart.x - h;
          b = HT_LINE | HT_DIR_VR;
        } else {
          y = _thd.selstart.y - w;
          b = HT_LINE | HT_DIR_VL;
        }
      }
    }
  }
 
  if (_settings_client.gui.measure_tooltip) {
    TileIndex t0 = TileVirtXY(_thd.selstart.x, _thd.selstart.y);
    TileIndex t1 = TileVirtXY(x, y);
    uint distance = DistanceManhattan(t0, t1) + 1;
 
    if (distance == 1) {
      HideMeasurementTooltips();
    } else {
      int heightdiff = CalcHeightdiff(b, distance, t0, t1);
      /* If we are showing a tooltip for horizontal or vertical drags,
       * 2 tiles have a length of 1. To bias towards the ceiling we add
       * one before division. It feels more natural to count 3 lengths as 2 */
      if ((b & HT_DIR_MASK) != HT_DIR_X && (b & HT_DIR_MASK) != HT_DIR_Y) {
        distance = CeilDiv(distance, 2);
      }
 
      if (heightdiff == 0) {
        ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_LENGTH, distance));
      } else {
        ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_LENGTH_HEIGHTDIFF, distance, heightdiff));
      }
    }
  }
 
  _thd.selend.x = x;
  _thd.selend.y = y;
  _thd.next_drawstyle = b;
}

void VpSelectTilesWithMethod(int x, int y, ViewportPlaceMethod method)
{
  int sx, sy;
  HighLightStyle style;
 
  if (x == -1) {
    _thd.selend.x = -1;
    return;
  }
 
  /* Special handling of drag in any (8-way) direction */
  if (method & (VPM_RAILDIRS | VPM_SIGNALDIRS)) {
    _thd.selend.x = x;
    _thd.selend.y = y;
    CalcRaildirsDrawstyle(x, y, method);
    return;
  }
 
  /* Needed so level-land is placed correctly */
  if ((_thd.next_drawstyle & HT_DRAG_MASK) == HT_POINT) {
    x += TILE_SIZE / 2;
    y += TILE_SIZE / 2;
  }
 
  sx = _thd.selstart.x;
  sy = _thd.selstart.y;
 
  int limit = 0;
 
  switch (method) {
    case VPM_X_OR_Y: // drag in X or Y direction
      if (abs(sy - y) < abs(sx - x)) {
        y = sy;
        style = HT_DIR_X;
      } else {
        x = sx;
        style = HT_DIR_Y;
      }
      goto calc_heightdiff_single_direction;
 
    case VPM_X_LIMITED: // Drag in X direction (limited size).
      limit = (_thd.sizelimit - 1) * TILE_SIZE;
      [[fallthrough]];
 
    case VPM_FIX_X: // drag in Y direction
      x = sx;
      style = HT_DIR_Y;
      goto calc_heightdiff_single_direction;
 
    case VPM_Y_LIMITED: // Drag in Y direction (limited size).
      limit = (_thd.sizelimit - 1) * TILE_SIZE;
      [[fallthrough]];
 
    case VPM_FIX_Y: // drag in X direction
      y = sy;
      style = HT_DIR_X;
 
calc_heightdiff_single_direction:;
      if (limit > 0) {
        x = sx + Clamp(x - sx, -limit, limit);
        y = sy + Clamp(y - sy, -limit, limit);
      }
      if (_settings_client.gui.measure_tooltip) {
        TileIndex t0 = TileVirtXY(sx, sy);
        TileIndex t1 = TileVirtXY(x, y);
        uint distance = DistanceManhattan(t0, t1) + 1;
 
        if (distance == 1) {
          HideMeasurementTooltips();
        } else {
          /* With current code passing a HT_LINE style to calculate the height
           * difference is enough. However if/when a point-tool is created
           * with this method, function should be called with new_style (below)
           * instead of HT_LINE | style case HT_POINT is handled specially
           * new_style := (_thd.next_drawstyle & HT_RECT) ? HT_LINE | style : _thd.next_drawstyle; */
          int heightdiff = CalcHeightdiff(HT_LINE | style, 0, t0, t1);
 
          if (heightdiff == 0) {
            ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_LENGTH, distance));
          } else {
            ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_LENGTH_HEIGHTDIFF, distance, heightdiff));
          }
        }
      }
      break;
 
    case VPM_X_AND_Y_LIMITED: // Drag an X by Y constrained rect area.
      limit = (_thd.sizelimit - 1) * TILE_SIZE;
      x = sx + Clamp(x - sx, -limit, limit);
      y = sy + Clamp(y - sy, -limit, limit);
      [[fallthrough]];
 
    case VPM_X_AND_Y: // drag an X by Y area
      if (_settings_client.gui.measure_tooltip) {
        TileIndex t0 = TileVirtXY(sx, sy);
        TileIndex t1 = TileVirtXY(x, y);
        uint dx = Delta(TileX(t0), TileX(t1)) + 1;
        uint dy = Delta(TileY(t0), TileY(t1)) + 1;
 
        /* If dragging an area (eg dynamite tool) and it is actually a single
         * row/column, change the type to 'line' to get proper calculation for height */
        style = (HighLightStyle)_thd.next_drawstyle;
        if (_thd.IsDraggingDiagonal()) {
          /* Determine the "area" of the diagonal dragged selection.
           * We assume the area is the number of tiles along the X
           * edge and the number of tiles along the Y edge. However,
           * multiplying these two numbers does not give the exact
           * number of tiles; basically we are counting the black
           * squares on a chess board and ignore the white ones to
           * make the tile counts at the edges match up. There is no
           * other way to make a proper count though.
           *
           * First convert to the rotated coordinate system. */
          int dist_x = TileX(t0) - TileX(t1);
          int dist_y = TileY(t0) - TileY(t1);
          int a_max = dist_x + dist_y;
          int b_max = dist_y - dist_x;
 
          /* Now determine the size along the edge, but due to the
           * chess board principle this counts double. */
          a_max = abs(a_max + (a_max > 0 ? 2 : -2)) / 2;
          b_max = abs(b_max + (b_max > 0 ? 2 : -2)) / 2;
 
          /* We get a 1x1 on normal 2x1 rectangles, due to it being
           * a seen as two sides. As the result for actual building
           * will be the same as non-diagonal dragging revert to that
           * behaviour to give it a more normally looking size. */
          if (a_max != 1 || b_max != 1) {
            dx = a_max;
            dy = b_max;
          }
        } else if (style & HT_RECT) {
          if (dx == 1) {
            style = HT_LINE | HT_DIR_Y;
          } else if (dy == 1) {
            style = HT_LINE | HT_DIR_X;
          }
        }
 
        if (dx != 1 || dy != 1) {
          int heightdiff = CalcHeightdiff(style, 0, t0, t1);
 
          dx -= (style & HT_POINT ? 1 : 0);
          dy -= (style & HT_POINT ? 1 : 0);
 
          if (heightdiff == 0) {
            ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_AREA, dx, dy));
          } else {
            ShowMeasurementTooltips(GetEncodedString(STR_MEASURE_AREA_HEIGHTDIFF, dx, dy, heightdiff));
          }
        }
      }
      break;
 
    default: NOT_REACHED();
  }
 
  _thd.selend.x = x;
  _thd.selend.y = y;
}

EventState VpHandlePlaceSizingDrag()
{
  if (_special_mouse_mode != WSM_SIZING && _special_mouse_mode != WSM_DRAGGING) return ES_NOT_HANDLED;
 
  /* stop drag mode if the window has been closed */
  Window *w = _thd.GetCallbackWnd();
  if (w == nullptr) {
    ResetObjectToPlace();
    return ES_HANDLED;
  }
 
  /* while dragging execute the drag procedure of the corresponding window (mostly VpSelectTilesWithMethod() ) */
  if (_left_button_down) {
    if (_special_mouse_mode == WSM_DRAGGING) {
      /* Only register a drag event when the mouse moved. */
      if (_thd.new_pos.x == _thd.selstart.x && _thd.new_pos.y == _thd.selstart.y) return ES_HANDLED;
      _thd.selstart.x = _thd.new_pos.x;
      _thd.selstart.y = _thd.new_pos.y;
    }
 
    w->OnPlaceDrag(_thd.select_method, _thd.select_proc, GetTileBelowCursor());
    return ES_HANDLED;
  }
 
  /* Mouse button released. */
  _special_mouse_mode = WSM_NONE;
  if (_special_mouse_mode == WSM_DRAGGING) return ES_HANDLED;
 
  /* Keep the selected tool, but reset it to the original mode. */
  HighLightStyle others = _thd.place_mode & ~(HT_DRAG_MASK | HT_DIR_MASK);
  if ((_thd.next_drawstyle & HT_DRAG_MASK) == HT_RECT) {
    _thd.place_mode = HT_RECT | others;
  } else if (_thd.select_method & VPM_SIGNALDIRS) {
    _thd.place_mode = HT_RECT | others;
  } else if (_thd.select_method & VPM_RAILDIRS) {
    _thd.place_mode = (_thd.select_method & ~VPM_RAILDIRS) ? _thd.next_drawstyle : (HT_RAIL | others);
  } else {
    _thd.place_mode = HT_POINT | others;
  }
  SetTileSelectSize(1, 1);
 
  HideMeasurementTooltips();
  w->OnPlaceMouseUp(_thd.select_method, _thd.select_proc, _thd.selend, TileVirtXY(_thd.selstart.x, _thd.selstart.y), TileVirtXY(_thd.selend.x, _thd.selend.y));
 
  return ES_HANDLED;
}

void SetObjectToPlaceWnd(CursorID icon, PaletteID pal, HighLightStyle mode, Window *w)
{
  SetObjectToPlace(icon, pal, mode, w->window_class, w->window_number);
}
 
#include "table/animcursors.h"

void SetObjectToPlace(CursorID icon, PaletteID pal, HighLightStyle mode, WindowClass window_class, WindowNumber window_num)
{
  if (_thd.window_class != WC_INVALID) {
    /* Undo clicking on button and drag & drop */
    Window *w = _thd.GetCallbackWnd();
    /* Call the abort function, but set the window class to something
     * that will never be used to avoid infinite loops. Setting it to
     * the 'next' window class must not be done because recursion into
     * this function might in some cases reset the newly set object to
     * place or not properly reset the original selection. */
    _thd.window_class = WC_INVALID;
    if (w != nullptr) {
      w->OnPlaceObjectAbort();
      HideMeasurementTooltips();
    }
  }
 
  /* Mark the old selection dirty, in case the selection shape or colour changes */
  if ((_thd.drawstyle & HT_DRAG_MASK) != HT_NONE) SetSelectionTilesDirty();
 
  SetTileSelectSize(1, 1);
 
  _thd.make_square_red = false;
 
  if (mode == HT_DRAG) { // HT_DRAG is for dragdropping trains in the depot window
    mode = HT_NONE;
    _special_mouse_mode = WSM_DRAGDROP;
  } else {
    _special_mouse_mode = WSM_NONE;
  }
 
  _thd.place_mode = mode;
  _thd.window_class = window_class;
  _thd.window_number = window_num;
 
  if ((mode & HT_DRAG_MASK) == HT_SPECIAL) { // special tools, like tunnels or docks start with presizing mode
    VpStartPreSizing();
  }
 
  SetCursor(icon, pal);
}

void ResetObjectToPlace()
{
  SetObjectToPlace(SPR_CURSOR_MOUSE, PAL_NONE, HT_NONE, WC_MAIN_WINDOW, 0);
}
 
Point GetViewportStationMiddle(const Viewport &vp, const Station *st)
{
  int x = TileX(st->xy) * TILE_SIZE;
  int y = TileY(st->xy) * TILE_SIZE;
  int z = GetSlopePixelZ(Clamp(x, 0, Map::SizeX() * TILE_SIZE - 1), Clamp(y, 0, Map::SizeY() * TILE_SIZE - 1));
 
  Point p = RemapCoords(x, y, z);
  p.x = UnScaleByZoom(p.x - vp.virtual_left, vp.zoom) + vp.left;
  p.y = UnScaleByZoom(p.y - vp.virtual_top, vp.zoom) + vp.top;
  return p;
}

struct ViewportSSCSS {
  VpSorterChecker fct_checker; 
  VpSpriteSorter fct_sorter;   
};

static const ViewportSSCSS _vp_sprite_sorters[] = {
#ifdef WITH_SSE
  { &ViewportSortParentSpritesSSE41Checker, &ViewportSortParentSpritesSSE41 },
#endif
  { []() { return true; /* Always available */ }, &ViewportSortParentSprites }
};

void InitializeSpriteSorter()
{
  for (const auto &sprite_sorter : _vp_sprite_sorters) {
    if (sprite_sorter.fct_checker()) {
      _vp_sprite_sorter = sprite_sorter.fct_sorter;
      break;
    }
  }
  assert(_vp_sprite_sorter != nullptr);
}

CommandCost CmdScrollViewport(DoCommandFlags flags, TileIndex tile, ViewportScrollTarget target, uint32_t ref)
{
  if (_current_company != OWNER_DEITY) return CMD_ERROR;
  switch (target) {
    case VST_EVERYONE:
      break;
    case VST_COMPANY:
      if (_local_company != (CompanyID)ref) return CommandCost();
      break;
    case VST_CLIENT:
      if (_network_own_client_id != (ClientID)ref) return CommandCost();
      break;
    default:
      return CMD_ERROR;
  }
 
  if (flags.Test(DoCommandFlag::Execute)) {
    ResetObjectToPlace();
    ScrollMainWindowToTile(tile);
  }
  return CommandCost();
}
 
void MarkCatchmentTilesDirty()
{
  if (_viewport_highlight_town != nullptr) {
    MarkWholeScreenDirty();
    return;
  }
 
  if (_viewport_highlight_station != nullptr) {
    if (_viewport_highlight_station->catchment_tiles.tile == INVALID_TILE) {
      MarkWholeScreenDirty();
      _viewport_highlight_station = nullptr;
    } else {
      BitmapTileIterator it(_viewport_highlight_station->catchment_tiles);
      for (TileIndex tile = it; tile != INVALID_TILE; tile = ++it) {
        MarkTileDirtyByTile(tile);
      }
    }
  }
 
  if (_viewport_highlight_station_rect != nullptr) {
    if (!_viewport_highlight_station_rect->IsInUse()) {
      _viewport_highlight_station_rect = nullptr;
    }
    MarkWholeScreenDirty();
  }
 
  if (_viewport_highlight_waypoint != nullptr) {
    if (!_viewport_highlight_waypoint->IsInUse()) {
      _viewport_highlight_waypoint = nullptr;
    }
    MarkWholeScreenDirty();
  }
 
  if (_viewport_highlight_waypoint_rect != nullptr) {
    if (!_viewport_highlight_waypoint_rect->IsInUse()) {
      _viewport_highlight_waypoint_rect = nullptr;
    }
    MarkWholeScreenDirty();
  }
}
 
static void SetWindowDirtyForViewportCatchment()
{
  if (_viewport_highlight_station != nullptr) SetWindowDirty(WC_STATION_VIEW, _viewport_highlight_station->index);
  if (_viewport_highlight_station_rect != nullptr) SetWindowDirty(WC_STATION_VIEW, _viewport_highlight_station_rect->index);
  if (_viewport_highlight_waypoint != nullptr) SetWindowDirty(WC_WAYPOINT_VIEW, _viewport_highlight_waypoint->index);
  if (_viewport_highlight_waypoint_rect != nullptr) SetWindowDirty(WC_WAYPOINT_VIEW, _viewport_highlight_waypoint_rect->index);
  if (_viewport_highlight_town != nullptr) SetWindowDirty(WC_TOWN_VIEW, _viewport_highlight_town->index);
}
 
static void ClearViewportCatchment()
{
  MarkCatchmentTilesDirty();
  _viewport_highlight_station = nullptr;
  _viewport_highlight_station_rect = nullptr;
  _viewport_highlight_waypoint = nullptr;
  _viewport_highlight_waypoint_rect = nullptr;
  _viewport_highlight_town = nullptr;
}

void SetViewportCatchmentStation(const Station *st, bool sel)
{
  SetWindowDirtyForViewportCatchment();
  /* Mark tiles dirty for redrawing and update selected station if a different station is already highlighted. */
  if (sel && _viewport_highlight_station != st) {
    ClearViewportCatchment();
    _viewport_highlight_station = st;
    MarkCatchmentTilesDirty();
  /* Mark tiles dirty for redrawing and clear station selection if deselecting highlight. */
  } else if (!sel && _viewport_highlight_station == st) {
    MarkCatchmentTilesDirty();
    _viewport_highlight_station = nullptr;
  }
  /* Redraw the currently selected station window */
  if (_viewport_highlight_station != nullptr) SetWindowDirty(WC_STATION_VIEW, _viewport_highlight_station->index);
}

void SetViewportStationRect(const Station *st, bool sel)
{
  SetWindowDirtyForViewportCatchment();
  /* Mark tiles dirty for redrawing and update selected station if a different station is already highlighted. */
  if (sel && _viewport_highlight_station_rect != st) {
    ClearViewportCatchment();
    _viewport_highlight_station_rect = st;
    MarkCatchmentTilesDirty();
  /* Mark tiles dirty for redrawing and clear station selection if deselecting highlight. */
  } else if (!sel && _viewport_highlight_station_rect == st) {
    MarkCatchmentTilesDirty();
    _viewport_highlight_station_rect = nullptr;
  }
  /* Redraw the currently selected station window */
  if (_viewport_highlight_station_rect != nullptr) SetWindowDirty(WC_STATION_VIEW, _viewport_highlight_station_rect->index);
}

void SetViewportCatchmentWaypoint(const Waypoint *wp, bool sel)
{
  SetWindowDirtyForViewportCatchment();
  /* Mark tiles dirty for redrawing and update selected waypoint if a different waypoint is already highlighted. */
  if (sel && _viewport_highlight_waypoint != wp) {
    ClearViewportCatchment();
    _viewport_highlight_waypoint = wp;
    MarkCatchmentTilesDirty();
  /* Mark tiles dirty for redrawing and clear waypoint selection if deselecting highlight. */
  } else if (!sel && _viewport_highlight_waypoint == wp) {
    MarkCatchmentTilesDirty();
    _viewport_highlight_waypoint = nullptr;
  }
  /* Redraw the currently selected waypoint window */
  if (_viewport_highlight_waypoint != nullptr) SetWindowDirty(WC_WAYPOINT_VIEW, _viewport_highlight_waypoint->index);
}

void SetViewportWaypointRect(const Waypoint *wp, bool sel)
{
  SetWindowDirtyForViewportCatchment();
  /* Mark tiles dirty for redrawing and update selected waypoint if a different waypoint is already highlighted. */
  if (sel && _viewport_highlight_waypoint_rect != wp) {
    ClearViewportCatchment();
    _viewport_highlight_waypoint_rect = wp;
    MarkCatchmentTilesDirty();
  /* Mark tiles dirty for redrawing and clear waypoint selection if deselecting highlight. */
  } else if (!sel && _viewport_highlight_waypoint_rect == wp) {
    MarkCatchmentTilesDirty();
    _viewport_highlight_waypoint_rect = nullptr;
  }
  /* Redraw the currently selected waypoint window */
  if (_viewport_highlight_waypoint_rect != nullptr) SetWindowDirty(WC_WAYPOINT_VIEW, _viewport_highlight_waypoint_rect->index);
}

void SetViewportCatchmentTown(const Town *t, bool sel)
{
  SetWindowDirtyForViewportCatchment();
  /* Mark tiles dirty for redrawing and update selected town if a different town is already highlighted. */
  if (sel && _viewport_highlight_town != t) {
    ClearViewportCatchment();
    _viewport_highlight_town = t;
    MarkWholeScreenDirty();
  /* Mark tiles dirty for redrawing and clear town selection if deselecting highlight. */
  } else if (!sel && _viewport_highlight_town == t) {
    _viewport_highlight_town = nullptr;
    MarkWholeScreenDirty();
  }
  /* Redraw the currently selected town window */
  if (_viewport_highlight_town != nullptr) SetWindowDirty(WC_TOWN_VIEW, _viewport_highlight_town->index);
}

void ViewportData::CancelFollow(const Window &viewport_window)
{
  if (this->follow_vehicle == VehicleID::Invalid()) return;
 
  if (viewport_window.window_class == WC_MAIN_WINDOW) {
    /* We're cancelling follow in the main viewport, so we need to check for a vehicle view window
     * to raise the location follow widget. */
    Window *vehicle_window = FindWindowById(WC_VEHICLE_VIEW, this->follow_vehicle);
    if (vehicle_window != nullptr) vehicle_window->RaiseWidgetWhenLowered(WID_VV_LOCATION);
  }
 
  this->follow_vehicle = VehicleID::Invalid();
}