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