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