Apply random selection precisely for curves, lattices & objects

This patch is part of: T87228.
Support accurate random selection for:

- CURVE_OT_select_random
- LATTICE_OT_select_random
- OBJECT_OT_select_random

Ref D11685

3 files changed, 101 insertions, 61 deletions

diff --git a/source/blender/editors/curve/editcurve_select.c b/source/blender/editors/curve/editcurve_select.c
index e1dc2ec30ca..35e102d60de 100644
--- a/source/blender/editors/curve/editcurve_select.c
+++ b/source/blender/editors/curve/editcurve_select.c
@@ -1200,45 +1200,6 @@ void CURVE_OT_select_less(wmOperatorType *ot)
 
 /********************** select random *********************/
 
-static void curve_select_random(ListBase *editnurb, float randfac, int seed, bool select)
-{
-  BezTriple *bezt;
-  BPoint *bp;
-  int a;
-
-  RNG *rng = BLI_rng_new_srandom(seed);
-
-  LISTBASE_FOREACH (Nurb *, nu, editnurb) {
-    if (nu->type == CU_BEZIER) {
-      bezt = nu->bezt;
-      a = nu->pntsu;
-      while (a--) {
-        if (!bezt->hide) {
-          if (BLI_rng_get_float(rng) < randfac) {
-            select_beztriple(bezt, select, SELECT, VISIBLE);
-          }
-        }
-        bezt++;
-      }
-    }
-    else {
-      bp = nu->bp;
-      a = nu->pntsu * nu->pntsv;
-
-      while (a--) {
-        if (!bp->hide) {
-          if (BLI_rng_get_float(rng) < randfac) {
-            select_bpoint(bp, select, SELECT, VISIBLE);
-          }
-        }
-        bp++;
-      }
-    }
-  }
-
-  BLI_rng_free(rng);
-}
-
 static int curve_select_random_exec(bContext *C, wmOperator *op)
 {
   const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
@@ -1260,9 +1221,71 @@ static int curve_select_random_exec(bContext *C, wmOperator *op)
       seed_iter += BLI_ghashutil_strhash_p(obedit->id.name);
     }
 
-    curve_select_random(editnurb, randfac, seed_iter, select);
-    BKE_curve_nurb_vert_active_validate(obedit->data);
+    int totvert = 0;
+    LISTBASE_FOREACH (Nurb *, nu, editnurb) {
+      if (nu->type == CU_BEZIER) {
+        int a = nu->pntsu;
+        BezTriple *bezt = nu->bezt;
+        while (a--) {
+          if (!bezt->hide) {
+            totvert++;
+          }
+          bezt++;
+        }
+      }
+      else {
+        int a = nu->pntsu * nu->pntsv;
+        BPoint *bp = nu->bp;
+        while (a--) {
+          if (!bp->hide) {
+            totvert++;
+          }
+          bp++;
+        }
+      }
+    }
+
+    BLI_bitmap *verts_selection_mask = BLI_BITMAP_NEW(totvert, __func__);
+    const int count_select = totvert * randfac;
+    for (int i = 0; i < count_select; i++) {
+      BLI_BITMAP_SET(verts_selection_mask, i, true);
+    }
+    BLI_bitmap_randomize(verts_selection_mask, totvert, seed_iter);
 
+    int bit_index = 0;
+    LISTBASE_FOREACH (Nurb *, nu, editnurb) {
+      if (nu->type == CU_BEZIER) {
+        int a = nu->pntsu;
+        BezTriple *bezt = nu->bezt;
+
+        while (a--) {
+          if (!bezt->hide) {
+            if (BLI_BITMAP_TEST(verts_selection_mask, bit_index)) {
+              select_beztriple(bezt, select, SELECT, VISIBLE);
+            }
+            bit_index++;
+          }
+          bezt++;
+        }
+      }
+      else {
+        int a = nu->pntsu * nu->pntsv;
+        BPoint *bp = nu->bp;
+
+        while (a--) {
+          if (!bp->hide) {
+            if (BLI_BITMAP_TEST(verts_selection_mask, bit_index)) {
+              select_bpoint(bp, select, SELECT, VISIBLE);
+            }
+            bit_index++;
+          }
+          bp++;
+        }
+      }
+    }
+
+    MEM_freeN(verts_selection_mask);
+    BKE_curve_nurb_vert_active_validate(obedit->data);
     DEG_id_tag_update(obedit->data, ID_RECALC_SELECT);
     WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
   }
diff --git a/source/blender/editors/lattice/editlattice_select.c b/source/blender/editors/lattice/editlattice_select.c
index cb3f9a89e62..8d8e1e9f06a 100644
--- a/source/blender/editors/lattice/editlattice_select.c
+++ b/source/blender/editors/lattice/editlattice_select.c
@@ -108,9 +108,9 @@ bool ED_lattice_deselect_all_multi(struct bContext *C)
 
 static int lattice_select_random_exec(bContext *C, wmOperator *op)
 {
+  const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
   const float randfac = RNA_float_get(op->ptr, "ratio");
   const int seed = WM_operator_properties_select_random_seed_increment_get(op);
-  const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
 
   ViewLayer *view_layer = CTX_data_view_layer(C);
   uint objects_len = 0;
@@ -119,29 +119,36 @@ static int lattice_select_random_exec(bContext *C, wmOperator *op)
   for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
     Object *obedit = objects[ob_index];
     Lattice *lt = ((Lattice *)obedit->data)->editlatt->latt;
+    int seed_iter = seed;
 
-    RNG *rng = BLI_rng_new_srandom(seed);
+    /* This gives a consistent result regardless of object order. */
+    if (ob_index) {
+      seed_iter += BLI_ghashutil_strhash_p(obedit->id.name);
+    }
 
-    int tot;
-    BPoint *bp;
+    int a = lt->pntsu * lt->pntsv * lt->pntsw;
+    int elem_map_len = 0;
+    BPoint **elem_map = MEM_mallocN(sizeof(*elem_map) * a, __func__);
+    BPoint *bp = lt->def;
 
-    tot = lt->pntsu * lt->pntsv * lt->pntsw;
-    bp = lt->def;
-    while (tot--) {
+    while (a--) {
       if (!bp->hide) {
-        if (BLI_rng_get_float(rng) < randfac) {
-          bpoint_select_set(bp, select);
-        }
+        elem_map[elem_map_len++] = bp;
       }
       bp++;
     }
 
+    BLI_array_randomize(elem_map, sizeof(*elem_map), elem_map_len, seed_iter);
+    const int count_select = elem_map_len * randfac;
+    for (int i = 0; i < count_select; i++) {
+      bpoint_select_set(elem_map[i], select);
+    }
+    MEM_freeN(elem_map);
+
     if (select == false) {
       lt->actbp = LT_ACTBP_NONE;
     }
 
-    BLI_rng_free(rng);
-
     DEG_id_tag_update(obedit->data, ID_RECALC_SELECT);
     WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
   }
diff --git a/source/blender/editors/object/object_select.c b/source/blender/editors/object/object_select.c
index 2fcf432bf18..1a0c5a6a83f 100644
--- a/source/blender/editors/object/object_select.c
+++ b/source/blender/editors/object/object_select.c
@@ -26,6 +26,8 @@
 #include <stdlib.h>
 #include <string.h>
 
+#include "MEM_guardedalloc.h"
+
 #include "DNA_anim_types.h"
 #include "DNA_armature_types.h"
 #include "DNA_collection_types.h"
@@ -1454,20 +1456,28 @@ void OBJECT_OT_select_less(wmOperatorType *ot)
 
 static int object_select_random_exec(bContext *C, wmOperator *op)
 {
+  const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
   const float randfac = RNA_float_get(op->ptr, "ratio");
   const int seed = WM_operator_properties_select_random_seed_increment_get(op);
-  const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
 
-  RNG *rng = BLI_rng_new_srandom(seed);
+  ListBase ctx_data_list;
+  CTX_data_selectable_bases(C, &ctx_data_list);
+  const int tot = BLI_listbase_count(&ctx_data_list);
+  int elem_map_len = 0;
+  Base **elem_map = MEM_mallocN(sizeof(*elem_map) * tot, __func__);
 
-  CTX_DATA_BEGIN (C, Base *, base, selectable_bases) {
-    if (BLI_rng_get_float(rng) < randfac) {
-      ED_object_base_select(base, select);
-    }
+  CollectionPointerLink *ctx_link;
+  for (ctx_link = ctx_data_list.first; ctx_link; ctx_link = ctx_link->next) {
+    elem_map[elem_map_len++] = ctx_link->ptr.data;
   }
-  CTX_DATA_END;
+  BLI_freelistN(&ctx_data_list);
 
-  BLI_rng_free(rng);
+  BLI_array_randomize(elem_map, sizeof(*elem_map), elem_map_len, seed);
+  const int count_select = elem_map_len * randfac;
+  for (int i = 0; i < count_select; i++) {
+    ED_object_base_select(elem_map[i], select);
+  }
+  MEM_freeN(elem_map);
 
   Scene *scene = CTX_data_scene(C);
   DEG_id_tag_update(&scene->id, ID_RECALC_SELECT);