Compositor: Speedup movie (un)distortion operation
[blender.git] / source / blender / blenkernel / intern / tracking.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2011 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation,
22  *                 Sergey Sharybin
23  *                 Keir Mierle
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/tracking.c
29  *  \ingroup bke
30  */
31
32 #include <stddef.h>
33 #include <limits.h>
34 #include <math.h>
35 #include <memory.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "DNA_anim_types.h"
40 #include "DNA_gpencil_types.h"
41 #include "DNA_camera_types.h"
42 #include "DNA_movieclip_types.h"
43 #include "DNA_object_types.h"   /* SELECT */
44 #include "DNA_scene_types.h"
45
46 #include "BLI_utildefines.h"
47 #include "BLI_math.h"
48 #include "BLI_math_base.h"
49 #include "BLI_listbase.h"
50 #include "BLI_path_util.h"
51 #include "BLI_string.h"
52 #include "BLI_threads.h"
53
54 #include "BLT_translation.h"
55
56 #include "BKE_fcurve.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 "RNA_access.h"
66
67 #include "libmv-capi.h"
68 #include "tracking_private.h"
69
70 typedef struct MovieDistortion {
71         struct libmv_CameraIntrinsics *intrinsics;
72         /* Parameters needed for coordinates normalization. */
73         float principal[2];
74         float pixel_aspect;
75         float focal;
76 } MovieDistortion;
77
78 static struct {
79         ListBase tracks;
80 } tracking_clipboard;
81
82 /*********************** Common functions *************************/
83
84 /* Free the whole list of tracks, list's head and tail are set to NULL. */
85 static void tracking_tracks_free(ListBase *tracks)
86 {
87         MovieTrackingTrack *track;
88
89         for (track = tracks->first; track; track = track->next) {
90                 BKE_tracking_track_free(track);
91         }
92
93         BLI_freelistN(tracks);
94 }
95
96 /* Free the whole list of plane tracks, list's head and tail are set to NULL. */
97 static void tracking_plane_tracks_free(ListBase *plane_tracks)
98 {
99         MovieTrackingPlaneTrack *plane_track;
100
101         for (plane_track = plane_tracks->first; plane_track; plane_track = plane_track->next) {
102                 BKE_tracking_plane_track_free(plane_track);
103         }
104
105         BLI_freelistN(plane_tracks);
106 }
107
108 /* Free reconstruction structures, only frees contents of a structure,
109  * (if structure is allocated in heap, it shall be handled outside).
110  *
111  * All the pointers inside structure becomes invalid after this call.
112  */
113 static void tracking_reconstruction_free(MovieTrackingReconstruction *reconstruction)
114 {
115         if (reconstruction->cameras)
116                 MEM_freeN(reconstruction->cameras);
117 }
118
119 /* Free memory used by tracking object, only frees contents of the structure,
120  * (if structure is allocated in heap, it shall be handled outside).
121  *
122  * All the pointers inside structure becomes invalid after this call.
123  */
124 static void tracking_object_free(MovieTrackingObject *object)
125 {
126         tracking_tracks_free(&object->tracks);
127         tracking_plane_tracks_free(&object->plane_tracks);
128         tracking_reconstruction_free(&object->reconstruction);
129 }
130
131 /* Free list of tracking objects, list's head and tail is set to NULL. */
132 static void tracking_objects_free(ListBase *objects)
133 {
134         MovieTrackingObject *object;
135
136         /* Free objects contents. */
137         for (object = objects->first; object; object = object->next)
138                 tracking_object_free(object);
139
140         /* Free objects themselves. */
141         BLI_freelistN(objects);
142 }
143
144 /* Free memory used by a dopesheet, only frees dopesheet contents.
145  * leaving dopesheet crystal clean for further usage.
146  */
147 static void tracking_dopesheet_free(MovieTrackingDopesheet *dopesheet)
148 {
149         MovieTrackingDopesheetChannel *channel;
150
151         /* Free channel's sergments. */
152         channel = dopesheet->channels.first;
153         while (channel) {
154                 if (channel->segments) {
155                         MEM_freeN(channel->segments);
156                 }
157
158                 channel = channel->next;
159         }
160
161         /* Free lists themselves. */
162         BLI_freelistN(&dopesheet->channels);
163         BLI_freelistN(&dopesheet->coverage_segments);
164
165         /* Ensure lists are clean. */
166         BLI_listbase_clear(&dopesheet->channels);
167         BLI_listbase_clear(&dopesheet->coverage_segments);
168         dopesheet->tot_channel = 0;
169 }
170
171 /* Free tracking structure, only frees structure contents
172  * (if structure is allocated in heap, it shall be handled outside).
173  *
174  * All the pointers inside structure becomes invalid after this call.
175  */
176 void BKE_tracking_free(MovieTracking *tracking)
177 {
178         tracking_tracks_free(&tracking->tracks);
179         tracking_plane_tracks_free(&tracking->plane_tracks);
180         tracking_reconstruction_free(&tracking->reconstruction);
181         tracking_objects_free(&tracking->objects);
182
183         if (tracking->camera.intrinsics)
184                 BKE_tracking_distortion_free(tracking->camera.intrinsics);
185
186         tracking_dopesheet_free(&tracking->dopesheet);
187 }
188
189 /* Initialize motion tracking settings to default values,
190  * used when new movie clip datablock is creating.
191  */
192 void BKE_tracking_settings_init(MovieTracking *tracking)
193 {
194         tracking->camera.sensor_width = 35.0f;
195         tracking->camera.pixel_aspect = 1.0f;
196         tracking->camera.units = CAMERA_UNITS_MM;
197
198         tracking->settings.default_motion_model = TRACK_MOTION_MODEL_TRANSLATION;
199         tracking->settings.default_minimum_correlation = 0.75;
200         tracking->settings.default_pattern_size = 21;
201         tracking->settings.default_search_size = 71;
202         tracking->settings.default_algorithm_flag |= TRACK_ALGORITHM_FLAG_USE_BRUTE;
203         tracking->settings.default_weight = 1.0f;
204         tracking->settings.dist = 1;
205         tracking->settings.object_distance = 1;
206
207         tracking->stabilization.scaleinf = 1.0f;
208         tracking->stabilization.locinf = 1.0f;
209         tracking->stabilization.rotinf = 1.0f;
210         tracking->stabilization.maxscale = 2.0f;
211         tracking->stabilization.filter = TRACKING_FILTER_BILINEAR;
212
213         BKE_tracking_object_add(tracking, "Camera");
214 }
215
216 /* Get list base of active object's tracks. */
217 ListBase *BKE_tracking_get_active_tracks(MovieTracking *tracking)
218 {
219         MovieTrackingObject *object = BKE_tracking_object_get_active(tracking);
220
221         if (object && (object->flag & TRACKING_OBJECT_CAMERA) == 0) {
222                 return &object->tracks;
223         }
224
225         return &tracking->tracks;
226 }
227
228 /* Get list base of active object's plane tracks. */
229 ListBase *BKE_tracking_get_active_plane_tracks(MovieTracking *tracking)
230 {
231         MovieTrackingObject *object = BKE_tracking_object_get_active(tracking);
232
233         if (object && (object->flag & TRACKING_OBJECT_CAMERA) == 0) {
234                 return &object->plane_tracks;
235         }
236
237         return &tracking->plane_tracks;
238 }
239
240 /* Get reconstruction data of active object. */
241 MovieTrackingReconstruction *BKE_tracking_get_active_reconstruction(MovieTracking *tracking)
242 {
243         MovieTrackingObject *object = BKE_tracking_object_get_active(tracking);
244
245         return BKE_tracking_object_get_reconstruction(tracking, object);
246 }
247
248 /* Get transformation matrix for a given object which is used
249  * for parenting motion tracker reconstruction to 3D world.
250  */
251 void BKE_tracking_get_camera_object_matrix(Scene *scene, Object *ob, float mat[4][4])
252 {
253         if (!ob) {
254                 if (scene->camera)
255                         ob = scene->camera;
256                 else
257                         ob = BKE_scene_camera_find(scene);
258         }
259
260         if (ob)
261                 BKE_object_where_is_calc_mat4(scene, ob, mat);
262         else
263                 unit_m4(mat);
264 }
265
266 /* Get projection matrix for camera specified by given tracking object
267  * and frame number.
268  *
269  * NOTE: frame number should be in clip space, not scene space
270  */
271 void BKE_tracking_get_projection_matrix(MovieTracking *tracking, MovieTrackingObject *object,
272                                         int framenr, int winx, int winy, float mat[4][4])
273 {
274         MovieReconstructedCamera *camera;
275         float lens = tracking->camera.focal * tracking->camera.sensor_width / (float)winx;
276         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
277         float winmat[4][4];
278         float ycor =  1.0f / tracking->camera.pixel_aspect;
279         float shiftx, shifty, winside = (float)min_ii(winx, winy);
280
281         BKE_tracking_camera_shift_get(tracking, winx, winy, &shiftx, &shifty);
282
283         clipsta = 0.1f;
284         clipend = 1000.0f;
285
286         if (winx >= winy)
287                 viewfac = (lens * winx) / tracking->camera.sensor_width;
288         else
289                 viewfac = (ycor * lens * winy) / tracking->camera.sensor_width;
290
291         pixsize = clipsta / viewfac;
292
293         left = -0.5f * (float)winx + shiftx * winside;
294         bottom = -0.5f * (ycor) * (float)winy + shifty * winside;
295         right =  0.5f * (float)winx + shiftx * winside;
296         top =  0.5f * (ycor) * (float)winy + shifty * winside;
297
298         left *= pixsize;
299         right *= pixsize;
300         bottom *= pixsize;
301         top *= pixsize;
302
303         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
304
305         camera = BKE_tracking_camera_get_reconstructed(tracking, object, framenr);
306
307         if (camera) {
308                 float imat[4][4];
309
310                 invert_m4_m4(imat, camera->mat);
311                 mul_m4_m4m4(mat, winmat, imat);
312         }
313         else {
314                 copy_m4_m4(mat, winmat);
315         }
316 }
317
318 /*********************** clipboard *************************/
319
320 /* Free clipboard by freeing memory used by all tracks in it. */
321 void BKE_tracking_clipboard_free(void)
322 {
323         MovieTrackingTrack *track = tracking_clipboard.tracks.first, *next_track;
324
325         while (track) {
326                 next_track = track->next;
327
328                 BKE_tracking_track_free(track);
329                 MEM_freeN(track);
330
331                 track = next_track;
332         }
333
334         BLI_listbase_clear(&tracking_clipboard.tracks);
335 }
336
337 /* Copy selected tracks from specified object to the clipboard. */
338 void BKE_tracking_clipboard_copy_tracks(MovieTracking *tracking, MovieTrackingObject *object)
339 {
340         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
341         MovieTrackingTrack *track = tracksbase->first;
342
343         /* First drop all tracks from current clipboard. */
344         BKE_tracking_clipboard_free();
345
346         /* Then copy all selected visible tracks to it. */
347         while (track) {
348                 if (TRACK_SELECTED(track) && (track->flag & TRACK_HIDDEN) == 0) {
349                         MovieTrackingTrack *new_track = BKE_tracking_track_duplicate(track);
350
351                         BLI_addtail(&tracking_clipboard.tracks, new_track);
352                 }
353
354                 track = track->next;
355         }
356 }
357
358 /* Check whether there're any tracks in the clipboard. */
359 bool BKE_tracking_clipboard_has_tracks(void)
360 {
361         return (BLI_listbase_is_empty(&tracking_clipboard.tracks) == false);
362 }
363
364 /* Paste tracks from clipboard to specified object.
365  *
366  * Names of new tracks in object are guaranteed to
367  * be unique here.
368  */
369 void BKE_tracking_clipboard_paste_tracks(MovieTracking *tracking, MovieTrackingObject *object)
370 {
371         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
372         MovieTrackingTrack *track = tracking_clipboard.tracks.first;
373
374         while (track) {
375                 MovieTrackingTrack *new_track = BKE_tracking_track_duplicate(track);
376                 if (track->prev == NULL) {
377                         tracking->act_track = new_track;
378                 }
379
380                 BLI_addtail(tracksbase, new_track);
381                 BKE_tracking_track_unique_name(tracksbase, new_track);
382
383                 track = track->next;
384         }
385 }
386
387 /*********************** Tracks *************************/
388
389 /* Add new track to a specified tracks base.
390  *
391  * Coordinates are expected to be in normalized 0..1 space,
392  * frame number is expected to be in clip space.
393  *
394  * Width and height are clip's dimension used to scale track's
395  * pattern and search regions.
396  */
397 MovieTrackingTrack *BKE_tracking_track_add(MovieTracking *tracking, ListBase *tracksbase, float x, float y,
398                                            int framenr, int width, int height)
399 {
400         MovieTrackingTrack *track;
401         MovieTrackingMarker marker;
402         MovieTrackingSettings *settings = &tracking->settings;
403
404         float half_pattern = (float)settings->default_pattern_size / 2.0f;
405         float half_search = (float)settings->default_search_size / 2.0f;
406         float pat[2], search[2];
407
408         pat[0] = half_pattern / (float)width;
409         pat[1] = half_pattern / (float)height;
410
411         search[0] = half_search / (float)width;
412         search[1] = half_search / (float)height;
413
414         track = MEM_callocN(sizeof(MovieTrackingTrack), "add_marker_exec track");
415         strcpy(track->name, "Track");
416
417         /* fill track's settings from default settings */
418         track->motion_model = settings->default_motion_model;
419         track->minimum_correlation = settings->default_minimum_correlation;
420         track->margin = settings->default_margin;
421         track->pattern_match = settings->default_pattern_match;
422         track->frames_limit = settings->default_frames_limit;
423         track->flag = settings->default_flag;
424         track->algorithm_flag = settings->default_algorithm_flag;
425         track->weight = settings->default_weight;
426
427         memset(&marker, 0, sizeof(marker));
428         marker.pos[0] = x;
429         marker.pos[1] = y;
430         marker.framenr = framenr;
431
432         marker.pattern_corners[0][0] = -pat[0];
433         marker.pattern_corners[0][1] = -pat[1];
434
435         marker.pattern_corners[1][0] = pat[0];
436         marker.pattern_corners[1][1] = -pat[1];
437
438         negate_v2_v2(marker.pattern_corners[2], marker.pattern_corners[0]);
439         negate_v2_v2(marker.pattern_corners[3], marker.pattern_corners[1]);
440
441         copy_v2_v2(marker.search_max, search);
442         negate_v2_v2(marker.search_min, search);
443
444         BKE_tracking_marker_insert(track, &marker);
445
446         BLI_addtail(tracksbase, track);
447         BKE_tracking_track_unique_name(tracksbase, track);
448
449         return track;
450 }
451
452 /* Duplicate the specified track, result will no belong to any list. */
453 MovieTrackingTrack *BKE_tracking_track_duplicate(MovieTrackingTrack *track)
454 {
455         MovieTrackingTrack *new_track;
456
457         new_track = MEM_callocN(sizeof(MovieTrackingTrack), "tracking_track_duplicate new_track");
458
459         *new_track = *track;
460         new_track->next = new_track->prev = NULL;
461
462         new_track->markers = MEM_dupallocN(new_track->markers);
463
464         return new_track;
465 }
466
467 /* Ensure specified track has got unique name,
468  * if it's not name of specified track will be changed
469  * keeping names of all other tracks unchanged.
470  */
471 void BKE_tracking_track_unique_name(ListBase *tracksbase, MovieTrackingTrack *track)
472 {
473         BLI_uniquename(tracksbase, track, CTX_DATA_(BLT_I18NCONTEXT_ID_MOVIECLIP, "Track"), '.',
474                        offsetof(MovieTrackingTrack, name), sizeof(track->name));
475 }
476
477 /* Free specified track, only frees contents of a structure
478  * (if track is allocated in heap, it shall be handled outside).
479  *
480  * All the pointers inside track becomes invalid after this call.
481  */
482 void BKE_tracking_track_free(MovieTrackingTrack *track)
483 {
484         if (track->markers)
485                 MEM_freeN(track->markers);
486 }
487
488 /* Set flag for all specified track's areas.
489  *
490  * area - which part of marker should be selected. see TRACK_AREA_* constants.
491  * flag - flag to be set for areas.
492  */
493 void BKE_tracking_track_flag_set(MovieTrackingTrack *track, int area, int flag)
494 {
495         if (area == TRACK_AREA_NONE)
496                 return;
497
498         if (area & TRACK_AREA_POINT)
499                 track->flag |= flag;
500         if (area & TRACK_AREA_PAT)
501                 track->pat_flag |= flag;
502         if (area & TRACK_AREA_SEARCH)
503                 track->search_flag |= flag;
504 }
505
506 /* Clear flag from all specified track's areas.
507  *
508  * area - which part of marker should be selected. see TRACK_AREA_* constants.
509  * flag - flag to be cleared for areas.
510  */
511 void BKE_tracking_track_flag_clear(MovieTrackingTrack *track, int area, int flag)
512 {
513         if (area == TRACK_AREA_NONE)
514                 return;
515
516         if (area & TRACK_AREA_POINT)
517                 track->flag &= ~flag;
518         if (area & TRACK_AREA_PAT)
519                 track->pat_flag &= ~flag;
520         if (area & TRACK_AREA_SEARCH)
521                 track->search_flag &= ~flag;
522 }
523
524 /* Check whether track has got marker at specified frame.
525  *
526  * NOTE: frame number should be in clip space, not scene space.
527  */
528 bool BKE_tracking_track_has_marker_at_frame(MovieTrackingTrack *track, int framenr)
529 {
530         return BKE_tracking_marker_get_exact(track, framenr) != NULL;
531 }
532
533 /* Check whether track has got enabled marker at specified frame.
534  *
535  * NOTE: frame number should be in clip space, not scene space.
536  */
537 bool BKE_tracking_track_has_enabled_marker_at_frame(MovieTrackingTrack *track, int framenr)
538 {
539         MovieTrackingMarker *marker = BKE_tracking_marker_get_exact(track, framenr);
540
541         return marker && (marker->flag & MARKER_DISABLED) == 0;
542 }
543
544 /* Clear track's path:
545  *
546  * - If action is TRACK_CLEAR_REMAINED path from ref_frame+1 up to
547  *   end will be clear.
548  *
549  * - If action is TRACK_CLEAR_UPTO path from the beginning up to
550  *   ref_frame-1 will be clear.
551  *
552  * - If action is TRACK_CLEAR_ALL only marker at frame ref_frame will remain.
553  *
554  * NOTE: frame number should be in clip space, not scene space
555  */
556 void BKE_tracking_track_path_clear(MovieTrackingTrack *track, int ref_frame, int action)
557 {
558         int a;
559
560         if (action == TRACK_CLEAR_REMAINED) {
561                 a = 1;
562
563                 while (a < track->markersnr) {
564                         if (track->markers[a].framenr > ref_frame) {
565                                 track->markersnr = a;
566                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
567
568                                 break;
569                         }
570
571                         a++;
572                 }
573
574                 if (track->markersnr)
575                         tracking_marker_insert_disabled(track, &track->markers[track->markersnr - 1], false, true);
576         }
577         else if (action == TRACK_CLEAR_UPTO) {
578                 a = track->markersnr - 1;
579
580                 while (a >= 0) {
581                         if (track->markers[a].framenr <= ref_frame) {
582                                 memmove(track->markers, track->markers + a, (track->markersnr - a) * sizeof(MovieTrackingMarker));
583
584                                 track->markersnr = track->markersnr - a;
585                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
586
587                                 break;
588                         }
589
590                         a--;
591                 }
592
593                 if (track->markersnr)
594                         tracking_marker_insert_disabled(track, &track->markers[0], true, true);
595         }
596         else if (action == TRACK_CLEAR_ALL) {
597                 MovieTrackingMarker *marker, marker_new;
598
599                 marker = BKE_tracking_marker_get(track, ref_frame);
600                 marker_new = *marker;
601
602                 MEM_freeN(track->markers);
603                 track->markers = NULL;
604                 track->markersnr = 0;
605
606                 BKE_tracking_marker_insert(track, &marker_new);
607
608                 tracking_marker_insert_disabled(track, &marker_new, true, true);
609                 tracking_marker_insert_disabled(track, &marker_new, false, true);
610         }
611 }
612
613 void BKE_tracking_tracks_join(MovieTracking *tracking, MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
614 {
615         int i = 0, a = 0, b = 0, tot;
616         MovieTrackingMarker *markers;
617
618         tot = dst_track->markersnr + src_track->markersnr;
619         markers = MEM_callocN(tot * sizeof(MovieTrackingMarker), "tmp tracking joined tracks");
620
621         while (a < src_track->markersnr || b < dst_track->markersnr) {
622                 if (b >= dst_track->markersnr) {
623                         markers[i] = src_track->markers[a++];
624                 }
625                 else if (a >= src_track->markersnr) {
626                         markers[i] = dst_track->markers[b++];
627                 }
628                 else if (src_track->markers[a].framenr < dst_track->markers[b].framenr) {
629                         markers[i] = src_track->markers[a++];
630                 }
631                 else if (src_track->markers[a].framenr > dst_track->markers[b].framenr) {
632                         markers[i] = dst_track->markers[b++];
633                 }
634                 else {
635                         if ((src_track->markers[a].flag & MARKER_DISABLED) == 0) {
636                                 if ((dst_track->markers[b].flag & MARKER_DISABLED) == 0) {
637                                         /* both tracks are enabled on this frame, so find the whole segment
638                                          * on which tracks are intersecting and blend tracks using linear
639                                          * interpolation to prevent jumps
640                                          */
641
642                                         MovieTrackingMarker *marker_a, *marker_b;
643                                         int start_a = a, start_b = b, len = 0, frame = src_track->markers[a].framenr;
644                                         int j, inverse = 0;
645
646                                         inverse = (b == 0) ||
647                                                   (dst_track->markers[b - 1].flag & MARKER_DISABLED) ||
648                                                   (dst_track->markers[b - 1].framenr != frame - 1);
649
650                                         /* find length of intersection */
651                                         while (a < src_track->markersnr && b < dst_track->markersnr) {
652                                                 marker_a = &src_track->markers[a];
653                                                 marker_b = &dst_track->markers[b];
654
655                                                 if (marker_a->flag & MARKER_DISABLED || marker_b->flag & MARKER_DISABLED)
656                                                         break;
657
658                                                 if (marker_a->framenr != frame || marker_b->framenr != frame)
659                                                         break;
660
661                                                 frame++;
662                                                 len++;
663                                                 a++;
664                                                 b++;
665                                         }
666
667                                         a = start_a;
668                                         b = start_b;
669
670                                         /* linear interpolation for intersecting frames */
671                                         for (j = 0; j < len; j++) {
672                                                 float fac = 0.5f;
673
674                                                 if (len > 1)
675                                                         fac = 1.0f / (len - 1) * j;
676
677                                                 if (inverse)
678                                                         fac = 1.0f - fac;
679
680                                                 marker_a = &src_track->markers[a];
681                                                 marker_b = &dst_track->markers[b];
682
683                                                 markers[i] = dst_track->markers[b];
684                                                 interp_v2_v2v2(markers[i].pos, marker_b->pos, marker_a->pos, fac);
685                                                 a++;
686                                                 b++;
687                                                 i++;
688                                         }
689
690                                         /* this values will be incremented at the end of the loop cycle */
691                                         a--; b--; i--;
692                                 }
693                                 else {
694                                         markers[i] = src_track->markers[a];
695                                 }
696                         }
697                         else {
698                                 markers[i] = dst_track->markers[b];
699                         }
700
701                         a++;
702                         b++;
703                 }
704
705                 i++;
706         }
707
708         MEM_freeN(dst_track->markers);
709
710         dst_track->markers = MEM_callocN(i * sizeof(MovieTrackingMarker), "tracking joined tracks");
711         memcpy(dst_track->markers, markers, i * sizeof(MovieTrackingMarker));
712
713         dst_track->markersnr = i;
714
715         MEM_freeN(markers);
716
717         BKE_tracking_dopesheet_tag_update(tracking);
718 }
719
720 MovieTrackingTrack *BKE_tracking_track_get_named(MovieTracking *tracking, MovieTrackingObject *object, const char *name)
721 {
722         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
723         MovieTrackingTrack *track = tracksbase->first;
724
725         while (track) {
726                 if (STREQ(track->name, name))
727                         return track;
728
729                 track = track->next;
730         }
731
732         return NULL;
733 }
734
735 MovieTrackingTrack *BKE_tracking_track_get_indexed(MovieTracking *tracking, int tracknr, ListBase **r_tracksbase)
736 {
737         MovieTrackingObject *object;
738         int cur = 1;
739
740         object = tracking->objects.first;
741         while (object) {
742                 ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
743                 MovieTrackingTrack *track = tracksbase->first;
744
745                 while (track) {
746                         if (track->flag & TRACK_HAS_BUNDLE) {
747                                 if (cur == tracknr) {
748                                         *r_tracksbase = tracksbase;
749                                         return track;
750                                 }
751
752                                 cur++;
753                         }
754
755                         track = track->next;
756                 }
757
758                 object = object->next;
759         }
760
761         *r_tracksbase = NULL;
762
763         return NULL;
764 }
765
766 MovieTrackingTrack *BKE_tracking_track_get_active(MovieTracking *tracking)
767 {
768         ListBase *tracksbase;
769
770         if (!tracking->act_track)
771                 return NULL;
772
773         tracksbase = BKE_tracking_get_active_tracks(tracking);
774
775         /* check that active track is in current tracks list */
776         if (BLI_findindex(tracksbase, tracking->act_track) != -1)
777                 return tracking->act_track;
778
779         return NULL;
780 }
781
782 static bGPDlayer *track_mask_gpencil_layer_get(MovieTrackingTrack *track)
783 {
784         bGPDlayer *layer;
785
786         if (!track->gpd)
787                 return NULL;
788
789         layer = track->gpd->layers.first;
790
791         while (layer) {
792                 if (layer->flag & GP_LAYER_ACTIVE) {
793                         bGPDframe *frame = layer->frames.first;
794                         bool ok = false;
795
796                         while (frame) {
797                                 if (frame->strokes.first) {
798                                         ok = true;
799                                         break;
800                                 }
801
802                                 frame = frame->next;
803                         }
804
805                         if (ok)
806                                 return layer;
807                 }
808
809                 layer = layer->next;
810         }
811
812         return NULL;
813 }
814
815 typedef struct TrackMaskSetPixelData {
816         float *mask;
817         int mask_width;
818         int mask_height;
819 } TrackMaskSetPixelData;
820
821 static void track_mask_set_pixel_cb(int x, int x_end, int y, void *user_data)
822 {
823         TrackMaskSetPixelData *data = (TrackMaskSetPixelData *)user_data;
824         size_t index =     (size_t)y * data->mask_width + x;
825         size_t index_end = (size_t)y * data->mask_width + x_end;
826         do {
827                 data->mask[index] = 1.0f;
828         } while (++index != index_end);
829 }
830
831 static void track_mask_gpencil_layer_rasterize(int frame_width, int frame_height,
832                                                MovieTrackingMarker *marker, bGPDlayer *layer,
833                                                float *mask, int mask_width, int mask_height)
834 {
835         bGPDframe *frame = layer->frames.first;
836         TrackMaskSetPixelData data;
837
838         data.mask = mask;
839         data.mask_width = mask_width;
840         data.mask_height = mask_height;
841
842         while (frame) {
843                 bGPDstroke *stroke = frame->strokes.first;
844
845                 while (stroke) {
846                         bGPDspoint *stroke_points = stroke->points;
847                         if (stroke->flag & GP_STROKE_2DSPACE) {
848                                 int *mask_points, *point;
849                                 point = mask_points = MEM_callocN(2 * stroke->totpoints * sizeof(int),
850                                                                "track mask rasterization points");
851                                 for (int i = 0; i < stroke->totpoints; i++, point += 2) {
852                                         point[0] = (stroke_points[i].x - marker->search_min[0]) * frame_width;
853                                         point[1] = (stroke_points[i].y - marker->search_min[1]) * frame_height;
854                                 }
855                                 /* TODO: add an option to control whether AA is enabled or not */
856                                 fill_poly_v2i_n(0, 0, mask_width, mask_height,
857                                                 (const int (*)[2])mask_points, stroke->totpoints,
858                                                 track_mask_set_pixel_cb, &data);
859                                 MEM_freeN(mask_points);
860                         }
861                         stroke = stroke->next;
862                 }
863                 frame = frame->next;
864         }
865 }
866
867 float *BKE_tracking_track_get_mask(int frame_width, int frame_height,
868                                    MovieTrackingTrack *track, MovieTrackingMarker *marker)
869 {
870         float *mask = NULL;
871         bGPDlayer *layer = track_mask_gpencil_layer_get(track);
872         int mask_width, mask_height;
873
874         mask_width = (marker->search_max[0] - marker->search_min[0]) * frame_width;
875         mask_height = (marker->search_max[1] - marker->search_min[1]) * frame_height;
876
877         if (layer) {
878                 mask = MEM_callocN(mask_width * mask_height * sizeof(float), "track mask");
879
880                 track_mask_gpencil_layer_rasterize(frame_width, frame_height, marker, layer,
881                                                    mask, mask_width, mask_height);
882         }
883
884         return mask;
885 }
886
887 float BKE_tracking_track_get_weight_for_marker(MovieClip *clip, MovieTrackingTrack *track, MovieTrackingMarker *marker)
888 {
889         FCurve *weight_fcurve;
890         float weight = track->weight;
891
892         weight_fcurve = id_data_find_fcurve(&clip->id, track, &RNA_MovieTrackingTrack,
893                                             "weight", 0, NULL);
894
895         if (weight_fcurve) {
896                 int scene_framenr =
897                         BKE_movieclip_remap_clip_to_scene_frame(clip, marker->framenr);
898                 weight = evaluate_fcurve(weight_fcurve, scene_framenr);
899         }
900
901         return weight;
902 }
903
904 /* area - which part of marker should be selected. see TRACK_AREA_* constants */
905 void BKE_tracking_track_select(ListBase *tracksbase, MovieTrackingTrack *track, int area, bool extend)
906 {
907         if (extend) {
908                 BKE_tracking_track_flag_set(track, area, SELECT);
909         }
910         else {
911                 MovieTrackingTrack *cur = tracksbase->first;
912
913                 while (cur) {
914                         if ((cur->flag & TRACK_HIDDEN) == 0) {
915                                 if (cur == track) {
916                                         BKE_tracking_track_flag_clear(cur, TRACK_AREA_ALL, SELECT);
917                                         BKE_tracking_track_flag_set(cur, area, SELECT);
918                                 }
919                                 else {
920                                         BKE_tracking_track_flag_clear(cur, TRACK_AREA_ALL, SELECT);
921                                 }
922                         }
923
924                         cur = cur->next;
925                 }
926         }
927 }
928
929 void BKE_tracking_track_deselect(MovieTrackingTrack *track, int area)
930 {
931         BKE_tracking_track_flag_clear(track, area, SELECT);
932 }
933
934 void BKE_tracking_tracks_deselect_all(ListBase *tracksbase)
935 {
936         MovieTrackingTrack *track;
937
938         for (track = tracksbase->first; track; track = track->next) {
939                 if ((track->flag & TRACK_HIDDEN) == 0) {
940                         BKE_tracking_track_flag_clear(track, TRACK_AREA_ALL, SELECT);
941                 }
942         }
943 }
944
945 /*********************** Marker *************************/
946
947 MovieTrackingMarker *BKE_tracking_marker_insert(MovieTrackingTrack *track, MovieTrackingMarker *marker)
948 {
949         MovieTrackingMarker *old_marker = NULL;
950
951         if (track->markersnr)
952                 old_marker = BKE_tracking_marker_get_exact(track, marker->framenr);
953
954         if (old_marker) {
955                 /* simply replace settings for already allocated marker */
956                 *old_marker = *marker;
957
958                 return old_marker;
959         }
960         else {
961                 int a = track->markersnr;
962
963                 /* find position in array where to add new marker */
964                 while (a--) {
965                         if (track->markers[a].framenr < marker->framenr)
966                                 break;
967                 }
968
969                 track->markersnr++;
970
971                 if (track->markers)
972                         track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
973                 else
974                         track->markers = MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
975
976                 /* shift array to "free" space for new marker */
977                 memmove(track->markers + a + 2, track->markers + a + 1,
978                         (track->markersnr - a - 2) * sizeof(MovieTrackingMarker));
979
980                 /* put new marker */
981                 track->markers[a + 1] = *marker;
982
983                 track->last_marker = a + 1;
984
985                 return &track->markers[a + 1];
986         }
987 }
988
989 void BKE_tracking_marker_delete(MovieTrackingTrack *track, int framenr)
990 {
991         int a = 0;
992
993         while (a < track->markersnr) {
994                 if (track->markers[a].framenr == framenr) {
995                         if (track->markersnr > 1) {
996                                 memmove(track->markers + a, track->markers + a + 1,
997                                         (track->markersnr - a - 1) * sizeof(MovieTrackingMarker));
998                                 track->markersnr--;
999                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
1000                         }
1001                         else {
1002                                 MEM_freeN(track->markers);
1003                                 track->markers = NULL;
1004                                 track->markersnr = 0;
1005                         }
1006
1007                         break;
1008                 }
1009
1010                 a++;
1011         }
1012 }
1013
1014 void BKE_tracking_marker_clamp(MovieTrackingMarker *marker, int event)
1015 {
1016         int a;
1017         float pat_min[2], pat_max[2];
1018
1019         BKE_tracking_marker_pattern_minmax(marker, pat_min, pat_max);
1020
1021         if (event == CLAMP_PAT_DIM) {
1022                 for (a = 0; a < 2; a++) {
1023                         /* search shouldn't be resized smaller than pattern */
1024                         marker->search_min[a] = min_ff(pat_min[a], marker->search_min[a]);
1025                         marker->search_max[a] = max_ff(pat_max[a], marker->search_max[a]);
1026                 }
1027         }
1028         else if (event == CLAMP_PAT_POS) {
1029                 float dim[2];
1030
1031                 sub_v2_v2v2(dim, pat_max, pat_min);
1032
1033                 for (a = 0; a < 2; a++) {
1034                         int b;
1035                         /* pattern shouldn't be moved outside of search */
1036                         if (pat_min[a] < marker->search_min[a]) {
1037                                 for (b = 0; b < 4; b++)
1038                                         marker->pattern_corners[b][a] += marker->search_min[a] - pat_min[a];
1039                         }
1040                         if (pat_max[a] > marker->search_max[a]) {
1041                                 for (b = 0; b < 4; b++)
1042                                         marker->pattern_corners[b][a] -= pat_max[a] - marker->search_max[a];
1043                         }
1044                 }
1045         }
1046         else if (event == CLAMP_SEARCH_DIM) {
1047                 for (a = 0; a < 2; a++) {
1048                         /* search shouldn't be resized smaller than pattern */
1049                         marker->search_min[a] = min_ff(pat_min[a], marker->search_min[a]);
1050                         marker->search_max[a] = max_ff(pat_max[a], marker->search_max[a]);
1051                 }
1052         }
1053         else if (event == CLAMP_SEARCH_POS) {
1054                 float dim[2];
1055
1056                 sub_v2_v2v2(dim, marker->search_max, marker->search_min);
1057
1058                 for (a = 0; a < 2; a++) {
1059                         /* search shouldn't be moved inside pattern */
1060                         if (marker->search_min[a] > pat_min[a]) {
1061                                 marker->search_min[a] = pat_min[a];
1062                                 marker->search_max[a] = marker->search_min[a] + dim[a];
1063                         }
1064                         if (marker->search_max[a] < pat_max[a]) {
1065                                 marker->search_max[a] = pat_max[a];
1066                                 marker->search_min[a] = marker->search_max[a] - dim[a];
1067                         }
1068                 }
1069         }
1070 }
1071
1072 MovieTrackingMarker *BKE_tracking_marker_get(MovieTrackingTrack *track, int framenr)
1073 {
1074         int a = track->markersnr - 1;
1075
1076         if (!track->markersnr)
1077                 return NULL;
1078
1079         /* approximate pre-first framenr marker with first marker */
1080         if (framenr < track->markers[0].framenr)
1081                 return &track->markers[0];
1082
1083         if (track->last_marker < track->markersnr)
1084                 a = track->last_marker;
1085
1086         if (track->markers[a].framenr <= framenr) {
1087                 while (a < track->markersnr && track->markers[a].framenr <= framenr) {
1088                         if (track->markers[a].framenr == framenr) {
1089                                 track->last_marker = a;
1090
1091                                 return &track->markers[a];
1092                         }
1093                         a++;
1094                 }
1095
1096                 /* if there's no marker for exact position, use nearest marker from left side */
1097                 return &track->markers[a - 1];
1098         }
1099         else {
1100                 while (a >= 0 && track->markers[a].framenr >= framenr) {
1101                         if (track->markers[a].framenr == framenr) {
1102                                 track->last_marker = a;
1103
1104                                 return &track->markers[a];
1105                         }
1106
1107                         a--;
1108                 }
1109
1110                 /* if there's no marker for exact position, use nearest marker from left side */
1111                 return &track->markers[a];
1112         }
1113
1114         return NULL;
1115 }
1116
1117 MovieTrackingMarker *BKE_tracking_marker_get_exact(MovieTrackingTrack *track, int framenr)
1118 {
1119         MovieTrackingMarker *marker = BKE_tracking_marker_get(track, framenr);
1120
1121         if (marker->framenr != framenr)
1122                 return NULL;
1123
1124         return marker;
1125 }
1126
1127 MovieTrackingMarker *BKE_tracking_marker_ensure(MovieTrackingTrack *track, int framenr)
1128 {
1129         MovieTrackingMarker *marker = BKE_tracking_marker_get(track, framenr);
1130
1131         if (marker->framenr != framenr) {
1132                 MovieTrackingMarker marker_new;
1133
1134                 marker_new = *marker;
1135                 marker_new.framenr = framenr;
1136
1137                 BKE_tracking_marker_insert(track, &marker_new);
1138                 marker = BKE_tracking_marker_get(track, framenr);
1139         }
1140
1141         return marker;
1142 }
1143
1144 void BKE_tracking_marker_pattern_minmax(const MovieTrackingMarker *marker, float min[2], float max[2])
1145 {
1146         INIT_MINMAX2(min, max);
1147
1148         minmax_v2v2_v2(min, max, marker->pattern_corners[0]);
1149         minmax_v2v2_v2(min, max, marker->pattern_corners[1]);
1150         minmax_v2v2_v2(min, max, marker->pattern_corners[2]);
1151         minmax_v2v2_v2(min, max, marker->pattern_corners[3]);
1152 }
1153
1154 void BKE_tracking_marker_get_subframe_position(MovieTrackingTrack *track, float framenr, float pos[2])
1155 {
1156         MovieTrackingMarker *marker = BKE_tracking_marker_get(track, (int) framenr);
1157         MovieTrackingMarker *marker_last = track->markers + (track->markersnr - 1);
1158
1159         if (marker != marker_last) {
1160                 MovieTrackingMarker *marker_next = marker + 1;
1161
1162                 if (marker_next->framenr == marker->framenr + 1) {
1163                         /* currently only do subframing inside tracked ranges, do not extrapolate tracked segments
1164                          * could be changed when / if mask parent would be interpolating position in-between
1165                          * tracked segments
1166                          */
1167
1168                         float fac = (framenr - (int) framenr) / (marker_next->framenr - marker->framenr);
1169
1170                         interp_v2_v2v2(pos, marker->pos, marker_next->pos, fac);
1171                 }
1172                 else {
1173                         copy_v2_v2(pos, marker->pos);
1174                 }
1175         }
1176         else {
1177                 copy_v2_v2(pos, marker->pos);
1178         }
1179
1180         /* currently track offset is always wanted to be applied here, could be made an option later */
1181         add_v2_v2(pos, track->offset);
1182 }
1183
1184 /*********************** Plane Track *************************/
1185
1186 /* Creates new plane track out of selected point tracks */
1187 MovieTrackingPlaneTrack *BKE_tracking_plane_track_add(MovieTracking *tracking, ListBase *plane_tracks_base,
1188                                                       ListBase *tracks, int framenr)
1189 {
1190         MovieTrackingPlaneTrack *plane_track;
1191         MovieTrackingPlaneMarker plane_marker;
1192         MovieTrackingTrack *track;
1193         float tracks_min[2], tracks_max[2];
1194         int track_index, num_selected_tracks = 0;
1195
1196         (void) tracking;  /* Ignored. */
1197
1198         /* Use bounding box of selected markers as an initial size of plane. */
1199         INIT_MINMAX2(tracks_min, tracks_max);
1200         for (track = tracks->first; track; track = track->next) {
1201                 if (TRACK_SELECTED(track)) {
1202                         MovieTrackingMarker *marker = BKE_tracking_marker_get(track, framenr);
1203                         float pattern_min[2], pattern_max[2];
1204                         BKE_tracking_marker_pattern_minmax(marker, pattern_min, pattern_max);
1205                         add_v2_v2(pattern_min, marker->pos);
1206                         add_v2_v2(pattern_max, marker->pos);
1207                         minmax_v2v2_v2(tracks_min, tracks_max, pattern_min);
1208                         minmax_v2v2_v2(tracks_min, tracks_max, pattern_max);
1209                         num_selected_tracks++;
1210                 }
1211         }
1212
1213         if (num_selected_tracks < 4) {
1214                 return NULL;
1215         }
1216
1217         /* Allocate new plane track. */
1218         plane_track = MEM_callocN(sizeof(MovieTrackingPlaneTrack), "new plane track");
1219
1220         /* Use some default name. */
1221         strcpy(plane_track->name, "Plane Track");
1222
1223         plane_track->image_opacity = 1.0f;
1224
1225         /* Use selected tracks from given list as a plane. */
1226         plane_track->point_tracks =
1227                 MEM_mallocN(sizeof(MovieTrackingTrack *) * num_selected_tracks, "new plane tracks array");
1228         for (track = tracks->first, track_index = 0; track; track = track->next) {
1229                 if (TRACK_SELECTED(track)) {
1230                         plane_track->point_tracks[track_index] = track;
1231                         track_index++;
1232                 }
1233         }
1234         plane_track->point_tracksnr = num_selected_tracks;
1235
1236         /* Setup new plane marker and add it to the track. */
1237         plane_marker.framenr = framenr;
1238         plane_marker.flag = 0;
1239
1240         copy_v2_v2(plane_marker.corners[0], tracks_min);
1241         copy_v2_v2(plane_marker.corners[2], tracks_max);
1242
1243         plane_marker.corners[1][0] = tracks_max[0];
1244         plane_marker.corners[1][1] = tracks_min[1];
1245         plane_marker.corners[3][0] = tracks_min[0];
1246         plane_marker.corners[3][1] = tracks_max[1];
1247
1248         BKE_tracking_plane_marker_insert(plane_track, &plane_marker);
1249
1250         /* Put new plane track to the list, ensure it's name is unique. */
1251         BLI_addtail(plane_tracks_base, plane_track);
1252         BKE_tracking_plane_track_unique_name(plane_tracks_base, plane_track);
1253
1254         return plane_track;
1255 }
1256
1257 void BKE_tracking_plane_track_unique_name(ListBase *plane_tracks_base, MovieTrackingPlaneTrack *plane_track)
1258 {
1259         BLI_uniquename(plane_tracks_base, plane_track, CTX_DATA_(BLT_I18NCONTEXT_ID_MOVIECLIP, "Plane Track"), '.',
1260                        offsetof(MovieTrackingPlaneTrack, name), sizeof(plane_track->name));
1261 }
1262
1263 /* Free specified plane track, only frees contents of a structure
1264  * (if track is allocated in heap, it shall be handled outside).
1265  *
1266  * All the pointers inside track becomes invalid after this call.
1267  */
1268 void BKE_tracking_plane_track_free(MovieTrackingPlaneTrack *plane_track)
1269 {
1270         if (plane_track->markers) {
1271                 MEM_freeN(plane_track->markers);
1272         }
1273
1274         MEM_freeN(plane_track->point_tracks);
1275 }
1276
1277 MovieTrackingPlaneTrack *BKE_tracking_plane_track_get_named(MovieTracking *tracking,
1278                                                             MovieTrackingObject *object,
1279                                                             const char *name)
1280 {
1281         ListBase *plane_tracks_base = BKE_tracking_object_get_plane_tracks(tracking, object);
1282         MovieTrackingPlaneTrack *plane_track;
1283
1284         for (plane_track = plane_tracks_base->first;
1285              plane_track;
1286              plane_track = plane_track->next)
1287         {
1288                 if (STREQ(plane_track->name, name)) {
1289                         return plane_track;
1290                 }
1291         }
1292
1293         return NULL;
1294 }
1295
1296 MovieTrackingPlaneTrack *BKE_tracking_plane_track_get_active(struct MovieTracking *tracking)
1297 {
1298         ListBase *plane_tracks_base;
1299
1300         if (tracking->act_plane_track == NULL) {
1301                 return NULL;
1302         }
1303
1304         plane_tracks_base = BKE_tracking_get_active_plane_tracks(tracking);
1305
1306         /* Check that active track is in current plane tracks list */
1307         if (BLI_findindex(plane_tracks_base, tracking->act_plane_track) != -1) {
1308                 return tracking->act_plane_track;
1309         }
1310
1311         return NULL;
1312 }
1313
1314 void BKE_tracking_plane_tracks_deselect_all(ListBase *plane_tracks_base)
1315 {
1316         MovieTrackingPlaneTrack *plane_track;
1317
1318         for (plane_track = plane_tracks_base->first; plane_track; plane_track = plane_track->next) {
1319                 plane_track->flag &= ~SELECT;
1320         }
1321 }
1322
1323 bool BKE_tracking_plane_track_has_point_track(MovieTrackingPlaneTrack *plane_track,
1324                                               MovieTrackingTrack *track)
1325 {
1326         int i;
1327         for (i = 0; i < plane_track->point_tracksnr; i++) {
1328                 if (plane_track->point_tracks[i] == track) {
1329                         return true;
1330                 }
1331         }
1332         return false;
1333 }
1334
1335 bool BKE_tracking_plane_track_remove_point_track(MovieTrackingPlaneTrack *plane_track,
1336                                                  MovieTrackingTrack *track)
1337 {
1338         int i, track_index;
1339         MovieTrackingTrack **new_point_tracks;
1340
1341         if (plane_track->point_tracksnr <= 4) {
1342                 return false;
1343         }
1344
1345         new_point_tracks = MEM_mallocN(sizeof(*new_point_tracks) * (plane_track->point_tracksnr - 1),
1346                                        "new point tracks array");
1347
1348         for (i = 0, track_index = 0; i < plane_track->point_tracksnr; i++) {
1349                 if (plane_track->point_tracks[i] != track) {
1350                         new_point_tracks[track_index++] = plane_track->point_tracks[i];
1351                 }
1352         }
1353
1354         MEM_freeN(plane_track->point_tracks);
1355         plane_track->point_tracks = new_point_tracks;
1356         plane_track->point_tracksnr--;
1357
1358         return true;
1359 }
1360
1361 void BKE_tracking_plane_tracks_remove_point_track(MovieTracking *tracking,
1362                                                   MovieTrackingTrack *track)
1363 {
1364         MovieTrackingPlaneTrack *plane_track, *next_plane_track;
1365         ListBase *plane_tracks_base = BKE_tracking_get_active_plane_tracks(tracking);
1366         for (plane_track = plane_tracks_base->first;
1367              plane_track;
1368              plane_track = next_plane_track)
1369         {
1370                 next_plane_track = plane_track->next;
1371                 if (BKE_tracking_plane_track_has_point_track(plane_track, track)) {
1372                         if (!BKE_tracking_plane_track_remove_point_track(plane_track, track)) {
1373                                 /* Delete planes with less than 3 point tracks in it. */
1374                                 BKE_tracking_plane_track_free(plane_track);
1375                                 BLI_freelinkN(plane_tracks_base, plane_track);
1376                         }
1377                 }
1378         }
1379 }
1380
1381 void BKE_tracking_plane_track_replace_point_track(MovieTrackingPlaneTrack *plane_track,
1382                                                   MovieTrackingTrack *old_track,
1383                                                   MovieTrackingTrack *new_track)
1384 {
1385         int i;
1386         for (i = 0; i < plane_track->point_tracksnr; i++) {
1387                 if (plane_track->point_tracks[i] == old_track) {
1388                         plane_track->point_tracks[i] = new_track;
1389                         break;
1390                 }
1391         }
1392 }
1393
1394 void BKE_tracking_plane_tracks_replace_point_track(MovieTracking *tracking,
1395                                                    MovieTrackingTrack *old_track,
1396                                                    MovieTrackingTrack *new_track)
1397 {
1398         MovieTrackingPlaneTrack *plane_track;
1399         ListBase *plane_tracks_base = BKE_tracking_get_active_plane_tracks(tracking);
1400         for (plane_track = plane_tracks_base->first;
1401              plane_track;
1402              plane_track = plane_track->next)
1403         {
1404                 if (BKE_tracking_plane_track_has_point_track(plane_track, old_track)) {
1405                         BKE_tracking_plane_track_replace_point_track(plane_track,
1406                                                                      old_track,
1407                                                                      new_track);
1408                 }
1409         }
1410 }
1411
1412 /*********************** Plane Marker *************************/
1413
1414 MovieTrackingPlaneMarker *BKE_tracking_plane_marker_insert(MovieTrackingPlaneTrack *plane_track,
1415                                                            MovieTrackingPlaneMarker *plane_marker)
1416 {
1417         MovieTrackingPlaneMarker *old_plane_marker = NULL;
1418
1419         if (plane_track->markersnr)
1420                 old_plane_marker = BKE_tracking_plane_marker_get_exact(plane_track, plane_marker->framenr);
1421
1422         if (old_plane_marker) {
1423                 /* Simply replace settings in existing marker. */
1424                 *old_plane_marker = *plane_marker;
1425
1426                 return old_plane_marker;
1427         }
1428         else {
1429                 int a = plane_track->markersnr;
1430
1431                 /* Find position in array where to add new marker. */
1432                 /* TODO(sergey): we coud use bisect to speed things up. */
1433                 while (a--) {
1434                         if (plane_track->markers[a].framenr < plane_marker->framenr) {
1435                                 break;
1436                         }
1437                 }
1438
1439                 plane_track->markersnr++;
1440                 plane_track->markers = MEM_reallocN(plane_track->markers,
1441                                                     sizeof(MovieTrackingPlaneMarker) * plane_track->markersnr);
1442
1443                 /* Shift array to "free" space for new marker. */
1444                 memmove(plane_track->markers + a + 2, plane_track->markers + a + 1,
1445                         (plane_track->markersnr - a - 2) * sizeof(MovieTrackingPlaneMarker));
1446
1447                 /* Put new marker to an array. */
1448                 plane_track->markers[a + 1] = *plane_marker;
1449                 plane_track->last_marker = a + 1;
1450
1451                 return &plane_track->markers[a + 1];
1452         }
1453 }
1454
1455 void BKE_tracking_plane_marker_delete(MovieTrackingPlaneTrack *plane_track, int framenr)
1456 {
1457         int a = 0;
1458
1459         while (a < plane_track->markersnr) {
1460                 if (plane_track->markers[a].framenr == framenr) {
1461                         if (plane_track->markersnr > 1) {
1462                                 memmove(plane_track->markers + a, plane_track->markers + a + 1,
1463                                         (plane_track->markersnr - a - 1) * sizeof(MovieTrackingPlaneMarker));
1464                                 plane_track->markersnr--;
1465                                 plane_track->markers = MEM_reallocN(plane_track->markers,
1466                                                                     sizeof(MovieTrackingMarker) * plane_track->markersnr);
1467                         }
1468                         else {
1469                                 MEM_freeN(plane_track->markers);
1470                                 plane_track->markers = NULL;
1471                                 plane_track->markersnr = 0;
1472                         }
1473
1474                         break;
1475                 }
1476
1477                 a++;
1478         }
1479 }
1480
1481 /* TODO(sergey): The next couple of functions are really quite the same as point marker version,
1482  *               would be nice to de-duplicate them somehow..
1483  */
1484
1485 /* Get a plane marker at given frame,
1486  * If there's no such marker, closest one from the left side will be returned.
1487  */
1488 MovieTrackingPlaneMarker *BKE_tracking_plane_marker_get(MovieTrackingPlaneTrack *plane_track, int framenr)
1489 {
1490         int a = plane_track->markersnr - 1;
1491
1492         if (!plane_track->markersnr)
1493                 return NULL;
1494
1495         /* Approximate pre-first framenr marker with first marker. */
1496         if (framenr < plane_track->markers[0].framenr) {
1497                 return &plane_track->markers[0];
1498         }
1499
1500         if (plane_track->last_marker < plane_track->markersnr) {
1501                 a = plane_track->last_marker;
1502         }
1503
1504         if (plane_track->markers[a].framenr <= framenr) {
1505                 while (a < plane_track->markersnr && plane_track->markers[a].framenr <= framenr) {
1506                         if (plane_track->markers[a].framenr == framenr) {
1507                                 plane_track->last_marker = a;
1508
1509                                 return &plane_track->markers[a];
1510                         }
1511                         a++;
1512                 }
1513
1514                 /* If there's no marker for exact position, use nearest marker from left side. */
1515                 return &plane_track->markers[a - 1];
1516         }
1517         else {
1518                 while (a >= 0 && plane_track->markers[a].framenr >= framenr) {
1519                         if (plane_track->markers[a].framenr == framenr) {
1520                                 plane_track->last_marker = a;
1521
1522                                 return &plane_track->markers[a];
1523                         }
1524
1525                         a--;
1526                 }
1527
1528                 /* If there's no marker for exact position, use nearest marker from left side. */
1529                 return &plane_track->markers[a];
1530         }
1531
1532         return NULL;
1533 }
1534
1535 /* Get a plane marker at exact given frame, if there's no marker at the frame,
1536  * NULL will be returned.
1537  */
1538 MovieTrackingPlaneMarker *BKE_tracking_plane_marker_get_exact(MovieTrackingPlaneTrack *plane_track, int framenr)
1539 {
1540         MovieTrackingPlaneMarker *plane_marker = BKE_tracking_plane_marker_get(plane_track, framenr);
1541
1542         if (plane_marker->framenr != framenr) {
1543                 return NULL;
1544         }
1545
1546         return plane_marker;
1547 }
1548
1549 /* Ensure there's a marker for the given frame. */
1550 MovieTrackingPlaneMarker *BKE_tracking_plane_marker_ensure(MovieTrackingPlaneTrack *plane_track, int framenr)
1551 {
1552         MovieTrackingPlaneMarker *plane_marker = BKE_tracking_plane_marker_get(plane_track, framenr);
1553
1554         if (plane_marker->framenr != framenr) {
1555                 MovieTrackingPlaneMarker plane_marker_new;
1556
1557                 plane_marker_new = *plane_marker;
1558                 plane_marker_new.framenr = framenr;
1559
1560                 plane_marker = BKE_tracking_plane_marker_insert(plane_track, &plane_marker_new);
1561         }
1562
1563         return plane_marker;
1564 }
1565
1566 void BKE_tracking_plane_marker_get_subframe_corners(MovieTrackingPlaneTrack *plane_track,
1567                                                     float framenr,
1568                                                     float corners[4][2])
1569 {
1570         MovieTrackingPlaneMarker *marker = BKE_tracking_plane_marker_get(plane_track, (int)framenr);
1571         MovieTrackingPlaneMarker *marker_last = plane_track->markers + (plane_track->markersnr - 1);
1572         int i;
1573         if (marker != marker_last) {
1574                 MovieTrackingPlaneMarker *marker_next = marker + 1;
1575                 if (marker_next->framenr == marker->framenr + 1) {
1576                         float fac = (framenr - (int) framenr) / (marker_next->framenr - marker->framenr);
1577                         for (i = 0; i < 4; ++i) {
1578                                 interp_v2_v2v2(corners[i], marker->corners[i],
1579                                                marker_next->corners[i], fac);
1580                         }
1581                 }
1582                 else {
1583                         for (i = 0; i < 4; ++i) {
1584                                 copy_v2_v2(corners[i], marker->corners[i]);
1585                         }
1586                 }
1587         }
1588         else {
1589                 for (i = 0; i < 4; ++i) {
1590                         copy_v2_v2(corners[i], marker->corners[i]);
1591                 }
1592         }
1593 }
1594
1595 /*********************** Object *************************/
1596
1597 MovieTrackingObject *BKE_tracking_object_add(MovieTracking *tracking, const char *name)
1598 {
1599         MovieTrackingObject *object = MEM_callocN(sizeof(MovieTrackingObject), "tracking object");
1600
1601         if (tracking->tot_object == 0) {
1602                 /* first object is always camera */
1603                 BLI_strncpy(object->name, "Camera", sizeof(object->name));
1604
1605                 object->flag |= TRACKING_OBJECT_CAMERA;
1606         }
1607         else {
1608                 BLI_strncpy(object->name, name, sizeof(object->name));
1609         }
1610
1611         BLI_addtail(&tracking->objects, object);
1612
1613         tracking->tot_object++;
1614         tracking->objectnr = BLI_listbase_count(&tracking->objects) - 1;
1615
1616         object->scale = 1.0f;
1617         object->keyframe1 = 1;
1618         object->keyframe2 = 30;
1619
1620         BKE_tracking_object_unique_name(tracking, object);
1621         BKE_tracking_dopesheet_tag_update(tracking);
1622
1623         return object;
1624 }
1625
1626 bool BKE_tracking_object_delete(MovieTracking *tracking, MovieTrackingObject *object)
1627 {
1628         MovieTrackingTrack *track;
1629         int index = BLI_findindex(&tracking->objects, object);
1630
1631         if (index == -1)
1632                 return false;
1633
1634         if (object->flag & TRACKING_OBJECT_CAMERA) {
1635                 /* object used for camera solving can't be deleted */
1636                 return false;
1637         }
1638
1639         track = object->tracks.first;
1640         while (track) {
1641                 if (track == tracking->act_track)
1642                         tracking->act_track = NULL;
1643
1644                 track = track->next;
1645         }
1646
1647         tracking_object_free(object);
1648         BLI_freelinkN(&tracking->objects, object);
1649
1650         tracking->tot_object--;
1651
1652         if (index != 0)
1653                 tracking->objectnr = index - 1;
1654         else
1655                 tracking->objectnr = 0;
1656
1657         BKE_tracking_dopesheet_tag_update(tracking);
1658
1659         return true;
1660 }
1661
1662 void BKE_tracking_object_unique_name(MovieTracking *tracking, MovieTrackingObject *object)
1663 {
1664         BLI_uniquename(&tracking->objects, object, DATA_("Object"), '.',
1665                        offsetof(MovieTrackingObject, name), sizeof(object->name));
1666 }
1667
1668 MovieTrackingObject *BKE_tracking_object_get_named(MovieTracking *tracking, const char *name)
1669 {
1670         MovieTrackingObject *object = tracking->objects.first;
1671
1672         while (object) {
1673                 if (STREQ(object->name, name))
1674                         return object;
1675
1676                 object = object->next;
1677         }
1678
1679         return NULL;
1680 }
1681
1682 MovieTrackingObject *BKE_tracking_object_get_active(MovieTracking *tracking)
1683 {
1684         return BLI_findlink(&tracking->objects, tracking->objectnr);
1685 }
1686
1687 MovieTrackingObject *BKE_tracking_object_get_camera(MovieTracking *tracking)
1688 {
1689         MovieTrackingObject *object = tracking->objects.first;
1690
1691         while (object) {
1692                 if (object->flag & TRACKING_OBJECT_CAMERA)
1693                         return object;
1694
1695                 object = object->next;
1696         }
1697
1698         return NULL;
1699 }
1700
1701 ListBase *BKE_tracking_object_get_tracks(MovieTracking *tracking, MovieTrackingObject *object)
1702 {
1703         if (object->flag & TRACKING_OBJECT_CAMERA) {
1704                 return &tracking->tracks;
1705         }
1706
1707         return &object->tracks;
1708 }
1709
1710 ListBase *BKE_tracking_object_get_plane_tracks(MovieTracking *tracking, MovieTrackingObject *object)
1711 {
1712         if (object->flag & TRACKING_OBJECT_CAMERA) {
1713                 return &tracking->plane_tracks;
1714         }
1715
1716         return &object->plane_tracks;
1717 }
1718
1719 MovieTrackingReconstruction *BKE_tracking_object_get_reconstruction(MovieTracking *tracking,
1720                                                                     MovieTrackingObject *object)
1721 {
1722         if (object->flag & TRACKING_OBJECT_CAMERA) {
1723                 return &tracking->reconstruction;
1724         }
1725
1726         return &object->reconstruction;
1727 }
1728
1729 /*********************** Camera *************************/
1730
1731 static int reconstructed_camera_index_get(MovieTrackingReconstruction *reconstruction, int framenr, bool nearest)
1732 {
1733         MovieReconstructedCamera *cameras = reconstruction->cameras;
1734         int a = 0, d = 1;
1735
1736         if (!reconstruction->camnr)
1737                 return -1;
1738
1739         if (framenr < cameras[0].framenr) {
1740                 if (nearest)
1741                         return 0;
1742                 else
1743                         return -1;
1744         }
1745
1746         if (framenr > cameras[reconstruction->camnr - 1].framenr) {
1747                 if (nearest)
1748                         return reconstruction->camnr - 1;
1749                 else
1750                         return -1;
1751         }
1752
1753         if (reconstruction->last_camera < reconstruction->camnr)
1754                 a = reconstruction->last_camera;
1755
1756         if (cameras[a].framenr >= framenr)
1757                 d = -1;
1758
1759         while (a >= 0 && a < reconstruction->camnr) {
1760                 int cfra = cameras[a].framenr;
1761
1762                 /* check if needed framenr was "skipped" -- no data for requested frame */
1763
1764                 if (d > 0 && cfra > framenr) {
1765                         /* interpolate with previous position */
1766                         if (nearest)
1767                                 return a - 1;
1768                         else
1769                                 break;
1770                 }
1771
1772                 if (d < 0 && cfra < framenr) {
1773                         /* interpolate with next position */
1774                         if (nearest)
1775                                 return a;
1776                         else
1777                                 break;
1778                 }
1779
1780                 if (cfra == framenr) {
1781                         reconstruction->last_camera = a;
1782
1783                         return a;
1784                 }
1785
1786                 a += d;
1787         }
1788
1789         return -1;
1790 }
1791
1792 static void reconstructed_camera_scale_set(MovieTrackingObject *object, float mat[4][4])
1793 {
1794         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0) {
1795                 float smat[4][4];
1796
1797                 scale_m4_fl(smat, 1.0f / object->scale);
1798                 mul_m4_m4m4(mat, mat, smat);
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                                                        float 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, (int)framenr, true);
1852
1853         if (a == -1) {
1854                 unit_m4(mat);
1855                 return;
1856         }
1857
1858         if (cameras[a].framenr != framenr && a < reconstruction->camnr - 1) {
1859                 float t = ((float)framenr - cameras[a].framenr) / (cameras[a + 1].framenr - cameras[a].framenr);
1860                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a + 1].mat, t);
1861         }
1862         else {
1863                 copy_m4_m4(mat, cameras[a].mat);
1864         }
1865
1866         reconstructed_camera_scale_set(object, mat);
1867 }
1868
1869 /*********************** Distortion/Undistortion *************************/
1870
1871 MovieDistortion *BKE_tracking_distortion_new(MovieTracking *tracking,
1872                                              int calibration_width, int calibration_height)
1873 {
1874         MovieDistortion *distortion;
1875         libmv_CameraIntrinsicsOptions camera_intrinsics_options;
1876
1877         tracking_cameraIntrinscisOptionsFromTracking(tracking,
1878                                                      calibration_width,
1879                                                      calibration_height,
1880                                                      &camera_intrinsics_options);
1881
1882         distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
1883         distortion->intrinsics = libmv_cameraIntrinsicsNew(&camera_intrinsics_options);
1884
1885         const MovieTrackingCamera *camera = &tracking->camera;
1886         copy_v2_v2(distortion->principal, camera->principal);
1887         distortion->pixel_aspect = camera->pixel_aspect;
1888         distortion->focal = camera->focal;
1889
1890         return distortion;
1891 }
1892
1893 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking,
1894                                     int calibration_width, int calibration_height)
1895 {
1896         libmv_CameraIntrinsicsOptions camera_intrinsics_options;
1897
1898         tracking_cameraIntrinscisOptionsFromTracking(tracking,
1899                                                      calibration_width,
1900                                                      calibration_height,
1901                                                      &camera_intrinsics_options);
1902
1903         const MovieTrackingCamera *camera = &tracking->camera;
1904         copy_v2_v2(distortion->principal, camera->principal);
1905         distortion->pixel_aspect = camera->pixel_aspect;
1906         distortion->focal = camera->focal;
1907
1908         libmv_cameraIntrinsicsUpdate(&camera_intrinsics_options, distortion->intrinsics);
1909 }
1910
1911 void BKE_tracking_distortion_set_threads(MovieDistortion *distortion, int threads)
1912 {
1913         libmv_cameraIntrinsicsSetThreads(distortion->intrinsics, threads);
1914 }
1915
1916 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
1917 {
1918         MovieDistortion *new_distortion;
1919
1920         new_distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
1921         *new_distortion = *distortion;
1922         new_distortion->intrinsics = libmv_cameraIntrinsicsCopy(distortion->intrinsics);
1923
1924         return new_distortion;
1925 }
1926
1927 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking, ImBuf *ibuf,
1928                                     int calibration_width, int calibration_height, float overscan, bool undistort)
1929 {
1930         ImBuf *resibuf;
1931
1932         BKE_tracking_distortion_update(distortion, tracking, calibration_width, calibration_height);
1933
1934         resibuf = IMB_dupImBuf(ibuf);
1935
1936         if (ibuf->rect_float) {
1937                 if (undistort) {
1938                         libmv_cameraIntrinsicsUndistortFloat(distortion->intrinsics,
1939                                                              ibuf->rect_float,
1940                                                              ibuf->x, ibuf->y,
1941                                                              overscan,
1942                                                              ibuf->channels,
1943                                                              resibuf->rect_float);
1944                 }
1945                 else {
1946                         libmv_cameraIntrinsicsDistortFloat(distortion->intrinsics,
1947                                                            ibuf->rect_float,
1948                                                            ibuf->x, ibuf->y,
1949                                                            overscan,
1950                                                            ibuf->channels,
1951                                                            resibuf->rect_float);
1952                 }
1953
1954                 if (ibuf->rect)
1955                         imb_freerectImBuf(ibuf);
1956         }
1957         else {
1958                 if (undistort) {
1959                         libmv_cameraIntrinsicsUndistortByte(distortion->intrinsics,
1960                                                             (unsigned char *)ibuf->rect,
1961                                                             ibuf->x, ibuf->y,
1962                                                             overscan,
1963                                                             ibuf->channels,
1964                                                             (unsigned char *)resibuf->rect);
1965                 }
1966                 else {
1967                         libmv_cameraIntrinsicsDistortByte(distortion->intrinsics,
1968                                                           (unsigned char *)ibuf->rect,
1969                                                           ibuf->x, ibuf->y,
1970                                                           overscan,
1971                                                           ibuf->channels,
1972                                                           (unsigned char *)resibuf->rect);
1973                 }
1974         }
1975
1976         return resibuf;
1977 }
1978
1979 void BKE_tracking_distortion_distort_v2(MovieDistortion *distortion,
1980                                         const float co[2],
1981                                         float r_co[2])
1982 {
1983         const float aspy = 1.0f / distortion->pixel_aspect;
1984
1985         /* Normalize coords. */
1986         float inv_focal = 1.0f / distortion->focal;
1987         double x = (co[0] - distortion->principal[0]) * inv_focal,
1988                y = (co[1] - distortion->principal[1] * aspy) * inv_focal;
1989
1990         libmv_cameraIntrinsicsApply(distortion->intrinsics, x, y, &x, &y);
1991
1992         /* Result is in image coords already. */
1993         r_co[0] = x;
1994         r_co[1] = y;
1995 }
1996
1997 void BKE_tracking_distortion_undistort_v2(MovieDistortion *distortion,
1998                                           const float co[2],
1999                                           float r_co[2])
2000 {
2001         double x = co[0], y = co[1];
2002         libmv_cameraIntrinsicsInvert(distortion->intrinsics, x, y, &x, &y);
2003
2004         const float aspy = 1.0f / distortion->pixel_aspect;
2005         r_co[0] = (float)x * distortion->focal + distortion->principal[0];
2006         r_co[1] = (float)y * distortion->focal + distortion->principal[1] * aspy;
2007 }
2008
2009 void BKE_tracking_distortion_free(MovieDistortion *distortion)
2010 {
2011         libmv_cameraIntrinsicsDestroy(distortion->intrinsics);
2012
2013         MEM_freeN(distortion);
2014 }
2015
2016 void BKE_tracking_distort_v2(MovieTracking *tracking, const float co[2], float r_co[2])
2017 {
2018         const MovieTrackingCamera *camera = &tracking->camera;
2019         const float aspy = 1.0f / tracking->camera.pixel_aspect;
2020
2021         libmv_CameraIntrinsicsOptions camera_intrinsics_options;
2022         tracking_cameraIntrinscisOptionsFromTracking(tracking,
2023                                                      0, 0,
2024                                                      &camera_intrinsics_options);
2025         libmv_CameraIntrinsics *intrinsics =
2026                 libmv_cameraIntrinsicsNew(&camera_intrinsics_options);
2027
2028         /* Normalize coordinates. */
2029         double x = (co[0] - camera->principal[0]) / camera->focal,
2030                y = (co[1] - camera->principal[1] * aspy) / camera->focal;
2031
2032         libmv_cameraIntrinsicsApply(intrinsics, x, y, &x, &y);
2033         libmv_cameraIntrinsicsDestroy(intrinsics);
2034
2035         /* Result is in image coords already. */
2036         r_co[0] = x;
2037         r_co[1] = y;
2038 }
2039
2040 void BKE_tracking_undistort_v2(MovieTracking *tracking, const float co[2], float r_co[2])
2041 {
2042         const MovieTrackingCamera *camera = &tracking->camera;
2043         const float aspy = 1.0f / tracking->camera.pixel_aspect;
2044
2045         libmv_CameraIntrinsicsOptions camera_intrinsics_options;
2046         tracking_cameraIntrinscisOptionsFromTracking(tracking,
2047                                                      0, 0,
2048                                                      &camera_intrinsics_options);
2049         libmv_CameraIntrinsics *intrinsics =
2050                 libmv_cameraIntrinsicsNew(&camera_intrinsics_options);
2051
2052         double x = co[0], y = co[1];
2053         libmv_cameraIntrinsicsInvert(intrinsics, x, y, &x, &y);
2054         libmv_cameraIntrinsicsDestroy(intrinsics);
2055
2056         r_co[0] = (float)x * camera->focal + camera->principal[0];
2057         r_co[1] = (float)y * camera->focal + camera->principal[1] * aspy;
2058 }
2059
2060 ImBuf *BKE_tracking_undistort_frame(MovieTracking *tracking, ImBuf *ibuf, int calibration_width,
2061                                     int calibration_height, float overscan)
2062 {
2063         MovieTrackingCamera *camera = &tracking->camera;
2064
2065         if (camera->intrinsics == NULL) {
2066                 camera->intrinsics = BKE_tracking_distortion_new(tracking, calibration_width, calibration_height);
2067         }
2068
2069         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, calibration_width,
2070                                             calibration_height, overscan, true);
2071 }
2072
2073 ImBuf *BKE_tracking_distort_frame(MovieTracking *tracking, ImBuf *ibuf, int calibration_width,
2074                                   int calibration_height, float overscan)
2075 {
2076         MovieTrackingCamera *camera = &tracking->camera;
2077
2078         if (camera->intrinsics == NULL) {
2079                 camera->intrinsics = BKE_tracking_distortion_new(tracking, calibration_width, calibration_height);
2080         }
2081
2082         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, calibration_width,
2083                                             calibration_height, overscan, false);
2084 }
2085
2086 void BKE_tracking_max_distortion_delta_across_bound(MovieTracking *tracking, rcti *rect,
2087                                                     bool undistort, float delta[2])
2088 {
2089         int a;
2090         float pos[2], warped_pos[2];
2091         const int coord_delta = 5;
2092         void (*apply_distortion) (MovieTracking *tracking,
2093                                  const float pos[2], float out[2]);
2094
2095         if (undistort) {
2096                 apply_distortion = BKE_tracking_undistort_v2;
2097         }
2098         else {
2099                 apply_distortion = BKE_tracking_distort_v2;
2100         }
2101
2102         delta[0] = delta[1] = -FLT_MAX;
2103
2104         for (a = rect->xmin; a <= rect->xmax + coord_delta; a += coord_delta) {
2105                 if (a > rect->xmax)
2106                         a = rect->xmax;
2107
2108                 /* bottom edge */
2109                 pos[0] = a;
2110                 pos[1] = rect->ymin;
2111
2112                 apply_distortion(tracking, pos, warped_pos);
2113
2114                 delta[0] = max_ff(delta[0], fabsf(pos[0] - warped_pos[0]));
2115                 delta[1] = max_ff(delta[1], fabsf(pos[1] - warped_pos[1]));
2116
2117                 /* top edge */
2118                 pos[0] = a;
2119                 pos[1] = rect->ymax;
2120
2121                 apply_distortion(tracking, pos, warped_pos);
2122
2123                 delta[0] = max_ff(delta[0], fabsf(pos[0] - warped_pos[0]));
2124                 delta[1] = max_ff(delta[1], fabsf(pos[1] - warped_pos[1]));
2125
2126                 if (a >= rect->xmax)
2127                         break;
2128         }
2129
2130         for (a = rect->ymin; a <= rect->ymax + coord_delta; a += coord_delta) {
2131                 if (a > rect->ymax)
2132                         a = rect->ymax;
2133
2134                 /* left edge */
2135                 pos[0] = rect->xmin;
2136                 pos[1] = a;
2137
2138                 apply_distortion(tracking, pos, warped_pos);
2139
2140                 delta[0] = max_ff(delta[0], fabsf(pos[0] - warped_pos[0]));
2141                 delta[1] = max_ff(delta[1], fabsf(pos[1] - warped_pos[1]));
2142
2143                 /* right edge */
2144                 pos[0] = rect->xmax;
2145                 pos[1] = a;
2146
2147                 apply_distortion(tracking, pos, warped_pos);
2148
2149                 delta[0] = max_ff(delta[0], fabsf(pos[0] - warped_pos[0]));
2150                 delta[1] = max_ff(delta[1], fabsf(pos[1] - warped_pos[1]));
2151
2152                 if (a >= rect->ymax)
2153                         break;
2154         }
2155 }
2156
2157 /*********************** Image sampling *************************/
2158
2159 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track, bool grayscale)
2160 {
2161         BKE_tracking_disable_channels(ibuf, track->flag & TRACK_DISABLE_RED,
2162                                       track->flag & TRACK_DISABLE_GREEN,
2163                                       track->flag & TRACK_DISABLE_BLUE, grayscale);
2164 }
2165
2166 ImBuf *BKE_tracking_sample_pattern(int frame_width, int frame_height, ImBuf *search_ibuf,
2167                                    MovieTrackingTrack *track, MovieTrackingMarker *marker,
2168                                    bool from_anchor, bool use_mask, int num_samples_x, int num_samples_y,
2169                                    float pos[2])
2170 {
2171         ImBuf *pattern_ibuf;
2172         double src_pixel_x[5], src_pixel_y[5];
2173         double warped_position_x, warped_position_y;
2174         float *mask = NULL;
2175
2176         if (num_samples_x <= 0 || num_samples_y <= 0)
2177                 return NULL;
2178
2179         pattern_ibuf = IMB_allocImBuf(num_samples_x, num_samples_y,
2180                                       32,
2181                                       search_ibuf->rect_float ? IB_rectfloat : IB_rect);
2182
2183         tracking_get_marker_coords_for_tracking(frame_width, frame_height, marker, src_pixel_x, src_pixel_y);
2184
2185         /* from_anchor means search buffer was obtained for an anchored position,
2186          * which means applying track offset rounded to pixel space (we could not
2187          * store search buffer with sub-pixel precision)
2188          *
2189          * in this case we need to alter coordinates a bit, to compensate rounded
2190          * fractional part of offset
2191          */
2192         if (from_anchor) {
2193                 int a;
2194
2195                 for (a = 0; a < 5; a++) {
2196                         src_pixel_x[a] += (double) ((track->offset[0] * frame_width) - ((int) (track->offset[0] * frame_width)));
2197                         src_pixel_y[a] += (double) ((track->offset[1] * frame_height) - ((int) (track->offset[1] * frame_height)));
2198
2199                         /* when offset is negative, rounding happens in opposite direction */
2200                         if (track->offset[0] < 0.0f)
2201                                 src_pixel_x[a] += 1.0;
2202                         if (track->offset[1] < 0.0f)
2203                                 src_pixel_y[a] += 1.0;
2204                 }
2205         }
2206
2207         if (use_mask) {
2208                 mask = BKE_tracking_track_get_mask(frame_width, frame_height, track, marker);
2209         }
2210
2211         if (search_ibuf->rect_float) {
2212                 libmv_samplePlanarPatchFloat(search_ibuf->rect_float,
2213                                              search_ibuf->x, search_ibuf->y, 4,
2214                                              src_pixel_x, src_pixel_y,
2215                                              num_samples_x, num_samples_y,
2216                                              mask,
2217                                              pattern_ibuf->rect_float,
2218                                              &warped_position_x,
2219                                              &warped_position_y);
2220         }
2221         else {
2222                 libmv_samplePlanarPatchByte((unsigned char *) search_ibuf->rect,
2223                                             search_ibuf->x, search_ibuf->y, 4,
2224                                             src_pixel_x, src_pixel_y,
2225                                             num_samples_x, num_samples_y,
2226                                             mask,
2227                                             (unsigned char *) pattern_ibuf->rect,
2228                                             &warped_position_x,
2229                                             &warped_position_y);
2230         }
2231
2232         if (pos) {
2233                 pos[0] = warped_position_x;
2234                 pos[1] = warped_position_y;
2235         }
2236
2237         if (mask) {
2238                 MEM_freeN(mask);
2239         }
2240
2241         return pattern_ibuf;
2242 }
2243
2244 ImBuf *BKE_tracking_get_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
2245                                       bool anchored, bool disable_channels)
2246 {
2247         ImBuf *pattern_ibuf, *search_ibuf;
2248         float pat_min[2], pat_max[2];
2249         int num_samples_x, num_samples_y;
2250
2251         BKE_tracking_marker_pattern_minmax(marker, pat_min, pat_max);
2252
2253         num_samples_x = (pat_max[0] - pat_min[0]) * ibuf->x;
2254         num_samples_y = (pat_max[1] - pat_min[1]) * ibuf->y;
2255
2256         search_ibuf = BKE_tracking_get_search_imbuf(ibuf, track, marker, anchored, disable_channels);
2257
2258         if (search_ibuf) {
2259                 pattern_ibuf = BKE_tracking_sample_pattern(ibuf->x, ibuf->y, search_ibuf, track, marker,
2260                                                            anchored, false, num_samples_x, num_samples_y, NULL);
2261
2262                 IMB_freeImBuf(search_ibuf);
2263         }
2264         else {
2265                 pattern_ibuf = NULL;
2266         }
2267
2268         return pattern_ibuf;
2269 }
2270
2271 ImBuf *BKE_tracking_get_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
2272                                      bool anchored, bool disable_channels)
2273 {
2274         ImBuf *searchibuf;
2275         int x, y, w, h;
2276         float search_origin[2];
2277
2278         tracking_get_search_origin_frame_pixel(ibuf->x, ibuf->y, marker, search_origin);
2279
2280         x = search_origin[0];
2281         y = search_origin[1];
2282
2283         if (anchored) {
2284                 x += track->offset[0] * ibuf->x;
2285                 y += track->offset[1] * ibuf->y;
2286         }
2287
2288         w = (marker->search_max[0] - marker->search_min[0]) * ibuf->x;
2289         h = (marker->search_max[1] - marker->search_min[1]) * ibuf->y;
2290
2291         if (w <= 0 || h <= 0)
2292                 return NULL;
2293
2294         searchibuf = IMB_allocImBuf(w, h, 32, ibuf->rect_float ? IB_rectfloat : IB_rect);
2295
2296         IMB_rectcpy(searchibuf, ibuf, 0, 0, x, y, w, h);
2297
2298         if (disable_channels) {
2299                 if ((track->flag & TRACK_PREVIEW_GRAYSCALE) ||
2300                     (track->flag & TRACK_DISABLE_RED)       ||
2301                     (track->flag & TRACK_DISABLE_GREEN)     ||
2302                     (track->flag & TRACK_DISABLE_BLUE))
2303                 {
2304                         disable_imbuf_channels(searchibuf, track, true);
2305                 }
2306         }
2307
2308         return searchibuf;
2309 }
2310
2311 /* zap channels from the imbuf that are disabled by the user. this can lead to
2312  * better tracks sometimes. however, instead of simply zeroing the channels
2313  * out, do a partial grayscale conversion so the display is better.
2314  */
2315 void BKE_tracking_disable_channels(ImBuf *ibuf, bool disable_red, bool disable_green, bool disable_blue,
2316                                    bool grayscale)
2317 {
2318         int x, y;
2319         float scale;
2320
2321         if (!disable_red && !disable_green && !disable_blue && !grayscale)
2322                 return;
2323
2324         /* if only some components are selected, it's important to rescale the result
2325          * appropriately so that e.g. if only blue is selected, it's not zeroed out.
2326          */
2327         scale = (disable_red   ? 0.0f : 0.2126f) +
2328                 (disable_green ? 0.0f : 0.7152f) +
2329                 (disable_blue  ? 0.0f : 0.0722f);
2330
2331         for (y = 0; y < ibuf->y; y++) {
2332                 for (x = 0; x < ibuf->x; x++) {
2333                         int pixel = ibuf->x * y + x;
2334
2335                         if (ibuf->rect_float) {
2336                                 float *rrgbf = ibuf->rect_float + pixel * 4;
2337                                 float r = disable_red   ? 0.0f : rrgbf[0];
2338                                 float g = disable_green ? 0.0f : rrgbf[1];
2339                                 float b = disable_blue  ? 0.0f : rrgbf[2];
2340
2341                                 if (grayscale) {
2342                                         float gray = (0.2126f * r + 0.7152f * g + 0.0722f * b) / scale;
2343
2344                                         rrgbf[0] = rrgbf[1] = rrgbf[2] = gray;
2345                                 }
2346                                 else {
2347                                         rrgbf[0] = r;
2348                                         rrgbf[1] = g;
2349                                         rrgbf[2] = b;
2350                                 }
2351                         }
2352                         else {
2353                                 char *rrgb = (char *)ibuf->rect + pixel * 4;
2354                                 char r = disable_red   ? 0 : rrgb[0];
2355                                 char g = disable_green ? 0 : rrgb[1];
2356                                 char b = disable_blue  ? 0 : rrgb[2];
2357
2358                                 if (grayscale) {
2359                                         float gray = (0.2126f * r + 0.7152f * g + 0.0722f * b) / scale;
2360
2361                                         rrgb[0] = rrgb[1] = rrgb[2] = gray;
2362                                 }
2363                                 else {
2364                                         rrgb[0] = r;
2365                                         rrgb[1] = g;
2366                                         rrgb[2] = b;
2367                                 }
2368                         }
2369                 }
2370         }
2371
2372         if (ibuf->rect_float)
2373                 ibuf->userflags |= IB_RECT_INVALID;
2374 }
2375
2376 /*********************** Dopesheet functions *************************/
2377
2378 /* ** Channels sort comparators ** */
2379
2380 static int channels_alpha_sort(const void *a, const void *b)
2381 {
2382         const MovieTrackingDopesheetChannel *channel_a = a;
2383         const MovieTrackingDopesheetChannel *channel_b = b;
2384
2385         if (BLI_strcasecmp(channel_a->track->name, channel_b->track->name) > 0)
2386                 return 1;
2387         else
2388                 return 0;
2389 }
2390
2391 static int channels_total_track_sort(const void *a, const void *b)
2392 {
2393         const MovieTrackingDopesheetChannel *channel_a = a;
2394         const MovieTrackingDopesheetChannel *channel_b = b;
2395
2396         if (channel_a->total_frames > channel_b->total_frames)
2397                 return 1;
2398         else
2399                 return 0;
2400 }
2401
2402 static int channels_longest_segment_sort(const void *a, const void *b)
2403 {
2404         const MovieTrackingDopesheetChannel *channel_a = a;
2405         const MovieTrackingDopesheetChannel *channel_b = b;
2406
2407         if (channel_a->max_segment > channel_b->max_segment)
2408                 return 1;
2409         else
2410                 return 0;
2411 }
2412
2413 static int channels_average_error_sort(const void *a, const void *b)
2414 {
2415         const MovieTrackingDopesheetChannel *channel_a = a;
2416         const MovieTrackingDopesheetChannel *channel_b = b;
2417
2418         if (channel_a->track->error > channel_b->track->error)
2419                 return 1;
2420         else
2421                 return 0;
2422 }
2423
2424 static int channels_alpha_inverse_sort(const void *a, const void *b)
2425 {
2426         if (channels_alpha_sort(a, b))
2427                 return 0;
2428         else
2429                 return 1;
2430 }
2431
2432 static int channels_total_track_inverse_sort(const void *a, const void *b)
2433 {
2434         if (channels_total_track_sort(a, b))
2435                 return 0;
2436         else
2437                 return 1;
2438 }
2439
2440 static int channels_longest_segment_inverse_sort(const void *a, const void *b)
2441 {
2442         if (channels_longest_segment_sort(a, b))
2443                 return 0;
2444         else
2445                 return 1;
2446 }
2447
2448 static int channels_average_error_inverse_sort(const void *a, const void *b)
2449 {
2450         const MovieTrackingDopesheetChannel *channel_a = a;
2451         const MovieTrackingDopesheetChannel *channel_b = b;
2452
2453         if (channel_a->track->error < channel_b->track->error)
2454                 return 1;
2455         else
2456                 return 0;
2457 }
2458
2459 /* Calculate frames segments at which track is tracked continuously. */
2460 static void tracking_dopesheet_channels_segments_calc(MovieTrackingDopesheetChannel *channel)
2461 {
2462         MovieTrackingTrack *track = channel->track;
2463         int i, segment;
2464
2465         channel->tot_segment = 0;
2466         channel->max_segment = 0;
2467         channel->total_frames = 0;
2468
2469         /* TODO(sergey): looks a bit code-duplicated, need to look into
2470          *               logic de-duplication here.
2471          */
2472
2473         /* count */
2474         i = 0;
2475         while (i < track->markersnr) {
2476                 MovieTrackingMarker *marker = &track->markers[i];
2477
2478                 if ((marker->flag & MARKER_DISABLED) == 0) {
2479                         int prev_fra = marker->framenr, len = 0;
2480
2481                         i++;
2482                         while (i < track->markersnr) {
2483                                 marker = &track->markers[i];
2484
2485                                 if (marker->framenr != prev_fra + 1)
2486                                         break;
2487                                 if (marker->flag & MARKER_DISABLED)
2488                                         break;
2489
2490                                 prev_fra = marker->framenr;
2491                                 len++;
2492                                 i++;
2493                         }
2494
2495                         channel->tot_segment++;
2496                 }
2497
2498                 i++;
2499         }
2500
2501         if (!channel->tot_segment)
2502                 return;
2503
2504         channel->segments = MEM_callocN(2 * sizeof(int) * channel->tot_segment, "tracking channel segments");
2505
2506         /* create segments */
2507         i = 0;
2508         segment = 0;
2509         while (i < track->markersnr) {
2510                 MovieTrackingMarker *marker = &track->markers[i];
2511
2512                 if ((marker->flag & MARKER_DISABLED) == 0) {
2513                         MovieTrackingMarker *start_marker = marker;
2514                         int prev_fra = marker->framenr, len = 0;
2515
2516                         i++;
2517                         while (i < track->markersnr) {
2518                                 marker = &track->markers[i];
2519
2520                                 if (marker->framenr != prev_fra + 1)
2521                                         break;
2522                                 if (marker->flag & MARKER_DISABLED)
2523                                         break;
2524
2525                                 prev_fra = marker->framenr;
2526                                 channel->total_frames++;
2527                                 len++;
2528                                 i++;
2529                         }
2530
2531                         channel->segments[2 * segment] = start_marker->framenr;
2532                         channel->segments[2 * segment + 1] = start_marker->framenr + len;
2533
2534                         channel->max_segment = max_ii(channel->max_segment, len);
2535                         segment++;
2536                 }
2537
2538                 i++;
2539         }
2540 }
2541
2542 /* Create channels for tracks and calculate tracked segments for them. */
2543 static void tracking_dopesheet_channels_calc(MovieTracking *tracking)
2544 {
2545         MovieTrackingObject *object = BKE_tracking_object_get_active(tracking);
2546         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
2547         MovieTrackingTrack *track;
2548         MovieTrackingReconstruction *reconstruction =
2549                 BKE_tracking_object_get_reconstruction(tracking, object);
2550         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
2551
2552         bool sel_only = (dopesheet->flag & TRACKING_DOPE_SELECTED_ONLY) != 0;
2553         bool show_hidden = (dopesheet->flag & TRACKING_DOPE_SHOW_HIDDEN) != 0;
2554
2555         for (track = tracksbase->first; track; track = track->next) {
2556                 MovieTrackingDopesheetChannel *channel;
2557
2558                 if (!show_hidden && (track->flag & TRACK_HIDDEN) != 0)
2559                         continue;
2560
2561                 if (sel_only && !TRACK_SELECTED(track))
2562                         continue;
2563
2564                 channel = MEM_callocN(sizeof(MovieTrackingDopesheetChannel), "tracking dopesheet channel");
2565                 channel->track = track;
2566
2567                 if (reconstruction->flag & TRACKING_RECONSTRUCTED) {
2568                         BLI_snprintf(channel->name, sizeof(channel->name), "%s (%.4f)", track->name, track->error);
2569                 }
2570                 else {
2571                         BLI_strncpy(channel->name, track->name, sizeof(channel->name));
2572                 }
2573
2574                 tracking_dopesheet_channels_segments_calc(channel);
2575
2576                 BLI_addtail(&dopesheet->channels, channel);
2577                 dopesheet->tot_channel++;
2578         }
2579 }
2580
2581 /* Sot dopesheet channels using given method (name, average error, total coverage,
2582  * longest tracked segment) and could also inverse the list if it's enabled.
2583  */
2584 static void tracking_dopesheet_channels_sort(MovieTracking *tracking, int sort_method, bool inverse)
2585 {
2586         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
2587
2588         if (inverse) {
2589                 if (sort_method == TRACKING_DOPE_SORT_NAME) {
2590                         BLI_listbase_sort(&dopesheet->channels, channels_alpha_inverse_sort);
2591                 }
2592                 else if (sort_method == TRACKING_DOPE_SORT_LONGEST) {
2593                         BLI_listbase_sort(&dopesheet->channels, channels_longest_segment_inverse_sort);
2594                 }
2595                 else if (sort_method == TRACKING_DOPE_SORT_TOTAL) {
2596                         BLI_listbase_sort(&dopesheet->channels, channels_total_track_inverse_sort);
2597                 }
2598                 else if (sort_method == TRACKING_DOPE_SORT_AVERAGE_ERROR) {
2599                         BLI_listbase_sort(&dopesheet->channels, channels_average_error_inverse_sort);
2600                 }
2601         }
2602         else {
2603                 if (sort_method == TRACKING_DOPE_SORT_NAME) {
2604                         BLI_listbase_sort(&dopesheet->channels, channels_alpha_sort);
2605                 }
2606                 else if (sort_method == TRACKING_DOPE_SORT_LONGEST) {
2607                         BLI_listbase_sort(&dopesheet->channels, channels_longest_segment_sort);
2608                 }
2609                 else if (sort_method == TRACKING_DOPE_SORT_TOTAL) {
2610                         BLI_listbase_sort(&dopesheet->channels, channels_total_track_sort);
2611                 }
2612                 else if (sort_method == TRACKING_DOPE_SORT_AVERAGE_ERROR) {
2613                         BLI_listbase_sort(&dopesheet->channels, channels_average_error_sort);
2614                 }
2615         }
2616 }
2617
2618 static int coverage_from_count(int count)
2619 {
2620         /* Values are actually arbitrary here, probably need to be tweaked. */
2621         if (count < 8)
2622                 return TRACKING_COVERAGE_BAD;
2623         else if (count < 16)
2624                 return TRACKING_COVERAGE_ACCEPTABLE;
2625         return TRACKING_COVERAGE_OK;
2626 }
2627
2628 /* Calculate coverage of frames with tracks, this information
2629  * is used to highlight dopesheet background depending on how
2630  * many tracks exists on the frame.
2631  */
2632 static void tracking_dopesheet_calc_coverage(MovieTracking *tracking)
2633 {
2634         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
2635         MovieTrackingObject *object = BKE_tracking_object_get_active(tracking);
2636         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
2637         MovieTrackingTrack *track;
2638         int frames, start_frame = INT_MAX, end_frame = -INT_MAX;
2639         int *per_frame_counter;
2640         int prev_coverage, last_segment_frame;
2641
2642         /* find frame boundaries */
2643         for (track = tracksbase->first; track; track = track->next) {
2644                 start_frame = min_ii(start_frame, track->markers[0].framenr);
2645                 end_frame = max_ii(end_frame, track->markers[track->markersnr - 1].framenr);
2646         }
2647
2648         frames = end_frame - start_frame + 1;
2649
2650         /* this is a per-frame counter of markers (how many markers belongs to the same frame) */
2651         per_frame_counter = MEM_callocN(sizeof(int) * frames, "per frame track counter");
2652
2653         /* find per-frame markers count */
2654         for (track = tracksbase->first; track; track = track->next) {
2655                 for (int i = 0; i < track->markersnr; i++) {
2656                         MovieTrackingMarker *marker = &track->markers[i];
2657
2658                         /* TODO: perhaps we need to add check for non-single-frame track here */
2659                         if ((marker->flag & MARKER_DISABLED) == 0)
2660                                 per_frame_counter[marker->framenr - start_frame]++;
2661                 }
2662         }
2663
2664         /* convert markers count to coverage and detect segments with the same coverage */
2665         prev_coverage = coverage_from_count(per_frame_counter[0]);
2666         last_segment_frame = start_frame;
2667
2668         /* means only disabled tracks in the beginning, could be ignored */
2669         if (!per_frame_counter[0])
2670                 prev_coverage = TRACKING_COVERAGE_OK;
2671
2672         for (int i = 1; i < frames; i++) {
2673                 int coverage = coverage_from_count(per_frame_counter[i]);
2674
2675                 /* means only disabled tracks in the end, could be ignored */
2676                 if (i == frames - 1 && !per_frame_counter[i])
2677                         coverage = TRACKING_COVERAGE_OK;
2678
2679                 if (coverage != prev_coverage || i == frames - 1) {
2680                         MovieTrackingDopesheetCoverageSegment *coverage_segment;
2681                         int end_segment_frame = i - 1 + start_frame;
2682
2683                         if (end_segment_frame == last_segment_frame)
2684                                 end_segment_frame++;
2685
2686                         coverage_segment = MEM_callocN(sizeof(MovieTrackingDopesheetCoverageSegment), "tracking coverage segment");
2687                         coverage_segment->coverage = prev_coverage;
2688                         coverage_segment->start_frame = last_segment_frame;
2689                         coverage_segment->end_frame = end_segment_frame;
2690
2691                         BLI_addtail(&dopesheet->coverage_segments, coverage_segment);
2692
2693                         last_segment_frame = end_segment_frame;
2694                 }
2695
2696                 prev_coverage = coverage;
2697         }
2698
2699         MEM_freeN(per_frame_counter);
2700 }
2701
2702 /* Tag dopesheet for update, actual update will happen later
2703  * when it'll be actually needed.
2704  */
2705 void BKE_tracking_dopesheet_tag_update(MovieTracking *tracking)
2706 {
2707         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
2708
2709         dopesheet->ok = false;
2710 }
2711
2712 /* Do dopesheet update, if update is not needed nothing will happen. */
2713 void BKE_tracking_dopesheet_update(MovieTracking *tracking)
2714 {
2715         MovieTrackingDopesheet *dopesheet = &tracking->dopesheet;
2716
2717         short sort_method = dopesheet->sort_method;
2718         bool inverse = (dopesheet->flag & TRACKING_DOPE_SORT_INVERSE) != 0;
2719
2720         if (dopesheet->ok)
2721                 return;
2722
2723         tracking_dopesheet_free(dopesheet);
2724
2725         /* channels */
2726         tracking_dopesheet_channels_calc(tracking);
2727         tracking_dopesheet_channels_sort(tracking, sort_method, inverse);
2728
2729         /* frame coverage */
2730         tracking_dopesheet_calc_coverage(tracking);
2731
2732         dopesheet->ok = true;
2733 }