remove unused includes
[blender.git] / source / blender / python / generic / Geometry.c
1 /* 
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * This is a new part of Blender.
24  *
25  * Contributor(s): Joseph Gilbert, Campbell Barton
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include "Geometry.h"
31
32 /* Used for PolyFill */
33 #include "BKE_displist.h"
34 #include "MEM_guardedalloc.h"
35 #include "BLI_blenlib.h"
36  
37 #include "BKE_utildefines.h"
38 #include "BKE_curve.h"
39 #include "BLI_boxpack2d.h"
40 #include "BLI_math.h"
41
42 #define SWAP_FLOAT(a,b,tmp) tmp=a; a=b; b=tmp
43 #define eps 0.000001
44
45
46 /*-------------------------DOC STRINGS ---------------------------*/
47 static char M_Geometry_doc[] = "The Blender Geometry module\n\n";
48 static char M_Geometry_Intersect_doc[] = "(v1, v2, v3, ray, orig, clip=1) - returns the intersection between a ray and a triangle, if possible, returns None otherwise";
49 static char M_Geometry_TriangleArea_doc[] = "(v1, v2, v3) - returns the area size of the 2D or 3D triangle defined";
50 static char M_Geometry_TriangleNormal_doc[] = "(v1, v2, v3) - returns the normal of the 3D triangle defined";
51 static char M_Geometry_QuadNormal_doc[] = "(v1, v2, v3, v4) - returns the normal of the 3D quad defined";
52 static char M_Geometry_LineIntersect_doc[] = "(v1, v2, v3, v4) - returns a tuple with the points on each line respectively closest to the other";
53 static char M_Geometry_PolyFill_doc[] = "(veclist_list) - takes a list of polylines (each point a vector) and returns the point indicies for a polyline filled with triangles";
54 static char M_Geometry_LineIntersect2D_doc[] = "(lineA_p1, lineA_p2, lineB_p1, lineB_p2) - takes 2 lines (as 4 vectors) and returns a vector for their point of intersection or None";
55 static char M_Geometry_ClosestPointOnLine_doc[] = "(pt, line_p1, line_p2) - takes a point and a line and returns a (Vector, float) for the point on the line, and the bool so you can know if the point was between the 2 points";
56 static char M_Geometry_PointInTriangle2D_doc[] = "(pt, tri_p1, tri_p2, tri_p3) - takes 4 vectors, one is the point and the next 3 define the triangle, only the x and y are used from the vectors";
57 static char M_Geometry_PointInQuad2D_doc[] = "(pt, quad_p1, quad_p2, quad_p3, quad_p4) - takes 5 vectors, one is the point and the next 4 define the quad, only the x and y are used from the vectors";
58 static char M_Geometry_BoxPack2D_doc[] = "";
59 static char M_Geometry_BezierInterp_doc[] = "";
60
61 //---------------------------------INTERSECTION FUNCTIONS--------------------
62 //----------------------------------Mathutils.Intersect() -------------------
63 static PyObject *M_Geometry_Intersect( PyObject * self, PyObject * args )
64 {
65         VectorObject *ray, *ray_off, *vec1, *vec2, *vec3;
66         float dir[3], orig[3], v1[3], v2[3], v3[3], e1[3], e2[3], pvec[3], tvec[3], qvec[3];
67         float det, inv_det, u, v, t;
68         int clip = 1;
69
70         if(!PyArg_ParseTuple(args, "O!O!O!O!O!|i", &vector_Type, &vec1, &vector_Type, &vec2, &vector_Type, &vec3, &vector_Type, &ray, &vector_Type, &ray_off , &clip)) {
71                 PyErr_SetString( PyExc_TypeError, "expected 5 vector types\n" );
72                 return NULL;
73         }
74         if(vec1->size != 3 || vec2->size != 3 || vec3->size != 3 || ray->size != 3 || ray_off->size != 3) {
75                 PyErr_SetString( PyExc_TypeError, "only 3D vectors for all parameters\n");
76                 return NULL;
77         }
78
79         if(!BaseMath_ReadCallback(vec1) || !BaseMath_ReadCallback(vec2) || !BaseMath_ReadCallback(vec3) || !BaseMath_ReadCallback(ray) || !BaseMath_ReadCallback(ray_off))
80                 return NULL;
81
82         VECCOPY(v1, vec1->vec);
83         VECCOPY(v2, vec2->vec);
84         VECCOPY(v3, vec3->vec);
85
86         VECCOPY(dir, ray->vec);
87         normalize_v3(dir);
88
89         VECCOPY(orig, ray_off->vec);
90
91         /* find vectors for two edges sharing v1 */
92         sub_v3_v3v3(e1, v2, v1);
93         sub_v3_v3v3(e2, v3, v1);
94
95         /* begin calculating determinant - also used to calculated U parameter */
96         cross_v3_v3v3(pvec, dir, e2);
97
98         /* if determinant is near zero, ray lies in plane of triangle */
99         det = dot_v3v3(e1, pvec);
100
101         if (det > -0.000001 && det < 0.000001) {
102                 Py_RETURN_NONE;
103         }
104
105         inv_det = 1.0f / det;
106
107         /* calculate distance from v1 to ray origin */
108         sub_v3_v3v3(tvec, orig, v1);
109
110         /* calculate U parameter and test bounds */
111         u = dot_v3v3(tvec, pvec) * inv_det;
112         if (clip && (u < 0.0f || u > 1.0f)) {
113                 Py_RETURN_NONE;
114         }
115
116         /* prepare to test the V parameter */
117         cross_v3_v3v3(qvec, tvec, e1);
118
119         /* calculate V parameter and test bounds */
120         v = dot_v3v3(dir, qvec) * inv_det;
121
122         if (clip && (v < 0.0f || u + v > 1.0f)) {
123                 Py_RETURN_NONE;
124         }
125
126         /* calculate t, ray intersects triangle */
127         t = dot_v3v3(e2, qvec) * inv_det;
128
129         mul_v3_fl(dir, t);
130         add_v3_v3v3(pvec, orig, dir);
131
132         return newVectorObject(pvec, 3, Py_NEW, NULL);
133 }
134 //----------------------------------Mathutils.LineIntersect() -------------------
135 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
136 static PyObject *M_Geometry_LineIntersect( PyObject * self, PyObject * args )
137 {
138         PyObject * tuple;
139         VectorObject *vec1, *vec2, *vec3, *vec4;
140         float v1[3], v2[3], v3[3], v4[3], i1[3], i2[3];
141
142         if( !PyArg_ParseTuple( args, "O!O!O!O!", &vector_Type, &vec1, &vector_Type, &vec2, &vector_Type, &vec3, &vector_Type, &vec4 ) ) {
143                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types\n" );
144                 return NULL;
145         }
146         if( vec1->size != vec2->size || vec1->size != vec3->size || vec3->size != vec2->size) {
147                 PyErr_SetString( PyExc_TypeError,"vectors must be of the same size\n" );
148                 return NULL;
149         }
150
151         if(!BaseMath_ReadCallback(vec1) || !BaseMath_ReadCallback(vec2) || !BaseMath_ReadCallback(vec3) || !BaseMath_ReadCallback(vec4))
152                 return NULL;
153
154         if( vec1->size == 3 || vec1->size == 2) {
155                 int result;
156
157                 if (vec1->size == 3) {
158                         VECCOPY(v1, vec1->vec);
159                         VECCOPY(v2, vec2->vec);
160                         VECCOPY(v3, vec3->vec);
161                         VECCOPY(v4, vec4->vec);
162                 }
163                 else {
164                         v1[0] = vec1->vec[0];
165                         v1[1] = vec1->vec[1];
166                         v1[2] = 0.0f;
167
168                         v2[0] = vec2->vec[0];
169                         v2[1] = vec2->vec[1];
170                         v2[2] = 0.0f;
171
172                         v3[0] = vec3->vec[0];
173                         v3[1] = vec3->vec[1];
174                         v3[2] = 0.0f;
175
176                         v4[0] = vec4->vec[0];
177                         v4[1] = vec4->vec[1];
178                         v4[2] = 0.0f;
179                 }
180
181                 result = isect_line_line_v3(v1, v2, v3, v4, i1, i2);
182
183                 if (result == 0) {
184                         /* colinear */
185                         Py_RETURN_NONE;
186                 }
187                 else {
188                         tuple = PyTuple_New( 2 );
189                         PyTuple_SetItem( tuple, 0, newVectorObject(i1, vec1->size, Py_NEW, NULL) );
190                         PyTuple_SetItem( tuple, 1, newVectorObject(i2, vec1->size, Py_NEW, NULL) );
191                         return tuple;
192                 }
193         }
194         else {
195                 PyErr_SetString( PyExc_TypeError, "2D/3D vectors only\n" );
196                 return NULL;
197         }
198 }
199
200
201
202 //---------------------------------NORMALS FUNCTIONS--------------------
203 //----------------------------------Mathutils.QuadNormal() -------------------
204 static PyObject *M_Geometry_QuadNormal( PyObject * self, PyObject * args )
205 {
206         VectorObject *vec1;
207         VectorObject *vec2;
208         VectorObject *vec3;
209         VectorObject *vec4;
210         float v1[3], v2[3], v3[3], v4[3], e1[3], e2[3], n1[3], n2[3];
211
212         if( !PyArg_ParseTuple( args, "O!O!O!O!", &vector_Type, &vec1, &vector_Type, &vec2, &vector_Type, &vec3, &vector_Type, &vec4 ) ) {
213                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types\n" );
214                 return NULL;
215         }
216         if( vec1->size != vec2->size || vec1->size != vec3->size || vec1->size != vec4->size) {
217                 PyErr_SetString( PyExc_TypeError,"vectors must be of the same size\n" );
218                 return NULL;
219         }
220         if( vec1->size != 3 ) {
221                 PyErr_SetString( PyExc_TypeError, "only 3D vectors\n" );
222                 return NULL;
223         }
224
225         if(!BaseMath_ReadCallback(vec1) || !BaseMath_ReadCallback(vec2) || !BaseMath_ReadCallback(vec3) || !BaseMath_ReadCallback(vec4))
226                 return NULL;
227
228         VECCOPY(v1, vec1->vec);
229         VECCOPY(v2, vec2->vec);
230         VECCOPY(v3, vec3->vec);
231         VECCOPY(v4, vec4->vec);
232
233         /* find vectors for two edges sharing v2 */
234         sub_v3_v3v3(e1, v1, v2);
235         sub_v3_v3v3(e2, v3, v2);
236
237         cross_v3_v3v3(n1, e2, e1);
238         normalize_v3(n1);
239
240         /* find vectors for two edges sharing v4 */
241         sub_v3_v3v3(e1, v3, v4);
242         sub_v3_v3v3(e2, v1, v4);
243
244         cross_v3_v3v3(n2, e2, e1);
245         normalize_v3(n2);
246
247         /* adding and averaging the normals of both triangles */
248         add_v3_v3v3(n1, n2, n1);
249         normalize_v3(n1);
250
251         return newVectorObject(n1, 3, Py_NEW, NULL);
252 }
253
254 //----------------------------Mathutils.TriangleNormal() -------------------
255 static PyObject *M_Geometry_TriangleNormal( PyObject * self, PyObject * args )
256 {
257         VectorObject *vec1, *vec2, *vec3;
258         float v1[3], v2[3], v3[3], e1[3], e2[3], n[3];
259
260         if( !PyArg_ParseTuple( args, "O!O!O!", &vector_Type, &vec1, &vector_Type, &vec2, &vector_Type, &vec3 ) ) {
261                 PyErr_SetString( PyExc_TypeError, "expected 3 vector types\n" );
262                 return NULL;
263         }
264         if( vec1->size != vec2->size || vec1->size != vec3->size ) {
265                 PyErr_SetString( PyExc_TypeError, "vectors must be of the same size\n" );
266                 return NULL;
267         }
268         if( vec1->size != 3 ) {
269                 PyErr_SetString( PyExc_TypeError, "only 3D vectors\n" );
270                 return NULL;
271         }
272
273         if(!BaseMath_ReadCallback(vec1) || !BaseMath_ReadCallback(vec2) || !BaseMath_ReadCallback(vec3))
274                 return NULL;
275
276         VECCOPY(v1, vec1->vec);
277         VECCOPY(v2, vec2->vec);
278         VECCOPY(v3, vec3->vec);
279
280         /* find vectors for two edges sharing v2 */
281         sub_v3_v3v3(e1, v1, v2);
282         sub_v3_v3v3(e2, v3, v2);
283
284         cross_v3_v3v3(n, e2, e1);
285         normalize_v3(n);
286
287         return newVectorObject(n, 3, Py_NEW, NULL);
288 }
289
290 //--------------------------------- AREA FUNCTIONS--------------------
291 //----------------------------------Mathutils.TriangleArea() -------------------
292 static PyObject *M_Geometry_TriangleArea( PyObject * self, PyObject * args )
293 {
294         VectorObject *vec1, *vec2, *vec3;
295         float v1[3], v2[3], v3[3];
296
297         if( !PyArg_ParseTuple
298             ( args, "O!O!O!", &vector_Type, &vec1, &vector_Type, &vec2
299                 , &vector_Type, &vec3 ) ) {
300                 PyErr_SetString( PyExc_TypeError, "expected 3 vector types\n");
301                 return NULL;
302         }
303         if( vec1->size != vec2->size || vec1->size != vec3->size ) {
304                 PyErr_SetString( PyExc_TypeError, "vectors must be of the same size\n" );
305                 return NULL;
306         }
307
308         if(!BaseMath_ReadCallback(vec1) || !BaseMath_ReadCallback(vec2) || !BaseMath_ReadCallback(vec3))
309                 return NULL;
310
311         if (vec1->size == 3) {
312                 VECCOPY(v1, vec1->vec);
313                 VECCOPY(v2, vec2->vec);
314                 VECCOPY(v3, vec3->vec);
315
316                 return PyFloat_FromDouble( area_tri_v3(v1, v2, v3) );
317         }
318         else if (vec1->size == 2) {
319                 v1[0] = vec1->vec[0];
320                 v1[1] = vec1->vec[1];
321
322                 v2[0] = vec2->vec[0];
323                 v2[1] = vec2->vec[1];
324
325                 v3[0] = vec3->vec[0];
326                 v3[1] = vec3->vec[1];
327
328                 return PyFloat_FromDouble( area_tri_v2(v1, v2, v3) );
329         }
330         else {
331                 PyErr_SetString( PyExc_TypeError, "only 2D,3D vectors are supported\n" );
332                 return NULL;
333         }
334 }
335
336 /*----------------------------------Geometry.PolyFill() -------------------*/
337 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
338 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * polyLineSeq )
339 {
340         PyObject *tri_list; /*return this list of tri's */
341         PyObject *polyLine, *polyVec;
342         int i, len_polylines, len_polypoints, ls_error = 0;
343         
344         /* display listbase */
345         ListBase dispbase={NULL, NULL};
346         DispList *dl;
347         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
348         int index, *dl_face, totpoints=0;
349         
350         
351         dispbase.first= dispbase.last= NULL;
352         
353         
354         if(!PySequence_Check(polyLineSeq)) {
355                 PyErr_SetString( PyExc_TypeError, "expected a sequence of poly lines" );
356                 return NULL;
357         }
358         
359         len_polylines = PySequence_Size( polyLineSeq );
360         
361         for( i = 0; i < len_polylines; ++i ) {
362                 polyLine= PySequence_GetItem( polyLineSeq, i );
363                 if (!PySequence_Check(polyLine)) {
364                         freedisplist(&dispbase);
365                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
366                         PyErr_SetString( PyExc_TypeError, "One or more of the polylines is not a sequence of Mathutils.Vector's" );
367                         return NULL;
368                 }
369                 
370                 len_polypoints= PySequence_Size( polyLine );
371                 if (len_polypoints>0) { /* dont bother adding edges as polylines */
372 #if 0
373                         if (EXPP_check_sequence_consistency( polyLine, &vector_Type ) != 1) {
374                                 freedisplist(&dispbase);
375                                 Py_DECREF(polyLine);
376                                 PyErr_SetString( PyExc_TypeError, "A point in one of the polylines is not a Mathutils.Vector type" );
377                                 return NULL;
378                         }
379 #endif
380                         dl= MEM_callocN(sizeof(DispList), "poly disp");
381                         BLI_addtail(&dispbase, dl);
382                         dl->type= DL_INDEX3;
383                         dl->nr= len_polypoints;
384                         dl->type= DL_POLY;
385                         dl->parts= 1; /* no faces, 1 edge loop */
386                         dl->col= 0; /* no material */
387                         dl->verts= fp= MEM_callocN( sizeof(float)*3*len_polypoints, "dl verts");
388                         dl->index= MEM_callocN(sizeof(int)*3*len_polypoints, "dl index");
389                         
390                         for( index = 0; index<len_polypoints; ++index, fp+=3) {
391                                 polyVec= PySequence_GetItem( polyLine, index );
392                                 if(VectorObject_Check(polyVec)) {
393                                         
394                                         if(!BaseMath_ReadCallback((VectorObject *)polyVec))
395                                                 ls_error= 1;
396                                         
397                                         fp[0] = ((VectorObject *)polyVec)->vec[0];
398                                         fp[1] = ((VectorObject *)polyVec)->vec[1];
399                                         if( ((VectorObject *)polyVec)->size > 2 )
400                                                 fp[2] = ((VectorObject *)polyVec)->vec[2];
401                                         else
402                                                 fp[2]= 0.0f; /* if its a 2d vector then set the z to be zero */
403                                 }
404                                 else {
405                                         ls_error= 1;
406                                 }
407                                 
408                                 totpoints++;
409                                 Py_DECREF(polyVec);
410                         }
411                 }
412                 Py_DECREF(polyLine);
413         }
414         
415         if(ls_error) {
416                 freedisplist(&dispbase); /* possible some dl was allocated */
417                 PyErr_SetString( PyExc_TypeError, "A point in one of the polylines is not a Mathutils.Vector type" );
418                 return NULL;
419         }
420         else if (totpoints) {
421                 /* now make the list to return */
422                 filldisplist(&dispbase, &dispbase);
423                 
424                 /* The faces are stored in a new DisplayList
425                 thats added to the head of the listbase */
426                 dl= dispbase.first; 
427                 
428                 tri_list= PyList_New(dl->parts);
429                 if( !tri_list ) {
430                         freedisplist(&dispbase);
431                         PyErr_SetString( PyExc_RuntimeError, "Geometry.PolyFill failed to make a new list" );
432                         return NULL;
433                 }
434                 
435                 index= 0;
436                 dl_face= dl->index;
437                 while(index < dl->parts) {
438                         PyList_SetItem(tri_list, index, Py_BuildValue("iii", dl_face[0], dl_face[1], dl_face[2]) );
439                         dl_face+= 3;
440                         index++;
441                 }
442                 freedisplist(&dispbase);
443         } else {
444                 /* no points, do this so scripts dont barf */
445                 freedisplist(&dispbase); /* possible some dl was allocated */
446                 tri_list= PyList_New(0);
447         }
448         
449         return tri_list;
450 }
451
452
453 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args )
454 {
455         VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
456         float a1x, a1y, a2x, a2y,  b1x, b1y, b2x, b2y, xi, yi, a1,a2,b1,b2, newvec[2];
457         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
458           &vector_Type, &line_a1,
459           &vector_Type, &line_a2,
460           &vector_Type, &line_b1,
461           &vector_Type, &line_b2)
462         ) {
463                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types\n" );
464                 return NULL;
465         }
466         
467         if(!BaseMath_ReadCallback(line_a1) || !BaseMath_ReadCallback(line_a2) || !BaseMath_ReadCallback(line_b1) || !BaseMath_ReadCallback(line_b2))
468                 return NULL;
469         
470         a1x= line_a1->vec[0];
471         a1y= line_a1->vec[1];
472         a2x= line_a2->vec[0];
473         a2y= line_a2->vec[1];
474
475         b1x= line_b1->vec[0];
476         b1y= line_b1->vec[1];
477         b2x= line_b2->vec[0];
478         b2y= line_b2->vec[1];
479         
480         if((MIN2(a1x, a2x) > MAX2(b1x, b2x)) ||
481            (MAX2(a1x, a2x) < MIN2(b1x, b2x)) ||
482            (MIN2(a1y, a2y) > MAX2(b1y, b2y)) ||
483            (MAX2(a1y, a2y) < MIN2(b1y, b2y))  ) {
484                 Py_RETURN_NONE;
485         }
486         /* Make sure the hoz/vert line comes first. */
487         if (fabs(b1x - b2x) < eps || fabs(b1y - b2y) < eps) {
488                 SWAP_FLOAT(a1x, b1x, xi); /*abuse xi*/
489                 SWAP_FLOAT(a1y, b1y, xi);
490                 SWAP_FLOAT(a2x, b2x, xi);
491                 SWAP_FLOAT(a2y, b2y, xi);
492         }
493         
494         if (fabs(a1x-a2x) < eps) { /* verticle line */
495                 if (fabs(b1x-b2x) < eps){ /*verticle second line */
496                         Py_RETURN_NONE; /* 2 verticle lines dont intersect. */
497                 }
498                 else if (fabs(b1y-b2y) < eps) {
499                         /*X of vert, Y of hoz. no calculation needed */
500                         newvec[0]= a1x;
501                         newvec[1]= b1y;
502                         return newVectorObject(newvec, 2, Py_NEW, NULL);
503                 }
504                 
505                 yi = (float)(((b1y / fabs(b1x - b2x)) * fabs(b2x - a1x)) + ((b2y / fabs(b1x - b2x)) * fabs(b1x - a1x)));
506                 
507                 if (yi > MAX2(a1y, a2y)) {/* New point above seg1's vert line */
508                         Py_RETURN_NONE;
509                 } else if (yi < MIN2(a1y, a2y)) { /* New point below seg1's vert line */
510                         Py_RETURN_NONE;
511                 }
512                 newvec[0]= a1x;
513                 newvec[1]= yi;
514                 return newVectorObject(newvec, 2, Py_NEW, NULL);
515         } else if (fabs(a2y-a1y) < eps) {  /* hoz line1 */
516                 if (fabs(b2y-b1y) < eps) { /*hoz line2*/
517                         Py_RETURN_NONE; /*2 hoz lines dont intersect*/
518                 }
519                 
520                 /* Can skip vert line check for seg 2 since its covered above. */
521                 xi = (float)(((b1x / fabs(b1y - b2y)) * fabs(b2y - a1y)) + ((b2x / fabs(b1y - b2y)) * fabs(b1y - a1y)));
522                 if (xi > MAX2(a1x, a2x)) { /* New point right of hoz line1's */
523                         Py_RETURN_NONE;
524                 } else if (xi < MIN2(a1x, a2x)) { /*New point left of seg1's hoz line */
525                         Py_RETURN_NONE;
526                 }
527                 newvec[0]= xi;
528                 newvec[1]= a1y;
529                 return newVectorObject(newvec, 2, Py_NEW, NULL);
530         }
531         
532         b1 = (a2y-a1y)/(a2x-a1x);
533         b2 = (b2y-b1y)/(b2x-b1x);
534         a1 = a1y-b1*a1x;
535         a2 = b1y-b2*b1x;
536         
537         if (b1 - b2 == 0.0) {
538                 Py_RETURN_NONE;
539         }
540         
541         xi = - (a1-a2)/(b1-b2);
542         yi = a1+b1*xi;
543         if ((a1x-xi)*(xi-a2x) >= 0 && (b1x-xi)*(xi-b2x) >= 0 && (a1y-yi)*(yi-a2y) >= 0 && (b1y-yi)*(yi-b2y)>=0) {
544                 newvec[0]= xi;
545                 newvec[1]= yi;
546                 return newVectorObject(newvec, 2, Py_NEW, NULL);
547         }
548         Py_RETURN_NONE;
549 }
550
551 static PyObject *M_Geometry_ClosestPointOnLine( PyObject * self, PyObject * args )
552 {
553         VectorObject *pt, *line_1, *line_2;
554         float pt_in[3], pt_out[3], l1[3], l2[3];
555         float lambda;
556         PyObject *ret;
557         
558         if( !PyArg_ParseTuple ( args, "O!O!O!",
559         &vector_Type, &pt,
560         &vector_Type, &line_1,
561         &vector_Type, &line_2)
562           ) {
563                 PyErr_SetString( PyExc_TypeError, "expected 3 vector types\n" );
564                 return NULL;
565         }
566         
567         if(!BaseMath_ReadCallback(pt) || !BaseMath_ReadCallback(line_1) || !BaseMath_ReadCallback(line_2))
568                 return NULL;
569         
570         /* accept 2d verts */
571         if (pt->size==3) { VECCOPY(pt_in, pt->vec);}
572         else { pt_in[2]=0.0;    VECCOPY2D(pt_in, pt->vec) }
573         
574         if (line_1->size==3) { VECCOPY(l1, line_1->vec);}
575         else { l1[2]=0.0;       VECCOPY2D(l1, line_1->vec) }
576         
577         if (line_2->size==3) { VECCOPY(l2, line_2->vec);}
578         else { l2[2]=0.0;       VECCOPY2D(l2, line_2->vec) }
579         
580         /* do the calculation */
581         lambda = closest_to_line_v3( pt_out,pt_in, l1, l2);
582         
583         ret = PyTuple_New(2);
584         PyTuple_SET_ITEM( ret, 0, newVectorObject(pt_out, 3, Py_NEW, NULL) );
585         PyTuple_SET_ITEM( ret, 1, PyFloat_FromDouble(lambda) );
586         return ret;
587 }
588
589 static PyObject *M_Geometry_PointInTriangle2D( PyObject * self, PyObject * args )
590 {
591         VectorObject *pt_vec, *tri_p1, *tri_p2, *tri_p3;
592         
593         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
594           &vector_Type, &pt_vec,
595           &vector_Type, &tri_p1,
596           &vector_Type, &tri_p2,
597           &vector_Type, &tri_p3)
598         ) {
599                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types\n" );
600                 return NULL;
601         }
602         
603         if(!BaseMath_ReadCallback(pt_vec) || !BaseMath_ReadCallback(tri_p1) || !BaseMath_ReadCallback(tri_p2) || !BaseMath_ReadCallback(tri_p3))
604                 return NULL;
605         
606         return PyLong_FromLong(isect_point_tri_v2(pt_vec->vec, tri_p1->vec, tri_p2->vec, tri_p3->vec));
607 }
608
609 static PyObject *M_Geometry_PointInQuad2D( PyObject * self, PyObject * args )
610 {
611         VectorObject *pt_vec, *quad_p1, *quad_p2, *quad_p3, *quad_p4;
612         
613         if( !PyArg_ParseTuple ( args, "O!O!O!O!O!",
614           &vector_Type, &pt_vec,
615           &vector_Type, &quad_p1,
616           &vector_Type, &quad_p2,
617           &vector_Type, &quad_p3,
618           &vector_Type, &quad_p4)
619         ) {
620                 PyErr_SetString( PyExc_TypeError, "expected 5 vector types\n" );
621                 return NULL;
622         }
623         
624         if(!BaseMath_ReadCallback(pt_vec) || !BaseMath_ReadCallback(quad_p1) || !BaseMath_ReadCallback(quad_p2) || !BaseMath_ReadCallback(quad_p3) || !BaseMath_ReadCallback(quad_p4))
625                 return NULL;
626         
627         return PyLong_FromLong(isect_point_quad_v2(pt_vec->vec, quad_p1->vec, quad_p2->vec, quad_p3->vec, quad_p4->vec));
628 }
629
630 static int boxPack_FromPyObject(PyObject * value, boxPack **boxarray )
631 {
632         int len, i;
633         PyObject *list_item, *item_1, *item_2;
634         boxPack *box;
635         
636         
637         /* Error checking must alredy be done */
638         if( !PyList_Check( value ) ) {
639                 PyErr_SetString( PyExc_TypeError, "can only back a list of [x,y,x,w]" );
640                 return -1;
641         }
642         
643         len = PyList_Size( value );
644         
645         (*boxarray) = MEM_mallocN( len*sizeof(boxPack), "boxPack box");
646         
647         
648         for( i = 0; i < len; i++ ) {
649                 list_item = PyList_GET_ITEM( value, i );
650                 if( !PyList_Check( list_item ) || PyList_Size( list_item ) < 4 ) {
651                         MEM_freeN(*boxarray);
652                         PyErr_SetString( PyExc_TypeError, "can only back a list of [x,y,x,w]" );
653                         return -1;
654                 }
655                 
656                 box = (*boxarray)+i;
657                 
658                 item_1 = PyList_GET_ITEM(list_item, 2);
659                 item_2 = PyList_GET_ITEM(list_item, 3);
660                 
661                 if (!PyNumber_Check(item_1) || !PyNumber_Check(item_2)) {
662                         MEM_freeN(*boxarray);
663                         PyErr_SetString( PyExc_TypeError, "can only back a list of 2d boxes [x,y,x,w]" );
664                         return -1;
665                 }
666                 
667                 box->w =  (float)PyFloat_AsDouble( item_1 );
668                 box->h =  (float)PyFloat_AsDouble( item_2 );
669                 box->index = i;
670                 /* verts will be added later */
671         }
672         return 0;
673 }
674
675 static void boxPack_ToPyObject(PyObject * value, boxPack **boxarray)
676 {
677         int len, i;
678         PyObject *list_item;
679         boxPack *box;
680         
681         len = PyList_Size( value );
682         
683         for( i = 0; i < len; i++ ) {
684                 box = (*boxarray)+i;
685                 list_item = PyList_GET_ITEM( value, box->index );
686                 PyList_SET_ITEM( list_item, 0, PyFloat_FromDouble( box->x ));
687                 PyList_SET_ITEM( list_item, 1, PyFloat_FromDouble( box->y ));
688         }
689         MEM_freeN(*boxarray);
690 }
691
692
693 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * boxlist )
694 {
695         boxPack *boxarray = NULL;
696         float tot_width, tot_height;
697         int len;
698         int error;
699         
700         if(!PyList_Check(boxlist)) {
701                 PyErr_SetString( PyExc_TypeError, "expected a sequence of boxes [[x,y,w,h], ... ]" );
702                 return NULL;
703         }
704         
705         len = PyList_Size( boxlist );
706         
707         if (!len)
708                 return Py_BuildValue( "ff", 0.0, 0.0);
709         
710         error = boxPack_FromPyObject(boxlist, &boxarray);
711         if (error!=0)   return NULL;
712         
713         /* Non Python function */
714         boxPack2D(boxarray, len, &tot_width, &tot_height);
715         
716         boxPack_ToPyObject(boxlist, &boxarray);
717         
718         return Py_BuildValue( "ff", tot_width, tot_height);
719 }
720
721 static PyObject *M_Geometry_BezierInterp( PyObject * self, PyObject * args )
722 {
723         VectorObject *vec_k1, *vec_h1, *vec_k2, *vec_h2;
724         int resolu;
725         int dims;
726         int i;
727         float *coord_array, *fp;
728         PyObject *list;
729         
730         float k1[4] = {0.0, 0.0, 0.0, 0.0};
731         float h1[4] = {0.0, 0.0, 0.0, 0.0};
732         float k2[4] = {0.0, 0.0, 0.0, 0.0};
733         float h2[4] = {0.0, 0.0, 0.0, 0.0};
734         
735         
736         if( !PyArg_ParseTuple ( args, "O!O!O!O!i",
737           &vector_Type, &vec_k1,
738           &vector_Type, &vec_h1,
739           &vector_Type, &vec_h2,
740           &vector_Type, &vec_k2, &resolu) || (resolu<=1)
741         ) {
742                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types and an int greater then 1\n" );
743                 return NULL;
744         }
745         
746         if(!BaseMath_ReadCallback(vec_k1) || !BaseMath_ReadCallback(vec_h1) || !BaseMath_ReadCallback(vec_k2) || !BaseMath_ReadCallback(vec_h2))
747                 return NULL;
748         
749         dims= MAX4(vec_k1->size, vec_h1->size, vec_h2->size, vec_k2->size);
750         
751         for(i=0; i < vec_k1->size; i++) k1[i]= vec_k1->vec[i];
752         for(i=0; i < vec_h1->size; i++) h1[i]= vec_h1->vec[i];
753         for(i=0; i < vec_k2->size; i++) k2[i]= vec_k2->vec[i];
754         for(i=0; i < vec_h2->size; i++) h2[i]= vec_h2->vec[i];
755         
756         coord_array = MEM_callocN(dims * (resolu) * sizeof(float), "BezierInterp");
757         for(i=0; i<dims; i++) {
758                 forward_diff_bezier(k1[i], h1[i], h2[i], k2[i], coord_array+i, resolu-1, sizeof(float)*dims);
759         }
760         
761         list= PyList_New(resolu);
762         fp= coord_array;
763         for(i=0; i<resolu; i++, fp= fp+dims) {
764                 PyList_SET_ITEM(list, i, newVectorObject(fp, dims, Py_NEW, NULL));
765         }
766         MEM_freeN(coord_array);
767         return list;
768 }
769
770 static PyObject *M_Geometry_BarycentricTransform(PyObject * self, PyObject * args)
771 {
772         VectorObject *vec_pt;
773         VectorObject *vec_t1_tar, *vec_t2_tar, *vec_t3_tar;
774         VectorObject *vec_t1_src, *vec_t2_src, *vec_t3_src;
775         float vec[3];
776
777         if( !PyArg_ParseTuple ( args, "O!O!O!O!O!O!O!",
778           &vector_Type, &vec_pt,
779           &vector_Type, &vec_t1_src,
780           &vector_Type, &vec_t2_src,
781           &vector_Type, &vec_t3_src,
782           &vector_Type, &vec_t1_tar,
783           &vector_Type, &vec_t2_tar,
784           &vector_Type, &vec_t3_tar) || (       vec_pt->size != 3 ||
785                                                                                 vec_t1_src->size != 3 ||
786                                                                                 vec_t2_src->size != 3 ||
787                                                                                 vec_t3_src->size != 3 ||
788                                                                                 vec_t1_tar->size != 3 ||
789                                                                                 vec_t2_tar->size != 3 ||
790                                                                                 vec_t3_tar->size != 3)
791         ) {
792                 PyErr_SetString( PyExc_TypeError, "expected 7, 3D vector types\n" );
793                 return NULL;
794         }
795
796         barycentric_transform(vec, vec_pt->vec,
797                         vec_t1_tar->vec, vec_t2_tar->vec, vec_t3_tar->vec,
798                         vec_t1_src->vec, vec_t2_src->vec, vec_t3_src->vec);
799
800         return newVectorObject(vec, 3, Py_NEW, NULL);
801 }
802
803 struct PyMethodDef M_Geometry_methods[] = {
804         {"Intersect", ( PyCFunction ) M_Geometry_Intersect, METH_VARARGS, M_Geometry_Intersect_doc},
805         {"TriangleArea", ( PyCFunction ) M_Geometry_TriangleArea, METH_VARARGS, M_Geometry_TriangleArea_doc},
806         {"TriangleNormal", ( PyCFunction ) M_Geometry_TriangleNormal, METH_VARARGS, M_Geometry_TriangleNormal_doc},
807         {"QuadNormal", ( PyCFunction ) M_Geometry_QuadNormal, METH_VARARGS, M_Geometry_QuadNormal_doc},
808         {"LineIntersect", ( PyCFunction ) M_Geometry_LineIntersect, METH_VARARGS, M_Geometry_LineIntersect_doc},
809         {"PolyFill", ( PyCFunction ) M_Geometry_PolyFill, METH_O, M_Geometry_PolyFill_doc},
810         {"LineIntersect2D", ( PyCFunction ) M_Geometry_LineIntersect2D, METH_VARARGS, M_Geometry_LineIntersect2D_doc},
811         {"ClosestPointOnLine", ( PyCFunction ) M_Geometry_ClosestPointOnLine, METH_VARARGS, M_Geometry_ClosestPointOnLine_doc},
812         {"PointInTriangle2D", ( PyCFunction ) M_Geometry_PointInTriangle2D, METH_VARARGS, M_Geometry_PointInTriangle2D_doc},
813         {"PointInQuad2D", ( PyCFunction ) M_Geometry_PointInQuad2D, METH_VARARGS, M_Geometry_PointInQuad2D_doc},
814         {"BoxPack2D", ( PyCFunction ) M_Geometry_BoxPack2D, METH_O, M_Geometry_BoxPack2D_doc},
815         {"BezierInterp", ( PyCFunction ) M_Geometry_BezierInterp, METH_VARARGS, M_Geometry_BezierInterp_doc},
816         {"BarycentricTransform", ( PyCFunction ) M_Geometry_BarycentricTransform, METH_VARARGS, NULL},
817         {NULL, NULL, 0, NULL}
818 };
819
820 static struct PyModuleDef M_Geometry_module_def = {
821         PyModuleDef_HEAD_INIT,
822         "Geometry",  /* m_name */
823         M_Geometry_doc,  /* m_doc */
824         0,  /* m_size */
825         M_Geometry_methods,  /* m_methods */
826         0,  /* m_reload */
827         0,  /* m_traverse */
828         0,  /* m_clear */
829         0,  /* m_free */
830 };
831
832 /*----------------------------MODULE INIT-------------------------*/
833 PyObject *Geometry_Init(void)
834 {
835         PyObject *submodule;
836
837         submodule = PyModule_Create(&M_Geometry_module_def);
838         PyDict_SetItemString(PySys_GetObject("modules"), M_Geometry_module_def.m_name, submodule);
839
840         return (submodule);
841 }