Tracking: Add interpolated accessor for markers

Allows to get marker position interpolated through out a gap.

Currently unused, but is covered with test. Aimed to be used for
track average operator.

3 files changed, 202 insertions, 1 deletions

diff --git a/source/blender/blenkernel/BKE_tracking.h b/source/blender/blenkernel/BKE_tracking.h
index 4dbc22ae18f..5da8d969f1e 100644
--- a/source/blender/blenkernel/BKE_tracking.h
+++ b/source/blender/blenkernel/BKE_tracking.h
@@ -139,6 +139,17 @@ struct MovieTrackingMarker *BKE_tracking_marker_get_exact(struct MovieTrackingTr
 struct MovieTrackingMarker *BKE_tracking_marker_ensure(struct MovieTrackingTrack *track,
                                                        int framenr);
 
+/* Get marker position, possibly interpolating interpolating gap between keyframed/tracked markers.
+ *
+ * The result marker frame number is set to the requested frame number. Its flags are 0 if the
+ * marker is interpolated, and is set to original marker flag if there were no interpolation
+ * involved.
+ *
+ * Returns truth if the result is usable. */
+bool BKE_tracking_marker_get_interpolated(struct MovieTrackingTrack *track,
+                                          const int framenr,
+                                          struct MovieTrackingMarker *r_marker);
+
 void BKE_tracking_marker_pattern_minmax(const struct MovieTrackingMarker *marker,
                                         float min[2],
                                         float max[2]);
diff --git a/source/blender/blenkernel/intern/tracking.c b/source/blender/blenkernel/intern/tracking.c
index 6cefbd746b0..7b075610ba9 100644
--- a/source/blender/blenkernel/intern/tracking.c
+++ b/source/blender/blenkernel/intern/tracking.c
@@ -1380,6 +1380,84 @@ MovieTrackingMarker *BKE_tracking_marker_ensure(MovieTrackingTrack *track, int f
   return marker;
 }
 
+static const MovieTrackingMarker *get_usable_marker_for_interpolation(
+    struct MovieTrackingTrack *track,
+    const MovieTrackingMarker *anchor_marker,
+    const int direction)
+{
+  BLI_assert(direction == -1 || direction == 1);
+
+  const MovieTrackingMarker *last_marker = track->markers + track->markersnr - 1;
+  const MovieTrackingMarker *current_marker = anchor_marker;
+
+  while (current_marker >= track->markers && current_marker <= last_marker) {
+    if ((current_marker->flag & MARKER_DISABLED) == 0) {
+      return current_marker;
+    }
+    current_marker += direction;
+  }
+
+  return NULL;
+}
+
+bool BKE_tracking_marker_get_interpolated(struct MovieTrackingTrack *track,
+                                          const int framenr,
+                                          struct MovieTrackingMarker *r_marker)
+{
+  const MovieTrackingMarker *closest_marker = BKE_tracking_marker_get(track, framenr);
+  if (closest_marker == NULL) {
+    return false;
+  }
+  if (closest_marker->framenr == framenr && (closest_marker->flag & MARKER_DISABLED) == 0) {
+    *r_marker = *closest_marker;
+    return true;
+  }
+
+  const MovieTrackingMarker *left_marker = get_usable_marker_for_interpolation(
+      track, closest_marker, -1);
+  if (left_marker == NULL) {
+    return false;
+  }
+
+  const MovieTrackingMarker *right_marker = get_usable_marker_for_interpolation(
+      track, closest_marker + 1, 1);
+  if (right_marker == NULL) {
+    return false;
+  }
+
+  if (left_marker == right_marker) {
+    *r_marker = *left_marker;
+    return true;
+  }
+
+  const float factor = (float)(framenr - left_marker->framenr) /
+                       (right_marker->framenr - left_marker->framenr);
+
+  interp_v2_v2v2(r_marker->pos, left_marker->pos, right_marker->pos, factor);
+
+  for (int i = 0; i < 4; i++) {
+    interp_v2_v2v2(r_marker->pattern_corners[i],
+                   left_marker->pattern_corners[i],
+                   right_marker->pattern_corners[i],
+                   factor);
+  }
+
+  interp_v2_v2v2(r_marker->search_min, left_marker->search_min, right_marker->search_min, factor);
+  interp_v2_v2v2(r_marker->search_max, left_marker->search_max, right_marker->search_max, factor);
+
+  r_marker->framenr = framenr;
+  r_marker->flag = 0;
+
+  if (framenr == left_marker->framenr) {
+    r_marker->flag = left_marker->flag;
+  }
+  else if (framenr == right_marker->framenr) {
+    r_marker->flag = right_marker->flag;
+  }
+
+  return true;
+}
+
 void BKE_tracking_marker_pattern_minmax(const MovieTrackingMarker *marker,
                                         float min[2],
                                         float max[2])
diff --git a/source/blender/blenkernel/intern/tracking_test.cc b/source/blender/blenkernel/intern/tracking_test.cc
index 6c3cf89a03f..2877d8db358 100644
--- a/source/blender/blenkernel/intern/tracking_test.cc
+++ b/source/blender/blenkernel/intern/tracking_test.cc
@@ -5,15 +5,23 @@
 #include "DNA_tracking_types.h"
 
 #include "BKE_tracking.h"
+#include "BLI_float2.hh"
+
+namespace blender {
 
 namespace {
 
 class TrackingTest : public ::testing::Test {
  protected:
-  MovieTrackingMarker *addMarkerToTrack(MovieTrackingTrack *track, int frame_number)
+  MovieTrackingMarker *addMarkerToTrack(MovieTrackingTrack *track,
+                                        int frame_number,
+                                        const float2 &position = float2(0.0f, 0.0f),
+                                        int flag = 0)
   {
     MovieTrackingMarker marker = {{0.0f}};
+    copy_v2_v2(marker.pos, position);
     marker.framenr = frame_number;
+    marker.flag = flag;
     return BKE_tracking_marker_insert(track, &marker);
   }
 };
@@ -96,3 +104,107 @@ TEST_F(TrackingTest, BKE_tracking_marker_get_exact)
 
   BKE_tracking_track_free(&track);
 }
+
+TEST_F(TrackingTest, BKE_tracking_marker_get_interpolated)
+{
+  /* Simple case, no disabled markers in a way. */
+  {
+    MovieTrackingTrack track = {nullptr};
+
+    addMarkerToTrack(&track, 1, float2(1.0f, 5.0f));
+    addMarkerToTrack(&track, 10, float2(2.0f, 1.0f));
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 1, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 1);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(1.0f, 5.0f), 1e-6f);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 10, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 10);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(2.0f, 1.0f), 1e-6f);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 4, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 4);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(1.3333333f, 3.6666666f), 1e-6f);
+    }
+
+    BKE_tracking_track_free(&track);
+  }
+
+  /* More comprehensive test, which resembles real life trackign scenario better. */
+  {
+    MovieTrackingTrack track = {nullptr};
+
+    addMarkerToTrack(&track, 1, float2(1.0f, 5.0f));
+    addMarkerToTrack(&track, 2, float2(0.0f, 0.0f), MARKER_DISABLED);
+    addMarkerToTrack(&track, 9, float2(0.0f, 0.0f), MARKER_DISABLED);
+    addMarkerToTrack(&track, 10, float2(2.0f, 1.0f));
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 1, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 1);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(1.0f, 5.0f), 1e-6f);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 10, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 10);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(2.0f, 1.0f), 1e-6f);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 4, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 4);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(1.3333333f, 3.6666666f), 1e-6f);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 9, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.framenr, 9);
+      EXPECT_V2_NEAR(interpolated_marker.pos, float2(1.888888f, 1.4444444f), 1e-6f);
+    }
+
+    BKE_tracking_track_free(&track);
+  }
+
+  /* Tracked/keyframed flag check. */
+  {
+    MovieTrackingTrack track = {nullptr};
+
+    addMarkerToTrack(&track, 1, float2(1.0f, 5.0f), MARKER_TRACKED);
+    addMarkerToTrack(&track, 10, float2(2.0f, 1.0f), MARKER_TRACKED);
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 1, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.flag, MARKER_TRACKED);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 10, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.flag, MARKER_TRACKED);
+    }
+
+    {
+      MovieTrackingMarker interpolated_marker;
+      EXPECT_TRUE(BKE_tracking_marker_get_interpolated(&track, 4, &interpolated_marker));
+      EXPECT_EQ(interpolated_marker.flag, 0);
+    }
+
+    BKE_tracking_track_free(&track);
+  }
+}
+
+}  // namespace blender