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