svn merge ^/trunk/blender -r47423:47506
[blender-staging.git] / source / blender / python / mathutils / mathutils_geometry.c
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  * This is a new part of Blender.
22  *
23  * Contributor(s): Joseph Gilbert, Campbell Barton
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/python/mathutils/mathutils_geometry.c
29  *  \ingroup pymathutils
30  */
31
32
33 #include <Python.h>
34
35 #include "mathutils_geometry.h"
36
37 /* Used for PolyFill */
38 #ifndef MATH_STANDALONE /* define when building outside blender */
39 #  include "MEM_guardedalloc.h"
40 #  include "BLI_blenlib.h"
41 #  include "BLI_boxpack2d.h"
42 #  include "BKE_displist.h"
43 #  include "BKE_curve.h"
44 #endif
45
46 #include "BLI_math.h"
47 #include "BLI_utildefines.h"
48
49 #define SWAP_FLOAT(a, b, tmp) tmp = a; a = b; b = tmp
50
51 /*-------------------------DOC STRINGS ---------------------------*/
52 PyDoc_STRVAR(M_Geometry_doc,
53 "The Blender geometry module"
54 );
55
56 //---------------------------------INTERSECTION FUNCTIONS--------------------
57
58 PyDoc_STRVAR(M_Geometry_intersect_ray_tri_doc,
59 ".. function:: intersect_ray_tri(v1, v2, v3, ray, orig, clip=True)\n"
60 "\n"
61 "   Returns the intersection between a ray and a triangle, if possible, returns None otherwise.\n"
62 "\n"
63 "   :arg v1: Point1\n"
64 "   :type v1: :class:`mathutils.Vector`\n"
65 "   :arg v2: Point2\n"
66 "   :type v2: :class:`mathutils.Vector`\n"
67 "   :arg v3: Point3\n"
68 "   :type v3: :class:`mathutils.Vector`\n"
69 "   :arg ray: Direction of the projection\n"
70 "   :type ray: :class:`mathutils.Vector`\n"
71 "   :arg orig: Origin\n"
72 "   :type orig: :class:`mathutils.Vector`\n"
73 "   :arg clip: When False, don't restrict the intersection to the area of the triangle, use the infinite plane defined by the triangle.\n"
74 "   :type clip: boolean\n"
75 "   :return: The point of intersection or None if no intersection is found\n"
76 "   :rtype: :class:`mathutils.Vector` or None\n"
77 );
78 static PyObject *M_Geometry_intersect_ray_tri(PyObject *UNUSED(self), PyObject *args)
79 {
80         VectorObject *ray, *ray_off, *vec1, *vec2, *vec3;
81         float dir[3], orig[3], v1[3], v2[3], v3[3], e1[3], e2[3], pvec[3], tvec[3], qvec[3];
82         float det, inv_det, u, v, t;
83         int clip = 1;
84
85         if (!PyArg_ParseTuple(args,
86                               "O!O!O!O!O!|i:intersect_ray_tri",
87                               &vector_Type, &vec1,
88                               &vector_Type, &vec2,
89                               &vector_Type, &vec3,
90                               &vector_Type, &ray,
91                               &vector_Type, &ray_off, &clip))
92         {
93                 return NULL;
94         }
95         if (vec1->size != 3 || vec2->size != 3 || vec3->size != 3 || ray->size != 3 || ray_off->size != 3) {
96                 PyErr_SetString(PyExc_ValueError,
97                                 "only 3D vectors for all parameters");
98                 return NULL;
99         }
100
101         if (BaseMath_ReadCallback(vec1) == -1 ||
102             BaseMath_ReadCallback(vec2) == -1 ||
103             BaseMath_ReadCallback(vec3) == -1 ||
104             BaseMath_ReadCallback(ray)  == -1 ||
105             BaseMath_ReadCallback(ray_off) == -1)
106         {
107                 return NULL;
108         }
109
110         copy_v3_v3(v1, vec1->vec);
111         copy_v3_v3(v2, vec2->vec);
112         copy_v3_v3(v3, vec3->vec);
113
114         copy_v3_v3(dir, ray->vec);
115         normalize_v3(dir);
116
117         copy_v3_v3(orig, ray_off->vec);
118
119         /* find vectors for two edges sharing v1 */
120         sub_v3_v3v3(e1, v2, v1);
121         sub_v3_v3v3(e2, v3, v1);
122
123         /* begin calculating determinant - also used to calculated U parameter */
124         cross_v3_v3v3(pvec, dir, e2);
125
126         /* if determinant is near zero, ray lies in plane of triangle */
127         det = dot_v3v3(e1, pvec);
128
129         if (det > -0.000001f && det < 0.000001f) {
130                 Py_RETURN_NONE;
131         }
132
133         inv_det = 1.0f / det;
134
135         /* calculate distance from v1 to ray origin */
136         sub_v3_v3v3(tvec, orig, v1);
137
138         /* calculate U parameter and test bounds */
139         u = dot_v3v3(tvec, pvec) * inv_det;
140         if (clip && (u < 0.0f || u > 1.0f)) {
141                 Py_RETURN_NONE;
142         }
143
144         /* prepare to test the V parameter */
145         cross_v3_v3v3(qvec, tvec, e1);
146
147         /* calculate V parameter and test bounds */
148         v = dot_v3v3(dir, qvec) * inv_det;
149
150         if (clip && (v < 0.0f || u + v > 1.0f)) {
151                 Py_RETURN_NONE;
152         }
153
154         /* calculate t, ray intersects triangle */
155         t = dot_v3v3(e2, qvec) * inv_det;
156
157         mul_v3_fl(dir, t);
158         add_v3_v3v3(pvec, orig, dir);
159
160         return Vector_CreatePyObject(pvec, 3, Py_NEW, NULL);
161 }
162
163 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
164
165 PyDoc_STRVAR(M_Geometry_intersect_line_line_doc,
166 ".. function:: intersect_line_line(v1, v2, v3, v4)\n"
167 "\n"
168 "   Returns a tuple with the points on each line respectively closest to the other.\n"
169 "\n"
170 "   :arg v1: First point of the first line\n"
171 "   :type v1: :class:`mathutils.Vector`\n"
172 "   :arg v2: Second point of the first line\n"
173 "   :type v2: :class:`mathutils.Vector`\n"
174 "   :arg v3: First point of the second line\n"
175 "   :type v3: :class:`mathutils.Vector`\n"
176 "   :arg v4: Second point of the second line\n"
177 "   :type v4: :class:`mathutils.Vector`\n"
178 "   :rtype: tuple of :class:`mathutils.Vector`'s\n"
179 );
180 static PyObject *M_Geometry_intersect_line_line(PyObject *UNUSED(self), PyObject *args)
181 {
182         PyObject *tuple;
183         VectorObject *vec1, *vec2, *vec3, *vec4;
184         float v1[3], v2[3], v3[3], v4[3], i1[3], i2[3];
185
186         if (!PyArg_ParseTuple(args, "O!O!O!O!:intersect_line_line",
187                               &vector_Type, &vec1,
188                               &vector_Type, &vec2,
189                               &vector_Type, &vec3,
190                               &vector_Type, &vec4))
191         {
192                 return NULL;
193         }
194
195         if (vec1->size != vec2->size || vec1->size != vec3->size || vec3->size != vec2->size) {
196                 PyErr_SetString(PyExc_ValueError,
197                                 "vectors must be of the same size");
198                 return NULL;
199         }
200
201         if (BaseMath_ReadCallback(vec1) == -1 ||
202             BaseMath_ReadCallback(vec2) == -1 ||
203             BaseMath_ReadCallback(vec3) == -1 ||
204             BaseMath_ReadCallback(vec4) == -1)
205         {
206                 return NULL;
207         }
208
209         if (vec1->size == 3 || vec1->size == 2) {
210                 int result;
211
212                 if (vec1->size == 3) {
213                         copy_v3_v3(v1, vec1->vec);
214                         copy_v3_v3(v2, vec2->vec);
215                         copy_v3_v3(v3, vec3->vec);
216                         copy_v3_v3(v4, vec4->vec);
217                 }
218                 else {
219                         v1[0] = vec1->vec[0];
220                         v1[1] = vec1->vec[1];
221                         v1[2] = 0.0f;
222
223                         v2[0] = vec2->vec[0];
224                         v2[1] = vec2->vec[1];
225                         v2[2] = 0.0f;
226
227                         v3[0] = vec3->vec[0];
228                         v3[1] = vec3->vec[1];
229                         v3[2] = 0.0f;
230
231                         v4[0] = vec4->vec[0];
232                         v4[1] = vec4->vec[1];
233                         v4[2] = 0.0f;
234                 }
235
236                 result = isect_line_line_v3(v1, v2, v3, v4, i1, i2);
237
238                 if (result == 0) {
239                         /* colinear */
240                         Py_RETURN_NONE;
241                 }
242                 else {
243                         tuple = PyTuple_New(2);
244                         PyTuple_SET_ITEM(tuple, 0, Vector_CreatePyObject(i1, vec1->size, Py_NEW, NULL));
245                         PyTuple_SET_ITEM(tuple, 1, Vector_CreatePyObject(i2, vec1->size, Py_NEW, NULL));
246                         return tuple;
247                 }
248         }
249         else {
250                 PyErr_SetString(PyExc_ValueError,
251                                 "2D/3D vectors only");
252                 return NULL;
253         }
254 }
255
256
257
258
259 //----------------------------geometry.normal() -------------------
260 PyDoc_STRVAR(M_Geometry_normal_doc,
261 ".. function:: normal(v1, v2, v3, v4=None)\n"
262 "\n"
263 "   Returns the normal of the 3D tri or quad.\n"
264 "\n"
265 "   :arg v1: Point1\n"
266 "   :type v1: :class:`mathutils.Vector`\n"
267 "   :arg v2: Point2\n"
268 "   :type v2: :class:`mathutils.Vector`\n"
269 "   :arg v3: Point3\n"
270 "   :type v3: :class:`mathutils.Vector`\n"
271 "   :arg v4: Point4 (optional)\n"
272 "   :type v4: :class:`mathutils.Vector`\n"
273 "   :rtype: :class:`mathutils.Vector`\n"
274 );
275 static PyObject *M_Geometry_normal(PyObject *UNUSED(self), PyObject *args)
276 {
277         VectorObject *vec1, *vec2, *vec3, *vec4;
278         float n[3];
279
280         if (PyTuple_GET_SIZE(args) == 3) {
281                 if (!PyArg_ParseTuple(args, "O!O!O!:normal",
282                                       &vector_Type, &vec1,
283                                       &vector_Type, &vec2,
284                                       &vector_Type, &vec3))
285                 {
286                         return NULL;
287                 }
288
289                 if (vec1->size != vec2->size || vec1->size != vec3->size) {
290                         PyErr_SetString(PyExc_ValueError,
291                                         "vectors must be of the same size");
292                         return NULL;
293                 }
294                 if (vec1->size < 3) {
295                         PyErr_SetString(PyExc_ValueError,
296                                         "2D vectors unsupported");
297                         return NULL;
298                 }
299
300                 if (BaseMath_ReadCallback(vec1) == -1 ||
301                     BaseMath_ReadCallback(vec2) == -1 ||
302                     BaseMath_ReadCallback(vec3) == -1)
303                 {
304                         return NULL;
305                 }
306
307                 normal_tri_v3(n, vec1->vec, vec2->vec, vec3->vec);
308         }
309         else {
310                 if (!PyArg_ParseTuple(args, "O!O!O!O!:normal",
311                                       &vector_Type, &vec1,
312                                       &vector_Type, &vec2,
313                                       &vector_Type, &vec3,
314                                       &vector_Type, &vec4))
315                 {
316                         return NULL;
317                 }
318                 if (vec1->size != vec2->size || vec1->size != vec3->size || vec1->size != vec4->size) {
319                         PyErr_SetString(PyExc_ValueError,
320                                         "vectors must be of the same size");
321                         return NULL;
322                 }
323                 if (vec1->size < 3) {
324                         PyErr_SetString(PyExc_ValueError,
325                                         "2D vectors unsupported");
326                         return NULL;
327                 }
328
329                 if (BaseMath_ReadCallback(vec1) == -1 ||
330                     BaseMath_ReadCallback(vec2) == -1 ||
331                     BaseMath_ReadCallback(vec3) == -1 ||
332                     BaseMath_ReadCallback(vec4) == -1)
333                 {
334                         return NULL;
335                 }
336
337                 normal_quad_v3(n, vec1->vec, vec2->vec, vec3->vec, vec4->vec);
338         }
339
340         return Vector_CreatePyObject(n, 3, Py_NEW, NULL);
341 }
342
343 //--------------------------------- AREA FUNCTIONS--------------------
344
345 PyDoc_STRVAR(M_Geometry_area_tri_doc,
346 ".. function:: area_tri(v1, v2, v3)\n"
347 "\n"
348 "   Returns the area size of the 2D or 3D triangle defined.\n"
349 "\n"
350 "   :arg v1: Point1\n"
351 "   :type v1: :class:`mathutils.Vector`\n"
352 "   :arg v2: Point2\n"
353 "   :type v2: :class:`mathutils.Vector`\n"
354 "   :arg v3: Point3\n"
355 "   :type v3: :class:`mathutils.Vector`\n"
356 "   :rtype: float\n"
357 );
358 static PyObject *M_Geometry_area_tri(PyObject *UNUSED(self), PyObject *args)
359 {
360         VectorObject *vec1, *vec2, *vec3;
361
362         if (!PyArg_ParseTuple(args, "O!O!O!:area_tri",
363                               &vector_Type, &vec1,
364                               &vector_Type, &vec2,
365                               &vector_Type, &vec3))
366         {
367                 return NULL;
368         }
369
370         if (vec1->size != vec2->size || vec1->size != vec3->size) {
371                 PyErr_SetString(PyExc_ValueError,
372                                 "vectors must be of the same size");
373                 return NULL;
374         }
375
376         if (BaseMath_ReadCallback(vec1) == -1 ||
377             BaseMath_ReadCallback(vec2) == -1 ||
378             BaseMath_ReadCallback(vec3) == -1)
379         {
380                 return NULL;
381         }
382
383         if (vec1->size == 3) {
384                 return PyFloat_FromDouble(area_tri_v3(vec1->vec, vec2->vec, vec3->vec));
385         }
386         else if (vec1->size == 2) {
387                 return PyFloat_FromDouble(area_tri_v2(vec1->vec, vec2->vec, vec3->vec));
388         }
389         else {
390                 PyErr_SetString(PyExc_ValueError,
391                                 "only 2D,3D vectors are supported");
392                 return NULL;
393         }
394 }
395
396
397 PyDoc_STRVAR(M_Geometry_intersect_line_line_2d_doc,
398 ".. function:: intersect_line_line_2d(lineA_p1, lineA_p2, lineB_p1, lineB_p2)\n"
399 "\n"
400 "   Takes 2 lines (as 4 vectors) and returns a vector for their point of intersection or None.\n"
401 "\n"
402 "   :arg lineA_p1: First point of the first line\n"
403 "   :type lineA_p1: :class:`mathutils.Vector`\n"
404 "   :arg lineA_p2: Second point of the first line\n"
405 "   :type lineA_p2: :class:`mathutils.Vector`\n"
406 "   :arg lineB_p1: First point of the second line\n"
407 "   :type lineB_p1: :class:`mathutils.Vector`\n"
408 "   :arg lineB_p2: Second point of the second line\n"
409 "   :type lineB_p2: :class:`mathutils.Vector`\n"
410 "   :return: The point of intersection or None when not found\n"
411 "   :rtype: :class:`mathutils.Vector` or None\n"
412 );
413 static PyObject *M_Geometry_intersect_line_line_2d(PyObject *UNUSED(self), PyObject *args)
414 {
415         VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
416         float vi[2];
417         if (!PyArg_ParseTuple(args, "O!O!O!O!:intersect_line_line_2d",
418                               &vector_Type, &line_a1,
419                               &vector_Type, &line_a2,
420                               &vector_Type, &line_b1,
421                               &vector_Type, &line_b2))
422         {
423                 return NULL;
424         }
425         
426         if (BaseMath_ReadCallback(line_a1) == -1 ||
427             BaseMath_ReadCallback(line_a2) == -1 ||
428             BaseMath_ReadCallback(line_b1) == -1 ||
429             BaseMath_ReadCallback(line_b2) == -1)
430         {
431                 return NULL;
432         }
433
434         if (isect_seg_seg_v2_point(line_a1->vec, line_a2->vec, line_b1->vec, line_b2->vec, vi) == 1) {
435                 return Vector_CreatePyObject(vi, 2, Py_NEW, NULL);
436         }
437         else {
438                 Py_RETURN_NONE;
439         }
440 }
441
442
443 PyDoc_STRVAR(M_Geometry_intersect_line_plane_doc,
444 ".. function:: intersect_line_plane(line_a, line_b, plane_co, plane_no, no_flip=False)\n"
445 "\n"
446 "   Calculate the intersection between a line (as 2 vectors) and a plane.\n"
447 "   Returns a vector for the intersection or None.\n"
448 "\n"
449 "   :arg line_a: First point of the first line\n"
450 "   :type line_a: :class:`mathutils.Vector`\n"
451 "   :arg line_b: Second point of the first line\n"
452 "   :type line_b: :class:`mathutils.Vector`\n"
453 "   :arg plane_co: A point on the plane\n"
454 "   :type plane_co: :class:`mathutils.Vector`\n"
455 "   :arg plane_no: The direction the plane is facing\n"
456 "   :type plane_no: :class:`mathutils.Vector`\n"
457 "   :arg no_flip: Always return an intersection on the directon defined bt line_a -> line_b\n"
458 "   :type no_flip: :boolean\n"
459 "   :return: The point of intersection or None when not found\n"
460 "   :rtype: :class:`mathutils.Vector` or None\n"
461 );
462 static PyObject *M_Geometry_intersect_line_plane(PyObject *UNUSED(self), PyObject *args)
463 {
464         VectorObject *line_a, *line_b, *plane_co, *plane_no;
465         int no_flip = 0;
466         float isect[3];
467         if (!PyArg_ParseTuple(args, "O!O!O!O!|i:intersect_line_plane",
468                               &vector_Type, &line_a,
469                               &vector_Type, &line_b,
470                               &vector_Type, &plane_co,
471                               &vector_Type, &plane_no,
472                               &no_flip))
473         {
474                 return NULL;
475         }
476
477         if (BaseMath_ReadCallback(line_a) == -1 ||
478             BaseMath_ReadCallback(line_b) == -1 ||
479             BaseMath_ReadCallback(plane_co) == -1 ||
480             BaseMath_ReadCallback(plane_no) == -1)
481         {
482                 return NULL;
483         }
484
485         if (ELEM4(2, line_a->size, line_b->size, plane_co->size, plane_no->size)) {
486                 PyErr_SetString(PyExc_ValueError,
487                                 "geometry.intersect_line_plane(...): "
488                                 " can't use 2D Vectors");
489                 return NULL;
490         }
491
492         if (isect_line_plane_v3(isect, line_a->vec, line_b->vec, plane_co->vec, plane_no->vec, no_flip) == 1) {
493                 return Vector_CreatePyObject(isect, 3, Py_NEW, NULL);
494         }
495         else {
496                 Py_RETURN_NONE;
497         }
498 }
499
500 PyDoc_STRVAR(M_Geometry_intersect_plane_plane_doc,
501 ".. function:: intersect_plane_plane(plane_a_co, plane_a_no, plane_b_co, plane_b_no)\n"
502 "\n"
503 "   Return the intersection between two planes\n"
504 "\n"
505 "   :arg plane_a_co: Point on the first plane\n"
506 "   :type plane_a_co: :class:`mathutils.Vector`\n"
507 "   :arg plane_a_no: Normal of the first plane\n"
508 "   :type plane_a_no: :class:`mathutils.Vector`\n"
509 "   :arg plane_b_co: Point on the second plane\n"
510 "   :type plane_b_co: :class:`mathutils.Vector`\n"
511 "   :arg plane_b_no: Normal of the second plane\n"
512 "   :type plane_b_no: :class:`mathutils.Vector`\n"
513 "   :return: The line of the intersection represented as a point and a vector\n"
514 "   :rtype: tuple pair of :class:`mathutils.Vector`\n"
515 );
516 static PyObject *M_Geometry_intersect_plane_plane(PyObject *UNUSED(self), PyObject *args)
517 {
518         PyObject *ret;
519         VectorObject *plane_a_co, *plane_a_no, *plane_b_co, *plane_b_no;
520
521         float isect_co[3];
522         float isect_no[3];
523
524         if (!PyArg_ParseTuple(args, "O!O!O!O!|i:intersect_plane_plane",
525                               &vector_Type, &plane_a_co,
526                               &vector_Type, &plane_a_no,
527                               &vector_Type, &plane_b_co,
528                               &vector_Type, &plane_b_no))
529         {
530                 return NULL;
531         }
532
533         if (BaseMath_ReadCallback(plane_a_co) == -1 ||
534             BaseMath_ReadCallback(plane_a_no) == -1 ||
535             BaseMath_ReadCallback(plane_b_co) == -1 ||
536             BaseMath_ReadCallback(plane_b_no) == -1)
537         {
538                 return NULL;
539         }
540
541         if (ELEM4(2, plane_a_co->size, plane_a_no->size, plane_b_co->size, plane_b_no->size)) {
542                 PyErr_SetString(PyExc_ValueError,
543                                 "geometry.intersect_plane_plane(...): "
544                                 " can't use 2D Vectors");
545                 return NULL;
546         }
547
548         isect_plane_plane_v3(isect_co, isect_no,
549                              plane_a_co->vec, plane_a_no->vec,
550                              plane_b_co->vec, plane_b_no->vec);
551
552         normalize_v3(isect_no);
553
554         ret = PyTuple_New(2);
555         PyTuple_SET_ITEM(ret, 0, Vector_CreatePyObject(isect_co, 3, Py_NEW, NULL));
556         PyTuple_SET_ITEM(ret, 1, Vector_CreatePyObject(isect_no, 3, Py_NEW, NULL));
557         return ret;
558 }
559
560 PyDoc_STRVAR(M_Geometry_intersect_line_sphere_doc,
561 ".. function:: intersect_line_sphere(line_a, line_b, sphere_co, sphere_radius, clip=True)\n"
562 "\n"
563 "   Takes a lines (as 2 vectors), a sphere as a point and a radius and\n"
564 "   returns the intersection\n"
565 "\n"
566 "   :arg line_a: First point of the first line\n"
567 "   :type line_a: :class:`mathutils.Vector`\n"
568 "   :arg line_b: Second point of the first line\n"
569 "   :type line_b: :class:`mathutils.Vector`\n"
570 "   :arg sphere_co: The center of the sphere\n"
571 "   :type sphere_co: :class:`mathutils.Vector`\n"
572 "   :arg sphere_radius: Radius of the sphere\n"
573 "   :type sphere_radius: sphere_radius\n"
574 "   :return: The intersection points as a pair of vectors or None when there is no intersection\n"
575 "   :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n"
576 );
577 static PyObject *M_Geometry_intersect_line_sphere(PyObject *UNUSED(self), PyObject *args)
578 {
579         VectorObject *line_a, *line_b, *sphere_co;
580         float sphere_radius;
581         int clip = TRUE;
582
583         float isect_a[3];
584         float isect_b[3];
585
586         if (!PyArg_ParseTuple(args, "O!O!O!f|i:intersect_line_sphere",
587                               &vector_Type, &line_a,
588                               &vector_Type, &line_b,
589                               &vector_Type, &sphere_co,
590                               &sphere_radius, &clip))
591         {
592                 return NULL;
593         }
594
595         if (BaseMath_ReadCallback(line_a) == -1 ||
596             BaseMath_ReadCallback(line_b) == -1 ||
597             BaseMath_ReadCallback(sphere_co) == -1)
598         {
599                 return NULL;
600         }
601
602         if (ELEM3(2, line_a->size, line_b->size, sphere_co->size)) {
603                 PyErr_SetString(PyExc_ValueError,
604                                 "geometry.intersect_line_sphere(...): "
605                                 " can't use 2D Vectors");
606                 return NULL;
607         }
608         else {
609                 short use_a = TRUE;
610                 short use_b = TRUE;
611                 float lambda;
612
613                 PyObject *ret = PyTuple_New(2);
614
615                 switch (isect_line_sphere_v3(line_a->vec, line_b->vec, sphere_co->vec, sphere_radius, isect_a, isect_b)) {
616                         case 1:
617                                 if (!(!clip || (((lambda = line_point_factor_v3(isect_a, line_a->vec, line_b->vec)) >= 0.0f) && (lambda <= 1.0f)))) use_a = FALSE;
618                                 use_b = FALSE;
619                                 break;
620                         case 2:
621                                 if (!(!clip || (((lambda = line_point_factor_v3(isect_a, line_a->vec, line_b->vec)) >= 0.0f) && (lambda <= 1.0f)))) use_a = FALSE;
622                                 if (!(!clip || (((lambda = line_point_factor_v3(isect_b, line_a->vec, line_b->vec)) >= 0.0f) && (lambda <= 1.0f)))) use_b = FALSE;
623                                 break;
624                         default:
625                                 use_a = FALSE;
626                                 use_b = FALSE;
627                 }
628
629                 if (use_a) { PyTuple_SET_ITEM(ret, 0,  Vector_CreatePyObject(isect_a, 3, Py_NEW, NULL)); }
630                 else       { PyTuple_SET_ITEM(ret, 0,  Py_None); Py_INCREF(Py_None); }
631
632                 if (use_b) { PyTuple_SET_ITEM(ret, 1,  Vector_CreatePyObject(isect_b, 3, Py_NEW, NULL)); }
633                 else       { PyTuple_SET_ITEM(ret, 1,  Py_None); Py_INCREF(Py_None); }
634
635                 return ret;
636         }
637 }
638
639 /* keep in sync with M_Geometry_intersect_line_sphere */
640 PyDoc_STRVAR(M_Geometry_intersect_line_sphere_2d_doc,
641 ".. function:: intersect_line_sphere_2d(line_a, line_b, sphere_co, sphere_radius, clip=True)\n"
642 "\n"
643 "   Takes a lines (as 2 vectors), a sphere as a point and a radius and\n"
644 "   returns the intersection\n"
645 "\n"
646 "   :arg line_a: First point of the first line\n"
647 "   :type line_a: :class:`mathutils.Vector`\n"
648 "   :arg line_b: Second point of the first line\n"
649 "   :type line_b: :class:`mathutils.Vector`\n"
650 "   :arg sphere_co: The center of the sphere\n"
651 "   :type sphere_co: :class:`mathutils.Vector`\n"
652 "   :arg sphere_radius: Radius of the sphere\n"
653 "   :type sphere_radius: sphere_radius\n"
654 "   :return: The intersection points as a pair of vectors or None when there is no intersection\n"
655 "   :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n"
656 );
657 static PyObject *M_Geometry_intersect_line_sphere_2d(PyObject *UNUSED(self), PyObject *args)
658 {
659         VectorObject *line_a, *line_b, *sphere_co;
660         float sphere_radius;
661         int clip = TRUE;
662
663         float isect_a[3];
664         float isect_b[3];
665
666         if (!PyArg_ParseTuple(args, "O!O!O!f|i:intersect_line_sphere_2d",
667                               &vector_Type, &line_a,
668                               &vector_Type, &line_b,
669                               &vector_Type, &sphere_co,
670                               &sphere_radius, &clip))
671         {
672                 return NULL;
673         }
674
675         if (BaseMath_ReadCallback(line_a) == -1 ||
676             BaseMath_ReadCallback(line_b) == -1 ||
677             BaseMath_ReadCallback(sphere_co) == -1)
678         {
679                 return NULL;
680         }
681         else {
682                 short use_a = TRUE;
683                 short use_b = TRUE;
684                 float lambda;
685
686                 PyObject *ret = PyTuple_New(2);
687
688                 switch (isect_line_sphere_v2(line_a->vec, line_b->vec, sphere_co->vec, sphere_radius, isect_a, isect_b)) {
689                         case 1:
690                                 if (!(!clip || (((lambda = line_point_factor_v2(isect_a, line_a->vec, line_b->vec)) >= 0.0f) && (lambda <= 1.0f)))) use_a = FALSE;
691                                 use_b = FALSE;
692                                 break;
693                         case 2:
694                                 if (!(!clip || (((lambda = line_point_factor_v2(isect_a, line_a->vec, line_b->vec)) >= 0.0f) && (lambda <= 1.0f)))) use_a = FALSE;
695                                 if (!(!clip || (((lambda = line_point_factor_v2(isect_b, line_a->vec, line_b->vec)) >= 0.0f) && (lambda <= 1.0f)))) use_b = FALSE;
696                                 break;
697                         default:
698                                 use_a = FALSE;
699                                 use_b = FALSE;
700                 }
701
702                 if (use_a) { PyTuple_SET_ITEM(ret, 0,  Vector_CreatePyObject(isect_a, 2, Py_NEW, NULL)); }
703                 else       { PyTuple_SET_ITEM(ret, 0,  Py_None); Py_INCREF(Py_None); }
704
705                 if (use_b) { PyTuple_SET_ITEM(ret, 1,  Vector_CreatePyObject(isect_b, 2, Py_NEW, NULL)); }
706                 else       { PyTuple_SET_ITEM(ret, 1,  Py_None); Py_INCREF(Py_None); }
707
708                 return ret;
709         }
710 }
711
712 PyDoc_STRVAR(M_Geometry_intersect_point_line_doc,
713 ".. function:: intersect_point_line(pt, line_p1, line_p2)\n"
714 "\n"
715 "   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"
716 "\n"
717 "   :arg pt: Point\n"
718 "   :type pt: :class:`mathutils.Vector`\n"
719 "   :arg line_p1: First point of the line\n"
720 "   :type line_p1: :class:`mathutils.Vector`\n"
721 "   :arg line_p1: Second point of the line\n"
722 "   :type line_p1: :class:`mathutils.Vector`\n"
723 "   :rtype: (:class:`mathutils.Vector`, float)\n"
724 );
725 static PyObject *M_Geometry_intersect_point_line(PyObject *UNUSED(self), PyObject *args)
726 {
727         VectorObject *pt, *line_1, *line_2;
728         float pt_in[3], pt_out[3], l1[3], l2[3];
729         float lambda;
730         PyObject *ret;
731         
732         if (!PyArg_ParseTuple(args, "O!O!O!:intersect_point_line",
733                               &vector_Type, &pt,
734                               &vector_Type, &line_1,
735                               &vector_Type, &line_2))
736         {
737                 return NULL;
738         }
739
740         if (BaseMath_ReadCallback(pt) == -1 ||
741             BaseMath_ReadCallback(line_1) == -1 ||
742             BaseMath_ReadCallback(line_2) == -1)
743         {
744                 return NULL;
745         }
746
747         /* accept 2d verts */
748         if (pt->size == 3) {     copy_v3_v3(pt_in, pt->vec); }
749         else { pt_in[2] = 0.0f;  copy_v2_v2(pt_in, pt->vec); }
750         
751         if (line_1->size == 3) { copy_v3_v3(l1, line_1->vec); }
752         else { l1[2] = 0.0f;     copy_v2_v2(l1, line_1->vec); }
753         
754         if (line_2->size == 3) { copy_v3_v3(l2, line_2->vec); }
755         else { l2[2] = 0.0f;     copy_v2_v2(l2, line_2->vec); }
756         
757         /* do the calculation */
758         lambda = closest_to_line_v3(pt_out, pt_in, l1, l2);
759         
760         ret = PyTuple_New(2);
761         PyTuple_SET_ITEM(ret, 0, Vector_CreatePyObject(pt_out, 3, Py_NEW, NULL));
762         PyTuple_SET_ITEM(ret, 1, PyFloat_FromDouble(lambda));
763         return ret;
764 }
765
766 PyDoc_STRVAR(M_Geometry_intersect_point_tri_2d_doc,
767 ".. function:: intersect_point_tri_2d(pt, tri_p1, tri_p2, tri_p3)\n"
768 "\n"
769 "   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"
770 "\n"
771 "   :arg pt: Point\n"
772 "   :type v1: :class:`mathutils.Vector`\n"
773 "   :arg tri_p1: First point of the triangle\n"
774 "   :type tri_p1: :class:`mathutils.Vector`\n"
775 "   :arg tri_p2: Second point of the triangle\n"
776 "   :type tri_p2: :class:`mathutils.Vector`\n"
777 "   :arg tri_p3: Third point of the triangle\n"
778 "   :type tri_p3: :class:`mathutils.Vector`\n"
779 "   :rtype: int\n"
780 );
781 static PyObject *M_Geometry_intersect_point_tri_2d(PyObject *UNUSED(self), PyObject *args)
782 {
783         VectorObject *pt_vec, *tri_p1, *tri_p2, *tri_p3;
784         
785         if (!PyArg_ParseTuple(args, "O!O!O!O!:intersect_point_tri_2d",
786                               &vector_Type, &pt_vec,
787                               &vector_Type, &tri_p1,
788                               &vector_Type, &tri_p2,
789                               &vector_Type, &tri_p3))
790         {
791                 return NULL;
792         }
793         
794         if (BaseMath_ReadCallback(pt_vec) == -1 ||
795             BaseMath_ReadCallback(tri_p1) == -1 ||
796             BaseMath_ReadCallback(tri_p2) == -1 ||
797             BaseMath_ReadCallback(tri_p3) == -1)
798         {
799                 return NULL;
800         }
801
802         return PyLong_FromLong(isect_point_tri_v2(pt_vec->vec, tri_p1->vec, tri_p2->vec, tri_p3->vec));
803 }
804
805 PyDoc_STRVAR(M_Geometry_intersect_point_quad_2d_doc,
806 ".. function:: intersect_point_quad_2d(pt, quad_p1, quad_p2, quad_p3, quad_p4)\n"
807 "\n"
808 "   Takes 5 vectors (using only the x and y coordinates): one is the point and the next 4 define the quad, \n"
809 "   only the x and y are used from the vectors. Returns 1 if the point is within the quad, otherwise 0.\n"
810 "   Works only with convex quads without singular edges."
811 "\n"
812 "   :arg pt: Point\n"
813 "   :type pt: :class:`mathutils.Vector`\n"
814 "   :arg quad_p1: First point of the quad\n"
815 "   :type quad_p1: :class:`mathutils.Vector`\n"
816 "   :arg quad_p2: Second point of the quad\n"
817 "   :type quad_p2: :class:`mathutils.Vector`\n"
818 "   :arg quad_p3: Third point of the quad\n"
819 "   :type quad_p3: :class:`mathutils.Vector`\n"
820 "   :arg quad_p4: Forth point of the quad\n"
821 "   :type quad_p4: :class:`mathutils.Vector`\n"
822 "   :rtype: int\n"
823 );
824 static PyObject *M_Geometry_intersect_point_quad_2d(PyObject *UNUSED(self), PyObject *args)
825 {
826         VectorObject *pt_vec, *quad_p1, *quad_p2, *quad_p3, *quad_p4;
827         
828         if (!PyArg_ParseTuple(args, "O!O!O!O!O!:intersect_point_quad_2d",
829                               &vector_Type, &pt_vec,
830                               &vector_Type, &quad_p1,
831                               &vector_Type, &quad_p2,
832                               &vector_Type, &quad_p3,
833                               &vector_Type, &quad_p4))
834         {
835                 return NULL;
836         }
837
838         if (BaseMath_ReadCallback(pt_vec)  == -1 ||
839             BaseMath_ReadCallback(quad_p1) == -1 ||
840             BaseMath_ReadCallback(quad_p2) == -1 ||
841             BaseMath_ReadCallback(quad_p3) == -1 ||
842             BaseMath_ReadCallback(quad_p4) == -1)
843         {
844                 return NULL;
845         }
846
847         return PyLong_FromLong(isect_point_quad_v2(pt_vec->vec, quad_p1->vec, quad_p2->vec, quad_p3->vec, quad_p4->vec));
848 }
849
850 PyDoc_STRVAR(M_Geometry_distance_point_to_plane_doc,
851 ".. function:: distance_point_to_plane(pt, plane_co, plane_no)\n"
852 "\n"
853 "   Returns the signed distance between a point and a plane "
854 "   (negative when below the normal).\n"
855 "\n"
856 "   :arg pt: Point\n"
857 "   :type pt: :class:`mathutils.Vector`\n"
858 "   :arg plane_co: First point of the quad\n"
859 "   :type plane_co: :class:`mathutils.Vector`\n"
860 "   :arg plane_no: Second point of the quad\n"
861 "   :type plane_no: :class:`mathutils.Vector`\n"
862 "   :rtype: float\n"
863 );
864 static PyObject *M_Geometry_distance_point_to_plane(PyObject *UNUSED(self), PyObject *args)
865 {
866         VectorObject *pt, *plene_co, *plane_no;
867
868         if (!PyArg_ParseTuple(args, "O!O!O!:distance_point_to_plane",
869                               &vector_Type, &pt,
870                               &vector_Type, &plene_co,
871                               &vector_Type, &plane_no))
872         {
873                 return NULL;
874         }
875
876         if (BaseMath_ReadCallback(pt) == -1 ||
877             BaseMath_ReadCallback(plene_co) == -1 ||
878             BaseMath_ReadCallback(plane_no) == -1)
879         {
880                 return NULL;
881         }
882
883         return PyFloat_FromDouble(dist_to_plane_v3(pt->vec, plene_co->vec, plane_no->vec));
884 }
885
886 PyDoc_STRVAR(M_Geometry_barycentric_transform_doc,
887 ".. function:: barycentric_transform(point, tri_a1, tri_a2, tri_a3, tri_b1, tri_b2, tri_b3)\n"
888 "\n"
889 "   Return a transformed point, the transformation is defined by 2 triangles.\n"
890 "\n"
891 "   :arg point: The point to transform.\n"
892 "   :type point: :class:`mathutils.Vector`\n"
893 "   :arg tri_a1: source triangle vertex.\n"
894 "   :type tri_a1: :class:`mathutils.Vector`\n"
895 "   :arg tri_a2: source triangle vertex.\n"
896 "   :type tri_a2: :class:`mathutils.Vector`\n"
897 "   :arg tri_a3: source triangle vertex.\n"
898 "   :type tri_a3: :class:`mathutils.Vector`\n"
899 "   :arg tri_a1: target triangle vertex.\n"
900 "   :type tri_a1: :class:`mathutils.Vector`\n"
901 "   :arg tri_a2: target triangle vertex.\n"
902 "   :type tri_a2: :class:`mathutils.Vector`\n"
903 "   :arg tri_a3: target triangle vertex.\n"
904 "   :type tri_a3: :class:`mathutils.Vector`\n"
905 "   :return: The transformed point\n"
906 "   :rtype: :class:`mathutils.Vector`'s\n"
907 );
908 static PyObject *M_Geometry_barycentric_transform(PyObject *UNUSED(self), PyObject *args)
909 {
910         VectorObject *vec_pt;
911         VectorObject *vec_t1_tar, *vec_t2_tar, *vec_t3_tar;
912         VectorObject *vec_t1_src, *vec_t2_src, *vec_t3_src;
913         float vec[3];
914
915         if (!PyArg_ParseTuple(args, "O!O!O!O!O!O!O!:barycentric_transform",
916                               &vector_Type, &vec_pt,
917                               &vector_Type, &vec_t1_src,
918                               &vector_Type, &vec_t2_src,
919                               &vector_Type, &vec_t3_src,
920                               &vector_Type, &vec_t1_tar,
921                               &vector_Type, &vec_t2_tar,
922                               &vector_Type, &vec_t3_tar))
923         {
924                 return NULL;
925         }
926
927         if (vec_pt->size != 3 ||
928             vec_t1_src->size != 3 ||
929             vec_t2_src->size != 3 ||
930             vec_t3_src->size != 3 ||
931             vec_t1_tar->size != 3 ||
932             vec_t2_tar->size != 3 ||
933             vec_t3_tar->size != 3)
934         {
935                 PyErr_SetString(PyExc_ValueError,
936                                 "One of more of the vector arguments wasn't a 3D vector");
937                 return NULL;
938         }
939
940         barycentric_transform(vec, vec_pt->vec,
941                               vec_t1_tar->vec, vec_t2_tar->vec, vec_t3_tar->vec,
942                               vec_t1_src->vec, vec_t2_src->vec, vec_t3_src->vec);
943
944         return Vector_CreatePyObject(vec, 3, Py_NEW, NULL);
945 }
946
947 #ifndef MATH_STANDALONE
948
949 PyDoc_STRVAR(M_Geometry_interpolate_bezier_doc,
950 ".. function:: interpolate_bezier(knot1, handle1, handle2, knot2, resolution)\n"
951 "\n"
952 "   Interpolate a bezier spline segment.\n"
953 "\n"
954 "   :arg knot1: First bezier spline point.\n"
955 "   :type knot1: :class:`mathutils.Vector`\n"
956 "   :arg handle1: First bezier spline handle.\n"
957 "   :type handle1: :class:`mathutils.Vector`\n"
958 "   :arg handle2: Second bezier spline handle.\n"
959 "   :type handle2: :class:`mathutils.Vector`\n"
960 "   :arg knot2: Second bezier spline point.\n"
961 "   :type knot2: :class:`mathutils.Vector`\n"
962 "   :arg resolution: Number of points to return.\n"
963 "   :type resolution: int\n"
964 "   :return: The interpolated points\n"
965 "   :rtype: list of :class:`mathutils.Vector`'s\n"
966 );
967 static PyObject *M_Geometry_interpolate_bezier(PyObject *UNUSED(self), PyObject *args)
968 {
969         VectorObject *vec_k1, *vec_h1, *vec_k2, *vec_h2;
970         int resolu;
971         int dims;
972         int i;
973         float *coord_array, *fp;
974         PyObject *list;
975
976         float k1[4] = {0.0, 0.0, 0.0, 0.0};
977         float h1[4] = {0.0, 0.0, 0.0, 0.0};
978         float k2[4] = {0.0, 0.0, 0.0, 0.0};
979         float h2[4] = {0.0, 0.0, 0.0, 0.0};
980
981
982         if (!PyArg_ParseTuple(args, "O!O!O!O!i:interpolate_bezier",
983                               &vector_Type, &vec_k1,
984                               &vector_Type, &vec_h1,
985                               &vector_Type, &vec_h2,
986                               &vector_Type, &vec_k2, &resolu))
987         {
988                 return NULL;
989         }
990
991         if (resolu <= 1) {
992                 PyErr_SetString(PyExc_ValueError,
993                                 "resolution must be 2 or over");
994                 return NULL;
995         }
996
997         if (BaseMath_ReadCallback(vec_k1) == -1 ||
998             BaseMath_ReadCallback(vec_h1) == -1 ||
999             BaseMath_ReadCallback(vec_k2) == -1 ||
1000             BaseMath_ReadCallback(vec_h2) == -1)
1001         {
1002                 return NULL;
1003         }
1004
1005         dims = MAX4(vec_k1->size, vec_h1->size, vec_h2->size, vec_k2->size);
1006
1007         for (i = 0; i < vec_k1->size; i++) k1[i] = vec_k1->vec[i];
1008         for (i = 0; i < vec_h1->size; i++) h1[i] = vec_h1->vec[i];
1009         for (i = 0; i < vec_k2->size; i++) k2[i] = vec_k2->vec[i];
1010         for (i = 0; i < vec_h2->size; i++) h2[i] = vec_h2->vec[i];
1011
1012         coord_array = MEM_callocN(dims * (resolu) * sizeof(float), "interpolate_bezier");
1013         for (i = 0; i < dims; i++) {
1014                 BKE_curve_forward_diff_bezier(k1[i], h1[i], h2[i], k2[i], coord_array + i, resolu - 1, sizeof(float) * dims);
1015         }
1016
1017         list = PyList_New(resolu);
1018         fp = coord_array;
1019         for (i = 0; i < resolu; i++, fp = fp + dims) {
1020                 PyList_SET_ITEM(list, i, Vector_CreatePyObject(fp, dims, Py_NEW, NULL));
1021         }
1022         MEM_freeN(coord_array);
1023         return list;
1024 }
1025
1026
1027 PyDoc_STRVAR(M_Geometry_tessellate_polygon_doc,
1028 ".. function:: tessellate_polygon(veclist_list)\n"
1029 "\n"
1030 "   Takes a list of polylines (each point a vector) and returns the point indices for a polyline filled with triangles.\n"
1031 "\n"
1032 "   :arg veclist_list: list of polylines\n"
1033 "   :rtype: list\n"
1034 );
1035 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
1036 static PyObject *M_Geometry_tessellate_polygon(PyObject *UNUSED(self), PyObject *polyLineSeq)
1037 {
1038         PyObject *tri_list; /*return this list of tri's */
1039         PyObject *polyLine, *polyVec;
1040         int i, len_polylines, len_polypoints, ls_error = 0;
1041
1042         /* display listbase */
1043         ListBase dispbase = {NULL, NULL};
1044         DispList *dl;
1045         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
1046         int index, *dl_face, totpoints = 0;
1047
1048         if (!PySequence_Check(polyLineSeq)) {
1049                 PyErr_SetString(PyExc_TypeError,
1050                                 "expected a sequence of poly lines");
1051                 return NULL;
1052         }
1053
1054         len_polylines = PySequence_Size(polyLineSeq);
1055
1056         for (i = 0; i < len_polylines; i++) {
1057                 polyLine = PySequence_GetItem(polyLineSeq, i);
1058                 if (!PySequence_Check(polyLine)) {
1059                         BKE_displist_free(&dispbase);
1060                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
1061                         PyErr_SetString(PyExc_TypeError,
1062                                         "One or more of the polylines is not a sequence of mathutils.Vector's");
1063                         return NULL;
1064                 }
1065
1066                 len_polypoints = PySequence_Size(polyLine);
1067                 if (len_polypoints > 0) { /* don't bother adding edges as polylines */
1068 #if 0
1069                         if (EXPP_check_sequence_consistency(polyLine, &vector_Type) != 1) {
1070                                 freedisplist(&dispbase);
1071                                 Py_DECREF(polyLine);
1072                                 PyErr_SetString(PyExc_TypeError,
1073                                                 "A point in one of the polylines is not a mathutils.Vector type");
1074                                 return NULL;
1075                         }
1076 #endif
1077                         dl = MEM_callocN(sizeof(DispList), "poly disp");
1078                         BLI_addtail(&dispbase, dl);
1079                         dl->type = DL_INDEX3;
1080                         dl->nr = len_polypoints;
1081                         dl->type = DL_POLY;
1082                         dl->parts = 1; /* no faces, 1 edge loop */
1083                         dl->col = 0; /* no material */
1084                         dl->verts = fp = MEM_callocN(sizeof(float) * 3 * len_polypoints, "dl verts");
1085                         dl->index = MEM_callocN(sizeof(int) * 3 * len_polypoints, "dl index");
1086
1087                         for (index = 0; index < len_polypoints; index++, fp += 3) {
1088                                 polyVec = PySequence_GetItem(polyLine, index);
1089                                 if (VectorObject_Check(polyVec)) {
1090
1091                                         if (BaseMath_ReadCallback((VectorObject *)polyVec) == -1)
1092                                                 ls_error = 1;
1093
1094                                         fp[0] = ((VectorObject *)polyVec)->vec[0];
1095                                         fp[1] = ((VectorObject *)polyVec)->vec[1];
1096                                         if (((VectorObject *)polyVec)->size > 2)
1097                                                 fp[2] = ((VectorObject *)polyVec)->vec[2];
1098                                         else
1099                                                 fp[2] = 0.0f;  /* if its a 2d vector then set the z to be zero */
1100                                 }
1101                                 else {
1102                                         ls_error = 1;
1103                                 }
1104
1105                                 totpoints++;
1106                                 Py_DECREF(polyVec);
1107                         }
1108                 }
1109                 Py_DECREF(polyLine);
1110         }
1111
1112         if (ls_error) {
1113                 BKE_displist_free(&dispbase); /* possible some dl was allocated */
1114                 PyErr_SetString(PyExc_TypeError,
1115                                 "A point in one of the polylines "
1116                                 "is not a mathutils.Vector type");
1117                 return NULL;
1118         }
1119         else if (totpoints) {
1120                 /* now make the list to return */
1121                 BKE_displist_fill(&dispbase, &dispbase, 0);
1122
1123                 /* The faces are stored in a new DisplayList
1124                  * thats added to the head of the listbase */
1125                 dl = dispbase.first;
1126
1127                 tri_list = PyList_New(dl->parts);
1128                 if (!tri_list) {
1129                         BKE_displist_free(&dispbase);
1130                         PyErr_SetString(PyExc_RuntimeError,
1131                                         "failed to make a new list");
1132                         return NULL;
1133                 }
1134
1135                 index = 0;
1136                 dl_face = dl->index;
1137                 while (index < dl->parts) {
1138                         PyList_SET_ITEM(tri_list, index, Py_BuildValue("iii", dl_face[0], dl_face[1], dl_face[2]));
1139                         dl_face += 3;
1140                         index++;
1141                 }
1142                 BKE_displist_free(&dispbase);
1143         }
1144         else {
1145                 /* no points, do this so scripts don't barf */
1146                 BKE_displist_free(&dispbase); /* possible some dl was allocated */
1147                 tri_list = PyList_New(0);
1148         }
1149
1150         return tri_list;
1151 }
1152
1153
1154 static int boxPack_FromPyObject(PyObject *value, BoxPack **boxarray)
1155 {
1156         Py_ssize_t len, i;
1157         PyObject *list_item, *item_1, *item_2;
1158         BoxPack *box;
1159
1160
1161         /* Error checking must already be done */
1162         if (!PyList_Check(value)) {
1163                 PyErr_SetString(PyExc_TypeError,
1164                                 "can only back a list of [x, y, w, h]");
1165                 return -1;
1166         }
1167
1168         len = PyList_GET_SIZE(value);
1169
1170         *boxarray = MEM_mallocN(len * sizeof(BoxPack), "BoxPack box");
1171
1172
1173         for (i = 0; i < len; i++) {
1174                 list_item = PyList_GET_ITEM(value, i);
1175                 if (!PyList_Check(list_item) || PyList_GET_SIZE(list_item) < 4) {
1176                         MEM_freeN(*boxarray);
1177                         PyErr_SetString(PyExc_TypeError,
1178                                         "can only pack a list of [x, y, w, h]");
1179                         return -1;
1180                 }
1181
1182                 box = (*boxarray) + i;
1183
1184                 item_1 = PyList_GET_ITEM(list_item, 2);
1185                 item_2 = PyList_GET_ITEM(list_item, 3);
1186
1187                 box->w =  (float)PyFloat_AsDouble(item_1);
1188                 box->h =  (float)PyFloat_AsDouble(item_2);
1189                 box->index = i;
1190
1191                 /* accounts for error case too and overwrites with own error */
1192                 if (box->w < 0.0f || box->h < 0.0f) {
1193                         MEM_freeN(*boxarray);
1194                         PyErr_SetString(PyExc_TypeError,
1195                                         "error parsing width and height values from list: "
1196                                         "[x, y, w, h], not numbers or below zero");
1197                         return -1;
1198                 }
1199
1200                 /* verts will be added later */
1201         }
1202         return 0;
1203 }
1204
1205 static void boxPack_ToPyObject(PyObject *value, BoxPack **boxarray)
1206 {
1207         Py_ssize_t len, i;
1208         PyObject *list_item;
1209         BoxPack *box;
1210
1211         len = PyList_GET_SIZE(value);
1212
1213         for (i = 0; i < len; i++) {
1214                 box = (*boxarray) + i;
1215                 list_item = PyList_GET_ITEM(value, box->index);
1216                 PyList_SET_ITEM(list_item, 0, PyFloat_FromDouble(box->x));
1217                 PyList_SET_ITEM(list_item, 1, PyFloat_FromDouble(box->y));
1218         }
1219         MEM_freeN(*boxarray);
1220 }
1221
1222 PyDoc_STRVAR(M_Geometry_box_pack_2d_doc,
1223 ".. function:: box_pack_2d(boxes)\n"
1224 "\n"
1225 "   Returns the normal of the 3D tri or quad.\n"
1226 "\n"
1227 "   :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"
1228 "   :type boxes: list\n"
1229 "   :return: the width and height of the packed bounding box\n"
1230 "   :rtype: tuple, pair of floats\n"
1231 );
1232 static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlist)
1233 {
1234         float tot_width = 0.0f, tot_height = 0.0f;
1235         Py_ssize_t len;
1236
1237         PyObject *ret;
1238
1239         if (!PyList_Check(boxlist)) {
1240                 PyErr_SetString(PyExc_TypeError,
1241                                 "expected a list of boxes [[x, y, w, h], ... ]");
1242                 return NULL;
1243         }
1244
1245         len = PyList_GET_SIZE(boxlist);
1246         if (len) {
1247                 BoxPack *boxarray = NULL;
1248                 if (boxPack_FromPyObject(boxlist, &boxarray) == -1) {
1249                         return NULL; /* exception set */
1250                 }
1251
1252                 /* Non Python function */
1253                 BLI_box_pack_2D(boxarray, len, &tot_width, &tot_height);
1254
1255                 boxPack_ToPyObject(boxlist, &boxarray);
1256         }
1257
1258         ret = PyTuple_New(2);
1259         PyTuple_SET_ITEM(ret, 0, PyFloat_FromDouble(tot_width));
1260         PyTuple_SET_ITEM(ret, 1, PyFloat_FromDouble(tot_width));
1261         return ret;
1262 }
1263
1264 #endif /* MATH_STANDALONE */
1265
1266
1267 static PyMethodDef M_Geometry_methods[] = {
1268         {"intersect_ray_tri", (PyCFunction) M_Geometry_intersect_ray_tri, METH_VARARGS, M_Geometry_intersect_ray_tri_doc},
1269         {"intersect_point_line", (PyCFunction) M_Geometry_intersect_point_line, METH_VARARGS, M_Geometry_intersect_point_line_doc},
1270         {"intersect_point_tri_2d", (PyCFunction) M_Geometry_intersect_point_tri_2d, METH_VARARGS, M_Geometry_intersect_point_tri_2d_doc},
1271         {"intersect_point_quad_2d", (PyCFunction) M_Geometry_intersect_point_quad_2d, METH_VARARGS, M_Geometry_intersect_point_quad_2d_doc},
1272         {"intersect_line_line", (PyCFunction) M_Geometry_intersect_line_line, METH_VARARGS, M_Geometry_intersect_line_line_doc},
1273         {"intersect_line_line_2d", (PyCFunction) M_Geometry_intersect_line_line_2d, METH_VARARGS, M_Geometry_intersect_line_line_2d_doc},
1274         {"intersect_line_plane", (PyCFunction) M_Geometry_intersect_line_plane, METH_VARARGS, M_Geometry_intersect_line_plane_doc},
1275         {"intersect_plane_plane", (PyCFunction) M_Geometry_intersect_plane_plane, METH_VARARGS, M_Geometry_intersect_plane_plane_doc},
1276         {"intersect_line_sphere", (PyCFunction) M_Geometry_intersect_line_sphere, METH_VARARGS, M_Geometry_intersect_line_sphere_doc},
1277         {"intersect_line_sphere_2d", (PyCFunction) M_Geometry_intersect_line_sphere_2d, METH_VARARGS, M_Geometry_intersect_line_sphere_2d_doc},
1278         {"distance_point_to_plane", (PyCFunction) M_Geometry_distance_point_to_plane, METH_VARARGS, M_Geometry_distance_point_to_plane_doc},
1279         {"area_tri", (PyCFunction) M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc},
1280         {"normal", (PyCFunction) M_Geometry_normal, METH_VARARGS, M_Geometry_normal_doc},
1281         {"barycentric_transform", (PyCFunction) M_Geometry_barycentric_transform, METH_VARARGS, M_Geometry_barycentric_transform_doc},
1282 #ifndef MATH_STANDALONE
1283         {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc},
1284         {"tessellate_polygon", (PyCFunction) M_Geometry_tessellate_polygon, METH_O, M_Geometry_tessellate_polygon_doc},
1285         {"box_pack_2d", (PyCFunction) M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc},
1286 #endif
1287         {NULL, NULL, 0, NULL}
1288 };
1289
1290 static struct PyModuleDef M_Geometry_module_def = {
1291         PyModuleDef_HEAD_INIT,
1292         "mathutils.geometry",  /* m_name */
1293         M_Geometry_doc,  /* m_doc */
1294         0,  /* m_size */
1295         M_Geometry_methods,  /* m_methods */
1296         NULL,  /* m_reload */
1297         NULL,  /* m_traverse */
1298         NULL,  /* m_clear */
1299         NULL,  /* m_free */
1300 };
1301
1302 /*----------------------------MODULE INIT-------------------------*/
1303 PyMODINIT_FUNC PyInit_mathutils_geometry(void)
1304 {
1305         PyObject *submodule = PyModule_Create(&M_Geometry_module_def);
1306         return submodule;
1307 }