diff options
-rw-r--r-- | source/blender/blenlib/BLI_convexhull2d.h | 5 | ||||
-rw-r--r-- | source/blender/blenlib/intern/convexhull2d.c | 47 | ||||
-rw-r--r-- | source/blender/editors/uvedit/uvedit_parametrizer.c | 30 | ||||
-rw-r--r-- | source/blender/python/mathutils/mathutils_geometry.c | 60 |
4 files changed, 93 insertions, 49 deletions
diff --git a/source/blender/blenlib/BLI_convexhull2d.h b/source/blender/blenlib/BLI_convexhull2d.h index d6b5acbb95e..3f0787b37b1 100644 --- a/source/blender/blenlib/BLI_convexhull2d.h +++ b/source/blender/blenlib/BLI_convexhull2d.h @@ -25,9 +25,10 @@ * \ingroup bli */ -int BLI_convexhull_2d_presorted(const float (*points)[2], const int n, int r_points[]); +int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]); int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]); -float BLI_convexhull_aabb_fit_2d(const float (*points_hull)[2], unsigned int n); +float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n); +float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n); #endif /* __BLI_CONVEXHULL2D__ */ diff --git a/source/blender/blenlib/intern/convexhull2d.c b/source/blender/blenlib/intern/convexhull2d.c index 16bbf464d65..536bb6d94e3 100644 --- a/source/blender/blenlib/intern/convexhull2d.c +++ b/source/blender/blenlib/intern/convexhull2d.c @@ -60,7 +60,7 @@ static float is_left(const float p0[2], const float p1[2], const float p2[2]) * \param r_points An array of the convex hull vertex indices (max is n). * \returns the number of points in r_points. */ -int BLI_convexhull_2d_presorted(const float (*points)[2], const int n, int r_points[]) +int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]) { /* the output array r_points[] will be used as the stack */ int bot = 0; @@ -207,7 +207,7 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) memcpy(points_sort[i], points_ref[i].pt, sizeof(float[2])); } - tot = BLI_convexhull_2d_presorted((const float (*)[2])points_sort, n, r_points); + tot = BLI_convexhull_2d_sorted((const float (*)[2])points_sort, n, r_points); /* map back to the original index values */ points_map = (int *)points_sort; /* abuse float array for temp storage */ @@ -237,9 +237,12 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) * * Intended to be used with #BLI_convexhull_2d * + * \param points Orded hull points + * (result of #BLI_convexhull_2d mapped to a contiguous array). + * * \note we could return the index of the best edge too if its needed. */ -float BLI_convexhull_aabb_fit_2d(const float (*points_hull)[2], unsigned int n) +float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], unsigned int n) { unsigned int i, i_prev; float area_best = FLT_MAX; @@ -289,4 +292,42 @@ float BLI_convexhull_aabb_fit_2d(const float (*points_hull)[2], unsigned int n) return angle_best; } + +/** + * Wrap #BLI_convexhull_aabb_fit_hull_2d and do the convex hull calculation. + * + * \param points arbitrary 2d points. + */ +float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], unsigned int n) +{ + int *index_map; + int tot; + + float angle; + + index_map = MEM_mallocN(sizeof(*index_map) * n, __func__); + + tot = BLI_convexhull_2d((const float (*)[2])points, (int)n, index_map); + + if (tot) { + float (*points_hull)[2]; + int j; + + points_hull = MEM_mallocN(sizeof(*points_hull) * (size_t)tot, __func__); + for (j = 0; j < tot; j++) { + copy_v2_v2(points_hull[j], points[index_map[j]]); + } + + angle = BLI_convexhull_aabb_fit_hull_2d((const float (*)[2])points_hull, (unsigned int)tot); + MEM_freeN(points_hull); + } + else { + angle = 0.0f; + } + + MEM_freeN(index_map); + + return angle; +} + /** \} */ diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c index 4bc7aa8e2d0..f0e97ffe3b1 100644 --- a/source/blender/editors/uvedit/uvedit_parametrizer.c +++ b/source/blender/editors/uvedit/uvedit_parametrizer.c @@ -4483,8 +4483,8 @@ static void param_pack_rotate(ParamHandle *handle) for (i = 0; i < phandle->ncharts; i++) { float (*points)[2]; - int *index_map; int tot; + float angle; chart = phandle->charts[i]; @@ -4493,34 +4493,18 @@ static void param_pack_rotate(ParamHandle *handle) } points = MEM_mallocN(sizeof(*points) * chart->nverts, __func__); - index_map = MEM_mallocN(sizeof(*index_map) * chart->nverts, __func__); p_chart_uv_to_array(chart, points); - tot = BLI_convexhull_2d((const float (*)[2])points, chart->nverts, index_map); + angle = BLI_convexhull_aabb_fit_points_2d((const float (*)[2])points, tot); - if (tot) { - float (*points_hull)[2]; - int j; - float angle; - - points_hull = MEM_mallocN(sizeof(*points) * tot, __func__); - for (j = 0; j < tot; j++) { - copy_v2_v2(points_hull[j], points[index_map[j]]); - } - - angle = BLI_convexhull_aabb_fit_2d((const float (*)[2])points_hull, tot); - MEM_freeN(points_hull); + MEM_freeN(points); - if (angle != 0.0f) { - float mat[2][2]; - angle_to_mat2(mat, angle); - p_chart_uv_transform(chart, mat); - } + if (angle != 0.0f) { + float mat[2][2]; + angle_to_mat2(mat, angle); + p_chart_uv_transform(chart, mat); } - - MEM_freeN(points); - MEM_freeN(index_map); } } diff --git a/source/blender/python/mathutils/mathutils_geometry.c b/source/blender/python/mathutils/mathutils_geometry.c index a8c23d3b0f4..06aa0cb2753 100644 --- a/source/blender/python/mathutils/mathutils_geometry.c +++ b/source/blender/python/mathutils/mathutils_geometry.c @@ -1504,6 +1504,38 @@ static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlis return ret; } +PyDoc_STRVAR(M_Geometry_box_fit_2d_doc, +".. function:: box_fit_2d(points)\n" +"\n" +" Returns a list of indices into the list given\n" +"\n" +" :arg points: list of 2d points.\n" +" :type points: list\n" +" :return: a list of indices\n" +" :rtype: list of ints\n" +); +static PyObject *M_Geometry_box_fit_2d(PyObject *UNUSED(self), PyObject *pointlist) +{ + float (*points)[2]; + Py_ssize_t len; + + float angle = 0.0f; + + len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "box_fit_2d"); + if (len == -1) { + return NULL; + } + + if (len) { + /* Non Python function */ + angle = BLI_convexhull_aabb_fit_points_2d((const float (*)[2])points, len); + + PyMem_Free(points); + } + + + return PyFloat_FromDouble(angle); +} PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc, ".. function:: convex_hull_2d(points)\n" @@ -1517,42 +1549,24 @@ PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc, ); static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *pointlist) { + float (*points)[2]; Py_ssize_t len; PyObject *ret; - if (!PyList_Check(pointlist)) { - PyErr_SetString(PyExc_TypeError, - "expected a list of Vectors"); + len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "convex_hull_2d"); + if (len == -1) { return NULL; } - len = PyList_GET_SIZE(pointlist); if (len) { - float (*points)[2] = MEM_mallocN(sizeof(*points) * len, __func__); int *index_map; Py_ssize_t len_ret, i; - PyObject *list_item; - bool ok = true; - - for (i = 0; i < len; i++) { - list_item = PyList_GET_ITEM(pointlist, i); - if (mathutils_array_parse(points[i], 2, 2, list_item, "convex_hull") == -1) { - ok = false; - break; - } - } - - if (ok == false) { - MEM_freeN(points); - return NULL; - } index_map = MEM_mallocN(sizeof(*index_map) * len, __func__); /* Non Python function */ len_ret = BLI_convexhull_2d((const float (*)[2])points, len, index_map); - MEM_freeN(points); ret = PyList_New(len_ret); for (i = 0; i < len_ret; i++) { @@ -1560,11 +1574,14 @@ static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *poi } MEM_freeN(index_map); + + PyMem_Free(points); } else { ret = PyList_New(0); } + return ret; } @@ -1593,6 +1610,7 @@ static PyMethodDef M_Geometry_methods[] = { {"interpolate_bezier", (PyCFunction) M_Geometry_interpolate_bezier, METH_VARARGS, M_Geometry_interpolate_bezier_doc}, {"tessellate_polygon", (PyCFunction) M_Geometry_tessellate_polygon, METH_O, M_Geometry_tessellate_polygon_doc}, {"convex_hull_2d", (PyCFunction) M_Geometry_convex_hull_2d, METH_O, M_Geometry_convex_hull_2d_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 {NULL, NULL, 0, NULL} |