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