BGE Py API
[blender.git] / source / blender / python / api2_2x / 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., 59 Temple Place - Suite 330, Boston, MA        02111-1307, 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 /*  - Not needed for now though other geometry functions will probably need them
33 #include "BLI_arithb.h"
34 #include "BKE_utildefines.h"
35 */
36
37 /* Used for PolyFill */
38 #include "BKE_displist.h"
39 #include "MEM_guardedalloc.h"
40 #include "BLI_blenlib.h"
41  
42 #include "BKE_utildefines.h"
43 #include "BKE_curve.h"
44 #include "BLI_boxpack2d.h"
45 #include "BLI_arithb.h"
46
47 #define SWAP_FLOAT(a,b,tmp) tmp=a; a=b; b=tmp
48 #define eul 0.000001
49
50 /*-- forward declarations -- */
51 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * polyLineSeq );
52 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args );
53 static PyObject *M_Geometry_ClosestPointOnLine( PyObject * self, PyObject * args );
54 static PyObject *M_Geometry_PointInTriangle2D( PyObject * self, PyObject * args );
55 static PyObject *M_Geometry_PointInQuad2D( PyObject * self, PyObject * args );
56 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args );
57 static PyObject *M_Geometry_BezierInterp( PyObject * self, PyObject * args );
58
59
60 /*-------------------------DOC STRINGS ---------------------------*/
61 static char M_Geometry_doc[] = "The Blender Geometry module\n\n";
62 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";
63 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";
64 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";
65 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";
66 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";
67 static char M_Geometry_BoxPack2D_doc[] = "";
68 static char M_Geometry_BezierInterp_doc[] = "";
69 /*-----------------------METHOD DEFINITIONS ----------------------*/
70 struct PyMethodDef M_Geometry_methods[] = {
71         {"PolyFill", ( PyCFunction ) M_Geometry_PolyFill, METH_O, M_Geometry_PolyFill_doc},
72         {"LineIntersect2D", ( PyCFunction ) M_Geometry_LineIntersect2D, METH_VARARGS, M_Geometry_LineIntersect2D_doc},
73         {"ClosestPointOnLine", ( PyCFunction ) M_Geometry_ClosestPointOnLine, METH_VARARGS, M_Geometry_ClosestPointOnLine_doc},
74         {"PointInTriangle2D", ( PyCFunction ) M_Geometry_PointInTriangle2D, METH_VARARGS, M_Geometry_PointInTriangle2D_doc},
75         {"PointInQuad2D", ( PyCFunction ) M_Geometry_PointInQuad2D, METH_VARARGS, M_Geometry_PointInQuad2D_doc},
76         {"BoxPack2D", ( PyCFunction ) M_Geometry_BoxPack2D, METH_O, M_Geometry_BoxPack2D_doc},
77         {"BezierInterp", ( PyCFunction ) M_Geometry_BezierInterp, METH_VARARGS, M_Geometry_BezierInterp_doc},
78         {NULL, NULL, 0, NULL}
79 };
80
81 #if (PY_VERSION_HEX >= 0x03000000)
82 static struct PyModuleDef M_Geometry_module_def = {
83         {}, /* m_base */
84         "Geometry",  /* m_name */
85         M_Geometry_doc,  /* m_doc */
86         0,  /* m_size */
87         M_Geometry_methods,  /* m_methods */
88         0,  /* m_reload */
89         0,  /* m_traverse */
90         0,  /* m_clear */
91         0,  /* m_free */
92 };
93 #endif
94
95 /*----------------------------MODULE INIT-------------------------*/
96 PyObject *Geometry_Init(const char *from)
97 {
98         PyObject *submodule;
99         
100 #if (PY_VERSION_HEX >= 0x03000000)
101         submodule = PyModule_Create(&M_Geometry_module_def);
102         PyDict_SetItemString(PySys_GetObject("modules"), M_Geometry_module_def.m_name, submodule);
103 #else
104         submodule = Py_InitModule3(from, M_Geometry_methods, M_Geometry_doc);
105 #endif
106         
107         return (submodule);
108 }
109
110 /*----------------------------------Geometry.PolyFill() -------------------*/
111 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
112 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * polyLineSeq )
113 {
114         PyObject *tri_list; /*return this list of tri's */
115         PyObject *polyLine, *polyVec;
116         int i, len_polylines, len_polypoints, ls_error = 0;
117         
118         /* display listbase */
119         ListBase dispbase={NULL, NULL};
120         DispList *dl;
121         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
122         int index, *dl_face, totpoints=0;
123         
124         
125         dispbase.first= dispbase.last= NULL;
126         
127         
128         if(!PySequence_Check(polyLineSeq)) {
129                 PyErr_SetString( PyExc_TypeError, "expected a sequence of poly lines" );
130                 return NULL;
131         }
132         
133         len_polylines = PySequence_Size( polyLineSeq );
134         
135         for( i = 0; i < len_polylines; ++i ) {
136                 polyLine= PySequence_GetItem( polyLineSeq, i );
137                 if (!PySequence_Check(polyLine)) {
138                         freedisplist(&dispbase);
139                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
140                         PyErr_SetString( PyExc_TypeError, "One or more of the polylines is not a sequence of Mathutils.Vector's" );
141                         return NULL;
142                 }
143                 
144                 len_polypoints= PySequence_Size( polyLine );
145                 if (len_polypoints>0) { /* dont bother adding edges as polylines */
146 #if 0
147                         if (EXPP_check_sequence_consistency( polyLine, &vector_Type ) != 1) {
148                                 freedisplist(&dispbase);
149                                 Py_DECREF(polyLine);
150                                 PyErr_SetString( PyExc_TypeError, "A point in one of the polylines is not a Mathutils.Vector type" );
151                                 return NULL;
152                         }
153 #endif
154                         dl= MEM_callocN(sizeof(DispList), "poly disp");
155                         BLI_addtail(&dispbase, dl);
156                         dl->type= DL_INDEX3;
157                         dl->nr= len_polypoints;
158                         dl->type= DL_POLY;
159                         dl->parts= 1; /* no faces, 1 edge loop */
160                         dl->col= 0; /* no material */
161                         dl->verts= fp= MEM_callocN( sizeof(float)*3*len_polypoints, "dl verts");
162                         dl->index= MEM_callocN(sizeof(int)*3*len_polypoints, "dl index");
163                         
164                         for( index = 0; index<len_polypoints; ++index, fp+=3) {
165                                 polyVec= PySequence_GetItem( polyLine, index );
166                                 if(VectorObject_Check(polyVec)) {
167                                         fp[0] = ((VectorObject *)polyVec)->vec[0];
168                                         fp[1] = ((VectorObject *)polyVec)->vec[1];
169                                         if( ((VectorObject *)polyVec)->size > 2 )
170                                                 fp[2] = ((VectorObject *)polyVec)->vec[2];
171                                         else
172                                                 fp[2]= 0.0f; /* if its a 2d vector then set the z to be zero */
173                                 }
174                                 else {
175                                         ls_error= 1;
176                                 }
177                                 
178                                 totpoints++;
179                                 Py_DECREF(polyVec);
180                         }
181                 }
182                 Py_DECREF(polyLine);
183         }
184         
185         if(ls_error) {
186                 freedisplist(&dispbase); /* possible some dl was allocated */
187                 PyErr_SetString( PyExc_TypeError, "A point in one of the polylines is not a Mathutils.Vector type" );
188                 return NULL;
189         }
190         else if (totpoints) {
191                 /* now make the list to return */
192                 filldisplist(&dispbase, &dispbase);
193                 
194                 /* The faces are stored in a new DisplayList
195                 thats added to the head of the listbase */
196                 dl= dispbase.first; 
197                 
198                 tri_list= PyList_New(dl->parts);
199                 if( !tri_list ) {
200                         freedisplist(&dispbase);
201                         PyErr_SetString( PyExc_RuntimeError, "Geometry.PolyFill failed to make a new list" );
202                         return NULL;
203                 }
204                 
205                 index= 0;
206                 dl_face= dl->index;
207                 while(index < dl->parts) {
208                         PyList_SetItem(tri_list, index, Py_BuildValue("iii", dl_face[0], dl_face[1], dl_face[2]) );
209                         dl_face+= 3;
210                         index++;
211                 }
212                 freedisplist(&dispbase);
213         } else {
214                 /* no points, do this so scripts dont barf */
215                 freedisplist(&dispbase); /* possible some dl was allocated */
216                 tri_list= PyList_New(0);
217         }
218         
219         return tri_list;
220 }
221
222
223 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args )
224 {
225         VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
226         float a1x, a1y, a2x, a2y,  b1x, b1y, b2x, b2y, xi, yi, a1,a2,b1,b2, newvec[2];
227         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
228           &vector_Type, &line_a1,
229           &vector_Type, &line_a2,
230           &vector_Type, &line_b1,
231           &vector_Type, &line_b2)
232         ) {
233                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types\n" );
234                 return NULL;
235         }
236         
237         a1x= line_a1->vec[0];
238         a1y= line_a1->vec[1];
239         a2x= line_a2->vec[0];
240         a2y= line_a2->vec[1];
241
242         b1x= line_b1->vec[0];
243         b1y= line_b1->vec[1];
244         b2x= line_b2->vec[0];
245         b2y= line_b2->vec[1];
246         
247         if((MIN2(a1x, a2x) > MAX2(b1x, b2x)) ||
248            (MAX2(a1x, a2x) < MIN2(b1x, b2x)) ||
249            (MIN2(a1y, a2y) > MAX2(b1y, b2y)) ||
250            (MAX2(a1y, a2y) < MIN2(b1y, b2y))  ) {
251                 Py_RETURN_NONE;
252         }
253         /* Make sure the hoz/vert line comes first. */
254         if (fabs(b1x - b2x) < eul || fabs(b1y - b2y) < eul) {
255                 SWAP_FLOAT(a1x, b1x, xi); /*abuse xi*/
256                 SWAP_FLOAT(a1y, b1y, xi);
257                 SWAP_FLOAT(a2x, b2x, xi);
258                 SWAP_FLOAT(a2y, b2y, xi);
259         }
260         
261         if (fabs(a1x-a2x) < eul) { /* verticle line */
262                 if (fabs(b1x-b2x) < eul){ /*verticle second line */
263                         Py_RETURN_NONE; /* 2 verticle lines dont intersect. */
264                 }
265                 else if (fabs(b1y-b2y) < eul) {
266                         /*X of vert, Y of hoz. no calculation needed */
267                         newvec[0]= a1x;
268                         newvec[1]= b1y;
269                         return newVectorObject(newvec, 2, Py_NEW);
270                 }
271                 
272                 yi = (float)(((b1y / fabs(b1x - b2x)) * fabs(b2x - a1x)) + ((b2y / fabs(b1x - b2x)) * fabs(b1x - a1x)));
273                 
274                 if (yi > MAX2(a1y, a2y)) {/* New point above seg1's vert line */
275                         Py_RETURN_NONE;
276                 } else if (yi < MIN2(a1y, a2y)) { /* New point below seg1's vert line */
277                         Py_RETURN_NONE;
278                 }
279                 newvec[0]= a1x;
280                 newvec[1]= yi;
281                 return newVectorObject(newvec, 2, Py_NEW);
282         } else if (fabs(a2y-a1y) < eul) {  /* hoz line1 */
283                 if (fabs(b2y-b1y) < eul) { /*hoz line2*/
284                         Py_RETURN_NONE; /*2 hoz lines dont intersect*/
285                 }
286                 
287                 /* Can skip vert line check for seg 2 since its covered above. */
288                 xi = (float)(((b1x / fabs(b1y - b2y)) * fabs(b2y - a1y)) + ((b2x / fabs(b1y - b2y)) * fabs(b1y - a1y)));
289                 if (xi > MAX2(a1x, a2x)) { /* New point right of hoz line1's */
290                         Py_RETURN_NONE;
291                 } else if (xi < MIN2(a1x, a2x)) { /*New point left of seg1's hoz line */
292                         Py_RETURN_NONE;
293                 }
294                 newvec[0]= xi;
295                 newvec[1]= a1y;
296                 return newVectorObject(newvec, 2, Py_NEW);
297         }
298         
299         b1 = (a2y-a1y)/(a2x-a1x);
300         b2 = (b2y-b1y)/(b2x-b1x);
301         a1 = a1y-b1*a1x;
302         a2 = b1y-b2*b1x;
303         
304         if (b1 - b2 == 0.0) {
305                 Py_RETURN_NONE;
306         }
307         
308         xi = - (a1-a2)/(b1-b2);
309         yi = a1+b1*xi;
310         if ((a1x-xi)*(xi-a2x) >= 0 && (b1x-xi)*(xi-b2x) >= 0 && (a1y-yi)*(yi-a2y) >= 0 && (b1y-yi)*(yi-b2y)>=0) {
311                 newvec[0]= xi;
312                 newvec[1]= yi;
313                 return newVectorObject(newvec, 2, Py_NEW);
314         }
315         Py_RETURN_NONE;
316 }
317
318 static PyObject *M_Geometry_ClosestPointOnLine( PyObject * self, PyObject * args )
319 {
320         VectorObject *pt, *line_1, *line_2;
321         float pt_in[3], pt_out[3], l1[3], l2[3];
322         float lambda;
323         PyObject *ret;
324         
325         if( !PyArg_ParseTuple ( args, "O!O!O!",
326         &vector_Type, &pt,
327         &vector_Type, &line_1,
328         &vector_Type, &line_2)
329           ) {
330                 PyErr_SetString( PyExc_TypeError, "expected 3 vector types\n" );
331                 return NULL;
332         }
333         /* accept 2d verts */
334         if (pt->size==3) { VECCOPY(pt_in, pt->vec);}
335         else { pt_in[2]=0.0;    VECCOPY2D(pt_in, pt->vec) }
336         
337         if (line_1->size==3) { VECCOPY(l1, line_1->vec);}
338         else { l1[2]=0.0;       VECCOPY2D(l1, line_1->vec) }
339         
340         if (line_2->size==3) { VECCOPY(l2, line_2->vec);}
341         else { l2[2]=0.0;       VECCOPY2D(l2, line_2->vec) }
342         
343         /* do the calculation */
344         lambda = lambda_cp_line_ex(pt_in, l1, l2, pt_out);
345         
346         ret = PyTuple_New(2);
347         PyTuple_SET_ITEM( ret, 0, newVectorObject(pt_out, 3, Py_NEW) );
348         PyTuple_SET_ITEM( ret, 1, PyFloat_FromDouble(lambda) );
349         return ret;
350 }
351
352 static PyObject *M_Geometry_PointInTriangle2D( PyObject * self, PyObject * args )
353 {
354         VectorObject *pt_vec, *tri_p1, *tri_p2, *tri_p3;
355         
356         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
357           &vector_Type, &pt_vec,
358           &vector_Type, &tri_p1,
359           &vector_Type, &tri_p2,
360           &vector_Type, &tri_p3)
361         ) {
362                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types\n" );
363                 return NULL;
364         }
365         
366         return PyInt_FromLong(IsectPT2Df(pt_vec->vec, tri_p1->vec, tri_p2->vec, tri_p3->vec));
367 }
368
369 static PyObject *M_Geometry_PointInQuad2D( PyObject * self, PyObject * args )
370 {
371         VectorObject *pt_vec, *quad_p1, *quad_p2, *quad_p3, *quad_p4;
372         
373         if( !PyArg_ParseTuple ( args, "O!O!O!O!O!",
374           &vector_Type, &pt_vec,
375           &vector_Type, &quad_p1,
376           &vector_Type, &quad_p2,
377           &vector_Type, &quad_p3,
378           &vector_Type, &quad_p4)
379         ) {
380                 PyErr_SetString( PyExc_TypeError, "expected 5 vector types\n" );
381                 return NULL;
382         }
383         
384         return PyInt_FromLong(IsectPQ2Df(pt_vec->vec, quad_p1->vec, quad_p2->vec, quad_p3->vec, quad_p4->vec));
385 }
386
387 static int boxPack_FromPyObject(PyObject * value, boxPack **boxarray )
388 {
389         int len, i;
390         PyObject *list_item, *item_1, *item_2;
391         boxPack *box;
392         
393         
394         /* Error checking must alredy be done */
395         if( !PyList_Check( value ) ) {
396                 PyErr_SetString( PyExc_TypeError, "can only back a list of [x,y,x,w]" );
397                 return -1;
398         }
399         
400         len = PyList_Size( value );
401         
402         (*boxarray) = MEM_mallocN( len*sizeof(boxPack), "boxPack box");
403         
404         
405         for( i = 0; i < len; i++ ) {
406                 list_item = PyList_GET_ITEM( value, i );
407                 if( !PyList_Check( list_item ) || PyList_Size( list_item ) < 4 ) {
408                         MEM_freeN(*boxarray);
409                         PyErr_SetString( PyExc_TypeError, "can only back a list of [x,y,x,w]" );
410                         return -1;
411                 }
412                 
413                 box = (*boxarray)+i;
414                 
415                 item_1 = PyList_GET_ITEM(list_item, 2);
416                 item_2 = PyList_GET_ITEM(list_item, 3);
417                 
418                 if (!PyNumber_Check(item_1) || !PyNumber_Check(item_2)) {
419                         MEM_freeN(*boxarray);
420                         PyErr_SetString( PyExc_TypeError, "can only back a list of 2d boxes [x,y,x,w]" );
421                         return -1;
422                 }
423                 
424                 box->w =  (float)PyFloat_AsDouble( item_1 );
425                 box->h =  (float)PyFloat_AsDouble( item_2 );
426                 box->index = i;
427                 /* verts will be added later */
428         }
429         return 0;
430 }
431
432 static void boxPack_ToPyObject(PyObject * value, boxPack **boxarray)
433 {
434         int len, i;
435         PyObject *list_item;
436         boxPack *box;
437         
438         len = PyList_Size( value );
439         
440         for( i = 0; i < len; i++ ) {
441                 box = (*boxarray)+i;
442                 list_item = PyList_GET_ITEM( value, box->index );
443                 PyList_SET_ITEM( list_item, 0, PyFloat_FromDouble( box->x ));
444                 PyList_SET_ITEM( list_item, 1, PyFloat_FromDouble( box->y ));
445         }
446         MEM_freeN(*boxarray);
447 }
448
449
450 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * boxlist )
451 {
452         boxPack *boxarray = NULL;
453         float tot_width, tot_height;
454         int len;
455         int error;
456         
457         if(!PyList_Check(boxlist)) {
458                 PyErr_SetString( PyExc_TypeError, "expected a sequence of boxes [[x,y,w,h], ... ]" );
459                 return NULL;
460         }
461         
462         len = PyList_Size( boxlist );
463         
464         if (!len)
465                 return Py_BuildValue( "ff", 0.0, 0.0);
466         
467         error = boxPack_FromPyObject(boxlist, &boxarray);
468         if (error!=0)   return NULL;
469         
470         /* Non Python function */
471         boxPack2D(boxarray, len, &tot_width, &tot_height);
472         
473         boxPack_ToPyObject(boxlist, &boxarray);
474         
475         return Py_BuildValue( "ff", tot_width, tot_height);
476 }
477
478 static PyObject *M_Geometry_BezierInterp( PyObject * self, PyObject * args )
479 {
480         VectorObject *vec_k1, *vec_h1, *vec_k2, *vec_h2;
481         int resolu;
482         int dims;
483         int i;
484         float *coord_array, *fp;
485         PyObject *list;
486         
487         float k1[4] = {0.0, 0.0, 0.0, 0.0};
488         float h1[4] = {0.0, 0.0, 0.0, 0.0};
489         float k2[4] = {0.0, 0.0, 0.0, 0.0};
490         float h2[4] = {0.0, 0.0, 0.0, 0.0};
491         
492         
493         if( !PyArg_ParseTuple ( args, "O!O!O!O!i",
494           &vector_Type, &vec_k1,
495           &vector_Type, &vec_h1,
496           &vector_Type, &vec_h2,
497           &vector_Type, &vec_k2, &resolu) || (resolu<=1)
498         ) {
499                 PyErr_SetString( PyExc_TypeError, "expected 4 vector types and an int greater then 1\n" );
500                 return NULL;
501         }
502         
503         dims= MAX4(vec_k1->size, vec_h1->size, vec_h2->size, vec_k2->size);
504         
505         for(i=0; i < vec_k1->size; i++) k1[i]= vec_k1->vec[i];
506         for(i=0; i < vec_h1->size; i++) h1[i]= vec_h1->vec[i];
507         for(i=0; i < vec_k2->size; i++) k2[i]= vec_k2->vec[i];
508         for(i=0; i < vec_h2->size; i++) h2[i]= vec_h2->vec[i];
509         
510         coord_array = MEM_callocN(dims * (resolu) * sizeof(float), "BezierInterp");
511         for(i=0; i<dims; i++) {
512                 forward_diff_bezier(k1[i], h1[i], h2[i], k2[i], coord_array+i, resolu-1, dims);
513         }
514         
515         list= PyList_New(resolu);
516         fp= coord_array;
517         for(i=0; i<resolu; i++, fp= fp+dims) {
518                 PyList_SET_ITEM(list, i, newVectorObject(fp, dims, Py_NEW));
519         }
520         MEM_freeN(coord_array);
521         return list;
522 }