1a86094dacd9c9b9135855ec75117080d212c5e5
[divverent/netradiant.git] / libs / mathlib.h
1 /*
2 Copyright (C) 1999-2006 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
28 #ifdef __cplusplus
29
30 // start declarations of functions defined in C library.
31 extern "C"
32 {
33
34 #endif
35
36 #include "bytebool.h"
37
38 typedef float vec_t;
39 typedef vec_t vec3_t[3];
40 typedef vec_t vec5_t[5];
41 typedef vec_t vec4_t[4];
42
43 #define SIDE_FRONT              0
44 #define SIDE_ON                 2
45 #define SIDE_BACK               1
46 #define SIDE_CROSS              -2
47
48 // plane types are used to speed some tests
49 // 0-2 are axial planes
50 #define PLANE_X                 0
51 #define PLANE_Y                 1
52 #define PLANE_Z                 2
53 #define PLANE_NON_AXIAL 3
54
55 #define Q_PI    3.14159265358979323846f
56
57 extern const vec3_t vec3_origin;
58
59 extern const vec3_t g_vec3_axis_x;
60 extern const vec3_t g_vec3_axis_y;
61 extern const vec3_t g_vec3_axis_z;
62
63 #define EQUAL_EPSILON   0.001
64
65 #define DotProduct(x,y) ((x)[0]*(y)[0]+(x)[1]*(y)[1]+(x)[2]*(y)[2])
66 #define VectorSubtract(a,b,c) ((c)[0]=(a)[0]-(b)[0],(c)[1]=(a)[1]-(b)[1],(c)[2]=(a)[2]-(b)[2])
67 #define VectorAdd(a,b,c) ((c)[0]=(a)[0]+(b)[0],(c)[1]=(a)[1]+(b)[1],(c)[2]=(a)[2]+(b)[2])
68 #define VectorIncrement(a,b) ((b)[0]+=(a)[0],(b)[1]+=(a)[1],(b)[2]+=(a)[2])
69 #define VectorCopy(a,b) ((b)[0]=(a)[0],(b)[1]=(a)[1],(b)[2]=(a)[2])
70 #define VectorSet(v, a, b, c) ((v)[0]=(a),(v)[1]=(b),(v)[2]=(c))
71 #define VectorScale(a,b,c) ((c)[0]=(b)*(a)[0],(c)[1]=(b)*(a)[1],(c)[2]=(b)*(a)[2])
72 #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)
73 #define VectorNegate(a,b) ((b)[0]=-(a)[0],(b)[1]=-(a)[1],(b)[2]=-(a)[2])
74 #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])
75 #define VectorClear(x) ((x)[0]=(x)[1]=(x)[2]=0)
76
77 #define FLOAT_SNAP(f,snap) ( (float)( floor( (f) / (snap) + 0.5 ) * (snap) ) )
78 #define FLOAT_TO_INTEGER(f) ( (float)( floor( (f) + 0.5 ) ) )
79
80 #define RGBTOGRAY(x) ( (float)((x)[0]) * 0.2989f + (float)((x)[1]) * 0.5870f + (float)((x)[2]) * 0.1140f )
81
82 #define Q_rint(in) ((vec_t)floor(in+0.5))
83
84 qboolean VectorCompare (const vec3_t v1, const vec3_t v2);
85
86 vec_t VectorLength(const vec3_t v);
87
88 void VectorMA( const vec3_t va, vec_t scale, const vec3_t vb, vec3_t vc );
89
90 void _CrossProduct (vec3_t v1, vec3_t v2, vec3_t cross);
91 vec_t VectorNormalize (const vec3_t in, vec3_t out);
92 vec_t VectorSetLength (const vec3_t in, vec_t length, vec3_t out);
93 vec_t ColorNormalize( const vec3_t in, vec3_t out );
94 void VectorInverse (vec3_t v);
95 void VectorPolar(vec3_t v, float radius, float theta, float phi);
96
97 // default snapping, to 1
98 void VectorSnap(vec3_t v);
99
100 // integer snapping
101 void VectorISnap(vec3_t point, int snap);
102
103 // Gef:   added snap to float for sub-integer grid sizes
104 // TTimo: we still use the int version of VectorSnap when possible
105 //        to avoid potential rounding issues
106 // TTimo: renaming to VectorFSnap for C implementation
107 void VectorFSnap(vec3_t point, float snap);
108
109 // NOTE: added these from Ritual's Q3Radiant
110 void ClearBounds (vec3_t mins, vec3_t maxs);
111 void AddPointToBounds (vec3_t v, vec3_t mins, vec3_t maxs);
112
113
114 #define PITCH                           0               // up / down
115 #define YAW                                     1               // left / right
116 #define ROLL                            2               // fall over
117
118 void AngleVectors (vec3_t angles, vec3_t forward, vec3_t right, vec3_t up);
119 void VectorToAngles( vec3_t vec, vec3_t angles );
120
121 #define ZERO_EPSILON 1.0E-6
122 #define RAD2DEGMULT 57.29577951308232f
123 #define DEG2RADMULT 0.01745329251994329f
124 #define RAD2DEG( a ) ( (a) * RAD2DEGMULT )
125 #define DEG2RAD( a ) ( (a) * DEG2RADMULT )
126
127 void VectorRotate (vec3_t vIn, vec3_t vRotation, vec3_t out);
128 void VectorRotateOrigin (vec3_t vIn, vec3_t vRotation, vec3_t vOrigin, vec3_t out);
129
130 // some function merged from tools mathlib code
131
132 qboolean PlaneFromPoints( vec4_t plane, const vec3_t a, const vec3_t b, const vec3_t c );
133 void NormalToLatLong( const vec3_t normal, byte bytes[2] );
134 int     PlaneTypeForNormal (vec3_t normal);
135 void RotatePointAroundVector( vec3_t dst, const vec3_t dir, const vec3_t point, float degrees );
136
137
138 /*!
139 \todo
140 FIXME test calls such as intersect tests should be named test_
141 */
142
143 typedef vec_t m3x3_t[9];
144 /*!NOTE 
145 m4x4 looks like this..
146
147                 x  y  z
148 x axis        ( 0  1  2)
149 y axis        ( 4  5  6)
150 z axis        ( 8  9 10)
151 translation   (12 13 14)
152 scale         ( 0  5 10)
153 */
154 typedef vec_t m4x4_t[16];
155
156 #define M4X4_INDEX(m,row,col) (m[(col<<2)+row])
157
158 typedef enum { eXYZ, eYZX, eZXY, eXZY, eYXZ, eZYX } eulerOrder_t;
159
160 #define CLIP_PASS 0x00 // 000000
161 #define CLIP_LT_X 0x01 // 000001
162 #define CLIP_GT_X 0x02 // 000010
163 #define CLIP_LT_Y 0x04 // 000100
164 #define CLIP_GT_Y 0x08 // 001000
165 #define CLIP_LT_Z 0x10 // 010000
166 #define CLIP_GT_Z 0x20 // 100000
167 #define CLIP_FAIL 0x3F // 111111
168 typedef unsigned char clipmask_t;
169
170 extern const m4x4_t g_m4x4_identity;
171
172 #define M4X4_COPY(dst,src) (\
173 (dst)[0]=(src)[0],\
174 (dst)[1]=(src)[1],\
175 (dst)[2]=(src)[2],\
176 (dst)[3]=(src)[3],\
177 (dst)[4]=(src)[4],\
178 (dst)[5]=(src)[5],\
179 (dst)[6]=(src)[6],\
180 (dst)[7]=(src)[7],\
181 (dst)[8]=(src)[8],\
182 (dst)[9]=(src)[9],\
183 (dst)[10]=(src)[10],\
184 (dst)[11]=(src)[11],\
185 (dst)[12]=(src)[12],\
186 (dst)[13]=(src)[13],\
187 (dst)[14]=(src)[14],\
188 (dst)[15]=(src)[15])
189
190 typedef enum
191 {
192   eRightHanded = 0,
193   eLeftHanded = 1,
194
195 m4x4Handedness_t;
196
197 m4x4Handedness_t m4x4_handedness(const m4x4_t matrix);
198
199 /*! assign other m4x4 to this m4x4 */
200 void m4x4_assign(m4x4_t matrix, const m4x4_t other);
201
202 // constructors
203 /*! create m4x4 as identity matrix */
204 void m4x4_identity(m4x4_t matrix);
205 /*! create m4x4 as a translation matrix, for a translation vec3 */
206 void m4x4_translation_for_vec3(m4x4_t matrix, const vec3_t translation);
207 /*! create m4x4 as a rotation matrix, for an euler angles (degrees) vec3 */
208 void m4x4_rotation_for_vec3(m4x4_t matrix, const vec3_t euler, eulerOrder_t order);
209 /*! create m4x4 as a scaling matrix, for a scale vec3 */
210 void m4x4_scale_for_vec3(m4x4_t matrix, const vec3_t scale);
211 /*! create m4x4 as a rotation matrix, for a quaternion vec4 */
212 void m4x4_rotation_for_quat(m4x4_t matrix, const vec4_t rotation);
213 /*! create m4x4 as a rotation matrix, for an axis vec3 and an angle (radians) */
214 void m4x4_rotation_for_axisangle(m4x4_t matrix, const vec3_t axis, double angle);
215 /*! generate a perspective matrix by specifying the view frustum */
216 void m4x4_frustum(m4x4_t matrix, vec_t left, vec_t right, vec_t bottom, vec_t top, vec_t nearval, vec_t farval);
217
218 // a valid m4x4 to access is always first argument
219 /*! extract translation vec3 from matrix */
220 void m4x4_get_translation_vec3(const m4x4_t matrix, vec3_t translation);
221 /*! extract euler rotation angles from a rotation-only matrix */
222 void m4x4_get_rotation_vec3(const m4x4_t matrix, vec3_t euler, eulerOrder_t order);
223 /*! extract scale vec3 from matrix */
224 void m4x4_get_scale_vec3(const m4x4_t matrix, vec3_t scale);
225 /*! extract translation/euler/scale from an orthogonal matrix. NOTE: requires right-handed axis-base */
226 void m4x4_get_transform_vec3(const m4x4_t matrix, vec3_t translation, vec3_t euler, eulerOrder_t order, vec3_t scale);
227
228 // a valid m4x4 to be modified is always first argument
229 /*! translate m4x4 by a translation vec3 */
230 void m4x4_translate_by_vec3(m4x4_t matrix, const vec3_t translation);
231 /*! rotate m4x4 by a euler (degrees) vec3 */
232 void m4x4_rotate_by_vec3(m4x4_t matrix, const vec3_t euler, eulerOrder_t order);
233 /*! scale m4x4 by a scaling vec3 */
234 void m4x4_scale_by_vec3(m4x4_t matrix, const vec3_t scale);
235 /*! rotate m4x4 by a quaternion vec4 */
236 void m4x4_rotate_by_quat(m4x4_t matrix, const vec4_t rotation);
237 /*! rotate m4x4 by an axis vec3 and an angle (radians) */
238 void m4x4_rotate_by_axisangle(m4x4_t matrix, const vec3_t axis, double angle);
239 /*! transform m4x4 by translation/eulerZYX/scaling vec3 (transform = scale * eulerZ * eulerY * eulerX * translation) */
240 void m4x4_transform_by_vec3(m4x4_t matrix, const vec3_t translation, const vec3_t euler, eulerOrder_t order, const vec3_t scale);
241 /*! rotate m4x4 around a pivot point by eulerZYX vec3 */
242 void m4x4_pivoted_rotate_by_vec3(m4x4_t matrix, const vec3_t euler, eulerOrder_t order, const vec3_t pivotpoint);
243 /*! scale m4x4 around a pivot point by scaling vec3 */
244 void m4x4_pivoted_scale_by_vec3(m4x4_t matrix, const vec3_t scale, const vec3_t pivotpoint);
245 /*! transform m4x4 around a pivot point by translation/eulerZYX/scaling vec3 */
246 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);
247 /*! transform m4x4 around a pivot point by translation/rotation/scaling vec3 */
248 void m4x4_pivoted_transform_by_rotation(m4x4_t matrix, const vec3_t translation, const m4x4_t rotation, const vec3_t scale, const vec3_t pivotpoint);
249 /*! rotate m4x4 around a pivot point by quaternion vec4 */
250 void m4x4_pivoted_rotate_by_quat(m4x4_t matrix, const vec4_t quat, const vec3_t pivotpoint);
251 /*! rotate m4x4 around a pivot point by axis vec3 and angle (radians) */
252 void m4x4_pivoted_rotate_by_axisangle(m4x4_t matrix, const vec3_t axis, double angle, const vec3_t pivotpoint);
253
254 /*! postmultiply m4x4 by another m4x4 */
255 void m4x4_multiply_by_m4x4(m4x4_t matrix, const m4x4_t matrix_src);
256 /*! premultiply m4x4 by another m4x4 */
257 void m4x4_premultiply_by_m4x4(m4x4_t matrix, const m4x4_t matrix_src);
258 /*! postmultiply orthogonal m4x4 by another orthogonal m4x4 */
259 void m4x4_orthogonal_multiply_by_m4x4(m4x4_t matrix, const m4x4_t matrix_src);
260 /*! premultiply orthogonal m4x4 by another orthogonal m4x4 */
261 void m4x4_orthogonal_premultiply_by_m4x4(m4x4_t matrix, const m4x4_t matrix_src);
262
263 /*! multiply a point (x,y,z,1) by matrix */
264 void m4x4_transform_point(const m4x4_t matrix, vec3_t point);
265 /*! multiply a normal (x,y,z,0) by matrix */
266 void m4x4_transform_normal(const m4x4_t matrix, vec3_t normal);
267 /*! multiply a vec4 (x,y,z,w) by matrix */
268 void m4x4_transform_vec4(const m4x4_t matrix, vec4_t vector);
269
270 /*! multiply a point (x,y,z,1) by matrix */
271 void m4x4_transform_point(const m4x4_t matrix, vec3_t point);
272 /*! multiply a normal (x,y,z,0) by matrix */
273 void m4x4_transform_normal(const m4x4_t matrix, vec3_t normal);
274
275 /*! transpose a m4x4 */
276 void m4x4_transpose(m4x4_t matrix);
277 /*! invert an orthogonal 4x3 subset of a 4x4 matrix */
278 int m4x4_orthogonal_invert(m4x4_t matrix);
279 /*! m4_det */
280 float m4_det( m4x4_t mr );
281 /*! invert any m4x4 using Kramer's rule.. return 1 if matrix is singular, else return 0 */
282 int m4x4_invert(m4x4_t matrix);
283
284 /*! clip a point (x,y,z,1) by canonical matrix */
285 clipmask_t m4x4_clip_point(const m4x4_t matrix, const vec3_t point, vec4_t clipped);
286 /*! device-space polygon for clipped triangle */
287 unsigned int m4x4_clip_triangle(const m4x4_t matrix, const vec3_t p0, const vec3_t p1, const vec3_t p2, vec4_t clipped[9]);
288 /*! device-space line for clipped line  */
289 unsigned int m4x4_clip_line(const m4x4_t matrix, const vec3_t p0, const vec3_t p1, vec4_t clipped[2]);
290
291
292 //! quaternion identity
293 void quat_identity(vec4_t quat);
294 //! quaternion from two unit vectors
295 void quat_for_unit_vectors(vec4_t quat, const vec3_t from, const vec3_t to);
296 //! quaternion from axis and angle (radians)
297 void quat_for_axisangle(vec4_t quat, const vec3_t axis, double angle);
298 //! concatenates two rotations.. equivalent to m4x4_multiply_by_m4x4 .. postmultiply.. the right-hand side is the first rotation performed
299 void quat_multiply_by_quat(vec4_t quat, const vec4_t other);
300 //! negate a quaternion
301 void quat_conjugate(vec4_t quat);
302 //! normalise a quaternion
303 void quat_normalise(vec4_t quat);
304
305
306
307 /*!
308 \todo object/ray intersection functions should maybe return a point rather than a distance?
309 */
310
311 /*!
312 aabb_t -  "axis-aligned" bounding box... 
313   origin: centre of bounding box... 
314   extents: +/- extents of box from origin... 
315 */
316 typedef struct aabb_s
317 {
318   vec3_t origin;
319   vec3_t extents;
320 } aabb_t;
321
322 extern const aabb_t g_aabb_null;
323
324 /*!
325 bbox_t - oriented bounding box... 
326   aabb: axis-aligned bounding box... 
327   axes: orientation axes... 
328 */
329 typedef struct bbox_s
330 {
331   aabb_t aabb;
332   vec3_t axes[3];
333   vec_t radius;
334 } bbox_t;
335
336 /*!
337 ray_t - origin point and direction unit-vector
338 */
339 typedef struct ray_s
340 {
341   vec3_t origin;
342   vec3_t direction;
343 } ray_t;
344
345 /*!
346 line_t - centre point and displacement of end point from centre
347 */
348 typedef struct line_s
349 {
350   vec3_t origin;
351   vec3_t extents;
352 } line_t;
353
354
355 /*! Generate line from start/end points. */
356 void line_construct_for_vec3(line_t* line, const vec3_t start, const vec3_t end);
357 /*! Return 2 if line is behind plane, else return 1 if line intersects plane, else return 0. */
358 int line_test_plane(const line_t* line, const vec4_t plane);
359
360 /*! Generate AABB from min/max. */
361 void aabb_construct_for_vec3(aabb_t* aabb, const vec3_t min, const vec3_t max);
362 /*! Initialise AABB to negative size. */
363 void aabb_clear(aabb_t* aabb);
364
365 /*! Extend AABB to include point. */
366 void aabb_extend_by_point(aabb_t* aabb, const vec3_t point);
367 /*! Extend AABB to include aabb_src. */
368 void aabb_extend_by_aabb(aabb_t* aabb, const aabb_t* aabb_src);
369 /*! Extend AABB by +/- extension vector. */
370 void aabb_extend_by_vec3(aabb_t* aabb, vec3_t extension);
371
372 /*! Return 2 if point is inside, else 1 if point is on surface, else 0. */
373 int aabb_test_point(const aabb_t* aabb, const vec3_t point);
374 /*! Return 2 if aabb_src intersects, else 1 if aabb_src touches exactly, else 0. */
375 int aabb_test_aabb(const aabb_t* aabb, const aabb_t* aabb_src);
376 /*! Return 2 if aabb is behind plane, else 1 if aabb intersects plane, else 0. */
377 int aabb_test_plane(const aabb_t* aabb, const float* plane);
378 /*! Return 1 if aabb intersects ray, else 0... dist = closest intersection. */
379 int aabb_intersect_ray(const aabb_t* aabb, const ray_t* ray, vec3_t intersection);
380 /*! Return 1 if aabb intersects ray, else 0. Faster, but does not provide point of intersection */
381 int aabb_test_ray(const aabb_t* aabb, const ray_t* ray);
382
383 /*! Return 2 if oriented aabb is behind plane, else 1 if aabb intersects plane, else 0. */
384 int aabb_oriented_intersect_plane(const aabb_t* aabb, const m4x4_t transform, const vec_t* plane);
385
386 /*! Calculate the corners of the aabb. */
387 void aabb_corners(const aabb_t* aabb, vec3_t corners[8]);
388
389 /*! (deprecated) Generate AABB from oriented bounding box. */
390 void aabb_for_bbox(aabb_t* aabb, const bbox_t* bbox);
391 /*! (deprecated) Generate AABB from 2-dimensions of min/max, specified by axis. */
392 void aabb_for_area(aabb_t* aabb, vec3_t area_tl, vec3_t area_br, int axis);
393 /*! Generate AABB to contain src*  transform. NOTE: transform must be orthogonal */
394 void aabb_for_transformed_aabb(aabb_t* dst, const aabb_t* src, const m4x4_t transform);
395
396 /*! Update bounding-sphere radius. */
397 void bbox_update_radius(bbox_t* bbox);
398 /*! Generate oriented bounding box from AABB and transformation matrix. */
399 /*!\todo Remove need to specify eulerZYX/scale. */
400 void bbox_for_oriented_aabb(bbox_t* bbox, const aabb_t* aabb,
401                     const m4x4_t matrix, const vec3_t eulerZYX, const vec3_t scale);
402 /*! Return 2 if bbox is behind plane, else return 1 if bbox intersects plane, else return 0. */
403 int bbox_intersect_plane(const bbox_t* bbox, const vec_t* plane);
404
405
406 /*! Generate a ray from an origin point and a direction unit-vector */
407 void ray_construct_for_vec3(ray_t* ray, const vec3_t origin, const vec3_t direction);
408   
409 /*! Transform a ray */
410 void ray_transform(ray_t* ray, const m4x4_t matrix);
411
412 /*! distance from ray origin in ray direction to point. FLT_MAX if no intersection. */
413 vec_t ray_intersect_point(const ray_t* ray, const vec3_t point, vec_t epsilon, vec_t divergence);
414 /*! distance from ray origin in ray direction to triangle. FLT_MAX if no intersection. */
415 vec_t ray_intersect_triangle(const ray_t* ray, qboolean bCullBack, const vec3_t vert0, const vec3_t vert1, const vec3_t vert2);
416 /*! distance from ray origin in ray direction to plane. */
417 vec_t ray_intersect_plane(const ray_t* ray, const vec3_t normal, vec_t dist);
418
419
420 int plane_intersect_planes(const vec4_t plane1, const vec4_t plane2, const vec4_t plane3, vec3_t intersection);
421
422
423 #ifdef __cplusplus
424 }
425 #endif
426
427 #endif /* __MATHLIB__ */