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