Fix T90782: add uv pack option to specify margin as a fraction

A refactor of the margin calculation of UV packing, in anticipation
of multiple packing methods soon becoming available.

Three margin scaling methods are now available:

* "Add", Simple method, just add the margin. [0]
    (The default margin scale from Blender 2.8 and earlier.)
* "Scaled", Use scale of existing UVs to multiply margin.
    (The default from Blender 3.3+)
* "Fraction", a new (slow) method to precisely specify
    a fraction of the UV unit square for margin. [1]

The "fraction" code path implements a novel combined search / secant
root finding method which exploits domain knowledge to accelerate
convergence while remaining robust against bad input.

[0]: Resolves T85978
[1]: Resolves T90782

Differential Revision: https://developer.blender.org/D16121

3 files changed, 253 insertions, 67 deletions

diff --git a/source/blender/editors/include/ED_uvedit.h b/source/blender/editors/include/ED_uvedit.h
index b499ae0ce59..e485fd2b061 100644
--- a/source/blender/editors/include/ED_uvedit.h
+++ b/source/blender/editors/include/ED_uvedit.h
@@ -339,12 +339,20 @@ bool ED_uvedit_udim_params_from_image_space(const struct SpaceImage *sima,
                                             bool use_active,
                                             struct UVMapUDIM_Params *udim_params);
 
+typedef enum {
+  ED_UVPACK_MARGIN_SCALED = 0, /* Use scale of existing UVs to multiply margin. */
+  ED_UVPACK_MARGIN_ADD,        /* Just add the margin, ignoring any UV scale. */
+  ED_UVPACK_MARGIN_FRACTION,   /* Specify a precise fraction of final UV output. */
+} eUVPackIsland_MarginMethod;
+
 struct UVPackIsland_Params {
   uint rotate : 1;
   uint only_selected_uvs : 1;
   uint only_selected_faces : 1;
   uint use_seams : 1;
   uint correct_aspect : 1;
+  eUVPackIsland_MarginMethod margin_method; /* Which formula to use when scaling island margin. */
+  float margin;                             /* Additional space to add around each island. */
 };
 
 /**
diff --git a/source/blender/editors/uvedit/uvedit_islands.cc b/source/blender/editors/uvedit/uvedit_islands.cc
index 2648ec5e2f6..4009447ba7e 100644
--- a/source/blender/editors/uvedit/uvedit_islands.cc
+++ b/source/blender/editors/uvedit/uvedit_islands.cc
@@ -403,6 +403,203 @@ int bm_mesh_calc_uv_islands(const Scene *scene,
 
 /** \} */
 
+static float pack_islands_scale_margin(const blender::Vector<FaceIsland *> &island_vector,
+                                       BoxPack *box_array,
+                                       const float scale,
+                                       const float margin)
+{
+  for (const int index : island_vector.index_range()) {
+    FaceIsland *island = island_vector[index];
+    BoxPack *box = &box_array[index];
+    box->index = index;
+    box->w = BLI_rctf_size_x(&island->bounds_rect) * scale + 2 * margin;
+    box->h = BLI_rctf_size_y(&island->bounds_rect) * scale + 2 * margin;
+  }
+  float max_u, max_v;
+  BLI_box_pack_2d(box_array, island_vector.size(), &max_u, &max_v);
+  return max_ff(max_u, max_v);
+}
+
+static float pack_islands_margin_fraction(const blender::Vector<FaceIsland *> &island_vector,
+                                          BoxPack *box_array,
+                                          const float margin_fraction)
+{
+  /*
+   * Root finding using a combined search / modified-secant method.
+   * First, use a robust search procedure to bracket the root within a factor of 10.
+   * Then, use a modified-secant method to converge.
+   *
+   * This is a specialized solver using domain knowledge to accelerate convergence.
+   */
+
+  float scale_low = 0.0f;
+  float value_low = 0.0f;
+  float scale_high = 0.0f;
+  float value_high = 0.0f;
+  float scale_last = 0.0f;
+
+  /* Scaling smaller than `min_scale_roundoff` is unlikely to fit and
+   * will destroy information in existing UVs. */
+  float min_scale_roundoff = 1e-5f;
+
+  /* Certain inputs might have poor convergence properties.
+   * Use `max_iteration` to prevent an infinite loop. */
+  int max_iteration = 25;
+  for (int iteration = 0; iteration < max_iteration; iteration++) {
+    float scale = 1.0f;
+
+    if (iteration == 0) {
+      BLI_assert(iteration == 0);
+      BLI_assert(scale == 1.0f);
+      BLI_assert(scale_low == 0.0f);
+      BLI_assert(scale_high == 0.0f);
+    }
+    else if (scale_low == 0.0f) {
+      BLI_assert(scale_high > 0.0f);
+      /* Search mode, shrink layout until we can find a scale that fits. */
+      scale = scale_high * 0.1f;
+    }
+    else if (scale_high == 0.0f) {
+      BLI_assert(scale_low > 0.0f);
+      /* Search mode, grow layout until we can find a scale that doesn't fit. */
+      scale = scale_low * 10.0f;
+    }
+    else {
+      /* Bracket mode, use modified secant method to find root. */
+      BLI_assert(scale_low > 0.0f);
+      BLI_assert(scale_high > 0.0f);
+      BLI_assert(value_low <= 0.0f);
+      BLI_assert(value_high >= 0.0f);
+      if (scale_high < scale_low * 1.0001f) {
+        /* Convergence. */
+        break;
+      }
+
+      /* Secant method for area. */
+      scale = (sqrtf(scale_low) * value_high - sqrtf(scale_high) * value_low) /
+              (value_high - value_low);
+      scale = scale * scale;
+
+      if (iteration & 1) {
+        /* Modified binary-search to improve robustness. */
+        scale = sqrtf(scale * sqrtf(scale_low * scale_high));
+      }
+    }
+
+    scale = max_ff(scale, min_scale_roundoff);
+
+    /* Evaluate our `f`. */
+    scale_last = scale;
+    float max_uv = pack_islands_scale_margin(
+        island_vector, box_array, scale_last, margin_fraction);
+    float value = sqrtf(max_uv) - 1.0f;
+
+    if (value <= 0.0f) {
+      scale_low = scale;
+      value_low = value;
+    }
+    else {
+      scale_high = scale;
+      value_high = value;
+      if (scale == min_scale_roundoff) {
+        /* Unable to pack without damaging UVs. */
+        scale_low = scale;
+        break;
+      }
+    }
+  }
+
+  const bool flush = true;
+  if (flush) {
+    /* Write back best pack as a side-effect. First get best pack. */
+    if (scale_last != scale_low) {
+      scale_last = scale_low;
+      float max_uv = pack_islands_scale_margin(
+          island_vector, box_array, scale_last, margin_fraction);
+      UNUSED_VARS(max_uv);
+      /* TODO (?): `if (max_uv < 1.0f) { scale_last /= max_uv; }` */
+    }
+
+    /* Then expand FaceIslands by the correct amount. */
+    for (const int index : island_vector.index_range()) {
+      BoxPack *box = &box_array[index];
+      box->x /= scale_last;
+      box->y /= scale_last;
+      FaceIsland *island = island_vector[index];
+      BLI_rctf_pad(
+          &island->bounds_rect, margin_fraction / scale_last, margin_fraction / scale_last);
+    }
+  }
+  return scale_last;
+}
+
+static float calc_margin_from_aabb_length_sum(const blender::Vector<FaceIsland *> &island_vector,
+                                              const struct UVPackIsland_Params &params)
+{
+  /* Logic matches behavior from #GEO_uv_parametrizer_pack.
+   * Attempt to give predictable results
+   * not dependent on current UV scale by using
+   * `aabb_length_sum` (was "`area`") to multiply
+   * the margin by the length (was "area").
+   */
+  double aabb_length_sum = 0.0f;
+  for (FaceIsland *island : island_vector) {
+    float w = BLI_rctf_size_x(&island->bounds_rect);
+    float h = BLI_rctf_size_y(&island->bounds_rect);
+    aabb_length_sum += sqrtf(w * h);
+  }
+  return params.margin * aabb_length_sum * 0.1f;
+}
+
+static BoxPack *pack_islands_params(const blender::Vector<FaceIsland *> &island_vector,
+                                    const struct UVPackIsland_Params &params,
+                                    float r_scale[2])
+{
+  BoxPack *box_array = static_cast<BoxPack *>(
+      MEM_mallocN(sizeof(*box_array) * island_vector.size(), __func__));
+
+  if (params.margin == 0.0f) {
+    /* Special case for zero margin. Margin_method is ignored as all formulas give same result. */
+    const float max_uv = pack_islands_scale_margin(island_vector, box_array, 1.0f, 0.0f);
+    r_scale[0] = 1.0f / max_uv;
+    r_scale[1] = r_scale[0];
+    return box_array;
+  }
+
+  if (params.margin_method == ED_UVPACK_MARGIN_FRACTION) {
+    /* Uses a line search on scale. ~10x slower than other method. */
+    const float scale = pack_islands_margin_fraction(island_vector, box_array, params.margin);
+    r_scale[0] = scale;
+    r_scale[1] = scale;
+    /* pack_islands_margin_fraction will pad FaceIslands, return early. */
+    return box_array;
+  }
+
+  float margin = params.margin;
+  switch (params.margin_method) {
+    case ED_UVPACK_MARGIN_ADD:    /* Default for Blender 2.8 and earlier. */
+      break;                      /* Nothing to do. */
+    case ED_UVPACK_MARGIN_SCALED: /* Default for Blender 3.3 and later. */
+      margin = calc_margin_from_aabb_length_sum(island_vector, params);
+      break;
+    case ED_UVPACK_MARGIN_FRACTION: /* Added as an option in Blender 3.4. */
+      BLI_assert_unreachable();     /* Handled above. */
+      break;
+    default:
+      BLI_assert_unreachable();
+  }
+
+  const float max_uv = pack_islands_scale_margin(island_vector, box_array, 1.0f, margin);
+  r_scale[0] = 1.0f / max_uv;
+  r_scale[1] = r_scale[0];
+
+  for (int index = 0; index < island_vector.size(); index++) {
+    FaceIsland *island = island_vector[index];
+    BLI_rctf_pad(&island->bounds_rect, margin, margin);
+  }
+  return box_array;
+}
+
 /* -------------------------------------------------------------------- */
 /** \name Public UV Island Packing
  *
@@ -455,19 +652,12 @@ void ED_uvedit_pack_islands_multi(const Scene *scene,
     return;
   }
 
-  float margin = scene->toolsettings->uvcalc_margin;
-  double area = 0.0f;
-
-  BoxPack *boxarray = static_cast<BoxPack *>(
-      MEM_mallocN(sizeof(*boxarray) * island_vector.size(), __func__));
-
   /* Coordinates of bounding box containing all selected UVs. */
   float selection_min_co[2], selection_max_co[2];
   INIT_MINMAX2(selection_min_co, selection_max_co);
 
   for (int index = 0; index < island_vector.size(); index++) {
     FaceIsland *island = island_vector[index];
-
     /* Skip calculation if using specified UDIM option. */
     if (udim_params && (udim_params->use_target_udim == false)) {
       float bounds_min[2], bounds_max[2];
@@ -489,17 +679,6 @@ void ED_uvedit_pack_islands_multi(const Scene *scene,
 
     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);
-
-    if (margin > 0.0f) {
-      area += double(sqrtf(box->w * box->h));
-    }
   }
 
   /* Center of bounding box containing all selected UVs. */
@@ -509,28 +688,8 @@ void ED_uvedit_pack_islands_multi(const Scene *scene,
     selection_center[1] = (selection_min_co[1] + selection_max_co[1]) / 2.0f;
   }
 
-  if (margin > 0.0f) {
-    /* Logic matches behavior from #GEO_uv_parametrizer_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_vector.size(); i++) {
-      FaceIsland *island = island_vector[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_vector.size(), &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]};
+  float scale[2] = {1.0f, 1.0f};
+  BoxPack *box_array = pack_islands_params(island_vector, *params, scale);
 
   /* Tile offset. */
   float base_offset[2] = {0.0f, 0.0f};
@@ -580,14 +739,14 @@ void ED_uvedit_pack_islands_multi(const Scene *scene,
   }
 
   for (int i = 0; i < island_vector.size(); i++) {
-    FaceIsland *island = island_vector[boxarray[i].index];
+    FaceIsland *island = island_vector[box_array[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) + base_offset[0],
-        ((boxarray[i].y * scale[1]) - island->bounds_rect.ymin) + base_offset[1],
+        ((box_array[i].x * scale[0]) - island->bounds_rect.xmin) + base_offset[0],
+        ((box_array[i].y * scale[1]) - island->bounds_rect.ymin) + base_offset[1],
     };
     for (int j = 0; j < island->faces_len; j++) {
       BMFace *efa = island->faces[j];
@@ -607,7 +766,7 @@ void ED_uvedit_pack_islands_multi(const Scene *scene,
     MEM_freeN(island);
   }
 
-  MEM_freeN(boxarray);
+  MEM_freeN(box_array);
 }
 
 /** \} */
diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index 661a2a1b05b..cedca88de6a 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -1125,7 +1125,6 @@ static int pack_islands_exec(bContext *C, wmOperator *op)
   }
 
   /* RNA props */
-  const bool rotate = RNA_boolean_get(op->ptr, "rotate");
   const int udim_source = RNA_enum_get(op->ptr, "udim_source");
   if (RNA_struct_property_is_set(op->ptr, "margin")) {
     scene->toolsettings->uvcalc_margin = RNA_float_get(op->ptr, "margin");
@@ -1139,21 +1138,36 @@ static int pack_islands_exec(bContext *C, wmOperator *op)
   const bool use_udim_params = ED_uvedit_udim_params_from_image_space(
       sima, use_active, &udim_params);
 
-  ED_uvedit_pack_islands_multi(scene,
-                               objects,
-                               objects_len,
-                               use_udim_params ? &udim_params : NULL,
-                               &(struct UVPackIsland_Params){
-                                   .rotate = rotate,
-                                   .only_selected_uvs = true,
-                                   .only_selected_faces = true,
-                                   .correct_aspect = true,
-                               });
+  struct UVPackIsland_Params params = {
+      .rotate = RNA_boolean_get(op->ptr, "rotate"),
+      .only_selected_uvs = true,
+      .only_selected_faces = true,
+      .correct_aspect = true,
+      .margin_method = RNA_enum_get(op->ptr, "margin_method"),
+      .margin = RNA_float_get(op->ptr, "margin"),
+  };
+  ED_uvedit_pack_islands_multi(
+      scene, objects, objects_len, use_udim_params ? &udim_params : NULL, &params);
 
   MEM_freeN(objects);
   return OPERATOR_FINISHED;
 }
 
+const EnumPropertyItem pack_margin_method[] = {
+    {ED_UVPACK_MARGIN_SCALED,
+     "SCALED",
+     0,
+     "Scaled",
+     "Use scale of existing UVs to multiply margin"},
+    {ED_UVPACK_MARGIN_ADD, "ADD", 0, "Add", "Just add the margin, ignoring any UV scale"},
+    {ED_UVPACK_MARGIN_FRACTION,
+     "FRACTION",
+     0,
+     "Fraction",
+     "Specify a precise fraction of final UV output"},
+    {0, NULL, 0, NULL, NULL},
+};
+
 void UV_OT_pack_islands(wmOperatorType *ot)
 {
   static const EnumPropertyItem pack_target[] = {
@@ -1180,6 +1194,8 @@ void UV_OT_pack_islands(wmOperatorType *ot)
   /* properties */
   RNA_def_enum(ot->srna, "udim_source", pack_target, PACK_UDIM_SRC_CLOSEST, "Pack to", "");
   RNA_def_boolean(ot->srna, "rotate", true, "Rotate", "Rotate islands for best fit");
+  RNA_def_enum(
+      ot->srna, "margin_method", pack_margin_method, ED_UVPACK_MARGIN_SCALED, "Margin Method", "");
   RNA_def_float_factor(
       ot->srna, "margin", 0.001f, 0.0f, 1.0f, "Margin", "Space between islands", 0.0f, 1.0f);
 }
@@ -2098,6 +2114,8 @@ void UV_OT_unwrap(wmOperatorType *ot)
       0,
       "Use Subdivision Surface",
       "Map UVs taking vertex position after Subdivision Surface modifier has been applied");
+  RNA_def_enum(
+      ot->srna, "margin_method", pack_margin_method, ED_UVPACK_MARGIN_SCALED, "Margin Method", "");
   RNA_def_float_factor(
       ot->srna, "margin", 0.001f, 0.0f, 1.0f, "Margin", "Space between islands", 0.0f, 1.0f);
 }
@@ -2118,7 +2136,6 @@ typedef struct ThickFace {
 
 static int smart_uv_project_thickface_area_cmp_fn(const void *tf_a_p, const void *tf_b_p)
 {
-
   const ThickFace *tf_a = (ThickFace *)tf_a_p;
   const ThickFace *tf_b = (ThickFace *)tf_b_p;
 
@@ -2412,17 +2429,17 @@ static int smart_project_exec(bContext *C, wmOperator *op)
 
     /* Depsgraph refresh functions are called here. */
     const bool correct_aspect = RNA_boolean_get(op->ptr, "correct_aspect");
-    ED_uvedit_pack_islands_multi(scene,
-                                 objects_changed,
-                                 object_changed_len,
-                                 NULL,
-                                 &(struct UVPackIsland_Params){
-                                     .rotate = true,
-                                     .only_selected_uvs = only_selected_uvs,
-                                     .only_selected_faces = true,
-                                     .correct_aspect = correct_aspect,
-                                     .use_seams = true,
-                                 });
+
+    const struct UVPackIsland_Params params = {
+        .rotate = true,
+        .only_selected_uvs = only_selected_uvs,
+        .only_selected_faces = true,
+        .correct_aspect = correct_aspect,
+        .use_seams = true,
+        .margin_method = RNA_enum_get(op->ptr, "margin_method"),
+        .margin = RNA_float_get(op->ptr, "island_margin"),
+    };
+    ED_uvedit_pack_islands_multi(scene, objects_changed, object_changed_len, NULL, &params);
 
     /* #ED_uvedit_pack_islands_multi only supports `per_face_aspect = false`. */
     const bool per_face_aspect = false;
@@ -2464,6 +2481,8 @@ void UV_OT_smart_project(wmOperatorType *ot)
                                 DEG2RADF(89.0f));
   RNA_def_property_float_default(prop, DEG2RADF(66.0f));
 
+  RNA_def_enum(
+      ot->srna, "margin_method", pack_margin_method, ED_UVPACK_MARGIN_SCALED, "Margin Method", "");
   RNA_def_float(ot->srna,
                 "island_margin",
                 0.0f,