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