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