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