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