diff options
Diffstat (limited to 'source/blender/python')
-rw-r--r-- | source/blender/python/mathutils/mathutils.c | 148 | ||||
-rw-r--r-- | source/blender/python/mathutils/mathutils.h | 10 | ||||
-rw-r--r-- | source/blender/python/mathutils/mathutils_geometry.c | 185 |
3 files changed, 343 insertions, 0 deletions
diff --git a/source/blender/python/mathutils/mathutils.c b/source/blender/python/mathutils/mathutils.c index befa6532e97..2b1ddbbb03a 100644 --- a/source/blender/python/mathutils/mathutils.c +++ b/source/blender/python/mathutils/mathutils.c @@ -25,6 +25,7 @@ #include "BLI_math.h" #include "BLI_utildefines.h" +#include "../generic/py_capi_utils.h" #include "../generic/python_utildefines.h" #ifndef MATH_STANDALONE @@ -328,6 +329,153 @@ int mathutils_array_parse_alloc_v(float **array, return size; } +/* Parse an sequence array_dim integers into array. */ +int mathutils_int_array_parse(int *array, int array_dim, PyObject *value, const char *error_prefix) +{ + int size, i; + PyObject *value_fast, **value_fast_items, *item; + + if (!(value_fast = PySequence_Fast(value, error_prefix))) { + /* PySequence_Fast sets the error */ + return -1; + } + + if ((size = PySequence_Fast_GET_SIZE(value_fast)) != array_dim) { + PyErr_Format(PyExc_ValueError, + "%.200s: sequence size is %d, expected %d", + error_prefix, + size, + array_dim); + Py_DECREF(value_fast); + return -1; + } + + value_fast_items = PySequence_Fast_ITEMS(value_fast); + i = size; + while (i > 0) { + i--; + if (((array[i] = PyC_Long_AsI32((item = value_fast_items[i]))) == -1) && PyErr_Occurred()) { + PyErr_Format(PyExc_TypeError, "%.200s: sequence index %d expected an int", error_prefix, i); + size = -1; + break; + } + } + Py_DECREF(value_fast); + + return size; +} + +/* Parse sequence of array_dim sequences of integers and return allocated result. */ +int mathutils_array_parse_alloc_vi(int **array, + int array_dim, + PyObject *value, + const char *error_prefix) +{ + PyObject *value_fast; + int i, size; + + if (!(value_fast = PySequence_Fast(value, error_prefix))) { + /* PySequence_Fast sets the error */ + return -1; + } + + size = PySequence_Fast_GET_SIZE(value_fast); + + if (size != 0) { + PyObject **value_fast_items = PySequence_Fast_ITEMS(value_fast); + int *ip; + + ip = *array = PyMem_Malloc(size * array_dim * sizeof(int)); + + for (i = 0; i < size; i++, ip += array_dim) { + PyObject *item = value_fast_items[i]; + + if (mathutils_int_array_parse(ip, array_dim, item, error_prefix) == -1) { + PyMem_Free(*array); + *array = NULL; + size = -1; + break; + } + } + } + + Py_DECREF(value_fast); + return size; +} + +/* Parse sequence of variable-length sequences of int and return allocated + * triple of arrays to represent the result: + * The flattened sequences are put into *array. + * The start index of each sequence goes into start_table. + * The length of each index goes into len_table. + */ +int mathutils_array_parse_alloc_viseq( + int **array, int **start_table, int **len_table, PyObject *value, const char *error_prefix) +{ + PyObject *value_fast, *subseq; + int i, size, start, subseq_len; + int *ip; + + *array = NULL; + *start_table = NULL; + *len_table = NULL; + if (!(value_fast = PySequence_Fast(value, error_prefix))) { + /* PySequence_Fast sets the error */ + return -1; + } + + size = PySequence_Fast_GET_SIZE(value_fast); + + if (size != 0) { + PyObject **value_fast_items = PySequence_Fast_ITEMS(value_fast); + + *start_table = PyMem_Malloc(size * sizeof(int)); + *len_table = PyMem_Malloc(size * sizeof(int)); + + /* First pass to set starts and len, and calculate size of array needed */ + start = 0; + for (i = 0; i < size; i++) { + subseq = value_fast_items[i]; + if ((subseq_len = (int)PySequence_Size(subseq)) == -1) { + PyErr_Format( + PyExc_ValueError, "%.200s: sequence expected to have subsequences", error_prefix); + PyMem_Free(*start_table); + PyMem_Free(*len_table); + Py_DECREF(value_fast); + *start_table = NULL; + *len_table = NULL; + return -1; + } + (*start_table)[i] = start; + (*len_table)[i] = subseq_len; + start += subseq_len; + } + + ip = *array = PyMem_Malloc(start * sizeof(int)); + + /* Second pass to parse the subsequences into array */ + for (i = 0; i < size; i++) { + subseq = value_fast_items[i]; + subseq_len = (*len_table)[i]; + + if (mathutils_int_array_parse(ip, subseq_len, subseq, error_prefix) == -1) { + PyMem_Free(*array); + PyMem_Free(*start_table); + PyMem_Free(*len_table); + *array = NULL; + *len_table = NULL; + *start_table = NULL; + size = -1; + break; + } + ip += subseq_len; + } + } + + Py_DECREF(value_fast); + return size; +} + int mathutils_any_to_rotmat(float rmat[3][3], PyObject *value, const char *error_prefix) { if (EulerObject_Check(value)) { diff --git a/source/blender/python/mathutils/mathutils.h b/source/blender/python/mathutils/mathutils.h index 8afd60a7324..c9d0dee044f 100644 --- a/source/blender/python/mathutils/mathutils.h +++ b/source/blender/python/mathutils/mathutils.h @@ -167,6 +167,16 @@ int mathutils_array_parse_alloc_v(float **array, int array_dim, PyObject *value, const char *error_prefix); +int mathutils_int_array_parse(int *array, + int array_dim, + PyObject *value, + const char *error_prefix); +int mathutils_array_parse_alloc_vi(int **array, + int array_dim, + PyObject *value, + const char *error_prefix); +int mathutils_array_parse_alloc_viseq( + int **array, int **start_table, int **len_table, PyObject *value, const char *error_prefix); int mathutils_any_to_rotmat(float rmat[3][3], PyObject *value, const char *error_prefix); Py_hash_t mathutils_array_hash(const float *float_array, size_t array_len); diff --git a/source/blender/python/mathutils/mathutils_geometry.c b/source/blender/python/mathutils/mathutils_geometry.c index 32ce78f702d..a6dded4ee8b 100644 --- a/source/blender/python/mathutils/mathutils_geometry.c +++ b/source/blender/python/mathutils/mathutils_geometry.c @@ -29,6 +29,7 @@ # include "BLI_blenlib.h" # include "BLI_boxpack_2d.h" # include "BLI_convexhull_2d.h" +# include "BLI_delaunay_2d.h" # include "BKE_displist.h" # include "BKE_curve.h" #endif @@ -1507,6 +1508,186 @@ static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *poi return ret; } +/* Return a PyObject that is a list of lists, using the flattened list array + * to fill values, with start_table and len_table giving the start index + * and length of the toplevel_len sublists + */ +static PyObject *list_of_lists_from_arrays(int *array, + int *start_table, + int *len_table, + int toplevel_len) +{ + PyObject *ret, *sublist; + int i, j, sublist_len, sublist_start, val; + + ret = PyList_New(toplevel_len); + for (i = 0; i < toplevel_len; i++) { + sublist_len = len_table[i]; + sublist = PyList_New(sublist_len); + sublist_start = start_table[i]; + for (j = 0; j < sublist_len; j++) { + val = array[sublist_start + j]; + PyList_SET_ITEM(sublist, j, PyLong_FromLong(val)); + } + PyList_SET_ITEM(ret, i, sublist); + } + return ret; +} + +PyDoc_STRVAR( + M_Geometry_delaunay_2d_cdt_doc, + ".. function:: delaunay_2d_cdt(vert_coords, edges, faces, output_type, epsilon)\n" + "\n" + "Computes the Constrained Delaunay Triangulation of a set of vertices, " + "with edges and faces that must appear in the triangulation. " + "Some triangles may be eaten away, or combined with other triangles, " + "according to output type. " + "The returned verts may be in a different order from input verts, may be moved " + "slightly, and may be merged with other nearby verts. " + "The three returned orig lists give, for each of verts, edges, and faces, the list of " + "input element indices corresponding to the positionally same output element. " + "For edges, the orig indices start with the input edges and then continue " + "with the edges implied by each of the faces (n of them for an n-gon).\n" + "\n" + " :arg vert_coords: Vertex coordinates (2d)\n" + " :type vert_coords: list of :class:`mathutils.Vector`\n" + " :arg edges: Edges, as pairs of indices in `vert_coords`\n" + " :type edges: list of (int, int)\n" + " :arg faces: Faces, each sublist is a face, as indices in `vert_coords` (CCW oriented)\n" + " :type faces: list of list of int\n" + " :arg output_type: What output looks like. 0 => triangles with convex hull. " + "1 => triangles inside constraints. " + "2 => the input constraints, intersected. " + "3 => like 2 but with extra edges to make valid BMesh faces.\n" + " :type output_type: int\\n" + " :arg epsilon: For nearness tests; should not be zero\n" + " :type epsilon: float\n" + " :return: Output tuple, (vert_coords, edges, faces, orig_verts, orig_edges, orig_faces)\n" + " :rtype: (list of `mathutils.Vector`, " + "list of (int, int), " + "list of list of int, " + "list of list of int, " + "list of list of int, " + "list of list of int)\n" + "\n"); +static PyObject *M_Geometry_delaunay_2d_cdt(PyObject *UNUSED(self), PyObject *args) +{ + const char *error_prefix = "delaunay_2d_cdt"; + PyObject *vert_coords, *edges, *faces, *item; + int output_type; + float epsilon; + float(*in_coords)[2] = NULL; + int(*in_edges)[2] = NULL; + int *in_faces = NULL; + int *in_faces_start_table = NULL; + int *in_faces_len_table = NULL; + Py_ssize_t vert_coords_len, edges_len, faces_len; + CDT_input in; + CDT_result *res = NULL; + PyObject *out_vert_coords = NULL; + PyObject *out_edges = NULL; + PyObject *out_faces = NULL; + PyObject *out_orig_verts = NULL; + PyObject *out_orig_edges = NULL; + PyObject *out_orig_faces = NULL; + PyObject *ret_value = NULL; + int i; + + if (!PyArg_ParseTuple( + args, "OOOif:delaunay_2d_cdt", &vert_coords, &edges, &faces, &output_type, &epsilon)) { + return NULL; + } + + vert_coords_len = mathutils_array_parse_alloc_v( + (float **)&in_coords, 2, vert_coords, error_prefix); + if (vert_coords_len == -1) { + return NULL; + } + + edges_len = mathutils_array_parse_alloc_vi((int **)&in_edges, 2, edges, error_prefix); + if (edges_len == -1) { + goto exit_cdt; + } + + faces_len = mathutils_array_parse_alloc_viseq( + &in_faces, &in_faces_start_table, &in_faces_len_table, faces, error_prefix); + if (faces_len == -1) { + goto exit_cdt; + } + + in.verts_len = (int)vert_coords_len; + in.vert_coords = in_coords; + in.edges_len = edges_len; + in.faces_len = faces_len; + in.edges = in_edges; + in.faces = in_faces; + in.faces_start_table = in_faces_start_table; + in.faces_len_table = in_faces_len_table; + in.epsilon = epsilon; + + res = BLI_delaunay_2d_cdt_calc(&in, output_type); + + ret_value = PyTuple_New(6); + + out_vert_coords = PyList_New(res->verts_len); + for (i = 0; i < res->verts_len; i++) { + item = Vector_CreatePyObject(res->vert_coords[i], 2, NULL); + if (item == NULL) { + Py_DECREF(ret_value); + Py_DECREF(out_vert_coords); + goto exit_cdt; + } + PyList_SET_ITEM(out_vert_coords, i, item); + } + PyTuple_SET_ITEM(ret_value, 0, out_vert_coords); + + out_edges = PyList_New(res->edges_len); + for (i = 0; i < res->edges_len; i++) { + item = PyTuple_New(2); + PyTuple_SET_ITEM(item, 0, PyLong_FromLong((long)res->edges[i][0])); + PyTuple_SET_ITEM(item, 1, PyLong_FromLong((long)res->edges[i][1])); + PyList_SET_ITEM(out_edges, i, item); + } + PyTuple_SET_ITEM(ret_value, 1, out_edges); + + out_faces = list_of_lists_from_arrays( + res->faces, res->faces_start_table, res->faces_len_table, res->faces_len); + PyTuple_SET_ITEM(ret_value, 2, out_faces); + + out_orig_verts = list_of_lists_from_arrays( + res->verts_orig, res->verts_orig_start_table, res->verts_orig_len_table, res->verts_len); + PyTuple_SET_ITEM(ret_value, 3, out_orig_verts); + + out_orig_edges = list_of_lists_from_arrays( + res->edges_orig, res->edges_orig_start_table, res->edges_orig_len_table, res->edges_len); + PyTuple_SET_ITEM(ret_value, 4, out_orig_edges); + + out_orig_faces = list_of_lists_from_arrays( + res->faces_orig, res->faces_orig_start_table, res->faces_orig_len_table, res->faces_len); + PyTuple_SET_ITEM(ret_value, 5, out_orig_faces); + +exit_cdt: + if (in_coords != NULL) { + PyMem_Free(in_coords); + } + if (in_edges != NULL) { + PyMem_Free(in_edges); + } + if (in_faces != NULL) { + PyMem_Free(in_faces); + } + if (in_faces_start_table != NULL) { + PyMem_Free(in_faces_start_table); + } + if (in_faces_len_table != NULL) { + PyMem_Free(in_faces_len_table); + } + if (res) { + BLI_delaunay_2d_cdt_free(res); + } + return ret_value; +} + #endif /* MATH_STANDALONE */ static PyMethodDef M_Geometry_methods[] = { @@ -1593,6 +1774,10 @@ static PyMethodDef M_Geometry_methods[] = { (PyCFunction)M_Geometry_convex_hull_2d, METH_O, M_Geometry_convex_hull_2d_doc}, + {"delaunay_2d_cdt", + (PyCFunction)M_Geometry_delaunay_2d_cdt, + METH_VARARGS, + M_Geometry_delaunay_2d_cdt_doc}, {"box_fit_2d", (PyCFunction)M_Geometry_box_fit_2d, METH_O, M_Geometry_box_fit_2d_doc}, {"box_pack_2d", (PyCFunction)M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc}, #endif |