Fix T82637: pack UV islands fails with some non-manifold meshes

Edges with 3 or more connected UV's caused UV pack to fail.

Instead of using functions from uvedit_parametrizer.c which are intended
specifically for ABF/LSCM unwrapping, use a simpler method for packing
which stores arrays of BMesh faces.

4 files changed, 528 insertions, 14 deletions

diff --git a/source/blender/editors/include/ED_uvedit.h b/source/blender/editors/include/ED_uvedit.h
index 629e77bd4f2..a55e97fff72 100644
--- a/source/blender/editors/include/ED_uvedit.h
+++ b/source/blender/editors/include/ED_uvedit.h
@@ -27,6 +27,7 @@
 extern "C" {
 #endif
 
+struct ARegion;
 struct ARegionType;
 struct BMEditMesh;
 struct BMFace;
@@ -233,6 +234,20 @@ void ED_image_draw_cursor(struct ARegion *region, const float cursor[2]);
 /* uvedit_buttons.c */
 void ED_uvedit_buttons_register(struct ARegionType *art);
 
+/* uvedit_islands.c */
+struct UVPackIsland_Params {
+  uint rotate : 1;
+  /** -1 not to align to axis, otherwise 0,1 for X,Y. */
+  int rotate_align_axis : 2;
+  uint only_selected_uvs : 1;
+  uint only_selected_faces : 1;
+  uint correct_aspect : 1;
+};
+void ED_uvedit_pack_islands_multi(const Scene *scene,
+                                  Object **objects,
+                                  const uint objects_len,
+                                  const struct UVPackIsland_Params *params);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/editors/uvedit/CMakeLists.txt b/source/blender/editors/uvedit/CMakeLists.txt
index f1751ef8d27..8e4a3df920e 100644
--- a/source/blender/editors/uvedit/CMakeLists.txt
+++ b/source/blender/editors/uvedit/CMakeLists.txt
@@ -39,6 +39,7 @@ set(SRC
   uvedit_parametrizer.c
   uvedit_path.c
   uvedit_rip.c
+  uvedit_islands.c
   uvedit_select.c
   uvedit_smart_stitch.c
   uvedit_unwrap_ops.c
diff --git a/source/blender/editors/uvedit/uvedit_islands.c b/source/blender/editors/uvedit/uvedit_islands.c
new file mode 100644
index 00000000000..ddca05bedc5
--- /dev/null
+++ b/source/blender/editors/uvedit/uvedit_islands.c
@@ -0,0 +1,485 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup eduv
+ *
+ * Utilities for manipulating UV islands.
+ *
+ * \note This is similar to `uvedit_parametrizer.c`,
+ * however the data structures there don't support arbitrary topology
+ * such as an edge with 3 or more faces using it.
+ * This API uses #BMesh data structures and doesn't have limitations for manifold meshes.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_meshdata_types.h"
+#include "DNA_scene_types.h"
+
+#include "BLI_boxpack_2d.h"
+#include "BLI_convexhull_2d.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+#include "BLI_rect.h"
+
+#include "BKE_editmesh.h"
+
+#include "DEG_depsgraph.h"
+
+#include "ED_uvedit.h" /* Own include. */
+
+#include "WM_api.h"
+#include "WM_types.h"
+
+#include "bmesh.h"
+
+/* -------------------------------------------------------------------- */
+/** \name UV Face Utilities
+ * \{ */
+
+static void bm_face_uv_scale_y(BMFace *f, const float scale_y, const int cd_loop_uv_offset)
+{
+  BMLoop *l_iter;
+  BMLoop *l_first;
+  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+  do {
+    MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_uv_offset);
+    luv->uv[1] *= scale_y;
+  } while ((l_iter = l_iter->next) != l_first);
+}
+
+static void bm_face_uv_translate_and_scale_around_pivot(BMFace *f,
+                                                        const float offset[2],
+                                                        const float scale[2],
+                                                        const float pivot[2],
+                                                        const int cd_loop_uv_offset)
+{
+  BMLoop *l_iter;
+  BMLoop *l_first;
+  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+  do {
+    MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_uv_offset);
+    for (int i = 0; i < 2; i++) {
+      luv->uv[i] = offset[i] + (((luv->uv[i] - pivot[i]) * scale[i]) + pivot[i]);
+    }
+  } while ((l_iter = l_iter->next) != l_first);
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name UV Face Array Utilities
+ * \{ */
+
+static void bm_face_array_calc_bounds(BMFace **faces,
+                                      int faces_len,
+                                      const uint cd_loop_uv_offset,
+                                      rctf *r_bounds_rect)
+{
+  float bounds_min[2], bounds_max[2];
+  INIT_MINMAX2(bounds_min, bounds_max);
+  for (int i = 0; i < faces_len; i++) {
+    BMFace *f = faces[i];
+    BM_face_uv_minmax(f, bounds_min, bounds_max, cd_loop_uv_offset);
+  }
+  r_bounds_rect->xmin = bounds_min[0];
+  r_bounds_rect->ymin = bounds_min[1];
+  r_bounds_rect->xmax = bounds_max[0];
+  r_bounds_rect->ymax = bounds_max[1];
+}
+
+/**
+ * Return an array of un-ordered UV coordinates,
+ * without duplicating coordinates for loops that share a vertex.
+ */
+static float (*bm_face_array_calc_unique_uv_coords(
+    BMFace **faces, int faces_len, const uint cd_loop_uv_offset, int *r_coords_len))[2]
+{
+  int coords_len_alloc = 0;
+  for (int i = 0; i < faces_len; i++) {
+    BMFace *f = faces[i];
+    BMLoop *l_iter, *l_first;
+    l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+    do {
+      BM_elem_flag_enable(l_iter, BM_ELEM_TAG);
+    } while ((l_iter = l_iter->next) != l_first);
+    coords_len_alloc += f->len;
+  }
+
+  float(*coords)[2] = MEM_mallocN(sizeof(*coords) * coords_len_alloc, __func__);
+  int coords_len = 0;
+
+  for (int i = 0; i < faces_len; i++) {
+    BMFace *f = faces[i];
+    BMLoop *l_iter, *l_first;
+    l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+    do {
+      if (!BM_elem_flag_test(l_iter, BM_ELEM_TAG)) {
+        /* Already walked over, continue. */
+        continue;
+      }
+
+      BM_elem_flag_disable(l_iter, BM_ELEM_TAG);
+      const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_uv_offset);
+      copy_v2_v2(coords[coords_len++], luv->uv);
+
+      /* Un tag all connected so we don't add them twice.
+       * Note that we will tag other loops not part of `faces` but this is harmless,
+       * since we're only turning off a tag. */
+      BMVert *v_pivot = l_iter->v;
+      BMEdge *e_first = v_pivot->e;
+      const BMEdge *e = e_first;
+      do {
+        const BMLoop *l_radial = e->l;
+        do {
+          if (l_radial->v == l_iter->v) {
+            if (BM_elem_flag_test(l_radial, BM_ELEM_TAG)) {
+              const MLoopUV *luv_radial = BM_ELEM_CD_GET_VOID_P(l_radial, cd_loop_uv_offset);
+              if (equals_v2v2(luv->uv, luv_radial->uv)) {
+                /* Don't add this UV when met in another face in `faces`. */
+                BM_elem_flag_disable(l_iter, BM_ELEM_TAG);
+              }
+            }
+          }
+        } while ((l_radial = l_radial->radial_next) != e->l);
+      } while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != e_first);
+    } while ((l_iter = l_iter->next) != l_first);
+  }
+  coords = MEM_reallocN(coords, sizeof(*coords) * coords_len);
+  *r_coords_len = coords_len;
+  return coords;
+}
+
+/**
+ * \param align_to_axis:
+ * - -1: don't align to an axis.
+ * -  0: align horizontally.
+ * -  1: align vertically.
+ */
+static void bm_face_array_uv_rotate_fit_aabb(BMFace **faces,
+                                             int faces_len,
+                                             int align_to_axis,
+                                             const uint cd_loop_uv_offset)
+{
+  /* Calculate unique coordinates since calculating a convex hull can be an expensive operation. */
+  int coords_len;
+  float(*coords)[2] = bm_face_array_calc_unique_uv_coords(
+      faces, faces_len, cd_loop_uv_offset, &coords_len);
+
+  float angle = BLI_convexhull_aabb_fit_points_2d(coords, coords_len);
+
+  if (align_to_axis != -1) {
+    if (angle != 0.0f) {
+      float matrix[2][2];
+      angle_to_mat2(matrix, angle);
+      for (int i = 0; i < coords_len; i++) {
+        mul_m2_v2(matrix, coords[i]);
+      }
+    }
+
+    float bounds_min[2], bounds_max[2];
+    INIT_MINMAX2(bounds_min, bounds_max);
+    for (int i = 0; i < coords_len; i++) {
+      minmax_v2v2_v2(bounds_min, bounds_max, coords[i]);
+    }
+
+    float size[2];
+    sub_v2_v2v2(size, bounds_max, bounds_min);
+    if (align_to_axis ? (size[1] < size[0]) : (size[0] < size[1])) {
+      angle += DEG2RAD(90.0);
+    }
+  }
+
+  MEM_freeN(coords);
+
+  if (angle != 0.0f) {
+    float matrix[2][2];
+    angle_to_mat2(matrix, angle);
+    for (int i = 0; i < faces_len; i++) {
+      BM_face_uv_transform(faces[i], matrix, cd_loop_uv_offset);
+    }
+  }
+}
+
+static void bm_face_array_uv_scale_y(BMFace **faces,
+                                     int faces_len,
+                                     const float scale_y,
+                                     const uint cd_loop_uv_offset)
+{
+  for (int i = 0; i < faces_len; i++) {
+    BMFace *f = faces[i];
+    bm_face_uv_scale_y(f, scale_y, cd_loop_uv_offset);
+  }
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Calculate UV Islands
+ *
+ * \note Currently this is a private API/type, it could be made public.
+ * \{ */
+
+struct FaceIsland {
+  struct FaceIsland *next, *prev;
+  BMFace **faces;
+  int faces_len;
+  rctf bounds_rect;
+  /**
+   * \note While this is duplicate information,
+   * it allows islands from multiple meshes to be stored in the same list.
+   */
+  uint cd_loop_uv_offset;
+  float aspect_y;
+};
+
+struct SharedUVLoopData {
+  uint cd_loop_uv_offset;
+};
+
+static bool bm_loop_uv_shared_edge_check(const BMLoop *l_a, const BMLoop *l_b, void *user_data)
+{
+  const struct SharedUVLoopData *data = user_data;
+  return BM_loop_uv_share_edge_check((BMLoop *)l_a, (BMLoop *)l_b, data->cd_loop_uv_offset);
+}
+
+/**
+ * Calculate islands and add them to \a island_list returning the number of items added.
+ */
+static int bm_mesh_calc_uv_islands(const Scene *scene,
+                                   BMesh *bm,
+                                   ListBase *island_list,
+                                   const bool only_selected_faces,
+                                   const bool only_selected_uvs,
+                                   const float aspect_y,
+                                   const uint cd_loop_uv_offset)
+{
+  int island_added = 0;
+  BM_mesh_elem_table_ensure(bm, BM_FACE);
+
+  struct SharedUVLoopData user_data = {
+      .cd_loop_uv_offset = cd_loop_uv_offset,
+  };
+
+  int *groups_array = MEM_mallocN(sizeof(*groups_array) * (size_t)bm->totface, __func__);
+
+  int(*group_index)[2];
+
+  /* Calculate the tag to use. */
+  uchar hflag_face_test = 0;
+  if (only_selected_faces) {
+    if (only_selected_uvs) {
+      BMFace *f;
+      BMIter iter;
+      BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+        bool value = false;
+        if (BM_elem_flag_test(f, BM_ELEM_SELECT) &&
+            uvedit_face_select_test(scene, f, cd_loop_uv_offset)) {
+          value = true;
+        }
+        BM_elem_flag_set(f, BM_ELEM_TAG, value);
+      }
+      hflag_face_test = BM_ELEM_TAG;
+    }
+    else {
+      hflag_face_test = BM_ELEM_SELECT;
+    }
+  }
+
+  const int group_len = BM_mesh_calc_face_groups(bm,
+                                                 groups_array,
+                                                 &group_index,
+                                                 NULL,
+                                                 bm_loop_uv_shared_edge_check,
+                                                 &user_data,
+                                                 hflag_face_test,
+                                                 BM_EDGE);
+
+  for (int i = 0; i < group_len; i++) {
+    const int faces_start = group_index[i][0];
+    const int faces_len = group_index[i][1];
+    BMFace **faces = MEM_mallocN(sizeof(*faces) * faces_len, __func__);
+
+    float bounds_min[2], bounds_max[2];
+    INIT_MINMAX2(bounds_min, bounds_max);
+
+    for (int j = 0; j < faces_len; j++) {
+      faces[j] = BM_face_at_index(bm, groups_array[faces_start + j]);
+    }
+
+    struct FaceIsland *island = MEM_callocN(sizeof(*island), __func__);
+    island->faces = faces;
+    island->faces_len = faces_len;
+    island->cd_loop_uv_offset = cd_loop_uv_offset;
+    island->aspect_y = aspect_y;
+    BLI_addtail(island_list, island);
+    island_added += 1;
+  }
+
+  MEM_freeN(groups_array);
+  MEM_freeN(group_index);
+  return island_added;
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Public UV Island Packing
+ *
+ * \note This behavior follows #param_pack.
+ * \{ */
+
+void ED_uvedit_pack_islands_multi(const Scene *scene,
+                                  Object **objects,
+                                  const uint objects_len,
+                                  const struct UVPackIsland_Params *params)
+{
+  /* Align to the Y axis, could make this configurable. */
+  const int rotate_align_axis = 1;
+  ListBase island_list = {NULL};
+  int island_list_len = 0;
+
+  for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+    Object *obedit = objects[ob_index];
+    BMEditMesh *em = BKE_editmesh_from_object(obedit);
+    BMesh *bm = em->bm;
+
+    const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV);
+    if (cd_loop_uv_offset == -1) {
+      continue;
+    }
+
+    float aspect_y = 1.0f;
+    if (params->correct_aspect) {
+      float aspx, aspy;
+      ED_uvedit_get_aspect(obedit, &aspx, &aspy);
+      if (aspx != aspy) {
+        aspect_y = aspx / aspy;
+      }
+    }
+
+    island_list_len += bm_mesh_calc_uv_islands(scene,
+                                               bm,
+                                               &island_list,
+                                               params->only_selected_faces,
+                                               params->only_selected_uvs,
+                                               aspect_y,
+                                               cd_loop_uv_offset);
+  }
+
+  if (island_list_len == 0) {
+    return;
+  }
+
+  float margin = scene->toolsettings->uvcalc_margin;
+  double area = 0.0f;
+
+  struct FaceIsland **island_array = MEM_mallocN(sizeof(*island_array) * island_list_len,
+                                                 __func__);
+  BoxPack *boxarray = MEM_mallocN(sizeof(*boxarray) * island_list_len, __func__);
+
+  int index;
+  LISTBASE_FOREACH_INDEX (struct FaceIsland *, island, &island_list, index) {
+
+    if (params->rotate) {
+      if (island->aspect_y != 1.0f) {
+        bm_face_array_uv_scale_y(
+            island->faces, island->faces_len, 1.0f / island->aspect_y, island->cd_loop_uv_offset);
+      }
+
+      bm_face_array_uv_rotate_fit_aabb(
+          island->faces, island->faces_len, rotate_align_axis, island->cd_loop_uv_offset);
+
+      if (island->aspect_y != 1.0f) {
+        bm_face_array_uv_scale_y(
+            island->faces, island->faces_len, island->aspect_y, island->cd_loop_uv_offset);
+      }
+    }
+
+    bm_face_array_calc_bounds(
+        island->faces, island->faces_len, island->cd_loop_uv_offset, &island->bounds_rect);
+
+    BoxPack *box = &boxarray[index];
+    box->index = index;
+    box->x = 0.0f;
+    box->y = 0.0f;
+    box->w = BLI_rctf_size_x(&island->bounds_rect);
+    box->h = BLI_rctf_size_y(&island->bounds_rect);
+
+    island_array[index] = island;
+
+    if (margin > 0.0f) {
+      area += (double)sqrtf(box->w * box->h);
+    }
+  }
+
+  if (margin > 0.0f) {
+    /* Logic matches behavior from #param_pack,
+     * use area so multiply the margin by the area to give
+     * predictable results not dependent on UV scale. */
+    margin = (margin * (float)area) * 0.1f;
+    for (int i = 0; i < island_list_len; i++) {
+      struct FaceIsland *island = island_array[i];
+      BoxPack *box = &boxarray[i];
+
+      BLI_rctf_pad(&island->bounds_rect, margin, margin);
+      box->w = BLI_rctf_size_x(&island->bounds_rect);
+      box->h = BLI_rctf_size_y(&island->bounds_rect);
+    }
+  }
+
+  float boxarray_size[2];
+  BLI_box_pack_2d(boxarray, island_list_len, &boxarray_size[0], &boxarray_size[1]);
+
+  /* Don't change the aspect when scaling. */
+  boxarray_size[0] = boxarray_size[1] = max_ff(boxarray_size[0], boxarray_size[1]);
+
+  const float scale[2] = {1.0f / boxarray_size[0], 1.0f / boxarray_size[1]};
+
+  for (int i = 0; i < island_list_len; i++) {
+    struct FaceIsland *island = island_array[boxarray[i].index];
+    const float pivot[2] = {
+        island->bounds_rect.xmin,
+        island->bounds_rect.ymin,
+    };
+    const float offset[2] = {
+        (boxarray[i].x * scale[0]) - island->bounds_rect.xmin,
+        (boxarray[i].y * scale[1]) - island->bounds_rect.ymin,
+    };
+    for (int j = 0; j < island->faces_len; j++) {
+      BMFace *efa = island->faces[j];
+      bm_face_uv_translate_and_scale_around_pivot(
+          efa, offset, scale, pivot, island->cd_loop_uv_offset);
+    }
+  }
+
+  for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+    Object *obedit = objects[ob_index];
+    DEG_id_tag_update(obedit->data, ID_RECALC_GEOMETRY);
+    WM_main_add_notifier(NC_GEOM | ND_DATA, obedit->data);
+  }
+
+  for (int i = 0; i < island_list_len; i++) {
+    MEM_freeN(island_array[i]->faces);
+    MEM_freeN(island_array[i]);
+  }
+
+  MEM_freeN(island_array);
+  MEM_freeN(boxarray);
+}
+
+/** \} */
diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index a50386a64e2..6989f0afbe8 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -965,6 +965,12 @@ static void uvedit_pack_islands(const Scene *scene, Object *ob, BMesh *bm)
   param_delete(handle);
 }
 
+/**
+ * \warning Since this uses #ParamHandle it doesn't work with non-manifold meshes (see T82637).
+ * Use #ED_uvedit_pack_islands_multi for a more general solution.
+ *
+ * TODO: remove this function, in favor of #ED_uvedit_pack_islands_multi.
+ */
 static void uvedit_pack_islands_multi(const Scene *scene,
                                       Object **objects,
                                       const uint objects_len,
@@ -999,7 +1005,6 @@ static int pack_islands_exec(bContext *C, wmOperator *op)
   };
 
   bool rotate = RNA_boolean_get(op->ptr, "rotate");
-  bool ignore_pinned = false;
 
   uint objects_len = 0;
   Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(
@@ -1017,7 +1022,16 @@ static int pack_islands_exec(bContext *C, wmOperator *op)
     RNA_float_set(op->ptr, "margin", scene->toolsettings->uvcalc_margin);
   }
 
-  uvedit_pack_islands_multi(scene, objects, objects_len, &options, rotate, ignore_pinned);
+  ED_uvedit_pack_islands_multi(scene,
+                               objects,
+                               objects_len,
+                               &(struct UVPackIsland_Params){
+                                   .rotate = rotate,
+                                   .rotate_align_axis = -1,
+                                   .only_selected_uvs = true,
+                                   .only_selected_faces = true,
+                                   .correct_aspect = true,
+                               });
 
   MEM_freeN(objects);
 
@@ -2149,20 +2163,19 @@ static int smart_project_exec(bContext *C, wmOperator *op)
   if (object_changed_len > 0) {
 
     scene->toolsettings->uvcalc_margin = island_margin;
-    const UnwrapOptions options = {
-        .topology_from_uvs = true,
-        /* Even though the islands are defined by UV's,
-         * split them by seams so users have control over the islands. */
-        .topology_from_uvs_use_seams = true,
-
-        .only_selected_faces = true,
-        .only_selected_uvs = false,
-        .fill_holes = true,
-        .correct_aspect = false,
-    };
 
     /* Depsgraph refresh functions are called here. */
-    uvedit_pack_islands_multi(scene, objects_changed, object_changed_len, &options, true, false);
+    ED_uvedit_pack_islands_multi(scene,
+                                 objects_changed,
+                                 object_changed_len,
+                                 &(struct UVPackIsland_Params){
+                                     .rotate = true,
+                                     /* We could make this optional. */
+                                     .rotate_align_axis = 1,
+                                     .only_selected_faces = true,
+                                     .correct_aspect = true,
+                                 });
+
     uv_map_clip_correct_multi(objects_changed, object_changed_len, op);
   }