1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
|
/*************************************************************************/
/* aabb.h */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
/* http://www.godotengine.org */
/*************************************************************************/
/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
/* */
/* Permission is hereby granted, free of charge, to any person obtaining */
/* a copy of this software and associated documentation files (the */
/* "Software"), to deal in the Software without restriction, including */
/* without limitation the rights to use, copy, modify, merge, publish, */
/* distribute, sublicense, and/or sell copies of the Software, and to */
/* permit persons to whom the Software is furnished to do so, subject to */
/* the following conditions: */
/* */
/* The above copyright notice and this permission notice shall be */
/* included in all copies or substantial portions of the Software. */
/* */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
#ifndef AABB_H
#define AABB_H
#include "vector3.h"
#include "plane.h"
/**
* AABB / AABB (Axis Aligned Bounding Box)
* This is implemented by a point (pos) and the box size
*/
class AABB {
public:
Vector3 pos;
Vector3 size;
float get_area() const; /// get area
_FORCE_INLINE_ bool has_no_area() const {
return (size.x<=CMP_EPSILON || size.y<=CMP_EPSILON || size.z<=CMP_EPSILON);
}
_FORCE_INLINE_ bool has_no_surface() const {
return (size.x<=CMP_EPSILON && size.y<=CMP_EPSILON && size.z<=CMP_EPSILON);
}
const Vector3& get_pos() const { return pos; }
void set_pos(const Vector3& p_pos) { pos=p_pos; }
const Vector3& get_size() const { return size; }
void set_size(const Vector3& p_size) { size=p_size; }
bool operator==(const AABB& p_rval) const;
bool operator!=(const AABB& p_rval) const;
_FORCE_INLINE_ bool intersects(const AABB& p_aabb) const; /// Both AABBs overlap
_FORCE_INLINE_ bool encloses(const AABB & p_aabb) const; /// p_aabb is completely inside this
AABB merge(const AABB& p_with) const;
void merge_with(const AABB& p_aabb); ///merge with another AABB
AABB intersection(const AABB& p_aabb) const; ///get box where two intersect, empty if no intersection occurs
bool intersects_segment(const Vector3& p_from, const Vector3& p_to,Vector3* r_clip=NULL,Vector3* r_normal=NULL) const;
bool intersects_ray(const Vector3& p_from, const Vector3& p_dir,Vector3* r_clip=NULL,Vector3* r_normal=NULL) const;
_FORCE_INLINE_ bool intersects_convex_shape(const Plane *p_plane, int p_plane_count) const;
bool intersects_plane(const Plane &p_plane) const;
_FORCE_INLINE_ bool has_point(const Vector3& p_point) const;
_FORCE_INLINE_ Vector3 get_support(const Vector3& p_normal) const;
Vector3 get_longest_axis() const;
int get_longest_axis_index() const;
_FORCE_INLINE_ real_t get_longest_axis_size() const;
Vector3 get_shortest_axis() const;
int get_shortest_axis_index() const;
_FORCE_INLINE_ real_t get_shortest_axis_size() const;
AABB grow(real_t p_by) const;
void grow_by(real_t p_amount);
void get_edge(int p_edge,Vector3& r_from,Vector3& r_to) const;
_FORCE_INLINE_ Vector3 get_endpoint(int p_point) const;
AABB expand(const Vector3& p_vector) const;
_FORCE_INLINE_ void project_range_in_plane(const Plane& p_plane,float &r_min,float& r_max) const;
_FORCE_INLINE_ void expand_to(const Vector3& p_vector); /** expand to contain a point if necesary */
operator String() const;
_FORCE_INLINE_ AABB() {}
inline AABB(const Vector3 &p_pos,const Vector3& p_size) { pos=p_pos; size=p_size; }
};
inline bool AABB::intersects(const AABB& p_aabb) const {
if ( pos.x > (p_aabb.pos.x + p_aabb.size.x) )
return false;
if ( (pos.x+size.x) < p_aabb.pos.x )
return false;
if ( pos.y > (p_aabb.pos.y + p_aabb.size.y) )
return false;
if ( (pos.y+size.y) < p_aabb.pos.y )
return false;
if ( pos.z > (p_aabb.pos.z + p_aabb.size.z) )
return false;
if ( (pos.z+size.z) < p_aabb.pos.z )
return false;
return true;
}
inline bool AABB::encloses(const AABB & p_aabb) const {
Vector3 src_min=pos;
Vector3 src_max=pos+size;
Vector3 dst_min=p_aabb.pos;
Vector3 dst_max=p_aabb.pos+p_aabb.size;
return (
(src_min.x <= dst_min.x) &&
(src_max.x > dst_max.x) &&
(src_min.y <= dst_min.y) &&
(src_max.y > dst_max.y) &&
(src_min.z <= dst_min.z) &&
(src_max.z > dst_max.z) );
}
Vector3 AABB::get_support(const Vector3& p_normal) const {
Vector3 half_extents = size * 0.5;
Vector3 ofs = pos + half_extents;
return Vector3(
(p_normal.x>0) ? -half_extents.x : half_extents.x,
(p_normal.y>0) ? -half_extents.y : half_extents.y,
(p_normal.z>0) ? -half_extents.z : half_extents.z
)+ofs;
}
Vector3 AABB::get_endpoint(int p_point) const {
switch(p_point) {
case 0: return Vector3( pos.x , pos.y , pos.z );
case 1: return Vector3( pos.x , pos.y , pos.z+size.z );
case 2: return Vector3( pos.x , pos.y+size.y , pos.z );
case 3: return Vector3( pos.x , pos.y+size.y , pos.z+size.z );
case 4: return Vector3( pos.x+size.x , pos.y , pos.z );
case 5: return Vector3( pos.x+size.x , pos.y , pos.z+size.z );
case 6: return Vector3( pos.x+size.x , pos.y+size.y , pos.z );
case 7: return Vector3( pos.x+size.x , pos.y+size.y , pos.z+size.z );
};
ERR_FAIL_V(Vector3());
}
bool AABB::intersects_convex_shape(const Plane *p_planes, int p_plane_count) const {
#if 1
Vector3 half_extents = size * 0.5;
Vector3 ofs = pos + half_extents;
for(int i=0;i<p_plane_count;i++) {
const Plane &p=p_planes[i];
Vector3 point(
(p.normal.x>0) ? -half_extents.x : half_extents.x,
(p.normal.y>0) ? -half_extents.y : half_extents.y,
(p.normal.z>0) ? -half_extents.z : half_extents.z
);
point+=ofs;
if (p.is_point_over(point))
return false;
}
return true;
#else
//cache all points to check against!
// #warning should be easy to optimize, just use the same as when taking the support and use only that point
Vector3 points[8] = {
Vector3( pos.x , pos.y , pos.z ),
Vector3( pos.x , pos.y , pos.z+size.z ),
Vector3( pos.x , pos.y+size.y , pos.z ),
Vector3( pos.x , pos.y+size.y , pos.z+size.z ),
Vector3( pos.x+size.x , pos.y , pos.z ),
Vector3( pos.x+size.x , pos.y , pos.z+size.z ),
Vector3( pos.x+size.x , pos.y+size.y , pos.z ),
Vector3( pos.x+size.x , pos.y+size.y , pos.z+size.z ),
};
for (int i=0;i<p_plane_count;i++) { //for each plane
const Plane & plane=p_planes[i];
bool all_points_over=true;
//test if it has all points over!
for (int j=0;j<8;j++) {
if (!plane.is_point_over( points[j] )) {
all_points_over=false;
break;
}
}
if (all_points_over) {
return false;
}
}
return true;
#endif
}
bool AABB::has_point(const Vector3& p_point) const {
if (p_point.x<pos.x)
return false;
if (p_point.y<pos.y)
return false;
if (p_point.z<pos.z)
return false;
if (p_point.x>pos.x+size.x)
return false;
if (p_point.y>pos.y+size.y)
return false;
if (p_point.z>pos.z+size.z)
return false;
return true;
}
inline void AABB::expand_to(const Vector3& p_vector) {
Vector3 begin=pos;
Vector3 end=pos+size;
if (p_vector.x<begin.x)
begin.x=p_vector.x;
if (p_vector.y<begin.y)
begin.y=p_vector.y;
if (p_vector.z<begin.z)
begin.z=p_vector.z;
if (p_vector.x>end.x)
end.x=p_vector.x;
if (p_vector.y>end.y)
end.y=p_vector.y;
if (p_vector.z>end.z)
end.z=p_vector.z;
pos=begin;
size=end-begin;
}
void AABB::project_range_in_plane(const Plane& p_plane,float &r_min,float& r_max) const {
Vector3 half_extents( size.x * 0.5, size.y * 0.5, size.z * 0.5 );
Vector3 center( pos.x + half_extents.x, pos.y + half_extents.y, pos.z + half_extents.z );
float length = p_plane.normal.abs().dot(half_extents);
float distance = p_plane.distance_to( center );
r_min = distance - length;
r_max = distance + length;
}
inline real_t AABB::get_longest_axis_size() const {
real_t max_size=size.x;
if (size.y > max_size ) {
max_size=size.y;
}
if (size.z > max_size ) {
max_size=size.z;
}
return max_size;
}
inline real_t AABB::get_shortest_axis_size() const {
real_t max_size=size.x;
if (size.y < max_size ) {
max_size=size.y;
}
if (size.z < max_size ) {
max_size=size.z;
}
return max_size;
}
typedef AABB Rect3;
#endif // AABB_H
|