Merge branch 'blender-v2.81-release'
[blender.git] / source / blender / blenlib / BLI_math_geom.h
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  *
19  * The Original Code is: some of this file.
20  *
21  * */
22
23 #ifndef __BLI_MATH_GEOM_H__
24 #define __BLI_MATH_GEOM_H__
25
26 /** \file
27  * \ingroup bli
28  */
29
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33
34 #include "BLI_compiler_attrs.h"
35 #include "BLI_math_inline.h"
36
37 #ifdef BLI_MATH_GCC_WARN_PRAGMA
38 #  pragma GCC diagnostic push
39 #  pragma GCC diagnostic ignored "-Wredundant-decls"
40 #endif
41
42 /********************************** Polygons *********************************/
43
44 float normal_tri_v3(float r[3], const float a[3], const float b[3], const float c[3]);
45 float normal_quad_v3(
46     float r[3], const float a[3], const float b[3], const float c[3], const float d[3]);
47 float normal_poly_v3(float r[3], const float verts[][3], unsigned int nr);
48
49 MINLINE float area_tri_v2(const float a[2], const float b[2], const float c[2]);
50 MINLINE float area_squared_tri_v2(const float a[2], const float b[2], const float c[2]);
51 MINLINE float area_tri_signed_v2(const float v1[2], const float v2[2], const float v3[2]);
52 float area_tri_v3(const float a[3], const float b[3], const float c[3]);
53 float area_squared_tri_v3(const float a[3], const float b[3], const float c[3]);
54 float area_tri_signed_v3(const float v1[3],
55                          const float v2[3],
56                          const float v3[3],
57                          const float normal[3]);
58 float area_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]);
59 float area_squared_quad_v3(const float a[3], const float b[3], const float c[3], const float d[3]);
60 float area_poly_v3(const float verts[][3], unsigned int nr);
61 float area_poly_v2(const float verts[][2], unsigned int nr);
62 float area_squared_poly_v3(const float verts[][3], unsigned int nr);
63 float area_squared_poly_v2(const float verts[][2], unsigned int nr);
64 float area_poly_signed_v2(const float verts[][2], unsigned int nr);
65 float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3]);
66
67 void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3]);
68 MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2]);
69 void cross_poly_v3(float n[3], const float verts[][3], unsigned int nr);
70 float cross_poly_v2(const float verts[][2], unsigned int nr);
71
72 /********************************* Planes **********************************/
73
74 void plane_from_point_normal_v3(float r_plane[4],
75                                 const float plane_co[3],
76                                 const float plane_no[3]);
77 void plane_to_point_vector_v3(const float plane[4], float r_plane_co[3], float r_plane_no[3]);
78 void plane_to_point_vector_v3_normalized(const float plane[4],
79                                          float r_plane_co[3],
80                                          float r_plane_no[3]);
81
82 MINLINE float plane_point_side_v3(const float plane[4], const float co[3]);
83
84 /********************************* Volume **********************************/
85
86 float volume_tetrahedron_v3(const float v1[3],
87                             const float v2[3],
88                             const float v3[3],
89                             const float v4[3]);
90 float volume_tetrahedron_signed_v3(const float v1[3],
91                                    const float v2[3],
92                                    const float v3[3],
93                                    const float v4[3]);
94
95 bool is_edge_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
96 bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
97 bool is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]);
98 bool is_poly_convex_v2(const float verts[][2], unsigned int nr);
99 int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]);
100 bool is_quad_flip_v3_first_third_fast(const float v1[3],
101                                       const float v2[3],
102                                       const float v3[3],
103                                       const float v4[3]);
104
105 /********************************* Distance **********************************/
106
107 float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
108 float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
109 float dist_squared_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
110 float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
111
112 float dist_signed_squared_to_plane_v3(const float p[3], const float plane[4]);
113 float dist_squared_to_plane_v3(const float p[3], const float plane[4]);
114 float dist_signed_to_plane_v3(const float p[3], const float plane[4]);
115 float dist_to_plane_v3(const float p[3], const float plane[4]);
116
117 /* plane3 versions */
118 float dist_signed_squared_to_plane3_v3(const float p[3], const float plane[4]);
119 float dist_squared_to_plane3_v3(const float p[3], const float plane[4]);
120 float dist_signed_to_plane3_v3(const float p[3], const float plane[4]);
121 float dist_to_plane3_v3(const float p[3], const float plane[4]);
122
123 float dist_squared_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]);
124 float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]);
125 float dist_squared_to_line_v3(const float p[3], const float l1[3], const float l2[3]);
126 float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3]);
127 float dist_signed_squared_to_corner_v3v3v3(const float p[3],
128                                            const float v1[3],
129                                            const float v2[3],
130                                            const float v3[3],
131                                            const float axis_ref[3]);
132 float dist_squared_to_ray_v3_normalized(const float ray_origin[3],
133                                         const float ray_direction[3],
134                                         const float co[3]);
135 float dist_squared_ray_to_seg_v3(const float ray_origin[3],
136                                  const float ray_direction[3],
137                                  const float v0[3],
138                                  const float v1[3],
139                                  float r_point[3],
140                                  float *r_depth);
141
142 void aabb_get_near_far_from_plane(const float plane_no[3],
143                                   const float bbmin[3],
144                                   const float bbmax[3],
145                                   float bb_near[3],
146                                   float bb_afar[3]);
147
148 struct DistRayAABB_Precalc {
149   float ray_origin[3];
150   float ray_direction[3];
151   float ray_inv_dir[3];
152 };
153 void dist_squared_ray_to_aabb_v3_precalc(struct DistRayAABB_Precalc *neasrest_precalc,
154                                          const float ray_origin[3],
155                                          const float ray_direction[3]);
156 float dist_squared_ray_to_aabb_v3(const struct DistRayAABB_Precalc *data,
157                                   const float bb_min[3],
158                                   const float bb_max[3],
159                                   float r_point[3],
160                                   float *r_depth);
161 /* when there is no advantage to precalc. */
162 float dist_squared_ray_to_aabb_v3_simple(const float ray_origin[3],
163                                          const float ray_direction[3],
164                                          const float bb_min[3],
165                                          const float bb_max[3],
166                                          float r_point[3],
167                                          float *r_depth);
168
169 struct DistProjectedAABBPrecalc {
170   float ray_origin[3];
171   float ray_direction[3];
172   float ray_inv_dir[3];
173   float pmat[4][4];
174   float mval[2];
175 };
176 void dist_squared_to_projected_aabb_precalc(struct DistProjectedAABBPrecalc *precalc,
177                                             const float projmat[4][4],
178                                             const float winsize[2],
179                                             const float mval[2]);
180 float dist_squared_to_projected_aabb(struct DistProjectedAABBPrecalc *data,
181                                      const float bbmin[3],
182                                      const float bbmax[3],
183                                      bool r_axis_closest[3]);
184 float dist_squared_to_projected_aabb_simple(const float projmat[4][4],
185                                             const float winsize[2],
186                                             const float mval[2],
187                                             const float bbmin[3],
188                                             const float bbmax[3]);
189
190 float closest_to_line_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2]);
191 double closest_to_line_v2_db(double r_close[2],
192                              const double p[2],
193                              const double l1[2],
194                              const double l2[2]);
195 float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3]);
196 void closest_to_line_segment_v2(float r_close[2],
197                                 const float p[2],
198                                 const float l1[2],
199                                 const float l2[2]);
200 void closest_to_line_segment_v3(float r_close[3],
201                                 const float p[3],
202                                 const float l1[3],
203                                 const float l2[3]);
204 void closest_to_plane_normalized_v3(float r_close[3], const float plane[4], const float pt[3]);
205 void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[3]);
206 void closest_to_plane3_normalized_v3(float r_close[3], const float plane[3], const float pt[3]);
207 void closest_to_plane3_v3(float r_close[3], const float plane[3], const float pt[3]);
208
209 /* Set 'r' to the point in triangle (t1, t2, t3) closest to point 'p' */
210 void closest_on_tri_to_point_v3(
211     float r[3], const float p[3], const float t1[3], const float t2[3], const float t3[3]);
212
213 float ray_point_factor_v3_ex(const float p[3],
214                              const float ray_origin[3],
215                              const float ray_direction[3],
216                              const float epsilon,
217                              const float fallback);
218 float ray_point_factor_v3(const float p[3],
219                           const float ray_origin[3],
220                           const float ray_direction[3]);
221
222 float line_point_factor_v3_ex(const float p[3],
223                               const float l1[3],
224                               const float l2[3],
225                               const float epsilon,
226                               const float fallback);
227 float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3]);
228
229 float line_point_factor_v2_ex(const float p[2],
230                               const float l1[2],
231                               const float l2[2],
232                               const float epsilon,
233                               const float fallback);
234 float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2]);
235
236 float line_plane_factor_v3(const float plane_co[3],
237                            const float plane_no[3],
238                            const float l1[3],
239                            const float l2[3]);
240
241 void limit_dist_v3(float v1[3], float v2[3], const float dist);
242
243 /******************************* Intersection ********************************/
244
245 /* TODO int return value consistency */
246
247 /* line-line */
248 #define ISECT_LINE_LINE_COLINEAR -1
249 #define ISECT_LINE_LINE_NONE 0
250 #define ISECT_LINE_LINE_EXACT 1
251 #define ISECT_LINE_LINE_CROSS 2
252
253 int isect_seg_seg_v2(const float a1[2], const float a2[2], const float b1[2], const float b2[2]);
254 void isect_seg_seg_v3(const float a0[3],
255                       const float a1[3],
256                       const float b0[3],
257                       const float b1[3],
258                       float r_a[3],
259                       float r_b[3]);
260
261 int isect_seg_seg_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]);
262 int isect_seg_seg_v2_point_ex(const float v0[2],
263                               const float v1[2],
264                               const float v2[2],
265                               const float v3[2],
266                               const float endpoint_bias,
267                               float vi[2]);
268 int isect_seg_seg_v2_point(
269     const float v0[2], const float v1[2], const float v2[2], const float v3[2], float vi[2]);
270 bool isect_seg_seg_v2_simple(const float v1[2],
271                              const float v2[2],
272                              const float v3[2],
273                              const float v4[2]);
274 int isect_seg_seg_v2_lambda_mu_db(const double v1[2],
275                                   const double v2[2],
276                                   const double v3[2],
277                                   const double v4[2],
278                                   double *r_lambda,
279                                   double *r_mu);
280 int isect_line_sphere_v3(const float l1[3],
281                          const float l2[3],
282                          const float sp[3],
283                          const float r,
284                          float r_p1[3],
285                          float r_p2[3]);
286 int isect_line_sphere_v2(const float l1[2],
287                          const float l2[2],
288                          const float sp[2],
289                          const float r,
290                          float r_p1[2],
291                          float r_p2[2]);
292
293 int isect_line_line_v2_point(
294     const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2]);
295 int isect_line_line_epsilon_v3(const float v1[3],
296                                const float v2[3],
297                                const float v3[3],
298                                const float v4[3],
299                                float i1[3],
300                                float i2[3],
301                                const float epsilon);
302 int isect_line_line_v3(const float v1[3],
303                        const float v2[3],
304                        const float v3[3],
305                        const float v4[3],
306                        float r_i1[3],
307                        float r_i2[3]);
308 bool isect_line_line_strict_v3(const float v1[3],
309                                const float v2[3],
310                                const float v3[3],
311                                const float v4[3],
312                                float vi[3],
313                                float *r_lambda);
314 bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3],
315                               const float ray_direction_a[3],
316                               const float ray_origin_b[3],
317                               const float ray_direction_b[3],
318                               const float epsilon,
319                               float *r_lambda_a,
320                               float *r_lambda_b);
321 bool isect_ray_ray_v3(const float ray_origin_a[3],
322                       const float ray_direction_a[3],
323                       const float ray_origin_b[3],
324                       const float ray_direction_b[3],
325                       float *r_lambda_a,
326                       float *r_lambda_b);
327
328 bool isect_ray_plane_v3(const float ray_origin[3],
329                         const float ray_direction[3],
330                         const float plane[4],
331                         float *r_lambda,
332                         const bool clip);
333
334 bool isect_point_planes_v3(float (*planes)[4], int totplane, const float p[3]);
335 bool isect_point_planes_v3_negated(const float (*planes)[4], const int totplane, const float p[3]);
336
337 bool isect_line_plane_v3(float r_isect_co[3],
338                          const float l1[3],
339                          const float l2[3],
340                          const float plane_co[3],
341                          const float plane_no[3]) ATTR_WARN_UNUSED_RESULT;
342
343 bool isect_plane_plane_plane_v3(const float plane_a[4],
344                                 const float plane_b[4],
345                                 const float plane_c[4],
346                                 float r_isect_co[3]) ATTR_WARN_UNUSED_RESULT;
347 bool isect_plane_plane_v3(const float plane_a[4],
348                           const float plane_b[4],
349                           float r_isect_co[3],
350                           float r_isect_no[3]) ATTR_WARN_UNUSED_RESULT;
351
352 /* line/ray triangle */
353 bool isect_line_segment_tri_v3(const float p1[3],
354                                const float p2[3],
355                                const float v0[3],
356                                const float v1[3],
357                                const float v2[3],
358                                float *r_lambda,
359                                float r_uv[2]);
360 bool isect_line_segment_tri_epsilon_v3(const float p1[3],
361                                        const float p2[3],
362                                        const float v0[3],
363                                        const float v1[3],
364                                        const float v2[3],
365                                        float *r_lambda,
366                                        float r_uv[2],
367                                        const float epsilon);
368 bool isect_axial_line_segment_tri_v3(const int axis,
369                                      const float p1[3],
370                                      const float p2[3],
371                                      const float v0[3],
372                                      const float v1[3],
373                                      const float v2[3],
374                                      float *r_lambda);
375
376 bool isect_ray_tri_v3(const float ray_origin[3],
377                       const float ray_direction[3],
378                       const float v0[3],
379                       const float v1[3],
380                       const float v2[3],
381                       float *r_lambda,
382                       float r_uv[2]);
383 bool isect_ray_tri_threshold_v3(const float ray_origin[3],
384                                 const float ray_direction[3],
385                                 const float v0[3],
386                                 const float v1[3],
387                                 const float v2[3],
388                                 float *r_lambda,
389                                 float r_uv[2],
390                                 const float threshold);
391 bool isect_ray_tri_epsilon_v3(const float ray_origin[3],
392                               const float ray_direction[3],
393                               const float v0[3],
394                               const float v1[3],
395                               const float v2[3],
396                               float *r_lambda,
397                               float r_uv[2],
398                               const float epsilon);
399 bool isect_tri_tri_epsilon_v3(const float t_a0[3],
400                               const float t_a1[3],
401                               const float t_a2[3],
402                               const float t_b0[3],
403                               const float t_b1[3],
404                               const float t_b2[3],
405                               float r_i1[3],
406                               float r_i2[3],
407                               const float epsilon);
408
409 bool isect_tri_tri_v2(const float p1[2],
410                       const float q1[2],
411                       const float r1[2],
412                       const float p2[2],
413                       const float q2[2],
414                       const float r2[2]);
415
416 /* water-tight raycast (requires pre-calculation) */
417 struct IsectRayPrecalc {
418   /* Maximal dimension kz, and orthogonal dimensions. */
419   int kx, ky, kz;
420
421   /* Shear constants. */
422   float sx, sy, sz;
423 };
424
425 void isect_ray_tri_watertight_v3_precalc(struct IsectRayPrecalc *isect_precalc,
426                                          const float ray_direction[3]);
427 bool isect_ray_tri_watertight_v3(const float ray_origin[3],
428                                  const struct IsectRayPrecalc *isect_precalc,
429                                  const float v0[3],
430                                  const float v1[3],
431                                  const float v2[3],
432                                  float *r_dist,
433                                  float r_uv[2]);
434 /* slower version which calculates IsectRayPrecalc each time */
435 bool isect_ray_tri_watertight_v3_simple(const float ray_origin[3],
436                                         const float ray_direction[3],
437                                         const float v0[3],
438                                         const float v1[3],
439                                         const float v2[3],
440                                         float *r_lambda,
441                                         float r_uv[2]);
442
443 bool isect_ray_seg_v2(const float ray_origin[2],
444                       const float ray_direction[2],
445                       const float v0[2],
446                       const float v1[2],
447                       float *r_lambda,
448                       float *r_u);
449
450 bool isect_ray_seg_v3(const float ray_origin[3],
451                       const float ray_direction[3],
452                       const float v0[3],
453                       const float v1[3],
454                       float *r_lambda);
455
456 /* point in polygon */
457 bool isect_point_poly_v2(const float pt[2],
458                          const float verts[][2],
459                          const unsigned int nr,
460                          const bool use_holes);
461 bool isect_point_poly_v2_int(const int pt[2],
462                              const int verts[][2],
463                              const unsigned int nr,
464                              const bool use_holes);
465
466 int isect_point_quad_v2(
467     const float p[2], const float a[2], const float b[2], const float c[2], const float d[2]);
468
469 int isect_point_tri_v2(const float pt[2], const float v1[2], const float v2[2], const float v3[2]);
470 bool isect_point_tri_v2_cw(const float pt[2],
471                            const float v1[2],
472                            const float v2[2],
473                            const float v3[2]);
474 int isect_point_tri_v2_int(
475     const int x1, const int y1, const int x2, const int y2, const int a, const int b);
476 bool isect_point_tri_prism_v3(const float p[3],
477                               const float v1[3],
478                               const float v2[3],
479                               const float v3[3]);
480 bool isect_point_tri_v3(const float p[3],
481                         const float v1[3],
482                         const float v2[3],
483                         const float v3[3],
484                         float r_isect_co[3]);
485
486 /* axis-aligned bounding box */
487 bool isect_aabb_aabb_v3(const float min1[3],
488                         const float max1[3],
489                         const float min2[3],
490                         const float max2[3]);
491
492 struct IsectRayAABB_Precalc {
493   float ray_origin[3];
494   float ray_inv_dir[3];
495   int sign[3];
496 };
497
498 void isect_ray_aabb_v3_precalc(struct IsectRayAABB_Precalc *data,
499                                const float ray_origin[3],
500                                const float ray_direction[3]);
501 bool isect_ray_aabb_v3(const struct IsectRayAABB_Precalc *data,
502                        const float bb_min[3],
503                        const float bb_max[3],
504                        float *tmin);
505 bool isect_ray_aabb_v3_simple(const float orig[3],
506                               const float dir[3],
507                               const float bb_min[3],
508                               const float bb_max[3],
509                               float *tmin,
510                               float *tmax);
511
512 /* other */
513 #define ISECT_AABB_PLANE_BEHIND_ANY 0
514 #define ISECT_AABB_PLANE_CROSS_ANY 1
515 #define ISECT_AABB_PLANE_IN_FRONT_ALL 2
516
517 int isect_aabb_planes_v3(const float (*planes)[4],
518                          const int totplane,
519                          const float bbmin[3],
520                          const float bbmax[3]);
521
522 bool isect_sweeping_sphere_tri_v3(const float p1[3],
523                                   const float p2[3],
524                                   const float radius,
525                                   const float v0[3],
526                                   const float v1[3],
527                                   const float v2[3],
528                                   float *r_lambda,
529                                   float ipoint[3]);
530
531 bool clip_segment_v3_plane(
532     const float p1[3], const float p2[3], const float plane[4], float r_p1[3], float r_p2[3]);
533 bool clip_segment_v3_plane_n(const float p1[3],
534                              const float p2[3],
535                              const float plane_array[][4],
536                              const int plane_tot,
537                              float r_p1[3],
538                              float r_p2[3]);
539
540 bool point_in_slice_seg(float p[3], float l1[3], float l2[3]);
541
542 /****************************** Interpolation ********************************/
543 void interp_weights_tri_v3(
544     float w[3], const float a[3], const float b[3], const float c[3], const float p[3]);
545 void interp_weights_quad_v3(float w[4],
546                             const float a[3],
547                             const float b[3],
548                             const float c[3],
549                             const float d[3],
550                             const float p[3]);
551 void interp_weights_poly_v3(float w[], float v[][3], const int n, const float co[3]);
552 void interp_weights_poly_v2(float w[], float v[][2], const int n, const float co[2]);
553
554 void interp_cubic_v3(float x[3],
555                      float v[3],
556                      const float x1[3],
557                      const float v1[3],
558                      const float x2[3],
559                      const float v2[3],
560                      const float t);
561
562 int interp_sparse_array(float *array, const int list_size, const float invalid);
563
564 void transform_point_by_tri_v3(float pt_tar[3],
565                                float const pt_src[3],
566                                const float tri_tar_p1[3],
567                                const float tri_tar_p2[3],
568                                const float tri_tar_p3[3],
569                                const float tri_src_p1[3],
570                                const float tri_src_p2[3],
571                                const float tri_src_p3[3]);
572 void transform_point_by_seg_v3(float p_dst[3],
573                                const float p_src[3],
574                                const float l_dst_p1[3],
575                                const float l_dst_p2[3],
576                                const float l_src_p1[3],
577                                const float l_src_p2[3]);
578
579 void barycentric_weights_v2(
580     const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]);
581 void barycentric_weights_v2_clamped(
582     const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]);
583 void barycentric_weights_v2_persp(
584     const float v1[4], const float v2[4], const float v3[4], const float co[2], float w[3]);
585 void barycentric_weights_v2_quad(const float v1[2],
586                                  const float v2[2],
587                                  const float v3[2],
588                                  const float v4[2],
589                                  const float co[2],
590                                  float w[4]);
591
592 bool barycentric_coords_v2(
593     const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]);
594 int barycentric_inside_triangle_v2(const float w[3]);
595
596 void resolve_tri_uv_v2(
597     float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2]);
598 void resolve_tri_uv_v3(
599     float r_uv[2], const float st[3], const float st0[3], const float st1[3], const float st2[3]);
600 void resolve_quad_uv_v2(float r_uv[2],
601                         const float st[2],
602                         const float st0[2],
603                         const float st1[2],
604                         const float st2[2],
605                         const float st3[2]);
606 void resolve_quad_uv_v2_deriv(float r_uv[2],
607                               float r_deriv[2][2],
608                               const float st[2],
609                               const float st0[2],
610                               const float st1[2],
611                               const float st2[2],
612                               const float st3[2]);
613 float resolve_quad_u_v2(const float st[2],
614                         const float st0[2],
615                         const float st1[2],
616                         const float st2[2],
617                         const float st3[2]);
618
619 /* use to find the point of a UV on a face */
620 void interp_bilinear_quad_v3(float data[4][3], float u, float v, float res[3]);
621 void interp_barycentric_tri_v3(float data[3][3], float u, float v, float res[3]);
622
623 /***************************** View & Projection *****************************/
624
625 void lookat_m4(
626     float mat[4][4], float vx, float vy, float vz, float px, float py, float pz, float twist);
627 void polarview_m4(float mat[4][4], float dist, float azimuth, float incidence, float twist);
628
629 void perspective_m4(float mat[4][4],
630                     const float left,
631                     const float right,
632                     const float bottom,
633                     const float top,
634                     const float nearClip,
635                     const float farClip);
636 void orthographic_m4(float mat[4][4],
637                      const float left,
638                      const float right,
639                      const float bottom,
640                      const float top,
641                      const float nearClip,
642                      const float farClip);
643 void window_translate_m4(float winmat[4][4], float perspmat[4][4], const float x, const float y);
644
645 void planes_from_projmat(float mat[4][4],
646                          float left[4],
647                          float right[4],
648                          float top[4],
649                          float bottom[4],
650                          float front[4],
651                          float back[4]);
652
653 void projmat_dimensions(const float projmat[4][4],
654                         float *r_left,
655                         float *r_right,
656                         float *r_bottom,
657                         float *r_top,
658                         float *r_near,
659                         float *r_far);
660
661 void projmat_from_subregion(const float projmat[4][4],
662                             const int win_size[2],
663                             const int x_min,
664                             const int x_max,
665                             const int y_min,
666                             const int y_max,
667                             float r_projmat[4][4]);
668
669 int box_clip_bounds_m4(float boundbox[2][3], const float bounds[4], float winmat[4][4]);
670 void box_minmax_bounds_m4(float min[3], float max[3], float boundbox[2][3], float mat[4][4]);
671
672 /********************************** Mapping **********************************/
673
674 void map_to_tube(float *r_u, float *r_v, const float x, const float y, const float z);
675 void map_to_sphere(float *r_u, float *r_v, const float x, const float y, const float z);
676 void map_to_plane_v2_v3v3(float r_co[2], const float co[3], const float no[3]);
677 void map_to_plane_axis_angle_v2_v3v3fl(float r_co[2],
678                                        const float co[3],
679                                        const float axis[3],
680                                        const float angle);
681
682 /********************************** Normals **********************************/
683
684 void accumulate_vertex_normals_tri_v3(float n1[3],
685                                       float n2[3],
686                                       float n3[3],
687                                       const float f_no[3],
688                                       const float co1[3],
689                                       const float co2[3],
690                                       const float co3[3]);
691
692 void accumulate_vertex_normals_v3(float n1[3],
693                                   float n2[3],
694                                   float n3[3],
695                                   float n4[3],
696                                   const float f_no[3],
697                                   const float co1[3],
698                                   const float co2[3],
699                                   const float co3[3],
700                                   const float co4[3]);
701
702 void accumulate_vertex_normals_poly_v3(float **vertnos,
703                                        const float polyno[3],
704                                        const float **vertcos,
705                                        float vdiffs[][3],
706                                        const int nverts);
707
708 /********************************* Tangents **********************************/
709
710 void tangent_from_uv_v3(const float uv1[2],
711                         const float uv2[2],
712                         const float uv3[2],
713                         const float co1[3],
714                         const float co2[3],
715                         const float co3[3],
716                         const float n[3],
717                         float r_tang[3]);
718
719 /******************************** Vector Clouds ******************************/
720
721 void vcloud_estimate_transform_v3(const int list_size,
722                                   const float (*pos)[3],
723                                   const float *weight,
724                                   const float (*rpos)[3],
725                                   const float *rweight,
726                                   float lloc[3],
727                                   float rloc[3],
728                                   float lrot[3][3],
729                                   float lscale[3][3]);
730
731 /****************************** Spherical Harmonics *************************/
732
733 /* Uses 2nd order SH => 9 coefficients, stored in this order:
734  * 0 = (0, 0),
735  * 1 = (1, -1), 2 = (1, 0), 3 = (1, 1),
736  * 4 = (2, -2), 5 = (2, -1), 6 = (2, 0), 7 = (2, 1), 8 = (2, 2) */
737
738 MINLINE void zero_sh(float r[9]);
739 MINLINE void copy_sh_sh(float r[9], const float a[9]);
740 MINLINE void mul_sh_fl(float r[9], const float f);
741 MINLINE void add_sh_shsh(float r[9], const float a[9], const float b[9]);
742 MINLINE float dot_shsh(const float a[9], const float b[9]);
743
744 MINLINE float eval_shv3(float r[9], const float v[3]);
745 MINLINE float diffuse_shv3(float r[9], const float v[3]);
746 MINLINE void vec_fac_to_sh(float r[9], const float v[3], const float f);
747 MINLINE void madd_sh_shfl(float r[9], const float sh[3], const float f);
748
749 /********************************* Form Factor *******************************/
750
751 float form_factor_quad(const float p[3],
752                        const float n[3],
753                        const float q0[3],
754                        const float q1[3],
755                        const float q2[3],
756                        const float q3[3]);
757 bool form_factor_visible_quad(const float p[3],
758                               const float n[3],
759                               const float v0[3],
760                               const float v1[3],
761                               const float v2[3],
762                               float q0[3],
763                               float q1[3],
764                               float q2[3],
765                               float q3[3]);
766 float form_factor_hemi_poly(
767     float p[3], float n[3], float v1[3], float v2[3], float v3[3], float v4[3]);
768
769 void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3]);
770 void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3]);
771
772 MINLINE void axis_dominant_v3(int *r_axis_a, int *r_axis_b, const float axis[3]);
773 MINLINE float axis_dominant_v3_max(int *r_axis_a,
774                                    int *r_axis_b,
775                                    const float axis[3]) ATTR_WARN_UNUSED_RESULT;
776 MINLINE int axis_dominant_v3_single(const float vec[3]);
777 MINLINE int axis_dominant_v3_ortho_single(const float vec[3]);
778
779 MINLINE int max_axis_v3(const float vec[3]);
780 MINLINE int min_axis_v3(const float vec[3]);
781
782 MINLINE int poly_to_tri_count(const int poly_count, const int corner_count);
783
784 MINLINE float shell_angle_to_dist(const float angle);
785 MINLINE float shell_v3v3_normalized_to_dist(const float a[3], const float b[3]);
786 MINLINE float shell_v2v2_normalized_to_dist(const float a[2], const float b[2]);
787 MINLINE float shell_v3v3_mid_normalized_to_dist(const float a[3], const float b[3]);
788 MINLINE float shell_v2v2_mid_normalized_to_dist(const float a[2], const float b[2]);
789
790 /********************************* Cubic (Bezier) *******************************/
791
792 float cubic_tangent_factor_circle_v3(const float tan_l[3], const float tan_r[3]);
793
794 /**************************** Inline Definitions ******************************/
795
796 #if BLI_MATH_DO_INLINE
797 #  include "intern/math_geom_inline.c"
798 #endif
799
800 #ifdef BLI_MATH_GCC_WARN_PRAGMA
801 #  pragma GCC diagnostic pop
802 #endif
803
804 #ifdef __cplusplus
805 }
806 #endif
807
808 #endif /* __BLI_MATH_GEOM_H__ */