Fix T91253: Slow pose bone selection with many bones

Viewport cull bones during selection to avoid depth-picking
reading the depth buffer for bones that aren't in the viewport.

Files with thousands of bones could hang blender for seconds while
selecting. The issue could still happen with overlapping bones or when
zoomed out so all bones are under the cursor, however in practice this
rarely happens.

Now files with many bones select quickly.

Related changes include:

- Split `BKE_pchan_minmax` out of `BKE_pose_minmax`.
- Add `mat3_to_size_max_axis` to return the length of the largest
  axis (used for scaling the radius).

Reviewed By: sybren

Maniphest Tasks: T91253

Ref D13990

5 files changed, 218 insertions, 30 deletions

diff --git a/source/blender/blenkernel/BKE_armature.h b/source/blender/blenkernel/BKE_armature.h
index 12d8135ba55..ede300b19dd 100644
--- a/source/blender/blenkernel/BKE_armature.h
+++ b/source/blender/blenkernel/BKE_armature.h
@@ -163,6 +163,30 @@ void BKE_armature_transform(struct bArmature *arm, const float mat[4][4], bool d
 /* Bounding box. */
 struct BoundBox *BKE_armature_boundbox_get(struct Object *ob);
 
+/**
+ * Calculate the axis-aligned bounds of `pchan` in world-space,
+ * taking into account custom transform when set.
+ *
+ * `r_min` and `r_max` are expanded to fit `pchan` so the caller must initialize them
+ * (typically using #INIT_MINMAX).
+ *
+ * \note The bounds are calculated based on the head & tail of the bone
+ * or the custom object's bounds (if the bone uses a custom object).
+ * Visual elements such as the envelopes radius & bendy-bone spline segments are *not* included,
+ * making this not so useful for viewport culling.
+ */
+void BKE_pchan_minmax(const struct Object *ob,
+                      const struct bPoseChannel *pchan,
+                      float r_min[3],
+                      float r_max[3]);
+/**
+ * Calculate the axis aligned bounds of the pose of `ob` in world-space.
+
+ * `r_min` and `r_max` are expanded to fit `ob->pose` so the caller must initialize them
+ * (typically using #INIT_MINMAX).
+ *
+ * \note This uses #BKE_pchan_minmax, see its documentation for details on bounds calculation.
+ */
 bool BKE_pose_minmax(
     struct Object *ob, float r_min[3], float r_max[3], bool use_hidden, bool use_select);
 
diff --git a/source/blender/blenkernel/intern/armature.c b/source/blender/blenkernel/intern/armature.c
index 7feb9d08915..1a9f0a9130d 100644
--- a/source/blender/blenkernel/intern/armature.c
+++ b/source/blender/blenkernel/intern/armature.c
@@ -2679,6 +2679,35 @@ BoundBox *BKE_armature_boundbox_get(Object *ob)
   return ob->runtime.bb;
 }
 
+void BKE_pchan_minmax(const Object *ob, const bPoseChannel *pchan, float r_min[3], float r_max[3])
+{
+  const bArmature *arm = ob->data;
+  const bPoseChannel *pchan_tx = (pchan->custom && pchan->custom_tx) ? pchan->custom_tx : pchan;
+  const BoundBox *bb_custom = ((pchan->custom) && !(arm->flag & ARM_NO_CUSTOM)) ?
+                                  BKE_object_boundbox_get(pchan->custom) :
+                                  NULL;
+  if (bb_custom) {
+    float mat[4][4], smat[4][4], rmat[4][4], tmp[4][4];
+    scale_m4_fl(smat, PCHAN_CUSTOM_BONE_LENGTH(pchan));
+    rescale_m4(smat, pchan->custom_scale_xyz);
+    eulO_to_mat4(rmat, pchan->custom_rotation_euler, ROT_MODE_XYZ);
+    copy_m4_m4(tmp, pchan_tx->pose_mat);
+    translate_m4(tmp,
+                 pchan->custom_translation[0],
+                 pchan->custom_translation[1],
+                 pchan->custom_translation[2]);
+    mul_m4_series(mat, ob->obmat, tmp, rmat, smat);
+    BKE_boundbox_minmax(bb_custom, mat, r_min, r_max);
+  }
+  else {
+    float vec[3];
+    mul_v3_m4v3(vec, ob->obmat, pchan_tx->pose_head);
+    minmax_v3v3_v3(r_min, r_max, vec);
+    mul_v3_m4v3(vec, ob->obmat, pchan_tx->pose_tail);
+    minmax_v3v3_v3(r_min, r_max, vec);
+  }
+}
+
 bool BKE_pose_minmax(Object *ob, float r_min[3], float r_max[3], bool use_hidden, bool use_select)
 {
   bool changed = false;
@@ -2692,31 +2721,8 @@ bool BKE_pose_minmax(Object *ob, float r_min[3], float r_max[3], bool use_hidden
        *     (editarmature.c:2592)... Skip in this case too! */
       if (pchan->bone && (!((use_hidden == false) && (PBONE_VISIBLE(arm, pchan->bone) == false)) &&
                           !((use_select == true) && ((pchan->bone->flag & BONE_SELECTED) == 0)))) {
-        bPoseChannel *pchan_tx = (pchan->custom && pchan->custom_tx) ? pchan->custom_tx : pchan;
-        BoundBox *bb_custom = ((pchan->custom) && !(arm->flag & ARM_NO_CUSTOM)) ?
-                                  BKE_object_boundbox_get(pchan->custom) :
-                                  NULL;
-        if (bb_custom) {
-          float mat[4][4], smat[4][4], rmat[4][4], tmp[4][4];
-          scale_m4_fl(smat, PCHAN_CUSTOM_BONE_LENGTH(pchan));
-          rescale_m4(smat, pchan->custom_scale_xyz);
-          eulO_to_mat4(rmat, pchan->custom_rotation_euler, ROT_MODE_XYZ);
-          copy_m4_m4(tmp, pchan_tx->pose_mat);
-          translate_m4(tmp,
-                       pchan->custom_translation[0],
-                       pchan->custom_translation[1],
-                       pchan->custom_translation[2]);
-          mul_m4_series(mat, ob->obmat, tmp, rmat, smat);
-          BKE_boundbox_minmax(bb_custom, mat, r_min, r_max);
-        }
-        else {
-          float vec[3];
-          mul_v3_m4v3(vec, ob->obmat, pchan_tx->pose_head);
-          minmax_v3v3_v3(r_min, r_max, vec);
-          mul_v3_m4v3(vec, ob->obmat, pchan_tx->pose_tail);
-          minmax_v3v3_v3(r_min, r_max, vec);
-        }
 
+        BKE_pchan_minmax(ob, pchan, r_min, r_max);
         changed = true;
       }
     }
diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h
index 03b6ff25a4f..1dcc1c1df49 100644
--- a/source/blender/blenlib/BLI_math_matrix.h
+++ b/source/blender/blenlib/BLI_math_matrix.h
@@ -431,6 +431,20 @@ void mat3_to_size(float size[3], const float M[3][3]);
 void mat4_to_size(float size[3], const float M[4][4]);
 
 /**
+ * Return the largest scale on any axis, the equivalent of calling:
+ * \code{.c}
+ * mat3_to_size(size_v3, mat);
+ * size = size_v3[max_axis_v3(size_v3)];
+ * \endcode
+ * .. without 2x unnecessary `sqrtf` calls.
+ */
+float mat3_to_size_max_axis(const float M[3][3]);
+/**
+ * Only the first 3 axes are used.
+ */
+float mat4_to_size_max_axis(const float M[4][4]);
+
+/**
  * Extract scale factors from the matrix, with correction to ensure
  * exact volume in case of a sheared matrix.
  */
diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c
index f307672361b..9c719b12756 100644
--- a/source/blender/blenlib/intern/math_matrix.c
+++ b/source/blender/blenlib/intern/math_matrix.c
@@ -2144,6 +2144,16 @@ void mat4_to_size(float size[3], const float M[4][4])
   size[2] = len_v3(M[2]);
 }
 
+float mat3_to_size_max_axis(const float M[3][3])
+{
+  return sqrtf(max_fff(len_squared_v3(M[0]), len_squared_v3(M[1]), len_squared_v3(M[2])));
+}
+
+float mat4_to_size_max_axis(const float M[4][4])
+{
+  return sqrtf(max_fff(len_squared_v3(M[0]), len_squared_v3(M[1]), len_squared_v3(M[2])));
+}
+
 void mat4_to_size_fix_shear(float size[3], const float M[4][4])
 {
   mat4_to_size(size, M);
diff --git a/source/blender/draw/engines/overlay/overlay_armature.c b/source/blender/draw/engines/overlay/overlay_armature.c
index ccf8f9e0c36..5abebe2f32b 100644
--- a/source/blender/draw/engines/overlay/overlay_armature.c
+++ b/source/blender/draw/engines/overlay/overlay_armature.c
@@ -2038,6 +2038,126 @@ static void draw_bone_name(ArmatureDrawContext *ctx,
 /** \} */
 
 /* -------------------------------------------------------------------- */
+/** \name Pose Bone Culling
+ *
+ * Used for selection since drawing many bones can be slow, see: T91253.
+ *
+ * Bounding spheres are used with margins added to ensure bones are included.
+ * An added margin is needed because #BKE_pchan_minmax only returns the bounds
+ * of the bones head & tail which doesn't account for parts of the bone users may select
+ * (octahedral spheres or envelope radius for example).
+ * \{ */
+
+static void pchan_culling_calc_bsphere(const Object *ob,
+                                       const bPoseChannel *pchan,
+                                       BoundSphere *r_bsphere)
+{
+  float min[3], max[3];
+  INIT_MINMAX(min, max);
+  BKE_pchan_minmax(ob, pchan, min, max);
+  mid_v3_v3v3(r_bsphere->center, min, max);
+  r_bsphere->radius = len_v3v3(min, r_bsphere->center);
+}
+
+/**
+ * \return true when bounding sphere from `pchan` intersect the view.
+ * (same for other "test" functions defined here).
+ */
+static bool pchan_culling_test_simple(const DRWView *view,
+                                      const Object *ob,
+                                      const bPoseChannel *pchan)
+{
+  BoundSphere bsphere;
+  pchan_culling_calc_bsphere(ob, pchan, &bsphere);
+  return DRW_culling_sphere_test(view, &bsphere);
+}
+
+static bool pchan_culling_test_with_radius_scale(const DRWView *view,
+                                                 const Object *ob,
+                                                 const bPoseChannel *pchan,
+                                                 const float scale)
+{
+  BoundSphere bsphere;
+  pchan_culling_calc_bsphere(ob, pchan, &bsphere);
+  bsphere.radius *= scale;
+  return DRW_culling_sphere_test(view, &bsphere);
+}
+
+static bool pchan_culling_test_custom(const DRWView *view,
+                                      const Object *ob,
+                                      const bPoseChannel *pchan)
+{
+  /* For more aggressive culling the bounding box of the custom-object could be used. */
+  return pchan_culling_test_simple(view, ob, pchan);
+}
+
+static bool pchan_culling_test_wire(const DRWView *view,
+                                    const Object *ob,
+                                    const bPoseChannel *pchan)
+{
+  BLI_assert(((const bArmature *)ob->data)->drawtype == ARM_WIRE);
+  return pchan_culling_test_simple(view, ob, pchan);
+}
+
+static bool pchan_culling_test_line(const DRWView *view,
+                                    const Object *ob,
+                                    const bPoseChannel *pchan)
+{
+  BLI_assert(((const bArmature *)ob->data)->drawtype == ARM_LINE);
+  /* Account for the end-points, as the line end-points size is in pixels, this is a rough value.
+   * Since the end-points are small the difference between having any margin or not is unlikely
+   * to be noticeable. */
+  const float scale = 1.1f;
+  return pchan_culling_test_with_radius_scale(view, ob, pchan, scale);
+}
+
+static bool pchan_culling_test_envelope(const DRWView *view,
+                                        const Object *ob,
+                                        const bPoseChannel *pchan)
+{
+  const bArmature *arm = ob->data;
+  BLI_assert(arm->drawtype == ARM_ENVELOPE);
+  BoundSphere bsphere;
+  pchan_culling_calc_bsphere(ob, pchan, &bsphere);
+  bsphere.radius += max_ff(pchan->bone->rad_head, pchan->bone->rad_tail) *
+                    mat4_to_size_max_axis(ob->obmat) * mat4_to_size_max_axis(pchan->disp_mat);
+  return DRW_culling_sphere_test(view, &bsphere);
+}
+
+static bool pchan_culling_test_bbone(const DRWView *view,
+                                     const Object *ob,
+                                     const bPoseChannel *pchan)
+{
+  const bArmature *arm = ob->data;
+  BLI_assert(arm->drawtype == ARM_B_BONE);
+  const float ob_scale = mat4_to_size_max_axis(ob->obmat);
+  const Mat4 *bbones_mat = (const Mat4 *)pchan->draw_data->bbone_matrix;
+  for (int i = pchan->bone->segments; i--; bbones_mat++) {
+    BoundSphere bsphere;
+    float size[3];
+    mat4_to_size(size, bbones_mat->mat);
+    copy_v3_v3(bsphere.center, bbones_mat->mat[3]);
+    bsphere.radius = len_v3(size) * ob_scale;
+    if (DRW_culling_sphere_test(view, &bsphere)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+static bool pchan_culling_test_octohedral(const DRWView *view,
+                                          const Object *ob,
+                                          const bPoseChannel *pchan)
+{
+  /* No type assertion as this is a fallback (files from the future will end up here). */
+  /* Account for spheres on the end-points. */
+  const float scale = 1.2f;
+  return pchan_culling_test_with_radius_scale(view, ob, pchan, scale);
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
 /** \name Main Draw Loops
  * \{ */
 
@@ -2185,6 +2305,8 @@ static void draw_armature_pose(ArmatureDrawContext *ctx)
     }
   }
 
+  const DRWView *view = is_pose_select ? DRW_view_default_get() : NULL;
+
   for (pchan = ob->pose->chanbase.first; pchan; pchan = pchan->next, index += 0x10000) {
     Bone *bone = pchan->bone;
     const bool bone_visible = (bone->flag & (BONE_HIDDEN_P | BONE_HIDDEN_PG)) == 0;
@@ -2225,27 +2347,39 @@ static void draw_armature_pose(ArmatureDrawContext *ctx)
 
         if ((pchan->custom) && !(arm->flag & ARM_NO_CUSTOM)) {
           draw_bone_update_disp_matrix_custom(pchan);
-          draw_bone_custom_shape(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          if (!is_pose_select || pchan_culling_test_custom(view, ob, pchan)) {
+            draw_bone_custom_shape(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          }
         }
         else if (arm->drawtype == ARM_ENVELOPE) {
           draw_bone_update_disp_matrix_default(NULL, pchan);
-          draw_bone_envelope(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          if (!is_pose_select || pchan_culling_test_envelope(view, ob, pchan)) {
+            draw_bone_envelope(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          }
         }
         else if (arm->drawtype == ARM_LINE) {
           draw_bone_update_disp_matrix_default(NULL, pchan);
-          draw_bone_line(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          if (!is_pose_select || pchan_culling_test_line(view, ob, pchan)) {
+            draw_bone_line(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          }
         }
         else if (arm->drawtype == ARM_WIRE) {
           draw_bone_update_disp_matrix_bbone(NULL, pchan);
-          draw_bone_wire(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          if (!is_pose_select || pchan_culling_test_wire(view, ob, pchan)) {
+            draw_bone_wire(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          }
         }
         else if (arm->drawtype == ARM_B_BONE) {
           draw_bone_update_disp_matrix_bbone(NULL, pchan);
-          draw_bone_box(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          if (!is_pose_select || pchan_culling_test_bbone(view, ob, pchan)) {
+            draw_bone_box(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          }
         }
         else {
           draw_bone_update_disp_matrix_default(NULL, pchan);
-          draw_bone_octahedral(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          if (!is_pose_select || pchan_culling_test_octohedral(view, ob, pchan)) {
+            draw_bone_octahedral(ctx, NULL, pchan, arm, boneflag, constflag, select_id);
+          }
         }
 
         /* These aren't included in the selection. */