Tomato: re-integrate ceres library with updates needed for tracking improvement
[blender.git] / source / blender / blenkernel / intern / tracking.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  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/blenkernel/intern/tracking.c
28  *  \ingroup bke
29  */
30
31 #include <stddef.h>
32 #include <limits.h>
33 #include <math.h>
34 #include <memory.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_gpencil_types.h"
39 #include "DNA_camera_types.h"
40 #include "DNA_movieclip_types.h"
41 #include "DNA_object_types.h"   /* SELECT */
42 #include "DNA_scene_types.h"
43
44 #include "BLI_utildefines.h"
45 #include "BLI_math.h"
46 #include "BLI_math_base.h"
47 #include "BLI_listbase.h"
48 #include "BLI_ghash.h"
49 #include "BLI_path_util.h"
50 #include "BLI_string.h"
51 #include "BLI_threads.h"
52
53 #include "BKE_global.h"
54 #include "BKE_tracking.h"
55 #include "BKE_movieclip.h"
56 #include "BKE_object.h"
57 #include "BKE_scene.h"
58
59 #include "IMB_imbuf_types.h"
60 #include "IMB_imbuf.h"
61
62 #ifdef WITH_LIBMV
63 #  include "libmv-capi.h"
64 #else
65 struct libmv_Features;
66 #endif
67
68 typedef struct MovieDistortion {
69         struct libmv_CameraIntrinsics *intrinsics;
70 } MovieDistortion;
71
72 static struct {
73         ListBase tracks;
74 } tracking_clipboard;
75
76 /*********************** common functions *************************/
77
78 void BKE_tracking_init_settings(MovieTracking *tracking)
79 {
80         tracking->camera.sensor_width = 35.0f;
81         tracking->camera.pixel_aspect = 1.0f;
82         tracking->camera.units = CAMERA_UNITS_MM;
83
84         tracking->settings.default_tracker = TRACKER_HYBRID;
85         tracking->settings.default_minimum_correlation = 0.75;
86         tracking->settings.default_pattern_size = 11;
87         tracking->settings.default_search_size = 61;
88         tracking->settings.default_pyramid_levels = 2;
89         tracking->settings.keyframe1 = 1;
90         tracking->settings.keyframe2 = 30;
91         tracking->settings.dist = 1;
92         tracking->settings.object_distance = 1;
93
94         tracking->stabilization.scaleinf = 1.0f;
95         tracking->stabilization.locinf = 1.0f;
96         tracking->stabilization.rotinf = 1.0f;
97         tracking->stabilization.maxscale = 2.0f;
98
99         BKE_tracking_new_object(tracking, "Camera");
100 }
101
102 void BKE_tracking_clamp_track(MovieTrackingTrack *track, int event)
103 {
104         int a;
105         float pat_min[2];
106         float pat_max[2];
107         float max_pyramid_level_factor = 1.0;
108
109         if (track->tracker == TRACKER_KLT) {
110                 max_pyramid_level_factor = 1 << (track->pyramid_levels - 1);
111         }
112
113         /* sort */
114         for (a = 0; a < 2; a++) {
115                 if (track->pat_min[a] > track->pat_max[a])
116                         SWAP(float, track->pat_min[a], track->pat_max[a]);
117
118                 if (track->search_min[a] > track->search_max[a])
119                         SWAP(float, track->search_min[a], track->search_max[a]);
120         }
121
122         /* compute the effective pattern size, which differs from the fine resolution
123          * pattern size for the pyramid KLT tracker */
124         for (a = 0; a < 2; a++) {
125                 pat_min[a] = max_pyramid_level_factor * track->pat_min[a];
126                 pat_max[a] = max_pyramid_level_factor * track->pat_max[a];
127         }
128
129         if (event == CLAMP_PAT_DIM) {
130                 for (a = 0; a < 2; a++) {
131                         /* search shouldn't be resized smaller than pattern */
132                         track->search_min[a] = MIN2(pat_min[a], track->search_min[a]);
133                         track->search_max[a] = MAX2(pat_max[a], track->search_max[a]);
134                 }
135         }
136         else if (event == CLAMP_PAT_POS) {
137                 float dim[2];
138
139                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
140
141                 for (a = 0; a < 2; a++) {
142                         /* pattern shouldn't be moved outside of search */
143                         if (pat_min[a] < track->search_min[a]) {
144                                 track->pat_min[a] = track->search_min[a] - (pat_min[a] - track->pat_min[a]);
145                                 track->pat_max[a] = track->pat_min[a] + dim[a];
146                         }
147                         if (track->pat_max[a] > track->search_max[a]) {
148                                 track->pat_max[a] = track->search_max[a] - (pat_max[a] - track->pat_max[a]);
149                                 track->pat_min[a] = track->pat_max[a] - dim[a];
150                         }
151                 }
152         }
153         else if (event == CLAMP_SEARCH_DIM) {
154                 for (a = 0; a < 2; a++) {
155                         /* search shouldn't be resized smaller than pattern */
156                         track->search_min[a] = MIN2(pat_min[a], track->search_min[a]);
157                         track->search_max[a] = MAX2(pat_max[a], track->search_max[a]);
158                 }
159         }
160         else if (event == CLAMP_SEARCH_POS) {
161                 float dim[2];
162
163                 sub_v2_v2v2(dim, track->search_max, track->search_min);
164
165                 for (a = 0; a < 2; a++) {
166                         /* search shouldn't be moved inside pattern */
167                         if (track->search_min[a] > pat_min[a]) {
168                                 track->search_min[a] = pat_min[a];
169                                 track->search_max[a] = track->search_min[a] + dim[a];
170                         }
171                         if (track->search_max[a] < pat_max[a]) {
172                                 track->search_max[a] = pat_max[a];
173                                 track->search_min[a] = track->search_max[a] - dim[a];
174                         }
175                 }
176         }
177         else if (event == CLAMP_PYRAMID_LEVELS || (event == CLAMP_SEARCH_DIM && track->tracker == TRACKER_KLT)) {
178                 float dim[2];
179                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
180                 {
181                         float search_ratio = 2.3f * max_pyramid_level_factor;
182
183                         /* resize the search area to something sensible based
184                          * on the number of pyramid levels */
185                         for (a = 0; a < 2; a++) {
186                                 track->search_min[a] = search_ratio * track->pat_min[a];
187                                 track->search_max[a] = search_ratio * track->pat_max[a];
188                         }
189                 }
190         }
191
192         /* marker's center should be in center of pattern */
193         if (event == CLAMP_PAT_DIM || event == CLAMP_PAT_POS) {
194                 float dim[2];
195
196                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
197
198                 for (a = 0; a < 2; a++) {
199                         track->pat_min[a] = -dim[a] / 2.0f;
200                         track->pat_max[a] = dim[a] / 2.0f;
201                 }
202         }
203 }
204
205 void BKE_tracking_track_flag(MovieTrackingTrack *track, int area, int flag, int clear)
206 {
207         if (area == TRACK_AREA_NONE)
208                 return;
209
210         if (clear) {
211                 if (area & TRACK_AREA_POINT)
212                         track->flag &= ~flag;
213                 if (area & TRACK_AREA_PAT)
214                         track->pat_flag &= ~flag;
215                 if (area & TRACK_AREA_SEARCH)
216                         track->search_flag &= ~flag;
217         }
218         else {
219                 if (area & TRACK_AREA_POINT)
220                         track->flag |= flag;
221                 if (area & TRACK_AREA_PAT)
222                         track->pat_flag |= flag;
223                 if (area & TRACK_AREA_SEARCH)
224                         track->search_flag |= flag;
225         }
226 }
227
228 MovieTrackingTrack *BKE_tracking_add_track(MovieTracking *tracking, ListBase *tracksbase, float x, float y,
229                                            int framenr, int width, int height)
230 {
231         MovieTrackingTrack *track;
232         MovieTrackingMarker marker;
233         MovieTrackingSettings *settings = &tracking->settings;
234
235         float half_pattern = (float)settings->default_pattern_size / 2.0f;
236         float half_search = (float)settings->default_search_size / 2.0f;
237         float pat[2], search[2];
238
239         pat[0] = half_pattern / (float)width;
240         pat[1] = half_pattern / (float)height;
241
242         search[0] = half_search / (float)width;
243         search[1] = half_search / (float)height;
244
245         track = MEM_callocN(sizeof(MovieTrackingTrack), "add_marker_exec track");
246         strcpy(track->name, "Track");
247
248         track->tracker = settings->default_tracker;
249         track->pyramid_levels = settings->default_pyramid_levels;
250         track->minimum_correlation = settings->default_minimum_correlation;
251         track->margin = settings->default_margin;
252         track->pattern_match = settings->default_pattern_match;
253         track->frames_limit = settings->default_frames_limit;
254         track->flag = settings->default_flag;
255
256         memset(&marker, 0, sizeof(marker));
257         marker.pos[0] = x;
258         marker.pos[1] = y;
259         marker.framenr = framenr;
260
261         copy_v2_v2(track->pat_max, pat);
262         negate_v2_v2(track->pat_min, pat);
263
264         copy_v2_v2(track->search_max, search);
265         negate_v2_v2(track->search_min, search);
266
267         BKE_tracking_insert_marker(track, &marker);
268
269         if (track->tracker == TRACKER_KLT)
270                 BKE_tracking_clamp_track(track, CLAMP_PYRAMID_LEVELS);
271
272         BLI_addtail(tracksbase, track);
273         BKE_track_unique_name(tracksbase, track);
274
275         return track;
276 }
277
278 MovieTrackingMarker *BKE_tracking_insert_marker(MovieTrackingTrack *track, MovieTrackingMarker *marker)
279 {
280         MovieTrackingMarker *old_marker = NULL;
281
282         if (track->markersnr)
283                 old_marker = BKE_tracking_exact_marker(track, marker->framenr);
284
285         if (old_marker) {
286                 *old_marker = *marker;
287
288                 return old_marker;
289         }
290         else {
291                 int a = track->markersnr;
292
293                 while (a--) {
294                         if (track->markers[a].framenr < marker->framenr)
295                                 break;
296                 }
297
298                 track->markersnr++;
299
300                 if (track->markers)
301                         track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
302                 else
303                         track->markers = MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
304
305                 memmove(track->markers + a + 2, track->markers + a + 1,
306                         (track->markersnr - a - 2) * sizeof(MovieTrackingMarker));
307                 track->markers[a + 1] = *marker;
308
309                 track->last_marker = a + 1;
310
311                 return &track->markers[a + 1];
312         }
313 }
314
315 void BKE_tracking_delete_marker(MovieTrackingTrack *track, int framenr)
316 {
317         int a = 0;
318
319         while (a < track->markersnr) {
320                 if (track->markers[a].framenr == framenr) {
321                         if (track->markersnr > 1) {
322                                 memmove(track->markers + a, track->markers + a + 1,
323                                         (track->markersnr - a - 1) * sizeof(MovieTrackingMarker));
324                                 track->markersnr--;
325                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
326                         }
327                         else {
328                                 MEM_freeN(track->markers);
329                                 track->markers = NULL;
330                                 track->markersnr = 0;
331                         }
332
333                         break;
334                 }
335
336                 a++;
337         }
338 }
339
340 MovieTrackingMarker *BKE_tracking_get_marker(MovieTrackingTrack *track, int framenr)
341 {
342         int a = track->markersnr - 1;
343
344         if (!track->markersnr)
345                 return NULL;
346
347         /* approximate pre-first framenr marker with first marker */
348         if (framenr < track->markers[0].framenr)
349                 return &track->markers[0];
350
351         if (track->last_marker < track->markersnr)
352                 a = track->last_marker;
353
354         if (track->markers[a].framenr <= framenr) {
355                 while (a < track->markersnr && track->markers[a].framenr <= framenr) {
356                         if (track->markers[a].framenr == framenr) {
357                                 track->last_marker = a;
358
359                                 return &track->markers[a];
360                         }
361                         a++;
362                 }
363
364                 /* if there's no marker for exact position, use nearest marker from left side */
365                 return &track->markers[a - 1];
366         }
367         else {
368                 while (a >= 0 && track->markers[a].framenr >= framenr) {
369                         if (track->markers[a].framenr == framenr) {
370                                 track->last_marker = a;
371
372                                 return &track->markers[a];
373                         }
374
375                         a--;
376                 }
377
378                 /* if there's no marker for exact position, use nearest marker from left side */
379                 return &track->markers[a];
380         }
381
382         return NULL;
383 }
384
385 MovieTrackingMarker *BKE_tracking_ensure_marker(MovieTrackingTrack *track, int framenr)
386 {
387         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
388
389         if (marker->framenr != framenr) {
390                 MovieTrackingMarker marker_new;
391
392                 marker_new = *marker;
393                 marker_new.framenr = framenr;
394
395                 BKE_tracking_insert_marker(track, &marker_new);
396                 marker = BKE_tracking_get_marker(track, framenr);
397         }
398
399         return marker;
400 }
401
402 MovieTrackingMarker *BKE_tracking_exact_marker(MovieTrackingTrack *track, int framenr)
403 {
404         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
405
406         if (marker->framenr != framenr)
407                 return NULL;
408
409         return marker;
410 }
411
412 int BKE_tracking_has_marker(MovieTrackingTrack *track, int framenr)
413 {
414         return BKE_tracking_exact_marker(track, framenr) != 0;
415 }
416
417 int BKE_tracking_has_enabled_marker(MovieTrackingTrack *track, int framenr)
418 {
419         MovieTrackingMarker *marker = BKE_tracking_exact_marker(track, framenr);
420
421         return marker && (marker->flag & MARKER_DISABLED) == 0;
422 }
423
424 void BKE_tracking_free_track(MovieTrackingTrack *track)
425 {
426         if (track->markers)
427                 MEM_freeN(track->markers);
428 }
429
430 static void put_disabled_marker(MovieTrackingTrack *track, MovieTrackingMarker *ref_marker, int before, int overwrite)
431 {
432         MovieTrackingMarker marker_new;
433
434         marker_new = *ref_marker;
435         marker_new.flag &= ~MARKER_TRACKED;
436         marker_new.flag |= MARKER_DISABLED;
437
438         if (before)
439                 marker_new.framenr--;
440         else
441                 marker_new.framenr++;
442
443         if (!BKE_tracking_has_marker(track, marker_new.framenr) || overwrite)
444                 BKE_tracking_insert_marker(track, &marker_new);
445 }
446
447 void BKE_tracking_clear_path(MovieTrackingTrack *track, int ref_frame, int action)
448 {
449         int a;
450
451         if (action == TRACK_CLEAR_REMAINED) {
452                 a = 1;
453
454                 while (a < track->markersnr) {
455                         if (track->markers[a].framenr > ref_frame) {
456                                 track->markersnr = a;
457                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
458
459                                 break;
460                         }
461
462                         a++;
463                 }
464
465                 if (track->markersnr)
466                         put_disabled_marker(track, &track->markers[track->markersnr - 1], 0, 1);
467         }
468         else if (action == TRACK_CLEAR_UPTO) {
469                 a = track->markersnr - 1;
470
471                 while (a >= 0) {
472                         if (track->markers[a].framenr <= ref_frame) {
473                                 memmove(track->markers, track->markers + a, (track->markersnr - a) * sizeof(MovieTrackingMarker));
474
475                                 track->markersnr = track->markersnr - a;
476                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
477
478                                 break;
479                         }
480
481                         a--;
482                 }
483
484                 if (track->markersnr)
485                         put_disabled_marker(track, &track->markers[0], 1, 1);
486         }
487         else if (action == TRACK_CLEAR_ALL) {
488                 MovieTrackingMarker *marker, marker_new;
489
490                 marker = BKE_tracking_get_marker(track, ref_frame);
491                 marker_new = *marker;
492
493                 MEM_freeN(track->markers);
494                 track->markers = NULL;
495                 track->markersnr = 0;
496
497                 BKE_tracking_insert_marker(track, &marker_new);
498
499                 put_disabled_marker(track, &marker_new, 1, 1);
500                 put_disabled_marker(track, &marker_new, 0, 1);
501         }
502 }
503
504 void BKE_tracking_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
505 {
506         int i = 0, a = 0, b = 0, tot;
507         MovieTrackingMarker *markers;
508
509         tot = dst_track->markersnr + src_track->markersnr;
510         markers = MEM_callocN(tot * sizeof(MovieTrackingMarker), "tmp tracking joined tracks");
511
512         while (a < src_track->markersnr || b < dst_track->markersnr) {
513                 if (b >= dst_track->markersnr) {
514                         markers[i] = src_track->markers[a++];
515                 }
516                 else if (a >= src_track->markersnr) {
517                         markers[i] = dst_track->markers[b++];
518                 }
519                 else if (src_track->markers[a].framenr < dst_track->markers[b].framenr) {
520                         markers[i] = src_track->markers[a++];
521                 }
522                 else if (src_track->markers[a].framenr > dst_track->markers[b].framenr) {
523                         markers[i] = dst_track->markers[b++];
524                 }
525                 else {
526                         if ((src_track->markers[a].flag & MARKER_DISABLED) == 0) {
527                                 if ((dst_track->markers[b].flag & MARKER_DISABLED) == 0) {
528                                         /* both tracks are enabled on this frame, so find the whole segment
529                                          * on which tracks are intersecting and blend tracks using linear
530                                          * interpolation to prevent jumps */
531
532                                         MovieTrackingMarker *marker_a, *marker_b;
533                                         int start_a = a, start_b = b, len = 0, frame = src_track->markers[a].framenr;
534                                         int j, inverse = 0;
535
536                                         inverse = (b == 0) ||
537                                                   (dst_track->markers[b - 1].flag & MARKER_DISABLED) ||
538                                                   (dst_track->markers[b - 1].framenr != frame - 1);
539
540                                         /* find length of intersection */
541                                         while (a < src_track->markersnr && b < dst_track->markersnr) {
542                                                 marker_a = &src_track->markers[a];
543                                                 marker_b = &dst_track->markers[b];
544
545                                                 if (marker_a->flag & MARKER_DISABLED || marker_b->flag & MARKER_DISABLED)
546                                                         break;
547
548                                                 if (marker_a->framenr != frame || marker_b->framenr != frame)
549                                                         break;
550
551                                                 frame++;
552                                                 len++;
553                                                 a++;
554                                                 b++;
555                                         }
556
557                                         a = start_a;
558                                         b = start_b;
559
560                                         /* linear interpolation for intersecting frames */
561                                         for (j = 0; j < len; j++) {
562                                                 float fac = 0.5f;
563
564                                                 if (len > 1)
565                                                         fac = 1.0f / (len - 1) * j;
566
567                                                 if (inverse)
568                                                         fac = 1.0f - fac;
569
570                                                 marker_a = &src_track->markers[a];
571                                                 marker_b = &dst_track->markers[b];
572
573                                                 markers[i] = dst_track->markers[b];
574                                                 interp_v2_v2v2(markers[i].pos, marker_b->pos, marker_a->pos, fac);
575                                                 a++;
576                                                 b++;
577                                                 i++;
578                                         }
579
580                                         /* this values will be incremented at the end of the loop cycle */
581                                         a--; b--; i--;
582                                 }
583                                 else markers[i] = src_track->markers[a];
584                         }
585                         else markers[i] = dst_track->markers[b];
586
587                         a++;
588                         b++;
589                 }
590
591                 i++;
592         }
593
594         MEM_freeN(dst_track->markers);
595
596         dst_track->markers = MEM_callocN(i*sizeof(MovieTrackingMarker), "tracking joined tracks");
597         memcpy(dst_track->markers, markers, i*sizeof(MovieTrackingMarker));
598
599         dst_track->markersnr = i;
600
601         MEM_freeN(markers);
602 }
603
604 static void tracking_tracks_free(ListBase *tracks)
605 {
606         MovieTrackingTrack *track;
607
608         for (track = tracks->first; track; track = track->next) {
609                 BKE_tracking_free_track(track);
610         }
611
612         BLI_freelistN(tracks);
613 }
614
615 static void tracking_reconstruction_free(MovieTrackingReconstruction *reconstruction)
616 {
617         if (reconstruction->cameras)
618                 MEM_freeN(reconstruction->cameras);
619 }
620
621 static void tracking_object_free(MovieTrackingObject *object)
622 {
623         tracking_tracks_free(&object->tracks);
624         tracking_reconstruction_free(&object->reconstruction);
625 }
626
627 static void tracking_objects_free(ListBase *objects)
628 {
629         MovieTrackingObject *object;
630
631         for (object = objects->first; object; object = object->next)
632                 tracking_object_free(object);
633
634         BLI_freelistN(objects);
635 }
636
637 static void tracking_dopesheet_free(MovieTrackingDopesheet *dopesheet)
638 {
639         MovieTrackingDopesheetChannel *channel;
640
641         channel = dopesheet->channels.first;
642         while (channel) {
643                 if (channel->segments) {
644                         MEM_freeN(channel->segments);
645                 }
646
647                 channel = channel->next;
648         }
649
650         BLI_freelistN(&dopesheet->channels);
651
652         dopesheet->channels.first = dopesheet->channels.last = NULL;
653         dopesheet->tot_channel = 0;
654 }
655
656 void BKE_tracking_free(MovieTracking *tracking)
657 {
658         tracking_tracks_free(&tracking->tracks);
659         tracking_reconstruction_free(&tracking->reconstruction);
660         tracking_objects_free(&tracking->objects);
661
662         if (tracking->stabilization.scaleibuf)
663                 IMB_freeImBuf(tracking->stabilization.scaleibuf);
664
665         if (tracking->camera.intrinsics)
666                 BKE_tracking_distortion_destroy(tracking->camera.intrinsics);
667
668         tracking_dopesheet_free(&tracking->dopesheet);
669 }
670
671 static MovieTrackingTrack *duplicate_track(MovieTrackingTrack *track)
672 {
673         MovieTrackingTrack *new_track;
674
675         new_track = MEM_callocN(sizeof(MovieTrackingTrack), "tracksMapMerge new_track");
676
677         *new_track = *track;
678         new_track->next = new_track->prev = NULL;
679
680         new_track->markers = MEM_dupallocN(new_track->markers);
681
682         return new_track;
683 }
684
685 /*********************** clipboard *************************/
686
687 void BKE_tracking_free_clipboard(void)
688 {
689         MovieTrackingTrack *track = tracking_clipboard.tracks.first, *next_track;
690
691         while (track) {
692                 next_track = track->next;
693
694                 BKE_tracking_free_track(track);
695                 MEM_freeN(track);
696
697                 track = next_track;
698         }
699 }
700
701 void BKE_tracking_clipboard_copy_tracks(MovieTracking *tracking, MovieTrackingObject *object)
702 {
703         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
704         MovieTrackingTrack *track = tracksbase->first;
705
706         BKE_tracking_free_clipboard();
707
708         while (track) {
709                 if (TRACK_SELECTED(track) && (track->flag & TRACK_HIDDEN) == 0) {
710                         MovieTrackingTrack *new_track = duplicate_track(track);
711
712                         BLI_addtail(&tracking_clipboard.tracks, new_track);
713                 }
714
715                 track = track->next;
716         }
717 }
718
719 int BKE_tracking_clipboard_has_tracks(void)
720 {
721         return tracking_clipboard.tracks.first != NULL;
722 }
723
724 void BKE_tracking_clipboard_paste_tracks(MovieTracking *tracking, MovieTrackingObject *object)
725 {
726         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
727         MovieTrackingTrack *track = tracking_clipboard.tracks.first;
728
729         while (track) {
730                 MovieTrackingTrack *new_track = duplicate_track(track);
731
732                 BLI_addtail(tracksbase, new_track);
733                 BKE_track_unique_name(tracksbase, new_track);
734
735                 track = track->next;
736         }
737 }
738
739 /*********************** tracks map *************************/
740
741 typedef struct TracksMap {
742         char object_name[MAX_NAME];
743         int is_camera;
744
745         int num_tracks;
746         int customdata_size;
747
748         char *customdata;
749         MovieTrackingTrack *tracks;
750
751         GHash *hash;
752
753         int ptr;
754 } TracksMap;
755
756 static TracksMap *tracks_map_new(const char *object_name, int is_camera, int num_tracks, int customdata_size)
757 {
758         TracksMap *map = MEM_callocN(sizeof(TracksMap), "TrackingsMap");
759
760         BLI_strncpy(map->object_name, object_name, sizeof(map->object_name));
761         map->is_camera = is_camera;
762
763         map->num_tracks = num_tracks;
764         map->customdata_size = customdata_size;
765
766         map->tracks = MEM_callocN(sizeof(MovieTrackingTrack)*num_tracks, "TrackingsMap tracks");
767
768         if (customdata_size)
769                 map->customdata = MEM_callocN(customdata_size*num_tracks, "TracksMap customdata");
770
771         map->hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "TracksMap hash");
772
773         return map;
774 }
775
776 static int tracks_map_size(TracksMap *map)
777 {
778         return map->num_tracks;
779 }
780
781 static void tracks_map_get(TracksMap *map, int index, MovieTrackingTrack **track, void **customdata)
782 {
783         *track = &map->tracks[index];
784
785         if (map->customdata)
786                 *customdata = &map->customdata[index*map->customdata_size];
787 }
788
789 static void tracks_map_insert(TracksMap *map, MovieTrackingTrack *track, void *customdata)
790 {
791         MovieTrackingTrack new_track = *track;
792
793         new_track.markers = MEM_dupallocN(new_track.markers);
794
795         map->tracks[map->ptr] = new_track;
796
797         if (customdata)
798                 memcpy(&map->customdata[map->ptr*map->customdata_size], customdata, map->customdata_size);
799
800         BLI_ghash_insert(map->hash, &map->tracks[map->ptr], track);
801
802         map->ptr++;
803 }
804
805 static void tracks_map_merge(TracksMap *map, MovieTracking *tracking)
806 {
807         MovieTrackingTrack *track;
808         MovieTrackingTrack *act_track = BKE_tracking_active_track(tracking);
809         MovieTrackingTrack *rot_track = tracking->stabilization.rot_track;
810         ListBase tracks = {NULL, NULL}, new_tracks = {NULL, NULL};
811         ListBase *old_tracks;
812         int a;
813
814         if (map->is_camera) {
815                 old_tracks = &tracking->tracks;
816         }
817         else {
818                 MovieTrackingObject *object = BKE_tracking_named_object(tracking, map->object_name);
819
820                 if (!object) {
821                         /* object was deleted by user, create new one */
822                         object = BKE_tracking_new_object(tracking, map->object_name);
823                 }
824
825                 old_tracks = &object->tracks;
826         }
827
828         /* duplicate currently operating tracks to temporary list.
829          * this is needed to keep names in unique state and it's faster to change names
830          * of currently operating tracks (if needed) */
831         for (a = 0; a < map->num_tracks; a++) {
832                 int replace_sel = 0, replace_rot = 0;
833                 MovieTrackingTrack *new_track, *old;
834
835                 track = &map->tracks[a];
836
837                 /* find original of operating track in list of previously displayed tracks */
838                 old = BLI_ghash_lookup(map->hash, track);
839                 if (old) {
840                         MovieTrackingTrack *cur = old_tracks->first;
841
842                         while (cur) {
843                                 if (cur == old)
844                                         break;
845
846                                 cur = cur->next;
847                         }
848
849                         /* original track was found, re-use flags and remove this track */
850                         if (cur) {
851                                 if (cur == act_track)
852                                         replace_sel = 1;
853                                 if (cur == rot_track)
854                                         replace_rot = 1;
855
856                                 track->flag = cur->flag;
857                                 track->pat_flag = cur->pat_flag;
858                                 track->search_flag = cur->search_flag;
859
860                                 BKE_tracking_free_track(cur);
861                                 BLI_freelinkN(old_tracks, cur);
862                         }
863                 }
864
865                 new_track = duplicate_track(track);
866
867                 BLI_ghash_remove(map->hash, track, NULL, NULL); /* XXX: are we actually need this */
868                 BLI_ghash_insert(map->hash, track, new_track);
869
870                 if (replace_sel)                /* update current selection in clip */
871                         tracking->act_track = new_track;
872
873                 if (replace_rot)                /* update track used for rotation stabilization */
874                         tracking->stabilization.rot_track = new_track;
875
876                 BLI_addtail(&tracks, new_track);
877         }
878
879         /* move all tracks, which aren't operating */
880         track = old_tracks->first;
881         while (track) {
882                 MovieTrackingTrack *next = track->next;
883
884                 track->next = track->prev = NULL;
885                 BLI_addtail(&new_tracks, track);
886
887                 track = next;
888         }
889
890         /* now move all tracks which are currently operating and keep their names unique */
891         track = tracks.first;
892         while (track) {
893                 MovieTrackingTrack *next = track->next;
894
895                 BLI_remlink(&tracks, track);
896
897                 track->next = track->prev = NULL;
898                 BLI_addtail(&new_tracks, track);
899
900                 BLI_uniquename(&new_tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
901
902                 track = next;
903         }
904
905         *old_tracks = new_tracks;
906 }
907
908 static void tracks_map_free(TracksMap *map, void (*customdata_free) (void *customdata))
909 {
910         int i = 0;
911
912         BLI_ghash_free(map->hash, NULL, NULL);
913
914         for (i = 0; i < map->num_tracks; i++) {
915                 if (map->customdata && customdata_free)
916                         customdata_free(&map->customdata[i*map->customdata_size]);
917
918                 BKE_tracking_free_track(&map->tracks[i]);
919         }
920
921         if (map->customdata)
922                 MEM_freeN(map->customdata);
923
924         MEM_freeN(map->tracks);
925         MEM_freeN(map);
926 }
927
928 /*********************** tracking *************************/
929
930 typedef struct TrackContext {
931 #ifdef WITH_LIBMV
932         float keyframed_pos[2];
933
934         struct libmv_RegionTracker *region_tracker;
935         float *patch;                   /* keyframed patch */
936 #else
937         int pad;
938 #endif
939 } TrackContext;
940
941 typedef struct MovieTrackingContext {
942         MovieClipUser user;
943         MovieClip *clip;
944         int clip_flag;
945
946         int first_time, frames;
947
948         MovieTrackingSettings settings;
949         TracksMap *tracks_map;
950
951         short backwards, sequence;
952         int sync_frame;
953 } MovieTrackingContext;
954
955 MovieTrackingContext *BKE_tracking_context_new(MovieClip *clip, MovieClipUser *user, short backwards, short sequence)
956 {
957         MovieTrackingContext *context = MEM_callocN(sizeof(MovieTrackingContext), "trackingContext");
958         MovieTracking *tracking = &clip->tracking;
959         MovieTrackingSettings *settings = &tracking->settings;
960         ListBase *tracksbase = BKE_tracking_get_tracks(tracking);
961         MovieTrackingTrack *track;
962         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
963         int num_tracks = 0;
964
965         context->settings = *settings;
966         context->backwards = backwards;
967         context->sync_frame = user->framenr;
968         context->first_time = TRUE;
969         context->sequence = sequence;
970
971         /* count */
972         track = tracksbase->first;
973         while (track) {
974                 if (TRACK_SELECTED(track) && (track->flag & (TRACK_LOCKED | TRACK_HIDDEN)) == 0) {
975                         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, user->framenr);
976
977                         if ((marker->flag & MARKER_DISABLED) == 0)
978                                 num_tracks++;
979                 }
980
981                 track = track->next;
982         }
983
984         if (num_tracks) {
985                 int width, height;
986
987                 context->tracks_map = tracks_map_new(object->name, object->flag & TRACKING_OBJECT_CAMERA,
988                                                      num_tracks, sizeof(TrackContext));
989
990                 BKE_movieclip_get_size(clip, user, &width, &height);
991
992                 /* create tracking data */
993                 track = tracksbase->first;
994                 while (track) {
995                         if (TRACK_SELECTED(track) && (track->flag & (TRACK_HIDDEN | TRACK_LOCKED)) == 0) {
996                                 MovieTrackingMarker *marker = BKE_tracking_get_marker(track, user->framenr);
997
998                                 if ((marker->flag & MARKER_DISABLED) == 0) {
999                                         TrackContext track_context;
1000
1001                                         memset(&track_context, 0, sizeof(TrackContext));
1002
1003 #ifdef WITH_LIBMV
1004                                         {
1005                                                 float patx = (int)((track->pat_max[0] - track->pat_min[0]) * width),
1006                                                       paty = (int)((track->pat_max[1] - track->pat_min[1]) * height);
1007
1008                                                 float search_size_x = (track->search_max[0] - track->search_min[0]) * width;
1009                                                 float search_size_y = (track->search_max[1] - track->search_min[1]) * height;
1010                                                 float pattern_size_x = (track->pat_max[0] - track->pat_min[0]) * width;
1011                                                 float pattern_size_y = (track->pat_max[1] - track->pat_min[1]) * height;
1012                                                 int wndx = (int)patx / 2, wndy = (int)paty / 2;
1013                                                 int half_wnd = MAX2(wndx, wndy);
1014
1015                                                         /* compute the maximum pyramid size */
1016                                                 float search_to_pattern_ratio = MIN2(search_size_x,  search_size_y)
1017                                                         / MAX2(pattern_size_x, pattern_size_y);
1018                                                 float log2_search_to_pattern_ratio = log(floor(search_to_pattern_ratio)) / M_LN2;
1019                                                 int max_pyramid_levels = floor(log2_search_to_pattern_ratio + 1);
1020
1021                                                 /* try to accommodate the user's choice of pyramid level in a way
1022                                                  * that doesn't cause the coarsest pyramid pattern to be larger
1023                                                  * than the search size */
1024                                                 int level = MIN2(track->pyramid_levels, max_pyramid_levels);
1025
1026                                                 struct libmv_RegionTracker *region_tracker;
1027
1028                                                 if (track->tracker == TRACKER_KLT) {
1029                                                         region_tracker = libmv_pyramidRegionTrackerNew(100, level, half_wnd,
1030                                                                                                        track->minimum_correlation);
1031                                                 }
1032                                                 else if (track->tracker == TRACKER_HYBRID) {
1033                                                         region_tracker = libmv_hybridRegionTrackerNew(100, half_wnd, track->minimum_correlation);
1034                                                 }
1035                                                 else if (track->tracker == TRACKER_SAD) {
1036                                                         region_tracker = libmv_bruteRegionTrackerNew(MAX2(wndx, wndy), track->minimum_correlation);
1037                                                 }
1038
1039                                                 track_context.region_tracker = region_tracker;
1040                                         }
1041 #endif
1042
1043                                         tracks_map_insert(context->tracks_map, track, &track_context);
1044                                 }
1045                         }
1046
1047                         track = track->next;
1048                 }
1049         }
1050
1051         context->clip = clip;
1052
1053         /* store needed clip flags passing to get_buffer functions
1054          * - MCLIP_USE_PROXY is needed to because timecode affects on movie clip
1055          *   only in case Proxy/Timecode flag is set, so store this flag to use
1056          *   timecodes properly but reset render size to SIZE_FULL so correct resolution
1057          *   would be used for images
1058          * - MCLIP_USE_PROXY_CUSTOM_DIR is needed because proxy/timecode files might
1059          *   be stored in a different location
1060          * ignore all the rest possible flags for now */
1061         context->clip_flag = clip->flag & MCLIP_TIMECODE_FLAGS;
1062
1063         context->user = *user;
1064         context->user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
1065         context->user.render_flag = 0;
1066
1067         if (!sequence)
1068                 BLI_begin_threaded_malloc();
1069
1070         return context;
1071 }
1072
1073 static void track_context_free(void *customdata)
1074 {
1075         TrackContext *track_context = (TrackContext *)customdata;
1076
1077 #if WITH_LIBMV
1078         if (track_context->region_tracker)
1079                 libmv_regionTrackerDestroy(track_context->region_tracker);
1080
1081         if (track_context->patch)
1082                 MEM_freeN(track_context->patch);
1083
1084 #else
1085                 (void) track_context;
1086 #endif
1087 }
1088
1089 void BKE_tracking_context_free(MovieTrackingContext *context)
1090 {
1091         if (!context->sequence)
1092                 BLI_end_threaded_malloc();
1093
1094         tracks_map_free(context->tracks_map, track_context_free);
1095
1096         MEM_freeN(context);
1097 }
1098
1099 /* zap channels from the imbuf that are disabled by the user. this can lead to
1100  * better tracks sometimes. however, instead of simply zeroing the channels
1101  * out, do a partial grayscale conversion so the display is better. */
1102 void BKE_tracking_disable_imbuf_channels(ImBuf *ibuf, int disable_red, int disable_green, int disable_blue,
1103                                          int grayscale)
1104 {
1105         int x, y;
1106         float scale;
1107
1108         if (!disable_red && !disable_green && !disable_blue && !grayscale)
1109                 return;
1110
1111         /* If only some components are selected, it's important to rescale the result
1112          * appropriately so that e.g. if only blue is selected, it's not zeroed out. */
1113         scale = (disable_red   ? 0.0f : 0.2126f) +
1114                 (disable_green ? 0.0f : 0.7152f) +
1115                 (disable_blue  ? 0.0f : 0.0722f);
1116
1117         for (y = 0; y < ibuf->y; y++) {
1118                 for (x = 0; x < ibuf->x; x++) {
1119                         int pixel = ibuf->x*y + x;
1120
1121                         if (ibuf->rect_float) {
1122                                 float *rrgbf = ibuf->rect_float + pixel*4;
1123                                 float r = disable_red   ? 0.0f : rrgbf[0];
1124                                 float g = disable_green ? 0.0f : rrgbf[1];
1125                                 float b = disable_blue  ? 0.0f : rrgbf[2];
1126
1127                                 if (grayscale) {
1128                                         float gray = (0.2126f*r + 0.7152f*g + 0.0722f*b) / scale;
1129
1130                                         rrgbf[0] = rrgbf[1] = rrgbf[2] = gray;
1131                                 }
1132                                 else {
1133                                         rrgbf[0] = r;
1134                                         rrgbf[1] = g;
1135                                         rrgbf[2] = b;
1136                                 }
1137                         }
1138                         else {
1139                                 char *rrgb = (char*)ibuf->rect + pixel*4;
1140                                 char r = disable_red   ? 0 : rrgb[0];
1141                                 char g = disable_green ? 0 : rrgb[1];
1142                                 char b = disable_blue  ? 0 : rrgb[2];
1143
1144                                 if (grayscale) {
1145                                         float gray = (0.2126f*r + 0.7152f*g + 0.0722f*b) / scale;
1146
1147                                         rrgb[0] = rrgb[1] = rrgb[2] = gray;
1148                                 }
1149                                 else {
1150                                         rrgb[0] = r;
1151                                         rrgb[1] = g;
1152                                         rrgb[2] = b;
1153                                 }
1154                         }
1155                 }
1156         }
1157
1158         if (ibuf->rect_float)
1159                 ibuf->userflags |= IB_RECT_INVALID;
1160 }
1161
1162 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track, int grayscale)
1163 {
1164         BKE_tracking_disable_imbuf_channels(ibuf, track->flag & TRACK_DISABLE_RED,
1165                         track->flag & TRACK_DISABLE_GREEN, track->flag & TRACK_DISABLE_BLUE, grayscale);
1166 }
1167
1168 static ImBuf *get_area_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1169                              float min[2], float max[2], int margin, int anchored, float pos[2], int origin[2])
1170 {
1171         ImBuf *tmpibuf;
1172         int x, y;
1173         int x1, y1, w, h;
1174         float mpos[2];
1175
1176         copy_v2_v2(mpos, marker->pos);
1177         if (anchored)
1178                 add_v2_v2(mpos, track->offset);
1179
1180         if (pos)
1181                 zero_v2(pos);
1182
1183         x = mpos[0]*ibuf->x;
1184         y = mpos[1]*ibuf->y;
1185
1186         w = (max[0] - min[0]) * ibuf->x;
1187         h = (max[1] - min[1]) * ibuf->y;
1188
1189         /* dimensions should be odd */
1190         w = w | 1;
1191         h = h | 1;
1192
1193         x1 = x - (int)(w * (-min[0] / (max[0] - min[0])));
1194         y1 = y - (int)(h * (-min[1] / (max[1] - min[1])));
1195
1196         if (ibuf->rect_float)
1197                 tmpibuf = IMB_allocImBuf(w + margin * 2, h + margin * 2, 32, IB_rectfloat);
1198         else
1199                 tmpibuf = IMB_allocImBuf(w + margin * 2, h + margin * 2, 32, IB_rect);
1200
1201         IMB_rectcpy(tmpibuf, ibuf, 0, 0, x1 - margin, y1 - margin, w + margin * 2, h + margin * 2);
1202
1203         if (pos != NULL) {
1204                 pos[0] = mpos[0] * ibuf->x - x1 + margin;
1205                 pos[1] = mpos[1] * ibuf->y - y1 + margin;
1206         }
1207
1208         if (origin != NULL) {
1209                 origin[0] = x1 - margin;
1210                 origin[1] = y1 - margin;
1211         }
1212
1213         if ((track->flag & TRACK_PREVIEW_GRAYSCALE) ||
1214            (track->flag & TRACK_DISABLE_RED)       ||
1215            (track->flag & TRACK_DISABLE_GREEN)     ||
1216            (track->flag & TRACK_DISABLE_BLUE))
1217         {
1218                 disable_imbuf_channels(tmpibuf, track, TRUE /* grayscale */);
1219         }
1220
1221         return tmpibuf;
1222 }
1223
1224 ImBuf *BKE_tracking_get_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1225                                       int margin, int anchored, float pos[2], int origin[2])
1226 {
1227         return get_area_imbuf(ibuf, track, marker, track->pat_min, track->pat_max, margin, anchored, pos, origin);
1228 }
1229
1230 ImBuf *BKE_tracking_get_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1231                                      int margin, int anchored, float pos[2], int origin[2])
1232 {
1233         return get_area_imbuf(ibuf, track, marker, track->search_min, track->search_max, margin, anchored, pos, origin);
1234 }
1235
1236 #ifdef WITH_LIBMV
1237 static float *get_search_floatbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1238                                   int *width_r, int *height_r, float pos[2], int origin[2])
1239 {
1240         ImBuf *tmpibuf;
1241         float *pixels, *fp;
1242         int x, y, width, height;
1243
1244         width = (track->search_max[0] - track->search_min[0]) * ibuf->x;
1245         height = (track->search_max[1] - track->search_min[1]) * ibuf->y;
1246
1247         tmpibuf = BKE_tracking_get_search_imbuf(ibuf, track, marker, 0, 0, pos, origin);
1248         disable_imbuf_channels(tmpibuf, track, FALSE /* don't grayscale */);
1249
1250         *width_r = width;
1251         *height_r = height;
1252
1253         fp = pixels = MEM_callocN(width * height * sizeof(float), "tracking floatBuf");
1254         for (y = 0; y < (int)height; y++) {
1255                 for (x = 0; x < (int)width; x++) {
1256                         int pixel = tmpibuf->x * y + x;
1257
1258                         if (tmpibuf->rect_float) {
1259                                 float *rrgbf = tmpibuf->rect_float + pixel * 4;
1260
1261                                 *fp = 0.2126 * rrgbf[0] + 0.7152 * rrgbf[1] + 0.0722 * rrgbf[2];
1262                         }
1263                         else {
1264                                 unsigned char *rrgb = (unsigned char*)tmpibuf->rect + pixel * 4;
1265
1266                                 *fp = (0.2126 * rrgb[0] + 0.7152 * rrgb[1] + 0.0722 * rrgb[2]) / 255.0f;
1267                         }
1268
1269                         fp++;
1270                 }
1271         }
1272
1273         IMB_freeImBuf(tmpibuf);
1274
1275         return pixels;
1276 }
1277
1278 static unsigned char *get_ucharbuf(ImBuf *ibuf)
1279 {
1280         int x, y;
1281         unsigned char *pixels, *cp;
1282
1283         cp = pixels = MEM_callocN(ibuf->x * ibuf->y * sizeof(unsigned char), "tracking ucharBuf");
1284         for (y = 0; y < ibuf->y; y++) {
1285                 for (x = 0; x < ibuf->x; x++) {
1286                         int pixel = ibuf->x * y + x;
1287
1288                         if (ibuf->rect_float) {
1289                                 const float *rrgbf = ibuf->rect_float + pixel*4;
1290                                 const float grey_f = 0.2126f * rrgbf[0] + 0.7152f * rrgbf[1] + 0.0722f * rrgbf[2];
1291
1292                                 *cp = FTOCHAR(grey_f);
1293                         }
1294                         else {
1295                                 const unsigned char *rrgb = (unsigned char*)ibuf->rect + pixel * 4;
1296
1297                                 *cp = 0.2126f * rrgb[0] + 0.7152f * rrgb[1] + 0.0722f * rrgb[2];
1298                         }
1299
1300                         cp++;
1301                 }
1302         }
1303
1304         return pixels;
1305 }
1306
1307 static ImBuf *get_frame_ibuf(MovieTrackingContext *context, int framenr)
1308 {
1309         ImBuf *ibuf;
1310         MovieClipUser user = context->user;
1311
1312         user.framenr = framenr;
1313
1314         ibuf = BKE_movieclip_get_ibuf_flag(context->clip, &user, context->clip_flag, MOVIECLIP_CACHE_SKIP);
1315
1316         return ibuf;
1317 }
1318
1319 static ImBuf *get_keyframed_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track,
1320                                  MovieTrackingMarker *marker, MovieTrackingMarker **marker_keyed)
1321 {
1322         int framenr = marker->framenr;
1323         int a = marker - track->markers;
1324
1325         *marker_keyed = marker;
1326
1327         while (a >= 0 && a < track->markersnr) {
1328                 int next = (context->backwards) ? a + 1 : a - 1;
1329                 int is_keyframed = FALSE;
1330                 MovieTrackingMarker *cur_marker = &track->markers[a];
1331                 MovieTrackingMarker *next_marker = NULL;
1332
1333                 if (next >= 0 && next < track->markersnr)
1334                         next_marker = &track->markers[next];
1335
1336                 /* if next mrker is disabled, stop searching keyframe and use current frame as keyframe */
1337                 if (next_marker && next_marker->flag & MARKER_DISABLED)
1338                         is_keyframed = TRUE;
1339
1340                 is_keyframed |= (cur_marker->flag & MARKER_TRACKED) == 0;
1341
1342                 if (is_keyframed) {
1343                         framenr = cur_marker->framenr;
1344                         *marker_keyed = cur_marker;
1345
1346                         break;
1347                 }
1348
1349                 a = next;
1350         }
1351
1352         return get_frame_ibuf(context, framenr);
1353 }
1354
1355 static ImBuf *get_adjust_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1356                               int curfra, MovieTrackingMarker **marker_keyed)
1357 {
1358         ImBuf *ibuf = NULL;
1359
1360         if (track->pattern_match == TRACK_MATCH_KEYFRAME) {
1361                 ibuf = get_keyframed_ibuf(context, track, marker, marker_keyed);
1362         }
1363         else {
1364                 ibuf = get_frame_ibuf(context, curfra);
1365
1366                 /* use current marker as keyframed position */
1367                 *marker_keyed = marker;
1368         }
1369
1370         return ibuf;
1371 }
1372
1373 #endif
1374
1375 void BKE_tracking_sync(MovieTrackingContext *context)
1376 {
1377         MovieTracking *tracking = &context->clip->tracking;
1378         int newframe;
1379
1380         tracks_map_merge(context->tracks_map, tracking);
1381
1382         if (context->backwards)
1383                 newframe = context->user.framenr + 1;
1384         else
1385                 newframe = context->user.framenr - 1;
1386
1387         context->sync_frame = newframe;
1388
1389         tracking->dopesheet.ok = FALSE;
1390 }
1391
1392 void BKE_tracking_sync_user(MovieClipUser *user, MovieTrackingContext *context)
1393 {
1394         user->framenr = context->sync_frame;
1395 }
1396
1397 int BKE_tracking_next(MovieTrackingContext *context)
1398 {
1399         ImBuf *ibuf_new;
1400         int curfra = context->user.framenr;
1401         int a, ok = FALSE, map_size;
1402
1403         map_size = tracks_map_size(context->tracks_map);
1404
1405         /* nothing to track, avoid unneeded frames reading to save time and memory */
1406         if (!map_size)
1407                 return FALSE;
1408
1409         if (context->backwards)
1410                 context->user.framenr--;
1411         else
1412                 context->user.framenr++;
1413
1414         ibuf_new = BKE_movieclip_get_ibuf_flag(context->clip, &context->user, context->clip_flag, MOVIECLIP_CACHE_SKIP);
1415         if (!ibuf_new)
1416                 return FALSE;
1417
1418         #pragma omp parallel for private(a) shared(ibuf_new, ok) if (map_size>1)
1419         for (a = 0; a < map_size; a++) {
1420                 TrackContext *track_context = NULL;
1421                 MovieTrackingTrack *track;
1422                 MovieTrackingMarker *marker;
1423
1424                 tracks_map_get(context->tracks_map, a, &track, (void**)&track_context);
1425
1426                 marker = BKE_tracking_exact_marker(track, curfra);
1427
1428                 if (marker && (marker->flag & MARKER_DISABLED) == 0) {
1429 #ifdef WITH_LIBMV
1430                         int width, height, origin[2], tracked = 0, need_readjust = 0;
1431                         float pos[2], margin[2], dim[2];
1432                         double x1, y1, x2, y2;
1433                         ImBuf *ibuf = NULL;
1434                         MovieTrackingMarker marker_new, *marker_keyed;
1435                         int onbound = FALSE, nextfra;
1436
1437                         if (track->pattern_match == TRACK_MATCH_KEYFRAME)
1438                                 need_readjust = context->first_time;
1439                         else
1440                                 need_readjust = TRUE;
1441
1442                         if (context->backwards)
1443                                 nextfra = curfra - 1;
1444                         else
1445                                 nextfra = curfra + 1;
1446
1447                         /* margin from frame boundaries */
1448                         sub_v2_v2v2(dim, track->pat_max, track->pat_min);
1449                         margin[0] = margin[1] = MAX2(dim[0], dim[1]) / 2.0f;
1450
1451                         margin[0] = MAX2(margin[0], (float)track->margin / ibuf_new->x);
1452                         margin[1] = MAX2(margin[1], (float)track->margin / ibuf_new->y);
1453
1454                         /* do not track markers which are too close to boundary */
1455                         if (marker->pos[0] < margin[0] || marker->pos[0] > 1.0f - margin[0] ||
1456                             marker->pos[1] < margin[1] || marker->pos[1] > 1.0f - margin[1])
1457                         {
1458                                 onbound = TRUE;
1459                         }
1460                         else {
1461                                 float *patch_new;
1462
1463                                 if (need_readjust) {
1464                                         /* calculate patch for keyframed position */
1465                                         ibuf = get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1466
1467                                         if (track_context->patch)
1468                                                 MEM_freeN(track_context->patch);
1469
1470                                         track_context->patch = get_search_floatbuf(ibuf, track, marker_keyed, &width, &height,
1471                                                                                    track_context->keyframed_pos, origin);
1472
1473                                         IMB_freeImBuf(ibuf);
1474                                 }
1475
1476                                 patch_new = get_search_floatbuf(ibuf_new, track, marker, &width, &height, pos, origin);
1477
1478                                 x1 = track_context->keyframed_pos[0];
1479                                 y1 = track_context->keyframed_pos[1];
1480
1481                                 x2 = pos[0];
1482                                 y2 = pos[1];
1483
1484                                 tracked = libmv_regionTrackerTrack(track_context->region_tracker, track_context->patch, patch_new,
1485                                                         width, height, x1, y1, &x2, &y2);
1486
1487                                 MEM_freeN(patch_new);
1488                         }
1489
1490                         if (tracked && !onbound && finite(x2) && finite(y2)) {
1491                                 if (context->first_time) {
1492                                         #pragma omp critical
1493                                         {
1494                                                 /* check if there's no keyframe/tracked markers before tracking marker.
1495                                                  * if so -- create disabled marker before currently tracking "segment" */
1496                                                 put_disabled_marker(track, marker, !context->backwards, 0);
1497                                         }
1498                                 }
1499
1500                                 memset(&marker_new, 0, sizeof(marker_new));
1501
1502                                 if (!onbound) {
1503                                         marker_new.pos[0] = (origin[0] + x2) / ibuf_new->x;
1504                                         marker_new.pos[1] = (origin[1] + y2) / ibuf_new->y;
1505                                 }
1506                                 else {
1507                                         copy_v2_v2(marker_new.pos, marker->pos);
1508                                 }
1509
1510                                 marker_new.flag |= MARKER_TRACKED;
1511                                 marker_new.framenr = nextfra;
1512
1513                                 #pragma omp critical
1514                                 {
1515                                         BKE_tracking_insert_marker(track, &marker_new);
1516                                 }
1517
1518                                 /* make currently tracked segment be finished with disabled marker */
1519                                 #pragma omp critical
1520                                 {
1521                                         put_disabled_marker(track, &marker_new, context->backwards, 0);
1522                                 }
1523                         }
1524                         else {
1525                                 marker_new = *marker;
1526
1527                                 marker_new.framenr = nextfra;
1528                                 marker_new.flag |= MARKER_DISABLED;
1529
1530                                 #pragma omp critical
1531                                 {
1532                                         BKE_tracking_insert_marker(track, &marker_new);
1533                                 }
1534                         }
1535
1536                         ok = TRUE;
1537 #endif
1538                 }
1539         }
1540
1541         IMB_freeImBuf(ibuf_new);
1542
1543         context->first_time = FALSE;
1544         context->frames++;
1545
1546         return ok;
1547 }
1548
1549 /*********************** camera solving *************************/
1550
1551 typedef struct MovieReconstructContext {
1552 #ifdef WITH_LIBMV
1553         struct libmv_Tracks *tracks;
1554         int keyframe1, keyframe2;
1555         short refine_flags;
1556
1557         struct libmv_Reconstruction *reconstruction;
1558 #endif
1559         char object_name[MAX_NAME];
1560         int is_camera;
1561         short motion_flag;
1562
1563         float focal_length;
1564         float principal_point[2];
1565         float k1, k2, k3;
1566
1567         float reprojection_error;
1568
1569         TracksMap *tracks_map;
1570
1571         int sfra, efra;
1572 } MovieReconstructContext;
1573
1574 typedef struct ReconstructProgressData {
1575         short *stop;
1576         short *do_update;
1577         float *progress;
1578         char *stats_message;
1579         int message_size;
1580 } ReconstructProgressData;
1581
1582 #if WITH_LIBMV
1583 static struct libmv_Tracks *create_libmv_tracks(ListBase *tracksbase, int width, int height)
1584 {
1585         int tracknr = 0;
1586         MovieTrackingTrack *track;
1587         struct libmv_Tracks *tracks = libmv_tracksNew();
1588
1589         track = tracksbase->first;
1590         while (track) {
1591                 int a = 0;
1592
1593                 for (a = 0; a < track->markersnr; a++) {
1594                         MovieTrackingMarker *marker = &track->markers[a];
1595
1596                         if ((marker->flag & MARKER_DISABLED) == 0) {
1597                                 libmv_tracksInsert(tracks, marker->framenr, tracknr,
1598                                                         marker->pos[0] * width, marker->pos[1] * height);
1599                         }
1600                 }
1601
1602                 track = track->next;
1603                 tracknr++;
1604         }
1605
1606         return tracks;
1607 }
1608
1609 static void retrieve_libmv_reconstruct_intrinscis(MovieReconstructContext *context, MovieTracking *tracking)
1610 {
1611         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
1612         struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_ReconstructionExtractIntrinsics(libmv_reconstruction);
1613
1614         float aspy = 1.0f / tracking->camera.pixel_aspect;
1615
1616         double focal_length, principal_x, principal_y, k1, k2, k3;
1617         int width, height;
1618
1619         libmv_CameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
1620                                       &k1, &k2, &k3, &width, &height);
1621
1622         tracking->camera.focal = focal_length;
1623         tracking->camera.principal[0] = principal_x;
1624
1625         tracking->camera.principal[1] = principal_y / aspy;
1626         tracking->camera.k1 = k1;
1627         tracking->camera.k2 = k2;
1628 }
1629
1630 static int retrieve_libmv_reconstruct_tracks(MovieReconstructContext *context, MovieTracking *tracking)
1631 {
1632         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
1633         MovieTrackingReconstruction *reconstruction = NULL;
1634         MovieReconstructedCamera *reconstructed;
1635         MovieTrackingTrack *track;
1636         ListBase *tracksbase =  NULL;
1637         int ok = TRUE, tracknr = 0, a, origin_set = FALSE;
1638         int sfra = context->sfra, efra = context->efra;
1639         float imat[4][4];
1640
1641         if (context->is_camera) {
1642                 tracksbase = &tracking->tracks;
1643                 reconstruction = &tracking->reconstruction;
1644         }
1645         else {
1646                 MovieTrackingObject *object = BKE_tracking_named_object(tracking, context->object_name);
1647
1648                 tracksbase = &object->tracks;
1649                 reconstruction = &object->reconstruction;
1650         }
1651
1652         unit_m4(imat);
1653
1654         track = tracksbase->first;
1655         while (track) {
1656                 double pos[3];
1657
1658                 if (libmv_reporojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
1659                         track->bundle_pos[0] = pos[0];
1660                         track->bundle_pos[1] = pos[1];
1661                         track->bundle_pos[2] = pos[2];
1662
1663                         track->flag |= TRACK_HAS_BUNDLE;
1664                         track->error = libmv_reporojectionErrorForTrack(libmv_reconstruction, tracknr);
1665                 }
1666                 else {
1667                         track->flag &= ~TRACK_HAS_BUNDLE;
1668                         ok = FALSE;
1669
1670                         printf("No bundle for track #%d '%s'\n", tracknr, track->name);
1671                 }
1672
1673                 track = track->next;
1674                 tracknr++;
1675         }
1676
1677         if (reconstruction->cameras)
1678                 MEM_freeN(reconstruction->cameras);
1679
1680         reconstruction->camnr = 0;
1681         reconstruction->cameras = NULL;
1682         reconstructed = MEM_callocN((efra - sfra + 1) * sizeof(MovieReconstructedCamera),
1683                                     "temp reconstructed camera");
1684
1685         for (a = sfra; a <= efra; a++) {
1686                 double matd[4][4];
1687
1688                 if (libmv_reporojectionCameraForImage(libmv_reconstruction, a, matd)) {
1689                         int i, j;
1690                         float mat[4][4];
1691                         float error = libmv_reporojectionErrorForImage(libmv_reconstruction, a);
1692
1693                         for (i = 0; i < 4; i++)
1694                                 for (j = 0; j < 4; j++)
1695                                         mat[i][j] = matd[i][j];
1696
1697                         if (!origin_set) {
1698                                 copy_m4_m4(imat, mat);
1699                                 invert_m4(imat);
1700                                 origin_set = TRUE;
1701                         }
1702
1703                         if (origin_set)
1704                                 mult_m4_m4m4(mat, imat, mat);
1705
1706                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
1707                         reconstructed[reconstruction->camnr].framenr = a;
1708                         reconstructed[reconstruction->camnr].error = error;
1709                         reconstruction->camnr++;
1710                 }
1711                 else {
1712                         ok = FALSE;
1713                         printf("No camera for frame %d\n", a);
1714                 }
1715         }
1716
1717         if (reconstruction->camnr) {
1718                 int size = reconstruction->camnr * sizeof(MovieReconstructedCamera);
1719                 reconstruction->cameras = MEM_callocN(size, "reconstructed camera");
1720                 memcpy(reconstruction->cameras, reconstructed, size);
1721         }
1722
1723         if (origin_set) {
1724                 track = tracksbase->first;
1725                 while (track) {
1726                         if (track->flag & TRACK_HAS_BUNDLE)
1727                                 mul_v3_m4v3(track->bundle_pos, imat, track->bundle_pos);
1728
1729                         track = track->next;
1730                 }
1731         }
1732
1733         MEM_freeN(reconstructed);
1734
1735         return ok;
1736 }
1737
1738 static int retrieve_libmv_reconstruct(MovieReconstructContext *context, MovieTracking *tracking)
1739 {
1740         /* take the intrinscis back from libmv */
1741         retrieve_libmv_reconstruct_intrinscis(context, tracking);
1742
1743         return retrieve_libmv_reconstruct_tracks(context, tracking);
1744 }
1745
1746 static int get_refine_intrinsics_flags(MovieTracking *tracking, MovieTrackingObject *object)
1747 {
1748         int refine = tracking->settings.refine_camera_intrinsics;
1749         int flags = 0;
1750
1751         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0)
1752                 return 0;
1753
1754         if (refine & REFINE_FOCAL_LENGTH)
1755                 flags |= LIBMV_REFINE_FOCAL_LENGTH;
1756
1757         if (refine & REFINE_PRINCIPAL_POINT)
1758                 flags |= LIBMV_REFINE_PRINCIPAL_POINT;
1759
1760         if (refine & REFINE_RADIAL_DISTORTION_K1)
1761                 flags |= REFINE_RADIAL_DISTORTION_K1;
1762
1763         if (refine & REFINE_RADIAL_DISTORTION_K2)
1764                 flags |= REFINE_RADIAL_DISTORTION_K2;
1765
1766         return flags;
1767 }
1768
1769 static int count_tracks_on_both_keyframes(MovieTracking *tracking, ListBase *tracksbase)
1770 {
1771         int tot = 0;
1772         int frame1 = tracking->settings.keyframe1, frame2 = tracking->settings.keyframe2;
1773         MovieTrackingTrack *track;
1774
1775         track = tracksbase->first;
1776         while (track) {
1777                 if (BKE_tracking_has_enabled_marker(track, frame1))
1778                         if (BKE_tracking_has_enabled_marker(track, frame2))
1779                                 tot++;
1780
1781                 track = track->next;
1782         }
1783
1784         return tot;
1785 }
1786 #endif
1787
1788 int BKE_tracking_can_reconstruct(MovieTracking *tracking, MovieTrackingObject *object, char *error_msg, int error_size)
1789 {
1790 #if WITH_LIBMV
1791         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
1792
1793         if (tracking->settings.motion_flag & TRACKING_MOTION_MODAL) {
1794                 /* TODO: check for number of tracks? */
1795                 return TRUE;
1796         }
1797         else if (count_tracks_on_both_keyframes(tracking, tracksbase) < 8) {
1798                 BLI_strncpy(error_msg, "At least 8 common tracks on both of keyframes are needed for reconstruction",
1799                             error_size);
1800
1801                 return FALSE;
1802         }
1803
1804         return TRUE;
1805 #else
1806         BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
1807
1808         (void) tracking;
1809         (void) object;
1810
1811         return 0;
1812 #endif
1813 }
1814
1815 MovieReconstructContext* BKE_tracking_reconstruction_context_new(MovieTracking *tracking, MovieTrackingObject *object,
1816                                                                  int keyframe1, int keyframe2, int width, int height)
1817 {
1818         MovieReconstructContext *context = MEM_callocN(sizeof(MovieReconstructContext), "MovieReconstructContext data");
1819         MovieTrackingCamera *camera = &tracking->camera;
1820         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
1821         float aspy = 1.0f / tracking->camera.pixel_aspect;
1822         int num_tracks = BLI_countlist(tracksbase);
1823         int sfra = INT_MAX, efra = INT_MIN;
1824         MovieTrackingTrack *track;
1825
1826         BLI_strncpy(context->object_name, object->name, sizeof(context->object_name));
1827         context->is_camera = object->flag & TRACKING_OBJECT_CAMERA;
1828         context->motion_flag = tracking->settings.motion_flag;
1829
1830         context->tracks_map = tracks_map_new(context->object_name, context->is_camera, num_tracks, 0);
1831
1832         track = tracksbase->first;
1833         while (track) {
1834                 int first = 0, last = track->markersnr - 1;
1835                 MovieTrackingMarker *first_marker = &track->markers[0];
1836                 MovieTrackingMarker *last_marker = &track->markers[track->markersnr - 1];
1837
1838                 /* find first not-disabled marker */
1839                 while (first <= track->markersnr - 1 && first_marker->flag & MARKER_DISABLED) {
1840                         first++;
1841                         first_marker++;
1842                 }
1843
1844                 /* find last not-disabled marker */
1845                 while (last >= 0 && last_marker->flag & MARKER_DISABLED) {
1846                         last--;
1847                         last_marker--;
1848                 }
1849
1850                 if (first < track->markersnr - 1)
1851                         sfra = MIN2(sfra, first_marker->framenr);
1852
1853                 if (last >= 0)
1854                         efra = MAX2(efra, last_marker->framenr);
1855
1856                 tracks_map_insert(context->tracks_map, track, NULL);
1857
1858                 track = track->next;
1859         }
1860
1861         context->sfra = sfra;
1862         context->efra = efra;
1863
1864 #ifdef WITH_LIBMV
1865         context->tracks = create_libmv_tracks(tracksbase, width, height*aspy);
1866         context->keyframe1 = keyframe1;
1867         context->keyframe2 = keyframe2;
1868         context->refine_flags = get_refine_intrinsics_flags(tracking, object);
1869 #else
1870         (void) width;
1871         (void) height;
1872         (void) keyframe1;
1873         (void) keyframe2;
1874 #endif
1875
1876         context->focal_length = camera->focal;
1877         context->principal_point[0] = camera->principal[0];
1878         context->principal_point[1] = camera->principal[1] * aspy;
1879
1880         context->k1 = camera->k1;
1881         context->k2 = camera->k2;
1882         context->k3 = camera->k3;
1883
1884         return context;
1885 }
1886
1887 void BKE_tracking_reconstruction_context_free(MovieReconstructContext *context)
1888 {
1889 #ifdef WITH_LIBMV
1890         if (context->reconstruction)
1891                         libmv_destroyReconstruction(context->reconstruction);
1892
1893         libmv_tracksDestroy(context->tracks);
1894 #endif
1895
1896         tracks_map_free(context->tracks_map, NULL);
1897
1898         MEM_freeN(context);
1899 }
1900
1901 #ifdef WITH_LIBMV
1902 static void solve_reconstruction_update_cb(void *customdata, double progress, const char *message)
1903 {
1904         ReconstructProgressData *progressdata = customdata;
1905
1906         if (progressdata->progress) {
1907                 *progressdata->progress = progress;
1908                 *progressdata->do_update = TRUE;
1909         }
1910
1911         BLI_snprintf(progressdata->stats_message, progressdata->message_size, "Solving camera | %s", message);
1912 }
1913 #endif
1914
1915 #if 0
1916 static int solve_reconstruction_testbreak_cb(void *customdata)
1917 {
1918         ReconstructProgressData *progressdata = customdata;
1919
1920         if (progressdata->stop && *progressdata->stop)
1921                 return TRUE;
1922
1923         return G.afbreek;
1924 }
1925 #endif
1926
1927 void BKE_tracking_solve_reconstruction(MovieReconstructContext *context, short *stop, short *do_update,
1928                                        float *progress, char *stats_message, int message_size)
1929 {
1930 #ifdef WITH_LIBMV
1931         float error;
1932
1933         ReconstructProgressData progressdata;
1934
1935         progressdata.stop = stop;
1936         progressdata.do_update = do_update;
1937         progressdata.progress = progress;
1938         progressdata.stats_message = stats_message;
1939         progressdata.message_size = message_size;
1940
1941         if (context->motion_flag & TRACKING_MOTION_MODAL) {
1942                 context->reconstruction = libmv_solveModal(context->tracks,
1943                         context->focal_length,
1944                         context->principal_point[0], context->principal_point[1],
1945                         context->k1, context->k2, context->k3,
1946                         solve_reconstruction_update_cb, &progressdata);
1947         }
1948         else {
1949                 context->reconstruction = libmv_solveReconstruction(context->tracks,
1950                         context->keyframe1, context->keyframe2,
1951                         context->refine_flags,
1952                         context->focal_length,
1953                         context->principal_point[0], context->principal_point[1],
1954                         context->k1, context->k2, context->k3,
1955                         solve_reconstruction_update_cb, &progressdata);
1956         }
1957
1958         error = libmv_reprojectionError(context->reconstruction);
1959
1960         context->reprojection_error = error;
1961 #else
1962         (void) context;
1963         (void) stop;
1964         (void) do_update;
1965         (void) progress;
1966         (void) stats_message;
1967         (void) message_size;
1968 #endif
1969 }
1970
1971 int BKE_tracking_finish_reconstruction(MovieReconstructContext *context, MovieTracking *tracking)
1972 {
1973         MovieTrackingReconstruction *reconstruction;
1974
1975         tracks_map_merge(context->tracks_map, tracking);
1976
1977         if (context->is_camera) {
1978                 reconstruction = &tracking->reconstruction;
1979         }
1980         else {
1981                 MovieTrackingObject *object;
1982
1983                 object = BKE_tracking_named_object(tracking, context->object_name);
1984                 reconstruction = &object->reconstruction;
1985         }
1986
1987         reconstruction->error = context->reprojection_error;
1988         reconstruction->flag |= TRACKING_RECONSTRUCTED;
1989
1990 #ifdef WITH_LIBMV
1991         if (!retrieve_libmv_reconstruct(context, tracking))
1992                 return FALSE;
1993 #endif
1994
1995         return TRUE;
1996 }
1997
1998 void BKE_track_unique_name(ListBase *tracksbase, MovieTrackingTrack *track)
1999 {
2000         BLI_uniquename(tracksbase, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
2001 }
2002
2003 MovieTrackingTrack *BKE_tracking_named_track(MovieTracking *tracking, MovieTrackingObject *object, const char *name)
2004 {
2005         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2006         MovieTrackingTrack *track = tracksbase->first;
2007
2008         while (track) {
2009                 if (!strcmp(track->name, name))
2010                         return track;
2011
2012                 track = track->next;
2013         }
2014
2015         return NULL;
2016 }
2017
2018 static int reconstruction_camera_index(MovieTrackingReconstruction *reconstruction, int framenr, int nearest)
2019 {
2020         MovieReconstructedCamera *cameras = reconstruction->cameras;
2021         int a = 0, d = 1;
2022
2023         if (!reconstruction->camnr)
2024                 return -1;
2025
2026         if (framenr < cameras[0].framenr) {
2027                 if (nearest)
2028                         return 0;
2029                 else
2030                         return -1;
2031         }
2032
2033         if (framenr > cameras[reconstruction->camnr - 1].framenr) {
2034                 if (nearest)
2035                         return reconstruction->camnr - 1;
2036                 else
2037                         return -1;
2038         }
2039
2040         if (reconstruction->last_camera < reconstruction->camnr)
2041                 a = reconstruction->last_camera;
2042
2043         if (cameras[a].framenr >= framenr)
2044                 d = -1;
2045
2046         while (a >= 0 && a < reconstruction->camnr) {
2047                 int cfra = cameras[a].framenr;
2048
2049                 /* check if needed framenr was "skipped" -- no data for requested frame */
2050
2051                 if (d > 0 && cfra > framenr) {
2052                         /* interpolate with previous position */
2053                         if (nearest)
2054                                 return a - 1;
2055                         else
2056                                 break;
2057                 }
2058
2059                 if (d < 0 && cfra < framenr) {
2060                         /* interpolate with next position */
2061                         if (nearest)
2062                                 return a;
2063                         else
2064                                 break;
2065                 }
2066
2067                 if (cfra == framenr) {
2068                         reconstruction->last_camera = a;
2069
2070                         return a;
2071                 }
2072
2073                 a += d;
2074         }
2075
2076         return -1;
2077 }
2078
2079 static void scale_reconstructed_camera(MovieTrackingObject *object, float mat[4][4])
2080 {
2081         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0) {
2082                 float smat[4][4];
2083
2084                 scale_m4_fl(smat, 1.0f / object->scale);
2085                 mult_m4_m4m4(mat, mat, smat);
2086         }
2087 }
2088
2089 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking,
2090                                                                 MovieTrackingObject *object, int framenr)
2091 {
2092         MovieTrackingReconstruction *reconstruction;
2093         int a;
2094
2095         reconstruction = BKE_tracking_object_reconstruction(tracking, object);
2096         a = reconstruction_camera_index(reconstruction, framenr, FALSE);
2097
2098         if (a ==-1)
2099                 return NULL;
2100
2101         return &reconstruction->cameras[a];
2102 }
2103
2104 void BKE_tracking_get_interpolated_camera(MovieTracking *tracking, MovieTrackingObject *object,
2105                                           int framenr, float mat[4][4])
2106 {
2107         MovieTrackingReconstruction *reconstruction;
2108         MovieReconstructedCamera *cameras;
2109         int a;
2110
2111         reconstruction = BKE_tracking_object_reconstruction(tracking, object);
2112         cameras = reconstruction->cameras;
2113         a = reconstruction_camera_index(reconstruction, framenr, 1);
2114
2115         if (a == -1) {
2116                 unit_m4(mat);
2117
2118                 return;
2119         }
2120
2121         if (cameras[a].framenr != framenr && a > 0 && a < reconstruction->camnr - 1) {
2122                 float t = ((float)framenr - cameras[a].framenr) / (cameras[a + 1].framenr - cameras[a].framenr);
2123
2124                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a + 1].mat, t);
2125         }
2126         else {
2127                 copy_m4_m4(mat, cameras[a].mat);
2128         }
2129
2130         scale_reconstructed_camera(object, mat);
2131 }
2132
2133 void BKE_get_tracking_mat(Scene *scene, Object *ob, float mat[4][4])
2134 {
2135         if (!ob) {
2136                 if (scene->camera)
2137                         ob = scene->camera;
2138                 else
2139                         ob = BKE_scene_camera_find(scene);
2140         }
2141
2142         if (ob)
2143                 BKE_object_where_is_calc_mat4(scene, ob, mat);
2144         else
2145                 unit_m4(mat);
2146 }
2147
2148 void BKE_tracking_camera_shift(MovieTracking *tracking, int winx, int winy, float *shiftx, float *shifty)
2149 {
2150         /* indeed in both of cases it should be winx -- it's just how camera shift works for blender's camera */
2151         *shiftx = (0.5f * winx - tracking->camera.principal[0]) / winx;
2152         *shifty = (0.5f * winy - tracking->camera.principal[1]) / winx;
2153 }
2154
2155 void BKE_tracking_camera_to_blender(MovieTracking *tracking, Scene *scene, Camera *camera, int width, int height)
2156 {
2157         float focal = tracking->camera.focal;
2158
2159         camera->sensor_x = tracking->camera.sensor_width;
2160         camera->sensor_fit = CAMERA_SENSOR_FIT_AUTO;
2161         camera->lens = focal * camera->sensor_x / width;
2162
2163         scene->r.xsch = width * tracking->camera.pixel_aspect;
2164         scene->r.ysch = height;
2165
2166         scene->r.xasp = 1.0f;
2167         scene->r.yasp = 1.0f;
2168
2169         BKE_tracking_camera_shift(tracking, width, height, &camera->shiftx, &camera->shifty);
2170 }
2171
2172 void BKE_tracking_projection_matrix(MovieTracking *tracking, MovieTrackingObject *object,
2173                                     int framenr, int winx, int winy, float mat[4][4])
2174 {
2175         MovieReconstructedCamera *camera;
2176         float lens = tracking->camera.focal * tracking->camera.sensor_width / (float)winx;
2177         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
2178         float winmat[4][4];
2179         float ycor =  1.0f / tracking->camera.pixel_aspect;
2180         float shiftx, shifty, winside = MAX2(winx, winy);
2181
2182         BKE_tracking_camera_shift(tracking, winx, winy, &shiftx, &shifty);
2183
2184         clipsta = 0.1f;
2185         clipend = 1000.0f;
2186
2187         if (winx >= winy)
2188                 viewfac = (lens * winx) / tracking->camera.sensor_width;
2189         else
2190                 viewfac = (ycor * lens * winy) / tracking->camera.sensor_width;
2191
2192         pixsize = clipsta / viewfac;
2193
2194         left = -0.5f * (float)winx + shiftx * winside;
2195         bottom = -0.5f * (ycor) * (float)winy + shifty * winside;
2196         right =  0.5f * (float)winx + shiftx * winside;
2197         top =  0.5f * (ycor) * (float)winy + shifty * winside;
2198
2199         left *= pixsize;
2200         right *= pixsize;
2201         bottom *= pixsize;
2202         top *= pixsize;
2203
2204         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
2205
2206         camera = BKE_tracking_get_reconstructed_camera(tracking, object, framenr);
2207
2208         if (camera) {
2209                 float imat[4][4];
2210
2211                 invert_m4_m4(imat, camera->mat);
2212                 mult_m4_m4m4(mat, winmat, imat);
2213         }
2214         else copy_m4_m4(mat, winmat);
2215 }
2216
2217 ListBase *BKE_tracking_get_tracks(MovieTracking *tracking)
2218 {
2219         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
2220
2221         if (object && (object->flag & TRACKING_OBJECT_CAMERA) == 0) {
2222                 return &object->tracks;
2223         }
2224
2225         return &tracking->tracks;
2226 }
2227
2228 MovieTrackingTrack *BKE_tracking_active_track(MovieTracking *tracking)
2229 {
2230         ListBase *tracksbase;
2231
2232         if (!tracking->act_track)
2233                 return NULL;
2234
2235         tracksbase = BKE_tracking_get_tracks(tracking);
2236
2237         /* check that active track is in current tracks list */
2238         if (BLI_findindex(tracksbase, tracking->act_track) >= 0)
2239                 return tracking->act_track;
2240
2241         return NULL;
2242 }
2243
2244 MovieTrackingObject *BKE_tracking_active_object(MovieTracking *tracking)
2245 {
2246         return BLI_findlink(&tracking->objects, tracking->objectnr);
2247 }
2248
2249 MovieTrackingObject *BKE_tracking_get_camera_object(MovieTracking *tracking)
2250 {
2251         MovieTrackingObject *object = tracking->objects.first;
2252
2253         while (object) {
2254                 if (object->flag & TRACKING_OBJECT_CAMERA)
2255                         return object;
2256
2257                 object = object->next;
2258         }
2259
2260         return NULL;
2261 }
2262
2263 ListBase *BKE_tracking_object_tracks(MovieTracking *tracking, MovieTrackingObject *object)
2264 {
2265         if (object->flag & TRACKING_OBJECT_CAMERA) {
2266                 return &tracking->tracks;
2267         }
2268
2269         return &object->tracks;
2270 }
2271
2272 MovieTrackingReconstruction *BKE_tracking_object_reconstruction(MovieTracking *tracking, MovieTrackingObject *object)
2273 {
2274         if (object->flag & TRACKING_OBJECT_CAMERA) {
2275                 return &tracking->reconstruction;
2276         }
2277
2278         return &object->reconstruction;
2279 }
2280
2281 MovieTrackingReconstruction *BKE_tracking_get_reconstruction(MovieTracking *tracking)
2282 {
2283         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
2284
2285         return BKE_tracking_object_reconstruction(tracking, object);
2286 }
2287
2288 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
2289 {
2290         MovieTrackingCamera *camera = &tracking->camera;
2291
2292 #ifdef WITH_LIBMV
2293         double x, y;
2294         float aspy = 1.0f / tracking->camera.pixel_aspect;
2295
2296         /* normalize coords */
2297         x = (co[0] - camera->principal[0]) / camera->focal;
2298         y = (co[1] - camera->principal[1] * aspy) / camera->focal;
2299
2300         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
2301                                     camera->k1, camera->k2, camera->k3, x, y, &x, &y);
2302
2303         /* result is in image coords already */
2304         nco[0] = x;
2305         nco[1] = y;
2306 #else
2307         (void) camera;
2308         (void) co;
2309         (void) nco;
2310 #endif
2311 }
2312
2313 void BKE_tracking_invert_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
2314 {
2315         MovieTrackingCamera *camera = &tracking->camera;
2316
2317 #ifdef WITH_LIBMV
2318         double x = co[0], y = co[1];
2319         float aspy = 1.0f / tracking->camera.pixel_aspect;
2320
2321         libmv_InvertIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
2322                                camera->k1, camera->k2, camera->k3, x, y, &x, &y);
2323
2324         nco[0] = x * camera->focal + camera->principal[0];
2325         nco[1] = y * camera->focal + camera->principal[1] * aspy;
2326 #else
2327         (void) camera;
2328         (void) co;
2329         (void) nco;
2330 #endif
2331 }
2332
2333 #ifdef WITH_LIBMV
2334 static int point_in_stroke(bGPDstroke *stroke, float x, float y)
2335 {
2336         int i, prev;
2337         int count = 0;
2338         bGPDspoint *points = stroke->points;
2339
2340         prev = stroke->totpoints - 1;
2341
2342         for (i = 0; i < stroke->totpoints; i++) {
2343                 if ((points[i].y < y && points[prev].y >= y) || (points[prev].y < y && points[i].y >= y)) {
2344                         float fac = (y - points[i].y) / (points[prev].y - points[i].y);
2345
2346                         if (points[i].x + fac * (points[prev].x - points[i].x) < x)
2347                                 count++;
2348                 }
2349
2350                 prev = i;
2351         }
2352
2353         return count % 2;
2354 }
2355
2356 static int point_in_layer(bGPDlayer *layer, float x, float y)
2357 {
2358         bGPDframe *frame = layer->frames.first;
2359
2360         while (frame) {
2361                 bGPDstroke *stroke = frame->strokes.first;
2362
2363                 while (stroke) {
2364                         if (point_in_stroke(stroke, x, y))
2365                                 return TRUE;
2366
2367                         stroke = stroke->next;
2368                 }
2369                 frame = frame->next;
2370         }
2371
2372         return FALSE;
2373 }
2374
2375 static void retrieve_libmv_features(MovieTracking *tracking, ListBase *tracksbase,
2376                                     struct libmv_Features *features, int framenr, int width, int height,
2377                                     bGPDlayer *layer, int place_outside_layer)
2378 {
2379         int a;
2380
2381         a = libmv_countFeatures(features);
2382         while (a--) {
2383                 MovieTrackingTrack *track;
2384                 double x, y, size, score;
2385                 int ok = TRUE;
2386                 float xu, yu;
2387
2388                 libmv_getFeature(features, a, &x, &y, &score, &size);
2389
2390                 xu = x / width;
2391                 yu = y / height;
2392
2393                 if (layer)
2394                         ok = point_in_layer(layer, xu, yu) != place_outside_layer;
2395
2396                 if (ok) {
2397                         track = BKE_tracking_add_track(tracking, tracksbase, xu, yu, framenr, width, height);
2398                         track->flag |= SELECT;
2399                         track->pat_flag |= SELECT;
2400                         track->search_flag |= SELECT;
2401                 }
2402         }
2403 }
2404 #endif
2405
2406 void BKE_tracking_detect_fast(MovieTracking *tracking, ListBase *tracksbase, ImBuf *ibuf,
2407                               int framenr, int margin, int min_trackness, int min_distance, bGPDlayer *layer,
2408                               int place_outside_layer)
2409 {
2410 #ifdef WITH_LIBMV
2411         struct libmv_Features *features;
2412         unsigned char *pixels = get_ucharbuf(ibuf);
2413
2414         features = libmv_detectFeaturesFAST(pixels, ibuf->x, ibuf->y, ibuf->x,
2415                                             margin, min_trackness, min_distance);
2416
2417         MEM_freeN(pixels);
2418
2419         retrieve_libmv_features(tracking, tracksbase, features, framenr,
2420                                 ibuf->x, ibuf->y, layer, place_outside_layer);
2421
2422         libmv_destroyFeatures(features);
2423 #else
2424         (void) tracking;
2425         (void) tracksbase;
2426         (void) ibuf;
2427         (void) framenr;
2428         (void) margin;
2429         (void) min_trackness;
2430         (void) min_distance;
2431         (void) layer;
2432         (void) place_outside_layer;
2433 #endif
2434 }
2435
2436 MovieTrackingTrack *BKE_tracking_indexed_track(MovieTracking *tracking, int tracknr, ListBase **tracksbase_r)
2437 {
2438         MovieTrackingObject *object;
2439         int cur = 1;
2440
2441         object = tracking->objects.first;
2442         while (object) {
2443                 ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2444                 MovieTrackingTrack *track = tracksbase->first;
2445
2446                 while (track) {
2447                         if (track->flag & TRACK_HAS_BUNDLE) {
2448                                 if (cur == tracknr) {
2449                                         *tracksbase_r = tracksbase;
2450                                         return track;
2451                                 }
2452
2453                                 cur++;
2454                         }
2455
2456                         track = track->next;
2457                 }
2458
2459                 object = object->next;
2460         }
2461
2462         *tracksbase_r = NULL;
2463
2464         return NULL;
2465 }
2466
2467 static int stabilization_median_point(MovieTracking *tracking, int framenr, float median[2])
2468 {
2469         int ok = FALSE;
2470         float min[2], max[2];
2471         MovieTrackingTrack *track;
2472
2473         INIT_MINMAX2(min, max);
2474
2475         track = tracking->tracks.first;
2476         while (track) {
2477                 if (track->flag & TRACK_USE_2D_STAB) {
2478                         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
2479
2480                         DO_MINMAX2(marker->pos, min, max);
2481
2482                         ok = TRUE;
2483                 }
2484
2485                 track = track->next;
2486         }
2487
2488         median[0] = (max[0] + min[0]) / 2.0f;
2489         median[1] = (max[1] + min[1]) / 2.0f;
2490
2491         return ok;
2492 }
2493
2494 static void calculate_stabdata(MovieTracking *tracking, int framenr, float width, float height,
2495                                float firstmedian[2], float median[2], float loc[2], float *scale, float *angle)
2496 {
2497         MovieTrackingStabilization *stab = &tracking->stabilization;
2498
2499         *scale = (stab->scale - 1.0f) * stab->scaleinf + 1.0f;
2500         *angle = 0.0f;
2501
2502         loc[0] = (firstmedian[0] - median[0]) *width * (*scale);
2503         loc[1] = (firstmedian[1] - median[1]) *height * (*scale);
2504
2505         mul_v2_fl(loc, stab->locinf);
2506
2507         if ((stab->flag & TRACKING_STABILIZE_ROTATION) && stab->rot_track && stab->rotinf) {
2508                 MovieTrackingMarker *marker;
2509                 float a[2], b[2];
2510                 float x0 = (float)width / 2.0f, y0 = (float)height / 2.0f;
2511                 float x = median[0] * width, y = median[1] * height;
2512
2513                 marker = BKE_tracking_get_marker(stab->rot_track, 1);
2514                 sub_v2_v2v2(a, marker->pos, firstmedian);
2515                 a[0] *= width;
2516                 a[1] *= height;
2517
2518                 marker = BKE_tracking_get_marker(stab->rot_track, framenr);
2519                 sub_v2_v2v2(b, marker->pos, median);
2520                 b[0] *= width;
2521                 b[1] *= height;
2522
2523                 *angle = -atan2(a[0] * b[1] - a[1] * b[0], a[0] * b[0] + a[1] * b[1]);
2524                 *angle *= stab->rotinf;
2525
2526                 /* convert to rotation around image center */
2527                 loc[0] -= (x0 + (x - x0) * cosf(*angle) - (y - y0) * sinf(*angle) - x) * (*scale);
2528                 loc[1] -= (y0 + (x - x0) * sinf(*angle) + (y - y0) * cosf(*angle) - y) * (*scale);
2529         }
2530 }
2531
2532 static float stabilization_auto_scale_factor(MovieTracking *tracking, int width, int height)
2533 {
2534         float firstmedian[2];
2535         MovieTrackingStabilization *stab = &tracking->stabilization;
2536         float aspect = tracking->camera.pixel_aspect;
2537
2538         if (stab->ok)
2539                 return stab->scale;
2540
2541         if (stabilization_median_point(tracking, 1, firstmedian)) {
2542                 int sfra = INT_MAX, efra = INT_MIN, cfra;
2543                 float scale = 1.0f;
2544                 MovieTrackingTrack *track;
2545
2546                 stab->scale = 1.0f;
2547
2548                 track = tracking->tracks.first;
2549                 while (track) {
2550                         if (track->flag & TRACK_USE_2D_STAB ||
2551                            ((stab->flag & TRACKING_STABILIZE_ROTATION) && track == stab->rot_track))
2552                         {
2553                                 sfra = MIN2(sfra, track->markers[0].framenr);
2554                                 efra = MAX2(efra, track->markers[track->markersnr - 1].framenr);
2555                         }
2556
2557                         track = track->next;
2558                 }
2559
2560                 for (cfra = sfra; cfra <= efra; cfra++) {
2561                         float median[2];
2562                         float loc[2], angle, tmp_scale;
2563                         int i;
2564                         float mat[4][4];
2565                         float points[4][2] = {{0.0f, 0.0f}, {0.0f, height}, {width, height}, {width, 0.0f}};
2566                         float si, co;
2567
2568                         stabilization_median_point(tracking, cfra, median);
2569
2570                         calculate_stabdata(tracking, cfra, width, height, firstmedian, median, loc, &tmp_scale, &angle);
2571
2572                         BKE_tracking_stabdata_to_mat4(width, height, aspect, loc, 1.0f, angle, mat);
2573
2574                         si = sin(angle);
2575                         co = cos(angle);
2576
2577                         for (i = 0; i < 4; i++) {
2578                                 int j;
2579                                 float a[3] = {0.0f, 0.0f, 0.0f}, b[3] = {0.0f, 0.0f, 0.0f};
2580
2581                                 copy_v3_v3(a, points[i]);
2582                                 copy_v3_v3(b, points[(i + 1) % 4]);
2583
2584                                 mul_m4_v3(mat, a);
2585                                 mul_m4_v3(mat, b);
2586
2587                                 for (j = 0; j < 4; j++) {
2588                                         float point[3] = {points[j][0], points[j][1], 0.0f};
2589                                         float v1[3], v2[3];
2590
2591                                         sub_v3_v3v3(v1, b, a);
2592                                         sub_v3_v3v3(v2, point, a);
2593
2594                                         if (cross_v2v2(v1, v2) >= 0.0f) {
2595                                                 const float rotDx[4][2] = {{1.0f, 0.0f}, {0.0f, -1.0f}, {-1.0f, 0.0f}, {0.0f, 1.0f}};
2596                                                 const float rotDy[4][2] = {{0.0f, 1.0f}, {1.0f, 0.0f}, {0.0f, -1.0f}, {-1.0f, 0.0f}};
2597
2598                                                 float dx = loc[0] * rotDx[j][0] + loc[1] * rotDx[j][1],
2599                                                       dy = loc[0] * rotDy[j][0] + loc[1] * rotDy[j][1];
2600
2601                                                 float w, h, E, F, G, H, I, J, K, S;
2602
2603                                                 if (j % 2) {
2604                                                         w = (float)height / 2.0f;
2605                                                         h = (float)width / 2.0f;
2606                                                 }
2607                                                 else {
2608                                                         w = (float)width / 2.0f;
2609                                                         h = (float)height / 2.0f;
2610                                                 }
2611
2612                                                 E = -w*co + h*si;
2613                                                 F = -h*co - w*si;
2614
2615                                                 if ((i % 2) == (j % 2)) {
2616                                                         G = -w*co - h*si;
2617                                                         H = h*co - w*si;
2618                                                 }
2619                                                 else {
2620                                                         G = w*co + h*si;
2621                                                         H = -h*co + w*si;
2622                                                 }
2623
2624                                                 I = F - H;
2625                                                 J = G - E;
2626                                                 K = G*F - E*H;
2627
2628                                                 S = (-w*I - h*J) / (dx*I + dy*J + K);
2629
2630                                                 scale = MAX2(scale, S);
2631                                         }
2632                                 }
2633                         }
2634                 }
2635
2636                 stab->scale = scale;
2637
2638                 if (stab->maxscale > 0.0f)
2639                         stab->scale = MIN2(stab->scale, stab->maxscale);
2640         }
2641         else {
2642                 stab->scale = 1.0f;
2643         }
2644
2645         stab->ok = TRUE;
2646
2647         return stab->scale;
2648 }
2649
2650 static ImBuf* stabilize_alloc_ibuf(ImBuf *cacheibuf, ImBuf *srcibuf, int fill)
2651 {
2652         int flags;
2653
2654         if (cacheibuf && (cacheibuf->x != srcibuf->x || cacheibuf->y != srcibuf->y)) {
2655                 IMB_freeImBuf(cacheibuf);
2656                 cacheibuf = NULL;
2657         }
2658
2659         flags = IB_rect;
2660
2661         if (srcibuf->rect_float)
2662                 flags |= IB_rectfloat;
2663
2664         if (cacheibuf) {
2665                 if (fill) {
2666                         float col[4] = {0.0f, 0.0f, 0.0f, 0.0f};
2667
2668                         IMB_rectfill(cacheibuf, col);
2669                 }
2670         }
2671         else {
2672                 cacheibuf = IMB_allocImBuf(srcibuf->x, srcibuf->y, srcibuf->planes, flags);
2673                 cacheibuf->profile = srcibuf->profile;
2674         }
2675
2676         return cacheibuf;
2677 }
2678
2679 void BKE_tracking_stabilization_data(MovieTracking *tracking, int framenr, int width, int height,
2680                                      float loc[2], float *scale, float *angle)
2681 {
2682         float firstmedian[2], median[2];
2683         MovieTrackingStabilization *stab = &tracking->stabilization;
2684
2685         if ((stab->flag & TRACKING_2D_STABILIZATION) == 0) {
2686                 zero_v2(loc);
2687                 *scale = 1.0f;
2688                 *angle = 0.0f;
2689
2690                 return;
2691         }
2692
2693         if (stabilization_median_point(tracking, 1, firstmedian)) {
2694                 stabilization_median_point(tracking, framenr, median);
2695
2696                 if ((stab->flag & TRACKING_AUTOSCALE) == 0)
2697                         stab->scale = 1.0f;
2698
2699                 if (!stab->ok) {
2700                         if (stab->flag & TRACKING_AUTOSCALE)
2701                                 stabilization_auto_scale_factor(tracking, width, height);
2702
2703                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2704
2705                         stab->ok = TRUE;
2706                 }
2707                 else {
2708                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2709                 }
2710         }
2711         else {
2712                 zero_v2(loc);
2713                 *scale = 1.0f;
2714                 *angle = 0.0f;
2715         }
2716 }
2717
2718 ImBuf *BKE_tracking_stabilize(MovieTracking *tracking, int framenr, ImBuf *ibuf,
2719                               float loc[2], float *scale, float *angle)
2720 {
2721         float tloc[2], tscale, tangle;
2722         MovieTrackingStabilization *stab = &tracking->stabilization;
2723         ImBuf *tmpibuf;
2724         float width = ibuf->x, height = ibuf->y;
2725         float aspect = tracking->camera.pixel_aspect;
2726
2727         if (loc)
2728                 copy_v2_v2(tloc, loc);
2729
2730         if (scale)
2731                 tscale = *scale;
2732
2733         if ((stab->flag & TRACKING_2D_STABILIZATION) == 0) {
2734                 if (loc)
2735                         zero_v2(loc);
2736
2737                 if (scale)
2738                         *scale = 1.0f;
2739
2740                 return ibuf;
2741         }
2742
2743         BKE_tracking_stabilization_data(tracking, framenr, width, height, tloc, &tscale, &tangle);
2744
2745         tmpibuf = stabilize_alloc_ibuf(NULL, ibuf, TRUE);
2746
2747         /* scale would be handled by matrix transformation when angle is non-zero */
2748         if (tscale != 1.0f && tangle == 0.0f) {
2749                 ImBuf *scaleibuf;
2750
2751                 stabilization_auto_scale_factor(tracking, width, height);
2752
2753                 scaleibuf = stabilize_alloc_ibuf(stab->scaleibuf, ibuf, 0);
2754                 stab->scaleibuf = scaleibuf;
2755
2756                 IMB_rectcpy(scaleibuf, ibuf, 0, 0, 0, 0, ibuf->x, ibuf->y);
2757                 IMB_scalefastImBuf(scaleibuf, ibuf->x*tscale, ibuf->y*tscale);
2758
2759                 ibuf = scaleibuf;
2760         }
2761
2762         if (tangle == 0.0f) {
2763                 /* if angle is zero, then it's much faster to use rect copy
2764                  * but could be issues with subpixel precisions */
2765                 IMB_rectcpy(tmpibuf, ibuf,
2766                             tloc[0] - (tscale - 1.0f) * width / 2.0f,
2767                             tloc[1] - (tscale - 1.0f) * height / 2.0f,
2768                             0, 0, ibuf->x, ibuf->y);
2769         }
2770         else {
2771                 float mat[4][4];
2772                 int i, j, filter = tracking->stabilization.filter;
2773                 void (*interpolation) (struct ImBuf*, struct ImBuf*, float, float, int, int) = NULL;
2774
2775                 BKE_tracking_stabdata_to_mat4(ibuf->x, ibuf->y, aspect, tloc, tscale, tangle, mat);
2776                 invert_m4(mat);
2777
2778                 if (filter == TRACKING_FILTER_NEAREAST)
2779                         interpolation = neareast_interpolation;
2780                 else if (filter == TRACKING_FILTER_BILINEAR)
2781                         interpolation = bilinear_interpolation;
2782                 else if (filter == TRACKING_FILTER_BICUBIC)
2783                         interpolation = bicubic_interpolation;
2784                 else
2785                         /* fallback to default interpolation method */
2786                         interpolation = neareast_interpolation;
2787
2788                 for (j = 0; j < tmpibuf->y; j++) {
2789                         for (i = 0; i < tmpibuf->x;i++) {
2790                                 float vec[3] = {i, j, 0};
2791
2792                                 mul_v3_m4v3(vec, mat, vec);
2793
2794                                 interpolation(ibuf, tmpibuf, vec[0], vec[1], i, j);
2795                         }
2796                 }
2797         }
2798
2799         tmpibuf->userflags |= IB_MIPMAP_INVALID;
2800
2801         if (tmpibuf->rect_float)
2802                 tmpibuf->userflags |= IB_RECT_INVALID;
2803
2804         if (loc)
2805                 copy_v2_v2(loc, tloc);
2806
2807         if (scale)
2808                 *scale = tscale;
2809
2810         if (angle)
2811                 *angle = tangle;
2812
2813         return tmpibuf;
2814 }
2815
2816 void BKE_tracking_stabdata_to_mat4(int width, int height, float aspect,
2817                                    float loc[2], float scale, float angle, float mat[4][4])
2818 {
2819         float lmat[4][4], rmat[4][4], smat[4][4], cmat[4][4], icmat[4][4], amat[4][4], iamat[4][4];
2820         float svec[3] = {scale, scale, scale};
2821
2822         unit_m4(rmat);
2823         unit_m4(lmat);
2824         unit_m4(smat);
2825         unit_m4(cmat);
2826         unit_m4(amat);
2827
2828         /* aspect ratio correction matrix */
2829         amat[0][0] = 1.0f / aspect;
2830         invert_m4_m4(iamat, amat);
2831
2832         /* image center as rotation center */
2833         cmat[3][0] = (float)width / 2.0f;
2834         cmat[3][1] = (float)height / 2.0f;
2835         invert_m4_m4(icmat, cmat);
2836
2837         size_to_mat4(smat, svec);               /* scale matrix */
2838         add_v2_v2(lmat[3], loc);                /* translation matrix */
2839         rotate_m4(rmat, 'Z', angle);    /* rotation matrix */
2840
2841         /* compose transformation matrix */
2842         mul_serie_m4(mat, lmat, cmat, amat, rmat, iamat, smat, icmat, NULL);
2843 }
2844
2845 MovieDistortion *BKE_tracking_distortion_create(void)
2846 {
2847         MovieDistortion *distortion;
2848
2849         distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2850
2851         return distortion;
2852 }
2853
2854 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
2855 {
2856         MovieDistortion *new_distortion;
2857
2858         new_distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2859
2860 #ifdef WITH_LIBMV
2861         new_distortion->intrinsics = libmv_CameraIntrinsicsCopy(distortion->intrinsics);
2862 #else
2863         (void) distortion;
2864 #endif
2865
2866         return new_distortion;
2867 }
2868
2869 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking, int width, int height)
2870 {
2871         MovieTrackingCamera *camera = &tracking->camera;
2872         float aspy = 1.0f / tracking->camera.pixel_aspect;
2873
2874 #ifdef WITH_LIBMV
2875         if (!distortion->intrinsics) {
2876                 distortion->intrinsics = libmv_CameraIntrinsicsNew(camera->focal,
2877                                 camera->principal[0], camera->principal[1] * aspy,
2878                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2879         }
2880         else {
2881                 libmv_CameraIntrinsicsUpdate(distortion->intrinsics, camera->focal,
2882                                 camera->principal[0], camera->principal[1] * aspy,
2883                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2884         }
2885 #else
2886         (void) distortion;
2887         (void) width;
2888         (void) height;
2889         (void) camera;
2890         (void) aspy;
2891 #endif
2892 }
2893
2894 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking,
2895                                     ImBuf *ibuf, int width, int height, float overscan, int undistort)
2896 {
2897         ImBuf *resibuf;
2898
2899         BKE_tracking_distortion_update(distortion, tracking, width, height);
2900
2901         resibuf = IMB_dupImBuf(ibuf);
2902
2903         if (ibuf->rect_float) {
2904 #ifdef WITH_LIBMV
2905                 if (undistort) {
2906                         libmv_CameraIntrinsicsUndistortFloat(distortion->intrinsics,
2907                                                 ibuf->rect_float, resibuf->rect_float,
2908                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2909                 }
2910                 else {
2911                         libmv_CameraIntrinsicsDistortFloat(distortion->intrinsics,
2912                                                 ibuf->rect_float, resibuf->rect_float,
2913                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2914                 }
2915 #endif
2916
2917                 ibuf->userflags |= IB_RECT_INVALID;
2918         }
2919         else {
2920 #ifdef WITH_LIBMV
2921                 if (undistort) {
2922                                 libmv_CameraIntrinsicsUndistortByte(distortion->intrinsics,
2923                                                         (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2924                                                         ibuf->x, ibuf->y, overscan, ibuf->channels);
2925                 }
2926                 else {
2927                         libmv_CameraIntrinsicsDistortByte(distortion->intrinsics,
2928                                                 (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2929                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2930                 }
2931 #endif
2932         }
2933
2934 #ifndef WITH_LIBMV
2935         (void) overscan;
2936         (void) undistort;
2937 #endif
2938
2939         return resibuf;
2940 }
2941
2942 void BKE_tracking_distortion_destroy(MovieDistortion *distortion)
2943 {
2944 #ifdef WITH_LIBMV
2945         libmv_CameraIntrinsicsDestroy(distortion->intrinsics);
2946 #endif
2947
2948         MEM_freeN(distortion);
2949 }
2950
2951 ImBuf *BKE_tracking_undistort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2952 {
2953         MovieTrackingCamera *camera = &tracking->camera;
2954
2955         if (camera->intrinsics == NULL)
2956                 camera->intrinsics = BKE_tracking_distortion_create();
2957
2958         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 1);
2959 }
2960
2961 ImBuf *BKE_tracking_distort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2962 {
2963         MovieTrackingCamera *camera = &tracking->camera;
2964
2965         if (camera->intrinsics == NULL)
2966                 camera->intrinsics = BKE_tracking_distortion_create();
2967
2968         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 0);
2969 }
2970
2971 /* area - which part of marker should be selected. see TRACK_AREA_* constants */
2972 void BKE_tracking_select_track(ListBase *tracksbase, MovieTrackingTrack *track, int area, int extend)
2973 {
2974         if (extend) {
2975                 BKE_tracking_track_flag(track, area, SELECT, 0);
2976         }
2977         else {
2978                 MovieTrackingTrack *cur = tracksbase->first;
2979
2980                 while (cur) {
2981                         if ((cur->flag & TRACK_HIDDEN) == 0) {
2982                                 if (cur == track) {
2983                                         BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2984                                         BKE_tracking_track_flag(cur, area, SELECT, 0);
2985                                 }
2986                                 else {
2987                                         BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2988                                 }
2989                         }
2990
2991                         cur = cur->next;
2992                 }
2993         }
2994 }
2995
2996 void BKE_tracking_deselect_track(MovieTrackingTrack *track, int area)
2997 {
2998         BKE_tracking_track_flag(track, area, SELECT, 1);
2999 }
3000
3001 MovieTrackingObject *BKE_tracking_new_object(MovieTracking *tracking, const char *name)
3002 {
3003         MovieTrackingObject *object = MEM_callocN(sizeof(MovieTrackingObject), "tracking object");
3004
3005         if (tracking->tot_object == 0) {
3006                 /* first object is always camera */
3007                 BLI_strncpy(object->name, "Camera", sizeof(object->name));
3008
3009                 object->flag |= TRACKING_OBJECT_CAMERA;
3010         }
3011         else {
3012                 BLI_strncpy(object->name, name, sizeof(object->name));
3013         }
3014
3015         BLI_addtail(&tracking->objects, object);
3016
3017         tracking->tot_object++;
3018         tracking->objectnr = BLI_countlist(&tracking->objects) - 1;
3019
3020         object->scale = 1.0f;
3021
3022         BKE_tracking_object_unique_name(tracking, object);
3023
3024         return object;
3025 }
3026
3027 void BKE_tracking_remove_object(MovieTracking *tracking, MovieTrackingObject *object)
3028 {
3029         MovieTrackingTrack *track;
3030         int index = BLI_findindex(&tracking->objects, object);
3031
3032         if (index < 0)
3033                 return;
3034
3035         if (object->flag & TRACKING_OBJECT_CAMERA) {
3036                 /* object used for camera solving can't be deleted */
3037                 return;
3038         }
3039
3040         track = object->tracks.first;
3041         while (track) {
3042                 if (track == tracking->act_track)
3043                         tracking->act_track = NULL;
3044
3045                 track = track->next;
3046         }
3047
3048         tracking_object_free(object);
3049         BLI_freelinkN(&tracking->objects, object);
3050
3051         tracking->tot_object--;
3052
3053         if (index > 0)
3054                 tracking->objectnr = index - 1;
3055         else
3056                 tracking->objectnr = 0;
3057 }
3058
3059 void BKE_tracking_object_unique_name(MovieTracking *tracking, MovieTrackingObject *object)
3060 {
3061         BLI_uniquename(&tracking->objects, object, "Object", '.',
3062                        offsetof(MovieTrackingObject, name), sizeof(object->name));
3063 }
3064
3065 MovieTrackingObject *BKE_tracking_named_object(MovieTracking *tracking, const char *name)
3066 {
3067         MovieTrackingObject *object = tracking->objects.first;
3068
3069         while (object) {
3070                 if (!strcmp(object->name, name))
3071                         return object;
3072
3073                 object = object->next;
3074         }
3075
3076         return NULL;
3077 }
3078
3079 /*********************** dopesheet functions *************************/
3080
3081 static int channels_alpha_sort(void *a, void *b)
3082 {
3083         MovieTrackingDopesheetChannel *channel_a = a;
3084         MovieTrackingDopesheetChannel *channel_b = b;
3085
3086         if (BLI_strcasecmp(channel_a->track->name, channel_b->track->name) > 0)
3087                 return 1;
3088         else
3089                 return 0;
3090 }
3091
3092 static int channels_total_track_sort(void *a, void *b)
3093 {
3094         MovieTrackingDopesheetChannel *channel_a = a;
3095         MovieTrackingDopesheetChannel *channel_b = b;
3096
3097         if (channel_a->total_frames > channel_b->total_frames)
3098                 return 1;
3099         else
3100                 return 0;
3101 }
3102
3103 static int channels_longest_segment_sort(void *a, void *b)
3104 {
3105         MovieTrackingDopesheetChannel *channel_a = a;
3106         MovieTrackingDopesheetChannel *channel_b = b;
3107
3108         if (channel_a->max_segment > channel_b->max_segment)
3109                 return 1;
3110         else
3111                 return 0;
3112 }
3113
3114 static int channels_alpha_inverse_sort(void *a, void *b)
3115 {
3116         if (channels_alpha_sort(a, b))
3117                 return 0;
3118         else
3119                 return 1;
3120 }
3121
3122 static int channels_total_track_inverse_sort(void *a, void *b)
3123 {
3124         if (channels_total_track_sort(a, b))
3125                 return 0;
3126         else
3127                 return 1;
3128 }
3129
3130 static int channels_longest_segment_inverse_sort(void *a, void *b)
3131 {
3132         if (channels_longest_segment_sort(a, b))
3133                 return 0;
3134         else
3135                 return 1;
3136 }
3137
3138 static void channels_segments_calc(MovieTrackingDopesheetChannel *channel)
3139 {
3140         MovieTrackingTrack *track = channel->track;
3141         int i, segment;
3142
3143         channel->tot_segment = 0;
3144         channel->max_segment = 0;
3145         channel->total_frames = 0;
3146
3147         /* count */
3148         i = 0;
3149         while (i < track->markersnr) {
3150                 MovieTrackingMarker *marker = &track->markers[i];
3151
3152                 if ((marker->flag & MARKER_DISABLED) == 0) {
3153                         int prev_fra = marker->framenr, len = 0;
3154
3155                         i++;
3156                         while (i < track->markersnr) {
3157                                 marker = &track->markers[i];
3158
3159                                 if (marker->framenr != prev_fra + 1)
3160                                         break;
3161                                 if (marker->flag & MARKER_DISABLED)
3162                                         break;
3163
3164                                 prev_fra = marker->framenr;
3165                                 len++;
3166                                 i++;
3167                         }
3168
3169                         channel->tot_segment++;
3170                 }
3171
3172                 i++;
3173         }
3174
3175         if (!channel->tot_segment)
3176                 return;
3177
3178         channel->segments = MEM_callocN(2 * sizeof(int) * channel->tot_segment, "tracking channel segments");
3179
3180         /* create segments */
3181         i = 0;
3182         segment = 0;
3183         while (i < track->markersnr) {
3184                 MovieTrackingMarker *marker = &track->markers[i];
3185
3186                 if ((marker->flag & MARKER_DISABLED) == 0) {
3187                         MovieTrackingMarker *start_marker = marker;
3188                         int prev_fra = marker->framenr, len = 0;
3189
3190                         i++;
3191                         while (i < track->markersnr) {
3192                                 marker = &track->markers[i];
3193
3194                                 if (marker->framenr != prev_fra + 1)
3195                                         break;
3196                                 if (marker->flag & MARKER_DISABLED)
3197                                         break;
3198
3199                                 prev_fra = marker->framenr;
3200                                 channel->total_frames++;
3201                                 len++;
3202                                 i++;
3203                         }
3204
3205                         channel->segments[2 * segment] = start_marker->framenr;
3206                         channel->segments[2 * segment + 1] = start_marker->framenr + len;
3207
3208                         channel->max_segment =  MAX2(channel->max_segment, len);
3209                         segment++;
3210                 }
3211
3212                 i++;
3213         }
3214 }
3215
3216 static void  tracking_dopesheet_sort(MovieTracking *tracking, int sort_method, int inverse)
3217 {
3218         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
3219
3220         if (dopesheet->sort_method == sort_method && dopesheet->sort_inverse == inverse)
3221                 return;
3222
3223         if (inverse) {
3224                 if (sort_method == TRACK_SORT_NAME) {
3225                         BLI_sortlist(&dopesheet->channels, channels_alpha_inverse_sort);
3226                 }
3227                 else if (sort_method == TRACK_SORT_LONGEST) {
3228                         BLI_sortlist(&dopesheet->channels, channels_longest_segment_inverse_sort);
3229                 }
3230                 else if (sort_method == TRACK_SORT_TOTAL) {
3231                         BLI_sortlist(&dopesheet->channels, channels_total_track_inverse_sort);
3232                 }
3233         }
3234         else {
3235                 if (sort_method == TRACK_SORT_NAME) {
3236                         BLI_sortlist(&dopesheet->channels, channels_alpha_sort);
3237                 }
3238                 else if (sort_method == TRACK_SORT_LONGEST) {
3239                         BLI_sortlist(&dopesheet->channels, channels_longest_segment_sort);
3240                 }
3241                 else if (sort_method == TRACK_SORT_TOTAL) {
3242                         BLI_sortlist(&dopesheet->channels, channels_total_track_sort);
3243                 }
3244         }
3245
3246         dopesheet->sort_method = sort_method;
3247         dopesheet->sort_inverse = inverse;
3248 }
3249
3250 void BKE_tracking_dopesheet_tag_update(MovieTracking *tracking)
3251 {
3252         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
3253
3254         dopesheet->ok = FALSE;
3255 }
3256
3257 void BKE_tracking_dopesheet_update(MovieTracking *tracking, int sort_method, int inverse)
3258 {
3259         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
3260         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
3261         MovieTrackingTrack *track;
3262         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);