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