spelling cleanup: tesselate -> tessellate (last of these found)
[blender.git] / source / blender / python / mathutils / mathutils_geometry.c
1 /*
2  *
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20  * All rights reserved.
21  *
22  * This is a new part of Blender.
23  *
24  * Contributor(s): Joseph Gilbert, Campbell Barton
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file blender/python/mathutils/mathutils_geometry.c
30  *  \ingroup pymathutils
31  */
32
33
34 #include <Python.h>
35
36 #include "mathutils_geometry.h"
37
38 /* Used for PolyFill */
39 #ifndef MATH_STANDALONE /* define when building outside blender */
40 #  include "MEM_guardedalloc.h"
41 #  include "BLI_blenlib.h"
42 #  include "BLI_boxpack2d.h"
43 #  include "BKE_displist.h"
44 #  include "BKE_curve.h"
45 #endif
46
47 #include "BLI_math.h"
48 #include "BLI_utildefines.h"
49
50 #define SWAP_FLOAT(a, b, tmp) tmp = a; a = b; b = tmp
51
52 /*-------------------------DOC STRINGS ---------------------------*/
53 PyDoc_STRVAR(M_Geometry_doc,
54 "The Blender geometry module"
55 );
56
57 //---------------------------------INTERSECTION FUNCTIONS--------------------
58
59 PyDoc_STRVAR(M_Geometry_intersect_ray_tri_doc,
60 ".. function:: intersect_ray_tri(v1, v2, v3, ray, orig, clip=True)\n"
61 "\n"
62 "   Returns the intersection between a ray and a triangle, if possible, returns None otherwise.\n"
63 "\n"
64 "   :arg v1: Point1\n"
65 "   :type v1: :class:`mathutils.Vector`\n"
66 "   :arg v2: Point2\n"
67 "   :type v2: :class:`mathutils.Vector`\n"
68 "   :arg v3: Point3\n"
69 "   :type v3: :class:`mathutils.Vector`\n"
70 "   :arg ray: Direction of the projection\n"
71 "   :type ray: :class:`mathutils.Vector`\n"
72 "   :arg orig: Origin\n"
73 "   :type orig: :class:`mathutils.Vector`\n"
74 "   :arg clip: When False, don't restrict the intersection to the area of the triangle, use the infinite plane defined by the triangle.\n"
75 "   :type clip: boolean\n"
76 "   :return: The point of intersection or None if no intersection is found\n"
77 "   :rtype: :class:`mathutils.Vector` or None\n"
78 );
79 static PyObject *M_Geometry_intersect_ray_tri(PyObject *UNUSED(self), PyObject *args)
80 {
81         VectorObject *ray, *ray_off, *vec1, *vec2, *vec3;
82         float dir[3], orig[3], v1[3], v2[3], v3[3], e1[3], e2[3], pvec[3], tvec[3], qvec[3];
83         float det, inv_det, u, v, t;
84         int clip = 1;
85
86         if (!PyArg_ParseTuple(args,
87                               "O!O!O!O!O!|i:intersect_ray_tri",
88                               &vector_Type, &vec1,
89                               &vector_Type, &vec2,
90                               &vector_Type, &vec3,
91                               &vector_Type, &ray,
92                               &vector_Type, &ray_off, &clip))
93         {
94                 return NULL;
95         }
96         if (vec1->size != 3 || vec2->size != 3 || vec3->size != 3 || ray->size != 3 || ray_off->size != 3) {
97                 PyErr_SetString(PyExc_ValueError,
98                                 "only 3D vectors for all parameters");
99                 return NULL;
100         }
101
102         if (BaseMath_ReadCallback(vec1) == -1 ||
103             BaseMath_ReadCallback(vec2) == -1 ||
104             BaseMath_ReadCallback(vec3) == -1 ||
105             BaseMath_ReadCallback(ray)  == -1 ||
106             BaseMath_ReadCallback(ray_off) == -1)
107         {
108                 return NULL;
109         }
110
111         copy_v3_v3(v1, vec1->vec);
112         copy_v3_v3(v2, vec2->vec);
113         copy_v3_v3(v3, vec3->vec);
114
115         copy_v3_v3(dir, ray->vec);
116         normalize_v3(dir);
117
118         copy_v3_v3(orig, ray_off->vec);
119
120         /* find vectors for two edges sharing v1 */
121         sub_v3_v3v3(e1, v2, v1);
122         sub_v3_v3v3(e2, v3, v1);
123
124         /* begin calculating determinant - also used to calculated U parameter */
125         cross_v3_v3v3(pvec, dir, e2);
126
127         /* if determinant is near zero, ray lies in plane of triangle */
128         det = dot_v3v3(e1, pvec);
129
130         if (det > -0.000001f && det < 0.000001f) {
131                 Py_RETURN_NONE;
132         }
133
134         inv_det = 1.0f / det;
135
136         /* calculate distance from v1 to ray origin */
137         sub_v3_v3v3(tvec, orig, v1);
138
139         /* calculate U parameter and test bounds */
140         u = dot_v3v3(tvec, pvec) * inv_det;
141         if (clip && (u < 0.0f || u > 1.0f)) {
142                 Py_RETURN_NONE;
143         }
144
145         /* prepare to test the V parameter */
146         cross_v3_v3v3(qvec, tvec, e1);
147
148         /* calculate V parameter and test bounds */
149         v = dot_v3v3(dir, qvec) * inv_det;
150
151         if (clip && (v < 0.0f || u + v > 1.0f)) {
152                 Py_RETURN_NONE;
153         }
154
155         /* calculate t, ray intersects triangle */
156         t = dot_v3v3(e2, qvec) * inv_det;
157
158         mul_v3_fl(dir, t);
159         add_v3_v3v3(pvec, orig, dir);
160
161         return Vector_CreatePyObject(pvec, 3, Py_NEW, NULL);
162 }
163
164 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
165
166 PyDoc_STRVAR(M_Geometry_intersect_line_line_doc,
167 ".. function:: intersect_line_line(v1, v2, v3, v4)\n"
168 "\n"
169 "   Returns a tuple with the points on each line respectively closest to the other.\n"
170 "\n"
171 "   :arg v1: First point of the first line\n"
172 "   :type v1: :class:`mathutils.Vector`\n"
173 "   :arg v2: Second point of the first line\n"
174 "   :type v2: :class:`mathutils.Vector`\n"
175 "   :arg v3: First point of the second line\n"
176 "   :type v3: :class:`mathutils.Vector`\n"
177 "   :arg v4: Second point of the second line\n"
178 "   :type v4: :class:`mathutils.Vector`\n"
179 "   :rtype: tuple of :class:`mathutils.Vector`'s\n"
180 );
181 static PyObject *M_Geometry_intersect_line_line(PyObject *UNUSED(self), PyObject *args)
182 {
183         PyObject *tuple;
184         VectorObject *vec1, *vec2, *vec3, *vec4;
185         float v1[3], v2[3], v3[3], v4[3], i1[3], i2[3];
186
187         if (!PyArg_ParseTuple(args, "O!O!O!O!:intersect_line_line",
188                               &vector_Type, &vec1,
189                               &vector_Type, &vec2,
190                               &vector_Type, &vec3,
191                               &vector_Type, &vec4))
192         {
193                 return NULL;
194         }
195
196         if (vec1->size != vec2->size || vec1->size != vec3->size || vec3->size != vec2->size) {
197                 PyErr_SetString(PyExc_ValueError,
198                                 "vectors must be of the same size");
199                 return NULL;
200         }
201
202         if (BaseMath_ReadCallback(vec1) == -1 ||
203             BaseMath_ReadCallback(vec2) == -1 ||
204             BaseMath_ReadCallback(vec3) == -1 ||
205             BaseMath_ReadCallback(vec4) == -1)
206         {
207                 return NULL;
208         }
209
210         if (vec1->size == 3 || vec1->size == 2) {
211                 int result;
212
213                 if (vec1->size == 3) {
214                         copy_v3_v3(v1, vec1->vec);
215                         copy_v3_v3(v2, vec2->vec);
216                         copy_v3_v3(v3, vec3->vec);
217                         copy_v3_v3(v4, vec4->vec);
218                 }
219                 else {
220                         v1[0] = vec1->vec[0];
221                         v1[1] = vec1->vec[1];
222                         v1[2] = 0.0f;
223
224                         v2[0] = vec2->vec[0];
225                         v2[1] = vec2->vec[1];
226                         v2[2] = 0.0f;
227
228                         v3[0] = vec3->vec[0];
229                         v3[1] = vec3->vec[1];
230                         v3[2] = 0.0f;
231
232                         v4[0] = vec4->vec[0];
233                         v4[1] = vec4->vec[1];
234                         v4[2] = 0.0f;
235                 }
236
237                 result = isect_line_line_v3(v1, v2, v3, v4, i1, i2);
238
239                 if (result == 0) {
240                         /* colinear */
241                         Py_RETURN_NONE;
242                 }
243                 else {
244                         tuple = PyTuple_New(2);
245                         PyTuple_SET_ITEM(tuple, 0, Vector_CreatePyObject(i1, vec1->size, Py_NEW, NULL));
246                         PyTuple_SET_ITEM(tuple, 1, Vector_CreatePyObject(i2, vec1->size, Py_NEW, NULL));
247                         return tuple;
248                 }
249         }
250         else {
251                 PyErr_SetString(PyExc_ValueError,
252                                 "2D/3D vectors only");
253                 return NULL;
254         }
255 }
256
257
258
259
260 //----------------------------geometry.normal() -------------------
261 PyDoc_STRVAR(M_Geometry_normal_doc,
262 ".. function:: normal(v1, v2, v3, v4=None)\n"
263 "\n"
264 "   Returns the normal of the 3D tri or quad.\n"
265 "\n"
266 "   :arg v1: Point1\n"
267 "   :type v1: :class:`mathutils.Vector`\n"
268 "   :arg v2: Point2\n"
269 "   :type v2: :class:`mathutils.Vector`\n"
270 "   :arg v3: Point3\n"
271 "   :type v3: :class:`mathutils.Vector`\n"
272 "   :arg v4: Point4 (optional)\n"
273 "   :type v4: :class:`mathutils.Vector`\n"
274 "   :rtype: :class:`mathutils.Vector`\n"
275 );
276 static PyObject *M_Geometry_normal(PyObject *UNUSED(self), PyObject *args)
277 {
278         VectorObject *vec1, *vec2, *vec3, *vec4;
279         float n[3];
280
281         if (PyTuple_GET_SIZE(args) == 3) {
282                 if (!PyArg_ParseTuple(args, "O!O!O!:normal",
283                                       &vector_Type, &vec1,
284                                       &vector_Type, &vec2,
285                                       &vector_Type, &vec3))
286                 {
287                         return NULL;
288                 }
289
290                 if (vec1->size != vec2->size || vec1->size != vec3->size) {
291                         PyErr_SetString(PyExc_ValueError,
292                                         "vectors must be of the same size");
293                         return NULL;
294                 }
295                 if (vec1->size < 3) {
296                         PyErr_SetString(PyExc_ValueError,
297                                         "2D vectors unsupported");
298                         return NULL;
299                 }
300
301                 if (BaseMath_ReadCallback(vec1) == -1 ||
302                     BaseMath_ReadCallback(vec2) == -1 ||
303                     BaseMath_ReadCallback(vec3) == -1)
304                 {
305                         return NULL;
306                 }
307
308                 normal_tri_v3(n, vec1->vec, vec2->vec, vec3->vec);
309         }
310         else {
311                 if (!PyArg_ParseTuple(args, "O!O!O!O!:normal",
312                                       &vector_Type, &vec1,
313                                       &vector_Type, &vec2,
314                                       &vector_Type, &vec3,
315                                       &vector_Type, &vec4))
316                 {
317                         return NULL;
318                 }
319                 if (vec1->size != vec2->size || vec1->size != vec3->size || vec1->size != vec4->size) {
320                         PyErr_SetString(PyExc_ValueError,
321                                         "vectors must be of the same size");
322                         return NULL;
323                 }
324                 if (vec1->size < 3) {
325                         PyErr_SetString(PyExc_ValueError,
326                                         "2D vectors unsupported");
327                         return NULL;
328                 }
329
330                 if (BaseMath_ReadCallback(vec1) == -1 ||
331                     BaseMath_ReadCallback(vec2) == -1 ||
332                     BaseMath_ReadCallback(vec3) == -1 ||
333                     BaseMath_ReadCallback(vec4) == -1)
334                 {
335                         return NULL;
336                 }
337
338                 normal_quad_v3(n, vec1->vec, vec2->vec, vec3->vec, vec4->vec);
339         }
340
341         return Vector_CreatePyObject(n, 3, Py_NEW, NULL);
342 }
343
344 //--------------------------------- AREA FUNCTIONS--------------------
345
346 PyDoc_STRVAR(M_Geometry_area_tri_doc,
347 ".. function:: area_tri(v1, v2, v3)\n"
348 "\n"
349 "   Returns the area size of the 2D or 3D triangle defined.\n"
350 "\n"
351 "   :arg v1: Point1\n"
352 "   :type v1: :class:`mathutils.Vector`\n"
353 "   :arg v2: Point2\n"
354 "   :type v2: :class:`mathutils.Vector`\n"
355 "   :arg v3: Point3\n"
356 "   :type v3: :class:`mathutils.Vector`\n"
357 "   :rtype: float\n"
358 );
359 static PyObject *M_Geometry_area_tri(PyObject *UNUSED(self), PyObject *args)
360 {
361         VectorObject *vec1, *vec2, *vec3;
362
363         if (!PyArg_ParseTuple(args, "O!O!O!:area_tri",
364                               &vector_Type, &vec1,
365                               &vector_Type, &vec2,
366                               &vector_Type, &vec3))
367         {
368                 return NULL;
369         }
370
371         if (vec1->size != vec2->size || vec1->size != vec3->size) {
372                 PyErr_SetString(PyExc_ValueError,
373                                 "vectors must be of the same size");
374                 return NULL;
375         }
376
377         if (BaseMath_ReadCallback(vec1) == -1 ||
378             BaseMath_ReadCallback(vec2) == -1 ||
379             BaseMath_ReadCallback(vec3) == -1)
380         {
381                 return NULL;
382         }
383
384         if (vec1->size == 3) {
385                 return PyFloat_FromDouble(area_tri_v3(vec1->vec, vec2->vec, vec3->vec));
386         }
387         else if (vec1->size == 2) {
388                 return PyFloat_FromDouble(area_tri_v2(vec1->vec, vec2->vec, vec3->vec));
389         }
390         else {
391                 PyErr_SetString(PyExc_ValueError,
392                                 "only 2D,3D vectors are supported");
393                 return NULL;
394         }
395 }
396
397
398 PyDoc_STRVAR(M_Geometry_intersect_line_line_2d_doc,
399 ".. function:: intersect_line_line_2d(lineA_p1, lineA_p2, lineB_p1, lineB_p2)\n"
400 "\n"
401 "   Takes 2 lines (as 4 vectors) and returns a vector for their point of intersection or None.\n"
402 "\n"
403 "   :arg lineA_p1: First point of the first line\n"
404 "   :type lineA_p1: :class:`mathutils.Vector`\n"
405 "   :arg lineA_p2: Second point of the first line\n"
406 "   :type lineA_p2: :class:`mathutils.Vector`\n"
407 "   :arg lineB_p1: First point of the second line\n"
408 "   :type lineB_p1: :class:`mathutils.Vector`\n"
409 "   :arg lineB_p2: Second point of the second line\n"
410 "   :type lineB_p2: :class:`mathutils.Vector`\n"
411 "   :return: The point of intersection or None when not found\n"
412 "   :rtype: :class:`mathutils.Vector` or None\n"
413 );
414 static PyObject *M_Geometry_intersect_line_line_2d(PyObject *UNUSED(self), PyObject *args)
415 {
416         VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
417         float vi[2];
418         if (!PyArg_ParseTuple(args, "O!O!O!O!:intersect_line_line_2d",
419                               &vector_Type, &line_a1,
420                               &vector_Type, &line_a2,
421                               &vector_Type, &line_b1,
422                               &vector_Type, &line_b2))
423         {
424                 return NULL;
425         }
426         
427         if (BaseMath_ReadCallback(line_a1) == -1 ||
428             BaseMath_ReadCallback(line_a2) == -1 ||
429             BaseMath_ReadCallback(line_b1) == -1 ||
430             BaseMath_ReadCallback(line_b2) == -1)
431         {
432                 return NULL;
433         }
434
435         if (isect_seg_seg_v2_point(line_a1->vec, line_a2->vec, line_b1->vec, line_b2->vec, vi) == 1) {
436                 return Vector_CreatePyObject(vi, 2, Py_NEW, NULL);
437         }
438         else {
439                 Py_RETURN_NONE;
440         }
441 }
442
443
444 PyDoc_STRVAR(M_Geometry_intersect_line_plane_doc,
445 ".. function:: intersect_line_plane(line_a, line_b, plane_co, plane_no, no_flip=False)\n"
446 "\n"
447 "   Takes 2 lines (as 4 vectors) and returns a vector for their point of 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                 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                         freedisplist(&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                 freedisplist(&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                 filldisplist(&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                         freedisplist(&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                 freedisplist(&dispbase);
1142         }
1143         else {
1144                 /* no points, do this so scripts don't barf */
1145                 freedisplist(&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                 boxPack2D(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 }