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