src/blitter/common.hpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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 <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file common.hpp Common functionality for all blitter implementations. */
   9
  10 #ifndef BLITTER_COMMON_HPP
  11 #define BLITTER_COMMON_HPP
  12
  13 #include "base.hpp"
  14 #include "../core/math_func.hpp"
  15
  16 #include <utility>
  17
  18 template <typename SetPixelT>
  19 void Blitter::DrawLineGeneric(int x1, int y1, int x2, int y2, int screen_width, int screen_height, int width, int dash, SetPixelT set_pixel)
  20 {
  21         int dy;
  22         int dx;
  23         int stepx;
  24         int stepy;
  25
  26         dy = (y2 - y1) * 2;
  27         if (dy < 0) {
  28                 dy = -dy;
  29                 stepy = -1;
  30         } else {
  31                 stepy = 1;
  32         }
  33
  34         dx = (x2 - x1) * 2;
  35         if (dx < 0) {
  36                 dx = -dx;
  37                 stepx = -1;
  38         } else {
  39                 stepx = 1;
  40         }
  41
  42         if (dx == 0 && dy == 0) {
  43                 /* The algorithm below cannot handle this special case; make it work at least for line width 1 */
  44                 if (x1 >= 0 && x1 < screen_width && y1 >= 0 && y1 < screen_height) set_pixel(x1, y1);
  45                 return;
  46         }
  47
  48         int frac_diff = width * std::max(dx, dy);
  49         if (width > 1) {
  50                 /* compute frac_diff = width * sqrt(dx*dx + dy*dy)
  51                  * Start interval:
  52                  *    max(dx, dy) <= sqrt(dx*dx + dy*dy) <= sqrt(2) * max(dx, dy) <= 3/2 * max(dx, dy) */
  53                 int64_t frac_sq = ((int64_t) width) * ((int64_t) width) * (((int64_t) dx) * ((int64_t) dx) + ((int64_t) dy) * ((int64_t) dy));
  54                 int frac_max = 3 * frac_diff / 2;
  55                 while (frac_diff < frac_max) {
  56                         int frac_test = (frac_diff + frac_max) / 2;
  57                         if (((int64_t) frac_test) * ((int64_t) frac_test) < frac_sq) {
  58                                 frac_diff = frac_test + 1;
  59                         } else {
  60                                 frac_max = frac_test - 1;
  61                         }
  62                 }
  63         }
  64
  65         int gap = dash;
  66         if (dash == 0) dash = 1;
  67         int dash_count = 0;
  68         if (dx > dy) {
  69                 if (stepx < 0) {
  70                         std::swap(x1, x2);
  71                         std::swap(y1, y2);
  72                         stepy = -stepy;
  73                 }
  74                 if (x2 < 0 || x1 >= screen_width) return;
  75
  76                 int y_low     = y1;
  77                 int y_high    = y1;
  78                 int frac_low  = dy - frac_diff / 2;
  79                 int frac_high = dy + frac_diff / 2;
  80
  81                 while (frac_low < -(dx / 2)) {
  82                         frac_low += dx;
  83                         y_low -= stepy;
  84                 }
  85                 while (frac_high >= dx / 2) {
  86                         frac_high -= dx;
  87                         y_high += stepy;
  88                 }
  89
  90                 if (x1 < 0) {
  91                         dash_count = (-x1) % (dash + gap);
  92                         auto adjust_frac = [&](int64_t frac, int &y_bound) -> int {
  93                                 frac -= ((int64_t) dy) * ((int64_t) x1);
  94                                 if (frac >= 0) {
  95                                         int quotient = frac / dx;
  96                                         int remainder = frac % dx;
  97                                         y_bound += (1 + quotient) * stepy;
  98                                         frac = remainder - dx;
  99                                 }
 100                                 return frac;
 101                         };
 102                         frac_low = adjust_frac(frac_low, y_low);
 103                         frac_high = adjust_frac(frac_high, y_high);
 104                         x1 = 0;
 105                 }
 106                 x2++;
 107                 if (x2 > screen_width) {
 108                         x2 = screen_width;
 109                 }
 110
 111                 while (x1 != x2) {
 112                         if (dash_count < dash) {
 113                                 for (int y = y_low; y != y_high; y += stepy) {
 114                                         if (y >= 0 && y < screen_height) set_pixel(x1, y);
 115                                 }
 116                         }
 117                         if (frac_low >= 0) {
 118                                 y_low += stepy;
 119                                 frac_low -= dx;
 120                         }
 121                         if (frac_high >= 0) {
 122                                 y_high += stepy;
 123                                 frac_high -= dx;
 124                         }
 125                         x1++;
 126                         frac_low += dy;
 127                         frac_high += dy;
 128                         if (++dash_count >= dash + gap) dash_count = 0;
 129                 }
 130         } else {
 131                 if (stepy < 0) {
 132                         std::swap(x1, x2);
 133                         std::swap(y1, y2);
 134                         stepx = -stepx;
 135                 }
 136                 if (y2 < 0 || y1 >= screen_height) return;
 137
 138                 int x_low     = x1;
 139                 int x_high    = x1;
 140                 int frac_low  = dx - frac_diff / 2;
 141                 int frac_high = dx + frac_diff / 2;
 142
 143                 while (frac_low < -(dy / 2)) {
 144                         frac_low += dy;
 145                         x_low -= stepx;
 146                 }
 147                 while (frac_high >= dy / 2) {
 148                         frac_high -= dy;
 149                         x_high += stepx;
 150                 }
 151
 152                 if (y1 < 0) {
 153                         dash_count = (-y1) % (dash + gap);
 154                         auto adjust_frac = [&](int64_t frac, int &x_bound) -> int {
 155                                 frac -= ((int64_t) dx) * ((int64_t) y1);
 156                                 if (frac >= 0) {
 157                                         int quotient = frac / dy;
 158                                         int remainder = frac % dy;
 159                                         x_bound += (1 + quotient) * stepx;
 160                                         frac = remainder - dy;
 161                                 }
 162                                 return frac;
 163                         };
 164                         frac_low = adjust_frac(frac_low, x_low);
 165                         frac_high = adjust_frac(frac_high, x_high);
 166                         y1 = 0;
 167                 }
 168                 y2++;
 169                 if (y2 > screen_height) {
 170                         y2 = screen_height;
 171                 }
 172
 173                 while (y1 != y2) {
 174                         if (dash_count < dash) {
 175                                 for (int x = x_low; x != x_high; x += stepx) {
 176                                         if (x >= 0 && x < screen_width) set_pixel(x, y1);
 177                                 }
 178                         }
 179                         if (frac_low >= 0) {
 180                                 x_low += stepx;
 181                                 frac_low -= dy;
 182                         }
 183                         if (frac_high >= 0) {
 184                                 x_high += stepx;
 185                                 frac_high -= dy;
 186                         }
 187                         y1++;
 188                         frac_low += dx;
 189                         frac_high += dx;
 190                         if (++dash_count >= dash + gap) dash_count = 0;
 191                 }
 192         }
 193 }
 194
 195 #endif /* BLITTER_COMMON_HPP */