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