moved the boxpacker from PyAPI's Geometry to BLI_boxpack2d
[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
51 #define SWAP_FLOAT(a,b,tmp) tmp=a; a=b; b=tmp
52 #define eul 0.000001
53
54 /*-- forward declarations -- */
55 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * args );
56 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args );
57 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args );
58
59 /*-------------------------DOC STRINGS ---------------------------*/
60 static char M_Geometry_doc[] = "The Blender Geometry module\n\n";
61 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";
62 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";
63 static char M_Geometry_BoxPack2D_doc[] = "";
64 /*-----------------------METHOD DEFINITIONS ----------------------*/
65 struct PyMethodDef M_Geometry_methods[] = {
66         {"PolyFill", ( PyCFunction ) M_Geometry_PolyFill, METH_VARARGS, M_Geometry_PolyFill_doc},
67         {"LineIntersect2D", ( PyCFunction ) M_Geometry_LineIntersect2D, METH_VARARGS, M_Geometry_LineIntersect2D_doc},
68         {"BoxPack2D", ( PyCFunction ) M_Geometry_BoxPack2D, METH_VARARGS, M_Geometry_BoxPack2D_doc},
69         {NULL, NULL, 0, NULL}
70 };
71 /*----------------------------MODULE INIT-------------------------*/
72 PyObject *Geometry_Init(void)
73 {
74         PyObject *submodule;
75
76         submodule = Py_InitModule3("Blender.Geometry",
77                                     M_Geometry_methods, M_Geometry_doc);
78         return (submodule);
79 }
80
81 /*----------------------------------Geometry.PolyFill() -------------------*/
82 /* PolyFill function, uses Blenders scanfill to fill multiple poly lines */
83 static PyObject *M_Geometry_PolyFill( PyObject * self, PyObject * args )
84 {
85         PyObject *tri_list; /*return this list of tri's */
86         PyObject *polyLineSeq, *polyLine, *polyVec;
87         int i, len_polylines, len_polypoints;
88         
89         /* display listbase */
90         ListBase dispbase={NULL, NULL};
91         DispList *dl;
92         float *fp; /*pointer to the array of malloced dl->verts to set the points from the vectors */
93         int index, *dl_face, totpoints=0;
94         
95         
96         dispbase.first= dispbase.last= NULL;
97         
98         
99         if(!PyArg_ParseTuple ( args, "O", &polyLineSeq) || !PySequence_Check(polyLineSeq)) {
100                 return EXPP_ReturnPyObjError( PyExc_TypeError,
101                                               "expected a sequence of poly lines" );
102         }
103         
104         len_polylines = PySequence_Size( polyLineSeq );
105         
106         for( i = 0; i < len_polylines; ++i ) {
107                 polyLine= PySequence_GetItem( polyLineSeq, i );
108                 if (!PySequence_Check(polyLine)) {
109                         freedisplist(&dispbase);
110                         Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
111                         return EXPP_ReturnPyObjError( PyExc_TypeError,
112                                   "One or more of the polylines is not a sequence of Mathutils.Vector's" );
113                 }
114                 
115                 len_polypoints= PySequence_Size( polyLine );
116                 if (len_polypoints>0) { /* dont bother adding edges as polylines */
117                         if (EXPP_check_sequence_consistency( polyLine, &vector_Type ) != 1) {
118                                 freedisplist(&dispbase);
119                                 Py_DECREF(polyLine);
120                                 return EXPP_ReturnPyObjError( PyExc_TypeError,
121                                           "A point in one of the polylines is not a Mathutils.Vector type" );
122                         }
123                         
124                         dl= MEM_callocN(sizeof(DispList), "poly disp");
125                         BLI_addtail(&dispbase, dl);
126                         dl->type= DL_INDEX3;
127                         dl->nr= len_polypoints;
128                         dl->type= DL_POLY;
129                         dl->parts= 1; /* no faces, 1 edge loop */
130                         dl->col= 0; /* no material */
131                         dl->verts= fp= MEM_callocN( sizeof(float)*3*len_polypoints, "dl verts");
132                         dl->index= MEM_callocN(sizeof(int)*3*len_polypoints, "dl index");
133                         
134                         for( index = 0; index<len_polypoints; ++index, fp+=3) {
135                                 polyVec= PySequence_GetItem( polyLine, index );
136                                 
137                                 fp[0] = ((VectorObject *)polyVec)->vec[0];
138                                 fp[1] = ((VectorObject *)polyVec)->vec[1];
139                                 if( ((VectorObject *)polyVec)->size > 2 )
140                                         fp[2] = ((VectorObject *)polyVec)->vec[2];
141                                 else
142                                         fp[2]= 0.0f; /* if its a 2d vector then set the z to be zero */
143                                 
144                                 totpoints++;
145                                 Py_DECREF(polyVec);
146                         }
147                 }
148                 Py_DECREF(polyLine);
149         }
150         
151         if (totpoints) {
152                 /* now make the list to return */
153                 filldisplist(&dispbase, &dispbase);
154                 
155                 /* The faces are stored in a new DisplayList
156                 thats added to the head of the listbase */
157                 dl= dispbase.first; 
158                 
159                 tri_list= PyList_New(dl->parts);
160                 if( !tri_list ) {
161                         freedisplist(&dispbase);
162                         return EXPP_ReturnPyObjError( PyExc_RuntimeError,
163                                         "Geometry.PolyFill failed to make a new list" );
164                 }
165                 
166                 index= 0;
167                 dl_face= dl->index;
168                 while(index < dl->parts) {
169                         PyList_SetItem(tri_list, index, Py_BuildValue("iii", dl_face[0], dl_face[1], dl_face[2]) );
170                         dl_face+= 3;
171                         index++;
172                 }
173                 freedisplist(&dispbase);
174         } else {
175                 /* no points, do this so scripts dont barf */
176                 tri_list= PyList_New(0);
177         }
178         
179         return tri_list;
180 }
181
182
183 static PyObject *M_Geometry_LineIntersect2D( PyObject * self, PyObject * args )
184 {
185         VectorObject *line_a1, *line_a2, *line_b1, *line_b2;
186         float a1x, a1y, a2x, a2y,  b1x, b1y, b2x, b2y, xi, yi, a1,a2,b1,b2, newvec[2];
187         if( !PyArg_ParseTuple ( args, "O!O!O!O!",
188           &vector_Type, &line_a1,
189           &vector_Type, &line_a2,
190           &vector_Type, &line_b1,
191           &vector_Type, &line_b2)
192         )
193                 return ( EXPP_ReturnPyObjError
194                          ( PyExc_TypeError, "expected 4 vector types\n" ) );
195         
196         a1x= line_a1->vec[0];
197         a1y= line_a1->vec[1];
198         a2x= line_a2->vec[0];
199         a2y= line_a2->vec[1];
200
201         b1x= line_b1->vec[0];
202         b1y= line_b1->vec[1];
203         b2x= line_b2->vec[0];
204         b2y= line_b2->vec[1];
205         
206         if((MIN2(a1x, a2x) > MAX2(b1x, b2x)) ||
207            (MAX2(a1x, a2x) < MIN2(b1x, b2x)) ||
208            (MIN2(a1y, a2y) > MAX2(b1y, b2y)) ||
209            (MAX2(a1y, a2y) < MIN2(b1y, b2y))  ) {
210                 Py_RETURN_NONE;
211         }
212         /* Make sure the hoz/vert line comes first. */
213         if (fabs(b1x - b2x) < eul || fabs(b1y - b2y) < eul) {
214                 SWAP_FLOAT(a1x, b1x, xi); /*abuse xi*/
215                 SWAP_FLOAT(a1y, b1y, xi);
216                 SWAP_FLOAT(a2x, b2x, xi);
217                 SWAP_FLOAT(a2y, b2y, xi);
218         }
219         
220         if (fabs(a1x-a2x) < eul) { /* verticle line */
221                 if (fabs(b1x-b2x) < eul){ /*verticle second line */
222                         Py_RETURN_NONE; /* 2 verticle lines dont intersect. */
223                 }
224                 else if (fabs(b1y-b2y) < eul) {
225                         /*X of vert, Y of hoz. no calculation needed */
226                         newvec[0]= a1x;
227                         newvec[1]= b1y;
228                         return newVectorObject(newvec, 2, Py_NEW);
229                 }
230                 
231                 yi = (float)(((b1y / fabs(b1x - b2x)) * fabs(b2x - a1x)) + ((b2y / fabs(b1x - b2x)) * fabs(b1x - a1x)));
232                 
233                 if (yi > MAX2(a1y, a2y)) {/* New point above seg1's vert line */
234                         Py_RETURN_NONE;
235                 } else if (yi < MIN2(a1y, a2y)) { /* New point below seg1's vert line */
236                         Py_RETURN_NONE;
237                 }
238                 newvec[0]= a1x;
239                 newvec[1]= yi;
240                 return newVectorObject(newvec, 2, Py_NEW);
241         } else if (fabs(a2y-a1y) < eul) {  /* hoz line1 */
242                 if (fabs(b2y-b1y) < eul) { /*hoz line2*/
243                         Py_RETURN_NONE; /*2 hoz lines dont intersect*/
244                 }
245                 
246                 /* Can skip vert line check for seg 2 since its covered above. */
247                 xi = (float)(((b1x / fabs(b1y - b2y)) * fabs(b2y - a1y)) + ((b2x / fabs(b1y - b2y)) * fabs(b1y - a1y)));
248                 if (xi > MAX2(a1x, a2x)) { /* New point right of hoz line1's */
249                         Py_RETURN_NONE;
250                 } else if (xi < MIN2(a1x, a2x)) { /*New point left of seg1's hoz line */
251                         Py_RETURN_NONE;
252                 }
253                 newvec[0]= xi;
254                 newvec[1]= a1y;
255                 return newVectorObject(newvec, 2, Py_NEW);
256         }
257         
258         b1 = (a2y-a1y)/(a2x-a1x);
259         b2 = (b2y-b1y)/(b2x-b1x);
260         a1 = a1y-b1*a1x;
261         a2 = b1y-b2*b1x;
262         
263         if (b1 - b2 == 0.0) {
264                 Py_RETURN_NONE;
265         }
266         
267         xi = - (a1-a2)/(b1-b2);
268         yi = a1+b1*xi;
269         if ((a1x-xi)*(xi-a2x) >= 0 && (b1x-xi)*(xi-b2x) >= 0 && (a1y-yi)*(yi-a2y) >= 0 && (b1y-yi)*(yi-b2y)>=0) {
270                 newvec[0]= xi;
271                 newvec[1]= yi;
272                 return newVectorObject(newvec, 2, Py_NEW);
273         }
274         Py_RETURN_NONE;
275 }
276
277 int boxPack_FromPyObject(PyObject * value, boxPack **boxarray )
278 {
279         int len, i;
280         PyObject *list_item, *item_1, *item_2;
281         boxPack *box;
282         
283         
284         /* Error checking must alredy be done */
285         if( !PyList_Check( value ) )
286                 return EXPP_ReturnIntError( PyExc_TypeError,
287                                 "can only back a list of [x,y,x,w]" );
288         
289         len = PyList_Size( value );
290         
291         (*boxarray) = MEM_mallocN( len*sizeof(boxPack), "boxPack box");
292         
293         
294         for( i = 0; i < len; i++ ) {
295                 list_item = PyList_GET_ITEM( value, i );
296                 if( !PyList_Check( list_item ) || PyList_Size( list_item ) < 4 ) {
297                         MEM_freeN(*boxarray);
298                         return EXPP_ReturnIntError( PyExc_TypeError,
299                                         "can only back a list of [x,y,x,w]" );
300                 }
301                 
302                 box = (*boxarray)+i;
303                 
304                 item_1 = PyList_GET_ITEM(list_item, 2);
305                 item_2 = PyList_GET_ITEM(list_item, 3);
306                 
307                 if (!PyNumber_Check(item_1) || !PyNumber_Check(item_2)) {
308                         MEM_freeN(*boxarray);
309                         return EXPP_ReturnIntError( PyExc_TypeError,
310                                         "can only back a list of 2d boxes [x,y,x,w]" );
311                 }
312                 
313                 box->w =  (float)PyFloat_AsDouble( item_1 );
314                 box->h =  (float)PyFloat_AsDouble( item_2 );
315                 box->index = i;
316                 /* verts will be added later */
317         }
318         return 0;
319 }
320
321 void boxPack_ToPyObject(PyObject * value, boxPack **boxarray)
322 {
323         int len, i;
324         PyObject *list_item;
325         boxPack *box;
326         
327         len = PyList_Size( value );
328         
329         for( i = 0; i < len; i++ ) {
330                 box = (*boxarray)+i;
331                 list_item = PyList_GET_ITEM( value, box->index );
332                 PyList_SET_ITEM( list_item, 0, PyFloat_FromDouble( box->x ));
333                 PyList_SET_ITEM( list_item, 1, PyFloat_FromDouble( box->y ));
334         }
335         MEM_freeN(*boxarray);
336 }
337
338
339 static PyObject *M_Geometry_BoxPack2D( PyObject * self, PyObject * args )
340 {
341         PyObject *boxlist; /*return this list of tri's */
342         boxPack *boxarray;
343         float tot_width, tot_height;
344         int len;
345         int error;
346         
347         if(!PyArg_ParseTuple ( args, "O", &boxlist) || !PyList_Check(boxlist)) {
348                 return EXPP_ReturnPyObjError( PyExc_TypeError,
349                                               "expected a sequence of boxes [[x,y,w,h], ... ]" );
350         }
351         
352         len = PyList_Size( boxlist );
353         
354         if (!len)
355                 return Py_BuildValue( "ff", 0.0, 0.0);
356         
357         error = boxPack_FromPyObject(boxlist, &boxarray);
358         if (error!=0)   return NULL;
359         
360         /* Non Python function */
361         boxPack2D(boxarray, len, &tot_width, &tot_height);
362         
363         boxPack_ToPyObject(boxlist, &boxarray);
364         
365         return Py_BuildValue( "ff", tot_width, tot_height);
366 }