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