e07d76f12df726a1f07c1de714ce6d1cc4c71791
[blender.git] / source / blender / blenlib / BLI_math_geom.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: some of this file.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  * */
25
26 #ifndef __BLI_MATH_GEOM_H__
27 #define __BLI_MATH_GEOM_H__
28
29 /** \file BLI_math_geom.h
30  *  \ingroup bli
31  */
32
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36
37 #include "BLI_math_inline.h"
38
39 #if BLI_MATH_DO_INLINE
40 #include "intern/math_geom_inline.c"
41 #endif
42
43 /********************************** Polygons *********************************/
44
45 void cent_tri_v3(float r[3], const float a[3], const float b[3], const float c[3]);
46 void cent_quad_v3(float r[3], const float a[3], const float b[3], const float c[3], const float d[3]);
47
48 float normal_tri_v3(float r[3], const float a[3], const float b[3], const float c[3]);
49 float normal_quad_v3(float r[3], const float a[3], const float b[3], const float c[3], const float d[3]);
50
51 float area_tri_v2(const float a[2], const float b[2], const float c[2]);
52 float area_tri_signed_v2(const float v1[2], const float v2[2], const float v3[2]);
53 float area_tri_v3(const float a[3], const float b[3], const float c[3]);
54 float area_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]);
55 float area_poly_v3(int nr, float verts[][3], const float normal[3]);
56 float area_poly_v2(int nr, float verts[][2]);
57
58 int is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
59 int is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]);
60
61 /********************************* Distance **********************************/
62
63 float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
64 float dist_squared_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
65 float         dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
66 void closest_to_line_segment_v2(float closest[2], const float p[2], const float l1[2], const float l2[2]);
67
68 float dist_to_plane_normalized_v3(const float p[3], const float plane_co[3], const float plane_no_unit[3]);
69 float dist_to_plane_v3(const float p[3], const float plane_co[3], const float plane_no[3]);
70 float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]);
71 float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3]);
72 float closest_to_line_v3(float r[3], const float p[3], const float l1[3], const float l2[3]);
73 float closest_to_line_v2(float r[2], const float p[2], const float l1[2], const float l2[2]);
74 void closest_to_line_segment_v3(float r[3], const float p[3], const float l1[3], const float l2[3]);
75 void closest_to_plane_v3(float r[3], const float plane_co[3], const float plane_no_unit[3], const float pt[3]);
76
77 /* Set 'r' to the point in triangle (t1, t2, t3) closest to point 'p' */
78 void closest_on_tri_to_point_v3(float r[3], const float p[3], const float t1[3], const float t2[3], const float t3[3]);
79
80
81 float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3]);
82 float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2]);
83 void limit_dist_v3(float v1[3], float v2[3], const float dist);
84
85 /******************************* Intersection ********************************/
86
87 /* TODO int return value consistency */
88
89 /* line-line */
90 #define ISECT_LINE_LINE_COLINEAR    -1
91 #define ISECT_LINE_LINE_NONE         0
92 #define ISECT_LINE_LINE_EXACT        1
93 #define ISECT_LINE_LINE_CROSS        2
94
95 int isect_line_line_v2_point(const float v1[2], const float v2[2], const float v3[2], const float v4[2], float vi[2]);
96 int isect_line_line_v2(const float a1[2], const float a2[2], const float b1[2], const float b2[2]);
97 int isect_line_line_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]);
98 int isect_line_sphere_v3(const float l1[3], const float l2[3], const float sp[3], const float r, float r_p1[3], float r_p2[3]);
99 int isect_line_sphere_v2(const float l1[2], const float l2[2], const float sp[2], const float r, float r_p1[2], float r_p2[2]);
100 int isect_seg_seg_v2_point(const float v1[2], const float v2[2], const float v3[2], const float v4[2], float vi[2]);
101 int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]);
102
103 int isect_line_line_v3(const float v1[3], const float v2[3],
104                        const float v3[3], const float v4[3],
105                        float i1[3], float i2[3]);
106 int isect_line_line_strict_v3(const float v1[3], const float v2[3],
107                               const float v3[3], const float v4[3],
108                               float vi[3], float *r_lambda);
109
110 int isect_ray_plane_v3(const float p1[3], const float d[3],
111                        const float v0[3], const float v1[3], const float v2[3],
112                        float *r_lambda, const int clip);
113
114 int isect_line_plane_v3(float out[3], const float l1[3], const float l2[3],
115                         const float plane_co[3], const float plane_no[3], const short no_flip);
116
117 void isect_plane_plane_v3(float r_isect_co[3], float r_isect_no[3],
118                           const float plane_a_co[3], const float plane_a_no[3],
119                           const float plane_b_co[3], const float plane_b_no[3]);
120
121 /* line/ray triangle */
122 int isect_line_tri_v3(const float p1[3], const float p2[3],
123                       const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]);
124 int isect_ray_tri_v3(const float p1[3], const float d[3],
125                      const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]);
126 int isect_ray_tri_threshold_v3(const float p1[3], const float d[3],
127                                const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], const float threshold);
128 int isect_ray_tri_epsilon_v3(const float p1[3], const float d[3],
129                              const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], const float epsilon);
130
131 /* point in polygon */
132 int isect_point_quad_v2(const float p[2], const float a[2], const float b[2], const float c[2], const float d[2]);
133
134 int isect_point_tri_v2(const float v1[2], const float v2[2], const float v3[2], const float pt[2]);
135 int isect_point_tri_v2_cw(const float pt[2], const float v1[2], const float v2[2], const float v3[2]);
136 int isect_point_tri_v2_int(const int x1, const int y1, const int x2, const int y2, const int a, const int b);
137 int isect_point_tri_prism_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3]);
138
139 void isect_point_quad_uv_v2(const float v0[2], const float v1[2], const float v2[2], const float v3[2],
140                             const float pt[2], float r_uv[2]);
141 void isect_point_face_uv_v2(const int isquad, const float v0[2], const float v1[2], const float v2[2],
142                             const float v3[2], const float pt[2], float r_uv[2]);
143
144 /* axis-aligned bounding box */
145 int isect_aabb_aabb_v3(const float min1[3], const float max1[3], const float min2[3], const float max2[3]);
146
147 typedef struct {
148         float ray_start[3];
149         float ray_inv_dir[3];
150         int sign[3];
151 } IsectRayAABBData;
152
153 void isect_ray_aabb_initialize(IsectRayAABBData *data, const float ray_start[3], const float ray_direction[3]);
154 int isect_ray_aabb(const IsectRayAABBData *data, const float bb_min[3], const float bb_max[3], float *tmin);
155
156 /* other */
157 int isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const float radius,
158                                  const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float ipoint[3]);
159
160 int isect_axial_line_tri_v3(const int axis, const float co1[3], const float co2[3],
161                             const float v0[3], const float v1[3], const float v2[3], float *r_lambda);
162
163 int clip_line_plane(float p1[3], float p2[3], const float plane[4]);
164
165 void plot_line_v2v2i(const int p1[2], const int p2[2], int (*callback)(int, int, void *), void *userData);
166
167 /****************************** Interpolation ********************************/
168
169 /* tri or quad, d can be NULL */
170 void interp_weights_face_v3(float w[4],
171                             const float a[3], const float b[3], const float c[3], const float d[3], const float p[3]);
172 void interp_weights_poly_v3(float w[], float v[][3], const int n, const float co[3]);
173 void interp_weights_poly_v2(float w[], float v[][2], const int n, const float co[2]);
174
175 void interp_cubic_v3(float x[3], float v[3],
176                      const float x1[3], const float v1[3], const float x2[3], const float v2[3], const float t);
177
178 int interp_sparse_array(float *array, const int list_size, const float invalid);
179
180 void barycentric_transform(float pt_tar[3], float const pt_src[3],
181                            const float tri_tar_p1[3], const float tri_tar_p2[3], const float tri_tar_p3[3],
182                            const float tri_src_p1[3], const float tri_src_p2[3], const float tri_src_p3[3]);
183
184 void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2],
185                             const float co[2], float w[3]);
186 void barycentric_weights_v2_quad(const float v1[2], const float v2[2], const float v3[2], const float v4[2],
187                                  const float co[2], float w[4]);
188
189 int barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]);
190 int barycentric_inside_triangle_v2(const float w[3]);
191
192 void resolve_tri_uv(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2]);
193 void resolve_quad_uv(float uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2]);
194
195 /* use to find the point of a UV on a face */
196 void interp_bilinear_quad_v3(float data[4][3], float u, float v, float res[3]);
197 void interp_barycentric_tri_v3(float data[3][3], float u, float v, float res[3]);
198
199 /***************************** View & Projection *****************************/
200
201 void lookat_m4(float mat[4][4], float vx, float vy, 
202                float vz, float px, float py, float pz, float twist);
203 void polarview_m4(float mat[4][4], float dist, float azimuth,
204                   float incidence, float twist);
205
206 void perspective_m4(float mat[4][4], const float left, const float right,
207                     const float bottom, const float top, const float nearClip, const float farClip);
208 void orthographic_m4(float mat[4][4], const float left, const float right,
209                      const float bottom, const float top, const float nearClip, const float farClip);
210 void window_translate_m4(float winmat[4][4], float perspmat[4][4],
211                          const float x, const float y);
212
213 int box_clip_bounds_m4(float boundbox[2][3],
214                        const float bounds[4], float winmat[4][4]);
215 void box_minmax_bounds_m4(float min[3], float max[3],
216                           float boundbox[2][3], float mat[4][4]);
217
218 /********************************** Mapping **********************************/
219
220 void map_to_tube(float *r_u, float *r_v, const float x, const float y, const float z);
221 void map_to_sphere(float *r_u, float *r_v, const float x, const float y, const float z);
222
223 /********************************** Normals **********************************/
224
225 void accumulate_vertex_normals(float n1[3], float n2[3], float n3[3],
226                                float n4[3], const float f_no[3], const float co1[3], const float co2[3],
227                                const float co3[3], const float co4[3]);
228
229 void accumulate_vertex_normals_poly(float **vertnos, float polyno[3],
230                                     float **vertcos, float vdiffs[][3], int nverts);
231
232 /********************************* Tangents **********************************/
233
234 void tangent_from_uv(float uv1[2], float uv2[2], float uv3[2],
235                      float co1[3], float co2[3], float co3[3], float n[3], float tang[3]);
236
237 /******************************** Vector Clouds ******************************/
238
239 void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight,
240                                float (*rpos)[3], float *rweight,
241                                float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3]);
242
243 /****************************** Spherical Harmonics *************************/
244
245 /* Uses 2nd order SH => 9 coefficients, stored in this order:
246  * 0 = (0, 0),
247  * 1 = (1, -1), 2 = (1, 0), 3 = (1, 1),
248  * 4 = (2, -2), 5 = (2, -1), 6 = (2, 0), 7 = (2, 1), 8 = (2, 2) */
249
250 MINLINE void zero_sh(float r[9]);
251 MINLINE void copy_sh_sh(float r[9], const float a[9]);
252 MINLINE void mul_sh_fl(float r[9], const float f);
253 MINLINE void add_sh_shsh(float r[9], const float a[9], const float b[9]);
254
255 MINLINE float eval_shv3(float r[9], const float v[3]);
256 MINLINE float diffuse_shv3(float r[9], const float v[3]);
257 MINLINE void vec_fac_to_sh(float r[9], const float v[3], const float f);
258 MINLINE void madd_sh_shfl(float r[9], const float sh[3], const float f);
259
260 /********************************* Form Factor *******************************/
261
262 float form_factor_hemi_poly(float p[3], float n[3],
263                             float v1[3], float v2[3], float v3[3], float v4[3]);
264
265 bool  axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3]);
266 void  axis_dominant_v3(int *r_axis_a, int *r_axis_b, const float axis[3]);
267 float axis_dominant_v3_max(int *r_axis_a, int *r_axis_b, const float axis[3])
268 #ifdef __GNUC__
269 __attribute__((warn_unused_result))
270 #endif
271 ;
272
273 MINLINE int max_axis_v3(const float vec[3]);
274 MINLINE int min_axis_v3(const float vec[3]);
275
276 MINLINE int poly_to_tri_count(const int poly_count, const int corner_count);
277
278 #ifdef __cplusplus
279 }
280 #endif
281
282 #endif /* __BLI_MATH_GEOM_H__ */
283