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