==Python API==
[blender.git] / source / blender / python / api2_2x / Geometry.c
1 /* 
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA        02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * This is a new part of Blender.
27  *
28  * Contributor(s): Joseph Gilbert, Campbell Barton
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 #include "Geometry.h"
34
35 /*  - Not needed for now though other geometry functions will probably need them
36 #include "BLI_arithb.h"
37 #include "BKE_utildefines.h"
38 */
39
40 /* Used for PolyFill */
41 #include "BKE_displist.h"
42 #include "MEM_guardedalloc.h"
43 #include "BLI_blenlib.h"
44
45 /* needed for EXPP_ReturnPyObjError and EXPP_check_sequence_consistency */
46 #include "gen_utils.h"
47  
48 #include "BKE_utildefines.h"
49 #include "BLI_boxpack2d.h"
50 #include "BLI_arithb.h"
51
52 #define SWAP_FLOAT(a,b,tmp) tmp=a; a=b; b=tmp
53 #define eul 0.000001
54
55 /*-- forward declarations -- */
56 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * polyLineSeq );
57 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args );
58 static PyObject *M_Geometry_ClosestPointOnLine( PyObject * self, PyObject * args );
59 static PyObject *M_Geometry_PointInTriangle2D( PyObject * self, PyObject * args );
60 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args );
61
62
63 /*-------------------------DOC STRINGS ---------------------------*/
64 static char M_Geometry_doc[] = "The Blender Geometry module\n\n";
65 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";
66 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";
67 static char M_Geometry_ClosestPointOnLine_doc[] = "(pt, line_p1, line_p2) - takes a point and a line and returns a (Vector, Bool) for the point on the line, and the bool so you can know if the point was between the 2 points";
68 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 triabgle, only the x and y are used from the vectors";
69 static char M_Geometry_BoxPack2D_doc[] = "";
70 /*-----------------------METHOD DEFINITIONS ----------------------*/
71 struct PyMethodDef M_Geometry_methods[] = {
72         {"PolyFill", ( PyCFunction ) M_Geometry_PolyFill, METH_O, M_Geometry_PolyFill_doc},
73         {"LineIntersect2D", ( PyCFunction ) M_Geometry_LineIntersect2D, METH_VARARGS, M_Geometry_LineIntersect2D_doc},
74         {"ClosestPointOnLine", ( PyCFunction ) M_Geometry_ClosestPointOnLine, METH_VARARGS, M_Geometry_ClosestPointOnLine_doc},
75         {"PointInTriangle2D", ( PyCFunction ) M_Geometry_PointInTriangle2D, METH_VARARGS, M_Geometry_PointInTriangle2D_doc},
76         {"BoxPack2D", ( PyCFunction ) M_Geometry_BoxPack2D, METH_O, M_Geometry_BoxPack2D_doc},
77         {NULL, NULL, 0, NULL}
78 };
79 /*----------------------------MODULE INIT-------------------------*/
80 PyObject *Geometry_Init(void)
81 {
82         PyObject *submodule;
83
84         submodule = Py_InitModule3("Blender.Geometry",
85                                     M_Geometry_methods, M_Geometry_doc);
86         return (submodule);
87 }
88
89 /*----------------------------------Geometry.PolyFill() -------------------*/
90 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
91 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * polyLineSeq )
92 {
93         PyObject *tri_list; /*return this list of tri's */
94         PyObject *polyLine, *polyVec;
95         int i, len_polylines, len_polypoints;
96         
97         /* display listbase */
98         ListBase dispbase={NULL, NULL};
99         DispList *dl;
100         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
101         int index, *dl_face, totpoints=0;
102         
103         
104         dispbase.first= dispbase.last= NULL;
105         
106         
107         if(!PySequence_Check(polyLineSeq)) {
108                 return EXPP_ReturnPyObjError( PyExc_TypeError,
109                                               "expected a sequence of poly lines" );
110         }
111         
112         len_polylines = PySequence_Size( polyLineSeq );
113         
114         for( i = 0; i < len_polylines; ++i ) {
115                 polyLine= PySequence_GetItem( polyLineSeq, i );
116                 if (!PySequence_Check(polyLine)) {
117                         freedisplist(&dispbase);
118                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
119                         return EXPP_ReturnPyObjError( PyExc_TypeError,
120                                   "One or more of the polylines is not a sequence of Mathutils.Vector's" );
121                 }
122                 
123                 len_polypoints= PySequence_Size( polyLine );
124                 if (len_polypoints>0) { /* dont bother adding edges as polylines */
125                         if (EXPP_check_sequence_consistency( polyLine, &vector_Type ) != 1) {
126                                 freedisplist(&dispbase);
127                                 Py_DECREF(polyLine);
128                                 return EXPP_ReturnPyObjError( PyExc_TypeError,
129                                           "A point in one of the polylines is not a Mathutils.Vector type" );
130                         }
131                         
132                         dl= MEM_callocN(sizeof(DispList), "poly disp");
133                         BLI_addtail(&dispbase, dl);
134                         dl->type= DL_INDEX3;
135                         dl->nr= len_polypoints;
136                         dl->type= DL_POLY;
137                         dl->parts= 1; /* no faces, 1 edge loop */
138                         dl->col= 0; /* no material */
139                         dl->verts= fp= MEM_callocN( sizeof(float)*3*len_polypoints, "dl verts");
140                         dl->index= MEM_callocN(sizeof(int)*3*len_polypoints, "dl index");
141                         
142                         for( index = 0; index<len_polypoints; ++index, fp+=3) {
143                                 polyVec= PySequence_GetItem( polyLine, index );
144                                 
145                                 fp[0] = ((VectorObject *)polyVec)->vec[0];
146                                 fp[1] = ((VectorObject *)polyVec)->vec[1];
147                                 if( ((VectorObject *)polyVec)->size > 2 )
148                                         fp[2] = ((VectorObject *)polyVec)->vec[2];
149                                 else
150                                         fp[2]= 0.0f; /* if its a 2d vector then set the z to be zero */
151                                 
152                                 totpoints++;
153                                 Py_DECREF(polyVec);
154                         }
155                 }
156                 Py_DECREF(polyLine);
157         }
158         
159         if (totpoints) {
160                 /* now make the list to return */
161                 filldisplist(&dispbase, &dispbase);
162                 
163                 /* The faces are stored in a new DisplayList
164                 thats added to the head of the listbase */
165                 dl= dispbase.first; 
166                 
167                 tri_list= PyList_New(dl->parts);
168                 if( !tri_list ) {
169                         freedisplist(&dispbase);
170                         return EXPP_ReturnPyObjError( PyExc_RuntimeError,
171                                         "Geometry.PolyFill failed to make a new list" );
172                 }
173                 
174                 index= 0;
175                 dl_face= dl->index;
176                 while(index < dl->parts) {
177                         PyList_SetItem(tri_list, index, Py_BuildValue("iii", dl_face[0], dl_face[1], dl_face[2]) );
178                         dl_face+= 3;
179                         index++;
180                 }
181                 freedisplist(&dispbase);
182         } else {
183                 /* no points, do this so scripts dont barf */
184                 tri_list= PyList_New(0);
185         }
186         
187         return tri_list;
188 }
189
190
191 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args )
192 {
193         VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
194         float a1x, a1y, a2x, a2y,  b1x, b1y, b2x, b2y, xi, yi, a1,a2,b1,b2, newvec[2];
195         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
196           &vector_Type, &line_a1,
197           &vector_Type, &line_a2,
198           &vector_Type, &line_b1,
199           &vector_Type, &line_b2)
200         )
201                 return ( EXPP_ReturnPyObjError
202                          ( PyExc_TypeError, "expected 4 vector types\n" ) );
203         
204         a1x= line_a1->vec[0];
205         a1y= line_a1->vec[1];
206         a2x= line_a2->vec[0];
207         a2y= line_a2->vec[1];
208
209         b1x= line_b1->vec[0];
210         b1y= line_b1->vec[1];
211         b2x= line_b2->vec[0];
212         b2y= line_b2->vec[1];
213         
214         if((MIN2(a1x, a2x) > MAX2(b1x, b2x)) ||
215            (MAX2(a1x, a2x) < MIN2(b1x, b2x)) ||
216            (MIN2(a1y, a2y) > MAX2(b1y, b2y)) ||
217            (MAX2(a1y, a2y) < MIN2(b1y, b2y))  ) {
218                 Py_RETURN_NONE;
219         }
220         /* Make sure the hoz/vert line comes first. */
221         if (fabs(b1x - b2x) < eul || fabs(b1y - b2y) < eul) {
222                 SWAP_FLOAT(a1x, b1x, xi); /*abuse xi*/
223                 SWAP_FLOAT(a1y, b1y, xi);
224                 SWAP_FLOAT(a2x, b2x, xi);
225                 SWAP_FLOAT(a2y, b2y, xi);
226         }
227         
228         if (fabs(a1x-a2x) < eul) { /* verticle line */
229                 if (fabs(b1x-b2x) < eul){ /*verticle second line */
230                         Py_RETURN_NONE; /* 2 verticle lines dont intersect. */
231                 }
232                 else if (fabs(b1y-b2y) < eul) {
233                         /*X of vert, Y of hoz. no calculation needed */
234                         newvec[0]= a1x;
235                         newvec[1]= b1y;
236                         return newVectorObject(newvec, 2, Py_NEW);
237                 }
238                 
239                 yi = (float)(((b1y / fabs(b1x - b2x)) * fabs(b2x - a1x)) + ((b2y / fabs(b1x - b2x)) * fabs(b1x - a1x)));
240                 
241                 if (yi > MAX2(a1y, a2y)) {/* New point above seg1's vert line */
242                         Py_RETURN_NONE;
243                 } else if (yi < MIN2(a1y, a2y)) { /* New point below seg1's vert line */
244                         Py_RETURN_NONE;
245                 }
246                 newvec[0]= a1x;
247                 newvec[1]= yi;
248                 return newVectorObject(newvec, 2, Py_NEW);
249         } else if (fabs(a2y-a1y) < eul) {  /* hoz line1 */
250                 if (fabs(b2y-b1y) < eul) { /*hoz line2*/
251                         Py_RETURN_NONE; /*2 hoz lines dont intersect*/
252                 }
253                 
254                 /* Can skip vert line check for seg 2 since its covered above. */
255                 xi = (float)(((b1x / fabs(b1y - b2y)) * fabs(b2y - a1y)) + ((b2x / fabs(b1y - b2y)) * fabs(b1y - a1y)));
256                 if (xi > MAX2(a1x, a2x)) { /* New point right of hoz line1's */
257                         Py_RETURN_NONE;
258                 } else if (xi < MIN2(a1x, a2x)) { /*New point left of seg1's hoz line */
259                         Py_RETURN_NONE;
260                 }
261                 newvec[0]= xi;
262                 newvec[1]= a1y;
263                 return newVectorObject(newvec, 2, Py_NEW);
264         }
265         
266         b1 = (a2y-a1y)/(a2x-a1x);
267         b2 = (b2y-b1y)/(b2x-b1x);
268         a1 = a1y-b1*a1x;
269         a2 = b1y-b2*b1x;
270         
271         if (b1 - b2 == 0.0) {
272                 Py_RETURN_NONE;
273         }
274         
275         xi = - (a1-a2)/(b1-b2);
276         yi = a1+b1*xi;
277         if ((a1x-xi)*(xi-a2x) >= 0 && (b1x-xi)*(xi-b2x) >= 0 && (a1y-yi)*(yi-a2y) >= 0 && (b1y-yi)*(yi-b2y)>=0) {
278                 newvec[0]= xi;
279                 newvec[1]= yi;
280                 return newVectorObject(newvec, 2, Py_NEW);
281         }
282         Py_RETURN_NONE;
283 }
284
285 static PyObject *M_Geometry_ClosestPointOnLine( PyObject * self, PyObject * args )
286 {
287         VectorObject *pt, *line_1, *line_2;
288         float pt_in[3], pt_out[3], l1[3], l2[3];
289         float lambda;
290         PyObject *ret, *val1, *val2;
291         
292         if( !PyArg_ParseTuple ( args, "O!O!O!",
293         &vector_Type, &pt,
294         &vector_Type, &line_1,
295         &vector_Type, &line_2)
296           )
297                 return ( EXPP_ReturnPyObjError
298                                 ( PyExc_TypeError, "expected 3 vector types\n" ) );
299         
300         /* accept 2d verts */
301         if (pt->size==3) { VECCOPY(pt_in, pt->vec);}
302         else { pt_in[2]=0.0;    VECCOPY2D(pt_in, pt->vec) }
303         
304         if (line_1->size==3) { VECCOPY(l1, line_1->vec);}
305         else { l1[2]=0.0;       VECCOPY2D(l1, line_1->vec) }
306         
307         if (line_2->size==3) { VECCOPY(l2, line_2->vec);}
308         else { l2[2]=0.0;       VECCOPY2D(l2, line_2->vec) }
309         
310         /* do the calculation */
311         lambda = lambda_cp_line_ex(pt_in, l1, l2, pt_out);
312         
313         val1 = newVectorObject(pt_out, 3, Py_NEW);
314         val2 = PyFloat_FromDouble(lambda);
315         
316         ret = PyTuple_Pack(2, val1, val2);
317         
318         Py_DECREF(val1);
319         Py_DECREF(val2);
320         
321         return ret;
322 }
323
324 #define SIDE_OF_LINE(pa,pb,pp)  ((pa[0]-pp[0])*(pb[1]-pp[1]))-((pb[0]-pp[0])*(pa[1]-pp[1]))
325 #define POINT_IN_TRI(p0,p1,p2,p3)       ((SIDE_OF_LINE(p1,p2,p0)>=0) && (SIDE_OF_LINE(p2,p3,p0)>=0) && (SIDE_OF_LINE(p3,p1,p0)>=0))
326
327 static PyObject *M_Geometry_PointInTriangle2D( PyObject * self, PyObject * args )
328 {
329         VectorObject *pt_vec, *tri_p1, *tri_p2, *tri_p3;
330         
331         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
332           &vector_Type, &pt_vec,
333           &vector_Type, &tri_p1,
334           &vector_Type, &tri_p2,
335           &vector_Type, &tri_p3)
336         )
337                 return ( EXPP_ReturnPyObjError
338                          ( PyExc_TypeError, "expected 4 vector types\n" ) );
339         
340         if POINT_IN_TRI(pt_vec->vec, tri_p1->vec, tri_p2->vec, tri_p3->vec)
341                 Py_RETURN_TRUE;
342         else
343                 Py_RETURN_FALSE;
344 }
345
346 int boxPack_FromPyObject(PyObject * value, boxPack **boxarray )
347 {
348         int len, i;
349         PyObject *list_item, *item_1, *item_2;
350         boxPack *box;
351         
352         
353         /* Error checking must alredy be done */
354         if( !PyList_Check( value ) )
355                 return EXPP_ReturnIntError( PyExc_TypeError,
356                                 "can only back a list of [x,y,x,w]" );
357         
358         len = PyList_Size( value );
359         
360         (*boxarray) = MEM_mallocN( len*sizeof(boxPack), "boxPack box");
361         
362         
363         for( i = 0; i < len; i++ ) {
364                 list_item = PyList_GET_ITEM( value, i );
365                 if( !PyList_Check( list_item ) || PyList_Size( list_item ) < 4 ) {
366                         MEM_freeN(*boxarray);
367                         return EXPP_ReturnIntError( PyExc_TypeError,
368                                         "can only back a list of [x,y,x,w]" );
369                 }
370                 
371                 box = (*boxarray)+i;
372                 
373                 item_1 = PyList_GET_ITEM(list_item, 2);
374                 item_2 = PyList_GET_ITEM(list_item, 3);
375                 
376                 if (!PyNumber_Check(item_1) || !PyNumber_Check(item_2)) {
377                         MEM_freeN(*boxarray);
378                         return EXPP_ReturnIntError( PyExc_TypeError,
379                                         "can only back a list of 2d boxes [x,y,x,w]" );
380                 }
381                 
382                 box->w =  (float)PyFloat_AsDouble( item_1 );
383                 box->h =  (float)PyFloat_AsDouble( item_2 );
384                 box->index = i;
385                 /* verts will be added later */
386         }
387         return 0;
388 }
389
390 void boxPack_ToPyObject(PyObject * value, boxPack **boxarray)
391 {
392         int len, i;
393         PyObject *list_item;
394         boxPack *box;
395         
396         len = PyList_Size( value );
397         
398         for( i = 0; i < len; i++ ) {
399                 box = (*boxarray)+i;
400                 list_item = PyList_GET_ITEM( value, box->index );
401                 PyList_SET_ITEM( list_item, 0, PyFloat_FromDouble( box->x ));
402                 PyList_SET_ITEM( list_item, 1, PyFloat_FromDouble( box->y ));
403         }
404         MEM_freeN(*boxarray);
405 }
406
407
408 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * boxlist )
409 {
410         boxPack *boxarray;
411         float tot_width, tot_height;
412         int len;
413         int error;
414         
415         if(!PyList_Check(boxlist))
416                 return EXPP_ReturnPyObjError( PyExc_TypeError,
417                                               "expected a sequence of boxes [[x,y,w,h], ... ]" );
418         
419         len = PyList_Size( boxlist );
420         
421         if (!len)
422                 return Py_BuildValue( "ff", 0.0, 0.0);
423         
424         error = boxPack_FromPyObject(boxlist, &boxarray);
425         if (error!=0)   return NULL;
426         
427         /* Non Python function */
428         boxPack2D(boxarray, len, &tot_width, &tot_height);
429         
430         boxPack_ToPyObject(boxlist, &boxarray);
431         
432         return Py_BuildValue( "ff", tot_width, tot_height);
433 }