1 /* Copyright (C) 2018 Wildfire Games.
2 * This file is part of 0 A.D.
3 *
4 * 0 A.D. is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * 0 A.D. is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "precompiled.h"
19
20 #include "Geometry.h"
21
22 using namespace Geometry;
23
24 // TODO: all of these things could be optimised quite easily
25
GetHalfBoundingBox(const CFixedVector2D & u,const CFixedVector2D & v,const CFixedVector2D & halfSize)26 CFixedVector2D Geometry::GetHalfBoundingBox(const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
27 {
28 return CFixedVector2D(
29 u.X.Multiply(halfSize.X).Absolute() + v.X.Multiply(halfSize.Y).Absolute(),
30 u.Y.Multiply(halfSize.X).Absolute() + v.Y.Multiply(halfSize.Y).Absolute()
31 );
32 }
33
DistanceToSquare(const CFixedVector2D & point,const CFixedVector2D & u,const CFixedVector2D & v,const CFixedVector2D & halfSize,bool countInsideAsZero)34 fixed Geometry::DistanceToSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize, bool countInsideAsZero)
35 {
36 /*
37 * Relative to its own coordinate system, we have a square like:
38 *
39 * A : B : C
40 * : :
41 * - - ########### - -
42 * # #
43 * # I #
44 * D # 0 # E v
45 * # # ^
46 * # # |
47 * - - ########### - - -->u
48 * : :
49 * F : G : H
50 *
51 * where 0 is the center, u and v are unit axes,
52 * and the square is hw*2 by hh*2 units in size.
53 *
54 * Points in the BIG regions should check distance to horizontal edges.
55 * Points in the DIE regions should check distance to vertical edges.
56 * Points in the ACFH regions should check distance to the corresponding corner.
57 *
58 * So we just need to check all of the regions to work out which calculations to apply.
59 *
60 */
61
62 // By symmetry (taking absolute values), we work only in the 0-B-C-E quadrant
63 // du, dv are the location of the point in the square's coordinate system
64 fixed du = point.Dot(u).Absolute();
65 fixed dv = point.Dot(v).Absolute();
66
67 fixed hw = halfSize.X;
68 fixed hh = halfSize.Y;
69
70 if (du < hw) // regions B, I, G
71 {
72 if (dv < hh) // region I
73 return countInsideAsZero ? fixed::Zero() : std::min(hw - du, hh - dv);
74 else
75 return dv - hh;
76 }
77 else if (dv < hh) // regions D, E
78 {
79 return du - hw; // vertical edges
80 }
81 else // regions A, C, F, H
82 {
83 CFixedVector2D distance(du - hw, dv - hh);
84 return distance.Length();
85 }
86 }
87
88 // Same as above except it does not use Length
89 // For explanations refer to DistanceToSquare
DistanceToSquareSquared(const CFixedVector2D & point,const CFixedVector2D & u,const CFixedVector2D & v,const CFixedVector2D & halfSize,bool countInsideAsZero)90 fixed Geometry::DistanceToSquareSquared(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize, bool countInsideAsZero)
91 {
92 fixed du = point.Dot(u).Absolute();
93 fixed dv = point.Dot(v).Absolute();
94
95 fixed hw = halfSize.X;
96 fixed hh = halfSize.Y;
97
98 if (du < hw) // regions B, I, G
99 {
100 if (dv < hh) // region I
101 return countInsideAsZero ? fixed::Zero() : std::min((hw - du).Square(), (hh - dv).Square());
102 else
103 return (dv - hh).Square(); // horizontal edges
104 }
105 else if (dv < hh) // regions D, E
106 {
107 return (du - hw).Square(); // vertical edges
108 }
109 else // regions A, C, F, H
110 {
111 return (du - hw).Square() + (dv - hh).Square();
112 }
113 }
114
NearestPointOnSquare(const CFixedVector2D & point,const CFixedVector2D & u,const CFixedVector2D & v,const CFixedVector2D & halfSize)115 CFixedVector2D Geometry::NearestPointOnSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
116 {
117 /*
118 * Relative to its own coordinate system, we have a square like:
119 *
120 * A : : C
121 * : :
122 * - - #### B #### - -
123 * #\ /#
124 * # \ / #
125 * D --0-- E v
126 * # / \ # ^
127 * #/ \# |
128 * - - #### G #### - - -->u
129 * : :
130 * F : : H
131 *
132 * where 0 is the center, u and v are unit axes,
133 * and the square is hw*2 by hh*2 units in size.
134 *
135 * Points in the BDEG regions are nearest to the corresponding edge.
136 * Points in the ACFH regions are nearest to the corresponding corner.
137 *
138 * So we just need to check all of the regions to work out which calculations to apply.
139 *
140 */
141
142 // du, dv are the location of the point in the square's coordinate system
143 fixed du = point.Dot(u);
144 fixed dv = point.Dot(v);
145
146 fixed hw = halfSize.X;
147 fixed hh = halfSize.Y;
148
149 if (-hw < du && du < hw) // regions B, G; or regions D, E inside the square
150 {
151 if (-hh < dv && dv < hh && (du.Absolute() - hw).Absolute() < (dv.Absolute() - hh).Absolute()) // regions D, E
152 {
153 if (du >= fixed::Zero()) // E
154 return u.Multiply(hw) + v.Multiply(dv);
155 else // D
156 return -u.Multiply(hw) + v.Multiply(dv);
157 }
158 else // B, G
159 {
160 if (dv >= fixed::Zero()) // B
161 return v.Multiply(hh) + u.Multiply(du);
162 else // G
163 return -v.Multiply(hh) + u.Multiply(du);
164 }
165 }
166 else if (-hh < dv && dv < hh) // regions D, E outside the square
167 {
168 if (du >= fixed::Zero()) // E
169 return u.Multiply(hw) + v.Multiply(dv);
170 else // D
171 return -u.Multiply(hw) + v.Multiply(dv);
172 }
173 else // regions A, C, F, H
174 {
175 CFixedVector2D corner;
176 if (du < fixed::Zero()) // A, F
177 corner -= u.Multiply(hw);
178 else // C, H
179 corner += u.Multiply(hw);
180 if (dv < fixed::Zero()) // F, H
181 corner -= v.Multiply(hh);
182 else // A, C
183 corner += v.Multiply(hh);
184
185 return corner;
186 }
187 }
188
TestRaySquare(const CFixedVector2D & a,const CFixedVector2D & b,const CFixedVector2D & u,const CFixedVector2D & v,const CFixedVector2D & halfSize)189 bool Geometry::TestRaySquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
190 {
191 /*
192 * We only consider collisions to be when the ray goes from outside to inside the shape (and possibly out again).
193 * Various cases to consider:
194 * 'a' inside, 'b' inside -> no collision
195 * 'a' inside, 'b' outside -> no collision
196 * 'a' outside, 'b' inside -> collision
197 * 'a' outside, 'b' outside -> depends; use separating axis theorem:
198 * if the ray's bounding box is outside the square -> no collision
199 * if the whole square is on the same side of the ray -> no collision
200 * otherwise -> collision
201 * (Points on the edge are considered 'inside'.)
202 */
203
204 fixed hw = halfSize.X;
205 fixed hh = halfSize.Y;
206
207 fixed au = a.Dot(u);
208 fixed av = a.Dot(v);
209
210 if (-hw <= au && au <= hw && -hh <= av && av <= hh)
211 return false; // a is inside
212
213 fixed bu = b.Dot(u);
214 fixed bv = b.Dot(v);
215
216 if (-hw <= bu && bu <= hw && -hh <= bv && bv <= hh) // TODO: isn't this subsumed by the next checks?
217 return true; // a is outside, b is inside
218
219 if ((au < -hw && bu < -hw) || (au > hw && bu > hw) || (av < -hh && bv < -hh) || (av > hh && bv > hh))
220 return false; // ab is entirely above/below/side the square
221
222 CFixedVector2D abp = (b - a).Perpendicular();
223 fixed s0 = abp.Dot((u.Multiply(hw) + v.Multiply(hh)) - a);
224 fixed s1 = abp.Dot((u.Multiply(hw) - v.Multiply(hh)) - a);
225 fixed s2 = abp.Dot((-u.Multiply(hw) - v.Multiply(hh)) - a);
226 fixed s3 = abp.Dot((-u.Multiply(hw) + v.Multiply(hh)) - a);
227 if (s0.IsZero() || s1.IsZero() || s2.IsZero() || s3.IsZero())
228 return true; // ray intersects the corner
229
230 bool sign = (s0 < fixed::Zero());
231 if ((s1 < fixed::Zero()) != sign || (s2 < fixed::Zero()) != sign || (s3 < fixed::Zero()) != sign)
232 return true; // ray cuts through the square
233
234 return false;
235 }
236
237 // Exactly like TestRaySquare with u=(1,0), v=(0,1)
TestRayAASquare(const CFixedVector2D & a,const CFixedVector2D & b,const CFixedVector2D & halfSize)238 bool Geometry::TestRayAASquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& halfSize)
239 {
240 fixed hw = halfSize.X;
241 fixed hh = halfSize.Y;
242
243 if (-hw <= a.X && a.X <= hw && -hh <= a.Y && a.Y <= hh)
244 return false; // a is inside
245
246 if (-hw <= b.X && b.X <= hw && -hh <= b.Y && b.Y <= hh) // TODO: isn't this subsumed by the next checks?
247 return true; // a is outside, b is inside
248
249 if ((a.X < -hw && b.X < -hw) || (a.X > hw && b.X > hw) || (a.Y < -hh && b.Y < -hh) || (a.Y > hh && b.Y > hh))
250 return false; // ab is entirely above/below/side the square
251
252 CFixedVector2D abp = (b - a).Perpendicular();
253 fixed s0 = abp.Dot(CFixedVector2D(hw, hh) - a);
254 fixed s1 = abp.Dot(CFixedVector2D(hw, -hh) - a);
255 fixed s2 = abp.Dot(CFixedVector2D(-hw, -hh) - a);
256 fixed s3 = abp.Dot(CFixedVector2D(-hw, hh) - a);
257 if (s0.IsZero() || s1.IsZero() || s2.IsZero() || s3.IsZero())
258 return true; // ray intersects the corner
259
260 bool sign = (s0 < fixed::Zero());
261 if ((s1 < fixed::Zero()) != sign || (s2 < fixed::Zero()) != sign || (s3 < fixed::Zero()) != sign)
262 return true; // ray cuts through the square
263
264 return false;
265 }
266
267 /**
268 * Separating axis test; returns true if the square defined by u/v/halfSize at the origin
269 * is not entirely on the clockwise side of a line in direction 'axis' passing through 'a'
270 */
SquareSAT(const CFixedVector2D & a,const CFixedVector2D & axis,const CFixedVector2D & u,const CFixedVector2D & v,const CFixedVector2D & halfSize)271 static bool SquareSAT(const CFixedVector2D& a, const CFixedVector2D& axis, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
272 {
273 fixed hw = halfSize.X;
274 fixed hh = halfSize.Y;
275
276 CFixedVector2D p = axis.Perpendicular();
277 if (p.Dot((u.Multiply(hw) + v.Multiply(hh)) - a) <= fixed::Zero())
278 return true;
279 if (p.Dot((u.Multiply(hw) - v.Multiply(hh)) - a) <= fixed::Zero())
280 return true;
281 if (p.Dot((-u.Multiply(hw) - v.Multiply(hh)) - a) <= fixed::Zero())
282 return true;
283 if (p.Dot((-u.Multiply(hw) + v.Multiply(hh)) - a) <= fixed::Zero())
284 return true;
285
286 return false;
287 }
288
TestSquareSquare(const CFixedVector2D & c0,const CFixedVector2D & u0,const CFixedVector2D & v0,const CFixedVector2D & halfSize0,const CFixedVector2D & c1,const CFixedVector2D & u1,const CFixedVector2D & v1,const CFixedVector2D & halfSize1)289 bool Geometry::TestSquareSquare(
290 const CFixedVector2D& c0, const CFixedVector2D& u0, const CFixedVector2D& v0, const CFixedVector2D& halfSize0,
291 const CFixedVector2D& c1, const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1)
292 {
293 // TODO: need to test this carefully
294
295 CFixedVector2D corner0a = c0 + u0.Multiply(halfSize0.X) + v0.Multiply(halfSize0.Y);
296 CFixedVector2D corner0b = c0 - u0.Multiply(halfSize0.X) - v0.Multiply(halfSize0.Y);
297 CFixedVector2D corner1a = c1 + u1.Multiply(halfSize1.X) + v1.Multiply(halfSize1.Y);
298 CFixedVector2D corner1b = c1 - u1.Multiply(halfSize1.X) - v1.Multiply(halfSize1.Y);
299
300 // Do a SAT test for each square vs each edge of the other square
301 if (!SquareSAT(corner0a - c1, -u0, u1, v1, halfSize1))
302 return false;
303 if (!SquareSAT(corner0a - c1, v0, u1, v1, halfSize1))
304 return false;
305 if (!SquareSAT(corner0b - c1, u0, u1, v1, halfSize1))
306 return false;
307 if (!SquareSAT(corner0b - c1, -v0, u1, v1, halfSize1))
308 return false;
309 if (!SquareSAT(corner1a - c0, -u1, u0, v0, halfSize0))
310 return false;
311 if (!SquareSAT(corner1a - c0, v1, u0, v0, halfSize0))
312 return false;
313 if (!SquareSAT(corner1b - c0, u1, u0, v0, halfSize0))
314 return false;
315 if (!SquareSAT(corner1b - c0, -v1, u0, v0, halfSize0))
316 return false;
317
318 return true;
319 }
320
GetPerimeterDistance(int x_max,int y_max,int x,int y)321 int Geometry::GetPerimeterDistance(int x_max, int y_max, int x, int y)
322 {
323 if (x_max <= 0 || y_max <= 0)
324 return 0;
325
326 int quarter = x_max + y_max;
327 if (x == x_max && y >= 0)
328 return y;
329 if (y == y_max)
330 return quarter - x;
331 if (x == -x_max)
332 return 2 * quarter - y;
333 if (y == -y_max)
334 return 3 * quarter + x;
335 if (x == x_max)
336 return 4 * quarter + y;
337 return 0;
338 }
339
GetPerimeterCoordinates(int x_max,int y_max,int k)340 std::pair<int, int> Geometry::GetPerimeterCoordinates(int x_max, int y_max, int k)
341 {
342 if (x_max <= 0 || y_max <= 0)
343 return std::pair<int, int>(0, 0);
344
345 int quarter = x_max + y_max;
346 k %= 4 * quarter;
347 if (k < 0)
348 k += 4 * quarter;
349
350 if (k < y_max)
351 return std::pair<int, int>(x_max, k);
352 if (k < quarter + x_max)
353 return std::pair<int, int>(quarter - k, y_max);
354 if (k < 2 * quarter + y_max)
355 return std::pair<int, int>(-x_max, 2 * quarter - k);
356 if (k < 3 * quarter + x_max)
357 return std::pair<int, int>(k - 3 * quarter, -y_max);
358 return std::pair<int, int>(x_max, k - 4 * quarter);
359 }
360