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