diff options
author | Chris Blackbourn <chrisbblend@gmail.com> | 2022-09-25 03:09:44 +0300 |
---|---|---|
committer | Chris Blackbourn <chrisbblend@gmail.com> | 2022-09-28 02:24:16 +0300 |
commit | 5c93c37678d16e4c6ee52c579e51fdafb7d0a879 (patch) | |
tree | 3bb28c8cae2da568aba3ca565c2296055822ef4c /source/blender/blenlib/intern | |
parent | 2ead05d73878721703de5d2fe6a07eb9053168aa (diff) |
Cleanup: improve 2D convex hull
Improve correctness, API, comments, memory usage and performance
of the 2D convex hull calculation.
Pre-requisite for UV packing improvements.
Differential Revision: https://developer.blender.org/D16055
Diffstat (limited to 'source/blender/blenlib/intern')
-rw-r--r-- | source/blender/blenlib/intern/convexhull_2d.c | 74 |
1 files changed, 35 insertions, 39 deletions
diff --git a/source/blender/blenlib/intern/convexhull_2d.c b/source/blender/blenlib/intern/convexhull_2d.c index ee5d000b72f..fee6241a817 100644 --- a/source/blender/blenlib/intern/convexhull_2d.c +++ b/source/blender/blenlib/intern/convexhull_2d.c @@ -39,8 +39,9 @@ static float is_left(const float p0[2], const float p1[2], const float p2[2]) return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]); } -int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]) +static int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points[]) { + BLI_assert(n >= 2); /* Doesn't handle trivial cases. */ /* the output array r_points[] will be used as the stack */ int bot = 0; int top = -1; /* indices for bottom and top of the stack */ @@ -66,6 +67,7 @@ int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points r_points[++top] = minmax; } r_points[++top] = minmin; /* add polygon endpoint */ + BLI_assert(top + 1 <= n); return top + 1; } @@ -122,16 +124,18 @@ int BLI_convexhull_2d_sorted(const float (*points)[2], const int n, int r_points } if (points[i][0] == points[r_points[0]][0] && points[i][1] == points[r_points[0]][1]) { + BLI_assert(top + 1 <= n); return top + 1; /* special case (mgomes) */ } r_points[++top] = i; /* push points[i] onto stack */ } - if (minmax != minmin) { + if (minmax != minmin && r_points[0] != minmin) { r_points[++top] = minmin; /* push joining endpoint onto stack */ } + BLI_assert(top + 1 <= n); return top + 1; } @@ -162,35 +166,38 @@ static int pointref_cmp_yx(const void *a_, const void *b_) int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) { - struct PointRef *points_ref = MEM_mallocN(sizeof(*points_ref) * (size_t)n, __func__); - float(*points_sort)[2] = MEM_mallocN(sizeof(*points_sort) * (size_t)n, __func__); - int *points_map; - int points_hull_num, i; + BLI_assert(n >= 0); + if (n < 2) { + if (n == 1) { + r_points[0] = 0; + } + return n; + } + struct PointRef *points_ref = MEM_mallocN(sizeof(*points_ref) * n, __func__); + float(*points_sort)[2] = MEM_mallocN(sizeof(*points_sort) * n, __func__); - for (i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { points_ref[i].pt = points[i]; } - /* Sort the points by X, then by Y (required by the algorithm) */ + /* Sort the points by X, then by Y. */ qsort(points_ref, (size_t)n, sizeof(struct PointRef), pointref_cmp_yx); - for (i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { memcpy(points_sort[i], points_ref[i].pt, sizeof(float[2])); } - points_hull_num = BLI_convexhull_2d_sorted(points_sort, n, r_points); + int points_hull_num = BLI_convexhull_2d_sorted(points_sort, n, r_points); - /* map back to the original index values */ - points_map = (int *)points_sort; /* abuse float array for temp storage */ - for (i = 0; i < points_hull_num; i++) { - points_map[i] = (int)((const float(*)[2])points_ref[r_points[i]].pt - points); + /* Map back to the unsorted index values. */ + for (int i = 0; i < points_hull_num; i++) { + r_points[i] = (int)((const float(*)[2])points_ref[r_points[i]].pt - points); } - memcpy(r_points, points_map, (size_t)points_hull_num * sizeof(*points_map)); - MEM_freeN(points_ref); MEM_freeN(points_sort); + BLI_assert(points_hull_num <= n); return points_hull_num; } @@ -202,14 +209,13 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) /** \name Utility Convex-Hull Functions * \{ */ -float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], uint n) +static float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], int n) { - uint i, i_prev; float area_best = FLT_MAX; float dvec_best[2]; /* best angle, delay atan2 */ - i_prev = n - 1; - for (i = 0; i < n; i++) { + int i_prev = n - 1; + for (int i = 0; i < n; i++) { const float *ev_a = points_hull[i]; const float *ev_b = points_hull[i_prev]; float dvec[2]; /* 2d rotation matrix */ @@ -218,10 +224,9 @@ float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], uint n) if (normalize_v2(dvec) != 0.0f) { /* rotation matrix */ float min[2] = {FLT_MAX, FLT_MAX}, max[2] = {-FLT_MAX, -FLT_MAX}; - uint j; float area; - for (j = 0; j < n; j++) { + for (int j = 0; j < n; j++) { float tvec[2]; mul_v2_v2_cw(tvec, dvec, points_hull[j]); @@ -249,32 +254,23 @@ float BLI_convexhull_aabb_fit_hull_2d(const float (*points_hull)[2], uint n) return (area_best != FLT_MAX) ? atan2f(dvec_best[0], dvec_best[1]) : 0.0f; } -float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], uint n) +float BLI_convexhull_aabb_fit_points_2d(const float (*points)[2], int n) { - int *index_map; - int points_hull_num; + float angle = 0.0f; - float angle; + int *index_map = MEM_mallocN(sizeof(*index_map) * n, __func__); - index_map = MEM_mallocN(sizeof(*index_map) * n * 2, __func__); + int points_hull_num = BLI_convexhull_2d(points, n, index_map); - points_hull_num = BLI_convexhull_2d(points, (int)n, index_map); - - if (points_hull_num) { - float(*points_hull)[2]; - int j; - - points_hull = MEM_mallocN(sizeof(*points_hull) * (size_t)points_hull_num, __func__); - for (j = 0; j < points_hull_num; j++) { + if (points_hull_num > 1) { + float(*points_hull)[2] = MEM_mallocN(sizeof(*points_hull) * points_hull_num, __func__); + for (int j = 0; j < points_hull_num; j++) { copy_v2_v2(points_hull[j], points[index_map[j]]); } - angle = BLI_convexhull_aabb_fit_hull_2d(points_hull, (uint)points_hull_num); + angle = BLI_convexhull_aabb_fit_hull_2d(points_hull, points_hull_num); MEM_freeN(points_hull); } - else { - angle = 0.0f; - } MEM_freeN(index_map); |