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