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