uv-pack operator: option to rotate uv islands to fit in the optimal rectangle when...
authorCampbell Barton <ideasman42@gmail.com>
Tue, 10 Sep 2013 23:11:58 +0000 (23:11 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 10 Sep 2013 23:11:58 +0000 (23:11 +0000)
source/blender/blenlib/BLI_convexhull2d.h
source/blender/blenlib/intern/convexhull2d.c
source/blender/editors/uvedit/uvedit_parametrizer.c
source/blender/editors/uvedit/uvedit_parametrizer.h
source/blender/editors/uvedit/uvedit_unwrap_ops.c

index 30de786eb96b0874fabd56118a6094de74045109..d6b5acbb95e0a1d582b2977bb812836ef67b0cb9 100644 (file)
@@ -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__ */
index 4b28d1f614782dfccd6c4a3bc76e0353192eac7b..16bbf464d6596ca472acb199e05737bdc38b1440 100644 (file)
@@ -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;
+}
+/** \} */
index b6fe60a8db70ed9bd1ac2963c6fd4c03c9bb7527..4bc7aa8e2d003462602d281a680a74d7e0f8b216 100644 (file)
@@ -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");
        
index 7127a43657012863532ffba4eea72815225e852e..265577555a643035f3bab75777541a434bb854d9 100644 (file)
@@ -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 */
 
index 49505b03a191d53538e1524a6d35a3c30d2e5f87..87cc42001d631188a5c2e2e3fa609637d403e980 100644 (file)
@@ -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);