Fix T51850: Motion tracking - poor performance with keyframe matching on large video
[blender.git] / source / blender / blenkernel / intern / tracking_util.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_util.c
29  *  \ingroup bke
30  *
31  * This file contains implementation of function which are used
32  * by multiple tracking files but which should not be public.
33  */
34
35 #include <stddef.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "DNA_movieclip_types.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_math.h"
43 #include "BLI_listbase.h"
44 #include "BLI_ghash.h"
45 #include "BLI_string.h"
46 #include "BLI_string_utils.h"
47
48 #include "BLT_translation.h"
49
50 #include "BKE_movieclip.h"
51 #include "BKE_tracking.h"
52
53 #include "IMB_imbuf_types.h"
54 #include "IMB_imbuf.h"
55 #include "IMB_moviecache.h"
56
57 #include "tracking_private.h"
58
59 #include "libmv-capi.h"
60
61 /* Uncomment this to have caching-specific debug prints. */
62 // #define DEBUG_CACHE
63
64 #ifdef DEBUG_CACHE
65 #  define CACHE_PRINTF(...) printf(__VA_ARGS__)
66 #else
67 #  define CACHE_PRINTF(...)
68 #endif
69
70 /*********************** Tracks map *************************/
71
72 TracksMap *tracks_map_new(const char *object_name, bool is_camera, int num_tracks, int customdata_size)
73 {
74         TracksMap *map = MEM_callocN(sizeof(TracksMap), "TrackingsMap");
75
76         BLI_strncpy(map->object_name, object_name, sizeof(map->object_name));
77         map->is_camera = is_camera;
78
79         map->num_tracks = num_tracks;
80         map->customdata_size = customdata_size;
81
82         map->tracks = MEM_callocN(sizeof(MovieTrackingTrack) * num_tracks, "TrackingsMap tracks");
83
84         if (customdata_size)
85                 map->customdata = MEM_callocN(customdata_size * num_tracks, "TracksMap customdata");
86
87         map->hash = BLI_ghash_ptr_new("TracksMap hash");
88
89         BLI_spin_init(&map->spin_lock);
90
91         return map;
92 }
93
94 int tracks_map_get_size(TracksMap *map)
95 {
96         return map->num_tracks;
97 }
98
99 void tracks_map_get_indexed_element(TracksMap *map, int index, MovieTrackingTrack **track, void **customdata)
100 {
101         *track = &map->tracks[index];
102
103         if (map->customdata)
104                 *customdata = &map->customdata[index * map->customdata_size];
105 }
106
107 void tracks_map_insert(TracksMap *map, MovieTrackingTrack *track, void *customdata)
108 {
109         MovieTrackingTrack new_track = *track;
110
111         new_track.markers = MEM_dupallocN(new_track.markers);
112
113         map->tracks[map->ptr] = new_track;
114
115         if (customdata)
116                 memcpy(&map->customdata[map->ptr * map->customdata_size], customdata, map->customdata_size);
117
118         BLI_ghash_insert(map->hash, &map->tracks[map->ptr], track);
119
120         map->ptr++;
121 }
122
123 void tracks_map_merge(TracksMap *map, MovieTracking *tracking)
124 {
125         MovieTrackingTrack *track;
126         ListBase tracks = {NULL, NULL}, new_tracks = {NULL, NULL};
127         ListBase *old_tracks;
128         int a;
129
130         if (map->is_camera) {
131                 old_tracks = &tracking->tracks;
132         }
133         else {
134                 MovieTrackingObject *object = BKE_tracking_object_get_named(tracking, map->object_name);
135
136                 if (!object) {
137                         /* object was deleted by user, create new one */
138                         object = BKE_tracking_object_add(tracking, map->object_name);
139                 }
140
141                 old_tracks = &object->tracks;
142         }
143
144         /* duplicate currently operating tracks to temporary list.
145          * this is needed to keep names in unique state and it's faster to change names
146          * of currently operating tracks (if needed)
147          */
148         for (a = 0; a < map->num_tracks; a++) {
149                 MovieTrackingTrack *old_track;
150                 bool mapped_to_old = false;
151
152                 track = &map->tracks[a];
153
154                 /* find original of operating track in list of previously displayed tracks */
155                 old_track = BLI_ghash_lookup(map->hash, track);
156                 if (old_track) {
157                         if (BLI_findindex(old_tracks, old_track) != -1) {
158                                 BLI_remlink(old_tracks, old_track);
159
160                                 BLI_spin_lock(&map->spin_lock);
161
162                                 /* Copy flags like selection back to the track map. */
163                                 track->flag = old_track->flag;
164                                 track->pat_flag = old_track->pat_flag;
165                                 track->search_flag = old_track->search_flag;
166
167                                 /* Copy all the rest settings back from the map to the actual tracks. */
168                                 MEM_freeN(old_track->markers);
169                                 *old_track = *track;
170                                 old_track->markers = MEM_dupallocN(old_track->markers);
171
172                                 BLI_spin_unlock(&map->spin_lock);
173
174                                 BLI_addtail(&tracks, old_track);
175
176                                 mapped_to_old = true;
177                         }
178                 }
179
180                 if (mapped_to_old == false) {
181                         MovieTrackingTrack *new_track = BKE_tracking_track_duplicate(track);
182
183                         /* Update old-new track mapping */
184                         BLI_ghash_reinsert(map->hash, track, new_track, NULL, NULL);
185
186                         BLI_addtail(&tracks, new_track);
187                 }
188         }
189
190         /* move all tracks, which aren't operating */
191         track = old_tracks->first;
192         while (track) {
193                 MovieTrackingTrack *next = track->next;
194                 BLI_addtail(&new_tracks, track);
195                 track = next;
196         }
197
198         /* now move all tracks which are currently operating and keep their names unique */
199         track = tracks.first;
200         while (track) {
201                 MovieTrackingTrack *next = track->next;
202
203                 BLI_remlink(&tracks, track);
204
205                 track->next = track->prev = NULL;
206                 BLI_addtail(&new_tracks, track);
207
208                 BLI_uniquename(&new_tracks, track, CTX_DATA_(BLT_I18NCONTEXT_ID_MOVIECLIP, "Track"), '.',
209                                offsetof(MovieTrackingTrack, name), sizeof(track->name));
210
211                 track = next;
212         }
213
214         *old_tracks = new_tracks;
215 }
216
217 void tracks_map_free(TracksMap *map, void (*customdata_free)(void *customdata))
218 {
219         int i = 0;
220
221         BLI_ghash_free(map->hash, NULL, NULL);
222
223         for (i = 0; i < map->num_tracks; i++) {
224                 if (map->customdata && customdata_free)
225                         customdata_free(&map->customdata[i * map->customdata_size]);
226
227                 BKE_tracking_track_free(&map->tracks[i]);
228         }
229
230         if (map->customdata)
231                 MEM_freeN(map->customdata);
232
233         MEM_freeN(map->tracks);
234
235         BLI_spin_end(&map->spin_lock);
236
237         MEM_freeN(map);
238 }
239
240 /*********************** Space transformation functions *************************/
241
242 /* Three coordinate frames: Frame, Search, and Marker
243  * Two units: Pixels, Unified
244  * Notation: {coordinate frame}_{unit}; for example, "search_pixel" are search
245  * window relative coordinates in pixels, and "frame_unified" are unified 0..1
246  * coordinates relative to the entire frame.
247  */
248 static void unified_to_pixel(int frame_width, int frame_height,
249                              const float unified_coords[2], float pixel_coords[2])
250 {
251         pixel_coords[0] = unified_coords[0] * frame_width;
252         pixel_coords[1] = unified_coords[1] * frame_height;
253 }
254
255 static void marker_to_frame_unified(const MovieTrackingMarker *marker, const float marker_unified_coords[2],
256                                     float frame_unified_coords[2])
257 {
258         frame_unified_coords[0] = marker_unified_coords[0] + marker->pos[0];
259         frame_unified_coords[1] = marker_unified_coords[1] + marker->pos[1];
260 }
261
262 static void marker_unified_to_frame_pixel_coordinates(int frame_width, int frame_height,
263                                                       const MovieTrackingMarker *marker,
264                                                       const float marker_unified_coords[2],
265                                                       float frame_pixel_coords[2])
266 {
267         marker_to_frame_unified(marker, marker_unified_coords, frame_pixel_coords);
268         unified_to_pixel(frame_width, frame_height, frame_pixel_coords, frame_pixel_coords);
269 }
270
271 void tracking_get_search_origin_frame_pixel(int frame_width, int frame_height,
272                                             const MovieTrackingMarker *marker,
273                                             float frame_pixel[2])
274 {
275         /* Get the lower left coordinate of the search window and snap to pixel coordinates */
276         marker_unified_to_frame_pixel_coordinates(frame_width, frame_height, marker, marker->search_min, frame_pixel);
277         frame_pixel[0] = (int)frame_pixel[0];
278         frame_pixel[1] = (int)frame_pixel[1];
279 }
280
281 static void pixel_to_unified(int frame_width, int frame_height, const float pixel_coords[2], float unified_coords[2])
282 {
283         unified_coords[0] = pixel_coords[0] / frame_width;
284         unified_coords[1] = pixel_coords[1] / frame_height;
285 }
286
287 static void marker_unified_to_search_pixel(int frame_width, int frame_height,
288                                            const MovieTrackingMarker *marker,
289                                            const float marker_unified[2], float search_pixel[2])
290 {
291         float frame_pixel[2];
292         float search_origin_frame_pixel[2];
293
294         marker_unified_to_frame_pixel_coordinates(frame_width, frame_height, marker, marker_unified, frame_pixel);
295         tracking_get_search_origin_frame_pixel(frame_width, frame_height, marker, search_origin_frame_pixel);
296         sub_v2_v2v2(search_pixel, frame_pixel, search_origin_frame_pixel);
297 }
298
299 static void search_pixel_to_marker_unified(int frame_width, int frame_height,
300                                            const MovieTrackingMarker *marker,
301                                            const float search_pixel[2], float marker_unified[2])
302 {
303         float frame_unified[2];
304         float search_origin_frame_pixel[2];
305
306         tracking_get_search_origin_frame_pixel(frame_width, frame_height, marker, search_origin_frame_pixel);
307         add_v2_v2v2(frame_unified, search_pixel, search_origin_frame_pixel);
308         pixel_to_unified(frame_width, frame_height, frame_unified, frame_unified);
309
310         /* marker pos is in frame unified */
311         sub_v2_v2v2(marker_unified, frame_unified, marker->pos);
312 }
313
314 /* Each marker has 5 coordinates associated with it that get warped with
315  * tracking: the four corners ("pattern_corners"), and the center ("pos").
316  * This function puts those 5 points into the appropriate frame for tracking
317  * (the "search" coordinate frame).
318  */
319 void tracking_get_marker_coords_for_tracking(int frame_width, int frame_height,
320                                              const MovieTrackingMarker *marker,
321                                              double search_pixel_x[5], double search_pixel_y[5])
322 {
323         int i;
324         float unified_coords[2];
325         float pixel_coords[2];
326
327         /* Convert the corners into search space coordinates. */
328         for (i = 0; i < 4; i++) {
329                 marker_unified_to_search_pixel(frame_width, frame_height, marker, marker->pattern_corners[i], pixel_coords);
330                 search_pixel_x[i] = pixel_coords[0] - 0.5f;
331                 search_pixel_y[i] = pixel_coords[1] - 0.5f;
332         }
333
334         /* Convert the center position (aka "pos"); this is the origin */
335         unified_coords[0] = 0.0f;
336         unified_coords[1] = 0.0f;
337         marker_unified_to_search_pixel(frame_width, frame_height, marker, unified_coords, pixel_coords);
338
339         search_pixel_x[4] = pixel_coords[0] - 0.5f;
340         search_pixel_y[4] = pixel_coords[1] - 0.5f;
341 }
342
343 /* Inverse of above. */
344 void tracking_set_marker_coords_from_tracking(int frame_width, int frame_height, MovieTrackingMarker *marker,
345                                               const double search_pixel_x[5], const double search_pixel_y[5])
346 {
347         int i;
348         float marker_unified[2];
349         float search_pixel[2];
350
351         /* Convert the corners into search space coordinates. */
352         for (i = 0; i < 4; i++) {
353                 search_pixel[0] = search_pixel_x[i] + 0.5;
354                 search_pixel[1] = search_pixel_y[i] + 0.5;
355                 search_pixel_to_marker_unified(frame_width, frame_height, marker, search_pixel, marker->pattern_corners[i]);
356         }
357
358         /* Convert the center position (aka "pos"); this is the origin */
359         search_pixel[0] = search_pixel_x[4] + 0.5;
360         search_pixel[1] = search_pixel_y[4] + 0.5;
361         search_pixel_to_marker_unified(frame_width, frame_height, marker, search_pixel, marker_unified);
362
363         /* If the tracker tracked nothing, then "marker_unified" would be zero.
364          * Otherwise, the entire patch shifted, and that delta should be applied to
365          * all the coordinates.
366          */
367         for (i = 0; i < 4; i++) {
368                 marker->pattern_corners[i][0] -= marker_unified[0];
369                 marker->pattern_corners[i][1] -= marker_unified[1];
370         }
371
372         marker->pos[0] += marker_unified[0];
373         marker->pos[1] += marker_unified[1];
374 }
375
376 /*********************** General purpose utility functions *************************/
377
378 /* Place a disabled marker before or after specified ref_marker.
379  *
380  * If before is truth, disabled marker is placed before reference
381  * one, and it's placed after it otherwise.
382  *
383  * If there's already a marker at the frame where disabled one
384  * is expected to be placed, nothing will happen if overwrite
385  * is false.
386  */
387 void tracking_marker_insert_disabled(MovieTrackingTrack *track, const MovieTrackingMarker *ref_marker,
388                                      bool before, bool overwrite)
389 {
390         MovieTrackingMarker marker_new;
391
392         marker_new = *ref_marker;
393         marker_new.flag &= ~MARKER_TRACKED;
394         marker_new.flag |= MARKER_DISABLED;
395
396         if (before)
397                 marker_new.framenr--;
398         else
399                 marker_new.framenr++;
400
401         if (overwrite || !BKE_tracking_track_has_marker_at_frame(track, marker_new.framenr))
402                 BKE_tracking_marker_insert(track, &marker_new);
403 }
404
405
406 /* Fill in Libmv C-API camera intrinsics options from tracking structure. */
407 void tracking_cameraIntrinscisOptionsFromTracking(MovieTracking *tracking,
408                                                   int calibration_width, int calibration_height,
409                                                   libmv_CameraIntrinsicsOptions *camera_intrinsics_options)
410 {
411         MovieTrackingCamera *camera = &tracking->camera;
412         float aspy = 1.0f / tracking->camera.pixel_aspect;
413
414         camera_intrinsics_options->focal_length = camera->focal;
415
416         camera_intrinsics_options->principal_point_x = camera->principal[0];
417         camera_intrinsics_options->principal_point_y = camera->principal[1] * aspy;
418
419         switch (camera->distortion_model) {
420                 case TRACKING_DISTORTION_MODEL_POLYNOMIAL:
421                         camera_intrinsics_options->distortion_model = LIBMV_DISTORTION_MODEL_POLYNOMIAL;
422                         camera_intrinsics_options->polynomial_k1 = camera->k1;
423                         camera_intrinsics_options->polynomial_k2 = camera->k2;
424                         camera_intrinsics_options->polynomial_k3 = camera->k3;
425                         camera_intrinsics_options->polynomial_p1 = 0.0;
426                         camera_intrinsics_options->polynomial_p2 = 0.0;
427                         break;
428                 case TRACKING_DISTORTION_MODEL_DIVISION:
429                         camera_intrinsics_options->distortion_model = LIBMV_DISTORTION_MODEL_DIVISION;
430                         camera_intrinsics_options->division_k1 = camera->division_k1;
431                         camera_intrinsics_options->division_k2 = camera->division_k2;
432                         break;
433                 default:
434                         BLI_assert(!"Unknown distortion model");
435                         break;
436         }
437
438         camera_intrinsics_options->image_width = calibration_width;
439         camera_intrinsics_options->image_height = (int) (calibration_height * aspy);
440 }
441
442 void tracking_trackingCameraFromIntrinscisOptions(MovieTracking *tracking,
443                                                   const libmv_CameraIntrinsicsOptions *camera_intrinsics_options)
444 {
445         float aspy = 1.0f / tracking->camera.pixel_aspect;
446         MovieTrackingCamera *camera = &tracking->camera;
447
448         camera->focal = camera_intrinsics_options->focal_length;
449
450         camera->principal[0] = camera_intrinsics_options->principal_point_x;
451         camera->principal[1] = camera_intrinsics_options->principal_point_y / (double) aspy;
452
453         switch (camera_intrinsics_options->distortion_model) {
454                 case LIBMV_DISTORTION_MODEL_POLYNOMIAL:
455                         camera->distortion_model = TRACKING_DISTORTION_MODEL_POLYNOMIAL;
456                         camera->k1 = camera_intrinsics_options->polynomial_k1;
457                         camera->k2 = camera_intrinsics_options->polynomial_k2;
458                         camera->k3 = camera_intrinsics_options->polynomial_k3;
459                         break;
460                 case LIBMV_DISTORTION_MODEL_DIVISION:
461                         camera->distortion_model = TRACKING_DISTORTION_MODEL_DIVISION;
462                         camera->division_k1 = camera_intrinsics_options->division_k1;
463                         camera->division_k2 = camera_intrinsics_options->division_k2;
464                         break;
465                 default:
466                         BLI_assert(!"Unknown distortion model");
467                         break;
468         }
469 }
470
471 /* Get previous keyframed marker. */
472 MovieTrackingMarker *tracking_get_keyframed_marker(MovieTrackingTrack *track,
473                                                    int current_frame,
474                                                    bool backwards)
475 {
476         MovieTrackingMarker *marker_keyed = NULL;
477         MovieTrackingMarker *marker_keyed_fallback = NULL;
478         int a = BKE_tracking_marker_get(track, current_frame) - track->markers;
479
480         while (a >= 0 && a < track->markersnr) {
481                 int next = backwards ? a + 1 : a - 1;
482                 bool is_keyframed = false;
483                 MovieTrackingMarker *cur_marker = &track->markers[a];
484                 MovieTrackingMarker *next_marker = NULL;
485
486                 if (next >= 0 && next < track->markersnr)
487                         next_marker = &track->markers[next];
488
489                 if ((cur_marker->flag & MARKER_DISABLED) == 0) {
490                         /* If it'll happen so we didn't find a real keyframe marker,
491                          * fallback to the first marker in current tracked segment
492                          * as a keyframe.
493                          */
494                         if (next_marker == NULL) {
495                                 /* Could happen when trying to get reference marker for the fist
496                                  * one on the segment which isn't surrounded by disabled markers.
497                                  *
498                                  * There's no really good choice here, just use the reference
499                                  * marker which looks correct..
500                                  */
501                                 if (marker_keyed_fallback == NULL) {
502                                         marker_keyed_fallback = cur_marker;
503                                 }
504                         }
505                         else if (next_marker->flag & MARKER_DISABLED) {
506                                 if (marker_keyed_fallback == NULL)
507                                         marker_keyed_fallback = cur_marker;
508                         }
509
510                         is_keyframed |= (cur_marker->flag & MARKER_TRACKED) == 0;
511                 }
512
513                 if (is_keyframed) {
514                         marker_keyed = cur_marker;
515
516                         break;
517                 }
518
519                 a = next;
520         }
521
522         if (marker_keyed == NULL)
523                 marker_keyed = marker_keyed_fallback;
524
525         return marker_keyed;
526 }
527
528 /*********************** Frame accessr *************************/
529
530 typedef struct AccessCacheKey {
531         int clip_index;
532         int frame;
533         int downscale;
534         libmv_InputMode input_mode;
535         bool has_region;
536         float region_min[2], region_max[2];
537         int64_t transform_key;
538 } AccessCacheKey;
539
540 static unsigned int accesscache_hashhash(const void *key_v)
541 {
542         const AccessCacheKey *key = (const AccessCacheKey *) key_v;
543         /* TODP(sergey): Need better hashing here for faster frame access. */
544         return key->clip_index << 16 | key->frame;
545 }
546
547 static bool accesscache_hashcmp(const void *a_v, const void *b_v)
548 {
549         const AccessCacheKey *a = (const AccessCacheKey *) a_v;
550         const AccessCacheKey *b = (const AccessCacheKey *) b_v;
551         if (a->clip_index != b->clip_index ||
552             a->frame != b->frame ||
553             a->downscale != b->downscale ||
554             a->input_mode != b->input_mode ||
555             a->has_region != b->has_region ||
556             a->transform_key != b->transform_key)
557         {
558                 return true;
559         }
560         /* If there is region applied, compare it. */
561         if (a->has_region) {
562                 if (!equals_v2v2(a->region_min, b->region_min) ||
563                     !equals_v2v2(a->region_max, b->region_max))
564                 {
565                         return true;
566                 }
567         }
568         return false;
569 }
570
571 static void accesscache_construct_key(AccessCacheKey *key,
572                                       int clip_index,
573                                       int frame,
574                                       libmv_InputMode input_mode,
575                                       int downscale,
576                                       const libmv_Region *region,
577                                       int64_t transform_key)
578 {
579         key->clip_index = clip_index;
580         key->frame = frame;
581         key->input_mode = input_mode;
582         key->downscale = downscale;
583         key->has_region = (region != NULL);
584         if (key->has_region) {
585                 copy_v2_v2(key->region_min, region->min);
586                 copy_v2_v2(key->region_max, region->max);
587         }
588         key->transform_key = transform_key;
589 }
590
591 static void accesscache_put(TrackingImageAccessor *accessor,
592                             int clip_index,
593                             int frame,
594                             libmv_InputMode input_mode,
595                             int downscale,
596                             const libmv_Region *region,
597                             int64_t transform_key,
598                             ImBuf *ibuf)
599 {
600         AccessCacheKey key;
601         accesscache_construct_key(&key, clip_index, frame, input_mode, downscale,
602                                   region, transform_key);
603         IMB_moviecache_put(accessor->cache, &key, ibuf);
604 }
605
606 static ImBuf *accesscache_get(TrackingImageAccessor *accessor,
607                               int clip_index,
608                               int frame,
609                               libmv_InputMode input_mode,
610                               int downscale,
611                               const libmv_Region *region,
612                               int64_t transform_key)
613 {
614         AccessCacheKey key;
615         accesscache_construct_key(&key, clip_index, frame, input_mode, downscale,
616                                   region, transform_key);
617         return IMB_moviecache_get(accessor->cache, &key);
618 }
619
620 static ImBuf *accessor_get_preprocessed_ibuf(TrackingImageAccessor *accessor,
621                                              int clip_index,
622                                              int frame)
623 {
624         MovieClip *clip;
625         MovieClipUser user;
626         ImBuf *ibuf;
627         int scene_frame;
628
629         BLI_assert(clip_index < accessor->num_clips);
630
631         clip = accessor->clips[clip_index];
632         scene_frame = BKE_movieclip_remap_clip_to_scene_frame(clip, frame);
633         BKE_movieclip_user_set_frame(&user, scene_frame);
634         user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
635         user.render_flag = 0;
636         ibuf = BKE_movieclip_get_ibuf(clip, &user);
637
638         return ibuf;
639 }
640
641 static ImBuf *make_grayscale_ibuf_copy(ImBuf *ibuf)
642 {
643         ImBuf *grayscale = IMB_allocImBuf(ibuf->x, ibuf->y, 32, 0);
644         size_t size;
645         int i;
646
647         BLI_assert(ibuf->channels == 3 || ibuf->channels == 4);
648
649         /* TODO(sergey): Bummer, currently IMB API only allows to create 4 channels
650          * float buffer, so we do it manually here.
651          *
652          * Will generalize it later.
653          */
654         size = (size_t)grayscale->x * (size_t)grayscale->y * sizeof(float);
655         grayscale->channels = 1;
656         if ((grayscale->rect_float = MEM_mapallocN(size, "tracking grayscale image")) != NULL) {
657                 grayscale->mall |= IB_rectfloat;
658                 grayscale->flags |= IB_rectfloat;
659
660                 for (i = 0; i < grayscale->x * grayscale->y; ++i) {
661                         const float *pixel = ibuf->rect_float + ibuf->channels * i;
662
663                         grayscale->rect_float[i] = 0.2126f * pixel[0] +
664                                                    0.7152f * pixel[1] +
665                                                    0.0722f * pixel[2];
666                 }
667         }
668
669         return grayscale;
670 }
671
672 static void ibuf_to_float_image(const ImBuf *ibuf, libmv_FloatImage *float_image)
673 {
674         BLI_assert(ibuf->rect_float != NULL);
675         float_image->buffer = ibuf->rect_float;
676         float_image->width = ibuf->x;
677         float_image->height = ibuf->y;
678         float_image->channels = ibuf->channels;
679 }
680
681 static ImBuf *float_image_to_ibuf(libmv_FloatImage *float_image)
682 {
683         ImBuf *ibuf = IMB_allocImBuf(float_image->width, float_image->height, 32, 0);
684         size_t size = (size_t)ibuf->x * (size_t)ibuf->y * float_image->channels * sizeof(float);
685         ibuf->channels = float_image->channels;
686         if ((ibuf->rect_float = MEM_mapallocN(size, "tracking grayscale image")) != NULL) {
687                 ibuf->mall |= IB_rectfloat;
688                 ibuf->flags |= IB_rectfloat;
689
690                 memcpy(ibuf->rect_float, float_image->buffer, size);
691         }
692         return ibuf;
693 }
694
695 static ImBuf *accessor_get_ibuf(TrackingImageAccessor *accessor,
696                                 int clip_index,
697                                 int frame,
698                                 libmv_InputMode input_mode,
699                                 int downscale,
700                                 const libmv_Region *region,
701                                 const libmv_FrameTransform *transform)
702 {
703         ImBuf *ibuf, *orig_ibuf, *final_ibuf;
704         int64_t transform_key = 0;
705         if (transform != NULL) {
706                 transform_key = libmv_frameAccessorgetTransformKey(transform);
707         }
708         /* First try to get fully processed image from the cache. */
709         BLI_spin_lock(&accessor->cache_lock);
710         ibuf = accesscache_get(accessor,
711                                clip_index,
712                                frame,
713                                input_mode,
714                                downscale,
715                                region,
716                                transform_key);
717         BLI_spin_unlock(&accessor->cache_lock);
718         if (ibuf != NULL) {
719                 CACHE_PRINTF("Used cached buffer for frame %d\n", frame);
720                 /* This is a little heuristic here: if we re-used image once, this is
721                  * a high probability of the image to be related to a keyframe matched
722                  * reference image. Those images we don't want to be thrown away because
723                  * if we toss them out we'll be re-calculating them at the next
724                  * iteration.
725                  */
726                 ibuf->userflags |= IB_PERSISTENT;
727                 return ibuf;
728         }
729         CACHE_PRINTF("Calculate new buffer for frame %d\n", frame);
730         /* And now we do postprocessing of the original frame. */
731         orig_ibuf = accessor_get_preprocessed_ibuf(accessor, clip_index, frame);
732         if (orig_ibuf == NULL) {
733                 return NULL;
734         }
735         /* Cut a region if requested. */
736         if (region != NULL) {
737                 int width = region->max[0] - region->min[0],
738                     height = region->max[1] - region->min[1];
739
740                 /* If the requested region goes outside of the actual frame we still
741                  * return the requested region size, but only fill it's partially with
742                  * the data we can.
743                  */
744                 int clamped_origin_x = max_ii((int)region->min[0], 0),
745                     clamped_origin_y = max_ii((int)region->min[1], 0);
746                 int dst_offset_x = clamped_origin_x - (int)region->min[0],
747                     dst_offset_y = clamped_origin_y - (int)region->min[1];
748                 int clamped_width = width - dst_offset_x,
749                     clamped_height = height - dst_offset_y;
750                 clamped_width = min_ii(clamped_width, orig_ibuf->x - clamped_origin_x);
751                 clamped_height = min_ii(clamped_height, orig_ibuf->y - clamped_origin_y);
752
753                 final_ibuf = IMB_allocImBuf(width, height, 32, IB_rectfloat);
754
755                 if (orig_ibuf->rect_float != NULL) {
756                         IMB_rectcpy(final_ibuf, orig_ibuf,
757                                     dst_offset_x, dst_offset_y,
758                                     clamped_origin_x, clamped_origin_y,
759                                     clamped_width, clamped_height);
760                 }
761                 else {
762                         int y;
763                         /* TODO(sergey): We don't do any color space or alpha conversion
764                          * here. Probably Libmv is better to work in the linear space,
765                          * but keep sRGB space here for compatibility for now.
766                          */
767                         for (y = 0; y < clamped_height; ++y) {
768                                 int x;
769                                 for (x = 0; x < clamped_width; ++x) {
770                                         int src_x = x + clamped_origin_x,
771                                             src_y = y + clamped_origin_y;
772                                         int dst_x = x + dst_offset_x,
773                                             dst_y = y + dst_offset_y;
774                                         int dst_index = (dst_y * width + dst_x) * 4,
775                                             src_index = (src_y * orig_ibuf->x + src_x) * 4;
776                                         rgba_uchar_to_float(final_ibuf->rect_float + dst_index,
777                                                             (unsigned char *)orig_ibuf->rect +
778                                                                              src_index);
779                                 }
780                         }
781                 }
782         }
783         else {
784                 /* Libmv only works with float images,
785                  *
786                  * This would likely make it so loads of float buffers are being stored
787                  * in the cache which is nice on the one hand (faster re-use of the
788                  * frames) but on the other hand it bumps the memory usage up.
789                  */
790                 BLI_lock_thread(LOCK_MOVIECLIP);
791                 IMB_float_from_rect(orig_ibuf);
792                 BLI_unlock_thread(LOCK_MOVIECLIP);
793                 final_ibuf = orig_ibuf;
794         }
795         /* Downscale if needed. */
796         if (downscale > 0) {
797                 if (final_ibuf == orig_ibuf) {
798                         final_ibuf = IMB_dupImBuf(orig_ibuf);
799                 }
800                 IMB_scaleImBuf(final_ibuf,
801                                orig_ibuf->x / (1 << downscale),
802                                orig_ibuf->y / (1 << downscale));
803         }
804         /* Apply possible transformation. */
805         if (transform != NULL) {
806                 libmv_FloatImage input_image, output_image;
807                 ibuf_to_float_image(final_ibuf, &input_image);
808                 libmv_frameAccessorgetTransformRun(transform,
809                                                    &input_image,
810                                                    &output_image);
811                 if (final_ibuf != orig_ibuf) {
812                         IMB_freeImBuf(final_ibuf);
813                 }
814                 final_ibuf = float_image_to_ibuf(&output_image);
815                 libmv_floatImageDestroy(&output_image);
816         }
817         /* Transform number of channels. */
818         if (input_mode == LIBMV_IMAGE_MODE_RGBA) {
819                 BLI_assert(orig_ibuf->channels == 3 || orig_ibuf->channels == 4);
820                 /* pass */
821         }
822         else /* if (input_mode == LIBMV_IMAGE_MODE_MONO) */ {
823                 BLI_assert(input_mode == LIBMV_IMAGE_MODE_MONO);
824                 if (final_ibuf->channels != 1) {
825                         ImBuf *grayscale_ibuf = make_grayscale_ibuf_copy(final_ibuf);
826                         if (final_ibuf != orig_ibuf) {
827                                 /* We dereference original frame later. */
828                                 IMB_freeImBuf(final_ibuf);
829                         }
830                         final_ibuf = grayscale_ibuf;
831                 }
832         }
833         /* It's possible processing still didn't happen at this point,
834          * but we really need a copy of the buffer to be transformed
835          * and to be put to the cache.
836          */
837         if (final_ibuf == orig_ibuf) {
838                 final_ibuf = IMB_dupImBuf(orig_ibuf);
839         }
840         IMB_freeImBuf(orig_ibuf);
841         BLI_spin_lock(&accessor->cache_lock);
842         /* Put final buffer to cache. */
843         accesscache_put(accessor,
844                         clip_index,
845                         frame,
846                         input_mode,
847                         downscale,
848                         region,
849                         transform_key,
850                         final_ibuf);
851         return final_ibuf;
852 }
853
854 static libmv_CacheKey accessor_get_image_callback(
855                 struct libmv_FrameAccessorUserData *user_data,
856                 int clip_index,
857                 int frame,
858                 libmv_InputMode input_mode,
859                 int downscale,
860                 const libmv_Region *region,
861                 const libmv_FrameTransform *transform,
862                 float **destination,
863                 int *width,
864                 int *height,
865                 int *channels)
866 {
867         TrackingImageAccessor *accessor = (TrackingImageAccessor *) user_data;
868         ImBuf *ibuf;
869
870         BLI_assert(clip_index >= 0 && clip_index < accessor->num_clips);
871
872         ibuf = accessor_get_ibuf(accessor,
873                                  clip_index,
874                                  frame,
875                                  input_mode,
876                                  downscale,
877                                  region,
878                                  transform);
879
880         if (ibuf) {
881                 *destination = ibuf->rect_float;
882                 *width = ibuf->x;
883                 *height = ibuf->y;
884                 *channels = ibuf->channels;
885         }
886         else {
887                 *destination = NULL;
888                 *width = 0;
889                 *height = 0;
890                 *channels = 0;
891         }
892
893         return ibuf;
894 }
895
896 static void accessor_release_image_callback(libmv_CacheKey cache_key)
897 {
898         ImBuf *ibuf = (ImBuf *) cache_key;
899         IMB_freeImBuf(ibuf);
900 }
901
902 static libmv_CacheKey accessor_get_mask_for_track_callback(
903         libmv_FrameAccessorUserData *user_data,
904         int clip_index,
905         int frame,
906         int track_index,
907         const libmv_Region *region,
908         float **r_destination,
909         int *r_width,
910         int *r_height)
911 {
912         /* Perform sanity checks first. */
913         TrackingImageAccessor *accessor = (TrackingImageAccessor *) user_data;
914         BLI_assert(clip_index < accessor->num_clips);
915         BLI_assert(track_index < accessor->num_tracks);
916         MovieTrackingTrack *track = accessor->tracks[track_index];
917         /* Early output, track does not use mask. */
918         if ((track->algorithm_flag & TRACK_ALGORITHM_FLAG_USE_MASK) == 0) {
919                 return NULL;
920         }
921         MovieClip *clip = accessor->clips[clip_index];
922         /* Construct fake user so we can access movie clip. */
923         MovieClipUser user;
924         int scene_frame = BKE_movieclip_remap_clip_to_scene_frame(clip, frame);
925         BKE_movieclip_user_set_frame(&user, scene_frame);
926         user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
927         user.render_flag = 0;
928         /* Get frame width and height so we can convert stroke coordinates
929          * and other things from normalized to pixel space.
930          */
931         int frame_width, frame_height;
932         BKE_movieclip_get_size(clip, &user, &frame_width, &frame_height);
933         /* Actual mask sampling. */
934         MovieTrackingMarker *marker = BKE_tracking_marker_get_exact(track, frame);
935         const float region_min[2] = {region->min[0] - marker->pos[0] * frame_width,
936                                      region->min[1] - marker->pos[1] * frame_height};
937         const float region_max[2] = {region->max[0] - marker->pos[0] * frame_width,
938                                      region->max[1] - marker->pos[1] * frame_height};
939         *r_destination = tracking_track_get_mask_for_region(frame_width, frame_height,
940                                                             region_min,
941                                                             region_max,
942                                                             track);
943         *r_width = region->max[0] - region->min[0];
944         *r_height = region->max[1] - region->min[1];
945         return *r_destination;
946 }
947
948 static void accessor_release_mask_callback(libmv_CacheKey cache_key)
949 {
950         if (cache_key != NULL) {
951                 float *mask = (float *)cache_key;
952                 MEM_freeN(mask);
953         }
954 }
955
956 TrackingImageAccessor *tracking_image_accessor_new(MovieClip *clips[MAX_ACCESSOR_CLIP],
957                                                    int num_clips,
958                                                    MovieTrackingTrack **tracks,
959                                                    int num_tracks,
960                                                    int start_frame)
961 {
962         TrackingImageAccessor *accessor =
963                 MEM_callocN(sizeof(TrackingImageAccessor), "tracking image accessor");
964
965         BLI_assert(num_clips <= MAX_ACCESSOR_CLIP);
966
967         accessor->cache = IMB_moviecache_create("frame access cache",
968                                                 sizeof(AccessCacheKey),
969                                                 accesscache_hashhash,
970                                                 accesscache_hashcmp);
971
972         memcpy(accessor->clips, clips, num_clips * sizeof(MovieClip *));
973         accessor->num_clips = num_clips;
974         accessor->tracks = tracks;
975         accessor->num_tracks = num_tracks;
976         accessor->start_frame = start_frame;
977
978         accessor->libmv_accessor =
979                 libmv_FrameAccessorNew((libmv_FrameAccessorUserData *) accessor,
980                                        accessor_get_image_callback,
981                                        accessor_release_image_callback,
982                                        accessor_get_mask_for_track_callback,
983                                        accessor_release_mask_callback);
984
985         BLI_spin_init(&accessor->cache_lock);
986
987         return accessor;
988 }
989
990 void tracking_image_accessor_destroy(TrackingImageAccessor *accessor)
991 {
992         IMB_moviecache_free(accessor->cache);
993         libmv_FrameAccessorDestroy(accessor->libmv_accessor);
994         MEM_freeN(accessor);
995 }