fb78e89cc307ba17fdd106139896bc7cc442880b
[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_ptr_new("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                         int framenr = BKE_movieclip_remap_scene_to_clip_frame(clip, user->framenr);
976                         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
977
978                         if ((marker->flag & MARKER_DISABLED) == 0)
979                                 num_tracks++;
980                 }
981
982                 track = track->next;
983         }
984
985         if (num_tracks) {
986                 int width, height;
987
988                 context->tracks_map = tracks_map_new(object->name, object->flag & TRACKING_OBJECT_CAMERA,
989                                                      num_tracks, sizeof(TrackContext));
990
991                 BKE_movieclip_get_size(clip, user, &width, &height);
992
993                 /* create tracking data */
994                 track = tracksbase->first;
995                 while (track) {
996                         if (TRACK_SELECTED(track) && (track->flag & (TRACK_HIDDEN | TRACK_LOCKED)) == 0) {
997                                 int framenr = BKE_movieclip_remap_scene_to_clip_frame(clip, user->framenr);
998                                 MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
999
1000                                 if ((marker->flag & MARKER_DISABLED) == 0) {
1001                                         TrackContext track_context;
1002
1003                                         memset(&track_context, 0, sizeof(TrackContext));
1004
1005 #ifdef WITH_LIBMV
1006                                         {
1007                                                 float patx = (int)((track->pat_max[0] - track->pat_min[0]) * width),
1008                                                       paty = (int)((track->pat_max[1] - track->pat_min[1]) * height);
1009
1010                                                 float search_size_x = (track->search_max[0] - track->search_min[0]) * width;
1011                                                 float search_size_y = (track->search_max[1] - track->search_min[1]) * height;
1012                                                 float pattern_size_x = (track->pat_max[0] - track->pat_min[0]) * width;
1013                                                 float pattern_size_y = (track->pat_max[1] - track->pat_min[1]) * height;
1014                                                 int wndx = (int)patx / 2, wndy = (int)paty / 2;
1015                                                 int half_wnd = MAX2(wndx, wndy);
1016
1017                                                         /* compute the maximum pyramid size */
1018                                                 float search_to_pattern_ratio = MIN2(search_size_x,  search_size_y)
1019                                                         / MAX2(pattern_size_x, pattern_size_y);
1020                                                 float log2_search_to_pattern_ratio = log(floor(search_to_pattern_ratio)) / M_LN2;
1021                                                 int max_pyramid_levels = floor(log2_search_to_pattern_ratio + 1);
1022
1023                                                 /* try to accommodate the user's choice of pyramid level in a way
1024                                                  * that doesn't cause the coarsest pyramid pattern to be larger
1025                                                  * than the search size */
1026                                                 int level = MIN2(track->pyramid_levels, max_pyramid_levels);
1027
1028                                                 struct libmv_RegionTracker *region_tracker;
1029
1030                                                 if (track->tracker == TRACKER_KLT) {
1031                                                         region_tracker = libmv_pyramidRegionTrackerNew(100, level, half_wnd,
1032                                                                                                        track->minimum_correlation);
1033                                                 }
1034                                                 else if (track->tracker == TRACKER_HYBRID) {
1035                                                         region_tracker = libmv_hybridRegionTrackerNew(100, half_wnd, track->minimum_correlation);
1036                                                 }
1037                                                 else if (track->tracker == TRACKER_SAD) {
1038                                                         region_tracker = libmv_bruteRegionTrackerNew(MAX2(wndx, wndy), track->minimum_correlation);
1039                                                 }
1040
1041                                                 track_context.region_tracker = region_tracker;
1042                                         }
1043 #endif
1044
1045                                         tracks_map_insert(context->tracks_map, track, &track_context);
1046                                 }
1047                         }
1048
1049                         track = track->next;
1050                 }
1051         }
1052
1053         context->clip = clip;
1054
1055         /* store needed clip flags passing to get_buffer functions
1056          * - MCLIP_USE_PROXY is needed to because timecode affects on movie clip
1057          *   only in case Proxy/Timecode flag is set, so store this flag to use
1058          *   timecodes properly but reset render size to SIZE_FULL so correct resolution
1059          *   would be used for images
1060          * - MCLIP_USE_PROXY_CUSTOM_DIR is needed because proxy/timecode files might
1061          *   be stored in a different location
1062          * ignore all the rest possible flags for now */
1063         context->clip_flag = clip->flag & MCLIP_TIMECODE_FLAGS;
1064
1065         context->user = *user;
1066         context->user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
1067         context->user.render_flag = 0;
1068
1069         if (!sequence)
1070                 BLI_begin_threaded_malloc();
1071
1072         return context;
1073 }
1074
1075 static void track_context_free(void *customdata)
1076 {
1077         TrackContext *track_context = (TrackContext *)customdata;
1078
1079 #if WITH_LIBMV
1080         if (track_context->region_tracker)
1081                 libmv_regionTrackerDestroy(track_context->region_tracker);
1082
1083         if (track_context->patch)
1084                 MEM_freeN(track_context->patch);
1085
1086 #else
1087                 (void) track_context;
1088 #endif
1089 }
1090
1091 void BKE_tracking_context_free(MovieTrackingContext *context)
1092 {
1093         if (!context->sequence)
1094                 BLI_end_threaded_malloc();
1095
1096         tracks_map_free(context->tracks_map, track_context_free);
1097
1098         MEM_freeN(context);
1099 }
1100
1101 /* zap channels from the imbuf that are disabled by the user. this can lead to
1102  * better tracks sometimes. however, instead of simply zeroing the channels
1103  * out, do a partial grayscale conversion so the display is better. */
1104 void BKE_tracking_disable_imbuf_channels(ImBuf *ibuf, int disable_red, int disable_green, int disable_blue,
1105                                          int grayscale)
1106 {
1107         int x, y;
1108         float scale;
1109
1110         if (!disable_red && !disable_green && !disable_blue && !grayscale)
1111                 return;
1112
1113         /* If only some components are selected, it's important to rescale the result
1114          * appropriately so that e.g. if only blue is selected, it's not zeroed out. */
1115         scale = (disable_red   ? 0.0f : 0.2126f) +
1116                 (disable_green ? 0.0f : 0.7152f) +
1117                 (disable_blue  ? 0.0f : 0.0722f);
1118
1119         for (y = 0; y < ibuf->y; y++) {
1120                 for (x = 0; x < ibuf->x; x++) {
1121                         int pixel = ibuf->x*y + x;
1122
1123                         if (ibuf->rect_float) {
1124                                 float *rrgbf = ibuf->rect_float + pixel*4;
1125                                 float r = disable_red   ? 0.0f : rrgbf[0];
1126                                 float g = disable_green ? 0.0f : rrgbf[1];
1127                                 float b = disable_blue  ? 0.0f : rrgbf[2];
1128
1129                                 if (grayscale) {
1130                                         float gray = (0.2126f*r + 0.7152f*g + 0.0722f*b) / scale;
1131
1132                                         rrgbf[0] = rrgbf[1] = rrgbf[2] = gray;
1133                                 }
1134                                 else {
1135                                         rrgbf[0] = r;
1136                                         rrgbf[1] = g;
1137                                         rrgbf[2] = b;
1138                                 }
1139                         }
1140                         else {
1141                                 char *rrgb = (char*)ibuf->rect + pixel*4;
1142                                 char r = disable_red   ? 0 : rrgb[0];
1143                                 char g = disable_green ? 0 : rrgb[1];
1144                                 char b = disable_blue  ? 0 : rrgb[2];
1145
1146                                 if (grayscale) {
1147                                         float gray = (0.2126f*r + 0.7152f*g + 0.0722f*b) / scale;
1148
1149                                         rrgb[0] = rrgb[1] = rrgb[2] = gray;
1150                                 }
1151                                 else {
1152                                         rrgb[0] = r;
1153                                         rrgb[1] = g;
1154                                         rrgb[2] = b;
1155                                 }
1156                         }
1157                 }
1158         }
1159
1160         if (ibuf->rect_float)
1161                 ibuf->userflags |= IB_RECT_INVALID;
1162 }
1163
1164 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track, int grayscale)
1165 {
1166         BKE_tracking_disable_imbuf_channels(ibuf, track->flag & TRACK_DISABLE_RED,
1167                         track->flag & TRACK_DISABLE_GREEN, track->flag & TRACK_DISABLE_BLUE, grayscale);
1168 }
1169
1170 static ImBuf *get_area_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1171                              float min[2], float max[2], int margin, int anchored, float pos[2], int origin[2])
1172 {
1173         ImBuf *tmpibuf;
1174         int x, y;
1175         int x1, y1, w, h;
1176         float mpos[2];
1177
1178         copy_v2_v2(mpos, marker->pos);
1179         if (anchored)
1180                 add_v2_v2(mpos, track->offset);
1181
1182         if (pos)
1183                 zero_v2(pos);
1184
1185         x = mpos[0]*ibuf->x;
1186         y = mpos[1]*ibuf->y;
1187
1188         w = (max[0] - min[0]) * ibuf->x;
1189         h = (max[1] - min[1]) * ibuf->y;
1190
1191         /* dimensions should be odd */
1192         w = w | 1;
1193         h = h | 1;
1194
1195         x1 = x - (int)(w * (-min[0] / (max[0] - min[0])));
1196         y1 = y - (int)(h * (-min[1] / (max[1] - min[1])));
1197
1198         if (ibuf->rect_float)
1199                 tmpibuf = IMB_allocImBuf(w + margin * 2, h + margin * 2, 32, IB_rectfloat);
1200         else
1201                 tmpibuf = IMB_allocImBuf(w + margin * 2, h + margin * 2, 32, IB_rect);
1202
1203         tmpibuf->profile = ibuf->profile;
1204
1205         IMB_rectcpy(tmpibuf, ibuf, 0, 0, x1 - margin, y1 - margin, w + margin * 2, h + margin * 2);
1206
1207         if (pos != NULL) {
1208                 pos[0] = mpos[0] * ibuf->x - x1 + margin;
1209                 pos[1] = mpos[1] * ibuf->y - y1 + margin;
1210         }
1211
1212         if (origin != NULL) {
1213                 origin[0] = x1 - margin;
1214                 origin[1] = y1 - margin;
1215         }
1216
1217         if ((track->flag & TRACK_PREVIEW_GRAYSCALE) ||
1218            (track->flag & TRACK_DISABLE_RED)       ||
1219            (track->flag & TRACK_DISABLE_GREEN)     ||
1220            (track->flag & TRACK_DISABLE_BLUE))
1221         {
1222                 disable_imbuf_channels(tmpibuf, track, TRUE /* grayscale */);
1223         }
1224
1225         return tmpibuf;
1226 }
1227
1228 ImBuf *BKE_tracking_get_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1229                                       int margin, int anchored, float pos[2], int origin[2])
1230 {
1231         return get_area_imbuf(ibuf, track, marker, track->pat_min, track->pat_max, margin, anchored, pos, origin);
1232 }
1233
1234 ImBuf *BKE_tracking_get_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1235                                      int margin, int anchored, float pos[2], int origin[2])
1236 {
1237         return get_area_imbuf(ibuf, track, marker, track->search_min, track->search_max, margin, anchored, pos, origin);
1238 }
1239
1240 #ifdef WITH_LIBMV
1241 static float *get_search_floatbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1242                                   int *width_r, int *height_r, float pos[2], int origin[2])
1243 {
1244         ImBuf *tmpibuf;
1245         float *pixels, *fp;
1246         int x, y, width, height;
1247
1248         width = (track->search_max[0] - track->search_min[0]) * ibuf->x;
1249         height = (track->search_max[1] - track->search_min[1]) * ibuf->y;
1250
1251         tmpibuf = BKE_tracking_get_search_imbuf(ibuf, track, marker, 0, 0, pos, origin);
1252         disable_imbuf_channels(tmpibuf, track, FALSE /* don't grayscale */);
1253
1254         *width_r = width;
1255         *height_r = height;
1256
1257         fp = pixels = MEM_callocN(width * height * sizeof(float), "tracking floatBuf");
1258         for (y = 0; y < (int)height; y++) {
1259                 for (x = 0; x < (int)width; x++) {
1260                         int pixel = tmpibuf->x * y + x;
1261
1262                         if (tmpibuf->rect_float) {
1263                                 float *rrgbf = tmpibuf->rect_float + pixel * 4;
1264
1265                                 *fp = 0.2126 * rrgbf[0] + 0.7152 * rrgbf[1] + 0.0722 * rrgbf[2];
1266                         }
1267                         else {
1268                                 unsigned char *rrgb = (unsigned char*)tmpibuf->rect + pixel * 4;
1269
1270                                 *fp = (0.2126 * rrgb[0] + 0.7152 * rrgb[1] + 0.0722 * rrgb[2]) / 255.0f;
1271                         }
1272
1273                         fp++;
1274                 }
1275         }
1276
1277         IMB_freeImBuf(tmpibuf);
1278
1279         return pixels;
1280 }
1281
1282 static unsigned char *get_ucharbuf(ImBuf *ibuf)
1283 {
1284         int x, y;
1285         unsigned char *pixels, *cp;
1286
1287         cp = pixels = MEM_callocN(ibuf->x * ibuf->y * sizeof(unsigned char), "tracking ucharBuf");
1288         for (y = 0; y < ibuf->y; y++) {
1289                 for (x = 0; x < ibuf->x; x++) {
1290                         int pixel = ibuf->x * y + x;
1291
1292                         if (ibuf->rect_float) {
1293                                 const float *rrgbf = ibuf->rect_float + pixel*4;
1294                                 const float grey_f = 0.2126f * rrgbf[0] + 0.7152f * rrgbf[1] + 0.0722f * rrgbf[2];
1295
1296                                 *cp = FTOCHAR(grey_f);
1297                         }
1298                         else {
1299                                 const unsigned char *rrgb = (unsigned char*)ibuf->rect + pixel * 4;
1300
1301                                 *cp = 0.2126f * rrgb[0] + 0.7152f * rrgb[1] + 0.0722f * rrgb[2];
1302                         }
1303
1304                         cp++;
1305                 }
1306         }
1307
1308         return pixels;
1309 }
1310
1311 static ImBuf *get_frame_ibuf(MovieTrackingContext *context, int framenr)
1312 {
1313         ImBuf *ibuf;
1314         MovieClipUser user = context->user;
1315
1316         user.framenr = BKE_movieclip_remap_clip_to_scene_frame(context->clip, framenr);
1317
1318         ibuf = BKE_movieclip_get_ibuf_flag(context->clip, &user, context->clip_flag, MOVIECLIP_CACHE_SKIP);
1319
1320         return ibuf;
1321 }
1322
1323 static ImBuf *get_keyframed_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track,
1324                                  MovieTrackingMarker *marker, MovieTrackingMarker **marker_keyed)
1325 {
1326         int framenr = marker->framenr;
1327         int a = marker - track->markers;
1328
1329         *marker_keyed = marker;
1330
1331         while (a >= 0 && a < track->markersnr) {
1332                 int next = (context->backwards) ? a + 1 : a - 1;
1333                 int is_keyframed = FALSE;
1334                 MovieTrackingMarker *cur_marker = &track->markers[a];
1335                 MovieTrackingMarker *next_marker = NULL;
1336
1337                 if (next >= 0 && next < track->markersnr)
1338                         next_marker = &track->markers[next];
1339
1340                 /* if next mrker is disabled, stop searching keyframe and use current frame as keyframe */
1341                 if (next_marker && next_marker->flag & MARKER_DISABLED)
1342                         is_keyframed = TRUE;
1343
1344                 is_keyframed |= (cur_marker->flag & MARKER_TRACKED) == 0;
1345
1346                 if (is_keyframed) {
1347                         framenr = cur_marker->framenr;
1348                         *marker_keyed = cur_marker;
1349
1350                         break;
1351                 }
1352
1353                 a = next;
1354         }
1355
1356         return get_frame_ibuf(context, framenr);
1357 }
1358
1359 static ImBuf *get_adjust_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1360                               int curfra, MovieTrackingMarker **marker_keyed)
1361 {
1362         ImBuf *ibuf = NULL;
1363
1364         if (track->pattern_match == TRACK_MATCH_KEYFRAME) {
1365                 ibuf = get_keyframed_ibuf(context, track, marker, marker_keyed);
1366         }
1367         else {
1368                 ibuf = get_frame_ibuf(context, curfra);
1369
1370                 /* use current marker as keyframed position */
1371                 *marker_keyed = marker;
1372         }
1373
1374         return ibuf;
1375 }
1376
1377 #endif
1378
1379 void BKE_tracking_sync(MovieTrackingContext *context)
1380 {
1381         MovieTracking *tracking = &context->clip->tracking;
1382         int newframe;
1383
1384         tracks_map_merge(context->tracks_map, tracking);
1385
1386         if (context->backwards)
1387                 newframe = context->user.framenr + 1;
1388         else
1389                 newframe = context->user.framenr - 1;
1390
1391         context->sync_frame = newframe;
1392
1393         tracking->dopesheet.ok = FALSE;
1394 }
1395
1396 void BKE_tracking_sync_user(MovieClipUser *user, MovieTrackingContext *context)
1397 {
1398         user->framenr = context->sync_frame;
1399 }
1400
1401 int BKE_tracking_next(MovieTrackingContext *context)
1402 {
1403         ImBuf *ibuf_new;
1404         int curfra =  BKE_movieclip_remap_scene_to_clip_frame(context->clip, context->user.framenr);
1405         int a, ok = FALSE, map_size;
1406
1407         map_size = tracks_map_size(context->tracks_map);
1408
1409         /* nothing to track, avoid unneeded frames reading to save time and memory */
1410         if (!map_size)
1411                 return FALSE;
1412
1413         if (context->backwards)
1414                 context->user.framenr--;
1415         else
1416                 context->user.framenr++;
1417
1418         ibuf_new = BKE_movieclip_get_ibuf_flag(context->clip, &context->user, context->clip_flag, MOVIECLIP_CACHE_SKIP);
1419         if (!ibuf_new)
1420                 return FALSE;
1421
1422         #pragma omp parallel for private(a) shared(ibuf_new, ok) if (map_size>1)
1423         for (a = 0; a < map_size; a++) {
1424                 TrackContext *track_context = NULL;
1425                 MovieTrackingTrack *track;
1426                 MovieTrackingMarker *marker;
1427
1428                 tracks_map_get(context->tracks_map, a, &track, (void**)&track_context);
1429
1430                 marker = BKE_tracking_exact_marker(track, curfra);
1431
1432                 if (marker && (marker->flag & MARKER_DISABLED) == 0) {
1433 #ifdef WITH_LIBMV
1434                         int width, height, origin[2], tracked = 0, need_readjust = 0;
1435                         float pos[2], margin[2], dim[2];
1436                         double x1, y1, x2, y2;
1437                         ImBuf *ibuf = NULL;
1438                         MovieTrackingMarker marker_new, *marker_keyed;
1439                         int onbound = FALSE, nextfra;
1440
1441                         if (track->pattern_match == TRACK_MATCH_KEYFRAME)
1442                                 need_readjust = context->first_time;
1443                         else
1444                                 need_readjust = TRUE;
1445
1446                         if (context->backwards)
1447                                 nextfra = curfra - 1;
1448                         else
1449                                 nextfra = curfra + 1;
1450
1451                         /* margin from frame boundaries */
1452                         sub_v2_v2v2(dim, track->pat_max, track->pat_min);
1453                         margin[0] = margin[1] = MAX2(dim[0], dim[1]) / 2.0f;
1454
1455                         margin[0] = MAX2(margin[0], (float)track->margin / ibuf_new->x);
1456                         margin[1] = MAX2(margin[1], (float)track->margin / ibuf_new->y);
1457
1458                         /* do not track markers which are too close to boundary */
1459                         if (marker->pos[0] < margin[0] || marker->pos[0] > 1.0f - margin[0] ||
1460                             marker->pos[1] < margin[1] || marker->pos[1] > 1.0f - margin[1])
1461                         {
1462                                 onbound = TRUE;
1463                         }
1464                         else {
1465                                 float *patch_new;
1466
1467                                 if (need_readjust) {
1468                                         /* calculate patch for keyframed position */
1469                                         ibuf = get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1470
1471                                         if (track_context->patch)
1472                                                 MEM_freeN(track_context->patch);
1473
1474                                         track_context->patch = get_search_floatbuf(ibuf, track, marker_keyed, &width, &height,
1475                                                                                    track_context->keyframed_pos, origin);
1476
1477                                         IMB_freeImBuf(ibuf);
1478                                 }
1479
1480                                 patch_new = get_search_floatbuf(ibuf_new, track, marker, &width, &height, pos, origin);
1481
1482                                 x1 = track_context->keyframed_pos[0];
1483                                 y1 = track_context->keyframed_pos[1];
1484
1485                                 x2 = pos[0];
1486                                 y2 = pos[1];
1487
1488                                 tracked = libmv_regionTrackerTrack(track_context->region_tracker, track_context->patch, patch_new,
1489                                                         width, height, x1, y1, &x2, &y2);
1490
1491                                 MEM_freeN(patch_new);
1492                         }
1493
1494                         if (tracked && !onbound && finite(x2) && finite(y2)) {
1495                                 if (context->first_time) {
1496                                         #pragma omp critical
1497                                         {
1498                                                 /* check if there's no keyframe/tracked markers before tracking marker.
1499                                                  * if so -- create disabled marker before currently tracking "segment" */
1500                                                 put_disabled_marker(track, marker, !context->backwards, 0);
1501                                         }
1502                                 }
1503
1504                                 memset(&marker_new, 0, sizeof(marker_new));
1505
1506                                 if (!onbound) {
1507                                         marker_new.pos[0] = (origin[0] + x2) / ibuf_new->x;
1508                                         marker_new.pos[1] = (origin[1] + y2) / ibuf_new->y;
1509                                 }
1510                                 else {
1511                                         copy_v2_v2(marker_new.pos, marker->pos);
1512                                 }
1513
1514                                 marker_new.flag |= MARKER_TRACKED;
1515                                 marker_new.framenr = nextfra;
1516
1517                                 #pragma omp critical
1518                                 {
1519                                         BKE_tracking_insert_marker(track, &marker_new);
1520                                 }
1521
1522                                 /* make currently tracked segment be finished with disabled marker */
1523                                 #pragma omp critical
1524                                 {
1525                                         put_disabled_marker(track, &marker_new, context->backwards, 0);
1526                                 }
1527                         }
1528                         else {
1529                                 marker_new = *marker;
1530
1531                                 marker_new.framenr = nextfra;
1532                                 marker_new.flag |= MARKER_DISABLED;
1533
1534                                 //#pragma omp critical
1535                                 {
1536                                         BKE_tracking_insert_marker(track, &marker_new);
1537                                 }
1538                         }
1539
1540                         ok = TRUE;
1541 #endif
1542                 }
1543         }
1544
1545         IMB_freeImBuf(ibuf_new);
1546
1547         context->first_time = FALSE;
1548         context->frames++;
1549
1550         return ok;
1551 }
1552
1553 /*********************** camera solving *************************/
1554
1555 typedef struct MovieReconstructContext {
1556 #ifdef WITH_LIBMV
1557         struct libmv_Tracks *tracks;
1558         int keyframe1, keyframe2;
1559         short refine_flags;
1560
1561         struct libmv_Reconstruction *reconstruction;
1562 #endif
1563         char object_name[MAX_NAME];
1564         int is_camera;
1565         short motion_flag;
1566
1567         float focal_length;
1568         float principal_point[2];
1569         float k1, k2, k3;
1570
1571         float reprojection_error;
1572
1573         TracksMap *tracks_map;
1574
1575         int sfra, efra;
1576 } MovieReconstructContext;
1577
1578 typedef struct ReconstructProgressData {
1579         short *stop;
1580         short *do_update;
1581         float *progress;
1582         char *stats_message;
1583         int message_size;
1584 } ReconstructProgressData;
1585
1586 #if WITH_LIBMV
1587 static struct libmv_Tracks *create_libmv_tracks(ListBase *tracksbase, int width, int height)
1588 {
1589         int tracknr = 0;
1590         MovieTrackingTrack *track;
1591         struct libmv_Tracks *tracks = libmv_tracksNew();
1592
1593         track = tracksbase->first;
1594         while (track) {
1595                 int a = 0;
1596
1597                 for (a = 0; a < track->markersnr; a++) {
1598                         MovieTrackingMarker *marker = &track->markers[a];
1599
1600                         if ((marker->flag & MARKER_DISABLED) == 0) {
1601                                 libmv_tracksInsert(tracks, marker->framenr, tracknr,
1602                                                         marker->pos[0] * width, marker->pos[1] * height);
1603                         }
1604                 }
1605
1606                 track = track->next;
1607                 tracknr++;
1608         }
1609
1610         return tracks;
1611 }
1612
1613 static void retrieve_libmv_reconstruct_intrinscis(MovieReconstructContext *context, MovieTracking *tracking)
1614 {
1615         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
1616         struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_ReconstructionExtractIntrinsics(libmv_reconstruction);
1617
1618         float aspy = 1.0f / tracking->camera.pixel_aspect;
1619
1620         double focal_length, principal_x, principal_y, k1, k2, k3;
1621         int width, height;
1622
1623         libmv_CameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
1624                                       &k1, &k2, &k3, &width, &height);
1625
1626         tracking->camera.focal = focal_length;
1627         tracking->camera.principal[0] = principal_x;
1628
1629         tracking->camera.principal[1] = principal_y / aspy;
1630         tracking->camera.k1 = k1;
1631         tracking->camera.k2 = k2;
1632 }
1633
1634 static int retrieve_libmv_reconstruct_tracks(MovieReconstructContext *context, MovieTracking *tracking)
1635 {
1636         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
1637         MovieTrackingReconstruction *reconstruction = NULL;
1638         MovieReconstructedCamera *reconstructed;
1639         MovieTrackingTrack *track;
1640         ListBase *tracksbase =  NULL;
1641         int ok = TRUE, tracknr = 0, a, origin_set = FALSE;
1642         int sfra = context->sfra, efra = context->efra;
1643         float imat[4][4];
1644
1645         if (context->is_camera) {
1646                 tracksbase = &tracking->tracks;
1647                 reconstruction = &tracking->reconstruction;
1648         }
1649         else {
1650                 MovieTrackingObject *object = BKE_tracking_named_object(tracking, context->object_name);
1651
1652                 tracksbase = &object->tracks;
1653                 reconstruction = &object->reconstruction;
1654         }
1655
1656         unit_m4(imat);
1657
1658         track = tracksbase->first;
1659         while (track) {
1660                 double pos[3];
1661
1662                 if (libmv_reporojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
1663                         track->bundle_pos[0] = pos[0];
1664                         track->bundle_pos[1] = pos[1];
1665                         track->bundle_pos[2] = pos[2];
1666
1667                         track->flag |= TRACK_HAS_BUNDLE;
1668                         track->error = libmv_reporojectionErrorForTrack(libmv_reconstruction, tracknr);
1669                 }
1670                 else {
1671                         track->flag &= ~TRACK_HAS_BUNDLE;
1672                         ok = FALSE;
1673
1674                         printf("No bundle for track #%d '%s'\n", tracknr, track->name);
1675                 }
1676
1677                 track = track->next;
1678                 tracknr++;
1679         }
1680
1681         if (reconstruction->cameras)
1682                 MEM_freeN(reconstruction->cameras);
1683
1684         reconstruction->camnr = 0;
1685         reconstruction->cameras = NULL;
1686         reconstructed = MEM_callocN((efra - sfra + 1) * sizeof(MovieReconstructedCamera),
1687                                     "temp reconstructed camera");
1688
1689         for (a = sfra; a <= efra; a++) {
1690                 double matd[4][4];
1691
1692                 if (libmv_reporojectionCameraForImage(libmv_reconstruction, a, matd)) {
1693                         int i, j;
1694                         float mat[4][4];
1695                         float error = libmv_reporojectionErrorForImage(libmv_reconstruction, a);
1696
1697                         for (i = 0; i < 4; i++)
1698                                 for (j = 0; j < 4; j++)
1699                                         mat[i][j] = matd[i][j];
1700
1701                         if (!origin_set) {
1702                                 copy_m4_m4(imat, mat);
1703                                 invert_m4(imat);
1704                                 origin_set = TRUE;
1705                         }
1706
1707                         if (origin_set)
1708                                 mult_m4_m4m4(mat, imat, mat);
1709
1710                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
1711                         reconstructed[reconstruction->camnr].framenr = a;
1712                         reconstructed[reconstruction->camnr].error = error;
1713                         reconstruction->camnr++;
1714                 }
1715                 else {
1716                         ok = FALSE;
1717                         printf("No camera for frame %d\n", a);
1718                 }
1719         }
1720
1721         if (reconstruction->camnr) {
1722                 int size = reconstruction->camnr * sizeof(MovieReconstructedCamera);
1723                 reconstruction->cameras = MEM_callocN(size, "reconstructed camera");
1724                 memcpy(reconstruction->cameras, reconstructed, size);
1725         }
1726
1727         if (origin_set) {
1728                 track = tracksbase->first;
1729                 while (track) {
1730                         if (track->flag & TRACK_HAS_BUNDLE)
1731                                 mul_v3_m4v3(track->bundle_pos, imat, track->bundle_pos);
1732
1733                         track = track->next;
1734                 }
1735         }
1736
1737         MEM_freeN(reconstructed);
1738
1739         return ok;
1740 }
1741
1742 static int retrieve_libmv_reconstruct(MovieReconstructContext *context, MovieTracking *tracking)
1743 {
1744         /* take the intrinscis back from libmv */
1745         retrieve_libmv_reconstruct_intrinscis(context, tracking);
1746
1747         return retrieve_libmv_reconstruct_tracks(context, tracking);
1748 }
1749
1750 static int get_refine_intrinsics_flags(MovieTracking *tracking, MovieTrackingObject *object)
1751 {
1752         int refine = tracking->settings.refine_camera_intrinsics;
1753         int flags = 0;
1754
1755         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0)
1756                 return 0;
1757
1758         if (refine & REFINE_FOCAL_LENGTH)
1759                 flags |= LIBMV_REFINE_FOCAL_LENGTH;
1760
1761         if (refine & REFINE_PRINCIPAL_POINT)
1762                 flags |= LIBMV_REFINE_PRINCIPAL_POINT;
1763
1764         if (refine & REFINE_RADIAL_DISTORTION_K1)
1765                 flags |= REFINE_RADIAL_DISTORTION_K1;
1766
1767         if (refine & REFINE_RADIAL_DISTORTION_K2)
1768                 flags |= REFINE_RADIAL_DISTORTION_K2;
1769
1770         return flags;
1771 }
1772
1773 static int count_tracks_on_both_keyframes(MovieTracking *tracking, ListBase *tracksbase)
1774 {
1775         int tot = 0;
1776         int frame1 = tracking->settings.keyframe1, frame2 = tracking->settings.keyframe2;
1777         MovieTrackingTrack *track;
1778
1779         track = tracksbase->first;
1780         while (track) {
1781                 if (BKE_tracking_has_enabled_marker(track, frame1))
1782                         if (BKE_tracking_has_enabled_marker(track, frame2))
1783                                 tot++;
1784
1785                 track = track->next;
1786         }
1787
1788         return tot;
1789 }
1790 #endif
1791
1792 int BKE_tracking_can_reconstruct(MovieTracking *tracking, MovieTrackingObject *object, char *error_msg, int error_size)
1793 {
1794 #if WITH_LIBMV
1795         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
1796
1797         if (tracking->settings.motion_flag & TRACKING_MOTION_MODAL) {
1798                 /* TODO: check for number of tracks? */
1799                 return TRUE;
1800         }
1801         else if (count_tracks_on_both_keyframes(tracking, tracksbase) < 8) {
1802                 BLI_strncpy(error_msg, "At least 8 common tracks on both of keyframes are needed for reconstruction",
1803                             error_size);
1804
1805                 return FALSE;
1806         }
1807
1808         return TRUE;
1809 #else
1810         BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
1811
1812         (void) tracking;
1813         (void) object;
1814
1815         return 0;
1816 #endif
1817 }
1818
1819 MovieReconstructContext* BKE_tracking_reconstruction_context_new(MovieTracking *tracking, MovieTrackingObject *object,
1820                                                                  int keyframe1, int keyframe2, int width, int height)
1821 {
1822         MovieReconstructContext *context = MEM_callocN(sizeof(MovieReconstructContext), "MovieReconstructContext data");
1823         MovieTrackingCamera *camera = &tracking->camera;
1824         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
1825         float aspy = 1.0f / tracking->camera.pixel_aspect;
1826         int num_tracks = BLI_countlist(tracksbase);
1827         int sfra = INT_MAX, efra = INT_MIN;
1828         MovieTrackingTrack *track;
1829
1830         BLI_strncpy(context->object_name, object->name, sizeof(context->object_name));
1831         context->is_camera = object->flag & TRACKING_OBJECT_CAMERA;
1832         context->motion_flag = tracking->settings.motion_flag;
1833
1834         context->tracks_map = tracks_map_new(context->object_name, context->is_camera, num_tracks, 0);
1835
1836         track = tracksbase->first;
1837         while (track) {
1838                 int first = 0, last = track->markersnr - 1;
1839                 MovieTrackingMarker *first_marker = &track->markers[0];
1840                 MovieTrackingMarker *last_marker = &track->markers[track->markersnr - 1];
1841
1842                 /* find first not-disabled marker */
1843                 while (first <= track->markersnr - 1 && first_marker->flag & MARKER_DISABLED) {
1844                         first++;
1845                         first_marker++;
1846                 }
1847
1848                 /* find last not-disabled marker */
1849                 while (last >= 0 && last_marker->flag & MARKER_DISABLED) {
1850                         last--;
1851                         last_marker--;
1852                 }
1853
1854                 if (first < track->markersnr - 1)
1855                         sfra = MIN2(sfra, first_marker->framenr);
1856
1857                 if (last >= 0)
1858                         efra = MAX2(efra, last_marker->framenr);
1859
1860                 tracks_map_insert(context->tracks_map, track, NULL);
1861
1862                 track = track->next;
1863         }
1864
1865         context->sfra = sfra;
1866         context->efra = efra;
1867
1868 #ifdef WITH_LIBMV
1869         context->tracks = create_libmv_tracks(tracksbase, width, height*aspy);
1870         context->keyframe1 = keyframe1;
1871         context->keyframe2 = keyframe2;
1872         context->refine_flags = get_refine_intrinsics_flags(tracking, object);
1873 #else
1874         (void) width;
1875         (void) height;
1876         (void) keyframe1;
1877         (void) keyframe2;
1878 #endif
1879
1880         context->focal_length = camera->focal;
1881         context->principal_point[0] = camera->principal[0];
1882         context->principal_point[1] = camera->principal[1] * aspy;
1883
1884         context->k1 = camera->k1;
1885         context->k2 = camera->k2;
1886         context->k3 = camera->k3;
1887
1888         return context;
1889 }
1890
1891 void BKE_tracking_reconstruction_context_free(MovieReconstructContext *context)
1892 {
1893 #ifdef WITH_LIBMV
1894         if (context->reconstruction)
1895                         libmv_destroyReconstruction(context->reconstruction);
1896
1897         libmv_tracksDestroy(context->tracks);
1898 #endif
1899
1900         tracks_map_free(context->tracks_map, NULL);
1901
1902         MEM_freeN(context);
1903 }
1904
1905 #ifdef WITH_LIBMV
1906 static void solve_reconstruction_update_cb(void *customdata, double progress, const char *message)
1907 {
1908         ReconstructProgressData *progressdata = customdata;
1909
1910         if (progressdata->progress) {
1911                 *progressdata->progress = progress;
1912                 *progressdata->do_update = TRUE;
1913         }
1914
1915         BLI_snprintf(progressdata->stats_message, progressdata->message_size, "Solving camera | %s", message);
1916 }
1917 #endif
1918
1919 #if 0
1920 static int solve_reconstruction_testbreak_cb(void *customdata)
1921 {
1922         ReconstructProgressData *progressdata = customdata;
1923
1924         if (progressdata->stop && *progressdata->stop)
1925                 return TRUE;
1926
1927         return G.afbreek;
1928 }
1929 #endif
1930
1931 void BKE_tracking_solve_reconstruction(MovieReconstructContext *context, short *stop, short *do_update,
1932                                        float *progress, char *stats_message, int message_size)
1933 {
1934 #ifdef WITH_LIBMV
1935         float error;
1936
1937         ReconstructProgressData progressdata;
1938
1939         progressdata.stop = stop;
1940         progressdata.do_update = do_update;
1941         progressdata.progress = progress;
1942         progressdata.stats_message = stats_message;
1943         progressdata.message_size = message_size;
1944
1945         if (context->motion_flag & TRACKING_MOTION_MODAL) {
1946                 context->reconstruction = libmv_solveModal(context->tracks,
1947                         context->focal_length,
1948                         context->principal_point[0], context->principal_point[1],
1949                         context->k1, context->k2, context->k3,
1950                         solve_reconstruction_update_cb, &progressdata);
1951         }
1952         else {
1953                 context->reconstruction = libmv_solveReconstruction(context->tracks,
1954                         context->keyframe1, context->keyframe2,
1955                         context->refine_flags,
1956                         context->focal_length,
1957                         context->principal_point[0], context->principal_point[1],
1958                         context->k1, context->k2, context->k3,
1959                         solve_reconstruction_update_cb, &progressdata);
1960         }
1961
1962         error = libmv_reprojectionError(context->reconstruction);
1963
1964         context->reprojection_error = error;
1965 #else
1966         (void) context;
1967         (void) stop;
1968         (void) do_update;
1969         (void) progress;
1970         (void) stats_message;
1971         (void) message_size;
1972 #endif
1973 }
1974
1975 int BKE_tracking_finish_reconstruction(MovieReconstructContext *context, MovieTracking *tracking)
1976 {
1977         MovieTrackingReconstruction *reconstruction;
1978
1979         tracks_map_merge(context->tracks_map, tracking);
1980
1981         if (context->is_camera) {
1982                 reconstruction = &tracking->reconstruction;
1983         }
1984         else {
1985                 MovieTrackingObject *object;
1986
1987                 object = BKE_tracking_named_object(tracking, context->object_name);
1988                 reconstruction = &object->reconstruction;
1989         }
1990
1991         reconstruction->error = context->reprojection_error;
1992         reconstruction->flag |= TRACKING_RECONSTRUCTED;
1993
1994 #ifdef WITH_LIBMV
1995         if (!retrieve_libmv_reconstruct(context, tracking))
1996                 return FALSE;
1997 #endif
1998
1999         return TRUE;
2000 }
2001
2002 void BKE_track_unique_name(ListBase *tracksbase, MovieTrackingTrack *track)
2003 {
2004         BLI_uniquename(tracksbase, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
2005 }
2006
2007 MovieTrackingTrack *BKE_tracking_named_track(MovieTracking *tracking, MovieTrackingObject *object, const char *name)
2008 {
2009         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2010         MovieTrackingTrack *track = tracksbase->first;
2011
2012         while (track) {
2013                 if (!strcmp(track->name, name))
2014                         return track;
2015
2016                 track = track->next;
2017         }
2018
2019         return NULL;
2020 }
2021
2022 static int reconstruction_camera_index(MovieTrackingReconstruction *reconstruction, int framenr, int nearest)
2023 {
2024         MovieReconstructedCamera *cameras = reconstruction->cameras;
2025         int a = 0, d = 1;
2026
2027         if (!reconstruction->camnr)
2028                 return -1;
2029
2030         if (framenr < cameras[0].framenr) {
2031                 if (nearest)
2032                         return 0;
2033                 else
2034                         return -1;
2035         }
2036
2037         if (framenr > cameras[reconstruction->camnr - 1].framenr) {
2038                 if (nearest)
2039                         return reconstruction->camnr - 1;
2040                 else
2041                         return -1;
2042         }
2043
2044         if (reconstruction->last_camera < reconstruction->camnr)
2045                 a = reconstruction->last_camera;
2046
2047         if (cameras[a].framenr >= framenr)
2048                 d = -1;
2049
2050         while (a >= 0 && a < reconstruction->camnr) {
2051                 int cfra = cameras[a].framenr;
2052
2053                 /* check if needed framenr was "skipped" -- no data for requested frame */
2054
2055                 if (d > 0 && cfra > framenr) {
2056                         /* interpolate with previous position */
2057                         if (nearest)
2058                                 return a - 1;
2059                         else
2060                                 break;
2061                 }
2062
2063                 if (d < 0 && cfra < framenr) {
2064                         /* interpolate with next position */
2065                         if (nearest)
2066                                 return a;
2067                         else
2068                                 break;
2069                 }
2070
2071                 if (cfra == framenr) {
2072                         reconstruction->last_camera = a;
2073
2074                         return a;
2075                 }
2076
2077                 a += d;
2078         }
2079
2080         return -1;
2081 }
2082
2083 static void scale_reconstructed_camera(MovieTrackingObject *object, float mat[4][4])
2084 {
2085         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0) {
2086                 float smat[4][4];
2087
2088                 scale_m4_fl(smat, 1.0f / object->scale);
2089                 mult_m4_m4m4(mat, mat, smat);
2090         }
2091 }
2092
2093 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking,
2094                                                                 MovieTrackingObject *object, int framenr)
2095 {
2096         MovieTrackingReconstruction *reconstruction;
2097         int a;
2098
2099         reconstruction = BKE_tracking_object_reconstruction(tracking, object);
2100         a = reconstruction_camera_index(reconstruction, framenr, FALSE);
2101
2102         if (a ==-1)
2103                 return NULL;
2104
2105         return &reconstruction->cameras[a];
2106 }
2107
2108 void BKE_tracking_get_interpolated_camera(MovieTracking *tracking, MovieTrackingObject *object,
2109                                           int framenr, float mat[4][4])
2110 {
2111         MovieTrackingReconstruction *reconstruction;
2112         MovieReconstructedCamera *cameras;
2113         int a;
2114
2115         reconstruction = BKE_tracking_object_reconstruction(tracking, object);
2116         cameras = reconstruction->cameras;
2117         a = reconstruction_camera_index(reconstruction, framenr, 1);
2118
2119         if (a == -1) {
2120                 unit_m4(mat);
2121
2122                 return;
2123         }
2124
2125         if (cameras[a].framenr != framenr && a > 0 && a < reconstruction->camnr - 1) {
2126                 float t = ((float)framenr - cameras[a].framenr) / (cameras[a + 1].framenr - cameras[a].framenr);
2127
2128                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a + 1].mat, t);
2129         }
2130         else {
2131                 copy_m4_m4(mat, cameras[a].mat);
2132         }
2133
2134         scale_reconstructed_camera(object, mat);
2135 }
2136
2137 void BKE_get_tracking_mat(Scene *scene, Object *ob, float mat[4][4])
2138 {
2139         if (!ob) {
2140                 if (scene->camera)
2141                         ob = scene->camera;
2142                 else
2143                         ob = BKE_scene_camera_find(scene);
2144         }
2145
2146         if (ob)
2147                 BKE_object_where_is_calc_mat4(scene, ob, mat);
2148         else
2149                 unit_m4(mat);
2150 }
2151
2152 void BKE_tracking_camera_shift(MovieTracking *tracking, int winx, int winy, float *shiftx, float *shifty)
2153 {
2154         /* indeed in both of cases it should be winx -- it's just how camera shift works for blender's camera */
2155         *shiftx = (0.5f * winx - tracking->camera.principal[0]) / winx;
2156         *shifty = (0.5f * winy - tracking->camera.principal[1]) / winx;
2157 }
2158
2159 void BKE_tracking_camera_to_blender(MovieTracking *tracking, Scene *scene, Camera *camera, int width, int height)
2160 {
2161         float focal = tracking->camera.focal;
2162
2163         camera->sensor_x = tracking->camera.sensor_width;
2164         camera->sensor_fit = CAMERA_SENSOR_FIT_AUTO;
2165         camera->lens = focal * camera->sensor_x / width;
2166
2167         scene->r.xsch = width * tracking->camera.pixel_aspect;
2168         scene->r.ysch = height;
2169
2170         scene->r.xasp = 1.0f;
2171         scene->r.yasp = 1.0f;
2172
2173         BKE_tracking_camera_shift(tracking, width, height, &camera->shiftx, &camera->shifty);
2174 }
2175
2176 void BKE_tracking_projection_matrix(MovieTracking *tracking, MovieTrackingObject *object,
2177                                     int framenr, int winx, int winy, float mat[4][4])
2178 {
2179         MovieReconstructedCamera *camera;
2180         float lens = tracking->camera.focal * tracking->camera.sensor_width / (float)winx;
2181         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
2182         float winmat[4][4];
2183         float ycor =  1.0f / tracking->camera.pixel_aspect;
2184         float shiftx, shifty, winside = MAX2(winx, winy);
2185
2186         BKE_tracking_camera_shift(tracking, winx, winy, &shiftx, &shifty);
2187
2188         clipsta = 0.1f;
2189         clipend = 1000.0f;
2190
2191         if (winx >= winy)
2192                 viewfac = (lens * winx) / tracking->camera.sensor_width;
2193         else
2194                 viewfac = (ycor * lens * winy) / tracking->camera.sensor_width;
2195
2196         pixsize = clipsta / viewfac;
2197
2198         left = -0.5f * (float)winx + shiftx * winside;
2199         bottom = -0.5f * (ycor) * (float)winy + shifty * winside;
2200         right =  0.5f * (float)winx + shiftx * winside;
2201         top =  0.5f * (ycor) * (float)winy + shifty * winside;
2202
2203         left *= pixsize;
2204         right *= pixsize;
2205         bottom *= pixsize;
2206         top *= pixsize;
2207
2208         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
2209
2210         camera = BKE_tracking_get_reconstructed_camera(tracking, object, framenr);
2211
2212         if (camera) {
2213                 float imat[4][4];
2214
2215                 invert_m4_m4(imat, camera->mat);
2216                 mult_m4_m4m4(mat, winmat, imat);
2217         }
2218         else copy_m4_m4(mat, winmat);
2219 }
2220
2221 ListBase *BKE_tracking_get_tracks(MovieTracking *tracking)
2222 {
2223         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
2224
2225         if (object && (object->flag & TRACKING_OBJECT_CAMERA) == 0) {
2226                 return &object->tracks;
2227         }
2228
2229         return &tracking->tracks;
2230 }
2231
2232 MovieTrackingTrack *BKE_tracking_active_track(MovieTracking *tracking)
2233 {
2234         ListBase *tracksbase;
2235
2236         if (!tracking->act_track)
2237                 return NULL;
2238
2239         tracksbase = BKE_tracking_get_tracks(tracking);
2240
2241         /* check that active track is in current tracks list */
2242         if (BLI_findindex(tracksbase, tracking->act_track) >= 0)
2243                 return tracking->act_track;
2244
2245         return NULL;
2246 }
2247
2248 MovieTrackingObject *BKE_tracking_active_object(MovieTracking *tracking)
2249 {
2250         return BLI_findlink(&tracking->objects, tracking->objectnr);
2251 }
2252
2253 MovieTrackingObject *BKE_tracking_get_camera_object(MovieTracking *tracking)
2254 {
2255         MovieTrackingObject *object = tracking->objects.first;
2256
2257         while (object) {
2258                 if (object->flag & TRACKING_OBJECT_CAMERA)
2259                         return object;
2260
2261                 object = object->next;
2262         }
2263
2264         return NULL;
2265 }
2266
2267 ListBase *BKE_tracking_object_tracks(MovieTracking *tracking, MovieTrackingObject *object)
2268 {
2269         if (object->flag & TRACKING_OBJECT_CAMERA) {
2270                 return &tracking->tracks;
2271         }
2272
2273         return &object->tracks;
2274 }
2275
2276 MovieTrackingReconstruction *BKE_tracking_object_reconstruction(MovieTracking *tracking, MovieTrackingObject *object)
2277 {
2278         if (object->flag & TRACKING_OBJECT_CAMERA) {
2279                 return &tracking->reconstruction;
2280         }
2281
2282         return &object->reconstruction;
2283 }
2284
2285 MovieTrackingReconstruction *BKE_tracking_get_reconstruction(MovieTracking *tracking)
2286 {
2287         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
2288
2289         return BKE_tracking_object_reconstruction(tracking, object);
2290 }
2291
2292 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
2293 {
2294         MovieTrackingCamera *camera = &tracking->camera;
2295
2296 #ifdef WITH_LIBMV
2297         double x, y;
2298         float aspy = 1.0f / tracking->camera.pixel_aspect;
2299
2300         /* normalize coords */
2301         x = (co[0] - camera->principal[0]) / camera->focal;
2302         y = (co[1] - camera->principal[1] * aspy) / camera->focal;
2303
2304         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
2305                                     camera->k1, camera->k2, camera->k3, x, y, &x, &y);
2306
2307         /* result is in image coords already */
2308         nco[0] = x;
2309         nco[1] = y;
2310 #else
2311         (void) camera;
2312         (void) co;
2313         (void) nco;
2314 #endif
2315 }
2316
2317 void BKE_tracking_invert_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
2318 {
2319         MovieTrackingCamera *camera = &tracking->camera;
2320
2321 #ifdef WITH_LIBMV
2322         double x = co[0], y = co[1];
2323         float aspy = 1.0f / tracking->camera.pixel_aspect;
2324
2325         libmv_InvertIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
2326                                camera->k1, camera->k2, camera->k3, x, y, &x, &y);
2327
2328         nco[0] = x * camera->focal + camera->principal[0];
2329         nco[1] = y * camera->focal + camera->principal[1] * aspy;
2330 #else
2331         (void) camera;
2332         (void) co;
2333         (void) nco;
2334 #endif
2335 }
2336
2337 #ifdef WITH_LIBMV
2338 static int point_in_stroke(bGPDstroke *stroke, float x, float y)
2339 {
2340         int i, prev;
2341         int count = 0;
2342         bGPDspoint *points = stroke->points;
2343
2344         prev = stroke->totpoints - 1;
2345
2346         for (i = 0; i < stroke->totpoints; i++) {
2347                 if ((points[i].y < y && points[prev].y >= y) || (points[prev].y < y && points[i].y >= y)) {
2348                         float fac = (y - points[i].y) / (points[prev].y - points[i].y);
2349
2350                         if (points[i].x + fac * (points[prev].x - points[i].x) < x)
2351                                 count++;
2352                 }
2353
2354                 prev = i;
2355         }
2356
2357         return count % 2;
2358 }
2359
2360 static int point_in_layer(bGPDlayer *layer, float x, float y)
2361 {
2362         bGPDframe *frame = layer->frames.first;
2363
2364         while (frame) {
2365                 bGPDstroke *stroke = frame->strokes.first;
2366
2367                 while (stroke) {
2368                         if (point_in_stroke(stroke, x, y))
2369                                 return TRUE;
2370
2371                         stroke = stroke->next;
2372                 }
2373                 frame = frame->next;
2374         }
2375
2376         return FALSE;
2377 }
2378
2379 static void retrieve_libmv_features(MovieTracking *tracking, ListBase *tracksbase,
2380                                     struct libmv_Features *features, int framenr, int width, int height,
2381                                     bGPDlayer *layer, int place_outside_layer)
2382 {
2383         int a;
2384
2385         a = libmv_countFeatures(features);
2386         while (a--) {
2387                 MovieTrackingTrack *track;
2388                 double x, y, size, score;
2389                 int ok = TRUE;
2390                 float xu, yu;
2391
2392                 libmv_getFeature(features, a, &x, &y, &score, &size);
2393
2394                 xu = x / width;
2395                 yu = y / height;
2396
2397                 if (layer)
2398                         ok = point_in_layer(layer, xu, yu) != place_outside_layer;
2399
2400                 if (ok) {
2401                         track = BKE_tracking_add_track(tracking, tracksbase, xu, yu, framenr, width, height);
2402                         track->flag |= SELECT;
2403                         track->pat_flag |= SELECT;
2404                         track->search_flag |= SELECT;
2405                 }
2406         }
2407 }
2408 #endif
2409
2410 void BKE_tracking_detect_fast(MovieTracking *tracking, ListBase *tracksbase, ImBuf *ibuf,
2411                               int framenr, int margin, int min_trackness, int min_distance, bGPDlayer *layer,
2412                               int place_outside_layer)
2413 {
2414 #ifdef WITH_LIBMV
2415         struct libmv_Features *features;
2416         unsigned char *pixels = get_ucharbuf(ibuf);
2417
2418         features = libmv_detectFeaturesFAST(pixels, ibuf->x, ibuf->y, ibuf->x,
2419                                             margin, min_trackness, min_distance);
2420
2421         MEM_freeN(pixels);
2422
2423         retrieve_libmv_features(tracking, tracksbase, features, framenr,
2424                                 ibuf->x, ibuf->y, layer, place_outside_layer);
2425
2426         libmv_destroyFeatures(features);
2427 #else
2428         (void) tracking;
2429         (void) tracksbase;
2430         (void) ibuf;
2431         (void) framenr;
2432         (void) margin;
2433         (void) min_trackness;
2434         (void) min_distance;
2435         (void) layer;
2436         (void) place_outside_layer;
2437 #endif
2438 }
2439
2440 MovieTrackingTrack *BKE_tracking_indexed_track(MovieTracking *tracking, int tracknr, ListBase **tracksbase_r)
2441 {
2442         MovieTrackingObject *object;
2443         int cur = 1;
2444
2445         object = tracking->objects.first;
2446         while (object) {
2447                 ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2448                 MovieTrackingTrack *track = tracksbase->first;
2449
2450                 while (track) {
2451                         if (track->flag & TRACK_HAS_BUNDLE) {
2452                                 if (cur == tracknr) {
2453                                         *tracksbase_r = tracksbase;
2454                                         return track;
2455                                 }
2456
2457                                 cur++;
2458                         }
2459
2460                         track = track->next;
2461                 }
2462
2463                 object = object->next;
2464         }
2465
2466         *tracksbase_r = NULL;
2467
2468         return NULL;
2469 }
2470
2471 static int stabilization_median_point(MovieTracking *tracking, int framenr, float median[2])
2472 {
2473         int ok = FALSE;
2474         float min[2], max[2];
2475         MovieTrackingTrack *track;
2476
2477         INIT_MINMAX2(min, max);
2478
2479         track = tracking->tracks.first;
2480         while (track) {
2481                 if (track->flag & TRACK_USE_2D_STAB) {
2482                         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
2483
2484                         DO_MINMAX2(marker->pos, min, max);
2485
2486                         ok = TRUE;
2487                 }
2488
2489                 track = track->next;
2490         }
2491
2492         median[0] = (max[0] + min[0]) / 2.0f;
2493         median[1] = (max[1] + min[1]) / 2.0f;
2494
2495         return ok;
2496 }
2497
2498 static void calculate_stabdata(MovieTracking *tracking, int framenr, float width, float height,
2499                                float firstmedian[2], float median[2], float loc[2], float *scale, float *angle)
2500 {
2501         MovieTrackingStabilization *stab = &tracking->stabilization;
2502
2503         *scale = (stab->scale - 1.0f) * stab->scaleinf + 1.0f;
2504         *angle = 0.0f;
2505
2506         loc[0] = (firstmedian[0] - median[0]) *width * (*scale);
2507         loc[1] = (firstmedian[1] - median[1]) *height * (*scale);
2508
2509         mul_v2_fl(loc, stab->locinf);
2510
2511         if ((stab->flag & TRACKING_STABILIZE_ROTATION) && stab->rot_track && stab->rotinf) {
2512                 MovieTrackingMarker *marker;
2513                 float a[2], b[2];
2514                 float x0 = (float)width / 2.0f, y0 = (float)height / 2.0f;
2515                 float x = median[0] * width, y = median[1] * height;
2516
2517                 marker = BKE_tracking_get_marker(stab->rot_track, 1);
2518                 sub_v2_v2v2(a, marker->pos, firstmedian);
2519                 a[0] *= width;
2520                 a[1] *= height;
2521
2522                 marker = BKE_tracking_get_marker(stab->rot_track, framenr);
2523                 sub_v2_v2v2(b, marker->pos, median);
2524                 b[0] *= width;
2525                 b[1] *= height;
2526
2527                 *angle = -atan2(a[0] * b[1] - a[1] * b[0], a[0] * b[0] + a[1] * b[1]);
2528                 *angle *= stab->rotinf;
2529
2530                 /* convert to rotation around image center */
2531                 loc[0] -= (x0 + (x - x0) * cosf(*angle) - (y - y0) * sinf(*angle) - x) * (*scale);
2532                 loc[1] -= (y0 + (x - x0) * sinf(*angle) + (y - y0) * cosf(*angle) - y) * (*scale);
2533         }
2534 }
2535
2536 static float stabilization_auto_scale_factor(MovieTracking *tracking, int width, int height)
2537 {
2538         float firstmedian[2];
2539         MovieTrackingStabilization *stab = &tracking->stabilization;
2540         float aspect = tracking->camera.pixel_aspect;
2541
2542         if (stab->ok)
2543                 return stab->scale;
2544
2545         if (stabilization_median_point(tracking, 1, firstmedian)) {
2546                 int sfra = INT_MAX, efra = INT_MIN, cfra;
2547                 float scale = 1.0f;
2548                 MovieTrackingTrack *track;
2549
2550                 stab->scale = 1.0f;
2551
2552                 track = tracking->tracks.first;
2553                 while (track) {
2554                         if (track->flag & TRACK_USE_2D_STAB ||
2555                            ((stab->flag & TRACKING_STABILIZE_ROTATION) && track == stab->rot_track))
2556                         {
2557                                 sfra = MIN2(sfra, track->markers[0].framenr);
2558                                 efra = MAX2(efra, track->markers[track->markersnr - 1].framenr);
2559                         }
2560
2561                         track = track->next;
2562                 }
2563
2564                 for (cfra = sfra; cfra <= efra; cfra++) {
2565                         float median[2];
2566                         float loc[2], angle, tmp_scale;
2567                         int i;
2568                         float mat[4][4];
2569                         float points[4][2] = {{0.0f, 0.0f}, {0.0f, height}, {width, height}, {width, 0.0f}};
2570                         float si, co;
2571
2572                         stabilization_median_point(tracking, cfra, median);
2573
2574                         calculate_stabdata(tracking, cfra, width, height, firstmedian, median, loc, &tmp_scale, &angle);
2575
2576                         BKE_tracking_stabdata_to_mat4(width, height, aspect, loc, 1.0f, angle, mat);
2577
2578                         si = sin(angle);
2579                         co = cos(angle);
2580
2581                         for (i = 0; i < 4; i++) {
2582                                 int j;
2583                                 float a[3] = {0.0f, 0.0f, 0.0f}, b[3] = {0.0f, 0.0f, 0.0f};
2584
2585                                 copy_v3_v3(a, points[i]);
2586                                 copy_v3_v3(b, points[(i + 1) % 4]);
2587
2588                                 mul_m4_v3(mat, a);
2589                                 mul_m4_v3(mat, b);
2590
2591                                 for (j = 0; j < 4; j++) {
2592                                         float point[3] = {points[j][0], points[j][1], 0.0f};
2593                                         float v1[3], v2[3];
2594
2595                                         sub_v3_v3v3(v1, b, a);
2596                                         sub_v3_v3v3(v2, point, a);
2597
2598                                         if (cross_v2v2(v1, v2) >= 0.0f) {
2599                                                 const float rotDx[4][2] = {{1.0f, 0.0f}, {0.0f, -1.0f}, {-1.0f, 0.0f}, {0.0f, 1.0f}};
2600                                                 const float rotDy[4][2] = {{0.0f, 1.0f}, {1.0f, 0.0f}, {0.0f, -1.0f}, {-1.0f, 0.0f}};
2601
2602                                                 float dx = loc[0] * rotDx[j][0] + loc[1] * rotDx[j][1],
2603                                                       dy = loc[0] * rotDy[j][0] + loc[1] * rotDy[j][1];
2604
2605                                                 float w, h, E, F, G, H, I, J, K, S;
2606
2607                                                 if (j % 2) {
2608                                                         w = (float)height / 2.0f;
2609                                                         h = (float)width / 2.0f;
2610                                                 }
2611                                                 else {
2612                                                         w = (float)width / 2.0f;
2613                                                         h = (float)height / 2.0f;
2614                                                 }
2615
2616                                                 E = -w*co + h*si;
2617                                                 F = -h*co - w*si;
2618
2619                                                 if ((i % 2) == (j % 2)) {
2620                                                         G = -w*co - h*si;
2621                                                         H = h*co - w*si;
2622                                                 }
2623                                                 else {
2624                                                         G = w*co + h*si;
2625                                                         H = -h*co + w*si;
2626                                                 }
2627
2628                                                 I = F - H;
2629                                                 J = G - E;
2630                                                 K = G*F - E*H;
2631
2632                                                 S = (-w*I - h*J) / (dx*I + dy*J + K);
2633
2634                                                 scale = MAX2(scale, S);
2635                                         }
2636                                 }
2637                         }
2638                 }
2639
2640                 stab->scale = scale;
2641
2642                 if (stab->maxscale > 0.0f)
2643                         stab->scale = MIN2(stab->scale, stab->maxscale);
2644         }
2645         else {
2646                 stab->scale = 1.0f;
2647         }
2648
2649         stab->ok = TRUE;
2650
2651         return stab->scale;
2652 }
2653
2654 static ImBuf* stabilize_alloc_ibuf(ImBuf *cacheibuf, ImBuf *srcibuf, int fill)
2655 {
2656         int flags;
2657
2658         if (cacheibuf && (cacheibuf->x != srcibuf->x || cacheibuf->y != srcibuf->y)) {
2659                 IMB_freeImBuf(cacheibuf);
2660                 cacheibuf = NULL;
2661         }
2662
2663         flags = IB_rect;
2664
2665         if (srcibuf->rect_float)
2666                 flags |= IB_rectfloat;
2667
2668         if (cacheibuf) {
2669                 if (fill) {
2670                         float col[4] = {0.0f, 0.0f, 0.0f, 0.0f};
2671
2672                         IMB_rectfill(cacheibuf, col);
2673                 }
2674         }
2675         else {
2676                 cacheibuf = IMB_allocImBuf(srcibuf->x, srcibuf->y, srcibuf->planes, flags);
2677                 cacheibuf->profile = srcibuf->profile;
2678         }
2679
2680         return cacheibuf;
2681 }
2682
2683 void BKE_tracking_stabilization_data(MovieTracking *tracking, int framenr, int width, int height,
2684                                      float loc[2], float *scale, float *angle)
2685 {
2686         float firstmedian[2], median[2];
2687         MovieTrackingStabilization *stab = &tracking->stabilization;
2688
2689         if ((stab->flag & TRACKING_2D_STABILIZATION) == 0) {
2690                 zero_v2(loc);
2691                 *scale = 1.0f;
2692                 *angle = 0.0f;
2693
2694                 return;
2695         }
2696
2697         if (stabilization_median_point(tracking, 1, firstmedian)) {
2698                 stabilization_median_point(tracking, framenr, median);
2699
2700                 if ((stab->flag & TRACKING_AUTOSCALE) == 0)
2701                         stab->scale = 1.0f;
2702
2703                 if (!stab->ok) {
2704                         if (stab->flag & TRACKING_AUTOSCALE)
2705                                 stabilization_auto_scale_factor(tracking, width, height);
2706
2707                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2708
2709                         stab->ok = TRUE;
2710                 }
2711                 else {
2712                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2713                 }
2714         }
2715         else {
2716                 zero_v2(loc);
2717                 *scale = 1.0f;
2718                 *angle = 0.0f;
2719         }
2720 }
2721
2722 ImBuf *BKE_tracking_stabilize(MovieTracking *tracking, int framenr, ImBuf *ibuf,
2723                               float loc[2], float *scale, float *angle)
2724 {
2725         float tloc[2], tscale, tangle;
2726         MovieTrackingStabilization *stab = &tracking->stabilization;
2727         ImBuf *tmpibuf;
2728         float width = ibuf->x, height = ibuf->y;
2729         float aspect = tracking->camera.pixel_aspect;
2730
2731         if (loc)
2732                 copy_v2_v2(tloc, loc);
2733
2734         if (scale)
2735                 tscale = *scale;
2736
2737         if ((stab->flag & TRACKING_2D_STABILIZATION) == 0) {
2738                 if (loc)
2739                         zero_v2(loc);
2740
2741                 if (scale)
2742                         *scale = 1.0f;
2743
2744                 return ibuf;
2745         }
2746
2747         BKE_tracking_stabilization_data(tracking, framenr, width, height, tloc, &tscale, &tangle);
2748
2749         tmpibuf = stabilize_alloc_ibuf(NULL, ibuf, TRUE);
2750
2751         /* scale would be handled by matrix transformation when angle is non-zero */
2752         if (tscale != 1.0f && tangle == 0.0f) {
2753                 ImBuf *scaleibuf;
2754
2755                 stabilization_auto_scale_factor(tracking, width, height);
2756
2757                 scaleibuf = stabilize_alloc_ibuf(stab->scaleibuf, ibuf, 0);
2758                 stab->scaleibuf = scaleibuf;
2759
2760                 IMB_rectcpy(scaleibuf, ibuf, 0, 0, 0, 0, ibuf->x, ibuf->y);
2761                 IMB_scalefastImBuf(scaleibuf, ibuf->x*tscale, ibuf->y*tscale);
2762
2763                 ibuf = scaleibuf;
2764         }
2765
2766         if (tangle == 0.0f) {
2767                 /* if angle is zero, then it's much faster to use rect copy
2768                  * but could be issues with subpixel precisions */
2769                 IMB_rectcpy(tmpibuf, ibuf,
2770                             tloc[0] - (tscale - 1.0f) * width / 2.0f,
2771                             tloc[1] - (tscale - 1.0f) * height / 2.0f,
2772                             0, 0, ibuf->x, ibuf->y);
2773         }
2774         else {
2775                 float mat[4][4];
2776                 int i, j, filter = tracking->stabilization.filter;
2777                 void (*interpolation) (struct ImBuf*, struct ImBuf*, float, float, int, int) = NULL;
2778
2779                 BKE_tracking_stabdata_to_mat4(ibuf->x, ibuf->y, aspect, tloc, tscale, tangle, mat);
2780                 invert_m4(mat);
2781
2782                 if (filter == TRACKING_FILTER_NEAREAST)
2783                         interpolation = neareast_interpolation;
2784                 else if (filter == TRACKING_FILTER_BILINEAR)
2785                         interpolation = bilinear_interpolation;
2786                 else if (filter == TRACKING_FILTER_BICUBIC)
2787                         interpolation = bicubic_interpolation;
2788                 else
2789                         /* fallback to default interpolation method */
2790                         interpolation = neareast_interpolation;
2791
2792                 for (j = 0; j < tmpibuf->y; j++) {
2793                         for (i = 0; i < tmpibuf->x;i++) {
2794                                 float vec[3] = {i, j, 0};
2795
2796                                 mul_v3_m4v3(vec, mat, vec);
2797
2798                                 interpolation(ibuf, tmpibuf, vec[0], vec[1], i, j);
2799                         }
2800                 }
2801         }
2802
2803         tmpibuf->userflags |= IB_MIPMAP_INVALID;
2804
2805         if (tmpibuf->rect_float)
2806                 tmpibuf->userflags |= IB_RECT_INVALID;
2807
2808         if (loc)
2809                 copy_v2_v2(loc, tloc);
2810
2811         if (scale)
2812                 *scale = tscale;
2813
2814         if (angle)
2815                 *angle = tangle;
2816
2817         return tmpibuf;
2818 }
2819
2820 void BKE_tracking_stabdata_to_mat4(int width, int height, float aspect,
2821                                    float loc[2], float scale, float angle, float mat[4][4])
2822 {
2823         float lmat[4][4], rmat[4][4], smat[4][4], cmat[4][4], icmat[4][4], amat[4][4], iamat[4][4];
2824         float svec[3] = {scale, scale, scale};
2825
2826         unit_m4(rmat);
2827         unit_m4(lmat);
2828         unit_m4(smat);
2829         unit_m4(cmat);
2830         unit_m4(amat);
2831
2832         /* aspect ratio correction matrix */
2833         amat[0][0] = 1.0f / aspect;
2834         invert_m4_m4(iamat, amat);
2835
2836         /* image center as rotation center */
2837         cmat[3][0] = (float)width / 2.0f;
2838         cmat[3][1] = (float)height / 2.0f;
2839         invert_m4_m4(icmat, cmat);
2840
2841         size_to_mat4(smat, svec);               /* scale matrix */
2842         add_v2_v2(lmat[3], loc);                /* translation matrix */
2843         rotate_m4(rmat, 'Z', angle);    /* rotation matrix */
2844
2845         /* compose transformation matrix */
2846         mul_serie_m4(mat, lmat, cmat, amat, rmat, iamat, smat, icmat, NULL);
2847 }
2848
2849 MovieDistortion *BKE_tracking_distortion_create(void)
2850 {
2851         MovieDistortion *distortion;
2852
2853         distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2854
2855         return distortion;
2856 }
2857
2858 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
2859 {
2860         MovieDistortion *new_distortion;
2861
2862         new_distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2863
2864 #ifdef WITH_LIBMV
2865         new_distortion->intrinsics = libmv_CameraIntrinsicsCopy(distortion->intrinsics);
2866 #else
2867         (void) distortion;
2868 #endif
2869
2870         return new_distortion;
2871 }
2872
2873 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking, int width, int height)
2874 {
2875         MovieTrackingCamera *camera = &tracking->camera;
2876         float aspy = 1.0f / tracking->camera.pixel_aspect;
2877
2878 #ifdef WITH_LIBMV
2879         if (!distortion->intrinsics) {
2880                 distortion->intrinsics = libmv_CameraIntrinsicsNew(camera->focal,
2881                                 camera->principal[0], camera->principal[1] * aspy,
2882                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2883         }
2884         else {
2885                 libmv_CameraIntrinsicsUpdate(distortion->intrinsics, camera->focal,
2886                                 camera->principal[0], camera->principal[1] * aspy,
2887                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2888         }
2889 #else
2890         (void) distortion;
2891         (void) width;
2892         (void) height;
2893         (void) camera;
2894         (void) aspy;
2895 #endif
2896 }
2897
2898 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking,
2899                                     ImBuf *ibuf, int width, int height, float overscan, int undistort)
2900 {
2901         ImBuf *resibuf;
2902
2903         BKE_tracking_distortion_update(distortion, tracking, width, height);
2904
2905         resibuf = IMB_dupImBuf(ibuf);
2906
2907         if (ibuf->rect_float) {
2908 #ifdef WITH_LIBMV
2909                 if (undistort) {
2910                         libmv_CameraIntrinsicsUndistortFloat(distortion->intrinsics,
2911                                                 ibuf->rect_float, resibuf->rect_float,
2912                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2913                 }
2914                 else {
2915                         libmv_CameraIntrinsicsDistortFloat(distortion->intrinsics,
2916                                                 ibuf->rect_float, resibuf->rect_float,
2917                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2918                 }
2919 #endif
2920
2921                 resibuf->userflags |= IB_RECT_INVALID;
2922         }
2923         else {
2924 #ifdef WITH_LIBMV
2925                 if (undistort) {
2926                                 libmv_CameraIntrinsicsUndistortByte(distortion->intrinsics,
2927                                                         (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2928                                                         ibuf->x, ibuf->y, overscan, ibuf->channels);
2929                 }
2930                 else {
2931                         libmv_CameraIntrinsicsDistortByte(distortion->intrinsics,
2932                                                 (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2933                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2934                 }
2935 #endif
2936         }
2937
2938 #ifndef WITH_LIBMV
2939         (void) overscan;
2940         (void) undistort;
2941 #endif
2942
2943         return resibuf;
2944 }
2945
2946 void BKE_tracking_distortion_destroy(MovieDistortion *distortion)
2947 {
2948 #ifdef WITH_LIBMV
2949         libmv_CameraIntrinsicsDestroy(distortion->intrinsics);
2950 #endif
2951
2952         MEM_freeN(distortion);
2953 }
2954
2955 ImBuf *BKE_tracking_undistort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2956 {
2957         MovieTrackingCamera *camera = &tracking->camera;
2958
2959         if (camera->intrinsics == NULL)
2960                 camera->intrinsics = BKE_tracking_distortion_create();
2961
2962         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 1);
2963 }
2964
2965 ImBuf *BKE_tracking_distort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2966 {
2967         MovieTrackingCamera *camera = &tracking->camera;
2968
2969         if (camera->intrinsics == NULL)
2970                 camera->intrinsics = BKE_tracking_distortion_create();
2971
2972         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 0);
2973 }
2974
2975 /* area - which part of marker should be selected. see TRACK_AREA_* constants */
2976 void BKE_tracking_select_track(ListBase *tracksbase, MovieTrackingTrack *track, int area, int extend)
2977 {
2978         if (extend) {
2979                 BKE_tracking_track_flag(track, area, SELECT, 0);
2980         }
2981         else {
2982                 MovieTrackingTrack *cur = tracksbase->first;
2983
2984                 while (cur) {
2985                         if ((cur->flag & TRACK_HIDDEN) == 0) {
2986                                 if (cur == track) {
2987                                         BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2988                                         BKE_tracking_track_flag(cur, area, SELECT, 0);
2989                                 }
2990                                 else {
2991                                         BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2992                                 }
2993                         }
2994
2995                         cur = cur->next;
2996                 }
2997         }
2998 }
2999
3000 void BKE_tracking_deselect_track(MovieTrackingTrack *track, int area)
3001 {
3002         BKE_tracking_track_flag(track, area, SELECT, 1);
3003 }
3004
3005 MovieTrackingObject *BKE_tracking_new_object(MovieTracking *tracking, const char *name)
3006 {
3007         MovieTrackingObject *object = MEM_callocN(sizeof(MovieTrackingObject), "tracking object");
3008
3009         if (tracking->tot_object == 0) {
3010                 /* first object is always camera */
3011                 BLI_strncpy(object->name, "Camera", sizeof(object->name));
3012
3013                 object->flag |= TRACKING_OBJECT_CAMERA;
3014         }
3015         else {
3016                 BLI_strncpy(object->name, name, sizeof(object->name));
3017         }
3018
3019         BLI_addtail(&tracking->objects, object);
3020
3021         tracking->tot_object++;
3022         tracking->objectnr = BLI_countlist(&tracking->objects) - 1;
3023
3024         object->scale = 1.0f;
3025
3026         BKE_tracking_object_unique_name(tracking, object);
3027
3028         return object;
3029 }
3030
3031 void BKE_tracking_remove_object(MovieTracking *tracking, MovieTrackingObject *object)
3032 {
3033         MovieTrackingTrack *track;
3034         int index = BLI_findindex(&tracking->objects, object);
3035
3036         if (index < 0)
3037                 return;
3038
3039         if (object->flag & TRACKING_OBJECT_CAMERA) {
3040                 /* object used for camera solving can't be deleted */
3041                 return;
3042         }
3043
3044         track = object->tracks.first;
3045         while (track) {
3046                 if (track == tracking->act_track)
3047                         tracking->act_track = NULL;
3048
3049                 track = track->next;
3050         }
3051
3052         tracking_object_free(object);
3053         BLI_freelinkN(&tracking->objects, object);
3054
3055         tracking->tot_object--;
3056
3057         if (index > 0)
3058                 tracking->objectnr = index - 1;
3059         else
3060                 tracking->objectnr = 0;
3061 }
3062
3063 void BKE_tracking_object_unique_name(MovieTracking *tracking, MovieTrackingObject *object)
3064 {
3065         BLI_uniquename(&tracking->objects, object, "Object", '.',
3066                        offsetof(MovieTrackingObject, name), sizeof(object->name));
3067 }
3068
3069 MovieTrackingObject *BKE_tracking_named_object(MovieTracking *tracking, const char *name)
3070 {
3071         MovieTrackingObject *object = tracking->objects.first;
3072
3073         while (object) {
3074                 if (!strcmp(object->name, name))
3075                         return object;
3076
3077                 object = object->next;
3078         }
3079
3080         return NULL;
3081 }
3082
3083 /*********************** dopesheet functions *************************/
3084
3085 static int channels_alpha_sort(void *a, void *b)
3086 {
3087         MovieTrackingDopesheetChannel *channel_a = a;
3088         MovieTrackingDopesheetChannel *channel_b = b;
3089
3090         if (BLI_strcasecmp(channel_a->track->name, channel_b->track->name) > 0)
3091                 return 1;
3092         else
3093                 return 0;
3094 }
3095
3096 static int channels_total_track_sort(void *a, void *b)
3097 {
3098         MovieTrackingDopesheetChannel *channel_a = a;
3099         MovieTrackingDopesheetChannel *channel_b = b;
3100
3101         if (channel_a->total_frames > channel_b->total_frames)
3102                 return 1;
3103         else
3104                 return 0;
3105 }
3106
3107 static int channels_longest_segment_sort(void *a, void *b)
3108 {
3109         MovieTrackingDopesheetChannel *channel_a = a;
3110         MovieTrackingDopesheetChannel *channel_b = b;
3111
3112         if (channel_a->max_segment > channel_b->max_segment)
3113                 return 1;
3114         else
3115                 return 0;
3116 }
3117
3118 static int channels_average_error_sort(void *a, void *b)
3119 {
3120         MovieTrackingDopesheetChannel *channel_a = a;
3121         MovieTrackingDopesheetChannel *channel_b = b;
3122
3123         if (channel_a->track->error > channel_b->track->error)
3124                 return 1;
3125         else
3126                 return 0;
3127 }
3128
3129 static int channels_alpha_inverse_sort(void *a, void *b)
3130 {
3131         if (channels_alpha_sort(a, b))
3132                 return 0;
3133         else
3134                 return 1;
3135 }
3136
3137 static int channels_total_track_inverse_sort(void *a, void *b)
3138 {
3139         if (channels_total_track_sort(a, b))
3140                 return 0;
3141         else
3142                 return 1;
3143 }
3144
3145 static int channels_longest_segment_inverse_sort(void *a, void *b)
3146 {
3147         if (channels_longest_segment_sort(a, b))
3148                 return 0;
3149         else
3150                 return 1;
3151 }
3152
3153 static int channels_average_error_inverse_sort(void *a, void *b)
3154 {
3155         MovieTrackingDopesheetChannel *channel_a = a;
3156         MovieTrackingDopesheetChannel *channel_b = b;
3157
3158         if (channel_a->track->error < channel_b->track->error)
3159                 return 1;
3160         else
3161                 return 0;
3162 }
3163
3164 static void channels_segments_calc(MovieTrackingDopesheetChannel *channel)
3165 {
3166         MovieTrackingTrack *track = channel->track;
3167         int i, segment;
3168
3169         channel->tot_segment = 0;
3170         channel->max_segment = 0;
3171         channel->total_frames = 0;
3172
3173         /* count */
3174         i = 0;
3175         while (i < track->markersnr) {
3176                 MovieTrackingMarker *marker = &track->markers[i];
3177
3178                 if ((marker->flag & MARKER_DISABLED) == 0) {
3179                         int prev_fra = marker->framenr, len = 0;
3180
3181                         i++;
3182                         while (i < track->markersnr) {
3183                                 marker = &track->markers[i];
3184
3185                                 if (marker->framenr != prev_fra + 1)
3186                                         break;
3187                                 if (marker->flag & MARKER_DISABLED)
3188                                         break;
3189
3190                                 prev_fra = marker->framenr;
3191                                 len++;
3192                                 i++;
3193                         }
3194
3195                         channel->tot_segment++;
3196                 }
3197
3198                 i++;
3199         }
3200
3201         if (!channel->tot_segment)
3202                 return;
3203
3204         channel->segments = MEM_callocN(2 * sizeof(int) * channel->tot_segment, "tracking channel segments");
3205
3206         /* create segments */
3207         i = 0;
3208         segment = 0;
3209         while (i < track->markersnr) {
3210                 MovieTrackingMarker *marker = &track->markers[i];
3211
3212                 if ((marker->flag & MARKER_DISABLED) == 0) {
3213                         MovieTrackingMarker *start_marker = marker;
3214                         int prev_fra = marker->framenr, len = 0;
3215
3216                         i++;
3217                         while (i < track->markersnr) {
3218                                 marker = &track->markers[i];
3219
3220                                 if (marker->framenr != prev_fra + 1)
3221                                         break;
3222                                 if (marker->flag & MARKER_DISABLED)
3223                                         break;
3224
3225                                 prev_fra = marker->framenr;
3226                                 channel->total_frames++;
3227                                 len++;
3228                                 i++;
3229                         }
3230
3231                         channel->segments[2 * segment] = start_marker->framenr;
3232                         channel->segments[2 * segment + 1] = start_marker->framenr + len;
3233
3234                         channel->max_segment =  MAX2(channel->max_segment, len);
3235                         segment++;
3236                 }
3237
3238                 i++;
3239         }
3240 }
3241
3242 static void  tracking_dopesheet_sort(MovieTracking *tracking, int sort_method, int inverse)
3243 {
3244         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
3245
3246         if (dopesheet->sort_method == sort_method && dopesheet->sort_inverse == inverse)
3247                 return;
3248
3249         if (inverse) {
3250                 if (sort_method == TRACK_SORT_NAME) {
3251                         BLI_sortlist(&dopesheet->channels, channels_alpha_inverse_sort);
3252                 }
3253                 else if (sort_method == TRACK_SORT_LONGEST) {
3254                         BLI_sortlist(&dopesheet->channels, channels_longest_segment_inverse_sort);
3255                 }
3256                 else if (sort_method == TRACK_SORT_TOTAL) {
3257                         BLI_sortlist(&dopesheet->channels, channels_total_track_inverse_so