Merge branch 'blender2.7'
[blender.git] / source / blender / python / mathutils / mathutils_geometry.c
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
17 /** \file
18  * \ingroup pymathutils
19  */
20
21
22 #include <Python.h>
23
24 #include "mathutils.h"
25 #include "mathutils_geometry.h"
26
27 /* Used for PolyFill */
28 #ifndef MATH_STANDALONE /* define when building outside blender */
29 #  include "MEM_guardedalloc.h"
30 #  include "BLI_blenlib.h"
31 #  include "BLI_boxpack_2d.h"
32 #  include "BLI_convexhull_2d.h"
33 #  include "BKE_displist.h"
34 #  include "BKE_curve.h"
35 #endif
36
37 #include "BLI_math.h"
38 #include "BLI_utildefines.h"
39
40 #include "../generic/py_capi_utils.h"
41 #include "../generic/python_utildefines.h"
42
43 /*-------------------------DOC STRINGS ---------------------------*/
44 PyDoc_STRVAR(M_Geometry_doc,
45 "The Blender geometry module"
46 );
47
48 /* ---------------------------------INTERSECTION FUNCTIONS-------------------- */
49
50 PyDoc_STRVAR(M_Geometry_intersect_ray_tri_doc,
51 ".. function:: intersect_ray_tri(v1, v2, v3, ray, orig, clip=True)\n"
52 "\n"
53 "   Returns the intersection between a ray and a triangle, if possible, returns None otherwise.\n"
54 "\n"
55 "   :arg v1: Point1\n"
56 "   :type v1: :class:`mathutils.Vector`\n"
57 "   :arg v2: Point2\n"
58 "   :type v2: :class:`mathutils.Vector`\n"
59 "   :arg v3: Point3\n"
60 "   :type v3: :class:`mathutils.Vector`\n"
61 "   :arg ray: Direction of the projection\n"
62 "   :type ray: :class:`mathutils.Vector`\n"
63 "   :arg orig: Origin\n"
64 "   :type orig: :class:`mathutils.Vector`\n"
65 "   :arg clip: When False, don't restrict the intersection to the area of the triangle, use the infinite plane defined by the triangle.\n"
66 "   :type clip: boolean\n"
67 "   :return: The point of intersection or None if no intersection is found\n"
68 "   :rtype: :class:`mathutils.Vector` or None\n"
69 );
70 static PyObject *M_Geometry_intersect_ray_tri(PyObject *UNUSED(self), PyObject *args)
71 {
72         const char *error_prefix = "intersect_ray_tri";
73         PyObject *py_ray, *py_ray_off, *py_tri[3];
74         float dir[3], orig[3], tri[3][3], e1[3], e2[3], pvec[3], tvec[3], qvec[3];
75         float det, inv_det, u, v, t;
76         bool clip = true;
77         int i;
78
79         if (!PyArg_ParseTuple(
80                 args, "OOOOO|O&:intersect_ray_tri",
81                 UNPACK3_EX(&, py_tri, ),
82                 &py_ray, &py_ray_off,
83                 PyC_ParseBool, &clip))
84         {
85                 return NULL;
86         }
87
88         if (((mathutils_array_parse(dir, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_ray, error_prefix) != -1) &&
89              (mathutils_array_parse(orig, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_ray_off, error_prefix) != -1)) == 0)
90         {
91                 return NULL;
92         }
93
94         for (i = 0; i < ARRAY_SIZE(tri); i++) {
95                 if (mathutils_array_parse(tri[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_tri[i], error_prefix) == -1) {
96                         return NULL;
97                 }
98         }
99
100         normalize_v3(dir);
101
102         /* find vectors for two edges sharing v1 */
103         sub_v3_v3v3(e1, tri[1], tri[0]);
104         sub_v3_v3v3(e2, tri[2], tri[0]);
105
106         /* begin calculating determinant - also used to calculated U parameter */
107         cross_v3_v3v3(pvec, dir, e2);
108
109         /* if determinant is near zero, ray lies in plane of triangle */
110         det = dot_v3v3(e1, pvec);
111
112         if (det > -0.000001f && det < 0.000001f) {
113                 Py_RETURN_NONE;
114         }
115
116         inv_det = 1.0f / det;
117
118         /* calculate distance from v1 to ray origin */
119         sub_v3_v3v3(tvec, orig, tri[0]);
120
121         /* calculate U parameter and test bounds */
122         u = dot_v3v3(tvec, pvec) * inv_det;
123         if (clip && (u < 0.0f || u > 1.0f)) {
124                 Py_RETURN_NONE;
125         }
126
127         /* prepare to test the V parameter */
128         cross_v3_v3v3(qvec, tvec, e1);
129
130         /* calculate V parameter and test bounds */
131         v = dot_v3v3(dir, qvec) * inv_det;
132
133         if (clip && (v < 0.0f || u + v > 1.0f)) {
134                 Py_RETURN_NONE;
135         }
136
137         /* calculate t, ray intersects triangle */
138         t = dot_v3v3(e2, qvec) * inv_det;
139
140         /* ray hit behind */
141         if (t < 0.0f) {
142                 Py_RETURN_NONE;
143         }
144
145         mul_v3_fl(dir, t);
146         add_v3_v3v3(pvec, orig, dir);
147
148         return Vector_CreatePyObject(pvec, 3, NULL);
149 }
150
151 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
152
153 PyDoc_STRVAR(M_Geometry_intersect_line_line_doc,
154 ".. function:: intersect_line_line(v1, v2, v3, v4)\n"
155 "\n"
156 "   Returns a tuple with the points on each line respectively closest to the other.\n"
157 "\n"
158 "   :arg v1: First point of the first line\n"
159 "   :type v1: :class:`mathutils.Vector`\n"
160 "   :arg v2: Second point of the first line\n"
161 "   :type v2: :class:`mathutils.Vector`\n"
162 "   :arg v3: First point of the second line\n"
163 "   :type v3: :class:`mathutils.Vector`\n"
164 "   :arg v4: Second point of the second line\n"
165 "   :type v4: :class:`mathutils.Vector`\n"
166 "   :rtype: tuple of :class:`mathutils.Vector`'s\n"
167 );
168 static PyObject *M_Geometry_intersect_line_line(PyObject *UNUSED(self), PyObject *args)
169 {
170         const char *error_prefix = "intersect_line_line";
171         PyObject *tuple;
172         PyObject *py_lines[4];
173         float lines[4][3], i1[3], i2[3];
174         int len;
175         int result;
176
177         if (!PyArg_ParseTuple(
178                 args, "OOOO:intersect_line_line",
179                 UNPACK4_EX(&, py_lines, )))
180         {
181                 return NULL;
182         }
183
184         if ((((len = mathutils_array_parse(lines[0], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_lines[0], error_prefix)) != -1) &&
185              (mathutils_array_parse(lines[1], len, len | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_lines[1], error_prefix) != -1) &&
186              (mathutils_array_parse(lines[2], len, len | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_lines[2], error_prefix) != -1) &&
187              (mathutils_array_parse(lines[3], len, len | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_lines[3], error_prefix) != -1)) == 0)
188         {
189                 return NULL;
190         }
191
192         result = isect_line_line_v3(UNPACK4(lines), i1, i2);
193         /* The return-code isnt exposed,
194          * this way we can check know how close the lines are. */
195         if (result == 1) {
196                 closest_to_line_v3(i2, i1, lines[2], lines[3]);
197         }
198
199         if (result == 0) {
200                 /* collinear */
201                 Py_RETURN_NONE;
202         }
203         else {
204                 tuple = PyTuple_New(2);
205                 PyTuple_SET_ITEMS(tuple,
206                         Vector_CreatePyObject(i1, len, NULL),
207                         Vector_CreatePyObject(i2, len, NULL));
208                 return tuple;
209         }
210 }
211
212 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
213
214 PyDoc_STRVAR(M_Geometry_intersect_sphere_sphere_2d_doc,
215 ".. function:: intersect_sphere_sphere_2d(p_a, radius_a, p_b, radius_b)\n"
216 "\n"
217 "   Returns 2 points on between intersecting circles.\n"
218 "\n"
219 "   :arg p_a: Center of the first circle\n"
220 "   :type p_a: :class:`mathutils.Vector`\n"
221 "   :arg radius_a: Radius of the first circle\n"
222 "   :type radius_a: float\n"
223 "   :arg p_b: Center of the second circle\n"
224 "   :type p_b: :class:`mathutils.Vector`\n"
225 "   :arg radius_b: Radius of the second circle\n"
226 "   :type radius_b: float\n"
227 "   :rtype: tuple of :class:`mathutils.Vector`'s or None when there is no intersection\n"
228 );
229 static PyObject *M_Geometry_intersect_sphere_sphere_2d(PyObject *UNUSED(self), PyObject *args)
230 {
231         const char *error_prefix = "intersect_sphere_sphere_2d";
232         PyObject *ret;
233         PyObject *py_v_a, *py_v_b;
234         float v_a[2], v_b[2];
235         float rad_a, rad_b;
236         float v_ab[2];
237         float dist;
238
239         if (!PyArg_ParseTuple(
240                 args, "OfOf:intersect_sphere_sphere_2d",
241                 &py_v_a, &rad_a,
242                 &py_v_b, &rad_b))
243         {
244                 return NULL;
245         }
246
247         if (((mathutils_array_parse(v_a, 2, 2, py_v_a, error_prefix) != -1) &&
248              (mathutils_array_parse(v_b, 2, 2, py_v_b, error_prefix) != -1)) == 0)
249         {
250                 return NULL;
251         }
252
253         ret = PyTuple_New(2);
254
255         sub_v2_v2v2(v_ab, v_b, v_a);
256         dist = len_v2(v_ab);
257
258         if (/* out of range */
259             (dist > rad_a + rad_b) ||
260             /* fully-contained in the other */
261             (dist < fabsf(rad_a - rad_b)) ||
262             /* co-incident */
263             (dist < FLT_EPSILON))
264         {
265                 /* out of range */
266                 PyTuple_SET_ITEMS(ret,
267                         Py_INCREF_RET(Py_None),
268                         Py_INCREF_RET(Py_None));
269         }
270         else {
271                 const float dist_delta = ((rad_a * rad_a) - (rad_b * rad_b) + (dist * dist)) / (2.0f * dist);
272                 const float h = powf(fabsf((rad_a * rad_a) - (dist_delta * dist_delta)), 0.5f);
273                 float i_cent[2];
274                 float i1[2], i2[2];
275
276                 i_cent[0] = v_a[0] + ((v_ab[0] * dist_delta) / dist);
277                 i_cent[1] = v_a[1] + ((v_ab[1] * dist_delta) / dist);
278
279                 i1[0] = i_cent[0] + h * v_ab[1] / dist;
280                 i1[1] = i_cent[1] - h * v_ab[0] / dist;
281
282                 i2[0] = i_cent[0] - h * v_ab[1] / dist;
283                 i2[1] = i_cent[1] + h * v_ab[0] / dist;
284
285                 PyTuple_SET_ITEMS(ret,
286                         Vector_CreatePyObject(i1, 2, NULL),
287                         Vector_CreatePyObject(i2, 2, NULL));
288         }
289
290         return ret;
291 }
292
293 PyDoc_STRVAR(M_Geometry_normal_doc,
294 ".. function:: normal(vectors)\n"
295 "\n"
296 "   Returns the normal of a 3D polygon.\n"
297 "\n"
298 "   :arg vectors: Vectors to calculate normals with\n"
299 "   :type vectors: sequence of 3 or more 3d vector\n"
300 "   :rtype: :class:`mathutils.Vector`\n"
301 );
302 static PyObject *M_Geometry_normal(PyObject *UNUSED(self), PyObject *args)
303 {
304         float (*coords)[3];
305         int coords_len;
306         float n[3];
307         PyObject *ret = NULL;
308
309         /* use */
310         if (PyTuple_GET_SIZE(args) == 1) {
311                 args = PyTuple_GET_ITEM(args, 0);
312         }
313
314         if ((coords_len = mathutils_array_parse_alloc_v((float **)&coords, 3 | MU_ARRAY_SPILL, args, "normal")) == -1) {
315                 return NULL;
316         }
317
318         if (coords_len < 3) {
319                 PyErr_SetString(PyExc_ValueError,
320                                 "Expected 3 or more vectors");
321                 goto finally;
322         }
323
324         normal_poly_v3(n, (const float (*)[3])coords, coords_len);
325         ret = Vector_CreatePyObject(n, 3, NULL);
326
327 finally:
328         PyMem_Free(coords);
329         return ret;
330 }
331
332 /* --------------------------------- AREA FUNCTIONS-------------------- */
333
334 PyDoc_STRVAR(M_Geometry_area_tri_doc,
335 ".. function:: area_tri(v1, v2, v3)\n"
336 "\n"
337 "   Returns the area size of the 2D or 3D triangle defined.\n"
338 "\n"
339 "   :arg v1: Point1\n"
340 "   :type v1: :class:`mathutils.Vector`\n"
341 "   :arg v2: Point2\n"
342 "   :type v2: :class:`mathutils.Vector`\n"
343 "   :arg v3: Point3\n"
344 "   :type v3: :class:`mathutils.Vector`\n"
345 "   :rtype: float\n"
346 );
347 static PyObject *M_Geometry_area_tri(PyObject *UNUSED(self), PyObject *args)
348 {
349         const char *error_prefix = "area_tri";
350         PyObject *py_tri[3];
351         float tri[3][3];
352         int len;
353
354         if (!PyArg_ParseTuple(
355                 args, "OOO:area_tri",
356                 UNPACK3_EX(&, py_tri, )))
357         {
358                 return NULL;
359         }
360
361         if ((((len = mathutils_array_parse(tri[0], 2, 3, py_tri[0], error_prefix)) != -1) &&
362              (mathutils_array_parse(tri[1], len, len, py_tri[1], error_prefix) != -1) &&
363              (mathutils_array_parse(tri[2], len, len, py_tri[2], error_prefix) != -1)) == 0)
364         {
365                 return NULL;
366         }
367
368         return PyFloat_FromDouble((len == 3 ? area_tri_v3 : area_tri_v2)(UNPACK3(tri)));
369 }
370
371 PyDoc_STRVAR(M_Geometry_volume_tetrahedron_doc,
372 ".. function:: volume_tetrahedron(v1, v2, v3, v4)\n"
373 "\n"
374 "   Return the volume formed by a tetrahedron (points can be in any order).\n"
375 "\n"
376 "   :arg v1: Point1\n"
377 "   :type v1: :class:`mathutils.Vector`\n"
378 "   :arg v2: Point2\n"
379 "   :type v2: :class:`mathutils.Vector`\n"
380 "   :arg v3: Point3\n"
381 "   :type v3: :class:`mathutils.Vector`\n"
382 "   :arg v4: Point4\n"
383 "   :type v4: :class:`mathutils.Vector`\n"
384 "   :rtype: float\n"
385 );
386 static PyObject *M_Geometry_volume_tetrahedron(PyObject *UNUSED(self), PyObject *args)
387 {
388         const char *error_prefix = "volume_tetrahedron";
389         PyObject *py_tet[4];
390         float tet[4][3];
391         int i;
392
393         if (!PyArg_ParseTuple(
394                 args, "OOOO:volume_tetrahedron",
395                 UNPACK4_EX(&, py_tet, )))
396         {
397                 return NULL;
398         }
399
400         for (i = 0; i < ARRAY_SIZE(tet); i++) {
401                 if (mathutils_array_parse(tet[i], 3, 3 | MU_ARRAY_SPILL, py_tet[i], error_prefix) == -1) {
402                         return NULL;
403                 }
404         }
405
406         return PyFloat_FromDouble(volume_tetrahedron_v3(UNPACK4(tet)));
407 }
408
409 PyDoc_STRVAR(M_Geometry_intersect_line_line_2d_doc,
410 ".. function:: intersect_line_line_2d(lineA_p1, lineA_p2, lineB_p1, lineB_p2)\n"
411 "\n"
412 "   Takes 2 segments (defined by 4 vectors) and returns a vector for their point of intersection or None.\n"
413 "\n"
414 "   .. warning:: Despite its name, this function works on segments, and not on lines.\n"
415 "\n"
416 "   :arg lineA_p1: First point of the first line\n"
417 "   :type lineA_p1: :class:`mathutils.Vector`\n"
418 "   :arg lineA_p2: Second point of the first line\n"
419 "   :type lineA_p2: :class:`mathutils.Vector`\n"
420 "   :arg lineB_p1: First point of the second line\n"
421 "   :type lineB_p1: :class:`mathutils.Vector`\n"
422 "   :arg lineB_p2: Second point of the second line\n"
423 "   :type lineB_p2: :class:`mathutils.Vector`\n"
424 "   :return: The point of intersection or None when not found\n"
425 "   :rtype: :class:`mathutils.Vector` or None\n"
426 );
427 static PyObject *M_Geometry_intersect_line_line_2d(PyObject *UNUSED(self), PyObject *args)
428 {
429         const char *error_prefix = "intersect_line_line_2d";
430         PyObject *py_lines[4];
431         float lines[4][2];
432         float vi[2];
433         int i;
434
435         if (!PyArg_ParseTuple(
436                 args, "OOOO:intersect_line_line_2d",
437                 UNPACK4_EX(&, py_lines, )))
438         {
439                 return NULL;
440         }
441
442         for (i = 0; i < ARRAY_SIZE(lines); i++) {
443                 if (mathutils_array_parse(lines[i], 2, 2 | MU_ARRAY_SPILL, py_lines[i], error_prefix) == -1) {
444                         return NULL;
445                 }
446         }
447
448         if (isect_seg_seg_v2_point(UNPACK4(lines), vi) == 1) {
449                 return Vector_CreatePyObject(vi, 2, NULL);
450         }
451         else {
452                 Py_RETURN_NONE;
453         }
454 }
455
456
457 PyDoc_STRVAR(M_Geometry_intersect_line_plane_doc,
458 ".. function:: intersect_line_plane(line_a, line_b, plane_co, plane_no, no_flip=False)\n"
459 "\n"
460 "   Calculate the intersection between a line (as 2 vectors) and a plane.\n"
461 "   Returns a vector for the intersection or None.\n"
462 "\n"
463 "   :arg line_a: First point of the first line\n"
464 "   :type line_a: :class:`mathutils.Vector`\n"
465 "   :arg line_b: Second point of the first line\n"
466 "   :type line_b: :class:`mathutils.Vector`\n"
467 "   :arg plane_co: A point on the plane\n"
468 "   :type plane_co: :class:`mathutils.Vector`\n"
469 "   :arg plane_no: The direction the plane is facing\n"
470 "   :type plane_no: :class:`mathutils.Vector`\n"
471 "   :return: The point of intersection or None when not found\n"
472 "   :rtype: :class:`mathutils.Vector` or None\n"
473 );
474 static PyObject *M_Geometry_intersect_line_plane(PyObject *UNUSED(self), PyObject *args)
475 {
476         const char *error_prefix = "intersect_line_plane";
477         PyObject *py_line_a, *py_line_b, *py_plane_co, *py_plane_no;
478         float line_a[3], line_b[3], plane_co[3], plane_no[3];
479         float isect[3];
480         bool no_flip = false;
481
482         if (!PyArg_ParseTuple(
483                 args, "OOOO|O&:intersect_line_plane",
484                 &py_line_a, &py_line_b, &py_plane_co, &py_plane_no,
485                 PyC_ParseBool, &no_flip))
486         {
487                 return NULL;
488         }
489
490         if (((mathutils_array_parse(line_a, 3, 3 | MU_ARRAY_SPILL, py_line_a, error_prefix) != -1) &&
491              (mathutils_array_parse(line_b, 3, 3 | MU_ARRAY_SPILL, py_line_b, error_prefix) != -1) &&
492              (mathutils_array_parse(plane_co, 3, 3 | MU_ARRAY_SPILL, py_plane_co, error_prefix) != -1) &&
493              (mathutils_array_parse(plane_no, 3, 3 | MU_ARRAY_SPILL, py_plane_no, error_prefix) != -1)) == 0)
494         {
495                 return NULL;
496         }
497
498         /* TODO: implements no_flip */
499         if (isect_line_plane_v3(isect, line_a, line_b, plane_co, plane_no) == 1) {
500                 return Vector_CreatePyObject(isect, 3, NULL);
501         }
502         else {
503                 Py_RETURN_NONE;
504         }
505 }
506
507 PyDoc_STRVAR(M_Geometry_intersect_plane_plane_doc,
508 ".. function:: intersect_plane_plane(plane_a_co, plane_a_no, plane_b_co, plane_b_no)\n"
509 "\n"
510 "   Return the intersection between two planes\n"
511 "\n"
512 "   :arg plane_a_co: Point on the first plane\n"
513 "   :type plane_a_co: :class:`mathutils.Vector`\n"
514 "   :arg plane_a_no: Normal of the first plane\n"
515 "   :type plane_a_no: :class:`mathutils.Vector`\n"
516 "   :arg plane_b_co: Point on the second plane\n"
517 "   :type plane_b_co: :class:`mathutils.Vector`\n"
518 "   :arg plane_b_no: Normal of the second plane\n"
519 "   :type plane_b_no: :class:`mathutils.Vector`\n"
520 "   :return: The line of the intersection represented as a point and a vector\n"
521 "   :rtype: tuple pair of :class:`mathutils.Vector` or None if the intersection can't be calculated\n"
522 );
523 static PyObject *M_Geometry_intersect_plane_plane(PyObject *UNUSED(self), PyObject *args)
524 {
525         const char *error_prefix = "intersect_plane_plane";
526         PyObject *ret, *ret_co, *ret_no;
527         PyObject *py_plane_a_co, *py_plane_a_no, *py_plane_b_co, *py_plane_b_no;
528         float plane_a_co[3], plane_a_no[3], plane_b_co[3], plane_b_no[3];
529         float plane_a[4], plane_b[4];
530
531         float isect_co[3];
532         float isect_no[3];
533
534         if (!PyArg_ParseTuple(
535                 args, "OOOO:intersect_plane_plane",
536                 &py_plane_a_co, &py_plane_a_no, &py_plane_b_co, &py_plane_b_no))
537         {
538                 return NULL;
539         }
540
541         if (((mathutils_array_parse(plane_a_co, 3, 3 | MU_ARRAY_SPILL, py_plane_a_co, error_prefix) != -1) &&
542              (mathutils_array_parse(plane_a_no, 3, 3 | MU_ARRAY_SPILL, py_plane_a_no, error_prefix) != -1) &&
543              (mathutils_array_parse(plane_b_co, 3, 3 | MU_ARRAY_SPILL, py_plane_b_co, error_prefix) != -1) &&
544              (mathutils_array_parse(plane_b_no, 3, 3 | MU_ARRAY_SPILL, py_plane_b_no, error_prefix) != -1)) == 0)
545         {
546                 return NULL;
547         }
548
549         plane_from_point_normal_v3(plane_a, plane_a_co, plane_a_no);
550         plane_from_point_normal_v3(plane_b, plane_b_co, plane_b_no);
551
552         if (isect_plane_plane_v3(
553                 plane_a, plane_b,
554                 isect_co, isect_no))
555         {
556                 normalize_v3(isect_no);
557
558                 ret_co = Vector_CreatePyObject(isect_co, 3, NULL);
559                 ret_no = Vector_CreatePyObject(isect_no, 3, NULL);
560         }
561         else {
562                 ret_co = Py_INCREF_RET(Py_None);
563                 ret_no = Py_INCREF_RET(Py_None);
564         }
565
566         ret = PyTuple_New(2);
567         PyTuple_SET_ITEMS(ret,
568                 ret_co,
569                 ret_no);
570         return ret;
571 }
572
573 PyDoc_STRVAR(M_Geometry_intersect_line_sphere_doc,
574 ".. function:: intersect_line_sphere(line_a, line_b, sphere_co, sphere_radius, clip=True)\n"
575 "\n"
576 "   Takes a line (as 2 points) and a sphere (as a point and a radius) and\n"
577 "   returns the intersection\n"
578 "\n"
579 "   :arg line_a: First point of the line\n"
580 "   :type line_a: :class:`mathutils.Vector`\n"
581 "   :arg line_b: Second point of the line\n"
582 "   :type line_b: :class:`mathutils.Vector`\n"
583 "   :arg sphere_co: The center of the sphere\n"
584 "   :type sphere_co: :class:`mathutils.Vector`\n"
585 "   :arg sphere_radius: Radius of the sphere\n"
586 "   :type sphere_radius: sphere_radius\n"
587 "   :return: The intersection points as a pair of vectors or None when there is no intersection\n"
588 "   :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n"
589 );
590 static PyObject *M_Geometry_intersect_line_sphere(PyObject *UNUSED(self), PyObject *args)
591 {
592         const char *error_prefix = "intersect_line_sphere";
593         PyObject *py_line_a, *py_line_b, *py_sphere_co;
594         float line_a[3], line_b[3], sphere_co[3];
595         float sphere_radius;
596         bool clip = true;
597
598         float isect_a[3];
599         float isect_b[3];
600
601         if (!PyArg_ParseTuple(
602                 args, "OOOf|O&:intersect_line_sphere",
603                 &py_line_a, &py_line_b, &py_sphere_co, &sphere_radius,
604                 PyC_ParseBool, &clip))
605         {
606                 return NULL;
607         }
608
609         if (((mathutils_array_parse(line_a, 3, 3 | MU_ARRAY_SPILL, py_line_a, error_prefix) != -1) &&
610              (mathutils_array_parse(line_b, 3, 3 | MU_ARRAY_SPILL, py_line_b, error_prefix) != -1) &&
611              (mathutils_array_parse(sphere_co, 3, 3 | MU_ARRAY_SPILL, py_sphere_co, error_prefix) != -1)) == 0)
612         {
613                 return NULL;
614         }
615         else {
616                 bool use_a = true;
617                 bool use_b = true;
618                 float lambda;
619
620                 PyObject *ret = PyTuple_New(2);
621
622                 switch (isect_line_sphere_v3(line_a, line_b, sphere_co, sphere_radius, isect_a, isect_b)) {
623                         case 1:
624                                 if (!(!clip || (((lambda = line_point_factor_v3(isect_a, line_a, line_b)) >= 0.0f) && (lambda <= 1.0f)))) use_a = false;
625                                 use_b = false;
626                                 break;
627                         case 2:
628                                 if (!(!clip || (((lambda = line_point_factor_v3(isect_a, line_a, line_b)) >= 0.0f) && (lambda <= 1.0f)))) use_a = false;
629                                 if (!(!clip || (((lambda = line_point_factor_v3(isect_b, line_a, line_b)) >= 0.0f) && (lambda <= 1.0f)))) use_b = false;
630                                 break;
631                         default:
632                                 use_a = false;
633                                 use_b = false;
634                                 break;
635                 }
636
637                 PyTuple_SET_ITEMS(ret,
638                         use_a ? Vector_CreatePyObject(isect_a, 3, NULL) : Py_INCREF_RET(Py_None),
639                         use_b ? Vector_CreatePyObject(isect_b, 3, NULL) : Py_INCREF_RET(Py_None));
640
641                 return ret;
642         }
643 }
644
645 /* keep in sync with M_Geometry_intersect_line_sphere */
646 PyDoc_STRVAR(M_Geometry_intersect_line_sphere_2d_doc,
647 ".. function:: intersect_line_sphere_2d(line_a, line_b, sphere_co, sphere_radius, clip=True)\n"
648 "\n"
649 "   Takes a line (as 2 points) and a sphere (as a point and a radius) and\n"
650 "   returns the intersection\n"
651 "\n"
652 "   :arg line_a: First point of the line\n"
653 "   :type line_a: :class:`mathutils.Vector`\n"
654 "   :arg line_b: Second point of the line\n"
655 "   :type line_b: :class:`mathutils.Vector`\n"
656 "   :arg sphere_co: The center of the sphere\n"
657 "   :type sphere_co: :class:`mathutils.Vector`\n"
658 "   :arg sphere_radius: Radius of the sphere\n"
659 "   :type sphere_radius: sphere_radius\n"
660 "   :return: The intersection points as a pair of vectors or None when there is no intersection\n"
661 "   :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n"
662 );
663 static PyObject *M_Geometry_intersect_line_sphere_2d(PyObject *UNUSED(self), PyObject *args)
664 {
665         const char *error_prefix = "intersect_line_sphere_2d";
666         PyObject *py_line_a, *py_line_b, *py_sphere_co;
667         float line_a[2], line_b[2], sphere_co[2];
668         float sphere_radius;
669         bool clip = true;
670
671         float isect_a[2];
672         float isect_b[2];
673
674         if (!PyArg_ParseTuple(
675                 args, "OOOf|O&:intersect_line_sphere_2d",
676                 &py_line_a, &py_line_b, &py_sphere_co, &sphere_radius,
677                 PyC_ParseBool, &clip))
678         {
679                 return NULL;
680         }
681
682         if (((mathutils_array_parse(line_a, 2, 2 | MU_ARRAY_SPILL, py_line_a, error_prefix) != -1) &&
683              (mathutils_array_parse(line_b, 2, 2 | MU_ARRAY_SPILL, py_line_b, error_prefix) != -1) &&
684              (mathutils_array_parse(sphere_co, 2, 2 | MU_ARRAY_SPILL, py_sphere_co, error_prefix) != -1)) == 0)
685         {
686                 return NULL;
687         }
688         else {
689                 bool use_a = true;
690                 bool use_b = true;
691                 float lambda;
692
693                 PyObject *ret = PyTuple_New(2);
694
695                 switch (isect_line_sphere_v2(line_a, line_b, sphere_co, sphere_radius, isect_a, isect_b)) {
696                         case 1:
697                                 if (!(!clip || (((lambda = line_point_factor_v2(isect_a, line_a, line_b)) >= 0.0f) && (lambda <= 1.0f)))) use_a = false;
698                                 use_b = false;
699                                 break;
700                         case 2:
701                                 if (!(!clip || (((lambda = line_point_factor_v2(isect_a, line_a, line_b)) >= 0.0f) && (lambda <= 1.0f)))) use_a = false;
702                                 if (!(!clip || (((lambda = line_point_factor_v2(isect_b, line_a, line_b)) >= 0.0f) && (lambda <= 1.0f)))) use_b = false;
703                                 break;
704                         default:
705                                 use_a = false;
706                                 use_b = false;
707                                 break;
708                 }
709
710                 PyTuple_SET_ITEMS(ret,
711                         use_a ? Vector_CreatePyObject(isect_a, 2, NULL) : Py_INCREF_RET(Py_None),
712                         use_b ? Vector_CreatePyObject(isect_b, 2, NULL) : Py_INCREF_RET(Py_None));
713
714                 return ret;
715         }
716 }
717
718 PyDoc_STRVAR(M_Geometry_intersect_point_line_doc,
719 ".. function:: intersect_point_line(pt, line_p1, line_p2)\n"
720 "\n"
721 "   Takes a point and a line and returns a tuple with the closest point on the line and its distance from the first point of the line as a percentage of the length of the line.\n"
722 "\n"
723 "   :arg pt: Point\n"
724 "   :type pt: :class:`mathutils.Vector`\n"
725 "   :arg line_p1: First point of the line\n"
726 "   :type line_p1: :class:`mathutils.Vector`\n"
727 "   :arg line_p1: Second point of the line\n"
728 "   :type line_p1: :class:`mathutils.Vector`\n"
729 "   :rtype: (:class:`mathutils.Vector`, float)\n"
730 );
731 static PyObject *M_Geometry_intersect_point_line(PyObject *UNUSED(self), PyObject *args)
732 {
733         const char *error_prefix = "intersect_point_line";
734         PyObject *py_pt, *py_line_a, *py_line_b;
735         float pt[3], pt_out[3], line_a[3], line_b[3];
736         float lambda;
737         PyObject *ret;
738         int size = 2;
739
740         if (!PyArg_ParseTuple(
741                 args, "OOO:intersect_point_line",
742                 &py_pt, &py_line_a, &py_line_b))
743         {
744                 return NULL;
745         }
746
747         /* accept 2d verts */
748         if ((((size = mathutils_array_parse(pt, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_pt, error_prefix)) != -1) &&
749              (mathutils_array_parse(line_a, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_line_a, error_prefix) != -1) &&
750              (mathutils_array_parse(line_b, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_line_b, error_prefix) != -1)) == 0)
751         {
752                 return NULL;
753         }
754
755         /* do the calculation */
756         lambda = closest_to_line_v3(pt_out, pt, line_a, line_b);
757
758         ret = PyTuple_New(2);
759         PyTuple_SET_ITEMS(ret,
760                 Vector_CreatePyObject(pt_out, size, NULL),
761                 PyFloat_FromDouble(lambda));
762         return ret;
763 }
764
765 PyDoc_STRVAR(M_Geometry_intersect_point_tri_doc,
766 ".. function:: intersect_point_tri(pt, tri_p1, tri_p2, tri_p3)\n"
767 "\n"
768 "   Takes 4 vectors: one is the point and the next 3 define the triangle.\n"
769 "\n"
770 "   :arg pt: Point\n"
771 "   :type pt: :class:`mathutils.Vector`\n"
772 "   :arg tri_p1: First point of the triangle\n"
773 "   :type tri_p1: :class:`mathutils.Vector`\n"
774 "   :arg tri_p2: Second point of the triangle\n"
775 "   :type tri_p2: :class:`mathutils.Vector`\n"
776 "   :arg tri_p3: Third point of the triangle\n"
777 "   :type tri_p3: :class:`mathutils.Vector`\n"
778 "   :return: Point on the triangles plane or None if its outside the triangle\n"
779 "   :rtype: :class:`mathutils.Vector` or None\n"
780 );
781 static PyObject *M_Geometry_intersect_point_tri(PyObject *UNUSED(self), PyObject *args)
782 {
783         const char *error_prefix = "intersect_point_tri";
784         PyObject *py_pt, *py_tri[3];
785         float pt[3], tri[3][3];
786         float vi[3];
787         int i;
788
789         if (!PyArg_ParseTuple(
790                 args, "OOOO:intersect_point_tri",
791                 &py_pt, UNPACK3_EX(&, py_tri, )))
792         {
793                 return NULL;
794         }
795
796         if (mathutils_array_parse(pt, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_pt, error_prefix) == -1) {
797                 return NULL;
798         }
799         for (i = 0; i < ARRAY_SIZE(tri); i++) {
800                 if (mathutils_array_parse(tri[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_tri[i], error_prefix) == -1) {
801                         return NULL;
802                 }
803         }
804
805         if (isect_point_tri_v3(pt, UNPACK3(tri), vi)) {
806                 return Vector_CreatePyObject(vi, 3, NULL);
807         }
808         else {
809                 Py_RETURN_NONE;
810         }
811 }
812
813 PyDoc_STRVAR(M_Geometry_intersect_point_tri_2d_doc,
814 ".. function:: intersect_point_tri_2d(pt, tri_p1, tri_p2, tri_p3)\n"
815 "\n"
816 "   Takes 4 vectors (using only the x and y coordinates): one is the point and the next 3 define the triangle. Returns 1 if the point is within the triangle, otherwise 0.\n"
817 "\n"
818 "   :arg pt: Point\n"
819 "   :type pt: :class:`mathutils.Vector`\n"
820 "   :arg tri_p1: First point of the triangle\n"
821 "   :type tri_p1: :class:`mathutils.Vector`\n"
822 "   :arg tri_p2: Second point of the triangle\n"
823 "   :type tri_p2: :class:`mathutils.Vector`\n"
824 "   :arg tri_p3: Third point of the triangle\n"
825 "   :type tri_p3: :class:`mathutils.Vector`\n"
826 "   :rtype: int\n"
827 );
828 static PyObject *M_Geometry_intersect_point_tri_2d(PyObject *UNUSED(self), PyObject *args)
829 {
830         const char *error_prefix = "intersect_point_tri_2d";
831         PyObject *py_pt, *py_tri[3];
832         float pt[2], tri[3][2];
833         int i;
834
835         if (!PyArg_ParseTuple(
836                 args, "OOOO:intersect_point_tri_2d",
837                 &py_pt, UNPACK3_EX(&, py_tri, )))
838         {
839                 return NULL;
840         }
841
842         if (mathutils_array_parse(pt, 2, 2 | MU_ARRAY_SPILL, py_pt, error_prefix) == -1) {
843                 return NULL;
844         }
845         for (i = 0; i < ARRAY_SIZE(tri); i++) {
846                 if (mathutils_array_parse(tri[i], 2, 2 | MU_ARRAY_SPILL, py_tri[i], error_prefix) == -1) {
847                         return NULL;
848                 }
849         }
850
851         return PyLong_FromLong(isect_point_tri_v2(pt, UNPACK3(tri)));
852 }
853
854 PyDoc_STRVAR(M_Geometry_intersect_point_quad_2d_doc,
855 ".. function:: intersect_point_quad_2d(pt, quad_p1, quad_p2, quad_p3, quad_p4)\n"
856 "\n"
857 "   Takes 5 vectors (using only the x and y coordinates): one is the point and the next 4 define the quad,\n"
858 "   only the x and y are used from the vectors. Returns 1 if the point is within the quad, otherwise 0.\n"
859 "   Works only with convex quads without singular edges.\n"
860 "\n"
861 "   :arg pt: Point\n"
862 "   :type pt: :class:`mathutils.Vector`\n"
863 "   :arg quad_p1: First point of the quad\n"
864 "   :type quad_p1: :class:`mathutils.Vector`\n"
865 "   :arg quad_p2: Second point of the quad\n"
866 "   :type quad_p2: :class:`mathutils.Vector`\n"
867 "   :arg quad_p3: Third point of the quad\n"
868 "   :type quad_p3: :class:`mathutils.Vector`\n"
869 "   :arg quad_p4: Fourth point of the quad\n"
870 "   :type quad_p4: :class:`mathutils.Vector`\n"
871 "   :rtype: int\n"
872 );
873 static PyObject *M_Geometry_intersect_point_quad_2d(PyObject *UNUSED(self), PyObject *args)
874 {
875         const char *error_prefix = "intersect_point_quad_2d";
876         PyObject *py_pt, *py_quad[4];
877         float pt[2], quad[4][2];
878         int i;
879
880         if (!PyArg_ParseTuple(
881                 args, "OOOOO:intersect_point_quad_2d",
882                 &py_pt, UNPACK4_EX(&, py_quad, )))
883         {
884                 return NULL;
885         }
886
887         if (mathutils_array_parse(pt, 2, 2 | MU_ARRAY_SPILL, py_pt, error_prefix) == -1) {
888                 return NULL;
889         }
890         for (i = 0; i < ARRAY_SIZE(quad); i++) {
891                 if (mathutils_array_parse(quad[i], 2, 2 | MU_ARRAY_SPILL, py_quad[i], error_prefix) == -1) {
892                         return NULL;
893                 }
894         }
895
896         return PyLong_FromLong(isect_point_quad_v2(pt, UNPACK4(quad)));
897 }
898
899 PyDoc_STRVAR(M_Geometry_distance_point_to_plane_doc,
900 ".. function:: distance_point_to_plane(pt, plane_co, plane_no)\n"
901 "\n"
902 "   Returns the signed distance between a point and a plane "
903 "   (negative when below the normal).\n"
904 "\n"
905 "   :arg pt: Point\n"
906 "   :type pt: :class:`mathutils.Vector`\n"
907 "   :arg plane_co: A point on the plane\n"
908 "   :type plane_co: :class:`mathutils.Vector`\n"
909 "   :arg plane_no: The direction the plane is facing\n"
910 "   :type plane_no: :class:`mathutils.Vector`\n"
911 "   :rtype: float\n"
912 );
913 static PyObject *M_Geometry_distance_point_to_plane(PyObject *UNUSED(self), PyObject *args)
914 {
915         const char *error_prefix = "distance_point_to_plane";
916         PyObject *py_pt, *py_plane_co, *py_plane_no;
917         float pt[3], plane_co[3], plane_no[3];
918         float plane[4];
919
920         if (!PyArg_ParseTuple(
921                 args, "OOO:distance_point_to_plane",
922                 &py_pt, &py_plane_co, &py_plane_no))
923         {
924                 return NULL;
925         }
926
927         if (((mathutils_array_parse(pt,       3, 3 | MU_ARRAY_SPILL, py_pt,       error_prefix) != -1) &&
928              (mathutils_array_parse(plane_co, 3, 3 | MU_ARRAY_SPILL, py_plane_co, error_prefix) != -1) &&
929              (mathutils_array_parse(plane_no, 3, 3 | MU_ARRAY_SPILL, py_plane_no, error_prefix) != -1)) == 0)
930         {
931                 return NULL;
932         }
933
934         plane_from_point_normal_v3(plane, plane_co, plane_no);
935         return PyFloat_FromDouble(dist_signed_to_plane_v3(pt, plane));
936 }
937
938 PyDoc_STRVAR(M_Geometry_barycentric_transform_doc,
939 ".. function:: barycentric_transform(point, tri_a1, tri_a2, tri_a3, tri_b1, tri_b2, tri_b3)\n"
940 "\n"
941 "   Return a transformed point, the transformation is defined by 2 triangles.\n"
942 "\n"
943 "   :arg point: The point to transform.\n"
944 "   :type point: :class:`mathutils.Vector`\n"
945 "   :arg tri_a1: source triangle vertex.\n"
946 "   :type tri_a1: :class:`mathutils.Vector`\n"
947 "   :arg tri_a2: source triangle vertex.\n"
948 "   :type tri_a2: :class:`mathutils.Vector`\n"
949 "   :arg tri_a3: source triangle vertex.\n"
950 "   :type tri_a3: :class:`mathutils.Vector`\n"
951 "   :arg tri_b1: target triangle vertex.\n"
952 "   :type tri_b1: :class:`mathutils.Vector`\n"
953 "   :arg tri_b2: target triangle vertex.\n"
954 "   :type tri_b2: :class:`mathutils.Vector`\n"
955 "   :arg tri_b3: target triangle vertex.\n"
956 "   :type tri_b3: :class:`mathutils.Vector`\n"
957 "   :return: The transformed point\n"
958 "   :rtype: :class:`mathutils.Vector`'s\n"
959 );
960 static PyObject *M_Geometry_barycentric_transform(PyObject *UNUSED(self), PyObject *args)
961 {
962         const char *error_prefix = "barycentric_transform";
963         PyObject *py_pt_src, *py_tri_src[3], *py_tri_dst[3];
964         float pt_src[3], pt_dst[3], tri_src[3][3], tri_dst[3][3];
965         int i;
966
967         if (!PyArg_ParseTuple(
968                 args, "OOOOOOO:barycentric_transform",
969                 &py_pt_src,
970                 UNPACK3_EX(&, py_tri_src, ),
971                 UNPACK3_EX(&, py_tri_dst, )))
972         {
973                 return NULL;
974         }
975
976         if (mathutils_array_parse(pt_src, 3, 3 | MU_ARRAY_SPILL, py_pt_src, error_prefix) == -1) {
977                 return NULL;
978         }
979         for (i = 0; i < ARRAY_SIZE(tri_src); i++) {
980                 if (((mathutils_array_parse(tri_src[i], 3, 3 | MU_ARRAY_SPILL, py_tri_src[i], error_prefix) != -1) &&
981                      (mathutils_array_parse(tri_dst[i], 3, 3 | MU_ARRAY_SPILL, py_tri_dst[i], error_prefix) != -1)) == 0)
982                 {
983                         return NULL;
984                 }
985         }
986
987         transform_point_by_tri_v3(
988                 pt_dst, pt_src,
989                 UNPACK3(tri_dst),
990                 UNPACK3(tri_src));
991
992         return Vector_CreatePyObject(pt_dst, 3, NULL);
993 }
994
995 PyDoc_STRVAR(M_Geometry_points_in_planes_doc,
996 ".. function:: points_in_planes(planes)\n"
997 "\n"
998 "   Returns a list of points inside all planes given and a list of index values for the planes used.\n"
999 "\n"
1000 "   :arg planes: List of planes (4D vectors).\n"
1001 "   :type planes: list of :class:`mathutils.Vector`\n"
1002 "   :return: two lists, once containing the vertices inside the planes, another containing the plane indices used\n"
1003 "   :rtype: pair of lists\n"
1004 );
1005 /* note: this function could be optimized by some spatial structure */
1006 static PyObject *M_Geometry_points_in_planes(PyObject *UNUSED(self), PyObject *args)
1007 {
1008         PyObject *py_planes;
1009         float (*planes)[4];
1010         unsigned int planes_len;
1011
1012         if (!PyArg_ParseTuple(
1013                 args, "O:points_in_planes",
1014                 &py_planes))
1015         {
1016                 return NULL;
1017         }
1018
1019         if ((planes_len = mathutils_array_parse_alloc_v((float **)&planes, 4, py_planes, "points_in_planes")) == -1) {
1020                 return NULL;
1021         }
1022         else {
1023                 /* note, this could be refactored into plain C easy - py bits are noted */
1024                 const float eps = 0.0001f;
1025                 const unsigned int len = (unsigned int)planes_len;
1026                 unsigned int i, j, k, l;
1027
1028                 float n1n2[3], n2n3[3], n3n1[3];
1029                 float potentialVertex[3];
1030                 char *planes_used = PyMem_Malloc(sizeof(char) * len);
1031
1032                 /* python */
1033                 PyObject *py_verts = PyList_New(0);
1034                 PyObject *py_plane_index = PyList_New(0);
1035
1036                 memset(planes_used, 0, sizeof(char) * len);
1037
1038                 for (i = 0; i < len; i++) {
1039                         const float *N1 = planes[i];
1040                         for (j = i + 1; j < len; j++) {
1041                                 const float *N2 = planes[j];
1042                                 cross_v3_v3v3(n1n2, N1, N2);
1043                                 if (len_squared_v3(n1n2) > eps) {
1044                                         for (k = j + 1; k < len; k++) {
1045                                                 const float *N3 = planes[k];
1046                                                 cross_v3_v3v3(n2n3, N2, N3);
1047                                                 if (len_squared_v3(n2n3) > eps) {
1048                                                         cross_v3_v3v3(n3n1, N3, N1);
1049                                                         if (len_squared_v3(n3n1) > eps) {
1050                                                                 const float quotient = dot_v3v3(N1, n2n3);
1051                                                                 if (fabsf(quotient) > eps) {
1052                                                                         /* potentialVertex = (n2n3 * N1[3] + n3n1 * N2[3] + n1n2 * N3[3]) * (-1.0 / quotient); */
1053                                                                         const float quotient_ninv = -1.0f / quotient;
1054                                                                         potentialVertex[0] = ((n2n3[0] * N1[3]) + (n3n1[0] * N2[3]) + (n1n2[0] * N3[3])) * quotient_ninv;
1055                                                                         potentialVertex[1] = ((n2n3[1] * N1[3]) + (n3n1[1] * N2[3]) + (n1n2[1] * N3[3])) * quotient_ninv;
1056                                                                         potentialVertex[2] = ((n2n3[2] * N1[3]) + (n3n1[2] * N2[3]) + (n1n2[2] * N3[3])) * quotient_ninv;
1057                                                                         for (l = 0; l < len; l++) {
1058                                                                                 const float *NP = planes[l];
1059                                                                                 if ((dot_v3v3(NP, potentialVertex) + NP[3]) > 0.000001f) {
1060                                                                                         break;
1061                                                                                 }
1062                                                                         }
1063
1064                                                                         if (l == len) { /* ok */
1065                                                                                 /* python */
1066                                                                                 PyList_APPEND(py_verts, Vector_CreatePyObject(potentialVertex, 3, NULL));
1067                                                                                 planes_used[i] = planes_used[j] = planes_used[k] = true;
1068                                                                         }
1069                                                                 }
1070                                                         }
1071                                                 }
1072                                         }
1073                                 }
1074                         }
1075                 }
1076
1077                 PyMem_Free(planes);
1078
1079                 /* now make a list of used planes */
1080                 for (i = 0; i < len; i++) {
1081                         if (planes_used[i]) {
1082                                 PyList_APPEND(py_plane_index, PyLong_FromLong(i));
1083                         }
1084                 }
1085                 PyMem_Free(planes_used);
1086
1087                 {
1088                         PyObject *ret = PyTuple_New(2);
1089                         PyTuple_SET_ITEMS(ret,
1090                                 py_verts,
1091                                 py_plane_index);
1092                         return ret;
1093                 }
1094         }
1095 }
1096
1097 #ifndef MATH_STANDALONE
1098
1099 PyDoc_STRVAR(M_Geometry_interpolate_bezier_doc,
1100 ".. function:: interpolate_bezier(knot1, handle1, handle2, knot2, resolution)\n"
1101 "\n"
1102 "   Interpolate a bezier spline segment.\n"
1103 "\n"
1104 "   :arg knot1: First bezier spline point.\n"
1105 "   :type knot1: :class:`mathutils.Vector`\n"
1106 "   :arg handle1: First bezier spline handle.\n"
1107 "   :type handle1: :class:`mathutils.Vector`\n"
1108 "   :arg handle2: Second bezier spline handle.\n"
1109 "   :type handle2: :class:`mathutils.Vector`\n"
1110 "   :arg knot2: Second bezier spline point.\n"
1111 "   :type knot2: :class:`mathutils.Vector`\n"
1112 "   :arg resolution: Number of points to return.\n"
1113 "   :type resolution: int\n"
1114 "   :return: The interpolated points\n"
1115 "   :rtype: list of :class:`mathutils.Vector`'s\n"
1116 );
1117 static PyObject *M_Geometry_interpolate_bezier(PyObject *UNUSED(self), PyObject *args)
1118 {
1119         const char *error_prefix = "interpolate_bezier";
1120         PyObject *py_data[4];
1121         float data[4][4] = {{0.0f}};
1122         int resolu;
1123         int dims = 0;
1124         int i;
1125         float *coord_array, *fp;
1126         PyObject *list;
1127
1128         if (!PyArg_ParseTuple(
1129                 args, "OOOOi:interpolate_bezier",
1130                 UNPACK4_EX(&, py_data, ), &resolu))
1131         {
1132                 return NULL;
1133         }
1134
1135         for (i = 0; i < 4; i++) {
1136                 int dims_tmp;
1137                 if ((dims_tmp = mathutils_array_parse(data[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_data[i], error_prefix)) == -1) {
1138                         return NULL;
1139                 }
1140                 dims = max_ii(dims, dims_tmp);
1141         }
1142
1143         if (resolu <= 1) {
1144                 PyErr_SetString(PyExc_ValueError,
1145                                 "resolution must be 2 or over");
1146                 return NULL;
1147         }
1148
1149         coord_array = MEM_callocN(dims * (resolu) * sizeof(float), error_prefix);
1150         for (i = 0; i < dims; i++) {
1151                 BKE_curve_forward_diff_bezier(UNPACK4_EX(, data, [i]), coord_array + i, resolu - 1, sizeof(float) * dims);
1152         }
1153
1154         list = PyList_New(resolu);
1155         fp = coord_array;
1156         for (i = 0; i < resolu; i++, fp = fp + dims) {
1157                 PyList_SET_ITEM(list, i, Vector_CreatePyObject(fp, dims, NULL));
1158         }
1159         MEM_freeN(coord_array);
1160         return list;
1161 }
1162
1163
1164 PyDoc_STRVAR(M_Geometry_tessellate_polygon_doc,
1165 ".. function:: tessellate_polygon(veclist_list)\n"
1166 "\n"
1167 "   Takes a list of polylines (each point a vector) and returns the point indices for a polyline filled with triangles.\n"
1168 "\n"
1169 "   :arg veclist_list: list of polylines\n"
1170 "   :rtype: list\n"
1171 );
1172 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
1173 static PyObject *M_Geometry_tessellate_polygon(PyObject *UNUSED(self), PyObject *polyLineSeq)
1174 {
1175         PyObject *tri_list; /*return this list of tri's */
1176         PyObject *polyLine, *polyVec;
1177         int i, len_polylines, len_polypoints, ls_error = 0;
1178
1179         /* display listbase */
1180         ListBase dispbase = {NULL, NULL};
1181         DispList *dl;
1182         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
1183         int index, *dl_face, totpoints = 0;
1184
1185         if (!PySequence_Check(polyLineSeq)) {
1186                 PyErr_SetString(PyExc_TypeError,
1187                                 "expected a sequence of poly lines");
1188                 return NULL;
1189         }
1190
1191         len_polylines = PySequence_Size(polyLineSeq);
1192
1193         for (i = 0; i < len_polylines; i++) {
1194                 polyLine = PySequence_GetItem(polyLineSeq, i);
1195                 if (!PySequence_Check(polyLine)) {
1196                         BKE_displist_free(&dispbase);
1197                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
1198                         PyErr_SetString(PyExc_TypeError,
1199                                         "One or more of the polylines is not a sequence of mathutils.Vector's");
1200                         return NULL;
1201                 }
1202
1203                 len_polypoints = PySequence_Size(polyLine);
1204                 if (len_polypoints > 0) { /* don't bother adding edges as polylines */
1205 #if 0
1206                         if (EXPP_check_sequence_consistency(polyLine, &vector_Type) != 1) {
1207                                 freedisplist(&dispbase);
1208                                 Py_DECREF(polyLine);
1209                                 PyErr_SetString(PyExc_TypeError,
1210                                                 "A point in one of the polylines is not a mathutils.Vector type");
1211                                 return NULL;
1212                         }
1213 #endif
1214                         dl = MEM_callocN(sizeof(DispList), "poly disp");
1215                         BLI_addtail(&dispbase, dl);
1216                         dl->type = DL_INDEX3;
1217                         dl->nr = len_polypoints;
1218                         dl->type = DL_POLY;
1219                         dl->parts = 1; /* no faces, 1 edge loop */
1220                         dl->col = 0; /* no material */
1221                         dl->verts = fp = MEM_callocN(sizeof(float) * 3 * len_polypoints, "dl verts");
1222                         dl->index = MEM_callocN(sizeof(int) * 3 * len_polypoints, "dl index");
1223
1224                         for (index = 0; index < len_polypoints; index++, fp += 3) {
1225                                 polyVec = PySequence_GetItem(polyLine, index);
1226                                 if (VectorObject_Check(polyVec)) {
1227
1228                                         if (BaseMath_ReadCallback((VectorObject *)polyVec) == -1)
1229                                                 ls_error = 1;
1230
1231                                         fp[0] = ((VectorObject *)polyVec)->vec[0];
1232                                         fp[1] = ((VectorObject *)polyVec)->vec[1];
1233                                         if (((VectorObject *)polyVec)->size > 2)
1234                                                 fp[2] = ((VectorObject *)polyVec)->vec[2];
1235                                         else
1236                                                 fp[2] = 0.0f;  /* if its a 2d vector then set the z to be zero */
1237                                 }
1238                                 else {
1239                                         ls_error = 1;
1240                                 }
1241
1242                                 totpoints++;
1243                                 Py_DECREF(polyVec);
1244                         }
1245                 }
1246                 Py_DECREF(polyLine);
1247         }
1248
1249         if (ls_error) {
1250                 BKE_displist_free(&dispbase); /* possible some dl was allocated */
1251                 PyErr_SetString(PyExc_TypeError,
1252                                 "A point in one of the polylines "
1253                                 "is not a mathutils.Vector type");
1254                 return NULL;
1255         }
1256         else if (totpoints) {
1257                 /* now make the list to return */
1258                 /* TODO, add normal arg */
1259                 BKE_displist_fill(&dispbase, &dispbase, NULL, false);
1260
1261                 /* The faces are stored in a new DisplayList
1262                  * that's added to the head of the listbase */
1263                 dl = dispbase.first;
1264
1265                 tri_list = PyList_New(dl->parts);
1266                 if (!tri_list) {
1267                         BKE_displist_free(&dispbase);
1268                         PyErr_SetString(PyExc_RuntimeError,
1269                                         "failed to make a new list");
1270                         return NULL;
1271                 }
1272
1273                 index = 0;
1274                 dl_face = dl->index;
1275                 while (index < dl->parts) {
1276                         PyList_SET_ITEM(tri_list, index, PyC_Tuple_Pack_I32(dl_face[0], dl_face[1], dl_face[2]));
1277                         dl_face += 3;
1278                         index++;
1279                 }
1280                 BKE_displist_free(&dispbase);
1281         }
1282         else {
1283                 /* no points, do this so scripts don't barf */
1284                 BKE_displist_free(&dispbase); /* possible some dl was allocated */
1285                 tri_list = PyList_New(0);
1286         }
1287
1288         return tri_list;
1289 }
1290
1291
1292 static int boxPack_FromPyObject(PyObject *value, BoxPack **boxarray)
1293 {
1294         Py_ssize_t len, i;
1295         PyObject *list_item, *item_1, *item_2;
1296         BoxPack *box;
1297
1298
1299         /* Error checking must already be done */
1300         if (!PyList_Check(value)) {
1301                 PyErr_SetString(PyExc_TypeError,
1302                                 "can only back a list of [x, y, w, h]");
1303                 return -1;
1304         }
1305
1306         len = PyList_GET_SIZE(value);
1307
1308         *boxarray = MEM_mallocN(len * sizeof(BoxPack), "BoxPack box");
1309
1310
1311         for (i = 0; i < len; i++) {
1312                 list_item = PyList_GET_ITEM(value, i);
1313                 if (!PyList_Check(list_item) || PyList_GET_SIZE(list_item) < 4) {
1314                         MEM_freeN(*boxarray);
1315                         PyErr_SetString(PyExc_TypeError,
1316                                         "can only pack a list of [x, y, w, h]");
1317                         return -1;
1318                 }
1319
1320                 box = (*boxarray) + i;
1321
1322                 item_1 = PyList_GET_ITEM(list_item, 2);
1323                 item_2 = PyList_GET_ITEM(list_item, 3);
1324
1325                 box->w =  (float)PyFloat_AsDouble(item_1);
1326                 box->h =  (float)PyFloat_AsDouble(item_2);
1327                 box->index = i;
1328
1329                 /* accounts for error case too and overwrites with own error */
1330                 if (box->w < 0.0f || box->h < 0.0f) {
1331                         MEM_freeN(*boxarray);
1332                         PyErr_SetString(PyExc_TypeError,
1333                                         "error parsing width and height values from list: "
1334                                         "[x, y, w, h], not numbers or below zero");
1335                         return -1;
1336                 }
1337
1338                 /* verts will be added later */
1339         }
1340         return 0;
1341 }
1342
1343 static void boxPack_ToPyObject(PyObject *value, BoxPack **boxarray)
1344 {
1345         Py_ssize_t len, i;
1346         PyObject *list_item;
1347         BoxPack *box;
1348
1349         len = PyList_GET_SIZE(value);
1350
1351         for (i = 0; i < len; i++) {
1352                 box = (*boxarray) + i;
1353                 list_item = PyList_GET_ITEM(value, box->index);
1354                 PyList_SET_ITEM(list_item, 0, PyFloat_FromDouble(box->x));
1355                 PyList_SET_ITEM(list_item, 1, PyFloat_FromDouble(box->y));
1356         }
1357         MEM_freeN(*boxarray);
1358 }
1359
1360 PyDoc_STRVAR(M_Geometry_box_pack_2d_doc,
1361 ".. function:: box_pack_2d(boxes)\n"
1362 "\n"
1363 "   Returns the normal of the 3D tri or quad.\n"
1364 "\n"
1365 "   :arg boxes: list of boxes, each box is a list where the first 4 items are [x, y, width, height, ...] other items are ignored.\n"
1366 "   :type boxes: list\n"
1367 "   :return: the width and height of the packed bounding box\n"
1368 "   :rtype: tuple, pair of floats\n"
1369 );
1370 static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlist)
1371 {
1372         float tot_width = 0.0f, tot_height = 0.0f;
1373         Py_ssize_t len;
1374
1375         PyObject *ret;
1376
1377         if (!PyList_Check(boxlist)) {
1378                 PyErr_SetString(PyExc_TypeError,
1379                                 "expected a list of boxes [[x, y, w, h], ... ]");
1380                 return NULL;
1381         }
1382
1383         len = PyList_GET_SIZE(boxlist);
1384         if (len) {
1385                 BoxPack *boxarray = NULL;
1386                 if (boxPack_FromPyObject(boxlist, &boxarray) == -1) {
1387                         return NULL; /* exception set */
1388                 }
1389
1390                 /* Non Python function */
1391                 BLI_box_pack_2d(boxarray, len, &tot_width, &tot_height);
1392
1393                 boxPack_ToPyObject(boxlist, &boxarray);
1394         }
1395
1396         ret = PyTuple_New(2);
1397         PyTuple_SET_ITEMS(ret,
1398                 PyFloat_FromDouble(tot_width),
1399                 PyFloat_FromDouble(tot_height));
1400         return ret;
1401 }
1402
1403 PyDoc_STRVAR(M_Geometry_box_fit_2d_doc,
1404 ".. function:: box_fit_2d(points)\n"
1405 "\n"
1406 "   Returns an angle that best fits the points to an axis aligned rectangle\n"
1407 "\n"
1408 "   :arg points: list of 2d points.\n"
1409 "   :type points: list\n"
1410 "   :return: angle\n"
1411 "   :rtype: float\n"
1412 );
1413 static PyObject *M_Geometry_box_fit_2d(PyObject *UNUSED(self), PyObject *pointlist)
1414 {
1415         float (*points)[2];
1416         Py_ssize_t len;
1417
1418         float angle = 0.0f;
1419
1420         len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "box_fit_2d");
1421         if (len == -1) {
1422                 return NULL;
1423         }
1424
1425         if (len) {
1426                 /* Non Python function */
1427                 angle = BLI_convexhull_aabb_fit_points_2d(points, len);
1428
1429                 PyMem_Free(points);
1430         }
1431
1432
1433         return PyFloat_FromDouble(angle);
1434 }
1435
1436 PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc,
1437 ".. function:: convex_hull_2d(points)\n"
1438 "\n"
1439 "   Returns a list of indices into the list given\n"
1440 "\n"
1441 "   :arg points: list of 2d points.\n"
1442 "   :type points: list\n"
1443 "   :return: a list of indices\n"
1444 "   :rtype: list of ints\n"
1445 );
1446 static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *pointlist)
1447 {
1448         float (*points)[2];
1449         Py_ssize_t len;
1450
1451         PyObject *ret;
1452
1453         len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "convex_hull_2d");
1454         if (len == -1) {
1455                 return NULL;
1456         }
1457
1458         if (len) {
1459                 int *index_map;
1460                 Py_ssize_t len_ret, i;
1461
1462                 index_map  = MEM_mallocN(sizeof(*index_map) * len * 2, __func__);
1463
1464                 /* Non Python function */
1465                 len_ret = BLI_convexhull_2d(points, len, index_map);
1466
1467                 ret = PyList_New(len_ret);
1468                 for (i = 0; i < len_ret; i++) {
1469                         PyList_SET_ITEM(ret, i, PyLong_FromLong(index_map[i]));
1470                 }
1471
1472                 MEM_freeN(index_map);
1473
1474                 PyMem_Free(points);
1475         }
1476         else {
1477                 ret = PyList_New(0);
1478         }
1479
1480
1481         return ret;
1482 }
1483
1484 #endif /* MATH_STANDALONE */
1485
1486
1487 static PyMethodDef M_Geometry_methods[] = {
1488         {"intersect_ray_tri", (PyCFunction) M_Geometry_intersect_ray_tri, METH_VARARGS, M_Geometry_intersect_ray_tri_doc},
1489         {"intersect_point_line", (PyCFunction) M_Geometry_intersect_point_line, METH_VARARGS, M_Geometry_intersect_point_line_doc},
1490         {"intersect_point_tri", (PyCFunction) M_Geometry_intersect_point_tri, METH_VARARGS, M_Geometry_intersect_point_tri_doc},
1491         {"intersect_point_tri_2d", (PyCFunction) M_Geometry_intersect_point_tri_2d, METH_VARARGS, M_Geometry_intersect_point_tri_2d_doc},
1492         {"intersect_point_quad_2d", (PyCFunction) M_Geometry_intersect_point_quad_2d, METH_VARARGS, M_Geometry_intersect_point_quad_2d_doc},
1493         {"intersect_line_line", (PyCFunction) M_Geometry_intersect_line_line, METH_VARARGS, M_Geometry_intersect_line_line_doc},
1494         {"intersect_line_line_2d", (PyCFunction) M_Geometry_intersect_line_line_2d, METH_VARARGS, M_Geometry_intersect_line_line_2d_doc},
1495         {"intersect_line_plane", (PyCFunction) M_Geometry_intersect_line_plane, METH_VARARGS, M_Geometry_intersect_line_plane_doc},
1496         {"intersect_plane_plane", (PyCFunction) M_Geometry_intersect_plane_plane, METH_VARARGS, M_Geometry_intersect_plane_plane_doc},
1497         {"intersect_line_sphere", (PyCFunction) M_Geometry_intersect_line_sphere, METH_VARARGS, M_Geometry_intersect_line_sphere_doc},
1498         {"intersect_line_sphere_2d", (PyCFunction) M_Geometry_intersect_line_sphere_2d, METH_VARARGS, M_Geometry_intersect_line_sphere_2d_doc},
1499         {"distance_point_to_plane", (PyCFunction) M_Geometry_distance_point_to_plane, METH_VARARGS, M_Geometry_distance_point_to_plane_doc},
1500         {"intersect_sphere_sphere_2d", (PyCFunction) M_Geometry_intersect_sphere_sphere_2d, METH_VARARGS, M_Geometry_intersect_sphere_sphere_2d_doc},
1501         {"area_tri", (PyCFunction) M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc},
1502         {"volume_tetrahedron", (PyCFunction) M_Geometry_volume_tetrahedron, METH_VARARGS, M_Geometry_volume_tetrahedron_doc},
1503         {"normal", (PyCFunction) M_Geometry_normal, METH_VARARGS, M_Geometry_normal_doc},
1504         {"barycentric_transform", (PyCFunction) M_Geometry_barycentric_transform, METH_VARARGS, M_Geometry_barycentric_transform_doc},
1505         {"points_in_planes", (PyCFunction) M_Geometry_points_in_planes, METH_VARARGS, M_Geometry_points_in_planes_doc},
1506 #ifndef MATH_STANDALONE
1507         {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc},
1508         {"tessellate_polygon", (PyCFunction) M_Geometry_tessellate_polygon, METH_O, M_Geometry_tessellate_polygon_doc},
1509         {"convex_hull_2d", (PyCFunction) M_Geometry_convex_hull_2d, METH_O, M_Geometry_convex_hull_2d_doc},
1510         {"box_fit_2d", (PyCFunction) M_Geometry_box_fit_2d, METH_O, M_Geometry_box_fit_2d_doc},
1511         {"box_pack_2d", (PyCFunction) M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc},
1512 #endif
1513         {NULL, NULL, 0, NULL},
1514 };
1515
1516 static struct PyModuleDef M_Geometry_module_def = {
1517         PyModuleDef_HEAD_INIT,
1518         "mathutils.geometry",  /* m_name */
1519         M_Geometry_doc,  /* m_doc */
1520         0,  /* m_size */
1521         M_Geometry_methods,  /* m_methods */
1522         NULL,  /* m_reload */
1523         NULL,  /* m_traverse */
1524         NULL,  /* m_clear */
1525         NULL,  /* m_free */
1526 };
1527
1528 /*----------------------------MODULE INIT-------------------------*/
1529 PyMODINIT_FUNC PyInit_mathutils_geometry(void)
1530 {
1531         PyObject *submodule = PyModule_Create(&M_Geometry_module_def);
1532         return submodule;
1533 }