svn merge ^/trunk/blender -r45927:HEAD --accept=theirs-full
[blender.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 "\n"
811 "   :arg pt: Point\n"
812 "   :type pt: :class:`mathutils.Vector`\n"
813 "   :arg quad_p1: First point of the quad\n"
814 "   :type quad_p1: :class:`mathutils.Vector`\n"
815 "   :arg quad_p2: Second point of the quad\n"
816 "   :type quad_p2: :class:`mathutils.Vector`\n"
817 "   :arg quad_p3: Third point of the quad\n"
818 "   :type quad_p3: :class:`mathutils.Vector`\n"
819 "   :arg quad_p4: Forth point of the quad\n"
820 "   :type quad_p4: :class:`mathutils.Vector`\n"
821 "   :rtype: int\n"
822 );
823 static PyObject *M_Geometry_intersect_point_quad_2d(PyObject *UNUSED(self), PyObject *args)
824 {
825         VectorObject *pt_vec, *quad_p1, *quad_p2, *quad_p3, *quad_p4;
826         
827         if (!PyArg_ParseTuple(args, "O!O!O!O!O!:intersect_point_quad_2d",
828                               &vector_Type, &pt_vec,
829                               &vector_Type, &quad_p1,
830                               &vector_Type, &quad_p2,
831                               &vector_Type, &quad_p3,
832                               &vector_Type, &quad_p4))
833         {
834                 return NULL;
835         }
836
837         if (BaseMath_ReadCallback(pt_vec)  == -1 ||
838             BaseMath_ReadCallback(quad_p1) == -1 ||
839             BaseMath_ReadCallback(quad_p2) == -1 ||
840             BaseMath_ReadCallback(quad_p3) == -1 ||
841             BaseMath_ReadCallback(quad_p4) == -1)
842         {
843                 return NULL;
844         }
845
846         return PyLong_FromLong(isect_point_quad_v2(pt_vec->vec, quad_p1->vec, quad_p2->vec, quad_p3->vec, quad_p4->vec));
847 }
848
849 PyDoc_STRVAR(M_Geometry_distance_point_to_plane_doc,
850 ".. function:: distance_point_to_plane(pt, plane_co, plane_no)\n"
851 "\n"
852 "   Returns the signed distance between a point and a plane "
853 "   (negative when below the normal).\n"
854 "\n"
855 "   :arg pt: Point\n"
856 "   :type pt: :class:`mathutils.Vector`\n"
857 "   :arg plane_co: First point of the quad\n"
858 "   :type plane_co: :class:`mathutils.Vector`\n"
859 "   :arg plane_no: Second point of the quad\n"
860 "   :type plane_no: :class:`mathutils.Vector`\n"
861 "   :rtype: float\n"
862 );
863 static PyObject *M_Geometry_distance_point_to_plane(PyObject *UNUSED(self), PyObject *args)
864 {
865         VectorObject *pt, *plene_co, *plane_no;
866
867         if (!PyArg_ParseTuple(args, "O!O!O!:distance_point_to_plane",
868                               &vector_Type, &pt,
869                               &vector_Type, &plene_co,
870                               &vector_Type, &plane_no))
871         {
872                 return NULL;
873         }
874
875         if (BaseMath_ReadCallback(pt) == -1 ||
876             BaseMath_ReadCallback(plene_co) == -1 ||
877             BaseMath_ReadCallback(plane_no) == -1)
878         {
879                 return NULL;
880         }
881
882         return PyFloat_FromDouble(dist_to_plane_v3(pt->vec, plene_co->vec, plane_no->vec));
883 }
884
885 PyDoc_STRVAR(M_Geometry_barycentric_transform_doc,
886 ".. function:: barycentric_transform(point, tri_a1, tri_a2, tri_a3, tri_b1, tri_b2, tri_b3)\n"
887 "\n"
888 "   Return a transformed point, the transformation is defined by 2 triangles.\n"
889 "\n"
890 "   :arg point: The point to transform.\n"
891 "   :type point: :class:`mathutils.Vector`\n"
892 "   :arg tri_a1: source triangle vertex.\n"
893 "   :type tri_a1: :class:`mathutils.Vector`\n"
894 "   :arg tri_a2: source triangle vertex.\n"
895 "   :type tri_a2: :class:`mathutils.Vector`\n"
896 "   :arg tri_a3: source triangle vertex.\n"
897 "   :type tri_a3: :class:`mathutils.Vector`\n"
898 "   :arg tri_a1: target triangle vertex.\n"
899 "   :type tri_a1: :class:`mathutils.Vector`\n"
900 "   :arg tri_a2: target triangle vertex.\n"
901 "   :type tri_a2: :class:`mathutils.Vector`\n"
902 "   :arg tri_a3: target triangle vertex.\n"
903 "   :type tri_a3: :class:`mathutils.Vector`\n"
904 "   :return: The transformed point\n"
905 "   :rtype: :class:`mathutils.Vector`'s\n"
906 );
907 static PyObject *M_Geometry_barycentric_transform(PyObject *UNUSED(self), PyObject *args)
908 {
909         VectorObject *vec_pt;
910         VectorObject *vec_t1_tar, *vec_t2_tar, *vec_t3_tar;
911         VectorObject *vec_t1_src, *vec_t2_src, *vec_t3_src;
912         float vec[3];
913
914         if (!PyArg_ParseTuple(args, "O!O!O!O!O!O!O!:barycentric_transform",
915                               &vector_Type, &vec_pt,
916                               &vector_Type, &vec_t1_src,
917                               &vector_Type, &vec_t2_src,
918                               &vector_Type, &vec_t3_src,
919                               &vector_Type, &vec_t1_tar,
920                               &vector_Type, &vec_t2_tar,
921                               &vector_Type, &vec_t3_tar))
922         {
923                 return NULL;
924         }
925
926         if (vec_pt->size != 3 ||
927             vec_t1_src->size != 3 ||
928             vec_t2_src->size != 3 ||
929             vec_t3_src->size != 3 ||
930             vec_t1_tar->size != 3 ||
931             vec_t2_tar->size != 3 ||
932             vec_t3_tar->size != 3)
933         {
934                 PyErr_SetString(PyExc_ValueError,
935                                 "One of more of the vector arguments wasn't a 3D vector");
936                 return NULL;
937         }
938
939         barycentric_transform(vec, vec_pt->vec,
940                               vec_t1_tar->vec, vec_t2_tar->vec, vec_t3_tar->vec,
941                               vec_t1_src->vec, vec_t2_src->vec, vec_t3_src->vec);
942
943         return Vector_CreatePyObject(vec, 3, Py_NEW, NULL);
944 }
945
946 #ifndef MATH_STANDALONE
947
948 PyDoc_STRVAR(M_Geometry_interpolate_bezier_doc,
949 ".. function:: interpolate_bezier(knot1, handle1, handle2, knot2, resolution)\n"
950 "\n"
951 "   Interpolate a bezier spline segment.\n"
952 "\n"
953 "   :arg knot1: First bezier spline point.\n"
954 "   :type knot1: :class:`mathutils.Vector`\n"
955 "   :arg handle1: First bezier spline handle.\n"
956 "   :type handle1: :class:`mathutils.Vector`\n"
957 "   :arg handle2: Second bezier spline handle.\n"
958 "   :type handle2: :class:`mathutils.Vector`\n"
959 "   :arg knot2: Second bezier spline point.\n"
960 "   :type knot2: :class:`mathutils.Vector`\n"
961 "   :arg resolution: Number of points to return.\n"
962 "   :type resolution: int\n"
963 "   :return: The interpolated points\n"
964 "   :rtype: list of :class:`mathutils.Vector`'s\n"
965 );
966 static PyObject *M_Geometry_interpolate_bezier(PyObject *UNUSED(self), PyObject *args)
967 {
968         VectorObject *vec_k1, *vec_h1, *vec_k2, *vec_h2;
969         int resolu;
970         int dims;
971         int i;
972         float *coord_array, *fp;
973         PyObject *list;
974
975         float k1[4] = {0.0, 0.0, 0.0, 0.0};
976         float h1[4] = {0.0, 0.0, 0.0, 0.0};
977         float k2[4] = {0.0, 0.0, 0.0, 0.0};
978         float h2[4] = {0.0, 0.0, 0.0, 0.0};
979
980
981         if (!PyArg_ParseTuple(args, "O!O!O!O!i:interpolate_bezier",
982                               &vector_Type, &vec_k1,
983                               &vector_Type, &vec_h1,
984                               &vector_Type, &vec_h2,
985                               &vector_Type, &vec_k2, &resolu))
986         {
987                 return NULL;
988         }
989
990         if (resolu <= 1) {
991                 PyErr_SetString(PyExc_ValueError,
992                                 "resolution must be 2 or over");
993                 return NULL;
994         }
995
996         if (BaseMath_ReadCallback(vec_k1) == -1 ||
997             BaseMath_ReadCallback(vec_h1) == -1 ||
998             BaseMath_ReadCallback(vec_k2) == -1 ||
999             BaseMath_ReadCallback(vec_h2) == -1)
1000         {
1001                 return NULL;
1002         }
1003
1004         dims = MAX4(vec_k1->size, vec_h1->size, vec_h2->size, vec_k2->size);
1005
1006         for (i = 0; i < vec_k1->size; i++) k1[i] = vec_k1->vec[i];
1007         for (i = 0; i < vec_h1->size; i++) h1[i] = vec_h1->vec[i];
1008         for (i = 0; i < vec_k2->size; i++) k2[i] = vec_k2->vec[i];
1009         for (i = 0; i < vec_h2->size; i++) h2[i] = vec_h2->vec[i];
1010
1011         coord_array = MEM_callocN(dims * (resolu) * sizeof(float), "interpolate_bezier");
1012         for (i = 0; i < dims; i++) {
1013                 BKE_curve_forward_diff_bezier(k1[i], h1[i], h2[i], k2[i], coord_array + i, resolu - 1, sizeof(float) * dims);
1014         }
1015
1016         list = PyList_New(resolu);
1017         fp = coord_array;
1018         for (i = 0; i < resolu; i++, fp = fp + dims) {
1019                 PyList_SET_ITEM(list, i, Vector_CreatePyObject(fp, dims, Py_NEW, NULL));
1020         }
1021         MEM_freeN(coord_array);
1022         return list;
1023 }
1024
1025
1026 PyDoc_STRVAR(M_Geometry_tessellate_polygon_doc,
1027 ".. function:: tessellate_polygon(veclist_list)\n"
1028 "\n"
1029 "   Takes a list of polylines (each point a vector) and returns the point indices for a polyline filled with triangles.\n"
1030 "\n"
1031 "   :arg veclist_list: list of polylines\n"
1032 "   :rtype: list\n"
1033 );
1034 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
1035 static PyObject *M_Geometry_tessellate_polygon(PyObject *UNUSED(self), PyObject *polyLineSeq)
1036 {
1037         PyObject *tri_list; /*return this list of tri's */
1038         PyObject *polyLine, *polyVec;
1039         int i, len_polylines, len_polypoints, ls_error = 0;
1040
1041         /* display listbase */
1042         ListBase dispbase = {NULL, NULL};
1043         DispList *dl;
1044         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
1045         int index, *dl_face, totpoints = 0;
1046
1047         if (!PySequence_Check(polyLineSeq)) {
1048                 PyErr_SetString(PyExc_TypeError,
1049                                 "expected a sequence of poly lines");
1050                 return NULL;
1051         }
1052
1053         len_polylines = PySequence_Size(polyLineSeq);
1054
1055         for (i = 0; i < len_polylines; i++) {
1056                 polyLine = PySequence_GetItem(polyLineSeq, i);
1057                 if (!PySequence_Check(polyLine)) {
1058                         BKE_displist_free(&dispbase);
1059                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
1060                         PyErr_SetString(PyExc_TypeError,
1061                                         "One or more of the polylines is not a sequence of mathutils.Vector's");
1062                         return NULL;
1063                 }
1064
1065                 len_polypoints = PySequence_Size(polyLine);
1066                 if (len_polypoints > 0) { /* don't bother adding edges as polylines */
1067 #if 0
1068                         if (EXPP_check_sequence_consistency(polyLine, &vector_Type) != 1) {
1069                                 freedisplist(&dispbase);
1070                                 Py_DECREF(polyLine);
1071                                 PyErr_SetString(PyExc_TypeError,
1072                                                 "A point in one of the polylines is not a mathutils.Vector type");
1073                                 return NULL;
1074                         }
1075 #endif
1076                         dl = MEM_callocN(sizeof(DispList), "poly disp");
1077                         BLI_addtail(&dispbase, dl);
1078                         dl->type = DL_INDEX3;
1079                         dl->nr = len_polypoints;
1080                         dl->type = DL_POLY;
1081                         dl->parts = 1; /* no faces, 1 edge loop */
1082                         dl->col = 0; /* no material */
1083                         dl->verts = fp = MEM_callocN(sizeof(float) * 3 * len_polypoints, "dl verts");
1084                         dl->index = MEM_callocN(sizeof(int) * 3 * len_polypoints, "dl index");
1085
1086                         for (index = 0; index < len_polypoints; index++, fp += 3) {
1087                                 polyVec = PySequence_GetItem(polyLine, index);
1088                                 if (VectorObject_Check(polyVec)) {
1089
1090                                         if (BaseMath_ReadCallback((VectorObject *)polyVec) == -1)
1091                                                 ls_error = 1;
1092
1093                                         fp[0] = ((VectorObject *)polyVec)->vec[0];
1094                                         fp[1] = ((VectorObject *)polyVec)->vec[1];
1095                                         if (((VectorObject *)polyVec)->size > 2)
1096                                                 fp[2] = ((VectorObject *)polyVec)->vec[2];
1097                                         else
1098                                                 fp[2] = 0.0f;  /* if its a 2d vector then set the z to be zero */
1099                                 }
1100                                 else {
1101                                         ls_error = 1;
1102                                 }
1103
1104                                 totpoints++;
1105                                 Py_DECREF(polyVec);
1106                         }
1107                 }
1108                 Py_DECREF(polyLine);
1109         }
1110
1111         if (ls_error) {
1112                 BKE_displist_free(&dispbase); /* possible some dl was allocated */
1113                 PyErr_SetString(PyExc_TypeError,
1114                                 "A point in one of the polylines "
1115                                 "is not a mathutils.Vector type");
1116                 return NULL;
1117         }
1118         else if (totpoints) {
1119                 /* now make the list to return */
1120                 BKE_displist_fill(&dispbase, &dispbase, 0);
1121
1122                 /* The faces are stored in a new DisplayList
1123                  * thats added to the head of the listbase */
1124                 dl = dispbase.first;
1125
1126                 tri_list = PyList_New(dl->parts);
1127                 if (!tri_list) {
1128                         BKE_displist_free(&dispbase);
1129                         PyErr_SetString(PyExc_RuntimeError,
1130                                         "failed to make a new list");
1131                         return NULL;
1132                 }
1133
1134                 index = 0;
1135                 dl_face = dl->index;
1136                 while (index < dl->parts) {
1137                         PyList_SET_ITEM(tri_list, index, Py_BuildValue("iii", dl_face[0], dl_face[1], dl_face[2]));
1138                         dl_face += 3;
1139                         index++;
1140                 }
1141                 BKE_displist_free(&dispbase);
1142         }
1143         else {
1144                 /* no points, do this so scripts don't barf */
1145                 BKE_displist_free(&dispbase); /* possible some dl was allocated */
1146                 tri_list = PyList_New(0);
1147         }
1148
1149         return tri_list;
1150 }
1151
1152
1153 static int boxPack_FromPyObject(PyObject *value, BoxPack **boxarray)
1154 {
1155         Py_ssize_t len, i;
1156         PyObject *list_item, *item_1, *item_2;
1157         BoxPack *box;
1158
1159
1160         /* Error checking must already be done */
1161         if (!PyList_Check(value)) {
1162                 PyErr_SetString(PyExc_TypeError,
1163                                 "can only back a list of [x, y, w, h]");
1164                 return -1;
1165         }
1166
1167         len = PyList_GET_SIZE(value);
1168
1169         *boxarray = MEM_mallocN(len * sizeof(BoxPack), "BoxPack box");
1170
1171
1172         for (i = 0; i < len; i++) {
1173                 list_item = PyList_GET_ITEM(value, i);
1174                 if (!PyList_Check(list_item) || PyList_GET_SIZE(list_item) < 4) {
1175                         MEM_freeN(*boxarray);
1176                         PyErr_SetString(PyExc_TypeError,
1177                                         "can only pack a list of [x, y, w, h]");
1178                         return -1;
1179                 }
1180
1181                 box = (*boxarray) + i;
1182
1183                 item_1 = PyList_GET_ITEM(list_item, 2);
1184                 item_2 = PyList_GET_ITEM(list_item, 3);
1185
1186                 box->w =  (float)PyFloat_AsDouble(item_1);
1187                 box->h =  (float)PyFloat_AsDouble(item_2);
1188                 box->index = i;
1189
1190                 /* accounts for error case too and overwrites with own error */
1191                 if (box->w < 0.0f || box->h < 0.0f) {
1192                         MEM_freeN(*boxarray);
1193                         PyErr_SetString(PyExc_TypeError,
1194                                         "error parsing width and height values from list: "
1195                                         "[x, y, w, h], not numbers or below zero");
1196                         return -1;
1197                 }
1198
1199                 /* verts will be added later */
1200         }
1201         return 0;
1202 }
1203
1204 static void boxPack_ToPyObject(PyObject *value, BoxPack **boxarray)
1205 {
1206         Py_ssize_t len, i;
1207         PyObject *list_item;
1208         BoxPack *box;
1209
1210         len = PyList_GET_SIZE(value);
1211
1212         for (i = 0; i < len; i++) {
1213                 box = (*boxarray) + i;
1214                 list_item = PyList_GET_ITEM(value, box->index);
1215                 PyList_SET_ITEM(list_item, 0, PyFloat_FromDouble(box->x));
1216                 PyList_SET_ITEM(list_item, 1, PyFloat_FromDouble(box->y));
1217         }
1218         MEM_freeN(*boxarray);
1219 }
1220
1221 PyDoc_STRVAR(M_Geometry_box_pack_2d_doc,
1222 ".. function:: box_pack_2d(boxes)\n"
1223 "\n"
1224 "   Returns the normal of the 3D tri or quad.\n"
1225 "\n"
1226 "   :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"
1227 "   :type boxes: list\n"
1228 "   :return: the width and height of the packed bounding box\n"
1229 "   :rtype: tuple, pair of floats\n"
1230 );
1231 static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlist)
1232 {
1233         float tot_width = 0.0f, tot_height = 0.0f;
1234         Py_ssize_t len;
1235
1236         PyObject *ret;
1237
1238         if (!PyList_Check(boxlist)) {
1239                 PyErr_SetString(PyExc_TypeError,
1240                                 "expected a list of boxes [[x, y, w, h], ... ]");
1241                 return NULL;
1242         }
1243
1244         len = PyList_GET_SIZE(boxlist);
1245         if (len) {
1246                 BoxPack *boxarray = NULL;
1247                 if (boxPack_FromPyObject(boxlist, &boxarray) == -1) {
1248                         return NULL; /* exception set */
1249                 }
1250
1251                 /* Non Python function */
1252                 BLI_box_pack_2D(boxarray, len, &tot_width, &tot_height);
1253
1254                 boxPack_ToPyObject(boxlist, &boxarray);
1255         }
1256
1257         ret = PyTuple_New(2);
1258         PyTuple_SET_ITEM(ret, 0, PyFloat_FromDouble(tot_width));
1259         PyTuple_SET_ITEM(ret, 1, PyFloat_FromDouble(tot_width));
1260         return ret;
1261 }
1262
1263 #endif /* MATH_STANDALONE */
1264
1265
1266 static PyMethodDef M_Geometry_methods[] = {
1267         {"intersect_ray_tri", (PyCFunction) M_Geometry_intersect_ray_tri, METH_VARARGS, M_Geometry_intersect_ray_tri_doc},
1268         {"intersect_point_line", (PyCFunction) M_Geometry_intersect_point_line, METH_VARARGS, M_Geometry_intersect_point_line_doc},
1269         {"intersect_point_tri_2d", (PyCFunction) M_Geometry_intersect_point_tri_2d, METH_VARARGS, M_Geometry_intersect_point_tri_2d_doc},
1270         {"intersect_point_quad_2d", (PyCFunction) M_Geometry_intersect_point_quad_2d, METH_VARARGS, M_Geometry_intersect_point_quad_2d_doc},
1271         {"intersect_line_line", (PyCFunction) M_Geometry_intersect_line_line, METH_VARARGS, M_Geometry_intersect_line_line_doc},
1272         {"intersect_line_line_2d", (PyCFunction) M_Geometry_intersect_line_line_2d, METH_VARARGS, M_Geometry_intersect_line_line_2d_doc},
1273         {"intersect_line_plane", (PyCFunction) M_Geometry_intersect_line_plane, METH_VARARGS, M_Geometry_intersect_line_plane_doc},
1274         {"intersect_plane_plane", (PyCFunction) M_Geometry_intersect_plane_plane, METH_VARARGS, M_Geometry_intersect_plane_plane_doc},
1275         {"intersect_line_sphere", (PyCFunction) M_Geometry_intersect_line_sphere, METH_VARARGS, M_Geometry_intersect_line_sphere_doc},
1276         {"intersect_line_sphere_2d", (PyCFunction) M_Geometry_intersect_line_sphere_2d, METH_VARARGS, M_Geometry_intersect_line_sphere_2d_doc},
1277         {"distance_point_to_plane", (PyCFunction) M_Geometry_distance_point_to_plane, METH_VARARGS, M_Geometry_distance_point_to_plane_doc},
1278         {"area_tri", (PyCFunction) M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc},
1279         {"normal", (PyCFunction) M_Geometry_normal, METH_VARARGS, M_Geometry_normal_doc},
1280         {"barycentric_transform", (PyCFunction) M_Geometry_barycentric_transform, METH_VARARGS, M_Geometry_barycentric_transform_doc},
1281 #ifndef MATH_STANDALONE
1282         {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc},
1283         {"tessellate_polygon", (PyCFunction) M_Geometry_tessellate_polygon, METH_O, M_Geometry_tessellate_polygon_doc},
1284         {"box_pack_2d", (PyCFunction) M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc},
1285 #endif
1286         {NULL, NULL, 0, NULL}
1287 };
1288
1289 static struct PyModuleDef M_Geometry_module_def = {
1290         PyModuleDef_HEAD_INIT,
1291         "mathutils.geometry",  /* m_name */
1292         M_Geometry_doc,  /* m_doc */
1293         0,  /* m_size */
1294         M_Geometry_methods,  /* m_methods */
1295         NULL,  /* m_reload */
1296         NULL,  /* m_traverse */
1297         NULL,  /* m_clear */
1298         NULL,  /* m_free */
1299 };
1300
1301 /*----------------------------MODULE INIT-------------------------*/
1302 PyMODINIT_FUNC PyInit_mathutils_geometry(void)
1303 {
1304         PyObject *submodule = PyModule_Create(&M_Geometry_module_def);
1305         return submodule;
1306 }