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 AABB( const Vector3& origin_, const Vector3& extents_ ) :
  39         origin( origin_ ), extents( extents_ ){
  40 }
  41 };
  42
  43 const float c_aabb_max = FLT_MAX;
  44
  45 inline bool extents_valid( float f ){
  46         return f >= 0.0f && f <= c_aabb_max;
  47 }
  48
  49 inline bool origin_valid( float f ){
  50         return f >= -c_aabb_max && f <= c_aabb_max;
  51 }
  52
  53 inline bool aabb_valid( const AABB& aabb ){
  54         return origin_valid( aabb.origin[0] )
  55                    && origin_valid( aabb.origin[1] )
  56                    && origin_valid( aabb.origin[2] )
  57                    && extents_valid( aabb.extents[0] )
  58                    && extents_valid( aabb.extents[1] )
  59                    && extents_valid( aabb.extents[2] );
  60 }
  61
  62 inline AABB aabb_for_minmax( const Vector3& min, const Vector3& max ){
  63         AABB aabb;
  64         aabb.origin = vector3_mid( min, max );
  65         aabb.extents = vector3_subtracted( max, aabb.origin );
  66         return aabb;
  67 }
  68
  69 template<typename Index>
  70 class AABBExtend
  71 {
  72 public:
  73 static void apply( AABB& aabb, const Vector3& point ){
  74         float displacement = point[Index::VALUE] - aabb.origin[Index::VALUE];
  75         float half_difference = static_cast<float>( 0.5 * ( fabs( displacement ) - aabb.extents[Index::VALUE] ) );
  76         if ( half_difference > 0.0f ) {
  77                 aabb.origin[Index::VALUE] += ( displacement >= 0.0f ) ? half_difference : -half_difference;
  78                 aabb.extents[Index::VALUE] += half_difference;
  79         }
  80 }
  81 static void apply( AABB& aabb, const AABB& other ){
  82         float displacement = other.origin[Index::VALUE] - aabb.origin[Index::VALUE];
  83         float difference = other.extents[Index::VALUE] - aabb.extents[Index::VALUE];
  84         if ( fabs( displacement ) > fabs( difference ) ) {
  85                 float half_difference = static_cast<float>( 0.5 * ( fabs( displacement ) + difference ) );
  86                 if ( half_difference > 0.0f ) {
  87                         aabb.origin[Index::VALUE] += ( displacement >= 0.0f ) ? half_difference : -half_difference;
  88                         aabb.extents[Index::VALUE] += half_difference;
  89                 }
  90         }
  91         else if ( difference > 0.0f ) {
  92                 aabb.origin[Index::VALUE] = other.origin[Index::VALUE];
  93                 aabb.extents[Index::VALUE] = other.extents[Index::VALUE];
  94         }
  95 }
  96 };
  97
  98 inline void aabb_extend_by_point( AABB& aabb, const Vector3& point ){
  99         AABBExtend< IntegralConstant<0> >::apply( aabb, point );
 100         AABBExtend< IntegralConstant<1> >::apply( aabb, point );
 101         AABBExtend< IntegralConstant<2> >::apply( aabb, point );
 102 }
 103
 104 inline void aabb_extend_by_point_safe( AABB& aabb, const Vector3& point ){
 105         if ( aabb_valid( aabb ) ) {
 106                 aabb_extend_by_point( aabb, point );
 107         }
 108         else
 109         {
 110                 aabb.origin = point;
 111                 aabb.extents = Vector3( 0, 0, 0 );
 112         }
 113 }
 114
 115 inline void aabb_extend_by_aabb( AABB& aabb, const AABB& other ){
 116         AABBExtend< IntegralConstant<0> >::apply( aabb, other );
 117         AABBExtend< IntegralConstant<1> >::apply( aabb, other );
 118         AABBExtend< IntegralConstant<2> >::apply( aabb, other );
 119 }
 120
 121 inline void aabb_extend_by_aabb_safe( AABB& aabb, const AABB& other ){
 122         if ( aabb_valid( aabb ) && aabb_valid( other ) ) {
 123                 aabb_extend_by_aabb( aabb, other );
 124         }
 125         else if ( aabb_valid( other ) ) {
 126                 aabb = other;
 127         }
 128 }
 129
 130 inline void aabb_extend_by_vec3( AABB& aabb, const Vector3& extension ){
 131         vector3_add( aabb.extents, extension );
 132 }
 133
 134
 135
 136
 137 template<typename Index>
 138 inline bool aabb_intersects_point_dimension( const AABB& aabb, const Vector3& point ){
 139         return fabs( point[Index::VALUE] - aabb.origin[Index::VALUE] ) < aabb.extents[Index::VALUE];
 140 }
 141
 142 inline bool aabb_intersects_point( const AABB& aabb, const Vector3& point ){
 143         return aabb_intersects_point_dimension< IntegralConstant<0> >( aabb, point )
 144                    && aabb_intersects_point_dimension< IntegralConstant<1> >( aabb, point )
 145                    && aabb_intersects_point_dimension< IntegralConstant<2> >( aabb, point );
 146 }
 147
 148 template<typename Index>
 149 inline bool aabb_intersects_aabb_dimension( const AABB& aabb, const AABB& other ){
 150         return fabs( other.origin[Index::VALUE] - aabb.origin[Index::VALUE] ) < ( aabb.extents[Index::VALUE] + other.extents[Index::VALUE] );
 151 }
 152
 153 inline bool aabb_intersects_aabb( const AABB& aabb, const AABB& other ){
 154         return aabb_intersects_aabb_dimension< IntegralConstant<0> >( aabb, other )
 155                    && aabb_intersects_aabb_dimension< IntegralConstant<1> >( aabb, other )
 156                    && aabb_intersects_aabb_dimension< IntegralConstant<2> >( aabb, other );
 157 }
 158
 159 inline unsigned int aabb_classify_plane( const AABB& aabb, const Plane3& plane ){
 160         double distance_origin = vector3_dot( plane.normal(), aabb.origin ) + plane.dist();
 161
 162         if ( fabs( distance_origin ) < ( fabs( plane.a * aabb.extents[0] )
 163                                                                          + fabs( plane.b * aabb.extents[1] )
 164                                                                          + fabs( plane.c * aabb.extents[2] ) ) ) {
 165                 return 1; // partially inside
 166         }
 167         else if ( distance_origin < 0 ) {
 168                 return 2; // totally inside
 169         }
 170         return 0; // totally outside
 171 }
 172
 173 inline unsigned int aabb_oriented_classify_plane( const AABB& aabb, const Matrix4& transform, const Plane3& plane ){
 174         double distance_origin = vector3_dot( plane.normal(), aabb.origin ) + plane.dist();
 175
 176         if ( fabs( distance_origin ) < ( fabs( aabb.extents[0] * vector3_dot( plane.normal(), vector4_to_vector3( transform.x() ) ) )
 177                                                                          + fabs( aabb.extents[1] * vector3_dot( plane.normal(), vector4_to_vector3( transform.y() ) ) )
 178                                                                          + fabs( aabb.extents[2] * vector3_dot( plane.normal(), vector4_to_vector3( transform.z() ) ) ) ) ) {
 179                 return 1; // partially inside
 180         }
 181         else if ( distance_origin < 0 ) {
 182                 return 2; // totally inside
 183         }
 184         return 0; // totally outside
 185 }
 186
 187 inline void aabb_corners( const AABB& aabb, Vector3 corners[8] ){
 188         Vector3 min( vector3_subtracted( aabb.origin, aabb.extents ) );
 189         Vector3 max( vector3_added( aabb.origin, aabb.extents ) );
 190         corners[0] = Vector3( min[0], max[1], max[2] );
 191         corners[1] = Vector3( max[0], max[1], max[2] );
 192         corners[2] = Vector3( max[0], min[1], max[2] );
 193         corners[3] = Vector3( min[0], min[1], max[2] );
 194         corners[4] = Vector3( min[0], max[1], min[2] );
 195         corners[5] = Vector3( max[0], max[1], min[2] );
 196         corners[6] = Vector3( max[0], min[1], min[2] );
 197         corners[7] = Vector3( min[0], min[1], min[2] );
 198 }
 199
 200 inline void aabb_corners_oriented( const AABB& aabb, const Matrix4& rotation, Vector3 corners[8] ){
 201         Vector3 x = vector4_to_vector3( rotation.x() ) * aabb.extents.x();
 202         Vector3 y = vector4_to_vector3( rotation.y() ) * aabb.extents.y();
 203         Vector3 z = vector4_to_vector3( rotation.z() ) * aabb.extents.z();
 204
 205         corners[0] = aabb.origin + -x +  y +  z;
 206         corners[1] = aabb.origin +  x +  y +  z;
 207         corners[2] = aabb.origin +  x + -y +  z;
 208         corners[3] = aabb.origin + -x + -y +  z;
 209         corners[4] = aabb.origin + -x +  y + -z;
 210         corners[5] = aabb.origin +  x +  y + -z;
 211         corners[6] = aabb.origin +  x + -y + -z;
 212         corners[7] = aabb.origin + -x + -y + -z;
 213 }
 214
 215 inline void aabb_planes( const AABB& aabb, Plane3 planes[6] ){
 216         planes[0] = Plane3( g_vector3_axes[0], aabb.origin[0] + aabb.extents[0] );
 217         planes[1] = Plane3( vector3_negated( g_vector3_axes[0] ), -( aabb.origin[0] - aabb.extents[0] ) );
 218         planes[2] = Plane3( g_vector3_axes[1], aabb.origin[1] + aabb.extents[1] );
 219         planes[3] = Plane3( vector3_negated( g_vector3_axes[1] ), -( aabb.origin[1] - aabb.extents[1] ) );
 220         planes[4] = Plane3( g_vector3_axes[2], aabb.origin[2] + aabb.extents[2] );
 221         planes[5] = Plane3( vector3_negated( g_vector3_axes[2] ), -( aabb.origin[2] - aabb.extents[2] ) );
 222 }
 223
 224 inline void aabb_planes_oriented( const AABB& aabb, const Matrix4& rotation, Plane3 planes[6] ){
 225         double x = vector3_dot( vector4_to_vector3( rotation.x() ), aabb.origin );
 226         double y = vector3_dot( vector4_to_vector3( rotation.y() ), aabb.origin );
 227         double z = vector3_dot( vector4_to_vector3( rotation.z() ), aabb.origin );
 228
 229         planes[0] = Plane3( vector4_to_vector3( rotation.x() ), x + aabb.extents[0] );
 230         planes[1] = Plane3( -vector4_to_vector3( rotation.x() ), -( x - aabb.extents[0] ) );
 231         planes[2] = Plane3( vector4_to_vector3( rotation.y() ), y + aabb.extents[1] );
 232         planes[3] = Plane3( -vector4_to_vector3( rotation.y() ), -( y - aabb.extents[1] ) );
 233         planes[4] = Plane3( vector4_to_vector3( rotation.z() ), z + aabb.extents[2] );
 234         planes[5] = Plane3( -vector4_to_vector3( rotation.z() ), -( z - aabb.extents[2] ) );
 235 }
 236
 237 const Vector3 aabb_normals[6] = {
 238         Vector3( 1, 0, 0 ),
 239         Vector3( 0, 1, 0 ),
 240         Vector3( 0, 0, 1 ),
 241         Vector3( -1, 0, 0 ),
 242         Vector3( 0,-1, 0 ),
 243         Vector3( 0, 0,-1 ),
 244 };
 245
 246 const float aabb_texcoord_topleft[2] = { 0, 0 };
 247 const float aabb_texcoord_topright[2] = { 1, 0 };
 248 const float aabb_texcoord_botleft[2] = { 0, 1 };
 249 const float aabb_texcoord_botright[2] = { 1, 1 };
 250
 251
 252 inline AABB aabb_for_oriented_aabb( const AABB& aabb, const Matrix4& transform ){
 253         return AABB(
 254                            matrix4_transformed_point( transform, aabb.origin ),
 255                            Vector3(
 256                                    static_cast<float>( fabs( transform[0]  * aabb.extents[0] )
 257                                                                            + fabs( transform[4]  * aabb.extents[1] )
 258                                                                            + fabs( transform[8]  * aabb.extents[2] ) ),
 259                                    static_cast<float>( fabs( transform[1]  * aabb.extents[0] )
 260                                                                            + fabs( transform[5]  * aabb.extents[1] )
 261                                                                            + fabs( transform[9]  * aabb.extents[2] ) ),
 262                                    static_cast<float>( fabs( transform[2]  * aabb.extents[0] )
 263                                                                            + fabs( transform[6]  * aabb.extents[1] )
 264                                                                            + fabs( transform[10] * aabb.extents[2] ) )
 265                                    )
 266                            );
 267 }
 268
 269 inline AABB aabb_for_oriented_aabb_safe( const AABB& aabb, const Matrix4& transform ){
 270         if ( aabb_valid( aabb ) ) {
 271                 return aabb_for_oriented_aabb( aabb, transform );
 272         }
 273         return aabb;
 274 }
 275
 276 inline AABB aabb_infinite(){
 277         return AABB( Vector3( 0, 0, 0 ), Vector3( c_aabb_max, c_aabb_max, c_aabb_max ) );
 278 }
 279
 280 #endif