Fix T86262: Tracking backwards fails after gap in track

The issue was caused by a prediction algorithm detecting tracking the
wrong way. Solved by passing tracking direction explicitly, so that
prediction will always happen correctly regardless of the state of the
Tracks context.

intern/libmv/intern/track_region.cc

@@ -39,6 +39,19 @@ using libmv::TrackRegionResult;
 
 namespace {
 
+TrackRegionOptions::Direction convertDirection(
+    libmv_TrackRegionDirection direction) {
+  switch (direction) {
+    case LIBMV_TRACK_REGION_FORWARD: return TrackRegionOptions::FORWARD;
+    case LIBMV_TRACK_REGION_BACKWARD: return TrackRegionOptions::BACKWARD;
+  }
+
+  LOG(FATAL) << "Unhandled tracking direction " << direction
+             << ", should never happen.";
+
+  return TrackRegionOptions::FORWARD;
+}
+
 TrackRegionOptions::Mode convertMotionModelToMode(int motion_model) {
   switch (motion_model) {
 #define LIBMV_CONVERT(the_model)                                               \
@@ -65,6 +78,7 @@ TrackRegionOptions::Mode convertMotionModelToMode(int motion_model) {
 void libmv_configureTrackRegionOptions(
     const libmv_TrackRegionOptions& options,
     TrackRegionOptions* track_region_options) {
+  track_region_options->direction = convertDirection(options.direction);
   track_region_options->mode = convertMotionModelToMode(options.motion_model);
   track_region_options->minimum_correlation = options.minimum_correlation;
   track_region_options->max_iterations = options.num_iterations;

intern/libmv/intern/track_region.h

@@ -24,7 +24,13 @@
 extern "C" {
 #endif
 
+typedef enum libmv_TrackRegionDirection {
+  LIBMV_TRACK_REGION_FORWARD,
+  LIBMV_TRACK_REGION_BACKWARD,
+} libmv_TrackRegionDirection;
+
 typedef struct libmv_TrackRegionOptions {
+  libmv_TrackRegionDirection direction;
   int motion_model;
   int num_iterations;
   int use_brute;

intern/libmv/libmv/autotrack/autotrack.cc

@@ -115,14 +115,27 @@ FrameAccessor::Key GetMaskForMarker(const Marker& marker,
       marker.clip, marker.frame, marker.track, &region, mask);
 }
 
+PredictDirection getPredictDirection(const TrackRegionOptions* track_options) {
+  switch (track_options->direction) {
+    case TrackRegionOptions::FORWARD: return PredictDirection::FORWARD;
+    case TrackRegionOptions::BACKWARD: return PredictDirection::BACKWARD;
+  }
+
+  LOG(FATAL) << "Unhandled tracking direction " << track_options->direction
+             << ", should never happen.";
+
+  return PredictDirection::AUTO;
+}
+
 }  // namespace
 
 bool AutoTrack::TrackMarker(Marker* tracked_marker,
                             TrackRegionResult* result,
                             const TrackRegionOptions* track_options) {
   // Try to predict the location of the second marker.
+  const PredictDirection predict_direction = getPredictDirection(track_options);
   bool predicted_position = false;
-  if (PredictMarkerPosition(tracks_, tracked_marker)) {
+  if (PredictMarkerPosition(tracks_, predict_direction, tracked_marker)) {
     LG << "Successfully predicted!";
     predicted_position = true;
   } else {

intern/libmv/libmv/autotrack/predict_tracks.cc

@@ -225,7 +225,9 @@ void RunPrediction(const vector<Marker*> previous_markers,
 
 }  // namespace
 
-bool PredictMarkerPosition(const Tracks& tracks, Marker* marker) {
+bool PredictMarkerPosition(const Tracks& tracks,
+                           const PredictDirection direction,
+                           Marker* marker) {
   // Get all markers for this clip and track.
   vector<Marker> markers;
   tracks.GetMarkersForTrackInClip(marker->clip, marker->track, &markers);
@@ -290,9 +292,17 @@ bool PredictMarkerPosition(const Tracks& tracks, Marker* marker) {
   }
 
   bool predict_forward = false;
-  if (backward_scan_end <= backward_scan_begin) {
-    // TODO(keir): Add smarter handling and detecting of consecutive frames!
-    predict_forward = true;
+  switch (direction) {
+    case PredictDirection::AUTO:
+      if (backward_scan_end <= backward_scan_begin) {
+        // TODO(keir): Add smarter handling and detecting of consecutive frames!
+        predict_forward = true;
+      }
+      break;
+
+    case PredictDirection::FORWARD: predict_forward = true; break;
+
+    case PredictDirection::BACKWARD: predict_forward = false; break;
   }
 
   const int max_frames_to_predict_from = 20;

intern/libmv/libmv/autotrack/predict_tracks.h

@@ -28,9 +28,27 @@ namespace mv {
 class Tracks;
 struct Marker;
 
+enum class PredictDirection {
+  // Detect direction in which to predict marker position based on an existing
+  // Tracks context. Prediction will happen in the preferred direction of a
+  // missing information.
+  // If markers exists to the both sides of the given one the prediction
+  // direction is preferred to be forward.
+  AUTO,
+
+  // Predict position of the marker from the past to the future (used for
+  // forward tracking).
+  FORWARD,
+
+  // Predict position from the future to the past (used for backward tracking).
+  BACKWARD,
+};
+
 // Predict the position of the given marker, and update it accordingly. The
 // existing position will be overwritten.
-bool PredictMarkerPosition(const Tracks& tracks, Marker* marker);
+bool PredictMarkerPosition(const Tracks& tracks,
+                           const PredictDirection direction,
+                           Marker* marker);
 
 }  // namespace mv
 

intern/libmv/libmv/tracking/track_region.cc

@@ -116,7 +116,8 @@ using ceres::Jet;
 using ceres::JetOps;
 
 TrackRegionOptions::TrackRegionOptions()
-    : mode(TRANSLATION),
+    : direction(FORWARD),
+      mode(TRANSLATION),
       minimum_correlation(0),
       max_iterations(20),
       use_esm(true),

intern/libmv/libmv/tracking/track_region.h

@@ -30,6 +30,12 @@ namespace libmv {
 struct TrackRegionOptions {
   TrackRegionOptions();
 
+  enum Direction {
+    FORWARD,
+    BACKWARD,
+  };
+  Direction direction;
+
   enum Mode {
     TRANSLATION,
     TRANSLATION_ROTATION,

source/blender/blenkernel/intern/tracking_auto.c

@@ -386,7 +386,8 @@ static void autotrack_context_init_tracks_for_clip(AutoTrackContext *context, in
     autotrack_track->track = track;
     autotrack_track->is_trackable = autotrack_is_track_trackable(context, autotrack_track);
 
-    tracking_configure_tracker(track, NULL, &autotrack_track->track_region_options);
+    tracking_configure_tracker(
+        track, NULL, context->is_backwards, &autotrack_track->track_region_options);
   }
 }
 

source/blender/blenkernel/intern/tracking_region_tracker.c

@@ -183,8 +183,11 @@ static ImBuf *tracking_context_get_reference_ibuf(MovieClip *clip,
 /* Fill in libmv tracker options structure with settings need to be used to perform track. */
 void tracking_configure_tracker(const MovieTrackingTrack *track,
                                 float *mask,
+                                const bool is_backwards,
                                 libmv_TrackRegionOptions *options)
 {
+  options->direction = is_backwards ? LIBMV_TRACK_REGION_BACKWARD : LIBMV_TRACK_REGION_FORWARD;
+
   /* TODO(sergey): Use explicit conversion, so that options are decoupled between the Libmv library
    * and enumerator values in DNA. */
   options->motion_model = track->motion_model;
@@ -220,6 +223,7 @@ static bool configure_and_run_tracker(ImBuf *destination_ibuf,
                                       int reference_search_area_width,
                                       int reference_search_area_height,
                                       float *mask,
+                                      const bool is_backward,
                                       double dst_pixel_x[5],
                                       double dst_pixel_y[5])
 {
@@ -248,7 +252,7 @@ static bool configure_and_run_tracker(ImBuf *destination_ibuf,
       destination_ibuf, track, marker, &new_search_area_width, &new_search_area_height);
 
   /* configure the tracker */
-  tracking_configure_tracker(track, mask, &options);
+  tracking_configure_tracker(track, mask, is_backward, &options);
 
   /* Convert the marker corners and center into pixel coordinates in the
    * search/destination images. */
@@ -374,6 +378,7 @@ void BKE_tracking_refine_marker(MovieClip *clip,
                                       search_area_width,
                                       search_area_height,
                                       mask,
+                                      backwards,
                                       dst_pixel_x,
                                       dst_pixel_y);
 

source/blender/blenkernel/tracking_private.h

@@ -111,6 +111,7 @@ struct libmv_TrackRegionOptions;
 
 void tracking_configure_tracker(const MovieTrackingTrack *track,
                                 float *mask,
+                                bool is_backwards,
                                 struct libmv_TrackRegionOptions *options);
 
 struct MovieTrackingMarker *tracking_get_keyframed_marker(struct MovieTrackingTrack *track,