Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / tracking_auto.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2011 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation,
22  *                 Sergey Sharybin
23  *                 Keir Mierle
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/tracking_auto.c
29  *  \ingroup bke
30  */
31
32 #include <stdlib.h>
33 #include "atomic_ops.h"
34
35 #include "MEM_guardedalloc.h"
36
37 #include "DNA_movieclip_types.h"
38 #include "DNA_object_types.h"   /* SELECT */
39
40 #include "BLI_utildefines.h"
41 #include "BLI_listbase.h"
42 #include "BLI_task.h"
43 #include "BLI_threads.h"
44 #include "BLI_math.h"
45
46 #include "BKE_movieclip.h"
47 #include "BKE_tracking.h"
48
49 #include "libmv-capi.h"
50 #include "tracking_private.h"
51
52 typedef struct AutoTrackOptions {
53         int clip_index;  /** Index of the clip this track belogs to. */
54         int track_index;  /* Index of the track in AutoTrack tracks structure. */
55         MovieTrackingTrack *track;  /* Pointer to an original track/ */
56         libmv_TrackRegionOptions track_region_options;  /* Options for the region
57                                                            tracker. */
58         bool use_keyframe_match;  /* Keyframe pattern matching. */
59
60         /* TODO(sergey): A bit awkward to keep it in here, only used to
61          * place a disabled marker once the tracking fails,
62          * Wither find a more clear way to do it or call it track context
63          * or state, not options.
64          */
65         bool is_failed;
66         int failed_frame;
67 } AutoTrackOptions;
68
69 typedef struct AutoTrackContext {
70         MovieClip *clips[MAX_ACCESSOR_CLIP];
71         int num_clips;
72
73         MovieClipUser user;
74         int frame_width, frame_height;
75
76         struct libmv_AutoTrack *autotrack;
77         TrackingImageAccessor *image_accessor;
78
79         int num_tracks;  /* Number of tracks being tracked. */
80         AutoTrackOptions *options;  /* Per-tracking track options. */
81
82         /* Array of all tracks, indexed by track_index. */
83         MovieTrackingTrack **tracks;
84
85         bool backwards;
86         bool sequence;
87         int first_frame;
88         int sync_frame;
89         bool first_sync;
90         SpinLock spin_lock;
91
92         bool step_ok;
93 } AutoTrackContext;
94
95 static void normalized_to_libmv_frame(const float normalized[2],
96                                       const int frame_dimensions[2],
97                                       float result[2])
98 {
99         result[0] = normalized[0] * frame_dimensions[0] - 0.5f;
100         result[1] = normalized[1] * frame_dimensions[1] - 0.5f;
101 }
102
103 static void normalized_relative_to_libmv_frame(const float normalized[2],
104                                                const float origin[2],
105                                                const int frame_dimensions[2],
106                                                float result[2])
107 {
108         result[0] = (normalized[0] + origin[0]) * frame_dimensions[0] - 0.5f;
109         result[1] = (normalized[1] + origin[1]) * frame_dimensions[1] - 0.5f;
110 }
111
112 static void libmv_frame_to_normalized(const float frame_coord[2],
113                                       const int frame_dimensions[2],
114                                       float result[2])
115 {
116         result[0] = (frame_coord[0] + 0.5f) / frame_dimensions[0];
117         result[1] = (frame_coord[1] + 0.5f) / frame_dimensions[1];
118 }
119
120 static void libmv_frame_to_normalized_relative(const float frame_coord[2],
121                                                const float origin[2],
122                                                const int frame_dimensions[2],
123                                                float result[2])
124 {
125         result[0] = (frame_coord[0] - origin[0]) / frame_dimensions[0];
126         result[1] = (frame_coord[1] - origin[1]) / frame_dimensions[1];
127 }
128
129 static void dna_marker_to_libmv_marker(/*const*/ MovieTrackingTrack *track,
130                                        /*const*/ MovieTrackingMarker *marker,
131                                        int clip,
132                                        int track_index,
133                                        int frame_width,
134                                        int frame_height,
135                                        bool backwards,
136                                        libmv_Marker *libmv_marker)
137 {
138         const int frame_dimensions[2] = {frame_width, frame_height};
139         int i;
140         libmv_marker->clip = clip;
141         libmv_marker->frame = marker->framenr;
142         libmv_marker->track = track_index;
143
144         normalized_to_libmv_frame(marker->pos,
145                                   frame_dimensions,
146                                   libmv_marker->center);
147         for (i = 0; i < 4; ++i) {
148                 normalized_relative_to_libmv_frame(marker->pattern_corners[i],
149                                                    marker->pos,
150                                                    frame_dimensions,
151                                                    libmv_marker->patch[i]);
152         }
153
154         normalized_relative_to_libmv_frame(marker->search_min,
155                                            marker->pos,
156                                            frame_dimensions,
157                                            libmv_marker->search_region_min);
158
159         normalized_relative_to_libmv_frame(marker->search_max,
160                                            marker->pos,
161                                            frame_dimensions,
162                                            libmv_marker->search_region_max);
163
164         /* TODO(sergey): All the markers does have 1.0 weight. */
165         libmv_marker->weight = 1.0f;
166
167         if (marker->flag & MARKER_TRACKED) {
168                 libmv_marker->source = LIBMV_MARKER_SOURCE_TRACKED;
169         }
170         else {
171                 libmv_marker->source = LIBMV_MARKER_SOURCE_MANUAL;
172         }
173         libmv_marker->status = LIBMV_MARKER_STATUS_UNKNOWN;
174         libmv_marker->model_type = LIBMV_MARKER_MODEL_TYPE_POINT;
175         libmv_marker->model_id = 0;
176
177         /* TODO(sergey): We currently don't support reference marker from
178          * different clip.
179          */
180         libmv_marker->reference_clip = clip;
181
182         if (track->pattern_match == TRACK_MATCH_KEYFRAME) {
183                 MovieTrackingMarker *keyframe_marker =
184                         tracking_get_keyframed_marker(track,
185                                                       marker->framenr,
186                                                       backwards);
187                 libmv_marker->reference_frame = keyframe_marker->framenr;
188         }
189         else {
190                 libmv_marker->reference_frame = backwards ?
191                                                 marker->framenr - 1 :
192                                                 marker->framenr;
193         }
194
195         libmv_marker->disabled_channels =
196                 ((track->flag & TRACK_DISABLE_RED)   ? LIBMV_MARKER_CHANNEL_R : 0) |
197                 ((track->flag & TRACK_DISABLE_GREEN) ? LIBMV_MARKER_CHANNEL_G : 0) |
198                 ((track->flag & TRACK_DISABLE_BLUE)  ? LIBMV_MARKER_CHANNEL_B : 0);
199 }
200
201 static void libmv_marker_to_dna_marker(libmv_Marker *libmv_marker,
202                                        int frame_width,
203                                        int frame_height,
204                                        MovieTrackingMarker *marker)
205 {
206         const int frame_dimensions[2] = {frame_width, frame_height};
207         int i;
208         marker->framenr = libmv_marker->frame;
209
210         libmv_frame_to_normalized(libmv_marker->center,
211                                   frame_dimensions,
212                                   marker->pos);
213         for (i = 0; i < 4; ++i) {
214                 libmv_frame_to_normalized_relative(libmv_marker->patch[i],
215                                                    libmv_marker->center,
216                                                    frame_dimensions,
217                                                    marker->pattern_corners[i]);
218         }
219
220         libmv_frame_to_normalized_relative(libmv_marker->search_region_min,
221                                            libmv_marker->center,
222                                            frame_dimensions,
223                                            marker->search_min);
224
225         libmv_frame_to_normalized_relative(libmv_marker->search_region_max,
226                                            libmv_marker->center,
227                                            frame_dimensions,
228                                            marker->search_max);
229
230         marker->flag = 0;
231         if (libmv_marker->source == LIBMV_MARKER_SOURCE_TRACKED) {
232                 marker->flag |= MARKER_TRACKED;
233         }
234         else {
235                 marker->flag &= ~MARKER_TRACKED;
236         }
237 }
238
239 static bool check_track_trackable(const MovieClip *clip,
240                                   MovieTrackingTrack *track,
241                                   const MovieClipUser *user)
242 {
243         if (TRACK_SELECTED(track) &&
244             (track->flag & (TRACK_LOCKED | TRACK_HIDDEN)) == 0)
245         {
246                 int frame = BKE_movieclip_remap_scene_to_clip_frame(clip, user->framenr);
247                 const MovieTrackingMarker *marker = BKE_tracking_marker_get(track, frame);
248                 return (marker->flag & MARKER_DISABLED) == 0;
249         }
250         return false;
251 }
252
253 /* Returns false if marker crossed margin area from frame bounds. */
254 static bool tracking_check_marker_margin(libmv_Marker *libmv_marker,
255                                          int margin,
256                                          int frame_width,
257                                          int frame_height)
258 {
259         float patch_min[2], patch_max[2];
260         float margin_left, margin_top, margin_right, margin_bottom;
261
262         INIT_MINMAX2(patch_min, patch_max);
263         minmax_v2v2_v2(patch_min, patch_max, libmv_marker->patch[0]);
264         minmax_v2v2_v2(patch_min, patch_max, libmv_marker->patch[1]);
265         minmax_v2v2_v2(patch_min, patch_max, libmv_marker->patch[2]);
266         minmax_v2v2_v2(patch_min, patch_max, libmv_marker->patch[3]);
267
268         margin_left   = max_ff(libmv_marker->center[0] - patch_min[0], margin);
269         margin_top    = max_ff(patch_max[1] - libmv_marker->center[1], margin);
270         margin_right  = max_ff(patch_max[0] - libmv_marker->center[0], margin);
271         margin_bottom = max_ff(libmv_marker->center[1] - patch_min[1], margin);
272
273         if (libmv_marker->center[0] < margin_left ||
274             libmv_marker->center[0] > frame_width - margin_right ||
275             libmv_marker->center[1] < margin_bottom ||
276             libmv_marker->center[1] > frame_height - margin_top)
277         {
278                 return false;
279         }
280
281         return true;
282 }
283
284 /* Provide Libmv side of auto track all information about given tracks. */
285 static void fill_autotrack_tracks(const int frame_width,
286                                   const int frame_height,
287                                   const ListBase *tracksbase,
288                                   const bool backwards,
289                                   struct libmv_AutoTrack *autotrack)
290 {
291         /* Count number of markers to be put to a context. */
292         size_t num_trackable_markers = 0;
293         for (MovieTrackingTrack *track = tracksbase->first;
294              track != NULL;
295              track = track->next)
296         {
297                 for (int i = 0; i < track->markersnr; ++i) {
298                         const MovieTrackingMarker *marker = track->markers + i;
299                         if ((marker->flag & MARKER_DISABLED) == 0) {
300                                 num_trackable_markers++;
301                         }
302                 }
303         }
304         /* Early output if we don't have any markers. */
305         if (num_trackable_markers == 0) {
306                 return;
307         }
308         /* Allocate memory for all the markers. */
309         libmv_Marker *libmv_markers = MEM_mallocN(
310                 sizeof(libmv_Marker) * num_trackable_markers,
311                 "libmv markers array");
312         /* Fill in markers array. */
313         int track_index = 0, num_filled_libmv_markers = 0;
314         for (MovieTrackingTrack *track = tracksbase->first;
315              track != NULL;
316              track = track->next)
317         {
318                 for (int i = 0; i < track->markersnr; ++i) {
319                         MovieTrackingMarker *marker = track->markers + i;
320                         if ((marker->flag & MARKER_DISABLED) != 0) {
321                                 continue;
322                         }
323                         dna_marker_to_libmv_marker(
324                                 track,
325                                 marker,
326                                 0,
327                                 track_index,
328                                 frame_width, frame_height,
329                                 backwards,
330                                 &libmv_markers[num_filled_libmv_markers++]);
331                 }
332                 /* Put all markers to autotrack at once. */
333                 track_index++;
334         }
335         /* Add all markers to autotrack. */
336         libmv_autoTrackSetMarkers(autotrack,
337                                   libmv_markers,
338                                   num_trackable_markers);
339         /* Free temporary memory. */
340         MEM_freeN(libmv_markers);
341 }
342
343 static void create_per_track_tracking_options(const MovieClip *clip,
344                                               const MovieClipUser *user,
345                                               const ListBase *tracksbase,
346                                               AutoTrackContext *context)
347 {
348         /* Count number of trackable tracks. */
349         for (MovieTrackingTrack *track = tracksbase->first;
350              track != NULL;
351              track = track->next)
352         {
353                 if (check_track_trackable(clip, track, user)) {
354                         context->num_tracks++;
355                 }
356         }
357         /* Allocate required memory. */
358         context->options =
359                 MEM_callocN(sizeof(AutoTrackOptions) * context->num_tracks,
360                             "auto track options");
361         /* Fill in all the settings. */
362         int i = 0, track_index = 0;
363         for (MovieTrackingTrack *track = tracksbase->first;
364              track != NULL;
365              track = track->next)
366         {
367                 if (!check_track_trackable(clip, track, user)) {
368                         ++track_index;
369                         continue;
370                 }
371                 AutoTrackOptions *options = &context->options[i++];
372                 /* TODO(sergey): Single clip only for now. */
373                 options->clip_index = 0;
374                 options->track_index = track_index;
375                 options->track = track;
376                 tracking_configure_tracker(track,
377                                            NULL,
378                                            &options->track_region_options);
379                 options->use_keyframe_match =
380                         track->pattern_match == TRACK_MATCH_KEYFRAME;
381                 context->tracks[track_index] = track;
382                 ++track_index;
383         }
384 }
385
386 AutoTrackContext *BKE_autotrack_context_new(MovieClip *clip,
387                                             MovieClipUser *user,
388                                             const bool backwards,
389                                             const bool sequence)
390 {
391         AutoTrackContext *context = MEM_callocN(sizeof(AutoTrackContext),
392                                                 "autotrack context");
393         MovieTracking *tracking = &clip->tracking;
394         ListBase *tracksbase = BKE_tracking_get_active_tracks(tracking);
395         int frame_width, frame_height;
396         /* get size of frame to convert normalized coordinates to a picture ones. */
397         BKE_movieclip_get_size(clip, user, &frame_width, &frame_height);
398         /* TODO(sergey): Currently using only a single clip. */
399         context->clips[0] = clip;
400         context->num_clips = 1;
401         context->user = *user;
402         context->user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
403         context->user.render_flag = 0;
404         context->frame_width = frame_width;
405         context->frame_height = frame_height;
406         context->backwards = backwards;
407         context->sequence = sequence;
408         context->first_frame = user->framenr;
409         context->sync_frame = user->framenr;
410         context->first_sync = true;
411         BLI_spin_init(&context->spin_lock);
412         const int num_total_tracks = BLI_listbase_count(tracksbase);
413         context->tracks =
414                 MEM_callocN(sizeof(MovieTrackingTrack *) * num_total_tracks,
415                             "auto track pointers");
416         /* Initialize image accessor. */
417         context->image_accessor =
418                 tracking_image_accessor_new(context->clips, 1,
419                                             context->tracks, num_total_tracks,
420                                             user->framenr);
421         /* Initialize auto track context and provide all information about currently
422          * tracked markers.
423          */
424         context->autotrack =
425                 libmv_autoTrackNew(context->image_accessor->libmv_accessor);
426         fill_autotrack_tracks(frame_width, frame_height,
427                               tracksbase,
428                               backwards,
429                               context->autotrack);
430         /* Create per-track tracking options. */
431         create_per_track_tracking_options(clip, user, tracksbase, context);
432         return context;
433 }
434
435 static void autotrack_context_step_cb(
436         void *__restrict userdata,
437         const int track,
438         const ParallelRangeTLS *__restrict UNUSED(tls))
439 {
440         AutoTrackContext *context = userdata;
441         const int frame_delta = context->backwards ? -1 : 1;
442
443         AutoTrackOptions *options = &context->options[track];
444         if (options->is_failed) {
445                 return;
446         }
447         libmv_Marker libmv_current_marker,
448                      libmv_reference_marker,
449                      libmv_tracked_marker;
450         libmv_TrackRegionResult libmv_result;
451         const int frame = BKE_movieclip_remap_scene_to_clip_frame(
452                 context->clips[options->clip_index],
453                 context->user.framenr);
454         BLI_spin_lock(&context->spin_lock);
455         const bool has_marker = libmv_autoTrackGetMarker(context->autotrack,
456                                                          options->clip_index,
457                                                          frame,
458                                                          options->track_index,
459                                                          &libmv_current_marker);
460         BLI_spin_unlock(&context->spin_lock);
461         /* Check whether we've got marker to sync with. */
462         if (!has_marker) {
463                 return;
464         }
465         /* Check whether marker is going outside of allowed frame margin. */
466         if (!tracking_check_marker_margin(&libmv_current_marker,
467                                           options->track->margin,
468                                           context->frame_width,
469                                           context->frame_height))
470         {
471                 return;
472         }
473         libmv_tracked_marker = libmv_current_marker;
474         libmv_tracked_marker.frame = frame + frame_delta;
475         /* Update reference frame. */
476         if (options->use_keyframe_match) {
477                 libmv_tracked_marker.reference_frame =
478                         libmv_current_marker.reference_frame;
479                 libmv_autoTrackGetMarker(context->autotrack,
480                                      options->clip_index,
481                                      libmv_tracked_marker.reference_frame,
482                                      options->track_index,
483                                      &libmv_reference_marker);
484         }
485         else {
486                 libmv_tracked_marker.reference_frame = frame;
487                 libmv_reference_marker = libmv_current_marker;
488         }
489         /* Perform actual tracking. */
490         if (libmv_autoTrackMarker(context->autotrack,
491                                   &options->track_region_options,
492                                   &libmv_tracked_marker,
493                                   &libmv_result))
494         {
495                 BLI_spin_lock(&context->spin_lock);
496                 libmv_autoTrackAddMarker(context->autotrack, &libmv_tracked_marker);
497                 BLI_spin_unlock(&context->spin_lock);
498         }
499         else {
500                 options->is_failed = true;
501                 options->failed_frame = frame + frame_delta;
502         }
503
504         /* Note: Atomic is probably not actually needed here, I doubt we could get
505          *       any other result than a true bool anyway.
506          *       But for sake of consistency, and since it costs nothing...
507          */
508         atomic_fetch_and_or_uint8((uint8_t *)&context->step_ok, true);
509 }
510
511 bool BKE_autotrack_context_step(AutoTrackContext *context)
512 {
513         const int frame_delta = context->backwards ? -1 : 1;
514         context->step_ok = false;
515
516         ParallelRangeSettings settings;
517         BLI_parallel_range_settings_defaults(&settings);
518         settings.use_threading = (context->num_tracks > 1);
519         BLI_task_parallel_range(0, context->num_tracks,
520                                 context,
521                                 autotrack_context_step_cb,
522                                 &settings);
523
524         /* Advance the frame. */
525         BLI_spin_lock(&context->spin_lock);
526         context->user.framenr += frame_delta;
527         BLI_spin_unlock(&context->spin_lock);
528         return context->step_ok;
529 }
530
531 void BKE_autotrack_context_sync(AutoTrackContext *context)
532 {
533         int newframe, frame_delta = context->backwards ? -1 : 1;
534         int frame;
535
536         BLI_spin_lock(&context->spin_lock);
537         newframe = context->user.framenr;
538         for (frame = context->sync_frame;
539              frame != (context->backwards ? newframe - 1 : newframe + 1);
540              frame += frame_delta)
541         {
542                 MovieTrackingMarker marker;
543                 libmv_Marker libmv_marker;
544                 int clip = 0;
545                 int track;
546                 for (track = 0; track < context->num_tracks; ++track) {
547                         AutoTrackOptions *options = &context->options[track];
548                         int track_frame = BKE_movieclip_remap_scene_to_clip_frame(
549                                 context->clips[options->clip_index], frame);
550                         if (options->is_failed) {
551                                 if (options->failed_frame == track_frame) {
552                                         MovieTrackingMarker *prev_marker =
553                                                 BKE_tracking_marker_get_exact(
554                                                         options->track,
555                                                         context->backwards
556                                                                 ? frame + 1
557                                                                 : frame - 1);
558                                         if (prev_marker) {
559                                                 marker = *prev_marker;
560                                                 marker.framenr = track_frame;
561                                                 marker.flag |= MARKER_DISABLED;
562                                                 BKE_tracking_marker_insert(options->track, &marker);
563                                                 continue;
564                                         }
565                                 }
566                                 if ((context->backwards && options->failed_frame > track_frame) ||
567                                     (!context->backwards && options->failed_frame < track_frame))
568                                 {
569                                         continue;
570                                 }
571                         }
572                         if (libmv_autoTrackGetMarker(context->autotrack,
573                                                      clip,
574                                                      track_frame,
575                                                      options->track_index,
576                                                      &libmv_marker))
577                         {
578                                 libmv_marker_to_dna_marker(&libmv_marker,
579                                                            context->frame_width,
580                                                            context->frame_height,
581                                                            &marker);
582                                 if (context->first_sync && frame == context->sync_frame) {
583                                         tracking_marker_insert_disabled(options->track,
584                                                                         &marker,
585                                                                         !context->backwards,
586                                                                         false);
587                                 }
588                                 BKE_tracking_marker_insert(options->track, &marker);
589                                 tracking_marker_insert_disabled(options->track,
590                                                                 &marker,
591                                                                 context->backwards,
592                                                                 false);
593                         }
594                 }
595         }
596         BLI_spin_unlock(&context->spin_lock);
597
598         for (int clip = 0; clip < context->num_clips; ++clip) {
599                 MovieTracking *tracking = &context->clips[clip]->tracking;
600                 BKE_tracking_dopesheet_tag_update(tracking);
601         }
602
603         context->sync_frame = newframe;
604         context->first_sync = false;
605 }
606
607 void BKE_autotrack_context_sync_user(AutoTrackContext *context,
608                                      MovieClipUser *user)
609 {
610         user->framenr = context->sync_frame;
611 }
612
613 void BKE_autotrack_context_finish(AutoTrackContext *context)
614 {
615         int clip_index;
616
617         for (clip_index = 0; clip_index < context->num_clips; ++clip_index) {
618                 MovieClip *clip = context->clips[clip_index];
619                 ListBase *plane_tracks_base =
620                         BKE_tracking_get_active_plane_tracks(&clip->tracking);
621                 MovieTrackingPlaneTrack *plane_track;
622
623                 for (plane_track = plane_tracks_base->first;
624                      plane_track;
625                      plane_track = plane_track->next)
626                 {
627                         if ((plane_track->flag & PLANE_TRACK_AUTOKEY) == 0) {
628                                 int track;
629                                 for (track = 0; track < context->num_tracks; ++track) {
630                                         if (BKE_tracking_plane_track_has_point_track(
631                                                     plane_track,
632                                                     context->options[track].track))
633                                         {
634                                                 BKE_tracking_track_plane_from_existing_motion(
635                                                         plane_track,
636                                                         context->first_frame);
637                                                 break;
638                                         }
639                                 }
640                         }
641                 }
642         }
643 }
644
645 void BKE_autotrack_context_free(AutoTrackContext *context)
646 {
647         libmv_autoTrackDestroy(context->autotrack);
648         tracking_image_accessor_destroy(context->image_accessor);
649         MEM_freeN(context->options);
650         MEM_freeN(context->tracks);
651         BLI_spin_end(&context->spin_lock);
652         MEM_freeN(context);
653 }