Rewriting BaseWindingForPlane() in polylib.c from the ground up. The behavior
[xonotic/netradiant.git] / 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
28 #include "bytebool.h"
29
30 #ifdef __cplusplus
31 extern "C"
32 {
33 #endif
34
35 typedef float vec_t;
36 typedef vec_t vec3_t[3];
37 typedef vec_t vec5_t[5];
38 typedef vec_t vec4_t[4];
39
40 #define SIDE_FRONT              0
41 #define SIDE_ON                 2
42 #define SIDE_BACK               1
43 #define SIDE_CROSS              -2
44
45 // plane types are used to speed some tests
46 // 0-2 are axial planes
47 #define PLANE_X                 0
48 #define PLANE_Y                 1
49 #define PLANE_Z                 2
50 #define PLANE_NON_AXIAL 3
51
52 #define Q_PI    3.14159265358979323846f
53
54 extern vec3_t vec3_origin;
55
56 #define EQUAL_EPSILON   0.001
57
58 #ifndef VEC_MAX
59 #define VEC_MAX 3.402823466e+38F
60 #endif
61
62 qboolean VectorCompare (vec3_t v1, vec3_t v2);
63
64 #define DotProduct(x,y) ((x)[0]*(y)[0]+(x)[1]*(y)[1]+(x)[2]*(y)[2])
65 #define VectorSubtract(a,b,c) ((c)[0]=(a)[0]-(b)[0],(c)[1]=(a)[1]-(b)[1],(c)[2]=(a)[2]-(b)[2])
66 #define VectorAdd(a,b,c) ((c)[0]=(a)[0]+(b)[0],(c)[1]=(a)[1]+(b)[1],(c)[2]=(a)[2]+(b)[2])
67 #define VectorIncrement(a,b) ((b)[0]+=(a)[0],(b)[1]+=(a)[1],(b)[2]+=(a)[2])
68 #define VectorCopy(a,b) ((b)[0]=(a)[0],(b)[1]=(a)[1],(b)[2]=(a)[2])
69 #define VectorSet(v, a, b, c) ((v)[0]=(a),(v)[1]=(b),(v)[2]=(c))
70 #define VectorScale(a,b,c) ((c)[0]=(b)*(a)[0],(c)[1]=(b)*(a)[1],(c)[2]=(b)*(a)[2])
71 #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)
72 #define VectorNegative(a,b) ((b)[0]=-(a)[0],(b)[1]=-(a)[1],(b)[2]=-(a)[2])
73 #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])
74 #define VectorClear(x) ((x)[0]=(x)[1]=(x)[2]=0)
75
76 #define Q_rint(in) ((vec_t)floor(in+0.5))
77
78 vec_t VectorLength(vec3_t v);
79
80 void VectorMA( const vec3_t va, vec_t scale, const vec3_t vb, vec3_t vc );
81
82 void _CrossProduct (vec3_t v1, vec3_t v2, vec3_t cross);
83 vec_t VectorNormalize (const vec3_t in, vec3_t out);
84 vec_t VectorSetLength (const vec3_t in, vec_t length, vec3_t out);
85 vec_t ColorNormalize( const vec3_t in, vec3_t out );
86 void VectorInverse (vec3_t v);
87 void VectorPolar(vec3_t v, float radius, float theta, float phi);
88
89 // default snapping, to 1
90 void VectorSnap(vec3_t v);
91
92 // integer snapping
93 void VectorISnap(vec3_t point, int snap);
94
95 // Gef:   added snap to float for sub-integer grid sizes
96 // TTimo: we still use the int version of VectorSnap when possible
97 //        to avoid potential rounding issues
98 // TTimo: renaming to VectorFSnap for C implementation
99 void VectorFSnap(vec3_t point, float snap);
100
101 // NOTE: added these from Ritual's Q3Radiant
102 void ClearBounds (vec3_t mins, vec3_t maxs);
103 void AddPointToBounds (vec3_t v, vec3_t mins, vec3_t maxs);
104
105 void AngleVectors (vec3_t angles, vec3_t forward, vec3_t right, vec3_t up);
106 void VectorToAngles( vec3_t vec, vec3_t angles );
107
108 #define ZERO_EPSILON 1.0E-6
109 #define RAD2DEGMULT 57.29577951308232f
110 #define DEG2RADMULT 0.01745329251994329f
111 #define RAD2DEG( a ) ( (a) * RAD2DEGMULT )
112 #define DEG2RAD( a ) ( (a) * DEG2RADMULT )
113
114 void VectorRotate (vec3_t vIn, vec3_t vRotation, vec3_t out);
115 void VectorRotateOrigin (vec3_t vIn, vec3_t vRotation, vec3_t vOrigin, vec3_t out);
116
117 // some function merged from tools mathlib code
118
119 qboolean PlaneFromPoints( vec4_t plane, const vec3_t a, const vec3_t b, const vec3_t c );
120 void NormalToLatLong( const vec3_t normal, byte bytes[2] );
121 int     PlaneTypeForNormal (vec3_t normal);
122 void RotatePointAroundVector( vec3_t dst, const vec3_t dir, const vec3_t point, float degrees );
123
124 // Spog
125 // code imported from geomlib
126
127 /*!
128 \todo
129 FIXME test calls such as intersect tests should be named test_
130 */
131
132 typedef vec_t m3x3_t[9];
133 /*!NOTE 
134 m4x4 looks like this..
135
136                 x  y  z
137 x axis        ( 0  1  2)
138 y axis        ( 4  5  6)
139 z axis        ( 8  9 10)
140 translation   (12 13 14)
141 scale         ( 0  5 10)
142 */
143 typedef vec_t m4x4_t[16];
144
145 #define M4X4_INDEX(m,row,col) (m[(col<<2)+row])
146
147 typedef enum { TRANSLATE, SCALE, ROTATE } transformtype; // legacy, used only in pmesh.cpp
148
149 typedef enum { eXYZ, eYZX, eZXY, eXZY, eYXZ, eZYX } eulerOrder_t;
150
151 // constructors
152 /*! create m4x4 as identity matrix */
153 void m4x4_identity(m4x4_t matrix);
154 /*! create m4x4 as a translation matrix, for a translation vec3 */
155 void m4x4_translation_for_vec3(m4x4_t matrix, const vec3_t translation);
156 /*! create m4x4 as a rotation matrix, for an euler angles (degrees) vec3 */
157 void m4x4_rotation_for_vec3(m4x4_t matrix, const vec3_t euler, eulerOrder_t order);
158 /*! create m4x4 as a scaling matrix, for a scale vec3 */
159 void m4x4_scale_for_vec3(m4x4_t matrix, const vec3_t scale);
160 /*! create m4x4 as a rotation matrix, for a quaternion vec4 */
161 void m4x4_rotation_for_quat(m4x4_t matrix, const vec4_t rotation);
162 /*! create m4x4 as a rotation matrix, for an axis vec3 and an angle (radians) */
163 void m4x4_rotation_for_axisangle(m4x4_t matrix, const vec3_t axis, vec_t angle);
164
165 // a valid m4x4 to be modified is always first argument
166 /*! translate m4x4 by a translation vec3 */
167 void m4x4_translate_by_vec3(m4x4_t matrix, const vec3_t translation);
168 /*! rotate m4x4 by a euler (degrees) vec3 */
169 void m4x4_rotate_by_vec3(m4x4_t matrix, const vec3_t euler, eulerOrder_t order);
170 /*! scale m4x4 by a scaling vec3 */
171 void m4x4_scale_by_vec3(m4x4_t matrix, const vec3_t scale);
172 /*! rotate m4x4 by a quaternion vec4 */
173 void m4x4_rotate_by_quat(m4x4_t matrix, const vec4_t rotation);
174 /*! rotate m4x4 by an axis vec3 and an angle (radians) */
175 void m4x4_rotate_by_axisangle(m4x4_t matrix, const vec3_t axis, vec_t angle);
176 /*! transform m4x4 by translation/euler/scaling vec3 (transform = translation.euler.scale) */
177 void m4x4_transform_by_vec3(m4x4_t matrix, const vec3_t translation, const vec3_t euler, eulerOrder_t order, const vec3_t scale);
178 /*! rotate m4x4 around a pivot point by euler(degrees) vec3 */
179 void m4x4_pivoted_rotate_by_vec3(m4x4_t matrix, const vec3_t euler, eulerOrder_t order, const vec3_t pivotpoint);
180 /*! scale m4x4 around a pivot point by scaling vec3 */
181 void m4x4_pivoted_scale_by_vec3(m4x4_t matrix, const vec3_t scale, const vec3_t pivotpoint);
182 /*! transform m4x4 around a pivot point by translation/euler/scaling vec3 */
183 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);
184 /*! rotate m4x4 around a pivot point by quaternion vec4 */
185 void m4x4_pivoted_rotate_by_quat(m4x4_t matrix, const vec4_t rotation, const vec3_t pivotpoint);
186 /*! rotate m4x4 around a pivot point by axis vec3 and angle (radians) */
187 void m4x4_pivoted_rotate_by_axisangle(m4x4_t matrix, const vec3_t axis, vec_t angle, const vec3_t pivotpoint);
188 /*! post-multiply m4x4 by another m4x4 */
189 void m4x4_multiply_by_m4x4(m4x4_t matrix, const m4x4_t other);
190 /*! pre-multiply m4x4 by another m4x4 */
191 void m4x4_premultiply_by_m4x4(m4x4_t matrix, const m4x4_t other);
192
193 /*! multiply a point (x,y,z,1) by matrix */
194 void m4x4_transform_point(const m4x4_t matrix, vec3_t point);
195 /*! multiply a normal (x,y,z,0) by matrix */
196 void m4x4_transform_normal(const m4x4_t matrix, vec3_t normal);
197 /*! multiply a vec4 (x,y,z,w) by matrix */
198 void m4x4_transform_vec4(const m4x4_t matrix, vec4_t vector);
199
200 /*! multiply a point (x,y,z,1) by matrix */
201 void m4x4_transform_point(const m4x4_t matrix, vec3_t point);
202 /*! multiply a normal (x,y,z,0) by matrix */
203 void m4x4_transform_normal(const m4x4_t matrix, vec3_t normal);
204
205 /*! transpose a m4x4 */
206 void m4x4_transpose(m4x4_t matrix);
207 /*! invert an orthogonal 4x3 subset of a 4x4 matrix */
208 void m4x4_orthogonal_invert(m4x4_t matrix);
209 /*! invert any m4x4 using Kramer's rule.. return 1 if matrix is singular, else return 0 */
210 int m4x4_invert(m4x4_t matrix);
211
212 /*!
213 \todo object/ray intersection functions should maybe return a point rather than a distance?
214 */
215
216 /*!
217 aabb_t -  "axis-aligned" bounding box... 
218   origin: centre of bounding box... 
219   extents: +/- extents of box from origin... 
220   radius: cached length of extents vector... 
221 */
222 typedef struct aabb_s
223 {
224   vec3_t origin;
225   vec3_t extents;
226   vec_t radius;
227 } aabb_t;
228
229 /*!
230 bbox_t - oriented bounding box... 
231   aabb: axis-aligned bounding box... 
232   axes: orientation axes... 
233 */
234 typedef struct bbox_s
235 {
236   aabb_t aabb;
237   vec3_t axes[3];
238 } bbox_t;
239
240 /*!
241 ray_t - origin point and direction unit-vector
242 */
243 typedef struct ray_s
244 {
245   vec3_t origin;
246   vec3_t direction;
247 } ray_t;
248
249
250 /*! Generate AABB from min/max. */
251 void aabb_construct_for_vec3(aabb_t *aabb, const vec3_t min, const vec3_t max);
252 /*! Update bounding-sphere radius. */
253 void aabb_update_radius(aabb_t *aabb);
254 /*! Initialise AABB to negative size. */
255 void aabb_clear(aabb_t *aabb);
256
257 /*! Extend AABB to include point. */
258 void aabb_extend_by_point(aabb_t *aabb, const vec3_t point);
259 /*! Extend AABB to include aabb_src. */
260 void aabb_extend_by_aabb(aabb_t *aabb, const aabb_t *aabb_src);
261 /*! Extend AABB by +/- extension vector. */
262 void aabb_extend_by_vec3(aabb_t *aabb, vec3_t extension);
263
264 /*! Return 2 if point is inside, else 1 if point is on surface, else 0. */
265 int aabb_intersect_point(const aabb_t *aabb, const vec3_t point);
266 /*! Return 2 if aabb_src intersects, else 1 if aabb_src touches exactly, else 0. */
267 int aabb_intersect_aabb(const aabb_t *aabb, const aabb_t *aabb_src);
268 /*! Return 2 if aabb is behind plane, else 1 if aabb intersects plane, else 0. */
269 int aabb_intersect_plane(const aabb_t *aabb, const float *plane);
270 /*! Return 1 if aabb intersects ray, else 0... dist = closest intersection. */
271 int aabb_intersect_ray(const aabb_t *aabb, const ray_t *ray, vec_t *dist);
272 /*! Return 1 if aabb intersects ray, else 0. Faster, but does not provide point of intersection */
273 int aabb_test_ray(const aabb_t* aabb, const ray_t* ray);
274
275 /*! Generate AABB from oriented bounding box. */
276 void aabb_for_bbox(aabb_t *aabb, const bbox_t *bbox);
277 /*! Generate AABB from 2-dimensions of min/max, specified by axis. */
278 void aabb_for_area(aabb_t *aabb, vec3_t area_tl, vec3_t area_br, int axis);
279 /*! Generate AABB to contain src * transform. NOTE: transform must be orthogonal */
280 void aabb_for_transformed_aabb(aabb_t* dst, const aabb_t* src, const m4x4_t transform);
281
282
283 /*! Generate oriented bounding box from AABB and transformation matrix. */
284 /*!\todo Remove need to specify euler/scale. */
285 void bbox_for_oriented_aabb(bbox_t *bbox, const aabb_t *aabb,
286                     const m4x4_t matrix, const vec3_t euler, const vec3_t scale);
287 /*! Return 2 is bbox is behind plane, else return 1 if bbox intersects plane, else return 0. */
288 int bbox_intersect_plane(const bbox_t *bbox, const vec_t* plane);
289
290
291 /*! Generate a ray from an origin point and a direction unit-vector */
292 void ray_construct_for_vec3(ray_t *ray, const vec3_t origin, const vec3_t direction);
293   
294 /*! Transform a ray */
295 void ray_transform(ray_t *ray, const m4x4_t matrix);
296
297 /*! return true if point intersects cone formed by ray, divergence and epsilon */
298 vec_t ray_intersect_point(const ray_t *ray, const vec3_t point, vec_t epsilon, vec_t divergence);
299 /*! return true if triangle intersects ray... dist = dist from intersection point to ray-origin */
300 vec_t ray_intersect_triangle(const ray_t *ray, qboolean bCullBack, const vec3_t vert0, const vec3_t vert1, const vec3_t vert2);
301
302 #ifdef __cplusplus
303 }
304 #endif
305
306 #endif /* __MATHLIB__ */