2 Copyright (C) 2001-2006, William Joseph.
5 This file is part of GtkRadiant.
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.
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.
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
22 #if !defined( INCLUDED_MATH_AABB_H )
23 #define INCLUDED_MATH_AABB_H
26 /// \brief Axis-aligned bounding-box data types and related operations.
28 #include "math/matrix.h"
29 #include "math/plane.h"
34 Vector3 origin, extents;
36 AABB() : origin( 0, 0, 0 ), extents( -1,-1,-1 ){
38 AABB( const Vector3& origin_, const Vector3& extents_ ) :
39 origin( origin_ ), extents( extents_ ){
43 const float c_aabb_max = FLT_MAX;
45 inline bool extents_valid( float f ){
46 return f >= 0.0f && f <= c_aabb_max;
49 inline bool origin_valid( float f ){
50 return f >= -c_aabb_max && f <= c_aabb_max;
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] );
62 inline AABB aabb_for_minmax( const Vector3& min, const Vector3& max ){
64 aabb.origin = vector3_mid( min, max );
65 aabb.extents = vector3_subtracted( max, aabb.origin );
69 template<typename Index>
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;
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;
91 else if ( difference > 0.0f ) {
92 aabb.origin[Index::VALUE] = other.origin[Index::VALUE];
93 aabb.extents[Index::VALUE] = other.extents[Index::VALUE];
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 );
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 );
111 aabb.extents = Vector3( 0, 0, 0 );
115 class AABBExtendByPoint
119 AABBExtendByPoint( AABB& aabb ) : m_aabb( aabb ){
121 void operator()( const Vector3& point ) const {
122 aabb_extend_by_point_safe( m_aabb, point );
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 );
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 );
136 else if ( aabb_valid( other ) ) {
141 inline void aabb_extend_by_vec3( AABB& aabb, const Vector3& extension ){
142 vector3_add( aabb.extents, extension );
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];
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 );
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] );
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 );
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();
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
178 else if ( distance_origin < 0 ) {
179 return 2; // totally inside
181 return 0; // totally outside
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();
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
192 else if ( distance_origin < 0 ) {
193 return 2; // totally inside
195 return 0; // totally outside
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] );
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();
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;
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] ) );
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 );
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] ) );
248 const Vector3 aabb_normals[6] = {
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 };
263 inline AABB aabb_for_oriented_aabb( const AABB& aabb, const Matrix4& transform ){
265 matrix4_transformed_point( transform, aabb.origin ),
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] ) )
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 );
287 inline AABB aabb_infinite(){
288 return AABB( Vector3( 0, 0, 0 ), Vector3( c_aabb_max, c_aabb_max, c_aabb_max ) );