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