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