svn merge ^/trunk/blender -r43381:43392
[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 #ifdef BLI_MATH_INLINE_H
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
57 int is_quad_convex_v3(const float *v1, const float *v2, const float *v3, const float *v4);
58
59 /********************************* Distance **********************************/
60
61 float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2]);
62 float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2]);
63 void closest_to_line_segment_v2(float closest[2], const float p[2], const float l1[2], const float l2[2]);
64
65 float dist_to_plane_normalized_v3(const float p[3], const float plane_co[3], const float plane_no_unit[3]);
66 float dist_to_plane_v3(const float p[3], const float plane_co[3], const float plane_no[3]);
67 float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3]);
68 float closest_to_line_v3(float r[3], const float p[3], const float l1[3], const float l2[3]);
69 float closest_to_line_v2(float r[2], const float p[2], const float l1[2], const float l2[2]);
70 void  closest_to_line_segment_v3(float r[3], const float p[3], const float l1[3], const float l2[3]);
71 void  closest_to_plane_v3(float r[3], const float plane_co[3], const float plane_no_unit[3], const float pt[3]);
72
73
74 float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3]);
75 float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2]);
76
77 /******************************* Intersection ********************************/
78
79 /* TODO int return value consistency */
80
81 /* line-line */
82 #define ISECT_LINE_LINE_COLINEAR        -1
83 #define ISECT_LINE_LINE_NONE             0
84 #define ISECT_LINE_LINE_EXACT            1
85 #define ISECT_LINE_LINE_CROSS            2
86
87 int isect_line_line_v2(const float a1[2], const float a2[2], const float b1[2], const float b2[2]);
88 int isect_line_line_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]);
89 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]);
90 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]);
91 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]);
92
93 /* Returns the number of point of interests
94  * 0 - lines are colinear
95  * 1 - lines are coplanar, i1 is set to intersection
96  * 2 - i1 and i2 are the nearest points on line 1 (v1, v2) and line 2 (v3, v4) respectively 
97  * */
98
99 int isect_line_line_v3(const float v1[3], const float v2[3],
100                        const float v3[3], const float v4[3],
101                        float i1[3], float i2[3]);
102 int isect_line_line_strict_v3(const float v1[3], const float v2[3],
103                               const float v3[3], const float v4[3],
104                               float vi[3], float *r_lambda);
105
106 /*if clip is nonzero, will only return true if lambda is >= 0.0
107   (i.e. intersection point is along positive d)*/
108 int isect_ray_plane_v3(const float p1[3], const float d[3],
109                        const float v0[3], const float v1[3], const float v2[3],
110                        float *r_lambda, const int clip);
111
112 /**
113  * Intersect line/plane, optionally treat line as directional (like a ray) with the no_flip argument.
114  * @param out The intersection point.
115  * @param l1 The first point of the line.
116  * @param l2 The second point of the line.
117  * @param plane_co A point on the plane to intersect with.
118  * @param plane_no The direction of the plane (does not need to be normalized).
119  * @param no_flip When true, the intersection point will always be from l1 to l2, even if this is not on the plane.
120  */
121 int isect_line_plane_v3(float out[3], const float l1[3], const float l2[3],
122                         const float plane_co[3], const float plane_no[3], const short no_flip);
123
124 /**
125  * Intersect two planes, return a point on the intersection and a vector
126  * that runs on the direction of the intersection.
127  * Return error code is the same as 'isect_line_line_v3'.
128  * @param r_isect_co The resulting intersection point.
129  * @param r_isect_no The resulting vector of the intersection.
130  * @param plane_a_co The point on the first plane.
131  * @param plane_a_no The normal of the first plane.
132  * @param plane_b_co The point on the second plane.
133  * @param plane_b_no The normal of the second plane.
134  */
135 void isect_plane_plane_v3(float r_isect_co[3], float r_isect_no[3],
136                           const float plane_a_co[3], const float plane_a_no[3],
137                           const float plane_b_co[3], const float plane_b_no[3]);
138
139 /* line/ray triangle */
140 int isect_line_tri_v3(const float p1[3], const float p2[3],
141         const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]);
142 int isect_ray_tri_v3(const float p1[3], const float d[3],
143         const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2]);
144 int isect_ray_tri_threshold_v3(const float p1[3], const float d[3],
145         const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], const float threshold);
146 int isect_ray_tri_epsilon_v3(const float p1[3], const float d[3],
147         const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], const float epsilon);
148
149 /* point in polygon */
150 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]);
151
152 int isect_point_tri_v2(const float v1[2], const float v2[2], const float v3[2], const float pt[2]);
153 int isect_point_tri_v2_int(const int x1, const int y1, const int x2, const int y2, const int a, const int b);
154 int isect_point_tri_prism_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3]);
155
156 void isect_point_quad_uv_v2(const float v0[2], const float v1[2], const float v2[2], const float v3[2],
157                             const float pt[2], float r_uv[2]);
158 void isect_point_face_uv_v2(const int isquad, const float v0[2], const float v1[2], const float v2[2],
159                             const float v3[2], const float pt[2], float r_uv[2]);
160
161 /* other */
162 int isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], const float radius,
163         const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float ipoint[3]);
164
165 int isect_axial_line_tri_v3(const int axis, const float co1[3], const float co2[3],
166         const float v0[3], const float v1[3], const float v2[3], float *r_lambda);
167
168 int isect_aabb_aabb_v3(const float min1[3], const float max1[3], const float min2[3], const float max2[3]);
169
170 int clip_line_plane(float p1[3], float p2[3], const float plane[4]);
171
172 void plot_line_v2v2i(const int p1[2], const int p2[2], int (*callback)(int, int, void *), void *userData);
173
174 /****************************** Interpolation ********************************/
175
176 /* tri or quad, d can be NULL */
177 void interp_weights_face_v3(float w[4],
178         const float a[3], const float b[3], const float c[3], const float d[3], const float p[3]);
179 void interp_weights_poly_v3(float w[], float v[][3], const int n, const float p[3]);
180
181 void interp_cubic_v3(float x[3], float v[3],
182         const float x1[3], const float v1[3], const float x2[3], const float v2[3], const float t);
183
184 int interp_sparse_array(float *array, const int list_size, const float invalid);
185
186 void barycentric_transform(float pt_tar[3], float const pt_src[3],
187         const float tri_tar_p1[3], const float tri_tar_p2[3], const float tri_tar_p3[3],
188         const float tri_src_p1[3], const float tri_src_p2[3], const float tri_src_p3[3]);
189
190 void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2],
191         const float co[2], float w[3]);
192
193 void resolve_tri_uv(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2]);
194 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]);
195
196 /***************************** View & Projection *****************************/
197
198 void lookat_m4(float mat[4][4], float vx, float vy, 
199         float vz, float px, float py, float pz, float twist);
200 void polarview_m4(float mat[4][4], float dist, float azimuth,
201         float incidence, float twist);
202
203 void perspective_m4(float mat[4][4], const float left, const float right,
204         const float bottom, const float top, const float nearClip, const float farClip);
205 void orthographic_m4(float mat[4][4], const float left, const float right,
206         const float bottom, const float top, const float nearClip, const float farClip);
207 void window_translate_m4(float winmat[][4], float perspmat[][4],
208         const float x, const float y);
209
210 int box_clip_bounds_m4(float boundbox[2][3],
211         const float bounds[4], float winmat[4][4]);
212 void box_minmax_bounds_m4(float min[3], float max[3],
213         float boundbox[2][3], float mat[4][4]);
214
215 /********************************** Mapping **********************************/
216
217 void map_to_tube(float *u, float *v, const float x, const float y, const float z);
218 void map_to_sphere(float *u, float *v, const float x, const float y, const float z);
219
220 /********************************** Normals **********************************/
221
222 void accumulate_vertex_normals(float n1[3], float n2[3], float n3[3],
223         float n4[3], const float f_no[3], const float co1[3], const float co2[3],
224         const float co3[3], const float co4[3]);
225
226 void accumulate_vertex_normals_poly(float **vertnos, float polyno[3],
227         float **vertcos, float vdiffs[][3], int nverts);
228
229 /********************************* Tangents **********************************/
230
231 typedef struct VertexTangent {
232         struct VertexTangent *next;
233         float tang[3], uv[2];
234 } VertexTangent;
235
236 float *find_vertex_tangent(VertexTangent *vtang, const float uv[2]);
237 void sum_or_add_vertex_tangent(void *arena, VertexTangent **vtang,
238         const float tang[3], const float uv[2]);
239 void tangent_from_uv(float uv1[2], float uv2[2], float uv3[2],
240         float co1[3], float co2[3], float co3[3], float n[3], float tang[3]);
241
242 /******************************** Vector Clouds ******************************/
243
244 void vcloud_estimate_transform(int list_size, float (*pos)[3], float *weight,
245         float (*rpos)[3], float *rweight,
246         float lloc[3],float rloc[3],float lrot[3][3],float lscale[3][3]);
247
248 /****************************** Spherical Harmonics *************************/
249
250 /* Uses 2nd order SH => 9 coefficients, stored in this order:
251    0 = (0,0),
252    1 = (1,-1), 2 = (1,0), 3 = (1,1),
253    4 = (2,-2), 5 = (2,-1), 6 = (2,0), 7 = (2,1), 8 = (2,2) */
254
255 MINLINE void zero_sh(float r[9]);
256 MINLINE void copy_sh_sh(float r[9], const float a[9]);
257 MINLINE void mul_sh_fl(float r[9], const float f);
258 MINLINE void add_sh_shsh(float r[9], const float a[9], const float b[9]);
259
260 MINLINE float eval_shv3(float r[9], const float v[3]);
261 MINLINE float diffuse_shv3(float r[9], const float v[3]);
262 MINLINE void vec_fac_to_sh(float r[9], const float v[3], const float f);
263 MINLINE void madd_sh_shfl(float r[9], const float sh[3], const float f);
264
265 /********************************* Form Factor *******************************/
266
267 float form_factor_hemi_poly(float p[3], float n[3],
268         float v1[3], float v2[3], float v3[3], float v4[3]);
269
270 void axis_dominant_v3(int *axis_a, int *axis_b, const float axis[3]);
271
272 #ifdef __cplusplus
273 }
274 #endif
275
276 #endif /* BLI_MATH_GEOM_H */
277