UV: port smart project from Python to C

Use C for faster operation on high poly models,
in my tests this gave ~27x speedup.

D8311 by @andreasterrius with edits.

1 files changed, 378 insertions, 7 deletions

diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index 6e11f4f5be9..2f30ef1caa6 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -35,7 +35,10 @@
 #include "DNA_scene_types.h"
 
 #include "BLI_alloca.h"
+#include "BLI_array.h"
+#include "BLI_linklist.h"
 #include "BLI_math.h"
+#include "BLI_memarena.h"
 #include "BLI_string.h"
 #include "BLI_utildefines.h"
 #include "BLI_uvproject.h"
@@ -1486,18 +1489,21 @@ static void correct_uv_aspect(Object *ob, BMEditMesh *em)
 /** \name UV Map Clip & Correct
  * \{ */
 
-static void uv_map_clip_correct_properties(wmOperatorType *ot)
+static void uv_map_clip_correct_properties_ex(wmOperatorType *ot, bool clip_to_bounds)
 {
   RNA_def_boolean(ot->srna,
                   "correct_aspect",
                   1,
                   "Correct Aspect",
                   "Map UVs taking image aspect ratio into account");
-  RNA_def_boolean(ot->srna,
-                  "clip_to_bounds",
-                  0,
-                  "Clip to Bounds",
-                  "Clip UV coordinates to bounds after unwrapping");
+  /* Optional, since not all unwrapping types need to be clipped. */
+  if (clip_to_bounds) {
+    RNA_def_boolean(ot->srna,
+                    "clip_to_bounds",
+                    0,
+                    "Clip to Bounds",
+                    "Clip UV coordinates to bounds after unwrapping");
+  }
   RNA_def_boolean(ot->srna,
                   "scale_to_bounds",
                   0,
@@ -1505,6 +1511,11 @@ static void uv_map_clip_correct_properties(wmOperatorType *ot)
                   "Scale UV coordinates to bounds after unwrapping");
 }
 
+static void uv_map_clip_correct_properties(wmOperatorType *ot)
+{
+  uv_map_clip_correct_properties_ex(ot, true);
+}
+
 static void uv_map_clip_correct_multi(Object **objects, uint objects_len, wmOperator *op)
 {
   BMFace *efa;
@@ -1513,7 +1524,8 @@ static void uv_map_clip_correct_multi(Object **objects, uint objects_len, wmOper
   MLoopUV *luv;
   float dx, dy, min[2], max[2];
   const bool correct_aspect = RNA_boolean_get(op->ptr, "correct_aspect");
-  const bool clip_to_bounds = RNA_boolean_get(op->ptr, "clip_to_bounds");
+  const bool clip_to_bounds = (RNA_struct_find_property(op->ptr, "clip_to_bounds") &&
+                               RNA_boolean_get(op->ptr, "clip_to_bounds"));
   const bool scale_to_bounds = RNA_boolean_get(op->ptr, "scale_to_bounds");
 
   INIT_MINMAX2(min, max);
@@ -1846,6 +1858,365 @@ void UV_OT_unwrap(wmOperatorType *ot)
 /** \} */
 
 /* -------------------------------------------------------------------- */
+/** \name Smart UV Project Operator
+ * \{ */
+
+/* Ignore all areas below this, as the UV's get zeroed. */
+static const float smart_uv_project_area_ignore = 1e-12f;
+
+typedef struct ThickFace {
+  float area;
+  BMFace *efa;
+} 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;
+
+  /* Ignore the area of small faces.
+   * Also, order checks so `!isfinite(...)` values are counted as zero area. */
+  if (!((tf_a->area > smart_uv_project_area_ignore) ||
+        (tf_b->area > smart_uv_project_area_ignore))) {
+    return 0;
+  }
+
+  if (tf_a->area < tf_b->area) {
+    return 1;
+  }
+  else if (tf_a->area > tf_b->area) {
+    return -1;
+  }
+  else {
+    return 0;
+  }
+}
+
+static uint smart_uv_project_calculate_project_normals(const ThickFace *thick_faces,
+                                                       const uint thick_faces_len,
+                                                       BMesh *bm,
+                                                       const float project_angle_limit_half_cos,
+                                                       const float project_angle_limit_cos,
+                                                       const float area_weight,
+                                                       float (**r_project_normal_array)[3])
+{
+  if (UNLIKELY(thick_faces_len == 0)) {
+    *r_project_normal_array = NULL;
+    return 0;
+  }
+
+  const float *project_normal = thick_faces[0].efa->no;
+
+  const ThickFace **project_thick_faces = NULL;
+  BLI_array_declare(project_thick_faces);
+
+  float(*project_normal_array)[3] = NULL;
+  BLI_array_declare(project_normal_array);
+
+  BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
+
+  while (true) {
+    for (int f_index = thick_faces_len - 1; f_index >= 0; f_index--) {
+      if (BM_elem_flag_test(thick_faces[f_index].efa, BM_ELEM_TAG)) {
+        continue;
+      }
+
+      if (dot_v3v3(thick_faces[f_index].efa->no, project_normal) > project_angle_limit_half_cos) {
+        BLI_array_append(project_thick_faces, &thick_faces[f_index]);
+        BM_elem_flag_set(thick_faces[f_index].efa, BM_ELEM_TAG, true);
+      }
+    }
+
+    float average_normal[3] = {0.0f, 0.0f, 0.0f};
+
+    if (area_weight <= 0.0f) {
+      for (int f_proj_index = 0; f_proj_index < BLI_array_len(project_thick_faces);
+           f_proj_index++) {
+        const ThickFace *tf = project_thick_faces[f_proj_index];
+        add_v3_v3(average_normal, tf->efa->no);
+      }
+    }
+    else if (area_weight >= 1.0f) {
+      for (int f_proj_index = 0; f_proj_index < BLI_array_len(project_thick_faces);
+           f_proj_index++) {
+        const ThickFace *tf = project_thick_faces[f_proj_index];
+        madd_v3_v3fl(average_normal, tf->efa->no, tf->area);
+      }
+    }
+    else {
+      for (int f_proj_index = 0; f_proj_index < BLI_array_len(project_thick_faces);
+           f_proj_index++) {
+        const ThickFace *tf = project_thick_faces[f_proj_index];
+        const float area_blend = (tf->area * area_weight) + (1.0f - area_weight);
+        madd_v3_v3fl(average_normal, tf->efa->no, area_blend);
+      }
+    }
+
+    /* Avoid NAN. */
+    if (normalize_v3(average_normal) != 0.0f) {
+      float(*normal)[3] = BLI_array_append_ret(project_normal_array);
+      copy_v3_v3(*normal, average_normal);
+    }
+
+    /* Find the most unique angle that points away from other normals. */
+    float anble_best = 1.0f;
+    uint angle_best_index = 0;
+
+    for (int f_index = thick_faces_len - 1; f_index >= 0; f_index--) {
+      if (BM_elem_flag_test(thick_faces[f_index].efa, BM_ELEM_TAG)) {
+        continue;
+      }
+
+      float angle_test = -1.0f;
+      for (int p_index = 0; p_index < BLI_array_len(project_normal_array); p_index++) {
+        angle_test = max_ff(angle_test,
+                            dot_v3v3(project_normal_array[p_index], thick_faces[f_index].efa->no));
+      }
+
+      if (angle_test < anble_best) {
+        anble_best = angle_test;
+        angle_best_index = f_index;
+      }
+    }
+
+    if (anble_best < project_angle_limit_cos) {
+      project_normal = thick_faces[angle_best_index].efa->no;
+      BLI_array_clear(project_thick_faces);
+      BLI_array_append(project_thick_faces, &thick_faces[angle_best_index]);
+      BM_elem_flag_enable(thick_faces[angle_best_index].efa, BM_ELEM_TAG);
+    }
+    else {
+      if (BLI_array_len(project_normal_array) >= 1) {
+        break;
+      }
+    }
+  }
+
+  BLI_array_free(project_thick_faces);
+  BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
+
+  *r_project_normal_array = project_normal_array;
+  return BLI_array_len(project_normal_array);
+}
+
+static int smart_project_exec(bContext *C, wmOperator *op)
+{
+  Scene *scene = CTX_data_scene(C);
+  ViewLayer *view_layer = CTX_data_view_layer(C);
+
+  /* May be NULL. */
+  View3D *v3d = CTX_wm_view3d(C);
+
+  const float project_angle_limit = RNA_float_get(op->ptr, "angle_limit");
+  const float island_margin = RNA_float_get(op->ptr, "island_margin");
+  const float area_weight = RNA_float_get(op->ptr, "area_weight");
+
+  const float project_angle_limit_cos = cosf(project_angle_limit);
+  const float project_angle_limit_half_cos = cosf(project_angle_limit / 2);
+
+  /* Memory arena for list links (cleared for each object). */
+  MemArena *arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
+
+  uint objects_len = 0;
+  Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(
+      view_layer, v3d, &objects_len);
+
+  Object **objects_changed = MEM_mallocN(sizeof(*objects_changed) * objects_len, __func__);
+  uint object_changed_len = 0;
+
+  BMFace *efa;
+  BMIter iter;
+  uint ob_index;
+
+  for (ob_index = 0; ob_index < objects_len; ob_index++) {
+    Object *obedit = objects[ob_index];
+    BMEditMesh *em = BKE_editmesh_from_object(obedit);
+    bool changed = false;
+
+    const uint cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+    ThickFace *thick_faces = MEM_mallocN(sizeof(*thick_faces) * em->bm->totface, __func__);
+
+    uint thick_faces_len = 0;
+    BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
+      if (!BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
+        continue;
+      }
+      thick_faces[thick_faces_len].area = BM_face_calc_area(efa);
+      thick_faces[thick_faces_len].efa = efa;
+      thick_faces_len++;
+    }
+
+    qsort(thick_faces, thick_faces_len, sizeof(ThickFace), smart_uv_project_thickface_area_cmp_fn);
+
+    /* Remove all zero area faces. */
+    while ((thick_faces_len > 0) &&
+           !(thick_faces[thick_faces_len - 1].area > smart_uv_project_area_ignore)) {
+
+      /* Zero UV's so they don't overlap with other faces being unwrapped. */
+      BMIter liter;
+      BMLoop *l;
+      BM_ITER_ELEM (l, &liter, thick_faces[thick_faces_len - 1].efa, BM_LOOPS_OF_FACE) {
+        MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
+        zero_v2(luv->uv);
+        changed = true;
+      }
+
+      thick_faces_len -= 1;
+    }
+
+    float(*project_normal_array)[3] = NULL;
+    int project_normals_len = smart_uv_project_calculate_project_normals(
+        thick_faces,
+        thick_faces_len,
+        em->bm,
+        project_angle_limit_half_cos,
+        project_angle_limit_cos,
+        area_weight,
+        &project_normal_array);
+
+    if (project_normals_len == 0) {
+      MEM_freeN(thick_faces);
+      BLI_assert(project_normal_array == NULL);
+      continue;
+    }
+
+    /* After finding projection vectors, we find the uv positions. */
+    LinkNode **thickface_project_groups = MEM_callocN(
+        sizeof(*thickface_project_groups) * project_normals_len, __func__);
+
+    BLI_memarena_clear(arena);
+
+    for (int f_index = thick_faces_len - 1; f_index >= 0; f_index--) {
+      const float *f_normal = thick_faces[f_index].efa->no;
+
+      float angle_best = dot_v3v3(f_normal, project_normal_array[0]);
+      uint angle_best_index = 0;
+
+      for (int p_index = 1; p_index < project_normals_len; p_index++) {
+        const float angle_test = dot_v3v3(f_normal, project_normal_array[p_index]);
+        if (angle_test > angle_best) {
+          angle_best = angle_test;
+          angle_best_index = p_index;
+        }
+      }
+
+      BLI_linklist_prepend_arena(
+          &thickface_project_groups[angle_best_index], &thick_faces[f_index], arena);
+    }
+
+    for (int p_index = 0; p_index < project_normals_len; p_index++) {
+      if (thickface_project_groups[p_index] == NULL) {
+        continue;
+      }
+
+      float axis_mat[3][3];
+      axis_dominant_v3_to_m3_negate(axis_mat, project_normal_array[p_index]);
+
+      for (LinkNode *list = thickface_project_groups[p_index]; list; list = list->next) {
+        ThickFace *tf = list->link;
+        BMIter liter;
+        BMLoop *l;
+        BM_ITER_ELEM (l, &liter, tf->efa, BM_LOOPS_OF_FACE) {
+          MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
+          mul_v2_m3v3(luv->uv, axis_mat, l->v->co);
+        }
+        changed = true;
+      }
+    }
+
+    MEM_freeN(thick_faces);
+    MEM_freeN(project_normal_array);
+
+    /* No need to free the lists in 'thickface_project_groups' values as the 'arena' is used. */
+    MEM_freeN(thickface_project_groups);
+
+    if (changed) {
+      objects_changed[object_changed_len] = objects[ob_index];
+      object_changed_len += 1;
+    }
+  }
+
+  BLI_memarena_free(arena);
+
+  MEM_freeN(objects);
+
+  /* Pack islands & Stretch to UV bounds */
+  if (object_changed_len > 0) {
+
+    scene->toolsettings->uvcalc_margin = island_margin;
+    const UnwrapOptions options = {
+        .topology_from_uvs = 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);
+    uv_map_clip_correct_multi(objects_changed, object_changed_len, op);
+  }
+
+  MEM_freeN(objects_changed);
+
+  return OPERATOR_FINISHED;
+}
+
+void UV_OT_smart_project(wmOperatorType *ot)
+{
+  PropertyRNA *prop;
+
+  /* identifiers */
+  ot->name = "Smart UV Project";
+  ot->idname = "UV_OT_smart_project";
+  ot->description = "Projection unwraps the selected faces of mesh objects";
+
+  ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+  /* api callbacks */
+  ot->exec = smart_project_exec;
+  ot->poll = ED_operator_uvmap;
+  ot->invoke = WM_operator_props_popup_confirm;
+
+  /* properties */
+  prop = RNA_def_float_rotation(ot->srna,
+                                "angle_limit",
+                                0,
+                                NULL,
+                                DEG2RADF(0.0f),
+                                DEG2RADF(90.0f),
+                                "Angle Limit",
+                                "Lower for more projection groups, higher for less distortion",
+                                DEG2RADF(0.0f),
+                                DEG2RADF(89.0f));
+  RNA_def_property_float_default(prop, DEG2RADF(66.0f));
+
+  RNA_def_float(ot->srna,
+                "island_margin",
+                0.0f,
+                0.0f,
+                1.0f,
+                "Island Margin",
+                "Margin to reduce bleed from adjacent islands",
+                0.0f,
+                1.0f);
+  RNA_def_float(ot->srna,
+                "area_weight",
+                0.0f,
+                0.0f,
+                1.0f,
+                "Area Weight",
+                "Weight projections vector by faces with larger areas",
+                0.0f,
+                1.0f);
+
+  uv_map_clip_correct_properties_ex(ot, false);
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
 /** \name Project UV From View Operator
  * \{ */