libs/mathlib.h

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   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 #ifndef __MATHLIB__
  23 #define __MATHLIB__
  24
  25 // mathlib.h
  26 #include <math.h>
  27 #include <float.h>
  28
  29 #include "bytebool.h"
  30
  31 #ifdef __cplusplus
  32 extern "C"
  33 {
  34 #endif
  35
  36 typedef float vec_t;
  37 typedef vec_t vec3_t[3];
  38 typedef vec_t vec5_t[5];
  39 typedef vec_t vec4_t[4];
  40
  41 // Smallest positive value for vec_t such that 1.0 + VEC_SMALLEST_EPSILON_AROUND_ONE != 1.0.
  42 // In the case of 32 bit floats (which is almost certainly the case), it's 0.00000011921.
  43 // Don't forget that your epsilons should depend on the possible range of values,
  44 // because for example adding VEC_SMALLEST_EPSILON_AROUND_ONE to 1024.0 will have no effect.
  45 #define VEC_SMALLEST_EPSILON_AROUND_ONE FLT_EPSILON
  46
  47 #define SIDE_FRONT      0
  48 #define SIDE_ON         2
  49 #define SIDE_BACK       1
  50 #define SIDE_CROSS      -2
  51
  52 // plane types are used to speed some tests
  53 // 0-2 are axial planes
  54 #define PLANE_X         0
  55 #define PLANE_Y         1
  56 #define PLANE_Z         2
  57 #define PLANE_NON_AXIAL 3
  58
  59 #define Q_PI    3.14159265358979323846f
  60
  61 extern vec3_t vec3_origin;
  62
  63 #define EQUAL_EPSILON   0.001
  64
  65 #ifndef VEC_MAX
  66 #define VEC_MAX 3.402823466e+38F
  67 #endif
  68
  69 qboolean VectorCompare( vec3_t v1, vec3_t v2 );
  70
  71 #define DotProduct( x,y ) ( ( x )[0] * ( y )[0] + ( x )[1] * ( y )[1] + ( x )[2] * ( y )[2] )
  72 #define VectorSubtract( a,b,c ) ( ( c )[0] = ( a )[0] - ( b )[0],( c )[1] = ( a )[1] - ( b )[1],( c )[2] = ( a )[2] - ( b )[2] )
  73 #define VectorAdd( a,b,c ) ( ( c )[0] = ( a )[0] + ( b )[0],( c )[1] = ( a )[1] + ( b )[1],( c )[2] = ( a )[2] + ( b )[2] )
  74 #define VectorIncrement( a,b ) ( ( b )[0] += ( a )[0],( b )[1] += ( a )[1],( b )[2] += ( a )[2] )
  75 #define VectorCopy( a,b ) ( ( b )[0] = ( a )[0],( b )[1] = ( a )[1],( b )[2] = ( a )[2] )
  76 #define VectorSet( v, a, b, c ) ( ( v )[0] = ( a ),( v )[1] = ( b ),( v )[2] = ( c ) )
  77 #define VectorScale( a,b,c ) ( ( c )[0] = ( b ) * ( a )[0],( c )[1] = ( b ) * ( a )[1],( c )[2] = ( b ) * ( a )[2] )
  78 #define VectorMid( a,b,c ) ( ( c )[0] = ( ( a )[0] + ( b )[0] ) * 0.5f,( c )[1] = ( ( a )[1] + ( b )[1] ) * 0.5f,( c )[2] = ( ( a )[2] + ( b )[2] ) * 0.5f )
  79 #define VectorNegative( a,b ) ( ( b )[0] = -( a )[0],( b )[1] = -( a )[1],( b )[2] = -( a )[2] )
  80 #define CrossProduct( a,b,c ) ( ( c )[0] = ( a )[1] * ( b )[2] - ( a )[2] * ( b )[1],( c )[1] = ( a )[2] * ( b )[0] - ( a )[0] * ( b )[2],( c )[2] = ( a )[0] * ( b )[1] - ( a )[1] * ( b )[0] )
  81 #define VectorClear( x ) ( ( x )[0] = ( x )[1] = ( x )[2] = 0 )
  82
  83 #define Q_rint( in ) ( (vec_t)floor( in + 0.5 ) )
  84
  85 qboolean VectorIsOnAxis( vec3_t v );
  86 qboolean VectorIsOnAxialPlane( vec3_t v );
  87
  88 vec_t VectorLength( vec3_t v );
  89
  90 void VectorMA( const vec3_t va, vec_t scale, const vec3_t vb, vec3_t vc );
  91
  92 void _CrossProduct( vec3_t v1, vec3_t v2, vec3_t cross );
  93 // I need this define in order to test some of the regression tests from time to time.
  94 // This define affect the precision of VectorNormalize() function only.
  95 #define MATHLIB_VECTOR_NORMALIZE_PRECISION_FIX 1
  96 vec_t VectorNormalize( const vec3_t in, vec3_t out );
  97 vec_t ColorNormalize( const vec3_t in, vec3_t out );
  98 void VectorInverse( vec3_t v );
  99 void VectorPolar( vec3_t v, float radius, float theta, float phi );
 100
 101 // default snapping, to 1
 102 void VectorSnap( vec3_t v );
 103
 104 // integer snapping
 105 void VectorISnap( vec3_t point, int snap );
 106
 107 // Gef:   added snap to float for sub-integer grid sizes
 108 // TTimo: we still use the int version of VectorSnap when possible
 109 //        to avoid potential rounding issues
 110 // TTimo: renaming to VectorFSnap for C implementation
 111 void VectorFSnap( vec3_t point, float snap );
 112
 113 // NOTE: added these from Ritual's Q3Radiant
 114 void ClearBounds( vec3_t mins, vec3_t maxs );
 115 void AddPointToBounds( vec3_t v, vec3_t mins, vec3_t maxs );
 116
 117 void AngleVectors( vec3_t angles, vec3_t forward, vec3_t right, vec3_t up );
 118 void VectorToAngles( vec3_t vec, vec3_t angles );
 119
 120 #define ZERO_EPSILON 1.0E-6
 121 #define RAD2DEGMULT 57.29577951308232f
 122 #define DEG2RADMULT 0.01745329251994329f
 123 #define RAD2DEG( a ) ( ( a ) * RAD2DEGMULT )
 124 #define DEG2RAD( a ) ( ( a ) * DEG2RADMULT )
 125
 126 void VectorRotate( vec3_t vIn, vec3_t vRotation, vec3_t out );
 127 void VectorRotateOrigin( vec3_t vIn, vec3_t vRotation, vec3_t vOrigin, vec3_t out );
 128
 129 // some function merged from tools mathlib code
 130
 131 qboolean PlaneFromPoints( vec4_t plane, const vec3_t a, const vec3_t b, const vec3_t c );
 132 void NormalToLatLong( const vec3_t normal, byte bytes[2] );
 133 int PlaneTypeForNormal( vec3_t normal );
 134 void RotatePointAroundVector( vec3_t dst, const vec3_t dir, const vec3_t point, float degrees );
 135
 136 // Spog
 137 // code imported from geomlib
 138
 139 /*!
 140    \todo
 141    FIXME test calls such as intersect tests should be named test_
 142  */
 143
 144 typedef vec_t m3x3_t[9];
 145 /*!NOTE
 146    m4x4 looks like this..
 147
 148                 x  y  z
 149    x axis        ( 0  1  2)
 150    y axis        ( 4  5  6)
 151    z axis        ( 8  9 10)
 152    translation   (12 13 14)
 153    scale         ( 0  5 10)
 154  */
 155 typedef vec_t m4x4_t[16];
 156
 157 #define M4X4_INDEX( m,row,col ) ( m[( col << 2 ) + row] )
 158
 159 typedef enum { TRANSLATE, SCALE, ROTATE } transformtype; // legacy, used only in pmesh.cpp
 160
 161 typedef enum { eXYZ, eYZX, eZXY, eXZY, eYXZ, eZYX } eulerOrder_t;
 162
 163 // constructors
 164 /*! create m4x4 as identity matrix */
 165 void m4x4_identity( m4x4_t matrix );
 166 /*! create m4x4 as a translation matrix, for a translation vec3 */
 167 void m4x4_translation_for_vec3( m4x4_t matrix, const vec3_t translation );
 168 /*! create m4x4 as a rotation matrix, for an euler angles (degrees) vec3 */
 169 void m4x4_rotation_for_vec3( m4x4_t matrix, const vec3_t euler, eulerOrder_t order );
 170 /*! create m4x4 as a scaling matrix, for a scale vec3 */
 171 void m4x4_scale_for_vec3( m4x4_t matrix, const vec3_t scale );
 172 /*! create m4x4 as a rotation matrix, for a quaternion vec4 */
 173 void m4x4_rotation_for_quat( m4x4_t matrix, const vec4_t rotation );
 174 /*! create m4x4 as a rotation matrix, for an axis vec3 and an angle (radians) */
 175 void m4x4_rotation_for_axisangle( m4x4_t matrix, const vec3_t axis, vec_t angle );
 176
 177 // a valid m4x4 to be modified is always first argument
 178 /*! translate m4x4 by a translation vec3 */
 179 void m4x4_translate_by_vec3( m4x4_t matrix, const vec3_t translation );
 180 /*! rotate m4x4 by a euler (degrees) vec3 */
 181 void m4x4_rotate_by_vec3( m4x4_t matrix, const vec3_t euler, eulerOrder_t order );
 182 /*! scale m4x4 by a scaling vec3 */
 183 void m4x4_scale_by_vec3( m4x4_t matrix, const vec3_t scale );
 184 /*! rotate m4x4 by a quaternion vec4 */
 185 void m4x4_rotate_by_quat( m4x4_t matrix, const vec4_t rotation );
 186 /*! rotate m4x4 by an axis vec3 and an angle (radians) */
 187 void m4x4_rotate_by_axisangle( m4x4_t matrix, const vec3_t axis, vec_t angle );
 188 /*! transform m4x4 by translation/euler/scaling vec3 (transform = translation.euler.scale) */
 189 void m4x4_transform_by_vec3( m4x4_t matrix, const vec3_t translation, const vec3_t euler, eulerOrder_t order, const vec3_t scale );
 190 /*! rotate m4x4 around a pivot point by euler(degrees) vec3 */
 191 void m4x4_pivoted_rotate_by_vec3( m4x4_t matrix, const vec3_t euler, eulerOrder_t order, const vec3_t pivotpoint );
 192 /*! scale m4x4 around a pivot point by scaling vec3 */
 193 void m4x4_pivoted_scale_by_vec3( m4x4_t matrix, const vec3_t scale, const vec3_t pivotpoint );
 194 /*! transform m4x4 around a pivot point by translation/euler/scaling vec3 */
 195 void m4x4_pivoted_transform_by_vec3( m4x4_t matrix, const vec3_t translation, const vec3_t euler, eulerOrder_t order, const vec3_t scale, const vec3_t pivotpoint );
 196 /*! rotate m4x4 around a pivot point by quaternion vec4 */
 197 void m4x4_pivoted_rotate_by_quat( m4x4_t matrix, const vec4_t rotation, const vec3_t pivotpoint );
 198 /*! rotate m4x4 around a pivot point by axis vec3 and angle (radians) */
 199 void m4x4_pivoted_rotate_by_axisangle( m4x4_t matrix, const vec3_t axis, vec_t angle, const vec3_t pivotpoint );
 200 /*! post-multiply m4x4 by another m4x4 */
 201 void m4x4_multiply_by_m4x4( m4x4_t matrix, const m4x4_t other );
 202 /*! pre-multiply m4x4 by another m4x4 */
 203 void m4x4_premultiply_by_m4x4( m4x4_t matrix, const m4x4_t other );
 204
 205 /*! multiply a point (x,y,z,1) by matrix */
 206 void m4x4_transform_point( const m4x4_t matrix, vec3_t point );
 207 /*! multiply a normal (x,y,z,0) by matrix */
 208 void m4x4_transform_normal( const m4x4_t matrix, vec3_t normal );
 209 /*! multiply a vec4 (x,y,z,w) by matrix */
 210 void m4x4_transform_vec4( const m4x4_t matrix, vec4_t vector );
 211
 212 /*! multiply a point (x,y,z,1) by matrix */
 213 void m4x4_transform_point( const m4x4_t matrix, vec3_t point );
 214 /*! multiply a normal (x,y,z,0) by matrix */
 215 void m4x4_transform_normal( const m4x4_t matrix, vec3_t normal );
 216
 217 /*! transpose a m4x4 */
 218 void m4x4_transpose( m4x4_t matrix );
 219 /*! invert an orthogonal 4x3 subset of a 4x4 matrix */
 220 void m4x4_orthogonal_invert( m4x4_t matrix );
 221 /*! invert any m4x4 using Kramer's rule.. return 1 if matrix is singular, else return 0 */
 222 int m4x4_invert( m4x4_t matrix );
 223
 224 /*!
 225    \todo object/ray intersection functions should maybe return a point rather than a distance?
 226  */
 227
 228 /*!
 229    aabb_t -  "axis-aligned" bounding box...
 230    origin: centre of bounding box...
 231    extents: +/- extents of box from origin...
 232    radius: cached length of extents vector...
 233  */
 234 typedef struct aabb_s
 235 {
 236         vec3_t origin;
 237         vec3_t extents;
 238         vec_t radius;
 239 } aabb_t;
 240
 241 /*!
 242    bbox_t - oriented bounding box...
 243    aabb: axis-aligned bounding box...
 244    axes: orientation axes...
 245  */
 246 typedef struct bbox_s
 247 {
 248         aabb_t aabb;
 249         vec3_t axes[3];
 250 } bbox_t;
 251
 252 /*!
 253    ray_t - origin point and direction unit-vector
 254  */
 255 typedef struct ray_s
 256 {
 257         vec3_t origin;
 258         vec3_t direction;
 259 } ray_t;
 260
 261
 262 /*! Generate AABB from min/max. */
 263 void aabb_construct_for_vec3( aabb_t *aabb, const vec3_t min, const vec3_t max );
 264 /*! Update bounding-sphere radius. */
 265 void aabb_update_radius( aabb_t *aabb );
 266 /*! Initialise AABB to negative size. */
 267 void aabb_clear( aabb_t *aabb );
 268
 269 /*! Extend AABB to include point. */
 270 void aabb_extend_by_point( aabb_t *aabb, const vec3_t point );
 271 /*! Extend AABB to include aabb_src. */
 272 void aabb_extend_by_aabb( aabb_t *aabb, const aabb_t *aabb_src );
 273 /*! Extend AABB by +/- extension vector. */
 274 void aabb_extend_by_vec3( aabb_t *aabb, vec3_t extension );
 275
 276 /*! Return 2 if point is inside, else 1 if point is on surface, else 0. */
 277 int aabb_intersect_point( const aabb_t *aabb, const vec3_t point );
 278 /*! Return 2 if aabb_src intersects, else 1 if aabb_src touches exactly, else 0. */
 279 int aabb_intersect_aabb( const aabb_t *aabb, const aabb_t *aabb_src );
 280 /*! Return 2 if aabb is behind plane, else 1 if aabb intersects plane, else 0. */
 281 int aabb_intersect_plane( const aabb_t *aabb, const float *plane );
 282 /*! Return 1 if aabb intersects ray, else 0... dist = closest intersection. */
 283 int aabb_intersect_ray( const aabb_t *aabb, const ray_t *ray, vec_t *dist );
 284 /*! Return 1 if aabb intersects ray, else 0. Faster, but does not provide point of intersection */
 285 int aabb_test_ray( const aabb_t* aabb, const ray_t* ray );
 286
 287 /*! Generate AABB from oriented bounding box. */
 288 void aabb_for_bbox( aabb_t *aabb, const bbox_t *bbox );
 289 /*! Generate AABB from 2-dimensions of min/max, specified by axis. */
 290 void aabb_for_area( aabb_t *aabb, vec3_t area_tl, vec3_t area_br, int axis );
 291 /*! Generate AABB to contain src * transform. NOTE: transform must be orthogonal */
 292 void aabb_for_transformed_aabb( aabb_t* dst, const aabb_t* src, const m4x4_t transform );
 293
 294
 295 /*! Generate oriented bounding box from AABB and transformation matrix. */
 296 /*!\todo Remove need to specify euler/scale. */
 297 void bbox_for_oriented_aabb( bbox_t *bbox, const aabb_t *aabb,
 298                                                          const m4x4_t matrix, const vec3_t euler, const vec3_t scale );
 299 /*! Return 2 is bbox is behind plane, else return 1 if bbox intersects plane, else return 0. */
 300 int bbox_intersect_plane( const bbox_t *bbox, const vec_t* plane );
 301
 302
 303 /*! Generate a ray from an origin point and a direction unit-vector */
 304 void ray_construct_for_vec3( ray_t *ray, const vec3_t origin, const vec3_t direction );
 305
 306 /*! Transform a ray */
 307 void ray_transform( ray_t *ray, const m4x4_t matrix );
 308
 309 /*! return true if point intersects cone formed by ray, divergence and epsilon */
 310 vec_t ray_intersect_point( const ray_t *ray, const vec3_t point, vec_t epsilon, vec_t divergence );
 311 /*! return true if triangle intersects ray... dist = dist from intersection point to ray-origin */
 312 vec_t ray_intersect_triangle( const ray_t *ray, qboolean bCullBack, const vec3_t vert0, const vec3_t vert1, const vec3_t vert2 );
 313
 314
 315 ////////////////////////////////////////////////////////////////////////////////
 316 // Below is double-precision math stuff.  This was initially needed by the new
 317 // "base winding" code in q3map2 brush processing in order to fix the famous
 318 // "disappearing triangles" issue.  These definitions can be used wherever extra
 319 // precision is needed.
 320 ////////////////////////////////////////////////////////////////////////////////
 321
 322 typedef double vec_accu_t;
 323 typedef vec_accu_t vec3_accu_t[3];
 324
 325 // Smallest positive value for vec_accu_t such that 1.0 + VEC_ACCU_SMALLEST_EPSILON_AROUND_ONE != 1.0.
 326 // In the case of 64 bit doubles (which is almost certainly the case), it's 0.00000000000000022204.
 327 // Don't forget that your epsilons should depend on the possible range of values,
 328 // because for example adding VEC_ACCU_SMALLEST_EPSILON_AROUND_ONE to 1024.0 will have no effect.
 329 #define VEC_ACCU_SMALLEST_EPSILON_AROUND_ONE DBL_EPSILON
 330
 331 vec_accu_t VectorLengthAccu( const vec3_accu_t v );
 332
 333 // I have a feeling it may be safer to break these #define functions out into actual functions
 334 // in order to avoid accidental loss of precision.  For example, say you call
 335 // VectorScaleAccu(vec3_t, vec_t, vec3_accu_t).  The scale would take place in 32 bit land
 336 // and the result would be cast to 64 bit, which would cause total loss of precision when
 337 // scaling by a large factor.
 338 //#define DotProductAccu(x, y) ((x)[0] * (y)[0] + (x)[1] * (y)[1] + (x)[2] * (y)[2])
 339 //#define VectorSubtractAccu(a, b, c) ((c)[0] = (a)[0] - (b)[0], (c)[1] = (a)[1] - (b)[1], (c)[2] = (a)[2] - (b)[2])
 340 //#define VectorAddAccu(a, b, c) ((c)[0] = (a)[0] + (b)[0], (c)[1] = (a)[1] + (b)[1], (c)[2] = (a)[2] + (b)[2])
 341 //#define VectorCopyAccu(a, b) ((b)[0] = (a)[0], (b)[1] = (a)[1], (b)[2] = (a)[2])
 342 //#define VectorScaleAccu(a, b, c) ((c)[0] = (b) * (a)[0], (c)[1] = (b) * (a)[1], (c)[2] = (b) * (a)[2])
 343 //#define CrossProductAccu(a, b, c) ((c)[0] = (a)[1] * (b)[2] - (a)[2] * (b)[1], (c)[1] = (a)[2] * (b)[0] - (a)[0] * (b)[2], (c)[2] = (a)[0] * (b)[1] - (a)[1] * (b)[0])
 344 //#define Q_rintAccu(in) ((vec_accu_t) floor(in + 0.5))
 345
 346 vec_accu_t DotProductAccu( const vec3_accu_t a, const vec3_accu_t b );
 347 void VectorSubtractAccu( const vec3_accu_t a, const vec3_accu_t b, vec3_accu_t out );
 348 void VectorAddAccu( const vec3_accu_t a, const vec3_accu_t b, vec3_accu_t out );
 349 void VectorCopyAccu( const vec3_accu_t in, vec3_accu_t out );
 350 void VectorScaleAccu( const vec3_accu_t in, vec_accu_t scaleFactor, vec3_accu_t out );
 351 void CrossProductAccu( const vec3_accu_t a, const vec3_accu_t b, vec3_accu_t out );
 352 vec_accu_t Q_rintAccu( vec_accu_t val );
 353
 354 void VectorCopyAccuToRegular( const vec3_accu_t in, vec3_t out );
 355 void VectorCopyRegularToAccu( const vec3_t in, vec3_accu_t out );
 356 vec_accu_t VectorNormalizeAccu( const vec3_accu_t in, vec3_accu_t out );
 357
 358 #ifdef __cplusplus
 359 }
 360 #endif
 361
 362 #endif /* __MATHLIB__ */