remove RSA's md4.c, replace by DP's
[xonotic/netradiant.git] / libs / math / aabb.h
1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20 */
21
22 #if !defined(INCLUDED_MATH_AABB_H)
23 #define INCLUDED_MATH_AABB_H
24
25 /// \file
26 /// \brief Axis-aligned bounding-box data types and related operations.
27
28 #include "math/matrix.h"
29 #include "math/plane.h"
30
31 class AABB
32 {
33 public:
34   Vector3 origin, extents;
35
36   AABB() : origin(0, 0, 0), extents(-1,-1,-1)
37   {
38   }
39   AABB(const Vector3& origin_, const Vector3& extents_) :
40     origin(origin_), extents(extents_)
41   {
42   }
43 };
44
45 const float c_aabb_max = FLT_MAX;
46
47 inline bool extents_valid(float f)
48 {
49   return f >= 0.0f && f <= c_aabb_max;
50 }
51
52 inline bool origin_valid(float f)
53 {
54   return f >= -c_aabb_max && f <= c_aabb_max;
55 }
56
57 inline bool aabb_valid(const AABB& aabb)
58 {
59   return origin_valid(aabb.origin[0])
60     && origin_valid(aabb.origin[1])
61     && origin_valid(aabb.origin[2])
62     && extents_valid(aabb.extents[0])
63     && extents_valid(aabb.extents[1])
64     && extents_valid(aabb.extents[2]);
65 }
66
67 inline AABB aabb_for_minmax(const Vector3& min, const Vector3& max)
68 {
69   AABB aabb;
70   aabb.origin = vector3_mid(min, max);
71   aabb.extents = vector3_subtracted(max, aabb.origin);
72   return aabb;
73 }
74
75 template<typename Index>
76 class AABBExtend
77 {
78 public:
79   static void apply(AABB& aabb, const Vector3& point)
80   {
81     float displacement = point[Index::VALUE] - aabb.origin[Index::VALUE];
82     float half_difference = static_cast<float>(0.5 * (fabs(displacement) - aabb.extents[Index::VALUE]));
83     if(half_difference > 0.0f)
84     {
85       aabb.origin[Index::VALUE] += (displacement >= 0.0f) ? half_difference : -half_difference;
86       aabb.extents[Index::VALUE] += half_difference;
87     }
88   }
89   static void apply(AABB& aabb, const AABB& other)
90   {
91     float displacement = other.origin[Index::VALUE] - aabb.origin[Index::VALUE];
92     float difference = other.extents[Index::VALUE] - aabb.extents[Index::VALUE];
93     if(fabs(displacement) > fabs(difference))
94     {
95       float half_difference = static_cast<float>(0.5 * (fabs(displacement) + difference));
96       if(half_difference > 0.0f)
97       {
98         aabb.origin[Index::VALUE] += (displacement >= 0.0f) ? half_difference : -half_difference;
99         aabb.extents[Index::VALUE] += half_difference;
100       }
101     }
102     else if(difference > 0.0f)
103     {
104       aabb.origin[Index::VALUE] = other.origin[Index::VALUE];
105       aabb.extents[Index::VALUE] = other.extents[Index::VALUE];
106     }
107   }
108 };
109
110 inline void aabb_extend_by_point(AABB& aabb, const Vector3& point)
111 {
112   AABBExtend< IntegralConstant<0> >::apply(aabb, point);
113   AABBExtend< IntegralConstant<1> >::apply(aabb, point);
114   AABBExtend< IntegralConstant<2> >::apply(aabb, point);
115 }
116
117 inline void aabb_extend_by_point_safe(AABB& aabb, const Vector3& point)
118 {
119   if(aabb_valid(aabb))
120   {
121     aabb_extend_by_point(aabb, point);
122   }
123   else
124   {
125     aabb.origin = point;
126     aabb.extents = Vector3(0, 0, 0);
127   }
128 }
129
130 class AABBExtendByPoint
131 {
132   AABB& m_aabb;
133 public:
134   AABBExtendByPoint(AABB& aabb) : m_aabb(aabb)
135   {
136   }
137   void operator()(const Vector3& point) const
138   {
139     aabb_extend_by_point_safe(m_aabb, point);
140   }
141 };
142   
143 inline void aabb_extend_by_aabb(AABB& aabb, const AABB& other)
144 {
145   AABBExtend< IntegralConstant<0> >::apply(aabb, other);
146   AABBExtend< IntegralConstant<1> >::apply(aabb, other);
147   AABBExtend< IntegralConstant<2> >::apply(aabb, other);
148 }
149
150 inline void aabb_extend_by_aabb_safe(AABB& aabb, const AABB& other)
151 {
152   if(aabb_valid(aabb) && aabb_valid(other))
153   {
154     aabb_extend_by_aabb(aabb, other);
155   }
156   else if(aabb_valid(other))
157   {
158     aabb = other;
159   }
160 }
161
162 inline void aabb_extend_by_vec3(AABB& aabb, const Vector3& extension)
163 {
164   vector3_add(aabb.extents, extension);
165 }
166
167
168
169
170 template<typename Index>
171 inline bool aabb_intersects_point_dimension(const AABB& aabb, const Vector3& point)
172 {
173   return fabs(point[Index::VALUE] - aabb.origin[Index::VALUE]) < aabb.extents[Index::VALUE];
174 }
175
176 inline bool aabb_intersects_point(const AABB& aabb, const Vector3& point)
177 {
178   return aabb_intersects_point_dimension< IntegralConstant<0> >(aabb, point)
179     && aabb_intersects_point_dimension< IntegralConstant<1> >(aabb, point)
180     && aabb_intersects_point_dimension< IntegralConstant<2> >(aabb, point);
181 }
182
183 template<typename Index>
184 inline bool aabb_intersects_aabb_dimension(const AABB& aabb, const AABB& other)
185 {
186   return fabs(other.origin[Index::VALUE] - aabb.origin[Index::VALUE]) < (aabb.extents[Index::VALUE] + other.extents[Index::VALUE]);
187 }
188
189 inline bool aabb_intersects_aabb(const AABB& aabb, const AABB& other)
190 {
191   return aabb_intersects_aabb_dimension< IntegralConstant<0> >(aabb, other)
192     && aabb_intersects_aabb_dimension< IntegralConstant<1> >(aabb, other)
193     && aabb_intersects_aabb_dimension< IntegralConstant<2> >(aabb, other);
194 }
195
196 inline unsigned int aabb_classify_plane(const AABB& aabb, const Plane3& plane)
197 {
198   double distance_origin = vector3_dot(plane.normal(), aabb.origin) + plane.dist();
199   
200   if(fabs(distance_origin) < (fabs(plane.a * aabb.extents[0])
201     + fabs(plane.b * aabb.extents[1])
202     + fabs(plane.c * aabb.extents[2])))
203   {
204     return 1; // partially inside
205   }
206   else if (distance_origin < 0)
207   {
208     return 2; // totally inside
209   }
210   return 0; // totally outside
211 }
212
213 inline unsigned int aabb_oriented_classify_plane(const AABB& aabb, const Matrix4& transform, const Plane3& plane)
214 {
215   double distance_origin = vector3_dot(plane.normal(), aabb.origin) + plane.dist();
216
217   if(fabs(distance_origin) < (fabs(aabb.extents[0] * vector3_dot(plane.normal(), vector4_to_vector3(transform.x())))
218     + fabs(aabb.extents[1] * vector3_dot(plane.normal(), vector4_to_vector3(transform.y())))
219     + fabs(aabb.extents[2] * vector3_dot(plane.normal(), vector4_to_vector3(transform.z())))))
220   {
221     return 1; // partially inside
222   }
223   else if (distance_origin < 0)
224   {
225     return 2; // totally inside
226   }
227   return 0; // totally outside
228 }
229
230 inline void aabb_corners(const AABB& aabb, Vector3 corners[8])
231 {
232   Vector3 min(vector3_subtracted(aabb.origin, aabb.extents));
233   Vector3 max(vector3_added(aabb.origin, aabb.extents));
234   corners[0] = Vector3(min[0], max[1], max[2]);
235   corners[1] = Vector3(max[0], max[1], max[2]);
236   corners[2] = Vector3(max[0], min[1], max[2]);
237   corners[3] = Vector3(min[0], min[1], max[2]);
238   corners[4] = Vector3(min[0], max[1], min[2]);
239   corners[5] = Vector3(max[0], max[1], min[2]);
240   corners[6] = Vector3(max[0], min[1], min[2]);
241   corners[7] = Vector3(min[0], min[1], min[2]);
242 }
243
244 inline void aabb_corners_oriented(const AABB& aabb, const Matrix4& rotation, Vector3 corners[8])
245 {
246   Vector3 x = vector4_to_vector3(rotation.x()) * aabb.extents.x();
247   Vector3 y = vector4_to_vector3(rotation.y()) * aabb.extents.y();
248   Vector3 z = vector4_to_vector3(rotation.z()) * aabb.extents.z();
249
250   corners[0] = aabb.origin + -x +  y +  z;
251   corners[1] = aabb.origin +  x +  y +  z;
252   corners[2] = aabb.origin +  x + -y +  z;
253   corners[3] = aabb.origin + -x + -y +  z;
254   corners[4] = aabb.origin + -x +  y + -z;
255   corners[5] = aabb.origin +  x +  y + -z;
256   corners[6] = aabb.origin +  x + -y + -z;
257   corners[7] = aabb.origin + -x + -y + -z;
258 }
259
260 inline void aabb_planes(const AABB& aabb, Plane3 planes[6])
261 {
262   planes[0] = Plane3(g_vector3_axes[0], aabb.origin[0] + aabb.extents[0]);
263   planes[1] = Plane3(vector3_negated(g_vector3_axes[0]), -(aabb.origin[0] - aabb.extents[0]));
264   planes[2] = Plane3(g_vector3_axes[1], aabb.origin[1] + aabb.extents[1]);
265   planes[3] = Plane3(vector3_negated(g_vector3_axes[1]), -(aabb.origin[1] - aabb.extents[1]));
266   planes[4] = Plane3(g_vector3_axes[2], aabb.origin[2] + aabb.extents[2]);
267   planes[5] = Plane3(vector3_negated(g_vector3_axes[2]), -(aabb.origin[2] - aabb.extents[2]));
268 }
269
270 inline void aabb_planes_oriented(const AABB& aabb, const Matrix4& rotation, Plane3 planes[6])
271 {
272   double x = vector3_dot(vector4_to_vector3(rotation.x()), aabb.origin);
273   double y = vector3_dot(vector4_to_vector3(rotation.y()), aabb.origin);
274   double z = vector3_dot(vector4_to_vector3(rotation.z()), aabb.origin);
275
276   planes[0] = Plane3(vector4_to_vector3(rotation.x()), x + aabb.extents[0]);
277   planes[1] = Plane3(-vector4_to_vector3(rotation.x()), -(x - aabb.extents[0]));
278   planes[2] = Plane3(vector4_to_vector3(rotation.y()), y + aabb.extents[1]);
279   planes[3] = Plane3(-vector4_to_vector3(rotation.y()), -(y - aabb.extents[1]));
280   planes[4] = Plane3(vector4_to_vector3(rotation.z()), z + aabb.extents[2]);
281   planes[5] = Plane3(-vector4_to_vector3(rotation.z()), -(z - aabb.extents[2]));
282 }
283
284 const Vector3 aabb_normals[6] = {
285   Vector3( 1, 0, 0 ),
286   Vector3( 0, 1, 0 ),
287   Vector3( 0, 0, 1 ),
288   Vector3(-1, 0, 0 ),
289   Vector3( 0,-1, 0 ),
290   Vector3( 0, 0,-1 ),
291 };
292
293 const float aabb_texcoord_topleft[2] = { 0, 0 };
294 const float aabb_texcoord_topright[2] = { 1, 0 };
295 const float aabb_texcoord_botleft[2] = { 0, 1 };
296 const float aabb_texcoord_botright[2] = { 1, 1 };
297
298
299 inline AABB aabb_for_oriented_aabb(const AABB& aabb, const Matrix4& transform)
300 {
301   return AABB(
302     matrix4_transformed_point(transform, aabb.origin),
303     Vector3(
304       static_cast<float>(fabs(transform[0]  * aabb.extents[0])
305                           + fabs(transform[4]  * aabb.extents[1])
306                           + fabs(transform[8]  * aabb.extents[2])),
307       static_cast<float>(fabs(transform[1]  * aabb.extents[0])
308                           + fabs(transform[5]  * aabb.extents[1])
309                           + fabs(transform[9]  * aabb.extents[2])),
310       static_cast<float>(fabs(transform[2]  * aabb.extents[0])
311                           + fabs(transform[6]  * aabb.extents[1])
312                           + fabs(transform[10] * aabb.extents[2]))
313     )
314   );
315 }
316
317 inline AABB aabb_for_oriented_aabb_safe(const AABB& aabb, const Matrix4& transform)
318 {
319   if(aabb_valid(aabb))
320   {
321     return aabb_for_oriented_aabb(aabb, transform);
322   }
323   return aabb;
324 }
325
326 inline AABB aabb_infinite()
327 {
328   return AABB(Vector3(0, 0, 0), Vector3(c_aabb_max, c_aabb_max, c_aabb_max));
329 }
330
331 #endif