Tracking: Re-write marker request function

There are two main things.

First, remove the marker index caching. Thins makes it possible to
safely use function from a threaded environment.

Second, replace linear search with binary search, which speeds up
random lookup.

There is no measurable difference in the stabilization which had a
comment about caching nature of track lookup. The random lookup
complexity changed from O(N) to O(log N). In practice this also
unlikely to be measurable, but thread-safety worth it.

4 files changed, 73 insertions, 53 deletions

diff --git a/source/blender/blenkernel/intern/tracking.c b/source/blender/blenkernel/intern/tracking.c
index e5f9d59270e..6cefbd746b0 100644
--- a/source/blender/blenkernel/intern/tracking.c
+++ b/source/blender/blenkernel/intern/tracking.c
@@ -1224,8 +1224,6 @@ MovieTrackingMarker *BKE_tracking_marker_insert(MovieTrackingTrack *track,
   /* put new marker */
   track->markers[a + 1] = *marker;
 
-  track->last_marker = a + 1;
-
   return &track->markers[a + 1];
 }
 
@@ -1314,51 +1312,44 @@ void BKE_tracking_marker_clamp(MovieTrackingMarker *marker, int event)
   }
 }
 
+/* Get marker closest to the given frame number.
+ *
+ * If there is maker with exact frame number it returned.
+ * Otherwise, marker with higherst frame number but lower than the requested
+ * frame is returned if such marker exists. Otherwise, the marker with lowest
+ * frame number greater than the requested frame number is returned.
+ *
+ * This function has complexity of O(log number_of_markers). */
 MovieTrackingMarker *BKE_tracking_marker_get(MovieTrackingTrack *track, int framenr)
 {
-  int a = track->markersnr - 1;
+  const int num_markers = track->markersnr;
 
-  if (!track->markersnr) {
+  if (num_markers == 0) {
+    BLI_assert(!"Detected degenerated track, should never happen.");
     return NULL;
   }
 
-  /* approximate pre-first framenr marker with first marker */
-  if (framenr < track->markers[0].framenr) {
-    return &track->markers[0];
-  }
-
-  if (track->last_marker < track->markersnr) {
-    a = track->last_marker;
-  }
-
-  if (track->markers[a].framenr <= framenr) {
-    while (a < track->markersnr && track->markers[a].framenr <= framenr) {
-      if (track->markers[a].framenr == framenr) {
-        track->last_marker = a;
+  int left_boundary = 0;
+  int right_boundary = num_markers;
+  while (left_boundary < right_boundary) {
+    const int median_index = (left_boundary + right_boundary) / 2;
+    MovieTrackingMarker *marker = &track->markers[median_index];
 
-        return &track->markers[a];
-      }
-      a++;
+    if (marker->framenr == framenr) {
+      return marker;
     }
-
-    /* if there's no marker for exact position, use nearest marker from left side */
-    return &track->markers[a - 1];
-  }
-
-  while (a >= 0 && track->markers[a].framenr >= framenr) {
-    if (track->markers[a].framenr == framenr) {
-      track->last_marker = a;
-
-      return &track->markers[a];
+    else if (marker->framenr < framenr) {
+      left_boundary = median_index + 1;
+    }
+    else {
+      BLI_assert(marker->framenr > framenr);
+      right_boundary = median_index - 1;
     }
-
-    a--;
   }
 
-  /* if there's no marker for exact position, use nearest marker from left side */
-  return &track->markers[a];
+  const int closest_index = clamp_i(right_boundary, 0, num_markers - 1);
 
-  return NULL;
+  return &track->markers[closest_index];
 }
 
 MovieTrackingMarker *BKE_tracking_marker_get_exact(MovieTrackingTrack *track, int framenr)
@@ -1683,7 +1674,6 @@ MovieTrackingPlaneMarker *BKE_tracking_plane_marker_insert(MovieTrackingPlaneTra
 
   /* Put new marker to an array. */
   plane_track->markers[a + 1] = *plane_marker;
-  plane_track->last_marker = a + 1;
 
   return &plane_track->markers[a + 1];
 }
diff --git a/source/blender/blenkernel/intern/tracking_stabilize.c b/source/blender/blenkernel/intern/tracking_stabilize.c
index 6f58416924f..46589a578a8 100644
--- a/source/blender/blenkernel/intern/tracking_stabilize.c
+++ b/source/blender/blenkernel/intern/tracking_stabilize.c
@@ -311,11 +311,7 @@ static void retrieve_next_lower_usable_frame(
  * translation stabilization, which has an enabled tracking marker at this very
  * frame. We search both for the next lower and next higher position, to allow
  * the caller to interpolate gaps and to extrapolate at the ends of the
- * definition range.
- *
- * NOTE: Regarding performance note that the individual tracks will cache the
- *       last search position.
- */
+ * definition range. */
 static void find_next_working_frames(StabContext *ctx,
                                      int framenr,
                                      int *next_lower,
diff --git a/source/blender/blenkernel/intern/tracking_test.cc b/source/blender/blenkernel/intern/tracking_test.cc
index 6afcf6872eb..6c3cf89a03f 100644
--- a/source/blender/blenkernel/intern/tracking_test.cc
+++ b/source/blender/blenkernel/intern/tracking_test.cc
@@ -22,24 +22,58 @@ class TrackingTest : public ::testing::Test {
 
 TEST_F(TrackingTest, BKE_tracking_marker_get)
 {
-  MovieTrackingTrack track = {nullptr};
+  {
+    MovieTrackingTrack track = {nullptr};
 
-  addMarkerToTrack(&track, 1);
-  addMarkerToTrack(&track, 10);
+    addMarkerToTrack(&track, 10);
 
-  {
-    const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 1);
-    EXPECT_NE(marker, nullptr);
-    EXPECT_EQ(marker->framenr, 1);
+    EXPECT_EQ(BKE_tracking_marker_get(&track, 0), &track.markers[0]);
+    EXPECT_EQ(BKE_tracking_marker_get(&track, 10), &track.markers[0]);
+    EXPECT_EQ(BKE_tracking_marker_get(&track, 20), &track.markers[0]);
+
+    BKE_tracking_track_free(&track);
   }
 
   {
-    const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 5);
-    EXPECT_NE(marker, nullptr);
-    EXPECT_EQ(marker->framenr, 1);
+    MovieTrackingTrack track = {nullptr};
+
+    addMarkerToTrack(&track, 1);
+    addMarkerToTrack(&track, 10);
+
+    {
+      const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 1);
+      EXPECT_NE(marker, nullptr);
+      EXPECT_EQ(marker->framenr, 1);
+    }
+
+    {
+      const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 5);
+      EXPECT_NE(marker, nullptr);
+      EXPECT_EQ(marker->framenr, 1);
+    }
+
+    BKE_tracking_track_free(&track);
   }
 
-  BKE_tracking_track_free(&track);
+  {
+    {
+      MovieTrackingTrack track = {nullptr};
+
+      addMarkerToTrack(&track, 1);
+      addMarkerToTrack(&track, 2);
+      addMarkerToTrack(&track, 10);
+
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 0), &track.markers[0]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 1), &track.markers[0]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 2), &track.markers[1]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 3), &track.markers[1]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 9), &track.markers[1]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 10), &track.markers[2]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 11), &track.markers[2]);
+
+      BKE_tracking_track_free(&track);
+    }
+  }
 }
 
 TEST_F(TrackingTest, BKE_tracking_marker_get_exact)
diff --git a/source/blender/makesdna/DNA_tracking_types.h b/source/blender/makesdna/DNA_tracking_types.h
index 908b06da2ce..5a8bbdc08a1 100644
--- a/source/blender/makesdna/DNA_tracking_types.h
+++ b/source/blender/makesdna/DNA_tracking_types.h
@@ -141,7 +141,7 @@ typedef struct MovieTrackingTrack {
   /** Count of markers in track. */
   int markersnr;
   /** Most recently used marker. */
-  int last_marker;
+  int _pad;
   /** Markers in track. */
   MovieTrackingMarker *markers;