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