From 44ec0b0aabef4c8d054680281747ea33320f0961 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 10 Sep 2013 23:11:58 +0000 Subject: uv-pack operator: option to rotate uv islands to fit in the optimal rectangle when packing. --- source/blender/blenlib/BLI_convexhull2d.h | 2 + source/blender/blenlib/intern/convexhull2d.c | 73 ++++++++++++++++- .../blender/editors/uvedit/uvedit_parametrizer.c | 91 +++++++++++++++++++++- .../blender/editors/uvedit/uvedit_parametrizer.h | 2 +- source/blender/editors/uvedit/uvedit_unwrap_ops.c | 6 +- 5 files changed, 168 insertions(+), 6 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenlib/BLI_convexhull2d.h b/source/blender/blenlib/BLI_convexhull2d.h index 30de786eb96..d6b5acbb95e 100644 --- a/source/blender/blenlib/BLI_convexhull2d.h +++ b/source/blender/blenlib/BLI_convexhull2d.h @@ -28,4 +28,6 @@ int BLI_convexhull_2d_presorted(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); + #endif /* __BLI_CONVEXHULL2D__ */ diff --git a/source/blender/blenlib/intern/convexhull2d.c b/source/blender/blenlib/intern/convexhull2d.c index 4b28d1f6147..16bbf464d65 100644 --- a/source/blender/blenlib/intern/convexhull2d.c +++ b/source/blender/blenlib/intern/convexhull2d.c @@ -24,7 +24,7 @@ #include "MEM_guardedalloc.h" #include "BLI_convexhull2d.h" - +#include "BLI_math.h" #include "BLI_strict_flags.h" #include "BLI_utildefines.h" @@ -37,6 +37,9 @@ * http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm */ +/** \name Main Convex-Hull Calculation + * \{ */ + /** * tests if a point is Left|On|Right of an infinite line. * Input: three points P0, P1, and P2 @@ -219,3 +222,71 @@ int BLI_convexhull_2d(const float (*points)[2], const int n, int r_points[]) return tot; } + +/** \} */ + + +/* -------------------------------------------------------------------- */ +/* Helper functions */ + +/** \name Utility Convex-Hull Functions + * \{ */ + +/** + * \return The best angle for fitting the convex hull to an axis aligned bounding box. + * + * Intended to be used with #BLI_convexhull_2d + * + * \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) +{ + unsigned int i, i_prev; + float area_best = FLT_MAX; + float angle_best = 0.0f; + + i_prev = n - 1; + for (i = 0; i < n; i++) { + const float *ev_a = points_hull[i]; + const float *ev_b = points_hull[i_prev]; + float dvec[2]; + + sub_v2_v2v2(dvec, ev_a, ev_b); + if (normalize_v2(dvec) != 0.0f) { + float mat[2][2]; + float min[2] = {FLT_MAX, FLT_MAX}, max[2] = {-FLT_MAX, -FLT_MAX}; + + unsigned int j; + const float angle = atan2f(dvec[0], dvec[1]); + float area; + + angle_to_mat2(mat, angle); + + for (j = 0; j < n; j++) { + float tvec[2]; + mul_v2_m2v2(tvec, mat, points_hull[j]); + + min[0] = min_ff(min[0], tvec[0]); + min[1] = min_ff(min[1], tvec[1]); + + max[0] = max_ff(max[0], tvec[0]); + max[1] = max_ff(max[1], tvec[1]); + + area = (max[0] - min[0]) * (max[1] - min[1]); + if (area > area_best) { + break; + } + } + + if (area < area_best) { + area_best = area; + angle_best = angle; + } + } + + i_prev = i; + } + + return angle_best; +} +/** \} */ diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c index b6fe60a8db7..4bc7aa8e2d0 100644 --- a/source/blender/editors/uvedit/uvedit_parametrizer.c +++ b/source/blender/editors/uvedit/uvedit_parametrizer.c @@ -33,6 +33,7 @@ #include "BLI_rand.h" #include "BLI_heap.h" #include "BLI_boxpack2d.h" +#include "BLI_convexhull2d.h" #include "ONL_opennl.h" @@ -485,6 +486,36 @@ static void p_chart_uv_translate(PChart *chart, float trans[2]) } } +static void p_chart_uv_transform(PChart *chart, float mat[2][2]) +{ + PVert *v; + + for (v = chart->verts; v; v = v->nextlink) { + mul_v2_m2v2(v->uv, mat, v->uv); + } +} + +static void p_chart_uv_to_array(PChart *chart, float (*points)[2]) +{ + PVert *v; + unsigned int i = 0; + + for (v = chart->verts; v; v = v->nextlink) { + copy_v2_v2(points[i++], v->uv); + } +} + +static void UNUSED_FUNCTION(p_chart_uv_from_array)(PChart *chart, float (*points)[2]) +{ + PVert *v; + unsigned int i = 0; + + for (v = chart->verts; v; v = v->nextlink) { + copy_v2_v2(v->uv, points[i++]); + } +} + + static PBool p_intersect_line_2d_dir(float *v1, float *dir1, float *v2, float *dir2, float *isect) { float lmbda, div; @@ -4441,8 +4472,59 @@ void param_smooth_area(ParamHandle *handle) p_smooth(chart); } } - -void param_pack(ParamHandle *handle, float margin) + +/* don't pack, just rotate (used for better packing) */ +static void param_pack_rotate(ParamHandle *handle) +{ + PChart *chart; + int i; + + PHandle *phandle = (PHandle *)handle; + + for (i = 0; i < phandle->ncharts; i++) { + float (*points)[2]; + int *index_map; + int tot; + + chart = phandle->charts[i]; + + if (chart->flag & PCHART_NOPACK) { + continue; + } + + 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); + + 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); + + 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); + } +} + +void param_pack(ParamHandle *handle, float margin, bool do_rotate) { /* box packing variables */ BoxPack *boxarray, *box; @@ -4461,6 +4543,11 @@ void param_pack(ParamHandle *handle, float margin) if (phandle->aspx != phandle->aspy) param_scale(handle, 1.0f / phandle->aspx, 1.0f / phandle->aspy); + /* this could be its own function */ + if (do_rotate) { + param_pack_rotate(handle); + } + /* we may not use all these boxes */ boxarray = MEM_mallocN(phandle->ncharts * sizeof(BoxPack), "BoxPack box"); diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.h b/source/blender/editors/uvedit/uvedit_parametrizer.h index 7127a436570..265577555a6 100644 --- a/source/blender/editors/uvedit/uvedit_parametrizer.h +++ b/source/blender/editors/uvedit/uvedit_parametrizer.h @@ -99,7 +99,7 @@ void param_smooth_area(ParamHandle *handle); /* Packing */ -void param_pack(ParamHandle *handle, float margin); +void param_pack(ParamHandle *handle, float margin, bool do_rotate); /* Average area for all charts */ diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c index 49505b03a19..87cc42001d6 100644 --- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c +++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c @@ -718,6 +718,7 @@ static int pack_islands_exec(bContext *C, wmOperator *op) BMEditMesh *em = BKE_editmesh_from_object(obedit); ParamHandle *handle; bool implicit = true; + bool do_rotate = RNA_boolean_get(op->ptr, "rotate"); if (!uvedit_have_selection(scene, em, implicit)) { return OPERATOR_CANCELLED; @@ -729,7 +730,7 @@ static int pack_islands_exec(bContext *C, wmOperator *op) RNA_float_set(op->ptr, "margin", scene->toolsettings->uvcalc_margin); handle = construct_param_handle(scene, obedit, em, implicit, 0, 1, 1); - param_pack(handle, scene->toolsettings->uvcalc_margin); + param_pack(handle, scene->toolsettings->uvcalc_margin, do_rotate); param_flush(handle); param_delete(handle); @@ -753,6 +754,7 @@ void UV_OT_pack_islands(wmOperatorType *ot) ot->poll = ED_operator_uvedit; /* properties */ + RNA_def_boolean(ot->srna, "rotate", true, "Rotate", "Rotate islands for best fit"); RNA_def_float_factor(ot->srna, "margin", 0.001f, 0.0f, 1.0f, "Margin", "Space between islands", 0.0f, 1.0f); } @@ -1151,7 +1153,7 @@ void ED_unwrap_lscm(Scene *scene, Object *obedit, const short sel) param_lscm_end(handle); param_average(handle); - param_pack(handle, scene->toolsettings->uvcalc_margin); + param_pack(handle, scene->toolsettings->uvcalc_margin, false); param_flush(handle); -- cgit v1.2.3