Multi-Objects: UV_OT_remove_doubles
authorAlan <Al@AlanTroth.me.uk>
Wed, 5 Sep 2018 20:33:07 +0000 (17:33 -0300)
committerDalai Felinto <dfelinto@gmail.com>
Wed, 5 Sep 2018 21:48:42 +0000 (18:48 -0300)
Use kdtree for doubles (old standing TODO for this operator).

Small changes from reviewer (Dalai Felinto):
* Code style ({ is in a new line only if it is a two-line if).
* Skip objetcs loops when we know for sure nothing is selected (or all is)

https://developer.blender.org/D3441

source/blender/editors/uvedit/uvedit_ops.c

index 8bcafebcdfef16d897084008c6aeee47f799c13d..b6b5e75b104a90a993d7752074f95893f412c769 100644 (file)
@@ -52,6 +52,7 @@
 #include "BLI_lasso_2d.h"
 #include "BLI_blenlib.h"
 #include "BLI_array.h"
+#include "BLI_kdtree.h"
 
 #include "BLT_translation.h"
 
@@ -1782,149 +1783,275 @@ static void UV_OT_align(wmOperatorType *ot)
 /** \name Remove Doubles Operator
  * \{ */
 
-typedef struct UVvert {
-       MLoopUV *uv_loop;
-       bool weld;
-} UVvert;
-
-static int uv_remove_doubles_exec(bContext *C, wmOperator *op)
+static int uv_remove_doubles_to_selected(bContext *C, wmOperator *op)
 {
+       Scene *scene = CTX_data_scene(C);
+       ViewLayer *view_layer = CTX_data_view_layer(C);
+       SpaceImage *sima = CTX_wm_space_image(C);
+       Image *ima = CTX_data_edit_image(C);
+       ToolSettings *ts = scene->toolsettings;
+
        const float threshold = RNA_float_get(op->ptr, "threshold");
-       const bool use_unselected = RNA_boolean_get(op->ptr, "use_unselected");
+       const bool synced_selection = (ts->uv_flag & UV_SYNC_SELECTION) != 0;
 
-       SpaceImage *sima;
-       Scene *scene;
-       Object *obedit = CTX_data_edit_object(C);
-       BMEditMesh *em = BKE_editmesh_from_object(obedit);
-       Image *ima;
-       int uv_a_index;
-       int uv_b_index;
-       float *uv_a;
-       const float *uv_b;
+       uint objects_len = 0;
+       Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(view_layer, &objects_len);
 
-       BMIter iter, liter;
-       BMFace *efa;
-       BMLoop *l;
+       bool *changed = MEM_callocN(sizeof(bool) * objects_len, "uv_remove_doubles_selected.changed");
 
-       const int cd_loop_uv_offset  = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+       /* Maximum index of an objects[i]'s MLoopUVs in MLoopUV_arr.
+        * It helps find which MLoopUV in *MLoopUV_arr belongs to which object. */
+       uint *ob_mloopuv_max_idx = MEM_callocN(sizeof(uint) * objects_len,
+                                              "uv_remove_doubles_selected.ob_mloopuv_max_idx");
 
-       sima = CTX_wm_space_image(C);
-       scene = CTX_data_scene(C);
-       ima = CTX_data_edit_image(C);
+       /* Calculate max possible number of kdtree nodes. */
+       int uv_maxlen = 0;
+       for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+               Object *obedit = objects[ob_index];
+               BMEditMesh *em = BKE_editmesh_from_object(obedit);
 
-       if (use_unselected == false) {
-               UVvert *vert_arr = NULL;
-               BLI_array_declare(vert_arr);
-               MLoopUV **loop_arr = NULL;
-               BLI_array_declare(loop_arr);
+               if (synced_selection && (em->bm->totvertsel == 0)) {
+                       continue;
+               }
 
-               /* TODO, use kd-tree as with MESH_OT_remove_doubles, this isn't optimal */
-               BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
-                       if (!uvedit_face_visible_test(scene, obedit, ima, efa))
+               uv_maxlen += em->bm->totloop;
+       }
+
+       KDTree *tree = BLI_kdtree_new(uv_maxlen);
+
+       int *duplicates = NULL;
+       BLI_array_declare(duplicates);
+
+       MLoopUV **mloopuv_arr = NULL;
+       BLI_array_declare(mloopuv_arr);
+
+       int mloopuv_count = 0;  /* Also used for *duplicates count. */
+
+       float uvw[3];
+       for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+               BMIter iter, liter;
+               BMFace *efa;
+               BMLoop *l;
+               Object *obedit = objects[ob_index];
+               BMEditMesh *em = BKE_editmesh_from_object(obedit);
+
+               if (synced_selection && (em->bm->totvertsel == 0)) {
+                       continue;
+               }
+
+               const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+
+               BM_ITER_MESH(efa, &iter, em->bm, BM_FACES_OF_MESH) {
+                       if (!uvedit_face_visible_test(scene, obedit, ima, efa)) {
                                continue;
+                       }
 
-                       BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
+                       BM_ITER_ELEM(l, &liter, efa, BM_LOOPS_OF_FACE) {
                                if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
                                        MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
-                                       UVvert vert;
-                                       vert.uv_loop = luv;
-                                       vert.weld = false;
-                                       BLI_array_append(vert_arr, vert);
+                                       copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f);
+                                       BLI_kdtree_insert(tree, mloopuv_count, uvw);
+                                       BLI_array_append(duplicates, -1);
+                                       BLI_array_append(mloopuv_arr, luv);
+                                       mloopuv_count++;
                                }
+                       }
+               }
 
+               ob_mloopuv_max_idx[ob_index] = mloopuv_count - 1;
+       }
+
+       BLI_kdtree_balance(tree);
+       int found_duplicates = BLI_kdtree_calc_duplicates_fast(tree, threshold, false, duplicates);
+
+       if (found_duplicates > 0) {
+               /* Calculate average uv for duplicates. */
+               int *uv_duplicate_count = MEM_callocN(sizeof(int) * mloopuv_count,
+                                                     "uv_remove_doubles_selected.uv_duplicate_count");
+               for (int i = 0; i < mloopuv_count; i++) {
+                       if (duplicates[i] == -1) {              /* If doesn't reference another */
+                               uv_duplicate_count[i]++;        /* self */
+                               continue;
+                       }
+
+                       if (duplicates[i] != i) {
+                               /* If not self then accumulate uv for averaging.
+                                * Self uv is already present in accumulator */
+                               add_v2_v2(mloopuv_arr[duplicates[i]]->uv, mloopuv_arr[i]->uv);
                        }
+                       uv_duplicate_count[duplicates[i]]++;
                }
 
-               for (uv_a_index = 0; uv_a_index < BLI_array_len(vert_arr); uv_a_index++) {
-                       if (vert_arr[uv_a_index].weld == false) {
-                               float uv_min[2];
-                               float uv_max[2];
+               for (int i = 0; i < mloopuv_count; i++) {
+                       if (uv_duplicate_count[i] < 2) {
+                               continue;
+                       }
 
-                               BLI_array_clear(loop_arr);
-                               BLI_array_append(loop_arr, vert_arr[uv_a_index].uv_loop);
+                       mul_v2_fl(mloopuv_arr[i]->uv, 1.0f/(float)uv_duplicate_count[i]);
+               }
+               MEM_freeN(uv_duplicate_count);
 
-                               uv_a = vert_arr[uv_a_index].uv_loop->uv;
+               /* Update duplicated uvs. */
+               uint ob_index = 0;
+               for (int i = 0; i < mloopuv_count; i++) {
+                       /* Make sure we know which object owns the MLoopUV at this index.
+                        * Remember that in some cases the object will have no loop uv,
+                        * thus we need the while loop, and not simply an if check. */
+                       while (ob_mloopuv_max_idx[ob_index] < i) {
+                               ob_index++;
+                       }
 
-                               copy_v2_v2(uv_max, uv_a);
-                               copy_v2_v2(uv_min, uv_a);
+                       if (duplicates[i] == -1) {
+                               continue;
+                       }
 
-                               vert_arr[uv_a_index].weld = true;
-                               for (uv_b_index = uv_a_index + 1; uv_b_index < BLI_array_len(vert_arr); uv_b_index++) {
-                                       uv_b = vert_arr[uv_b_index].uv_loop->uv;
-                                       if ((vert_arr[uv_b_index].weld == false) &&
-                                           (len_manhattan_v2v2(uv_a, uv_b) < threshold))
-                                       {
-                                               minmax_v2v2_v2(uv_min, uv_max, uv_b);
-                                               BLI_array_append(loop_arr, vert_arr[uv_b_index].uv_loop);
-                                               vert_arr[uv_b_index].weld = true;
-                                       }
-                               }
-                               if (BLI_array_len(loop_arr)) {
-                                       float uv_mid[2];
-                                       mid_v2_v2v2(uv_mid, uv_min, uv_max);
-                                       for (uv_b_index = 0; uv_b_index < BLI_array_len(loop_arr); uv_b_index++) {
-                                               copy_v2_v2(loop_arr[uv_b_index]->uv, uv_mid);
-                                       }
-                               }
+                       copy_v2_v2(mloopuv_arr[i]->uv, mloopuv_arr[duplicates[i]]->uv);
+                       changed[ob_index] = true;
+               }
+
+               for (ob_index = 0; ob_index < objects_len; ob_index++) {
+                       if (changed[ob_index]) {
+                               Object *obedit = objects[ob_index];
+                               uvedit_live_unwrap_update(sima, scene, obedit);
+                               DEG_id_tag_update(obedit->data, 0);
+                               WM_event_add_notifier(C, NC_GEOM | ND_DATA, obedit->data);
                        }
                }
+       }
+
+       BLI_kdtree_free(tree);
+       BLI_array_free(mloopuv_arr);
+       BLI_array_free(duplicates);
+       MEM_freeN(changed);
+       MEM_freeN(objects);
+       MEM_freeN(ob_mloopuv_max_idx);
+
+       return OPERATOR_FINISHED;
+}
+
+static int uv_remove_doubles_to_unselected(bContext *C, wmOperator *op)
+{
+       Scene *scene = CTX_data_scene(C);
+       ViewLayer *view_layer = CTX_data_view_layer(C);
+       SpaceImage *sima = CTX_wm_space_image(C);
+       Image *ima = CTX_data_edit_image(C);
+       ToolSettings *ts = scene->toolsettings;
+
+       const float threshold = RNA_float_get(op->ptr, "threshold");
+       const bool synced_selection = (ts->uv_flag & UV_SYNC_SELECTION) != 0;
 
-               BLI_array_free(vert_arr);
-               BLI_array_free(loop_arr);
+       uint objects_len = 0;
+       Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(view_layer, &objects_len);
+
+       /* Calculate max possible number of kdtree nodes. */
+       int uv_maxlen = 0;
+       for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+               Object *obedit = objects[ob_index];
+               BMEditMesh *em = BKE_editmesh_from_object(obedit);
+               uv_maxlen += em->bm->totloop;
        }
-       else {
-               /* selected -> unselected
-                *
-                * No need to use 'UVvert' here */
-               MLoopUV **loop_arr = NULL;
-               BLI_array_declare(loop_arr);
-               MLoopUV **loop_arr_unselected = NULL;
-               BLI_array_declare(loop_arr_unselected);
 
-               BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
-                       if (!uvedit_face_visible_test(scene, obedit, ima, efa))
+       KDTree *tree = BLI_kdtree_new(uv_maxlen);
+
+       MLoopUV **mloopuv_arr = NULL;
+       BLI_array_declare(mloopuv_arr);
+
+       int mloopuv_count = 0;
+
+       float uvw[3];
+       /* Add visible non-selected uvs to tree */
+       for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+               BMIter iter, liter;
+               BMFace *efa;
+               BMLoop *l;
+               Object *obedit = objects[ob_index];
+               BMEditMesh *em = BKE_editmesh_from_object(obedit);
+
+               if (synced_selection && (em->bm->totvertsel == em->bm->totvert)) {
+                       continue;
+               }
+
+               const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+
+               BM_ITER_MESH(efa, &iter, em->bm, BM_FACES_OF_MESH) {
+                       if (!uvedit_face_visible_test(scene, obedit, ima, efa)) {
                                continue;
+                       }
 
-                       BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
-                               MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
-                               if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
-                                       BLI_array_append(loop_arr, luv);
-                               }
-                               else {
-                                       BLI_array_append(loop_arr_unselected, luv);
+                       BM_ITER_ELEM(l, &liter, efa, BM_LOOPS_OF_FACE) {
+                               if (!uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
+                                       MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
+                                       copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f);
+                                       BLI_kdtree_insert(tree, mloopuv_count, uvw);
+                                       BLI_array_append(mloopuv_arr, luv);
+                                       mloopuv_count++;
                                }
                        }
                }
+       }
 
-               for (uv_a_index = 0; uv_a_index < BLI_array_len(loop_arr); uv_a_index++) {
-                       float dist_best = FLT_MAX, dist;
-                       const float *uv_best = NULL;
+       BLI_kdtree_balance(tree);
 
-                       uv_a = loop_arr[uv_a_index]->uv;
-                       for (uv_b_index = 0; uv_b_index < BLI_array_len(loop_arr_unselected); uv_b_index++) {
-                               uv_b = loop_arr_unselected[uv_b_index]->uv;
-                               dist = len_manhattan_v2v2(uv_a, uv_b);
-                               if ((dist < threshold) && (dist < dist_best)) {
-                                       uv_best = uv_b;
-                                       dist_best = dist;
-                               }
+       /* For each selected uv, find duplicate non selected uv. */
+       for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
+               BMIter iter, liter;
+               BMFace *efa;
+               BMLoop *l;
+               bool changed = false;
+               Object *obedit = objects[ob_index];
+               BMEditMesh *em = BKE_editmesh_from_object(obedit);
+
+               if (synced_selection && (em->bm->totvertsel == 0)) {
+                       continue;
+               }
+
+               const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);
+
+               BM_ITER_MESH(efa, &iter, em->bm, BM_FACES_OF_MESH) {
+                       if (!uvedit_face_visible_test(scene, obedit, ima, efa)) {
+                               continue;
                        }
-                       if (uv_best) {
-                               copy_v2_v2(uv_a, uv_best);
+
+                       BM_ITER_ELEM(l, &liter, efa, BM_LOOPS_OF_FACE) {
+                               if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) {
+                                       MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
+                                       copy_v3_fl3(uvw, luv->uv[0], luv->uv[1], 0.0f);
+
+                                       KDTreeNearest nearest;
+                                       const int i = BLI_kdtree_find_nearest(tree, uvw, &nearest);
+
+                                       if (i != -1 && nearest.dist < threshold) {
+                                               copy_v2_v2(luv->uv, mloopuv_arr[i]->uv);
+                                               changed = true;
+                                       }
+                               }
                        }
                }
 
-               BLI_array_free(loop_arr);
-               BLI_array_free(loop_arr_unselected);
+               if (changed) {
+                       uvedit_live_unwrap_update(sima, scene, obedit);
+                       DEG_id_tag_update(obedit->data, 0);
+                       WM_event_add_notifier(C, NC_GEOM | ND_DATA, obedit->data);
+               }
        }
 
-       uvedit_live_unwrap_update(sima, scene, obedit);
-       DEG_id_tag_update(obedit->data, 0);
-       WM_event_add_notifier(C, NC_GEOM | ND_DATA, obedit->data);
+       BLI_kdtree_free(tree);
+       BLI_array_free(mloopuv_arr);
+       MEM_freeN(objects);
 
        return OPERATOR_FINISHED;
 }
 
+static int uv_remove_doubles_exec(bContext *C, wmOperator *op)
+{
+       if (RNA_boolean_get(op->ptr, "use_unselected")) {
+               return uv_remove_doubles_to_unselected(C, op);
+       }
+       else {
+               return uv_remove_doubles_to_selected(C, op);
+       }
+}
+
 static void UV_OT_remove_doubles(wmOperatorType *ot)
 {
        /* identifiers */