[mutter/gbsneto/graphene-ray: 9/11] Use graphene_ray_t to pick actors




commit e1cceabfc1be89041d114a9ae494ce94f2fa970f
Author: Georges Basile Stavracas Neto <georges stavracas gmail com>
Date:   Sat Oct 17 11:52:45 2020 -0300

    Use graphene_ray_t to pick actors
    
    This commit introduces a few important changes in order to
    acommodate graphene_ray_t. Most of them are positive changes,
    so don't panic :)
    
    The first very visible change is that neither the actor box
    nor the clip rectangles are projected before being pushed.
    This required changing the parameters of the related functions
    at both ClutterPickContext, and ClutterPickStack, to receive
    boxes instead of vertices. These rectangles are projected on
    demand now, so in the best case (first actor picked) only
    one projection happens; and in the worst case, it projects
    as much as it does now.
    
    The second important change is that there are no more checks
    for axis-alignment anymore. That's because picking now happens
    in 3D space, using triangles.
    
    Talking about triangles in 3D space, this is what is used now
    for picking. We break down each actor rectangle in 2 triangles,
    and check if the ray intersects any one of them. The same check
    happens for the clip rectangles.
    
    https://gitlab.gnome.org/GNOME/mutter/-/merge_requests/1509

 clutter/clutter/clutter-actor.c              |  80 +----------
 clutter/clutter/clutter-pick-context.c       |  14 +-
 clutter/clutter/clutter-pick-context.h       |  10 +-
 clutter/clutter/clutter-pick-stack-private.h |  15 +--
 clutter/clutter/clutter-pick-stack.c         | 195 +++++++++++----------------
 clutter/clutter/clutter-stage.c              |  34 ++++-
 6 files changed, 132 insertions(+), 216 deletions(-)
---
diff --git a/clutter/clutter/clutter-actor.c b/clutter/clutter/clutter-actor.c
index 93904a79de..ad94659b8b 100644
--- a/clutter/clutter/clutter-actor.c
+++ b/clutter/clutter/clutter-actor.c
@@ -1249,57 +1249,6 @@ clutter_actor_verify_map_state (ClutterActor *self)
 
 #endif /* CLUTTER_ENABLE_DEBUG */
 
-static gboolean
-_clutter_actor_transform_local_box_to_stage (ClutterActor          *self,
-                                             ClutterStage          *stage,
-                                             ClutterPickContext    *pick_context,
-                                             const ClutterActorBox *box,
-                                             graphene_point_t       vertices[4])
-{
-  ClutterActor *stage_actor = CLUTTER_ACTOR (stage);
-  ClutterActorPrivate *stage_priv = stage_actor->priv;
-  graphene_matrix_t modelview, transform_to_stage;
-  int v;
-
-  ensure_valid_actor_transform (stage_actor);
-
-  if (!stage_priv->has_inverse_transform)
-    return FALSE;
-  clutter_pick_context_get_transform (pick_context, &modelview);
-  graphene_matrix_multiply (&modelview,
-                            &stage_priv->inverse_transform,
-                            &transform_to_stage);
-
-  vertices[0].x = box->x1;
-  vertices[0].y = box->y1;
-
-  vertices[1].x = box->x2;
-  vertices[1].y = box->y1;
-
-  vertices[2].x = box->x2;
-  vertices[2].y = box->y2;
-
-  vertices[3].x = box->x1;
-  vertices[3].y = box->y2;
-
-  for (v = 0; v < 4; v++)
-    {
-      float z = 0.f;
-      float w = 1.f;
-
-      cogl_graphene_matrix_project_point (&transform_to_stage,
-                                          &vertices[v].x,
-                                          &vertices[v].y,
-                                          &z,
-                                          &w);
-
-      clutter_round_to_256ths (&vertices[v].x);
-      clutter_round_to_256ths (&vertices[v].y);
-    }
-
-  return TRUE;
-}
-
 /**
  * clutter_actor_pick_box:
  * @self: The #ClutterActor being "pick" painted.
@@ -1317,38 +1266,13 @@ clutter_actor_pick_box (ClutterActor          *self,
                         ClutterPickContext    *pick_context,
                         const ClutterActorBox *box)
 {
-  ClutterStage *stage;
-  graphene_point_t vertices[4];
-
   g_return_if_fail (CLUTTER_IS_ACTOR (self));
   g_return_if_fail (box != NULL);
 
   if (box->x1 >= box->x2 || box->y1 >= box->y2)
     return;
 
-  stage = CLUTTER_STAGE (_clutter_actor_get_stage_internal (self));
-
-  if (_clutter_actor_transform_local_box_to_stage (self, stage, pick_context,
-                                                   box, vertices))
-    clutter_pick_context_log_pick (pick_context, vertices, self);
-}
-
-static gboolean
-_clutter_actor_push_pick_clip (ClutterActor          *self,
-                               ClutterPickContext    *pick_context,
-                               const ClutterActorBox *clip)
-{
-  ClutterStage *stage;
-  graphene_point_t vertices[4];
-
-  stage = CLUTTER_STAGE (_clutter_actor_get_stage_internal (self));
-
-  if (!_clutter_actor_transform_local_box_to_stage (self, stage, pick_context,
-                                                    clip, vertices))
-    return FALSE;
-
-  clutter_pick_context_push_clip (pick_context, vertices);
-  return TRUE;
+  clutter_pick_context_log_pick (pick_context, box, self);
 }
 
 static void
@@ -4080,7 +4004,7 @@ clutter_actor_pick (ClutterActor       *actor,
     }
 
   if (clip_set)
-    clip_set = _clutter_actor_push_pick_clip (actor, pick_context, &clip);
+    clutter_pick_context_push_clip (pick_context, &clip);
 
   priv->next_effect_to_paint = NULL;
   if (priv->effects)
diff --git a/clutter/clutter/clutter-pick-context.c b/clutter/clutter/clutter-pick-context.c
index cc75f441db..b22c0dc1b8 100644
--- a/clutter/clutter/clutter-pick-context.c
+++ b/clutter/clutter/clutter-pick-context.c
@@ -111,21 +111,21 @@ clutter_pick_context_steal_stack (ClutterPickContext *pick_context)
  * clutter_pick_context_log_pick:
  */
 void
-clutter_pick_context_log_pick (ClutterPickContext     *pick_context,
-                               const graphene_point_t *vertices,
-                               ClutterActor           *actor)
+clutter_pick_context_log_pick (ClutterPickContext    *pick_context,
+                               const ClutterActorBox *box,
+                               ClutterActor          *actor)
 {
-  clutter_pick_stack_log_pick (pick_context->pick_stack, vertices, actor);
+  clutter_pick_stack_log_pick (pick_context->pick_stack, box, actor);
 }
 
 /**
  * clutter_pick_context_push_clip:
  */
 void
-clutter_pick_context_push_clip (ClutterPickContext     *pick_context,
-                                const graphene_point_t *vertices)
+clutter_pick_context_push_clip (ClutterPickContext    *pick_context,
+                                const ClutterActorBox *box)
 {
-  clutter_pick_stack_push_clip (pick_context->pick_stack, vertices);
+  clutter_pick_stack_push_clip (pick_context->pick_stack, box);
 }
 
 /**
diff --git a/clutter/clutter/clutter-pick-context.h b/clutter/clutter/clutter-pick-context.h
index b89441bdcf..0faf028256 100644
--- a/clutter/clutter/clutter-pick-context.h
+++ b/clutter/clutter/clutter-pick-context.h
@@ -50,13 +50,13 @@ CLUTTER_EXPORT
 ClutterPickMode clutter_pick_context_get_mode (ClutterPickContext *pick_context);
 
 CLUTTER_EXPORT
-void clutter_pick_context_log_pick (ClutterPickContext     *pick_context,
-                                    const graphene_point_t *vertices,
-                                    ClutterActor           *actor);
+void clutter_pick_context_log_pick (ClutterPickContext    *pick_context,
+                                    const ClutterActorBox *box,
+                                    ClutterActor          *actor);
 
 CLUTTER_EXPORT
-void clutter_pick_context_push_clip (ClutterPickContext     *pick_context,
-                                     const graphene_point_t *vertices);
+void clutter_pick_context_push_clip (ClutterPickContext    *pick_context,
+                                     const ClutterActorBox *box);
 
 CLUTTER_EXPORT
 void clutter_pick_context_pop_clip (ClutterPickContext *pick_context);
diff --git a/clutter/clutter/clutter-pick-stack-private.h b/clutter/clutter/clutter-pick-stack-private.h
index 03a7e5aa4f..0c84ce2250 100644
--- a/clutter/clutter/clutter-pick-stack-private.h
+++ b/clutter/clutter/clutter-pick-stack-private.h
@@ -39,12 +39,12 @@ void clutter_pick_stack_unref (ClutterPickStack *pick_stack);
 
 void clutter_pick_stack_seal (ClutterPickStack *pick_stack);
 
-void clutter_pick_stack_log_pick (ClutterPickStack       *pick_stack,
-                                  const graphene_point_t *vertices,
-                                  ClutterActor           *actor);
+void clutter_pick_stack_log_pick (ClutterPickStack      *pick_stack,
+                                  const ClutterActorBox *box,
+                                  ClutterActor          *actor);
 
-void clutter_pick_stack_push_clip (ClutterPickStack       *pick_stack,
-                                   const graphene_point_t *vertices);
+void clutter_pick_stack_push_clip (ClutterPickStack      *pick_stack,
+                                   const ClutterActorBox *box);
 
 void clutter_pick_stack_pop_clip (ClutterPickStack *pick_stack);
 
@@ -56,9 +56,8 @@ void clutter_pick_stack_get_transform (ClutterPickStack  *pick_stack,
 
 void clutter_pick_stack_pop_transform (ClutterPickStack *pick_stack);
 
-ClutterActor * clutter_pick_stack_find_actor_at (ClutterPickStack *pick_stack,
-                                                 float             x,
-                                                 float             y);
+ClutterActor * clutter_pick_stack_search_actor (ClutterPickStack     *pick_stack,
+                                                const graphene_ray_t *ray);
 
 G_END_DECLS
 
diff --git a/clutter/clutter/clutter-pick-stack.c b/clutter/clutter/clutter-pick-stack.c
index 4cba703af9..de23373971 100644
--- a/clutter/clutter/clutter-pick-stack.c
+++ b/clutter/clutter/clutter-pick-stack.c
@@ -20,17 +20,23 @@
 
 typedef struct
 {
-  graphene_point_t vertex[4];
+  graphene_point3d_t vertex[4];
+  CoglMatrixEntry *matrix_entry;
+  ClutterActorBox rect;
+  gboolean projected;
+} Record;
+
+typedef struct
+{
+  Record r;
   ClutterActor *actor;
   int clip_stack_top;
-  CoglMatrixEntry *matrix_entry;
 } PickRecord;
 
 typedef struct
 {
+  Record r;
   int prev;
-  graphene_point_t vertex[4];
-  CoglMatrixEntry *matrix_entry;
 } PickClipRecord;
 
 struct _ClutterPickStack
@@ -48,133 +54,87 @@ struct _ClutterPickStack
 G_DEFINE_BOXED_TYPE (ClutterPickStack, clutter_pick_stack,
                      clutter_pick_stack_ref, clutter_pick_stack_unref)
 
-static gboolean
-is_quadrilateral_axis_aligned_rectangle (const graphene_point_t *vertices)
+static void
+project_vertices (CoglMatrixEntry       *matrix_entry,
+                  const ClutterActorBox *box,
+                  graphene_point3d_t    *vertices)
 {
+  graphene_matrix_t m;
   int i;
 
+  cogl_matrix_entry_get (matrix_entry, &m);
+
+  graphene_point3d_init (&vertices[0], box->x1, box->y1, 0.f);
+  graphene_point3d_init (&vertices[1], box->x2, box->y1, 0.f);
+  graphene_point3d_init (&vertices[2], box->x2, box->y2, 0.f);
+  graphene_point3d_init (&vertices[3], box->x1, box->y2, 0.f);
+
   for (i = 0; i < 4; i++)
     {
-      if (!G_APPROX_VALUE (vertices[i].x,
-                           vertices[(i + 1) % 4].x,
-                           FLT_EPSILON) &&
-          !G_APPROX_VALUE (vertices[i].y,
-                           vertices[(i + 1) % 4].y,
-                           FLT_EPSILON))
-        return FALSE;
-    }
-  return TRUE;
-}
+      float w = 1.f;
 
-static gboolean
-is_inside_axis_aligned_rectangle (const graphene_point_t *point,
-                                  const graphene_point_t *vertices)
-{
-  float min_x = FLT_MAX;
-  float max_x = -FLT_MAX;
-  float min_y = FLT_MAX;
-  float max_y = -FLT_MAX;
-  int i;
+      cogl_graphene_matrix_project_point (&m,
+                                          &vertices[i].x,
+                                          &vertices[i].y,
+                                          &vertices[i].z,
+                                          &w);
 
-  for (i = 0; i < 3; i++)
-    {
-      min_x = MIN (min_x, vertices[i].x);
-      min_y = MIN (min_y, vertices[i].y);
-      max_x = MAX (max_x, vertices[i].x);
-      max_y = MAX (max_y, vertices[i].y);
+      clutter_round_to_256ths (&vertices[i].x);
+      clutter_round_to_256ths (&vertices[i].y);
+      clutter_round_to_256ths (&vertices[i].z);
     }
-
-  return (point->x >= min_x &&
-          point->y >= min_y &&
-          point->x < max_x &&
-          point->y < max_y);
 }
-
-static int
-clutter_point_compare_line (const graphene_point_t *p,
-                            const graphene_point_t *a,
-                            const graphene_point_t *b)
+static void
+maybe_project_record (Record *rec)
 {
-  graphene_vec3_t vec_pa;
-  graphene_vec3_t vec_pb;
-  graphene_vec3_t cross;
-  float cross_z;
-
-  graphene_vec3_init (&vec_pa, p->x - a->x, p->y - a->y, 0.f);
-  graphene_vec3_init (&vec_pb, p->x - b->x, p->y - b->y, 0.f);
-  graphene_vec3_cross (&vec_pa, &vec_pb, &cross);
-  cross_z = graphene_vec3_get_z (&cross);
-
-  if (cross_z > 0.f)
-    return 1;
-  else if (cross_z < 0.f)
-    return -1;
-  else
-    return 0;
+  if (rec->projected)
+    return;
+
+  project_vertices (rec->matrix_entry, &rec->rect, rec->vertex);
+  rec->projected = TRUE;
 }
 
 static gboolean
-is_inside_unaligned_rectangle (const graphene_point_t *point,
-                               const graphene_point_t *vertices)
+ray_intersects_input_region (const graphene_ray_t     *ray,
+                             const graphene_point3d_t *vertices)
 {
-  unsigned int i;
-  int first_side;
-
-  first_side = 0;
-
-  for (i = 0; i < 4; i++)
-    {
-      int side;
-
-      side = clutter_point_compare_line (point,
-                                         &vertices[i],
-                                         &vertices[(i + 1) % 4]);
-
-      if (side)
-        {
-          if (first_side == 0)
-            first_side = side;
-          else if (side != first_side)
-            return FALSE;
-        }
-    }
+  graphene_triangle_t t0, t1;
 
-  if (first_side == 0)
-    return FALSE;
+  graphene_triangle_init_from_point3d (&t0,
+                                       &vertices[0],
+                                       &vertices[1],
+                                       &vertices[2]);
 
-  return TRUE;
-}
+  graphene_triangle_init_from_point3d (&t1,
+                                       &vertices[0],
+                                       &vertices[2],
+                                       &vertices[3]);
 
-static gboolean
-is_inside_input_region (const graphene_point_t *point,
-                        const graphene_point_t *vertices)
-{
-
-  if (is_quadrilateral_axis_aligned_rectangle (vertices))
-    return is_inside_axis_aligned_rectangle (point, vertices);
-  else
-    return is_inside_unaligned_rectangle (point, vertices);
+  return graphene_ray_intersects_triangle (ray, &t0) ||
+         graphene_ray_intersects_triangle (ray, &t1);
 }
 
 static gboolean
-pick_record_contains_point (ClutterPickStack *pick_stack,
-                            const PickRecord *rec,
-                            float             x,
-                            float             y)
+ray_intersects_record (ClutterPickStack     *pick_stack,
+                       PickRecord           *rec,
+                       const graphene_ray_t *ray)
 {
-  const graphene_point_t point = GRAPHENE_POINT_INIT (x, y);
   int clip_index;
 
-  if (!is_inside_input_region (&point, rec->vertex))
+  maybe_project_record (&rec->r);
+
+  if (!ray_intersects_input_region (ray, rec->r.vertex))
     return FALSE;
 
   clip_index = rec->clip_stack_top;
   while (clip_index >= 0)
     {
-      const PickClipRecord *clip =
+      PickClipRecord *clip =
         &g_array_index (pick_stack->clip_stack, PickClipRecord, clip_index);
 
-      if (!is_inside_input_region (&point, clip->vertex))
+      maybe_project_record (&clip->r);
+
+      if (!ray_intersects_input_region (ray, clip->r.vertex))
         return FALSE;
 
       clip_index = clip->prev;
@@ -230,14 +190,14 @@ static void
 clear_pick_record (gpointer data)
 {
   PickRecord *rec = data;
-  g_clear_pointer (&rec->matrix_entry, cogl_matrix_entry_unref);
+  g_clear_pointer (&rec->r.matrix_entry, cogl_matrix_entry_unref);
 }
 
 static void
 clear_clip_record (gpointer data)
 {
   PickClipRecord *clip = data;
-  g_clear_pointer (&clip->matrix_entry, cogl_matrix_entry_unref);
+  g_clear_pointer (&clip->r.matrix_entry, cogl_matrix_entry_unref);
 }
 
 /**
@@ -308,7 +268,7 @@ clutter_pick_stack_seal (ClutterPickStack *pick_stack)
 
 void
 clutter_pick_stack_log_pick (ClutterPickStack       *pick_stack,
-                             const graphene_point_t *vertices,
+                             const ClutterActorBox  *box,
                              ClutterActor           *actor)
 {
   PickRecord rec;
@@ -317,27 +277,29 @@ clutter_pick_stack_log_pick (ClutterPickStack       *pick_stack,
 
   g_assert (!pick_stack->sealed);
 
-  memcpy (rec.vertex, vertices, 4 * sizeof (graphene_point_t));
   rec.actor = actor;
   rec.clip_stack_top = pick_stack->clip_stack_top;
-  rec.matrix_entry = cogl_matrix_stack_get_entry (pick_stack->matrix_stack);
-  cogl_matrix_entry_ref (rec.matrix_entry);
+  rec.r.rect = *box;
+  rec.r.projected = FALSE;
+  rec.r.matrix_entry = cogl_matrix_stack_get_entry (pick_stack->matrix_stack);
+  cogl_matrix_entry_ref (rec.r.matrix_entry);
 
   g_array_append_val (pick_stack->vertices_stack, rec);
 }
 
 void
-clutter_pick_stack_push_clip (ClutterPickStack       *pick_stack,
-                              const graphene_point_t *vertices)
+clutter_pick_stack_push_clip (ClutterPickStack      *pick_stack,
+                              const ClutterActorBox *box)
 {
   PickClipRecord clip;
 
   g_assert (!pick_stack->sealed);
 
   clip.prev = pick_stack->clip_stack_top;
-  memcpy (clip.vertex, vertices, 4 * sizeof (graphene_point_t));
-  clip.matrix_entry = cogl_matrix_stack_get_entry (pick_stack->matrix_stack);
-  cogl_matrix_entry_ref (clip.matrix_entry);
+  clip.r.rect = *box;
+  clip.r.projected = FALSE;
+  clip.r.matrix_entry = cogl_matrix_stack_get_entry (pick_stack->matrix_stack);
+  cogl_matrix_entry_ref (clip.r.matrix_entry);
 
   g_array_append_val (pick_stack->clip_stack, clip);
   pick_stack->clip_stack_top = pick_stack->clip_stack->len - 1;
@@ -386,9 +348,8 @@ clutter_pick_stack_pop_transform (ClutterPickStack *pick_stack)
 }
 
 ClutterActor *
-clutter_pick_stack_find_actor_at (ClutterPickStack *pick_stack,
-                                  float             x,
-                                  float             y)
+clutter_pick_stack_search_actor (ClutterPickStack     *pick_stack,
+                                 const graphene_ray_t *ray)
 {
   int i;
 
@@ -398,10 +359,10 @@ clutter_pick_stack_find_actor_at (ClutterPickStack *pick_stack,
    */
   for (i = pick_stack->vertices_stack->len - 1; i >= 0; i--)
     {
-      const PickRecord *rec =
+      PickRecord *rec =
         &g_array_index (pick_stack->vertices_stack, PickRecord, i);
 
-      if (rec->actor && pick_record_contains_point (pick_stack, rec, x, y))
+      if (rec->actor && ray_intersects_record (pick_stack, rec, ray))
         return rec->actor;
     }
 
diff --git a/clutter/clutter/clutter-stage.c b/clutter/clutter/clutter-stage.c
index d273e88861..94cdc1547e 100644
--- a/clutter/clutter/clutter-stage.c
+++ b/clutter/clutter/clutter-stage.c
@@ -1131,6 +1131,35 @@ _clutter_stage_has_full_redraw_queued (ClutterStage *stage)
   return is_full_stage_redraw_queued (stage);
 }
 
+static void
+setup_ray_for_coordinates (ClutterStage   *stage,
+                           float           x,
+                           float           y,
+                           graphene_ray_t *ray)
+{
+  ClutterStagePrivate *priv = stage->priv;
+  graphene_point3d_t camera_position;
+  graphene_vec3_t direction;
+  graphene_vec4_t cv;
+  graphene_vec4_t v;
+
+  camera_position = GRAPHENE_POINT3D_INIT_ZERO;
+  graphene_vec4_init (&cv,
+                      camera_position.x,
+                      camera_position.y,
+                      camera_position.z,
+                      1.f);
+
+  graphene_vec4_init (&v, x, y, 0.f, 1.f);
+  graphene_matrix_transform_vec4 (&priv->view, &v, &v);
+
+  graphene_vec4_subtract (&v, &cv, &v);
+  graphene_vec4_normalize (&v, &v);
+  graphene_vec4_get_xyz (&v, &direction);
+
+  graphene_ray_init (ray, &camera_position, &direction);
+}
+
 static ClutterActor *
 _clutter_stage_do_pick_on_view (ClutterStage     *stage,
                                 float             x,
@@ -1139,6 +1168,7 @@ _clutter_stage_do_pick_on_view (ClutterStage     *stage,
                                 ClutterStageView *view)
 {
   ClutterStagePrivate *priv = stage->priv;
+  graphene_ray_t ray;
   ClutterActor *actor;
 
   COGL_TRACE_BEGIN_SCOPED (ClutterStagePickView, "Pick (view)");
@@ -1158,7 +1188,9 @@ _clutter_stage_do_pick_on_view (ClutterStage     *stage,
       clutter_pick_context_destroy (pick_context);
     }
 
-  actor = clutter_pick_stack_find_actor_at (priv->pick_stack, x, y);
+  setup_ray_for_coordinates (stage, x, y, &ray);
+
+  actor = clutter_pick_stack_search_actor (priv->pick_stack, &ray);
   return actor ? actor : CLUTTER_ACTOR (stage);
 }
 


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]