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