diff options
author | Sergey Sharybin <sergey@blender.org> | 2020-11-25 12:40:17 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey@blender.org> | 2021-01-18 18:38:40 +0300 |
commit | 0ca0d3366d4c79949914e229858f0a5477b9e6ec (patch) | |
tree | b89cd6245af0ac3d379cbb4bd85ff0ece27b967d /source | |
parent | f508292277d7a12c04b2cb2655622683ee4fef54 (diff) |
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.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/intern/tracking.c | 62 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/tracking_stabilize.c | 6 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/tracking_test.cc | 56 | ||||
-rw-r--r-- | source/blender/makesdna/DNA_tracking_types.h | 2 |
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; |