← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty

« back to all changes in this revision

Viewing changes to source/blender/python/mathutils/mathutils_geometry.c

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/python/mathutils/mathutils_geometry.c
1
1
/*
2
 
 *
3
2
 * ***** BEGIN GPL LICENSE BLOCK *****
4
3
 *
5
4
 * This program is free software; you can redistribute it and/or
47
46
#include "BLI_math.h"
48
47
#include "BLI_utildefines.h"
49
48
 
50
 
#define SWAP_FLOAT(a, b, tmp) tmp = a; a = b; b = tmp
51
 
 
52
49
/*-------------------------DOC STRINGS ---------------------------*/
53
50
PyDoc_STRVAR(M_Geometry_doc,
54
51
"The Blender geometry module"
55
52
);
56
53
 
57
 
//---------------------------------INTERSECTION FUNCTIONS--------------------
 
54
/* ---------------------------------INTERSECTION FUNCTIONS-------------------- */
58
55
 
59
56
PyDoc_STRVAR(M_Geometry_intersect_ray_tri_doc,
60
57
".. function:: intersect_ray_tri(v1, v2, v3, ray, orig, clip=True)\n"
254
251
        }
255
252
}
256
253
 
257
 
 
258
 
 
259
 
 
260
 
//----------------------------geometry.normal() -------------------
 
254
/* Line-Line intersection using algorithm from mathworld.wolfram.com */
 
255
 
 
256
PyDoc_STRVAR(M_Geometry_intersect_sphere_sphere_2d_doc,
 
257
".. function:: intersect_sphere_sphere_2d(p_a, radius_a, p_b, radius_b)\n"
 
258
"\n"
 
259
"   Returns 2 points on between intersecting circles.\n"
 
260
"\n"
 
261
"   :arg p_a: Center of the first circle\n"
 
262
"   :type p_a: :class:`mathutils.Vector`\n"
 
263
"   :arg radius_a: Radius of the first circle\n"
 
264
"   :type radius_a: float\n"
 
265
"   :arg p_b: Center of the second circle\n"
 
266
"   :type p_b: :class:`mathutils.Vector`\n"
 
267
"   :arg radius_b: Radius of the second circle\n"
 
268
"   :type radius_b: float\n"
 
269
"   :rtype: tuple of :class:`mathutils.Vector`'s or None when there is no intersection\n"
 
270
);
 
271
static PyObject *M_Geometry_intersect_sphere_sphere_2d(PyObject *UNUSED(self), PyObject *args)
 
272
{
 
273
        PyObject *ret;
 
274
        VectorObject *vec_a, *vec_b;
 
275
        float *v_a, *v_b;
 
276
        float rad_a, rad_b;
 
277
        float v_ab[2];
 
278
        float dist;
 
279
 
 
280
        if (!PyArg_ParseTuple(args, "O!fO!f:intersect_sphere_sphere_2d",
 
281
                              &vector_Type, &vec_a, &rad_a,
 
282
                              &vector_Type, &vec_b, &rad_b))
 
283
        {
 
284
                return NULL;
 
285
        }
 
286
 
 
287
        if (BaseMath_ReadCallback(vec_a) == -1 ||
 
288
            BaseMath_ReadCallback(vec_b) == -1)
 
289
        {
 
290
                return NULL;
 
291
        }
 
292
 
 
293
        ret = PyTuple_New(2);
 
294
 
 
295
        v_a = vec_a->vec;
 
296
        v_b = vec_b->vec;
 
297
 
 
298
        sub_v2_v2v2(v_ab, v_b, v_a);
 
299
        dist = len_v2(v_ab);
 
300
 
 
301
        if (/* out of range */
 
302
            (dist > rad_a + rad_b) ||
 
303
            /* fully-contained in the other */
 
304
            (dist < abs(rad_a - rad_b)) ||
 
305
            /* co-incident */
 
306
            (dist < FLT_EPSILON))
 
307
        {
 
308
                /* out of range */
 
309
                PyTuple_SET_ITEM(ret, 0,  Py_None); Py_INCREF(Py_None);
 
310
                PyTuple_SET_ITEM(ret, 1,  Py_None); Py_INCREF(Py_None);
 
311
        }
 
312
        else {
 
313
                const float dist_delta = ((rad_a * rad_a) - (rad_b * rad_b) + (dist * dist)) / (2.0f * dist);
 
314
                const float h = powf(fabsf((rad_a * rad_a) - (dist_delta * dist_delta)), 0.5f);
 
315
                float i_cent[2];
 
316
                float i1[2], i2[2];
 
317
 
 
318
                i_cent[0] = v_a[0] + ((v_ab[0] * dist_delta) / dist);
 
319
                i_cent[1] = v_a[1] + ((v_ab[1] * dist_delta) / dist);
 
320
 
 
321
                i1[0] = i_cent[0] + h * v_ab[1] / dist;
 
322
                i1[1] = i_cent[1] - h * v_ab[0] / dist;
 
323
 
 
324
                i2[0] = i_cent[0] - h * v_ab[1] / dist;
 
325
                i2[1] = i_cent[1] + h * v_ab[0] / dist;
 
326
 
 
327
                PyTuple_SET_ITEM(ret, 0, Vector_CreatePyObject(i1, 2, Py_NEW, NULL));
 
328
                PyTuple_SET_ITEM(ret, 1, Vector_CreatePyObject(i2, 2, Py_NEW, NULL));
 
329
        }
 
330
 
 
331
        return ret;
 
332
}
 
333
 
261
334
PyDoc_STRVAR(M_Geometry_normal_doc,
262
335
".. function:: normal(v1, v2, v3, v4=None)\n"
263
336
"\n"
341
414
        return Vector_CreatePyObject(n, 3, Py_NEW, NULL);
342
415
}
343
416
 
344
 
//--------------------------------- AREA FUNCTIONS--------------------
 
417
/* --------------------------------- AREA FUNCTIONS-------------------- */
345
418
 
346
419
PyDoc_STRVAR(M_Geometry_area_tri_doc,
347
420
".. function:: area_tri(v1, v2, v3)\n"
729
802
        float pt_in[3], pt_out[3], l1[3], l2[3];
730
803
        float lambda;
731
804
        PyObject *ret;
 
805
        int size = 2;
732
806
        
733
807
        if (!PyArg_ParseTuple(args, "O!O!O!:intersect_point_line",
734
808
                              &vector_Type, &pt,
746
820
        }
747
821
 
748
822
        /* accept 2d verts */
749
 
        if (pt->size == 3) {     copy_v3_v3(pt_in, pt->vec); }
750
 
        else { pt_in[2] = 0.0f;  copy_v2_v2(pt_in, pt->vec); }
751
 
        
752
 
        if (line_1->size == 3) { copy_v3_v3(l1, line_1->vec); }
753
 
        else { l1[2] = 0.0f;     copy_v2_v2(l1, line_1->vec); }
754
 
        
755
 
        if (line_2->size == 3) { copy_v3_v3(l2, line_2->vec); }
756
 
        else { l2[2] = 0.0f;     copy_v2_v2(l2, line_2->vec); }
 
823
        if (pt->size >= 3)     { copy_v3_v3(pt_in, pt->vec); size = 3; }
 
824
        else                   { copy_v2_v2(pt_in, pt->vec); pt_in[2] = 0.0f; }
 
825
        
 
826
        if (line_1->size >= 3) { copy_v3_v3(l1, line_1->vec); size = 3; }
 
827
        else                   { copy_v2_v2(l1, line_1->vec); l1[2] = 0.0f; }
 
828
        
 
829
        if (line_2->size >= 3) { copy_v3_v3(l2, line_2->vec); size = 3; }
 
830
        else                   { copy_v2_v2(l2, line_2->vec); l2[2] = 0.0f; }
757
831
        
758
832
        /* do the calculation */
759
833
        lambda = closest_to_line_v3(pt_out, pt_in, l1, l2);
760
834
        
761
835
        ret = PyTuple_New(2);
762
 
        PyTuple_SET_ITEM(ret, 0, Vector_CreatePyObject(pt_out, 3, Py_NEW, NULL));
 
836
        PyTuple_SET_ITEM(ret, 0, Vector_CreatePyObject(pt_out, size, Py_NEW, NULL));
763
837
        PyTuple_SET_ITEM(ret, 1, PyFloat_FromDouble(lambda));
764
838
        return ret;
765
839
}
808
882
"\n"
809
883
"   Takes 5 vectors (using only the x and y coordinates): one is the point and the next 4 define the quad, \n"
810
884
"   only the x and y are used from the vectors. Returns 1 if the point is within the quad, otherwise 0.\n"
 
885
"   Works only with convex quads without singular edges."
811
886
"\n"
812
887
"   :arg pt: Point\n"
813
888
"   :type pt: :class:`mathutils.Vector`\n"
944
1019
        return Vector_CreatePyObject(vec, 3, Py_NEW, NULL);
945
1020
}
946
1021
 
 
1022
PyDoc_STRVAR(M_Geometry_points_in_planes_doc,
 
1023
".. function:: points_in_planes(planes)\n"
 
1024
"\n"
 
1025
"   Returns a list of points inside all planes given and a list of index values for the planes used.\n"
 
1026
"\n"
 
1027
"   :arg planes: List of planes (4D vectors).\n"
 
1028
"   :type planes: list of :class:`mathutils.Vector`\n"
 
1029
"   :return: two lists, once containing the vertices inside the planes, another containing the plane indicies used\n"
 
1030
"   :rtype: pair of lists\n"
 
1031
);
 
1032
/* note: this function could be optimized by some spatial structure */
 
1033
static PyObject *M_Geometry_points_in_planes(PyObject *UNUSED(self), PyObject *args)
 
1034
{
 
1035
        PyObject *py_planes;
 
1036
        float (*planes)[4];
 
1037
        unsigned int planes_len;
 
1038
 
 
1039
        if (!PyArg_ParseTuple(args, "O:points_in_planes",
 
1040
                              &py_planes))
 
1041
        {
 
1042
                return NULL;
 
1043
        }
 
1044
 
 
1045
        if ((planes_len = mathutils_array_parse_alloc_v((float **)&planes, 4, py_planes, "points_in_planes")) == -1) {
 
1046
                return NULL;
 
1047
        }
 
1048
        else {
 
1049
                /* note, this could be refactored into plain C easy - py bits are noted */
 
1050
                const float eps = 0.0001f;
 
1051
                const unsigned int len = (unsigned int)planes_len;
 
1052
                unsigned int i, j, k, l;
 
1053
 
 
1054
                float n1n2[3], n2n3[3], n3n1[3];
 
1055
                float potentialVertex[3];
 
1056
                char *planes_used = PyMem_Malloc(sizeof(char) * len);
 
1057
 
 
1058
                /* python */
 
1059
                PyObject *py_verts = PyList_New(0);
 
1060
                PyObject *py_plene_index = PyList_New(0);
 
1061
 
 
1062
                memset(planes_used, 0, sizeof(char) * len);
 
1063
 
 
1064
                for (i = 0; i < len; i++) {
 
1065
                        const float *N1 = planes[i];
 
1066
                        for (j = i + 1; j < len; j++) {
 
1067
                                const float *N2 = planes[j];
 
1068
                                cross_v3_v3v3(n1n2, N1, N2);
 
1069
                                if (len_squared_v3(n1n2) > eps) {
 
1070
                                        for (k = j + 1; k < len; k++) {
 
1071
                                                const float *N3 = planes[k];
 
1072
                                                cross_v3_v3v3(n2n3, N2, N3);
 
1073
                                                if (len_squared_v3(n2n3) > eps) {
 
1074
                                                        cross_v3_v3v3(n3n1, N3, N1);
 
1075
                                                        if (len_squared_v3(n3n1) > eps) {
 
1076
                                                                const float quotient = dot_v3v3(N1, n2n3);
 
1077
                                                                if (fabsf(quotient) > eps) {
 
1078
                                                                        /* potentialVertex = (n2n3 * N1[3] + n3n1 * N2[3] + n1n2 * N3[3]) * (-1.0 / quotient); */
 
1079
                                                                        const float quotient_ninv = -1.0f / quotient;
 
1080
                                                                        potentialVertex[0] = ((n2n3[0] * N1[3]) + (n3n1[0] * N2[3]) + (n1n2[0] * N3[3])) * quotient_ninv;
 
1081
                                                                        potentialVertex[1] = ((n2n3[1] * N1[3]) + (n3n1[1] * N2[3]) + (n1n2[1] * N3[3])) * quotient_ninv;
 
1082
                                                                        potentialVertex[2] = ((n2n3[2] * N1[3]) + (n3n1[2] * N2[3]) + (n1n2[2] * N3[3])) * quotient_ninv;
 
1083
                                                                        for (l = 0; l < len; l++) {
 
1084
                                                                                const float *NP = planes[l];
 
1085
                                                                                if ((dot_v3v3(NP, potentialVertex) + NP[3]) > 0.000001f) {
 
1086
                                                                                        break;
 
1087
                                                                                }
 
1088
                                                                        }
 
1089
 
 
1090
                                                                        if (l == len) { /* ok */
 
1091
                                                                                /* python */
 
1092
                                                                                PyObject *item = Vector_CreatePyObject(potentialVertex, 3, Py_NEW, NULL);
 
1093
                                                                                PyList_Append(py_verts, item);
 
1094
                                                                                Py_DECREF(item);
 
1095
 
 
1096
                                                                                planes_used[i] = planes_used[j] = planes_used[k] = TRUE;
 
1097
                                                                        }
 
1098
                                                                }
 
1099
                                                        }
 
1100
                                                }
 
1101
                                        }
 
1102
                                }
 
1103
                        }
 
1104
                }
 
1105
 
 
1106
                PyMem_Free(planes);
 
1107
 
 
1108
                /* now make a list of used planes */
 
1109
                for (i = 0; i < len; i++) {
 
1110
                        if (planes_used[i]) {
 
1111
                                PyObject *item = PyLong_FromLong(i);
 
1112
                                PyList_Append(py_plene_index, item);
 
1113
                                Py_DECREF(item);
 
1114
                        }
 
1115
                }
 
1116
                PyMem_Free(planes_used);
 
1117
 
 
1118
                {
 
1119
                        PyObject *ret = PyTuple_New(2);
 
1120
                        PyTuple_SET_ITEM(ret, 0, py_verts);
 
1121
                        PyTuple_SET_ITEM(ret, 1, py_plene_index);
 
1122
                        return ret;
 
1123
                }
 
1124
        }
 
1125
}
 
1126
 
947
1127
#ifndef MATH_STANDALONE
948
1128
 
949
1129
PyDoc_STRVAR(M_Geometry_interpolate_bezier_doc,
1002
1182
                return NULL;
1003
1183
        }
1004
1184
 
1005
 
        dims = MAX4(vec_k1->size, vec_h1->size, vec_h2->size, vec_k2->size);
 
1185
        dims = max_iiii(vec_k1->size, vec_h1->size, vec_h2->size, vec_k2->size);
1006
1186
 
1007
1187
        for (i = 0; i < vec_k1->size; i++) k1[i] = vec_k1->vec[i];
1008
1188
        for (i = 0; i < vec_h1->size; i++) h1[i] = vec_h1->vec[i];
1011
1191
 
1012
1192
        coord_array = MEM_callocN(dims * (resolu) * sizeof(float), "interpolate_bezier");
1013
1193
        for (i = 0; i < dims; i++) {
1014
 
                forward_diff_bezier(k1[i], h1[i], h2[i], k2[i], coord_array + i, resolu - 1, sizeof(float) * dims);
 
1194
                BKE_curve_forward_diff_bezier(k1[i], h1[i], h2[i], k2[i], coord_array + i, resolu - 1, sizeof(float) * dims);
1015
1195
        }
1016
1196
 
1017
1197
        list = PyList_New(resolu);
1056
1236
        for (i = 0; i < len_polylines; i++) {
1057
1237
                polyLine = PySequence_GetItem(polyLineSeq, i);
1058
1238
                if (!PySequence_Check(polyLine)) {
1059
 
                        freedisplist(&dispbase);
 
1239
                        BKE_displist_free(&dispbase);
1060
1240
                        Py_XDECREF(polyLine); /* may be null so use Py_XDECREF*/
1061
1241
                        PyErr_SetString(PyExc_TypeError,
1062
1242
                                        "One or more of the polylines is not a sequence of mathutils.Vector's");
1110
1290
        }
1111
1291
 
1112
1292
        if (ls_error) {
1113
 
                freedisplist(&dispbase); /* possible some dl was allocated */
 
1293
                BKE_displist_free(&dispbase); /* possible some dl was allocated */
1114
1294
                PyErr_SetString(PyExc_TypeError,
1115
1295
                                "A point in one of the polylines "
1116
1296
                                "is not a mathutils.Vector type");
1118
1298
        }
1119
1299
        else if (totpoints) {
1120
1300
                /* now make the list to return */
1121
 
                filldisplist(&dispbase, &dispbase, 0);
 
1301
                BKE_displist_fill(&dispbase, &dispbase, 0);
1122
1302
 
1123
1303
                /* The faces are stored in a new DisplayList
1124
1304
                 * thats added to the head of the listbase */
1126
1306
 
1127
1307
                tri_list = PyList_New(dl->parts);
1128
1308
                if (!tri_list) {
1129
 
                        freedisplist(&dispbase);
 
1309
                        BKE_displist_free(&dispbase);
1130
1310
                        PyErr_SetString(PyExc_RuntimeError,
1131
1311
                                        "failed to make a new list");
1132
1312
                        return NULL;
1139
1319
                        dl_face += 3;
1140
1320
                        index++;
1141
1321
                }
1142
 
                freedisplist(&dispbase);
 
1322
                BKE_displist_free(&dispbase);
1143
1323
        }
1144
1324
        else {
1145
1325
                /* no points, do this so scripts don't barf */
1146
 
                freedisplist(&dispbase); /* possible some dl was allocated */
 
1326
                BKE_displist_free(&dispbase); /* possible some dl was allocated */
1147
1327
                tri_list = PyList_New(0);
1148
1328
        }
1149
1329
 
1151
1331
}
1152
1332
 
1153
1333
 
1154
 
static int boxPack_FromPyObject(PyObject *value, boxPack **boxarray)
 
1334
static int boxPack_FromPyObject(PyObject *value, BoxPack **boxarray)
1155
1335
{
1156
1336
        Py_ssize_t len, i;
1157
1337
        PyObject *list_item, *item_1, *item_2;
1158
 
        boxPack *box;
 
1338
        BoxPack *box;
1159
1339
 
1160
1340
 
1161
1341
        /* Error checking must already be done */
1167
1347
 
1168
1348
        len = PyList_GET_SIZE(value);
1169
1349
 
1170
 
        *boxarray = MEM_mallocN(len * sizeof(boxPack), "boxPack box");
 
1350
        *boxarray = MEM_mallocN(len * sizeof(BoxPack), "BoxPack box");
1171
1351
 
1172
1352
 
1173
1353
        for (i = 0; i < len; i++) {
1202
1382
        return 0;
1203
1383
}
1204
1384
 
1205
 
static void boxPack_ToPyObject(PyObject *value, boxPack **boxarray)
 
1385
static void boxPack_ToPyObject(PyObject *value, BoxPack **boxarray)
1206
1386
{
1207
1387
        Py_ssize_t len, i;
1208
1388
        PyObject *list_item;
1209
 
        boxPack *box;
 
1389
        BoxPack *box;
1210
1390
 
1211
1391
        len = PyList_GET_SIZE(value);
1212
1392
 
1244
1424
 
1245
1425
        len = PyList_GET_SIZE(boxlist);
1246
1426
        if (len) {
1247
 
                boxPack *boxarray = NULL;
 
1427
                BoxPack *boxarray = NULL;
1248
1428
                if (boxPack_FromPyObject(boxlist, &boxarray) == -1) {
1249
1429
                        return NULL; /* exception set */
1250
1430
                }
1251
1431
 
1252
1432
                /* Non Python function */
1253
 
                boxPack2D(boxarray, len, &tot_width, &tot_height);
 
1433
                BLI_box_pack_2D(boxarray, len, &tot_width, &tot_height);
1254
1434
 
1255
1435
                boxPack_ToPyObject(boxlist, &boxarray);
1256
1436
        }
1276
1456
        {"intersect_line_sphere", (PyCFunction) M_Geometry_intersect_line_sphere, METH_VARARGS, M_Geometry_intersect_line_sphere_doc},
1277
1457
        {"intersect_line_sphere_2d", (PyCFunction) M_Geometry_intersect_line_sphere_2d, METH_VARARGS, M_Geometry_intersect_line_sphere_2d_doc},
1278
1458
        {"distance_point_to_plane", (PyCFunction) M_Geometry_distance_point_to_plane, METH_VARARGS, M_Geometry_distance_point_to_plane_doc},
 
1459
        {"intersect_sphere_sphere_2d", (PyCFunction) M_Geometry_intersect_sphere_sphere_2d, METH_VARARGS, M_Geometry_intersect_sphere_sphere_2d_doc},
1279
1460
        {"area_tri", (PyCFunction) M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc},
1280
1461
        {"normal", (PyCFunction) M_Geometry_normal, METH_VARARGS, M_Geometry_normal_doc},
1281
1462
        {"barycentric_transform", (PyCFunction) M_Geometry_barycentric_transform, METH_VARARGS, M_Geometry_barycentric_transform_doc},
 
1463
        {"points_in_planes", (PyCFunction) M_Geometry_points_in_planes, METH_VARARGS, M_Geometry_points_in_planes_doc},
1282
1464
#ifndef MATH_STANDALONE
1283
1465
        {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc},
1284
1466
        {"tessellate_polygon", (PyCFunction) M_Geometry_tessellate_polygon, METH_O, M_Geometry_tessellate_polygon_doc},