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 class AABBExtendByPoint
 116 {
 117 AABB& m_aabb;
 118 public:
 119 AABBExtendByPoint( AABB& aabb ) : m_aabb( aabb ){
 120 }
 121 void operator()( const Vector3& point ) const {
 122         aabb_extend_by_point_safe( m_aabb, point );
 123 }
 124 };
 125
 126 inline void aabb_extend_by_aabb( AABB& aabb, const AABB& other ){
 127         AABBExtend< IntegralConstant<0> >::apply( aabb, other );
 128         AABBExtend< IntegralConstant<1> >::apply( aabb, other );
 129         AABBExtend< IntegralConstant<2> >::apply( aabb, other );
 130 }
 131
 132 inline void aabb_extend_by_aabb_safe( AABB& aabb, const AABB& other ){
 133         if ( aabb_valid( aabb ) && aabb_valid( other ) ) {
 134                 aabb_extend_by_aabb( aabb, other );
 135         }
 136         else if ( aabb_valid( other ) ) {
 137                 aabb = other;
 138         }
 139 }
 140
 141 inline void aabb_extend_by_vec3( AABB& aabb, const Vector3& extension ){
 142         vector3_add( aabb.extents, extension );
 143 }
 144
 145
 146
 147
 148 template<typename Index>
 149 inline bool aabb_intersects_point_dimension( const AABB& aabb, const Vector3& point ){
 150         return fabs( point[Index::VALUE] - aabb.origin[Index::VALUE] ) < aabb.extents[Index::VALUE];
 151 }
 152
 153 inline bool aabb_intersects_point( const AABB& aabb, const Vector3& point ){
 154         return aabb_intersects_point_dimension< IntegralConstant<0> >( aabb, point )
 155                    && aabb_intersects_point_dimension< IntegralConstant<1> >( aabb, point )
 156                    && aabb_intersects_point_dimension< IntegralConstant<2> >( aabb, point );
 157 }
 158
 159 template<typename Index>
 160 inline bool aabb_intersects_aabb_dimension( const AABB& aabb, const AABB& other ){
 161         return fabs( other.origin[Index::VALUE] - aabb.origin[Index::VALUE] ) < ( aabb.extents[Index::VALUE] + other.extents[Index::VALUE] );
 162 }
 163
 164 inline bool aabb_intersects_aabb( const AABB& aabb, const AABB& other ){
 165         return aabb_intersects_aabb_dimension< IntegralConstant<0> >( aabb, other )
 166                    && aabb_intersects_aabb_dimension< IntegralConstant<1> >( aabb, other )
 167                    && aabb_intersects_aabb_dimension< IntegralConstant<2> >( aabb, other );
 168 }
 169
 170 inline unsigned int aabb_classify_plane( const AABB& aabb, const Plane3& plane ){
 171         double distance_origin = vector3_dot( plane.normal(), aabb.origin ) + plane.dist();
 172
 173         if ( fabs( distance_origin ) < ( fabs( plane.a * aabb.extents[0] )
 174                                                                          + fabs( plane.b * aabb.extents[1] )
 175                                                                          + fabs( plane.c * aabb.extents[2] ) ) ) {
 176                 return 1; // partially inside
 177         }
 178         else if ( distance_origin < 0 ) {
 179                 return 2; // totally inside
 180         }
 181         return 0; // totally outside
 182 }
 183
 184 inline unsigned int aabb_oriented_classify_plane( const AABB& aabb, const Matrix4& transform, const Plane3& plane ){
 185         double distance_origin = vector3_dot( plane.normal(), aabb.origin ) + plane.dist();
 186
 187         if ( fabs( distance_origin ) < ( fabs( aabb.extents[0] * vector3_dot( plane.normal(), vector4_to_vector3( transform.x() ) ) )
 188                                                                          + fabs( aabb.extents[1] * vector3_dot( plane.normal(), vector4_to_vector3( transform.y() ) ) )
 189                                                                          + fabs( aabb.extents[2] * vector3_dot( plane.normal(), vector4_to_vector3( transform.z() ) ) ) ) ) {
 190                 return 1; // partially inside
 191         }
 192         else if ( distance_origin < 0 ) {
 193                 return 2; // totally inside
 194         }
 195         return 0; // totally outside
 196 }
 197
 198 inline void aabb_corners( const AABB& aabb, Vector3 corners[8] ){
 199         Vector3 min( vector3_subtracted( aabb.origin, aabb.extents ) );
 200         Vector3 max( vector3_added( aabb.origin, aabb.extents ) );
 201         corners[0] = Vector3( min[0], max[1], max[2] );
 202         corners[1] = Vector3( max[0], max[1], max[2] );
 203         corners[2] = Vector3( max[0], min[1], max[2] );
 204         corners[3] = Vector3( min[0], min[1], max[2] );
 205         corners[4] = Vector3( min[0], max[1], min[2] );
 206         corners[5] = Vector3( max[0], max[1], min[2] );
 207         corners[6] = Vector3( max[0], min[1], min[2] );
 208         corners[7] = Vector3( min[0], min[1], min[2] );
 209 }
 210
 211 inline void aabb_corners_oriented( const AABB& aabb, const Matrix4& rotation, Vector3 corners[8] ){
 212         Vector3 x = vector4_to_vector3( rotation.x() ) * aabb.extents.x();
 213         Vector3 y = vector4_to_vector3( rotation.y() ) * aabb.extents.y();
 214         Vector3 z = vector4_to_vector3( rotation.z() ) * aabb.extents.z();
 215
 216         corners[0] = aabb.origin + -x +  y +  z;
 217         corners[1] = aabb.origin +  x +  y +  z;
 218         corners[2] = aabb.origin +  x + -y +  z;
 219         corners[3] = aabb.origin + -x + -y +  z;
 220         corners[4] = aabb.origin + -x +  y + -z;
 221         corners[5] = aabb.origin +  x +  y + -z;
 222         corners[6] = aabb.origin +  x + -y + -z;
 223         corners[7] = aabb.origin + -x + -y + -z;
 224 }
 225
 226 inline void aabb_planes( const AABB& aabb, Plane3 planes[6] ){
 227         planes[0] = Plane3( g_vector3_axes[0], aabb.origin[0] + aabb.extents[0] );
 228         planes[1] = Plane3( vector3_negated( g_vector3_axes[0] ), -( aabb.origin[0] - aabb.extents[0] ) );
 229         planes[2] = Plane3( g_vector3_axes[1], aabb.origin[1] + aabb.extents[1] );
 230         planes[3] = Plane3( vector3_negated( g_vector3_axes[1] ), -( aabb.origin[1] - aabb.extents[1] ) );
 231         planes[4] = Plane3( g_vector3_axes[2], aabb.origin[2] + aabb.extents[2] );
 232         planes[5] = Plane3( vector3_negated( g_vector3_axes[2] ), -( aabb.origin[2] - aabb.extents[2] ) );
 233 }
 234
 235 inline void aabb_planes_oriented( const AABB& aabb, const Matrix4& rotation, Plane3 planes[6] ){
 236         double x = vector3_dot( vector4_to_vector3( rotation.x() ), aabb.origin );
 237         double y = vector3_dot( vector4_to_vector3( rotation.y() ), aabb.origin );
 238         double z = vector3_dot( vector4_to_vector3( rotation.z() ), aabb.origin );
 239
 240         planes[0] = Plane3( vector4_to_vector3( rotation.x() ), x + aabb.extents[0] );
 241         planes[1] = Plane3( -vector4_to_vector3( rotation.x() ), -( x - aabb.extents[0] ) );
 242         planes[2] = Plane3( vector4_to_vector3( rotation.y() ), y + aabb.extents[1] );
 243         planes[3] = Plane3( -vector4_to_vector3( rotation.y() ), -( y - aabb.extents[1] ) );
 244         planes[4] = Plane3( vector4_to_vector3( rotation.z() ), z + aabb.extents[2] );
 245         planes[5] = Plane3( -vector4_to_vector3( rotation.z() ), -( z - aabb.extents[2] ) );
 246 }
 247
 248 const Vector3 aabb_normals[6] = {
 249         Vector3( 1, 0, 0 ),
 250         Vector3( 0, 1, 0 ),
 251         Vector3( 0, 0, 1 ),
 252         Vector3( -1, 0, 0 ),
 253         Vector3( 0,-1, 0 ),
 254         Vector3( 0, 0,-1 ),
 255 };
 256
 257 const float aabb_texcoord_topleft[2] = { 0, 0 };
 258 const float aabb_texcoord_topright[2] = { 1, 0 };
 259 const float aabb_texcoord_botleft[2] = { 0, 1 };
 260 const float aabb_texcoord_botright[2] = { 1, 1 };
 261
 262
 263 inline AABB aabb_for_oriented_aabb( const AABB& aabb, const Matrix4& transform ){
 264         return AABB(
 265                            matrix4_transformed_point( transform, aabb.origin ),
 266                            Vector3(
 267                                    static_cast<float>( fabs( transform[0]  * aabb.extents[0] )
 268                                                                            + fabs( transform[4]  * aabb.extents[1] )
 269                                                                            + fabs( transform[8]  * aabb.extents[2] ) ),
 270                                    static_cast<float>( fabs( transform[1]  * aabb.extents[0] )
 271                                                                            + fabs( transform[5]  * aabb.extents[1] )
 272                                                                            + fabs( transform[9]  * aabb.extents[2] ) ),
 273                                    static_cast<float>( fabs( transform[2]  * aabb.extents[0] )
 274                                                                            + fabs( transform[6]  * aabb.extents[1] )
 275                                                                            + fabs( transform[10] * aabb.extents[2] ) )
 276                                    )
 277                            );
 278 }
 279
 280 inline AABB aabb_for_oriented_aabb_safe( const AABB& aabb, const Matrix4& transform ){
 281         if ( aabb_valid( aabb ) ) {
 282                 return aabb_for_oriented_aabb( aabb, transform );
 283         }
 284         return aabb;
 285 }
 286
 287 inline AABB aabb_infinite(){
 288         return AABB( Vector3( 0, 0, 0 ), Vector3( c_aabb_max, c_aabb_max, c_aabb_max ) );
 289 }
 290
 291 #endif