[Bf-blender-cvs] [c2256bf7f71] master: Fix T90782: add uv pack option to specify margin as a fraction
Chris Blackbourn
noreply at git.blender.org
Wed Oct 12 00:08:48 CEST 2022
Commit: c2256bf7f714bbd41388af3e184b3d84b496fbf3
Author: Chris Blackbourn
Date: Wed Oct 12 10:57:17 2022 +1300
Branches: master
https://developer.blender.org/rBc2256bf7f714bbd41388af3e184b3d84b496fbf3
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
===================================================================
M source/blender/editors/include/ED_uvedit.h
M source/blender/editors/uvedit/uvedit_islands.cc
M source/blender/editors/uvedit/uvedit_unwrap_ops.c
===================================================================
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 ¶ms)
+{
+ /* 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 ¶ms,
+ 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_ma
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list