Line data Source code
1 : /* Copyright (C) 2020 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 : namespace Geometry
23 : {
24 :
25 : // TODO: all of these things could be optimised quite easily
26 :
27 13 : CFixedVector2D GetHalfBoundingBox(const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
28 : {
29 65 : return CFixedVector2D(
30 39 : u.X.Multiply(halfSize.X).Absolute() + v.X.Multiply(halfSize.Y).Absolute(),
31 39 : u.Y.Multiply(halfSize.X).Absolute() + v.Y.Multiply(halfSize.Y).Absolute()
32 26 : );
33 : }
34 :
35 76 : fixed DistanceToSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize, bool countInsideAsZero)
36 : {
37 : /*
38 : * Relative to its own coordinate system, we have a square like:
39 : *
40 : * A : B : C
41 : * : :
42 : * - - ########### - -
43 : * # #
44 : * # I #
45 : * D # 0 # E v
46 : * # # ^
47 : * # # |
48 : * - - ########### - - -->u
49 : * : :
50 : * F : G : H
51 : *
52 : * where 0 is the center, u and v are unit axes,
53 : * and the square is hw*2 by hh*2 units in size.
54 : *
55 : * Points in the BIG regions should check distance to horizontal edges.
56 : * Points in the DIE regions should check distance to vertical edges.
57 : * Points in the ACFH regions should check distance to the corresponding corner.
58 : *
59 : * So we just need to check all of the regions to work out which calculations to apply.
60 : *
61 : */
62 :
63 : // By symmetry (taking absolute values), we work only in the 0-B-C-E quadrant
64 : // du, dv are the location of the point in the square's coordinate system
65 76 : fixed du = point.Dot(u).Absolute();
66 76 : fixed dv = point.Dot(v).Absolute();
67 :
68 76 : fixed hw = halfSize.X;
69 76 : fixed hh = halfSize.Y;
70 :
71 76 : if (du < hw) // regions B, I, G
72 : {
73 7 : if (dv < hh) // region I
74 1 : return countInsideAsZero ? fixed::Zero() : std::min(hw - du, hh - dv);
75 : else
76 6 : return dv - hh;
77 : }
78 69 : else if (dv < hh) // regions D, E
79 : {
80 32 : return du - hw; // vertical edges
81 : }
82 : else // regions A, C, F, H
83 : {
84 37 : CFixedVector2D distance(du - hw, dv - hh);
85 37 : return distance.Length();
86 : }
87 : }
88 :
89 : // Same as above except it does not use Length
90 : // For explanations refer to DistanceToSquare
91 0 : fixed DistanceToSquareSquared(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize, bool countInsideAsZero)
92 : {
93 0 : fixed du = point.Dot(u).Absolute();
94 0 : fixed dv = point.Dot(v).Absolute();
95 :
96 0 : fixed hw = halfSize.X;
97 0 : fixed hh = halfSize.Y;
98 :
99 0 : if (du < hw) // regions B, I, G
100 : {
101 0 : if (dv < hh) // region I
102 0 : return countInsideAsZero ? fixed::Zero() : std::min((hw - du).Square(), (hh - dv).Square());
103 : else
104 0 : return (dv - hh).Square(); // horizontal edges
105 : }
106 0 : else if (dv < hh) // regions D, E
107 : {
108 0 : return (du - hw).Square(); // vertical edges
109 : }
110 : else // regions A, C, F, H
111 : {
112 0 : return (du - hw).Square() + (dv - hh).Square();
113 : }
114 : }
115 :
116 2 : CFixedVector2D NearestPointOnSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
117 : {
118 : /*
119 : * Relative to its own coordinate system, we have a square like:
120 : *
121 : * A : : C
122 : * : :
123 : * - - #### B #### - -
124 : * #\ /#
125 : * # \ / #
126 : * D --0-- E v
127 : * # / \ # ^
128 : * #/ \# |
129 : * - - #### G #### - - -->u
130 : * : :
131 : * F : : H
132 : *
133 : * where 0 is the center, u and v are unit axes,
134 : * and the square is hw*2 by hh*2 units in size.
135 : *
136 : * Points in the BDEG regions are nearest to the corresponding edge.
137 : * Points in the ACFH regions are nearest to the corresponding corner.
138 : *
139 : * So we just need to check all of the regions to work out which calculations to apply.
140 : *
141 : */
142 :
143 : // du, dv are the location of the point in the square's coordinate system
144 2 : fixed du = point.Dot(u);
145 2 : fixed dv = point.Dot(v);
146 :
147 2 : fixed hw = halfSize.X;
148 2 : fixed hh = halfSize.Y;
149 :
150 2 : if (-hw < du && du < hw) // regions B, G; or regions D, E inside the square
151 : {
152 1 : if (-hh < dv && dv < hh && (du.Absolute() - hw).Absolute() < (dv.Absolute() - hh).Absolute()) // regions D, E
153 : {
154 0 : if (du >= fixed::Zero()) // E
155 0 : return u.Multiply(hw) + v.Multiply(dv);
156 : else // D
157 0 : return -u.Multiply(hw) + v.Multiply(dv);
158 : }
159 : else // B, G
160 : {
161 1 : if (dv >= fixed::Zero()) // B
162 0 : return v.Multiply(hh) + u.Multiply(du);
163 : else // G
164 1 : return -v.Multiply(hh) + u.Multiply(du);
165 : }
166 : }
167 1 : else if (-hh < dv && dv < hh) // regions D, E outside the square
168 : {
169 0 : if (du >= fixed::Zero()) // E
170 0 : return u.Multiply(hw) + v.Multiply(dv);
171 : else // D
172 0 : return -u.Multiply(hw) + v.Multiply(dv);
173 : }
174 : else // regions A, C, F, H
175 : {
176 1 : CFixedVector2D corner;
177 1 : if (du < fixed::Zero()) // A, F
178 1 : corner -= u.Multiply(hw);
179 : else // C, H
180 0 : corner += u.Multiply(hw);
181 1 : if (dv < fixed::Zero()) // F, H
182 1 : corner -= v.Multiply(hh);
183 : else // A, C
184 0 : corner += v.Multiply(hh);
185 :
186 1 : return corner;
187 : }
188 : }
189 :
190 18 : fixed DistanceSquareToSquare(const CFixedVector2D& relativePos, const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1, const CFixedVector2D& u2, const CFixedVector2D& v2, const CFixedVector2D& halfSize2)
191 : {
192 : /*
193 : * The shortest distance between two non colliding squares equals the distance between a corner
194 : * and other square. Thus calculating all 8 those distances and taking the smallest.
195 : * For colliding squares we simply return 0. When one of the points is inside the other square
196 : * we depend on DistanceToSquare's countInsideAsZero. When no point is inside the other square,
197 : * it is enough to check that two adjacent edges of one square does not collide with the other square.
198 : */
199 18 : fixed hw1 = halfSize1.X;
200 18 : fixed hh1 = halfSize1.Y;
201 18 : fixed hw2 = halfSize2.X;
202 18 : fixed hh2 = halfSize2.Y;
203 47 : if (TestRaySquare(relativePos + u1.Multiply(hw1) + v1.Multiply(hh1), relativePos - u1.Multiply(hw1) + v1.Multiply(hh1), u2, v2, halfSize2) ||
204 29 : TestRaySquare(relativePos + u1.Multiply(hw1) + v1.Multiply(hh1), relativePos + u1.Multiply(hw1) - v1.Multiply(hh1), u2, v2, halfSize2))
205 9 : return fixed::Zero();
206 :
207 : return std::min(std::min(std::min(
208 18 : DistanceToSquare(relativePos + u1.Multiply(hw1) + v1.Multiply(hh1), u2, v2, halfSize2, true),
209 18 : DistanceToSquare(relativePos + u1.Multiply(hw1) - v1.Multiply(hh1), u2, v2, halfSize2, true)),
210 : std::min(
211 18 : DistanceToSquare(relativePos - u1.Multiply(hw1) + v1.Multiply(hh1), u2, v2, halfSize2, true),
212 18 : DistanceToSquare(relativePos - u1.Multiply(hw1) - v1.Multiply(hh1), u2, v2, halfSize2, true))),
213 : std::min(std::min(
214 18 : DistanceToSquare(relativePos + u2.Multiply(hw2) + v2.Multiply(hh2), u1, v1, halfSize1, true),
215 18 : DistanceToSquare(relativePos + u2.Multiply(hw2) - v2.Multiply(hh2), u1, v1, halfSize1, true)),
216 : std::min(
217 18 : DistanceToSquare(relativePos - u2.Multiply(hw2) + v2.Multiply(hh2), u1, v1, halfSize1, true),
218 54 : DistanceToSquare(relativePos - u2.Multiply(hw2) - v2.Multiply(hh2), u1, v1, halfSize1, true))));
219 : }
220 :
221 38 : fixed MaxDistanceToSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize, bool countInsideAsZero)
222 : {
223 38 : fixed hw = halfSize.X;
224 38 : fixed hh = halfSize.Y;
225 :
226 38 : if (point.Dot(u).Absolute() < hw && point.Dot(v).Absolute() < hh && countInsideAsZero)
227 0 : return fixed::Zero();
228 :
229 : /*
230 : * The maximum distance from a point to an edge of a square equals the greatest distance
231 : * from the point to the a corner. Thus calculating all and taking the greatest.
232 : */
233 : return std::max(std::max(
234 76 : (point + u.Multiply(hw) + v.Multiply(hh)).Length(),
235 76 : (point + u.Multiply(hw) - v.Multiply(hh)).Length()),
236 : std::max(
237 76 : (point - u.Multiply(hw) + v.Multiply(hh)).Length(),
238 152 : (point - u.Multiply(hw) - v.Multiply(hh)).Length()));
239 : }
240 :
241 9 : fixed MaxDistanceSquareToSquare(const CFixedVector2D& relativePos, const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1, const CFixedVector2D& u2, const CFixedVector2D& v2, const CFixedVector2D& halfSize2)
242 : {
243 : /*
244 : * The maximum distance from an edge of a square to the edge of another square
245 : * equals the greatest distance from the any of the 16 corner corner distances.
246 : */
247 9 : fixed hw1 = halfSize1.X;
248 9 : fixed hh1 = halfSize1.Y;
249 :
250 : return std::max(std::max(
251 18 : MaxDistanceToSquare(relativePos + u1.Multiply(hw1) + v1.Multiply(hh1), u2, v2, halfSize2, true),
252 18 : MaxDistanceToSquare(relativePos + u1.Multiply(hw1) - v1.Multiply(hh1), u2, v2, halfSize2, true)),
253 18 : std::max(MaxDistanceToSquare(relativePos - u1.Multiply(hw1) + v1.Multiply(hh1), u2, v2, halfSize2, true),
254 36 : MaxDistanceToSquare(relativePos - u1.Multiply(hw1) - v1.Multiply(hh1), u2, v2, halfSize2, true)));
255 : }
256 :
257 29 : bool TestRaySquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
258 : {
259 : /*
260 : * We only consider collisions to be when the ray goes from outside to inside the shape (and possibly out again).
261 : * Various cases to consider:
262 : * 'a' inside, 'b' inside -> no collision
263 : * 'a' inside, 'b' outside -> no collision
264 : * 'a' outside, 'b' inside -> collision
265 : * 'a' outside, 'b' outside -> depends; use separating axis theorem:
266 : * if the ray's bounding box is outside the square -> no collision
267 : * if the whole square is on the same side of the ray -> no collision
268 : * otherwise -> collision
269 : * (Points on the edge are considered 'inside'.)
270 : */
271 :
272 29 : fixed hw = halfSize.X;
273 29 : fixed hh = halfSize.Y;
274 :
275 29 : fixed au = a.Dot(u);
276 29 : fixed av = a.Dot(v);
277 :
278 29 : if (-hw <= au && au <= hw && -hh <= av && av <= hh)
279 2 : return false; // a is inside
280 :
281 27 : fixed bu = b.Dot(u);
282 27 : fixed bv = b.Dot(v);
283 :
284 27 : if (-hw <= bu && bu <= hw && -hh <= bv && bv <= hh) // TODO: isn't this subsumed by the next checks?
285 2 : return true; // a is outside, b is inside
286 :
287 25 : if ((au < -hw && bu < -hw) || (au > hw && bu > hw) || (av < -hh && bv < -hh) || (av > hh && bv > hh))
288 18 : return false; // ab is entirely above/below/side the square
289 :
290 7 : CFixedVector2D abp = (b - a).Perpendicular();
291 7 : fixed s0 = abp.Dot((u.Multiply(hw) + v.Multiply(hh)) - a);
292 7 : fixed s1 = abp.Dot((u.Multiply(hw) - v.Multiply(hh)) - a);
293 7 : fixed s2 = abp.Dot((-u.Multiply(hw) - v.Multiply(hh)) - a);
294 7 : fixed s3 = abp.Dot((-u.Multiply(hw) + v.Multiply(hh)) - a);
295 7 : if (s0.IsZero() || s1.IsZero() || s2.IsZero() || s3.IsZero())
296 7 : return true; // ray intersects the corner
297 :
298 0 : bool sign = (s0 < fixed::Zero());
299 0 : if ((s1 < fixed::Zero()) != sign || (s2 < fixed::Zero()) != sign || (s3 < fixed::Zero()) != sign)
300 0 : return true; // ray cuts through the square
301 :
302 0 : return false;
303 : }
304 :
305 : // Exactly like TestRaySquare with u=(1,0), v=(0,1)
306 0 : bool TestRayAASquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& halfSize)
307 : {
308 0 : fixed hw = halfSize.X;
309 0 : fixed hh = halfSize.Y;
310 :
311 0 : if (-hw <= a.X && a.X <= hw && -hh <= a.Y && a.Y <= hh)
312 0 : return false; // a is inside
313 :
314 0 : if (-hw <= b.X && b.X <= hw && -hh <= b.Y && b.Y <= hh) // TODO: isn't this subsumed by the next checks?
315 0 : return true; // a is outside, b is inside
316 :
317 0 : 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))
318 0 : return false; // ab is entirely above/below/side the square
319 :
320 0 : CFixedVector2D abp = (b - a).Perpendicular();
321 0 : fixed s0 = abp.Dot(CFixedVector2D(hw, hh) - a);
322 0 : fixed s1 = abp.Dot(CFixedVector2D(hw, -hh) - a);
323 0 : fixed s2 = abp.Dot(CFixedVector2D(-hw, -hh) - a);
324 0 : fixed s3 = abp.Dot(CFixedVector2D(-hw, hh) - a);
325 0 : if (s0.IsZero() || s1.IsZero() || s2.IsZero() || s3.IsZero())
326 0 : return true; // ray intersects the corner
327 :
328 0 : bool sign = (s0 < fixed::Zero());
329 0 : if ((s1 < fixed::Zero()) != sign || (s2 < fixed::Zero()) != sign || (s3 < fixed::Zero()) != sign)
330 0 : return true; // ray cuts through the square
331 :
332 0 : return false;
333 : }
334 :
335 : /**
336 : * Separating axis test; returns true if the square defined by u/v/halfSize at the origin
337 : * is not entirely on the clockwise side of a line in direction 'axis' passing through 'a'
338 : */
339 37 : static bool SquareSAT(const CFixedVector2D& a, const CFixedVector2D& axis, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
340 : {
341 37 : fixed hw = halfSize.X;
342 37 : fixed hh = halfSize.Y;
343 :
344 37 : CFixedVector2D p = axis.Perpendicular();
345 37 : if (p.RelativeOrientation(u.Multiply(hw) + v.Multiply(hh) - a) <= 0)
346 25 : return true;
347 12 : if (p.RelativeOrientation(u.Multiply(hw) - v.Multiply(hh) - a) <= 0)
348 4 : return true;
349 8 : if (p.RelativeOrientation(-u.Multiply(hw) - v.Multiply(hh) - a) <= 0)
350 5 : return true;
351 3 : if (p.RelativeOrientation(-u.Multiply(hw) + v.Multiply(hh) - a) <= 0)
352 0 : return true;
353 :
354 3 : return false;
355 : }
356 :
357 7 : bool TestSquareSquare(
358 : const CFixedVector2D& c0, const CFixedVector2D& u0, const CFixedVector2D& v0, const CFixedVector2D& halfSize0,
359 : const CFixedVector2D& c1, const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1)
360 : {
361 : // TODO: need to test this carefully
362 :
363 7 : CFixedVector2D corner0a = c0 + u0.Multiply(halfSize0.X) + v0.Multiply(halfSize0.Y);
364 7 : CFixedVector2D corner0b = c0 - u0.Multiply(halfSize0.X) - v0.Multiply(halfSize0.Y);
365 7 : CFixedVector2D corner1a = c1 + u1.Multiply(halfSize1.X) + v1.Multiply(halfSize1.Y);
366 7 : CFixedVector2D corner1b = c1 - u1.Multiply(halfSize1.X) - v1.Multiply(halfSize1.Y);
367 :
368 : // Do a SAT test for each square vs each edge of the other square
369 7 : if (!SquareSAT(corner0a - c1, -u0, u1, v1, halfSize1))
370 2 : return false;
371 5 : if (!SquareSAT(corner0a - c1, v0, u1, v1, halfSize1))
372 0 : return false;
373 5 : if (!SquareSAT(corner0b - c1, u0, u1, v1, halfSize1))
374 1 : return false;
375 4 : if (!SquareSAT(corner0b - c1, -v0, u1, v1, halfSize1))
376 0 : return false;
377 4 : if (!SquareSAT(corner1a - c0, -u1, u0, v0, halfSize0))
378 0 : return false;
379 4 : if (!SquareSAT(corner1a - c0, v1, u0, v0, halfSize0))
380 0 : return false;
381 4 : if (!SquareSAT(corner1b - c0, u1, u0, v0, halfSize0))
382 0 : return false;
383 4 : if (!SquareSAT(corner1b - c0, -v1, u0, v0, halfSize0))
384 0 : return false;
385 :
386 4 : return true;
387 : }
388 :
389 0 : int GetPerimeterDistance(int x_max, int y_max, int x, int y)
390 : {
391 0 : if (x_max <= 0 || y_max <= 0)
392 0 : return 0;
393 :
394 0 : int quarter = x_max + y_max;
395 0 : if (x == x_max && y >= 0)
396 0 : return y;
397 0 : if (y == y_max)
398 0 : return quarter - x;
399 0 : if (x == -x_max)
400 0 : return 2 * quarter - y;
401 0 : if (y == -y_max)
402 0 : return 3 * quarter + x;
403 0 : if (x == x_max)
404 0 : return 4 * quarter + y;
405 0 : return 0;
406 : }
407 :
408 0 : std::pair<int, int> GetPerimeterCoordinates(int x_max, int y_max, int k)
409 : {
410 0 : if (x_max <= 0 || y_max <= 0)
411 0 : return std::pair<int, int>(0, 0);
412 :
413 0 : int quarter = x_max + y_max;
414 0 : k %= 4 * quarter;
415 0 : if (k < 0)
416 0 : k += 4 * quarter;
417 :
418 0 : if (k < y_max)
419 0 : return std::pair<int, int>(x_max, k);
420 0 : if (k < quarter + x_max)
421 0 : return std::pair<int, int>(quarter - k, y_max);
422 0 : if (k < 2 * quarter + y_max)
423 0 : return std::pair<int, int>(-x_max, 2 * quarter - k);
424 0 : if (k < 3 * quarter + x_max)
425 0 : return std::pair<int, int>(k - 3 * quarter, -y_max);
426 0 : return std::pair<int, int>(x_max, k - 4 * quarter);
427 : }
428 :
429 0 : fixed DistanceToSegment(
430 : const CFixedVector2D& point, const CFixedVector2D& a, const CFixedVector2D& b)
431 : {
432 : // First we need to figure out from which part of the segment we should
433 : // calculate distance.
434 : // We split 2D space in three spaces:
435 : // | |
436 : // 1 | 2 | 3
437 : // A--------------------------------B
438 : // Here we need | Between A and B we need to | Here we need
439 : // distance to A | calculate distance to the line | distance to B
440 : //
441 0 : const CFixedVector2D dir = b - a;
442 : // We project the point, point A, and point B upon the direction of the
443 : // segment to figure out in which space the point is.
444 0 : const fixed pointDot = dir.Dot(point);
445 0 : const fixed aDot = dir.Dot(a);
446 : // The point is lying in space #1.
447 0 : if (pointDot <= aDot)
448 0 : return (point - a).Length();
449 0 : const fixed bDot = dir.Dot(b);
450 : // The point is lying in space #3.
451 0 : if (pointDot >= bDot)
452 0 : return (point - b).Length();
453 : // The point is lying in space #2.
454 0 : CFixedVector2D normal = dir.Perpendicular();
455 0 : normal.Normalize();
456 0 : return (normal.Dot(a) - normal.Dot(point)).Absolute();
457 : }
458 :
459 : } // namespace Geometry
|
