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