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