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