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