1/**************************************************************************/
2/* bvh_abb.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef BVH_ABB_H
32#define BVH_ABB_H
33
34// special optimized version of axis aligned bounding box
35template <class BOUNDS = AABB, class POINT = Vector3>
36struct BVH_ABB {
37 struct ConvexHull {
38 // convex hulls (optional)
39 const Plane *planes;
40 int num_planes;
41 const Vector3 *points;
42 int num_points;
43 };
44
45 struct Segment {
46 POINT from;
47 POINT to;
48 };
49
50 enum IntersectResult {
51 IR_MISS = 0,
52 IR_PARTIAL,
53 IR_FULL,
54 };
55
56 // we store mins with a negative value in order to test them with SIMD
57 POINT min;
58 POINT neg_max;
59
60 bool operator==(const BVH_ABB &o) const { return (min == o.min) && (neg_max == o.neg_max); }
61 bool operator!=(const BVH_ABB &o) const { return (*this == o) == false; }
62
63 void set(const POINT &_min, const POINT &_max) {
64 min = _min;
65 neg_max = -_max;
66 }
67
68 // to and from standard AABB
69 void from(const BOUNDS &p_aabb) {
70 min = p_aabb.position;
71 neg_max = -(p_aabb.position + p_aabb.size);
72 }
73
74 void to(BOUNDS &r_aabb) const {
75 r_aabb.position = min;
76 r_aabb.size = calculate_size();
77 }
78
79 void merge(const BVH_ABB &p_o) {
80 for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) {
81 neg_max[axis] = MIN(neg_max[axis], p_o.neg_max[axis]);
82 min[axis] = MIN(min[axis], p_o.min[axis]);
83 }
84 }
85
86 POINT calculate_size() const {
87 return -neg_max - min;
88 }
89
90 POINT calculate_center() const {
91 return POINT((calculate_size() * 0.5) + min);
92 }
93
94 real_t get_proximity_to(const BVH_ABB &p_b) const {
95 const POINT d = (min - neg_max) - (p_b.min - p_b.neg_max);
96 real_t proximity = 0.0;
97 for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) {
98 proximity += Math::abs(d[axis]);
99 }
100 return proximity;
101 }
102
103 int select_by_proximity(const BVH_ABB &p_a, const BVH_ABB &p_b) const {
104 return (get_proximity_to(p_a) < get_proximity_to(p_b) ? 0 : 1);
105 }
106
107 uint32_t find_cutting_planes(const typename BVH_ABB::ConvexHull &p_hull, uint32_t *p_plane_ids) const {
108 uint32_t count = 0;
109
110 for (int n = 0; n < p_hull.num_planes; n++) {
111 const Plane &p = p_hull.planes[n];
112 if (intersects_plane(p)) {
113 p_plane_ids[count++] = n;
114 }
115 }
116
117 return count;
118 }
119
120 bool intersects_plane(const Plane &p_p) const {
121 Vector3 size = calculate_size();
122 Vector3 half_extents = size * 0.5;
123 Vector3 ofs = min + half_extents;
124
125 // forward side of plane?
126 Vector3 point_offset(
127 (p_p.normal.x < 0) ? -half_extents.x : half_extents.x,
128 (p_p.normal.y < 0) ? -half_extents.y : half_extents.y,
129 (p_p.normal.z < 0) ? -half_extents.z : half_extents.z);
130 Vector3 point = point_offset + ofs;
131
132 if (!p_p.is_point_over(point)) {
133 return false;
134 }
135
136 point = -point_offset + ofs;
137 if (p_p.is_point_over(point)) {
138 return false;
139 }
140
141 return true;
142 }
143
144 bool intersects_convex_optimized(const ConvexHull &p_hull, const uint32_t *p_plane_ids, uint32_t p_num_planes) const {
145 Vector3 size = calculate_size();
146 Vector3 half_extents = size * 0.5;
147 Vector3 ofs = min + half_extents;
148
149 for (unsigned int i = 0; i < p_num_planes; i++) {
150 const Plane &p = p_hull.planes[p_plane_ids[i]];
151 Vector3 point(
152 (p.normal.x > 0) ? -half_extents.x : half_extents.x,
153 (p.normal.y > 0) ? -half_extents.y : half_extents.y,
154 (p.normal.z > 0) ? -half_extents.z : half_extents.z);
155 point += ofs;
156 if (p.is_point_over(point)) {
157 return false;
158 }
159 }
160
161 return true;
162 }
163
164 bool intersects_convex_partial(const ConvexHull &p_hull) const {
165 BOUNDS bb;
166 to(bb);
167 return bb.intersects_convex_shape(p_hull.planes, p_hull.num_planes, p_hull.points, p_hull.num_points);
168 }
169
170 IntersectResult intersects_convex(const ConvexHull &p_hull) const {
171 if (intersects_convex_partial(p_hull)) {
172 // fully within? very important for tree checks
173 if (is_within_convex(p_hull)) {
174 return IR_FULL;
175 }
176
177 return IR_PARTIAL;
178 }
179
180 return IR_MISS;
181 }
182
183 bool is_within_convex(const ConvexHull &p_hull) const {
184 // use half extents routine
185 BOUNDS bb;
186 to(bb);
187 return bb.inside_convex_shape(p_hull.planes, p_hull.num_planes);
188 }
189
190 bool is_point_within_hull(const ConvexHull &p_hull, const Vector3 &p_pt) const {
191 for (int n = 0; n < p_hull.num_planes; n++) {
192 if (p_hull.planes[n].distance_to(p_pt) > 0.0f) {
193 return false;
194 }
195 }
196 return true;
197 }
198
199 bool intersects_segment(const Segment &p_s) const {
200 BOUNDS bb;
201 to(bb);
202 return bb.intersects_segment(p_s.from, p_s.to);
203 }
204
205 bool intersects_point(const POINT &p_pt) const {
206 if (_any_lessthan(-p_pt, neg_max)) {
207 return false;
208 }
209 if (_any_lessthan(p_pt, min)) {
210 return false;
211 }
212 return true;
213 }
214
215 // Very hot in profiling, make sure optimized
216 bool intersects(const BVH_ABB &p_o) const {
217 if (_any_morethan(p_o.min, -neg_max)) {
218 return false;
219 }
220 if (_any_morethan(min, -p_o.neg_max)) {
221 return false;
222 }
223 return true;
224 }
225
226 // for pre-swizzled tester (this object)
227 bool intersects_swizzled(const BVH_ABB &p_o) const {
228 if (_any_lessthan(min, p_o.min)) {
229 return false;
230 }
231 if (_any_lessthan(neg_max, p_o.neg_max)) {
232 return false;
233 }
234 return true;
235 }
236
237 bool is_other_within(const BVH_ABB &p_o) const {
238 if (_any_lessthan(p_o.neg_max, neg_max)) {
239 return false;
240 }
241 if (_any_lessthan(p_o.min, min)) {
242 return false;
243 }
244 return true;
245 }
246
247 void grow(const POINT &p_change) {
248 neg_max -= p_change;
249 min -= p_change;
250 }
251
252 void expand(real_t p_change) {
253 POINT change;
254 for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) {
255 change[axis] = p_change;
256 }
257 grow(change);
258 }
259
260 // Actually surface area metric.
261 float get_area() const {
262 POINT d = calculate_size();
263 return 2.0f * (d.x * d.y + d.y * d.z + d.z * d.x);
264 }
265
266 void set_to_max_opposite_extents() {
267 for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) {
268 neg_max[axis] = FLT_MAX;
269 }
270 min = neg_max;
271 }
272
273 bool _any_morethan(const POINT &p_a, const POINT &p_b) const {
274 for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) {
275 if (p_a[axis] > p_b[axis]) {
276 return true;
277 }
278 }
279 return false;
280 }
281
282 bool _any_lessthan(const POINT &p_a, const POINT &p_b) const {
283 for (int axis = 0; axis < POINT::AXIS_COUNT; ++axis) {
284 if (p_a[axis] < p_b[axis]) {
285 return true;
286 }
287 }
288 return false;
289 }
290};
291
292#endif // BVH_ABB_H
293