1// SuperTux
2// Copyright (C) 2006 Matthias Braun <matze@braunis.de>
3//
4// This program 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 3 of the License, or
7// (at your option) any later version.
8//
9// This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
16
17#include "collision/collision.hpp"
18
19#include <algorithm>
20
21#include "math/aatriangle.hpp"
22#include "math/rectf.hpp"
23
24namespace collision {
25
26bool intersects(const Rectf& r1, const Rectf& r2)
27{
28 if (r1.get_right() < r2.get_left() || r1.get_left() > r2.get_right())
29 return false;
30 if (r1.get_bottom() < r2.get_top() || r1.get_top() > r2.get_bottom())
31 return false;
32
33 return true;
34}
35
36//---------------------------------------------------------------------------
37
38namespace {
39inline void makePlane(const Vector& p1, const Vector& p2, Vector& n, float& c)
40{
41 n = Vector(p2.y - p1.y, p1.x - p2.x);
42 c = -(p2 * n);
43 float nval = n.norm();
44 n /= nval;
45 c /= nval;
46}
47
48}
49
50bool rectangle_aatriangle(Constraints* constraints, const Rectf& rect,
51 const AATriangle& triangle, const Vector& addl_ground_movement)
52{
53 if (!intersects(rect, triangle.bbox))
54 return false;
55
56 Vector normal;
57 float c = 0.0;
58 Vector p1;
59 Rectf area;
60 switch (triangle.dir & AATriangle::DEFORM_MASK) {
61 case 0:
62 area.set_p1(triangle.bbox.p1());
63 area.set_p2(triangle.bbox.p2());
64 break;
65 case AATriangle::DEFORM_BOTTOM:
66 area.set_p1(Vector(triangle.bbox.get_left(), triangle.bbox.get_top() + triangle.bbox.get_height()/2));
67 area.set_p2(triangle.bbox.p2());
68 break;
69 case AATriangle::DEFORM_TOP:
70 area.set_p1(triangle.bbox.p1());
71 area.set_p2(Vector(triangle.bbox.get_right(), triangle.bbox.get_top() + triangle.bbox.get_height()/2));
72 break;
73 case AATriangle::DEFORM_LEFT:
74 area.set_p1(triangle.bbox.p1());
75 area.set_p2(Vector(triangle.bbox.get_left() + triangle.bbox.get_width()/2, triangle.bbox.get_bottom()));
76 break;
77 case AATriangle::DEFORM_RIGHT:
78 area.set_p1(Vector(triangle.bbox.get_left() + triangle.bbox.get_width()/2, triangle.bbox.get_top()));
79 area.set_p2(triangle.bbox.p2());
80 break;
81 default:
82 assert(false);
83 }
84
85 switch (triangle.dir & AATriangle::DIRECTION_MASK) {
86 case AATriangle::SOUTHWEST:
87 p1 = Vector(rect.get_left(), rect.get_bottom());
88 makePlane(area.p1(), area.p2(), normal, c);
89 break;
90 case AATriangle::NORTHEAST:
91 p1 = Vector(rect.get_right(), rect.get_top());
92 makePlane(area.p2(), area.p1(), normal, c);
93 break;
94 case AATriangle::SOUTHEAST:
95 p1 = rect.p2();
96 makePlane(Vector(area.get_left(), area.get_bottom()),
97 Vector(area.get_right(), area.get_top()), normal, c);
98 break;
99 case AATriangle::NORTHWEST:
100 p1 = rect.p1();
101 makePlane(Vector(area.get_right(), area.get_top()),
102 Vector(area.get_left(), area.get_bottom()), normal, c);
103 break;
104 default:
105 assert(false);
106 }
107
108 float n_p1 = -(normal * p1);
109 float depth = n_p1 - c;
110 if (depth < 0)
111 return false;
112
113#if 0
114 std::cout << "R: " << rect << " Tri: " << triangle << "\n";
115 std::cout << "Norm: " << normal << " Depth: " << depth << "\n";
116#endif
117
118 Vector outvec = normal * (depth + 0.2f);
119
120 const float RDELTA = 3;
121 if (p1.x < area.get_left() - RDELTA || p1.x > area.get_right() + RDELTA
122 || p1.y < area.get_top() - RDELTA || p1.y > area.get_bottom() + RDELTA) {
123 set_rectangle_rectangle_constraints(constraints, rect, area);
124 } else {
125 if (outvec.x < 0) {
126 constraints->constrain_right(rect.get_right() + outvec.x, addl_ground_movement.x);
127 constraints->hit.right = true;
128 } else {
129 constraints->constrain_left(rect.get_left() + outvec.x, addl_ground_movement.x);
130 constraints->hit.left = true;
131 }
132
133 if (outvec.y < 0) {
134 constraints->constrain_bottom(rect.get_bottom() + outvec.y, addl_ground_movement.y);
135 constraints->hit.bottom = true;
136 constraints->ground_movement += addl_ground_movement;
137 } else {
138 constraints->constrain_top(rect.get_top() + outvec.y, addl_ground_movement.y);
139 constraints->hit.top = true;
140 }
141 constraints->hit.slope_normal = normal;
142 }
143
144 return true;
145}
146
147void set_rectangle_rectangle_constraints(Constraints* constraints,
148 const Rectf& r1, const Rectf& r2, const Vector& addl_ground_movement)
149{
150 float itop = r1.get_bottom() - r2.get_top();
151 float ibottom = r2.get_bottom() - r1.get_top();
152 float ileft = r1.get_right() - r2.get_left();
153 float iright = r2.get_right() - r1.get_left();
154
155 float vert_penetration = std::min(itop, ibottom);
156 float horiz_penetration = std::min(ileft, iright);
157 if (vert_penetration < horiz_penetration) {
158 if (itop < ibottom) {
159 constraints->constrain_bottom(r2.get_top(), addl_ground_movement.y);
160 constraints->hit.bottom = true;
161 constraints->ground_movement += addl_ground_movement;
162 } else {
163 constraints->constrain_top(r2.get_bottom(), addl_ground_movement.y);
164 constraints->hit.top = true;
165 }
166 } else {
167 if (ileft < iright) {
168 constraints->constrain_right(r2.get_left(), addl_ground_movement.x);
169 constraints->hit.right = true;
170 } else {
171 constraints->constrain_left(r2.get_right(), addl_ground_movement.x);
172 constraints->hit.left = true;
173 }
174 }
175}
176
177bool line_intersects_line(const Vector& line1_start, const Vector& line1_end, const Vector& line2_start, const Vector& line2_end)
178{
179 // Adapted from Striker, (C) 1999 Joris van der Hoeven, GPL
180
181 float a1 = line1_start.x, b1 = line1_start.y, a2 = line1_end.x, b2 = line1_end.y;
182 float c1 = line2_start.x, d1 = line2_start.y, c2 = line2_end.x, d2 = line2_end.y;
183
184 float num = (b2-b1)*(c2-c1) - (a2-a1)*(d2-d1);
185 float den1 = (d2-b2)*(c1-c2) + (a2-c2)*(d1-d2);
186 float den2 = (d2-b2)*(a1-a2) + (a2-c2)*(b1-b2);
187
188 // normalize to positive numerator
189 if (num < 0) {
190 num = -num;
191 den1 = -den1;
192 den2 = -den2;
193 }
194
195 // numerator is zero -> Check for parallel or coinciding lines
196 if (num == 0) {
197 if ((b1-b2)*(c1-a2) != (a1-a2)*(d1-b2)) return false;
198 if (a1 == a2) {
199 std::swap(a1, b1);
200 std::swap(a2, b2);
201 std::swap(c1, d1);
202 std::swap(c2, d2);
203 }
204 if (a1 > a2) std::swap(a1, a2);
205 if (c1 > c2) std::swap(c1, c2);
206 return ((a1 <= c2) && (a2 >= c1));
207 }
208
209 // Standard check
210 return (den1>=0) && (den1<=num) && (den2>=0) && (den2<=num);
211
212}
213
214bool intersects_line(const Rectf& r, const Vector& line_start, const Vector& line_end)
215{
216 Vector p1 = r.p1();
217 Vector p2 = Vector(r.get_right(), r.get_top());
218 Vector p3 = r.p2();
219 Vector p4 = Vector(r.get_left(), r.get_bottom());
220 if (line_intersects_line(p1, p2, line_start, line_end)) return true;
221 if (line_intersects_line(p2, p3, line_start, line_end)) return true;
222 if (line_intersects_line(p3, p4, line_start, line_end)) return true;
223 if (line_intersects_line(p4, p1, line_start, line_end)) return true;
224 return false;
225}
226
227}
228
229/* EOF */
230