Merging remained part of hybrid tracker which adds correlation threshold
[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  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/blenkernel/intern/tracking.c
28  *  \ingroup bke
29  */
30
31 #include <stddef.h>
32 #include <limits.h>
33 #include <math.h>
34 #include <memory.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_gpencil_types.h"
39 #include "DNA_camera_types.h"
40 #include "DNA_movieclip_types.h"
41 #include "DNA_object_types.h"   /* SELECT */
42 #include "DNA_scene_types.h"
43
44 #include "BLI_utildefines.h"
45 #include "BLI_math.h"
46 #include "BLI_math_base.h"
47 #include "BLI_listbase.h"
48 #include "BLI_ghash.h"
49 #include "BLI_path_util.h"
50 #include "BLI_string.h"
51
52 #include "BKE_global.h"
53 #include "BKE_tracking.h"
54 #include "BKE_movieclip.h"
55 #include "BKE_object.h"
56 #include "BKE_scene.h"
57
58 #include "IMB_imbuf_types.h"
59 #include "IMB_imbuf.h"
60
61 #ifdef WITH_LIBMV
62 #  include "libmv-capi.h"
63 #else
64 struct libmv_Features;
65 #endif
66
67 typedef struct MovieDistortion {
68         struct libmv_CameraIntrinsics *intrinsics;
69 } MovieDistortion;
70
71 /*********************** common functions *************************/
72
73 void BKE_tracking_init_settings(MovieTracking *tracking)
74 {
75         tracking->camera.sensor_width= 35.0f;
76         tracking->camera.pixel_aspect= 1.0f;
77         tracking->camera.units= CAMERA_UNITS_MM;
78
79         tracking->settings.default_tracker= TRACKER_HYBRID;
80         tracking->settings.default_minimum_correlation= 0.75;
81         tracking->settings.default_pattern_size= 11;
82         tracking->settings.default_search_size= 51;
83         tracking->settings.default_pyramid_levels= 2;
84         tracking->settings.keyframe1= 1;
85         tracking->settings.keyframe2= 30;
86         tracking->settings.dist= 1;
87
88         tracking->stabilization.scaleinf= 1.0f;
89         tracking->stabilization.locinf= 1.0f;
90         tracking->stabilization.rotinf= 1.0f;
91         tracking->stabilization.maxscale= 2.0f;
92 }
93
94 void BKE_tracking_clamp_track(MovieTrackingTrack *track, int event)
95 {
96         int a;
97         float pat_min[2];
98         float pat_max[2];
99         float max_pyramid_level_factor = 1.0;
100
101         if (track->tracker == TRACKER_KLT) {
102                 max_pyramid_level_factor= 1 << (track->pyramid_levels - 1);
103         }
104
105         /* sort */
106         for(a= 0; a<2; a++) {
107                 if(track->pat_min[a]>track->pat_max[a])
108                         SWAP(float, track->pat_min[a], track->pat_max[a]);
109
110                 if(track->search_min[a]>track->search_max[a])
111                         SWAP(float, track->search_min[a], track->search_max[a]);
112         }
113
114         /* compute the effective pattern size, which differs from the fine resolution
115          * pattern size for the pyramid KLT tracker */
116         for(a= 0; a<2; a++) {
117                 pat_min[a] = max_pyramid_level_factor * track->pat_min[a];
118                 pat_max[a] = max_pyramid_level_factor * track->pat_max[a];
119         }
120
121         if(event==CLAMP_PAT_DIM) {
122                 for(a= 0; a<2; a++) {
123                         /* search shouldn't be resized smaller than pattern */
124                         track->search_min[a]= MIN2(pat_min[a], track->search_min[a]);
125                         track->search_max[a]= MAX2(pat_max[a], track->search_max[a]);
126                 }
127         }
128         else if(event==CLAMP_PAT_POS) {
129                 float dim[2];
130                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
131
132                 for(a= 0; a<2; a++) {
133                         /* pattern shouldn't be moved outside of search */
134                         if(pat_min[a] < track->search_min[a]) {
135                                 track->pat_min[a]= track->search_min[a] - (pat_min[a] - track->pat_min[a]);
136                                 track->pat_max[a]= track->pat_min[a] + dim[a];
137                         }
138                         if(track->pat_max[a] > track->search_max[a]) {
139                                 track->pat_max[a]= track->search_max[a] - (pat_max[a] - track->pat_max[a]);
140                                 track->pat_min[a]= track->pat_max[a] - dim[a];
141                         }
142                 }
143         }
144         else if(event==CLAMP_SEARCH_DIM) {
145                 for(a= 0; a<2; a++) {
146                         /* search shouldn't be resized smaller than pattern */
147                         track->search_min[a]= MIN2(pat_min[a], track->search_min[a]);
148                         track->search_max[a]= MAX2(pat_max[a], track->search_max[a]);
149                 }
150         }
151         else if(event==CLAMP_SEARCH_POS) {
152                 float dim[2];
153                 sub_v2_v2v2(dim, track->search_max, track->search_min);
154
155                 for(a= 0; a<2; a++) {
156                         /* search shouldn't be moved inside pattern */
157                         if(track->search_min[a] > pat_min[a]) {
158                                 track->search_min[a]= pat_min[a];
159                                 track->search_max[a]= track->search_min[a]+dim[a];
160                         }
161                         if(track->search_max[a] < pat_max[a]) {
162                                 track->search_max[a]= pat_max[a];
163                                 track->search_min[a]= track->search_max[a]-dim[a];
164                         }
165                 }
166         }
167         else if(event==CLAMP_PYRAMID_LEVELS || (event==CLAMP_SEARCH_DIM && track->tracker == TRACKER_KLT))  {
168                 float dim[2];
169                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
170                 {
171                         float search_ratio= 2.3f * max_pyramid_level_factor;
172
173                         /* resize the search area to something sensible based
174                          * on the number of pyramid levels */
175                         for(a= 0; a<2; a++) {
176                                 track->search_min[a]= search_ratio * track->pat_min[a];
177                                 track->search_max[a]= search_ratio * track->pat_max[a];
178                         }
179                 }
180         }
181
182         /* marker's center should be in center of pattern */
183         if(event==CLAMP_PAT_DIM || event==CLAMP_PAT_POS) {
184                 float dim[2];
185                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
186
187                 for(a= 0; a<2; a++) {
188                         track->pat_min[a]= -dim[a]/2.0f;
189                         track->pat_max[a]= dim[a]/2.0f;
190                 }
191         }
192 }
193
194 void BKE_tracking_track_flag(MovieTrackingTrack *track, int area, int flag, int clear)
195 {
196         if(area==TRACK_AREA_NONE)
197                 return;
198
199         if(clear) {
200                 if(area&TRACK_AREA_POINT)       track->flag&= ~flag;
201                 if(area&TRACK_AREA_PAT)         track->pat_flag&= ~flag;
202                 if(area&TRACK_AREA_SEARCH)      track->search_flag&= ~flag;
203         } else {
204                 if(area&TRACK_AREA_POINT)       track->flag|= flag;
205                 if(area&TRACK_AREA_PAT)         track->pat_flag|= flag;
206                 if(area&TRACK_AREA_SEARCH)      track->search_flag|= flag;
207         }
208 }
209
210 MovieTrackingTrack *BKE_tracking_add_track(MovieTracking *tracking, float x, float y,
211                         int framenr, int width, int height)
212 {
213         MovieTrackingTrack *track;
214         MovieTrackingMarker marker;
215         MovieTrackingSettings *settings= &tracking->settings;
216
217         float half_pattern= (float)settings->default_pattern_size/2.0f;
218         float half_search= (float)settings->default_search_size/2.0f;
219         float pat[2], search[2];
220
221         pat[0]= half_pattern/(float)width;
222         pat[1]= half_pattern/(float)height;
223
224         search[0]= half_search/(float)width;
225         search[1]= half_search/(float)height;
226
227         track= MEM_callocN(sizeof(MovieTrackingTrack), "add_marker_exec track");
228         strcpy(track->name, "Track");
229
230         track->tracker= settings->default_tracker;
231         track->pyramid_levels= settings->default_pyramid_levels;
232         track->minimum_correlation= settings->default_minimum_correlation;
233         track->margin= settings->default_margin;
234         track->pattern_match= settings->default_pattern_match;
235         track->frames_limit= settings->default_frames_limit;
236
237         memset(&marker, 0, sizeof(marker));
238         marker.pos[0]= x;
239         marker.pos[1]= y;
240         marker.framenr= framenr;
241
242         copy_v2_v2(track->pat_max, pat);
243         negate_v2_v2(track->pat_min, pat);
244
245         copy_v2_v2(track->search_max, search);
246         negate_v2_v2(track->search_min, search);
247
248         BKE_tracking_insert_marker(track, &marker);
249
250         if(track->tracker == TRACKER_KLT)
251                 BKE_tracking_clamp_track(track, CLAMP_PYRAMID_LEVELS);
252
253         BLI_addtail(&tracking->tracks, track);
254         BKE_track_unique_name(tracking, track);
255
256         return track;
257 }
258
259 void BKE_tracking_insert_marker(MovieTrackingTrack *track, MovieTrackingMarker *marker)
260 {
261         MovieTrackingMarker *old_marker= NULL;
262
263         if(track->markersnr)
264                 old_marker= BKE_tracking_exact_marker(track, marker->framenr);
265
266         if(old_marker) {
267                 *old_marker= *marker;
268         } else {
269                 int a= track->markersnr;
270
271                 while(a--) {
272                         if(track->markers[a].framenr<marker->framenr)
273                                 break;
274                 }
275
276                 track->markersnr++;
277
278                 if(track->markers) track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
279                 else track->markers= MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
280
281                 memmove(track->markers+a+2, track->markers+a+1, (track->markersnr-a-2)*sizeof(MovieTrackingMarker));
282                 track->markers[a+1]= *marker;
283
284                 track->last_marker= a+1;
285         }
286 }
287
288 void BKE_tracking_delete_marker(MovieTrackingTrack *track, int framenr)
289 {
290         int a= 0;
291
292         while(a<track->markersnr) {
293                 if(track->markers[a].framenr==framenr) {
294                         if(track->markersnr>1) {
295                                 memmove(track->markers+a, track->markers+a+1, (track->markersnr-a-1)*sizeof(MovieTrackingMarker));
296                                 track->markersnr--;
297                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
298                         } else {
299                                 MEM_freeN(track->markers);
300                                 track->markers= NULL;
301                                 track->markersnr= 0;
302                         }
303
304                         break;
305                 }
306
307                 a++;
308         }
309 }
310
311 MovieTrackingMarker *BKE_tracking_get_marker(MovieTrackingTrack *track, int framenr)
312 {
313         int a= track->markersnr-1;
314
315         if(!track->markersnr)
316                 return NULL;
317
318         /* approximate pre-first framenr marker with first marker */
319         if(framenr<track->markers[0].framenr)
320                 return &track->markers[0];
321
322         if(track->last_marker<track->markersnr)
323                 a= track->last_marker;
324
325         if(track->markers[a].framenr<=framenr) {
326                 while(a<track->markersnr && track->markers[a].framenr<=framenr) {
327                         if(track->markers[a].framenr==framenr) {
328                                 track->last_marker= a;
329                                 return &track->markers[a];
330                         }
331                         a++;
332                 }
333
334                 /* if there's no marker for exact position, use nearest marker from left side */
335                 return &track->markers[a-1];
336         } else {
337                 while(a>=0 && track->markers[a].framenr>=framenr) {
338                         if(track->markers[a].framenr==framenr) {
339                                 track->last_marker= a;
340                                 return &track->markers[a];
341                         }
342
343                         a--;
344                 }
345
346                 /* if there's no marker for exact position, use nearest marker from left side */
347                 return &track->markers[a];
348         }
349
350         return NULL;
351 }
352
353 MovieTrackingMarker *BKE_tracking_ensure_marker(MovieTrackingTrack *track, int framenr)
354 {
355         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
356
357         if(marker->framenr!=framenr) {
358                 MovieTrackingMarker marker_new;
359
360                 marker_new= *marker;
361                 marker_new.framenr= framenr;
362
363                 BKE_tracking_insert_marker(track, &marker_new);
364                 marker= BKE_tracking_get_marker(track, framenr);
365         }
366
367         return marker;
368 }
369
370 MovieTrackingMarker *BKE_tracking_exact_marker(MovieTrackingTrack *track, int framenr)
371 {
372         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
373
374         if(marker->framenr!=framenr)
375                 return NULL;
376
377         return marker;
378 }
379
380 int BKE_tracking_has_marker(MovieTrackingTrack *track, int framenr)
381 {
382         return BKE_tracking_exact_marker(track, framenr) != 0;
383 }
384
385 void BKE_tracking_free_track(MovieTrackingTrack *track)
386 {
387         if(track->markers) MEM_freeN(track->markers);
388 }
389
390 static void put_disabled_marker(MovieTrackingTrack *track, MovieTrackingMarker *ref_marker, int before, int overwrite)
391 {
392         MovieTrackingMarker marker_new;
393
394         marker_new= *ref_marker;
395         marker_new.flag&= ~MARKER_TRACKED;
396         marker_new.flag|= MARKER_DISABLED;
397
398         if(before) marker_new.framenr--;
399         else marker_new.framenr++;
400
401         if(!BKE_tracking_has_marker(track, marker_new.framenr) || overwrite)
402                 BKE_tracking_insert_marker(track, &marker_new);
403 }
404
405 void BKE_tracking_clear_path(MovieTrackingTrack *track, int ref_frame, int action)
406 {
407         int a;
408
409         if(action==TRACK_CLEAR_REMAINED) {
410                 a= 1;
411                 while(a<track->markersnr) {
412                         if(track->markers[a].framenr>ref_frame) {
413                                 track->markersnr= a;
414                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
415
416                                 break;
417                         }
418
419                         a++;
420                 }
421
422                 if(track->markersnr)
423                         put_disabled_marker(track, &track->markers[track->markersnr-1], 0, 1);
424         } else if(action==TRACK_CLEAR_UPTO) {
425                 a= track->markersnr-1;
426                 while(a>=0) {
427                         if(track->markers[a].framenr<=ref_frame) {
428                                 memmove(track->markers, track->markers+a, (track->markersnr-a)*sizeof(MovieTrackingMarker));
429
430                                 track->markersnr= track->markersnr-a;
431                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
432
433                                 break;
434                         }
435
436                         a--;
437                 }
438
439                 if(track->markersnr)
440                         put_disabled_marker(track, &track->markers[0], 1, 1);
441         } else if(action==TRACK_CLEAR_ALL) {
442                 MovieTrackingMarker *marker, marker_new;
443
444                 marker= BKE_tracking_get_marker(track, ref_frame);
445                 marker_new= *marker;
446
447                 MEM_freeN(track->markers);
448                 track->markers= NULL;
449                 track->markersnr= 0;
450
451                 BKE_tracking_insert_marker(track, &marker_new);
452
453                 put_disabled_marker(track, &marker_new, 1, 1);
454                 put_disabled_marker(track, &marker_new, 0, 1);
455         }
456 }
457
458 int BKE_tracking_test_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
459 {
460         int a= 0, b= 0;
461         int count= 0;
462
463         while(a<src_track->markersnr || b<dst_track->markersnr) {
464                 if(b>=dst_track->markersnr) {
465                         a++;
466                         count++;
467                 }
468                 else if(a>=src_track->markersnr) {
469                         b++;
470                         count++;
471                 }
472                 else if(src_track->markers[a].framenr<dst_track->markers[b].framenr) {
473                         a++;
474                         count++;
475                 } else if(src_track->markers[a].framenr>dst_track->markers[b].framenr) {
476                         b++;
477                         count++;
478                 } else {
479                         if((src_track->markers[a].flag&MARKER_DISABLED)==0 && (dst_track->markers[b].flag&MARKER_DISABLED)==0)
480                                 return 0;
481
482                         a++;
483                         b++;
484                         count++;
485                 }
486         }
487
488         return count;
489 }
490
491 void BKE_tracking_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
492 {
493         int i, a= 0, b= 0, tot;
494         MovieTrackingMarker *markers;
495
496         tot= BKE_tracking_test_join_tracks(dst_track, src_track);
497
498         markers= MEM_callocN(tot*sizeof(MovieTrackingMarker), "tracking joined tracks");
499
500         for(i= 0; i<tot; i++) {
501                 if(b>=dst_track->markersnr) {
502                         markers[i]= src_track->markers[a++];
503                 }
504                 else if(a>=src_track->markersnr) {
505                         markers[i]= dst_track->markers[b++];
506                 }
507                 else if(src_track->markers[a].framenr<dst_track->markers[b].framenr) {
508                         markers[i]= src_track->markers[a++];
509                 } else if(src_track->markers[a].framenr>dst_track->markers[b].framenr) {
510                         markers[i]= dst_track->markers[b++];
511                 } else {
512                         if((src_track->markers[a].flag&MARKER_DISABLED)) markers[i]= dst_track->markers[b];
513                         else markers[i]= src_track->markers[a++];
514
515                         a++;
516                         b++;
517                 }
518         }
519
520         MEM_freeN(dst_track->markers);
521
522         dst_track->markers= markers;
523         dst_track->markersnr= tot;
524 }
525
526 void BKE_tracking_free(MovieTracking *tracking)
527 {
528         MovieTrackingTrack *track;
529
530         for(track= tracking->tracks.first; track; track= track->next) {
531                 BKE_tracking_free_track(track);
532         }
533
534         BLI_freelistN(&tracking->tracks);
535
536         if(tracking->reconstruction.cameras)
537                 MEM_freeN(tracking->reconstruction.cameras);
538
539         if(tracking->stabilization.scaleibuf)
540                 IMB_freeImBuf(tracking->stabilization.scaleibuf);
541
542         if(tracking->camera.intrinsics)
543                 BKE_tracking_distortion_destroy(tracking->camera.intrinsics);
544 }
545
546 /*********************** tracks map *************************/
547
548 typedef struct TracksMap {
549         int num_tracks;
550         int customdata_size;
551
552         char *customdata;
553         MovieTrackingTrack *tracks;
554
555         GHash *hash;
556
557         int ptr;
558 } TracksMap;
559
560 static TracksMap *tracks_map_new(int num_tracks, int customdata_size)
561 {
562         TracksMap *map= MEM_callocN(sizeof(TracksMap), "TrackingsMap");
563
564         map->num_tracks= num_tracks;
565         map->customdata_size= customdata_size;
566
567         map->tracks= MEM_callocN(sizeof(MovieTrackingTrack)*num_tracks, "TrackingsMap tracks");
568
569         if(customdata_size)
570                 map->customdata= MEM_callocN(customdata_size*num_tracks, "TracksMap customdata");
571
572         map->hash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "TracksMap hash");
573
574         return map;
575 }
576
577 static int tracks_map_size(TracksMap *map)
578 {
579         return map->num_tracks;
580 }
581
582 static void tracks_map_get(TracksMap *map, int index, MovieTrackingTrack **track, void **customdata)
583 {
584         *track= &map->tracks[index];
585
586         if(map->customdata)
587                 *customdata= &map->customdata[index*map->customdata_size];
588 }
589
590 static void tracks_map_insert(TracksMap *map, MovieTrackingTrack *track, void *customdata)
591 {
592         MovieTrackingTrack new_track= *track;
593
594         new_track.markers= MEM_dupallocN(new_track.markers);
595
596         map->tracks[map->ptr]= new_track;
597
598         if(customdata)
599                 memcpy(&map->customdata[map->ptr*map->customdata_size], customdata, map->customdata_size);
600
601         BLI_ghash_insert(map->hash, &map->tracks[map->ptr], track);
602
603         map->ptr++;
604 }
605
606 static void tracks_map_merge(TracksMap *map, MovieTracking *tracking)
607 {
608         MovieTrackingTrack *track;
609         ListBase tracks= {NULL, NULL}, new_tracks= {NULL, NULL};
610         ListBase *old_tracks= &tracking->tracks;
611         int a;
612
613         /* duplicate currently operating tracks to temporary list.
614            this is needed to keep names in unique state and it's faster to change names
615            of currently operating tracks (if needed) */
616         for(a= 0; a<map->num_tracks; a++) {
617                 int replace_sel= 0;
618                 MovieTrackingTrack *new_track, *old;
619
620                 track= &map->tracks[a];
621
622                 /* find original of operating track in list of previously displayed tracks */
623                 old= BLI_ghash_lookup(map->hash, track);
624                 if(old) {
625                         MovieTrackingTrack *cur= old_tracks->first;
626
627                         while(cur) {
628                                 if(cur==old)
629                                         break;
630
631                                 cur= cur->next;
632                         }
633
634                         /* original track was found, re-use flags and remove this track */
635                         if(cur) {
636                                 if(cur==tracking->act_track)
637                                         replace_sel= 1;
638
639                                 track->flag= cur->flag;
640                                 track->pat_flag= cur->pat_flag;
641                                 track->search_flag= cur->search_flag;
642
643                                 BKE_tracking_free_track(cur);
644                                 BLI_freelinkN(old_tracks, cur);
645                         }
646                 }
647
648                 new_track= MEM_callocN(sizeof(MovieTrackingTrack), "tracksMapMerge new_track");
649                 *new_track= *track;
650                 new_track->markers= MEM_dupallocN(new_track->markers);
651
652                 BLI_ghash_remove(map->hash, track, NULL, NULL); /* XXX: are we actually need this */
653                 BLI_ghash_insert(map->hash, track, new_track);
654
655                 if(replace_sel)         /* update current selection in clip */
656                         tracking->act_track= new_track;
657
658                 BLI_addtail(&tracks, new_track);
659         }
660
661         /* move all tracks, which aren't operating */
662         track= old_tracks->first;
663         while(track) {
664                 MovieTrackingTrack *next= track->next;
665
666                 track->next= track->prev= NULL;
667                 BLI_addtail(&new_tracks, track);
668
669                 track= next;
670         }
671
672         /* now move all tracks which are currently operating and keep their names unique */
673         track= tracks.first;
674         while(track) {
675                 MovieTrackingTrack *next= track->next;
676
677                 BLI_remlink(&tracks, track);
678
679                 track->next= track->prev= NULL;
680                 BLI_addtail(&new_tracks, track);
681
682                 BLI_uniquename(&new_tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
683
684                 track= next;
685         }
686
687         tracking->tracks= new_tracks;
688 }
689
690 static void tracks_map_free(TracksMap *map, void (*customdata_free) (void *customdata))
691 {
692         int i= 0;
693
694         BLI_ghash_free(map->hash, NULL, NULL);
695
696         for(i= 0; i<map->num_tracks; i++) {
697                 if(map->customdata && customdata_free)
698                         customdata_free(&map->customdata[i*map->customdata_size]);
699
700                 BKE_tracking_free_track(&map->tracks[i]);
701         }
702
703         if(map->customdata)
704                 MEM_freeN(map->customdata);
705
706         MEM_freeN(map->tracks);
707         MEM_freeN(map);
708 }
709
710 /*********************** tracking *************************/
711
712 typedef struct TrackContext {
713 #ifdef WITH_LIBMV
714         float keyframed_pos[2];
715
716         /* ** KLT tracker ** */
717         struct libmv_RegionTracker *region_tracker;
718         float *patch;                   /* keyframed patch */
719
720         /* ** SAD tracker ** */
721         int pattern_size;               /* size of pattern */
722         unsigned char *pattern; /* keyframed pattern */
723         unsigned char *warped;  /* warped version of reference */
724 #else
725         int pad;
726 #endif
727 } TrackContext;
728
729 typedef struct MovieTrackingContext {
730         MovieClipUser user;
731         MovieClip *clip;
732
733         int first_time, frames;
734
735         MovieTrackingSettings settings;
736         TracksMap *tracks_map;
737
738         short backwards, disable_failed;
739         int sync_frame;
740 } MovieTrackingContext;
741
742 MovieTrackingContext *BKE_tracking_context_new(MovieClip *clip, MovieClipUser *user, short backwards, short disable_failed)
743 {
744         MovieTrackingContext *context= MEM_callocN(sizeof(MovieTrackingContext), "trackingContext");
745         MovieTracking *tracking= &clip->tracking;
746         MovieTrackingSettings *settings= &tracking->settings;
747         MovieTrackingTrack *track;
748         int num_tracks= 0;
749
750         context->settings= *settings;
751         context->backwards= backwards;
752         context->disable_failed= disable_failed;
753         context->sync_frame= user->framenr;
754         context->first_time= 1;
755
756         /* count */
757         track= tracking->tracks.first;
758         while(track) {
759                 if(TRACK_SELECTED(track) && (track->flag&TRACK_LOCKED)==0) {
760                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
761
762                         if((marker->flag&MARKER_DISABLED)==0)
763                                 num_tracks++;
764                 }
765
766                 track= track->next;
767         }
768
769         if(num_tracks) {
770                 int width, height;
771
772                 context->tracks_map= tracks_map_new(num_tracks, sizeof(TrackContext));
773
774                 BKE_movieclip_get_size(clip, user, &width, &height);
775
776                 /* create tracking data */
777                 track= tracking->tracks.first;
778                 while(track) {
779                         if(TRACK_SELECTED(track) && (track->flag&TRACK_LOCKED)==0) {
780                                 MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
781
782                                 if((marker->flag&MARKER_DISABLED)==0) {
783                                         TrackContext track_context;
784
785                                         memset(&track_context, 0, sizeof(TrackContext));
786
787 #ifdef WITH_LIBMV
788                                         {
789                                                 float patx, paty;
790                                                 patx= (int)((track->pat_max[0]-track->pat_min[0])*width);
791                                                 paty= (int)((track->pat_max[1]-track->pat_min[1])*height);
792
793                                                 if(ELEM(track->tracker, TRACKER_KLT, TRACKER_HYBRID)) {
794                                                         float search_size_x= (track->search_max[0]-track->search_min[0])*width;
795                                                         float search_size_y= (track->search_max[1]-track->search_min[1])*height;
796                                                         float pattern_size_x= (track->pat_max[0]-track->pat_min[0])*width;
797                                                         float pattern_size_y= (track->pat_max[1]-track->pat_min[1])*height;
798                                                         int wndx= (int)patx/2, wndy= (int)paty/2;
799
800                                                         /* compute the maximum pyramid size */
801                                                         float search_to_pattern_ratio= MIN2(search_size_x,  search_size_y)
802                                                                 / MAX2(pattern_size_x, pattern_size_y);
803                                                         float log2_search_to_pattern_ratio = log(floor(search_to_pattern_ratio)) / M_LN2;
804                                                         int max_pyramid_levels= floor(log2_search_to_pattern_ratio + 1);
805
806                                                         /* try to accomodate the user's choice of pyramid level in a way
807                                                          * that doesn't cause the coarsest pyramid pattern to be larger
808                                                          * than the search size */
809                                                         int level= MIN2(track->pyramid_levels, max_pyramid_levels);
810
811                                                         if(track->tracker==TRACKER_KLT)
812                                                                 track_context.region_tracker= libmv_pyramidRegionTrackerNew(100, level, MAX2(wndx, wndy), track->minimum_correlation);
813                                                         else
814                                                                 track_context.region_tracker= libmv_hybridRegionTrackerNew(100, MAX2(wndx, wndy), track->minimum_correlation);
815                                                 }
816                                                 else if(track->tracker==TRACKER_SAD) {
817                                                         track_context.pattern_size= MAX2(patx, paty);
818                                                 }
819                                         }
820 #endif
821
822                                         tracks_map_insert(context->tracks_map, track, &track_context);
823                                 }
824                         }
825
826                         track= track->next;
827                 }
828         }
829
830         context->clip= clip;
831         context->user= *user;
832
833         return context;
834 }
835
836 static void track_context_free(void *customdata)
837 {
838         TrackContext *track_context= (TrackContext *)customdata;
839
840 #if WITH_LIBMV
841         if(track_context->region_tracker)
842                 libmv_regionTrackerDestroy(track_context->region_tracker);
843
844         if(track_context->patch)
845                 MEM_freeN(track_context->patch);
846
847         if(track_context->pattern)
848                 MEM_freeN(track_context->pattern);
849
850         if(track_context->warped)
851                 MEM_freeN(track_context->warped);
852 #else
853                 (void) track_context;
854 #endif
855 }
856
857 void BKE_tracking_context_free(MovieTrackingContext *context)
858 {
859         tracks_map_free(context->tracks_map, track_context_free);
860
861         MEM_freeN(context);
862 }
863
864 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track)
865 {
866         int x, y;
867
868         if((track->flag&(TRACK_DISABLE_RED|TRACK_DISABLE_GREEN|TRACK_DISABLE_BLUE))==0)
869                 return;
870
871         for(y= 0; y<ibuf->y; y++) {
872                 for (x= 0; x<ibuf->x; x++) {
873                         int pixel= ibuf->x*y + x;
874
875                         if(ibuf->rect_float) {
876                                 float *rrgbf= ibuf->rect_float + pixel*4;
877
878                                 if(track->flag&TRACK_DISABLE_RED)       rrgbf[0]= 0;
879                                 if(track->flag&TRACK_DISABLE_GREEN)     rrgbf[1]= 0;
880                                 if(track->flag&TRACK_DISABLE_BLUE)      rrgbf[2]= 0;
881                         } else {
882                                 char *rrgb= (char*)ibuf->rect + pixel*4;
883
884                                 if(track->flag&TRACK_DISABLE_RED)       rrgb[0]= 0;
885                                 if(track->flag&TRACK_DISABLE_GREEN)     rrgb[1]= 0;
886                                 if(track->flag&TRACK_DISABLE_BLUE)      rrgb[2]= 0;
887                         }
888                 }
889         }
890 }
891
892 static ImBuf *get_area_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
893                         float min[2], float max[2], int margin, int anchored, float pos[2], int origin[2])
894 {
895         ImBuf *tmpibuf;
896         int x, y;
897         int x1, y1, x2, y2, w, h;
898         float mpos[2];
899
900         copy_v2_v2(mpos, marker->pos);
901         if(anchored)
902                 add_v2_v2(mpos, track->offset);
903
904         x= mpos[0]*ibuf->x;
905         y= mpos[1]*ibuf->y;
906         x1= x-(int)(-min[0]*ibuf->x);
907         y1= y-(int)(-min[1]*ibuf->y);
908         x2= x+(int)(max[0]*ibuf->x);
909         y2= y+(int)(max[1]*ibuf->y);
910
911         /* dimensions should be odd */
912         w= (x2-x1)|1;
913         h= (y2-y1)|1;
914
915         tmpibuf= IMB_allocImBuf(w+margin*2, h+margin*2, 32, IB_rect);
916         IMB_rectcpy(tmpibuf, ibuf, 0, 0, x1-margin, y1-margin, w+margin*2, h+margin*2);
917
918         if(pos != NULL) {
919                 pos[0]= mpos[0]*ibuf->x-x1+margin;
920                 pos[1]= mpos[1]*ibuf->y-y1+margin;
921         }
922
923         if(origin != NULL) {
924                 origin[0]= x1-margin;
925                 origin[1]= y1-margin;
926         }
927
928         disable_imbuf_channels(tmpibuf, track);
929
930         return tmpibuf;
931 }
932
933 ImBuf *BKE_tracking_get_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
934                         int margin, int anchored, float pos[2], int origin[2])
935 {
936         return get_area_imbuf(ibuf, track, marker, track->pat_min, track->pat_max, margin, anchored, pos, origin);
937 }
938
939 ImBuf *BKE_tracking_get_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
940                         int margin, int anchored, float pos[2], int origin[2])
941 {
942         return get_area_imbuf(ibuf, track, marker, track->search_min, track->search_max, margin, anchored, pos, origin);
943 }
944
945 #ifdef WITH_LIBMV
946 static float *get_search_floatbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
947                         int *width_r, int *height_r, float pos[2], int origin[2])
948 {
949         ImBuf *tmpibuf;
950         float *pixels, *fp;
951         int x, y, width, height;
952
953         width= (track->search_max[0]-track->search_min[0])*ibuf->x;
954         height= (track->search_max[1]-track->search_min[1])*ibuf->y;
955
956         tmpibuf= BKE_tracking_get_search_imbuf(ibuf, track, marker, 0, 0, pos, origin);
957         disable_imbuf_channels(tmpibuf, track);
958
959         *width_r= width;
960         *height_r= height;
961
962         fp= pixels= MEM_callocN(width*height*sizeof(float), "tracking floatBuf");
963         for(y= 0; y<(int)height; y++) {
964                 for (x= 0; x<(int)width; x++) {
965                         int pixel= tmpibuf->x*y + x;
966
967                         if(tmpibuf->rect_float) {
968                                 float *rrgbf= tmpibuf->rect_float + pixel*4;
969
970                                 *fp= 0.2126*rrgbf[0] + 0.7152*rrgbf[1] + 0.0722*rrgbf[2];
971                         } else {
972                                 unsigned char *rrgb= (unsigned char*)tmpibuf->rect + pixel*4;
973
974                                 *fp= (0.2126*rrgb[0] + 0.7152*rrgb[1] + 0.0722*rrgb[2])/255.0f;
975                         }
976
977                         fp++;
978                 }
979         }
980
981         IMB_freeImBuf(tmpibuf);
982
983         return pixels;
984 }
985
986 static unsigned char *get_ucharbuf(ImBuf *ibuf)
987 {
988         int x, y;
989         unsigned char *pixels, *cp;
990
991         cp= pixels= MEM_callocN(ibuf->x*ibuf->y*sizeof(unsigned char), "tracking ucharBuf");
992         for(y= 0; y<ibuf->y; y++) {
993                 for (x= 0; x<ibuf->x; x++) {
994                         int pixel= ibuf->x*y + x;
995
996                         if(ibuf->rect_float) {
997                                 float *rrgbf= ibuf->rect_float + pixel*4;
998
999                                 *cp= FTOCHAR(0.2126f*rrgbf[0] + 0.7152f*rrgbf[1] + 0.0722f*rrgbf[2]);
1000                         } else {
1001                                 unsigned char *rrgb= (unsigned char*)ibuf->rect + pixel*4;
1002
1003                                 *cp= 0.2126f*rrgb[0] + 0.7152f*rrgb[1] + 0.0722f*rrgb[2];
1004                         }
1005
1006                         cp++;
1007                 }
1008         }
1009
1010         return pixels;
1011 }
1012
1013 static unsigned char *get_search_bytebuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1014                         int *width_r, int *height_r, float pos[2], int origin[2])
1015 {
1016         ImBuf *tmpibuf;
1017         unsigned char *pixels;
1018
1019         tmpibuf= BKE_tracking_get_search_imbuf(ibuf, track, marker, 0, 0, pos, origin);
1020         disable_imbuf_channels(tmpibuf, track);
1021
1022         *width_r= tmpibuf->x;
1023         *height_r= tmpibuf->y;
1024
1025         pixels= get_ucharbuf(tmpibuf);
1026
1027         IMB_freeImBuf(tmpibuf);
1028
1029         return pixels;
1030 }
1031
1032 static ImBuf *get_frame_ibuf(MovieTrackingContext *context, int framenr)
1033 {
1034         ImBuf *ibuf;
1035         MovieClipUser user= context->user;
1036
1037         user.framenr= framenr;
1038
1039         ibuf= BKE_movieclip_get_ibuf_flag(context->clip, &user, 0);
1040
1041         return ibuf;
1042 }
1043
1044 static ImBuf *get_keyframed_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track,
1045                         MovieTrackingMarker *marker, MovieTrackingMarker **marker_keyed)
1046 {
1047         int framenr= marker->framenr;
1048         int a= marker-track->markers;
1049
1050         *marker_keyed= marker;
1051
1052         while(a>=0 && a<track->markersnr) {
1053                 int next= (context->backwards) ? a+1 : a-1;
1054                 int is_keyframed= 0;
1055                 MovieTrackingMarker *cur_marker= &track->markers[a];
1056                 MovieTrackingMarker *next_marker= NULL;
1057
1058                 if(next>=0 && next<track->markersnr)
1059                         next_marker= &track->markers[next];
1060
1061                 /* if next mrker is disabled, stop searching keyframe and use current frame as keyframe */
1062                 if(next_marker && next_marker->flag&MARKER_DISABLED)
1063                         is_keyframed= 1;
1064
1065                 is_keyframed|= (cur_marker->flag&MARKER_TRACKED)==0;
1066
1067                 if(is_keyframed) {
1068                         framenr= cur_marker->framenr;
1069                         *marker_keyed= cur_marker;
1070                         break;
1071                 }
1072
1073                 a= next;
1074         }
1075
1076         return get_frame_ibuf(context, framenr);
1077 }
1078
1079 static ImBuf *get_adjust_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1080                         int curfra, MovieTrackingMarker **marker_keyed)
1081 {
1082         ImBuf *ibuf= NULL;
1083
1084         if(track->pattern_match == TRACK_MATCH_KEYFRAME) {
1085                 ibuf= get_keyframed_ibuf(context, track, marker, marker_keyed);
1086         } else {
1087                 ibuf= get_frame_ibuf(context, curfra);
1088
1089                 /* use current marker as keyframed position */
1090                 *marker_keyed= marker;
1091         }
1092
1093         return ibuf;
1094 }
1095
1096 static void get_warped(TrackContext *track_context, int x, int y, int width, unsigned char *image)
1097 {
1098         int i, j;
1099
1100         for(i=0; i<track_context->pattern_size; i++) {
1101                 for(j=0; j<track_context->pattern_size; j++) {
1102                         track_context->warped[i*track_context->pattern_size+j]=
1103                                         image[(y+i-track_context->pattern_size/2)*width+x+j-track_context->pattern_size/2];
1104                 }
1105         }
1106 }
1107
1108 #endif
1109
1110 void BKE_tracking_sync(MovieTrackingContext *context)
1111 {
1112         MovieTracking *tracking= &context->clip->tracking;
1113         int newframe;
1114
1115         tracks_map_merge(context->tracks_map, tracking);
1116
1117         if(context->backwards) newframe= context->user.framenr+1;
1118         else newframe= context->user.framenr-1;
1119
1120         context->sync_frame= newframe;
1121 }
1122
1123 void BKE_tracking_sync_user(MovieClipUser *user, MovieTrackingContext *context)
1124 {
1125         user->framenr= context->sync_frame;
1126 }
1127
1128 int BKE_tracking_next(MovieTrackingContext *context)
1129 {
1130         ImBuf *ibuf_new;
1131         int curfra= context->user.framenr;
1132         int a, ok= 0, map_size;
1133
1134         map_size= tracks_map_size(context->tracks_map);
1135
1136         /* nothing to track, avoid unneeded frames reading to save time and memory */
1137         if(!map_size)
1138                 return 0;
1139
1140         if(context->backwards) context->user.framenr--;
1141         else context->user.framenr++;
1142
1143         ibuf_new= BKE_movieclip_get_ibuf_flag(context->clip, &context->user, 0);
1144         if(!ibuf_new)
1145                 return 0;
1146
1147         #pragma omp parallel for private(a) shared(ibuf_new, ok) if(map_size>1)
1148         for(a= 0; a<map_size; a++) {
1149                 TrackContext *track_context;
1150                 MovieTrackingTrack *track;
1151                 MovieTrackingMarker *marker;
1152
1153                 tracks_map_get(context->tracks_map, a, &track, (void**)&track_context);
1154
1155                 marker= BKE_tracking_exact_marker(track, curfra);
1156
1157                 if(marker && (marker->flag&MARKER_DISABLED)==0) {
1158 #ifdef WITH_LIBMV
1159                         int width, height, origin[2], tracked= 0, need_readjust= 0;
1160                         float pos[2], margin[2], dim[2];
1161                         double x1, y1, x2, y2;
1162                         ImBuf *ibuf= NULL;
1163                         MovieTrackingMarker marker_new, *marker_keyed;
1164                         int onbound= 0, coords_correct= 0;
1165                         int nextfra;
1166
1167                         if(track->pattern_match==TRACK_MATCH_KEYFRAME)
1168                                 need_readjust= context->first_time;
1169                         else
1170                                 need_readjust= 1;
1171
1172                         if(context->backwards) nextfra= curfra-1;
1173                         else nextfra= curfra+1;
1174
1175                         /* margin from frame boundaries */
1176                         sub_v2_v2v2(dim, track->pat_max, track->pat_min);
1177                         margin[0]= margin[1]= MAX2(dim[0], dim[1]) / 2.0f;
1178
1179                         margin[0]= MAX2(margin[0], (float)track->margin / ibuf_new->x);
1180                         margin[1]= MAX2(margin[1], (float)track->margin / ibuf_new->y);
1181
1182                         /* do not track markers which are too close to boundary */
1183                         if(marker->pos[0]<margin[0] || marker->pos[0]>1.0f-margin[0] ||
1184                            marker->pos[1]<margin[1] || marker->pos[1]>1.0f-margin[1]) {
1185                                 onbound= 1;
1186                         }
1187                         else if(ELEM(track->tracker, TRACKER_KLT, TRACKER_HYBRID)) {
1188                                 float *patch_new;
1189
1190                                 if(need_readjust) {
1191                                         /* calculate patch for keyframed position */
1192                                         ibuf= get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1193
1194                                         if(track_context->patch)
1195                                                 MEM_freeN(track_context->patch);
1196
1197                                         track_context->patch= get_search_floatbuf(ibuf, track, marker_keyed, &width, &height, track_context->keyframed_pos, origin);
1198
1199                                         IMB_freeImBuf(ibuf);
1200                                 }
1201
1202                                 patch_new= get_search_floatbuf(ibuf_new, track, marker, &width, &height, pos, origin);
1203
1204                                 x1= track_context->keyframed_pos[0];
1205                                 y1= track_context->keyframed_pos[1];
1206
1207                                 x2= pos[0];
1208                                 y2= pos[1];
1209
1210                                 tracked= libmv_regionTrackerTrack(track_context->region_tracker, track_context->patch, patch_new,
1211                                                         width, height, x1, y1, &x2, &y2);
1212
1213                                 MEM_freeN(patch_new);
1214                         }
1215                         else if(track->tracker==TRACKER_SAD) {
1216                                 unsigned char *image_new;
1217                                 float correlation;
1218                                 float warp[3][2]={{0}};
1219
1220                                 if(need_readjust) {
1221                                         unsigned char *image;
1222
1223                                         /* calculate pattern for keyframed position */
1224                                         ibuf= get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1225
1226                                         image= get_search_bytebuf(ibuf, track, marker_keyed, &width, &height, pos, origin);
1227
1228                                         memset(warp, 0, sizeof(warp));
1229                                         warp[0][0]= 1;
1230                                         warp[1][1]= 1;
1231                                         warp[2][0]= pos[0];
1232                                         warp[2][1]= pos[1];
1233
1234                                         if(!track_context->pattern) {
1235                                                 int square= track_context->pattern_size*track_context->pattern_size;
1236                                                 track_context->pattern= MEM_callocN(sizeof(unsigned char)*square, "trackking pattern");
1237                                         }
1238
1239                                         libmv_SADSamplePattern(image, width, warp, track_context->pattern, track_context->pattern_size);
1240
1241                                         MEM_freeN(image);
1242                                         IMB_freeImBuf(ibuf);
1243                                 }
1244
1245                                 image_new= get_search_bytebuf(ibuf_new, track, marker, &width, &height, pos, origin);
1246
1247                                 if(track_context->warped==NULL) {
1248                                         unsigned char *image_old;
1249
1250                                         ibuf= get_frame_ibuf(context, curfra);
1251
1252                                         if(track_context->warped==NULL) {
1253                                                 int square= track_context->pattern_size*track_context->pattern_size;
1254                                                 track_context->warped= MEM_callocN(sizeof(unsigned char)*square, "trackking warped");
1255                                         }
1256
1257                                         image_old= get_search_bytebuf(ibuf, track, marker, &width, &height, pos, origin);
1258                                         get_warped(track_context, pos[0], pos[1], width, image_old);
1259                                         IMB_freeImBuf(ibuf);
1260                                         MEM_freeN(image_old);
1261                                 }
1262
1263                                 memset(warp, 0, sizeof(warp));
1264                                 warp[0][0]= 1;
1265                                 warp[1][1]= 1;
1266                                 warp[2][0]= pos[0];
1267                                 warp[2][1]= pos[1];
1268
1269                                 correlation= libmv_SADTrackerTrack(track_context->pattern, track_context->warped,
1270                                                         track_context->pattern_size, image_new, width, width, height, warp);
1271
1272                                 x2= warp[2][0];
1273                                 y2= warp[2][1];
1274
1275                                 tracked= track->minimum_correlation < correlation;
1276
1277                                 if(tracked)
1278                                         get_warped(track_context, x2, y2, width, image_new);
1279
1280                                 MEM_freeN(image_new);
1281                         }
1282
1283                         coords_correct= !isnan(x2) && !isnan(y2) && finite(x2) && finite(y2);
1284                         if(coords_correct && !onbound && (tracked || !context->disable_failed)) {
1285                                 if(context->first_time) {
1286                                         #pragma omp critical
1287                                         {
1288                                                 /* check if there's no keyframe/tracked markers before tracking marker.
1289                                                    if so -- create disabled marker before currently tracking "segment" */
1290                                                 put_disabled_marker(track, marker, !context->backwards, 0);
1291                                         }
1292                                 }
1293
1294                                 memset(&marker_new, 0, sizeof(marker_new));
1295
1296                                 if(!onbound) {
1297                                         marker_new.pos[0]= (origin[0]+x2)/ibuf_new->x;
1298                                         marker_new.pos[1]= (origin[1]+y2)/ibuf_new->y;
1299                                 } else {
1300                                         copy_v2_v2(marker_new.pos, marker->pos);
1301                                 }
1302
1303                                 marker_new.flag|= MARKER_TRACKED;
1304                                 marker_new.framenr= nextfra;
1305
1306                                 #pragma omp critical
1307                                 {
1308                                         BKE_tracking_insert_marker(track, &marker_new);
1309                                 }
1310
1311                                 /* make currently tracked segment be finished with disabled marker */
1312                                 #pragma omp critical
1313                                 {
1314                                         put_disabled_marker(track, &marker_new, context->backwards, 0);
1315                                 }
1316                         } else {
1317                                 marker_new= *marker;
1318
1319                                 marker_new.framenr= nextfra;
1320                                 marker_new.flag|= MARKER_DISABLED;
1321
1322                                 #pragma omp critical
1323                                 {
1324                                         BKE_tracking_insert_marker(track, &marker_new);
1325                                 }
1326                         }
1327
1328                         ok= 1;
1329 #endif
1330                 }
1331         }
1332
1333         IMB_freeImBuf(ibuf_new);
1334
1335         context->first_time= 0;
1336         context->frames++;
1337
1338         return ok;
1339 }
1340
1341 /*********************** camera solving *************************/
1342
1343 typedef struct MovieReconstructContext {
1344 #ifdef WITH_LIBMV
1345         struct libmv_Tracks *tracks;
1346         int keyframe1, keyframe2;
1347         short refine_flags;
1348
1349         struct libmv_Reconstruction *reconstruction;
1350 #endif
1351
1352         float focal_length;
1353         float principal_point[2];
1354         float k1, k2, k3;
1355
1356         float reprojection_error;
1357
1358         TracksMap *tracks_map;
1359
1360         int sfra, efra;
1361 } MovieReconstructContext;
1362
1363 typedef struct ReconstructProgressData {
1364         short *stop;
1365         short *do_update;
1366         float *progress;
1367         char *stats_message;
1368         int message_size;
1369 } ReconstructProgressData;
1370
1371 #if WITH_LIBMV
1372 static struct libmv_Tracks *create_libmv_tracks(MovieTracking *tracking, int width, int height)
1373 {
1374         int tracknr= 0;
1375         MovieTrackingTrack *track;
1376         struct libmv_Tracks *tracks= libmv_tracksNew();
1377
1378         track= tracking->tracks.first;
1379         while(track) {
1380                 int a= 0;
1381
1382                 for(a= 0; a<track->markersnr; a++) {
1383                         MovieTrackingMarker *marker= &track->markers[a];
1384
1385                         if((marker->flag&MARKER_DISABLED)==0)
1386                                 libmv_tracksInsert(tracks, marker->framenr, tracknr,
1387                                                         marker->pos[0]*width, marker->pos[1]*height);
1388                 }
1389
1390                 track= track->next;
1391                 tracknr++;
1392         }
1393
1394         return tracks;
1395 }
1396
1397 static void retrieve_libmv_reconstruct_intrinscis(MovieReconstructContext *context, MovieTracking *tracking)
1398 {
1399         struct libmv_Reconstruction *libmv_reconstruction= context->reconstruction;
1400         struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_ReconstructionExtractIntrinsics(libmv_reconstruction);
1401
1402         float aspy= 1.0f/tracking->camera.pixel_aspect;
1403
1404         double focal_length, principal_x, principal_y, k1, k2, k3;
1405         int width, height;
1406
1407         libmv_CameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
1408                         &k1, &k2, &k3, &width, &height);
1409
1410         tracking->camera.focal= focal_length;
1411         tracking->camera.principal[0]= principal_x;
1412
1413         /* todo: verify divide by aspy is correct */
1414         tracking->camera.principal[1]= principal_y / aspy;
1415         tracking->camera.k1= k1;
1416         tracking->camera.k2= k2;
1417 }
1418
1419 static int retrieve_libmv_reconstruct_tracks(MovieReconstructContext *context, MovieTracking *tracking)
1420 {
1421         struct libmv_Reconstruction *libmv_reconstruction= context->reconstruction;
1422         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1423         MovieReconstructedCamera *reconstructed;
1424         MovieTrackingTrack *track;
1425         int ok= 1, tracknr= 0, a, origin_set= 0;
1426         int sfra= context->sfra, efra= context->efra;
1427         float imat[4][4];
1428
1429         unit_m4(imat);
1430
1431         track= tracking->tracks.first;
1432         while(track) {
1433                 double pos[3];
1434
1435                 if(libmv_reporojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
1436                         track->bundle_pos[0]= pos[0];
1437                         track->bundle_pos[1]= pos[1];
1438                         track->bundle_pos[2]= pos[2];
1439
1440                         track->flag|= TRACK_HAS_BUNDLE;
1441                         track->error= libmv_reporojectionErrorForTrack(libmv_reconstruction, tracknr);
1442                 } else {
1443                         track->flag&= ~TRACK_HAS_BUNDLE;
1444                         ok= 0;
1445
1446                         printf("No bundle for track #%d '%s'\n", tracknr, track->name);
1447                 }
1448
1449                 track= track->next;
1450                 tracknr++;
1451         }
1452
1453         if(reconstruction->cameras)
1454                 MEM_freeN(reconstruction->cameras);
1455
1456         reconstruction->camnr= 0;
1457         reconstruction->cameras= NULL;
1458         reconstructed= MEM_callocN((efra-sfra+1)*sizeof(MovieReconstructedCamera), "temp reconstructed camera");
1459
1460         for(a= sfra; a<=efra; a++) {
1461                 double matd[4][4];
1462
1463                 if(libmv_reporojectionCameraForImage(libmv_reconstruction, a, matd)) {
1464                         int i, j;
1465                         float mat[4][4];
1466                         float error= libmv_reporojectionErrorForImage(libmv_reconstruction, a);
1467
1468                         for(i=0; i<4; i++)
1469                                 for(j= 0; j<4; j++)
1470                                         mat[i][j]= matd[i][j];
1471
1472                         if(!origin_set) {
1473                                 copy_m4_m4(imat, mat);
1474                                 invert_m4(imat);
1475                                 origin_set= 1;
1476                         }
1477
1478                         if(origin_set)
1479                                 mul_m4_m4m4(mat, mat, imat);
1480
1481                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
1482                         reconstructed[reconstruction->camnr].framenr= a;
1483                         reconstructed[reconstruction->camnr].error= error;
1484                         reconstruction->camnr++;
1485                 } else {
1486                         ok= 0;
1487                         printf("No camera for frame %d\n", a);
1488                 }
1489         }
1490
1491         if(reconstruction->camnr) {
1492                 reconstruction->cameras= MEM_callocN(reconstruction->camnr*sizeof(MovieReconstructedCamera), "reconstructed camera");
1493                 memcpy(reconstruction->cameras, reconstructed, reconstruction->camnr*sizeof(MovieReconstructedCamera));
1494         }
1495
1496         if(origin_set) {
1497                 track= tracking->tracks.first;
1498                 while(track) {
1499                         if(track->flag&TRACK_HAS_BUNDLE)
1500                                 mul_v3_m4v3(track->bundle_pos, imat, track->bundle_pos);
1501
1502                         track= track->next;
1503                 }
1504         }
1505
1506         MEM_freeN(reconstructed);
1507
1508         return ok;
1509 }
1510
1511 static int retrieve_libmv_reconstruct(MovieReconstructContext *context, MovieTracking *tracking)
1512 {
1513         tracks_map_merge(context->tracks_map, tracking);
1514
1515         /* take the intrinscis back from libmv */
1516         retrieve_libmv_reconstruct_intrinscis(context, tracking);
1517
1518         return retrieve_libmv_reconstruct_tracks(context, tracking);
1519 }
1520
1521 static int get_refine_intrinsics_flags(MovieTracking *tracking)
1522 {
1523         int refine= tracking->settings.refine_camera_intrinsics;
1524         int flags= 0;
1525
1526         if(refine&REFINE_FOCAL_LENGTH)
1527                 flags|= LIBMV_REFINE_FOCAL_LENGTH;
1528
1529         if(refine&REFINE_PRINCIPAL_POINT)
1530                 flags|= LIBMV_REFINE_PRINCIPAL_POINT;
1531
1532         if(refine&REFINE_RADIAL_DISTORTION_K1)
1533                 flags|= REFINE_RADIAL_DISTORTION_K1;
1534
1535         if(refine&REFINE_RADIAL_DISTORTION_K2)
1536                 flags|= REFINE_RADIAL_DISTORTION_K2;
1537
1538         return flags;
1539 }
1540
1541 static int count_tracks_on_both_keyframes(MovieTracking *tracking)
1542 {
1543         int tot= 0;
1544         int frame1= tracking->settings.keyframe1, frame2= tracking->settings.keyframe2;
1545         MovieTrackingTrack *track;
1546
1547         track= tracking->tracks.first;
1548         while(track) {
1549                 if(BKE_tracking_has_marker(track, frame1))
1550                         if(BKE_tracking_has_marker(track, frame2))
1551                                 tot++;
1552
1553                 track= track->next;
1554         }
1555
1556         return tot;
1557 }
1558 #endif
1559
1560 int BKE_tracking_can_reconstruct(MovieTracking *tracking, char *error_msg, int error_size)
1561 {
1562 #if WITH_LIBMV
1563         if(count_tracks_on_both_keyframes(tracking)<8) {
1564                 BLI_strncpy(error_msg, "At least 8 tracks on both of keyframes are needed for reconstruction", error_size);
1565                 return 0;
1566         }
1567
1568         return 1;
1569 #else
1570         BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
1571         (void) tracking;
1572
1573         return 0;
1574 #endif
1575 }
1576
1577 MovieReconstructContext* BKE_tracking_reconstruction_context_new(MovieTracking *tracking,
1578                         int keyframe1, int keyframe2, int width, int height)
1579 {
1580         MovieReconstructContext *context= MEM_callocN(sizeof(MovieReconstructContext), "MovieReconstructContext data");
1581         MovieTrackingCamera *camera= &tracking->camera;
1582         float aspy= 1.0f/tracking->camera.pixel_aspect;
1583         int num_tracks= BLI_countlist(&tracking->tracks);
1584         int sfra= INT_MAX, efra= INT_MIN;
1585         MovieTrackingTrack *track;
1586
1587         context->tracks_map= tracks_map_new(num_tracks, 0);
1588         track= tracking->tracks.first;
1589         while(track) {
1590                 int first= 0, last= track->markersnr;
1591                 MovieTrackingMarker *first_marker= &track->markers[0];
1592                 MovieTrackingMarker *last_marker= &track->markers[track->markersnr-1];
1593
1594                 /* find first not-disabled marker */
1595                 while(first<track->markersnr-1 && first_marker->flag&MARKER_DISABLED) {
1596                         first++;
1597                         first_marker++;
1598                 }
1599
1600                 /* find last not-disabled marker */
1601                 while(last>=0 && last_marker->flag&MARKER_DISABLED) {
1602                         last--;
1603                         last_marker--;
1604                 }
1605
1606                 if(first<track->markersnr-1)
1607                         sfra= MIN2(sfra, first_marker->framenr);
1608
1609                 if(last>=0)
1610                         efra= MAX2(efra, last_marker->framenr);
1611
1612                 tracks_map_insert(context->tracks_map, track, NULL);
1613
1614                 track= track->next;
1615         }
1616
1617         context->sfra= sfra;
1618         context->efra= efra;
1619
1620 #ifdef WITH_LIBMV
1621         context->tracks= create_libmv_tracks(tracking, width, height*aspy);
1622         context->keyframe1= keyframe1;
1623         context->keyframe2= keyframe2;
1624         context->refine_flags= get_refine_intrinsics_flags(tracking);
1625 #else
1626         (void) width;
1627         (void) height;
1628         (void) keyframe1;
1629         (void) keyframe2;
1630 #endif
1631
1632         context->focal_length= camera->focal;
1633         context->principal_point[0]= camera->principal[0];
1634         context->principal_point[1]= camera->principal[1]*aspy;
1635
1636         context->k1= camera->k1;
1637         context->k2= camera->k2;
1638         context->k2= camera->k2;
1639
1640         return context;
1641 }
1642
1643 void BKE_tracking_reconstruction_context_free(MovieReconstructContext *context)
1644 {
1645 #ifdef WITH_LIBMV
1646         if(context->reconstruction)
1647                         libmv_destroyReconstruction(context->reconstruction);
1648
1649         libmv_tracksDestroy(context->tracks);
1650 #endif
1651
1652         tracks_map_free(context->tracks_map, NULL);
1653
1654         MEM_freeN(context);
1655 }
1656
1657 #ifdef WITH_LIBMV
1658 static void solve_reconstruction_update_cb(void *customdata, double progress, const char *message)
1659 {
1660         ReconstructProgressData *progressdata= customdata;
1661
1662         if(progressdata->progress) {
1663                 *progressdata->progress= progress;
1664                 *progressdata->do_update= 1;
1665         }
1666
1667         BLI_snprintf(progressdata->stats_message, progressdata->message_size,
1668                         "Solving camera | %s", message);
1669 }
1670 #endif
1671
1672 #if 0
1673 static int solve_reconstruction_testbreak_cb(void *customdata)
1674 {
1675         ReconstructProgressData *progressdata= customdata;
1676
1677         if(progressdata->stop && *progressdata->stop)
1678                 return 1;
1679
1680         return G.afbreek;
1681 }
1682 #endif
1683
1684 void BKE_tracking_solve_reconstruction(MovieReconstructContext *context, short *stop,
1685                         short *do_update, float *progress, char *stats_message, int message_size)
1686 {
1687 #ifdef WITH_LIBMV
1688         float error;
1689
1690         ReconstructProgressData progressdata;
1691
1692         progressdata.stop= stop;
1693         progressdata.do_update= do_update;
1694         progressdata.progress= progress;
1695         progressdata.stats_message= stats_message;
1696         progressdata.message_size= message_size;
1697
1698         context->reconstruction = libmv_solveReconstruction(context->tracks,
1699                 context->keyframe1, context->keyframe2,
1700                 context->refine_flags,
1701                 context->focal_length,
1702                 context->principal_point[0], context->principal_point[1],
1703                 context->k1, context->k2, context->k3,
1704                 solve_reconstruction_update_cb, &progressdata);
1705
1706         error= libmv_reprojectionError(context->reconstruction);
1707
1708         context->reprojection_error= error;
1709 #else
1710         (void) context;
1711         (void) stop;
1712         (void) do_update;
1713         (void) progress;
1714         (void) stats_message;
1715         (void) message_size;
1716 #endif
1717 }
1718
1719 int BKE_tracking_finish_reconstruction(MovieReconstructContext *context, MovieTracking *tracking)
1720 {
1721         tracking->reconstruction.error= context->reprojection_error;
1722         tracking->reconstruction.flag|= TRACKING_RECONSTRUCTED;
1723
1724 #ifdef WITH_LIBMV
1725         if(!retrieve_libmv_reconstruct(context, tracking))
1726                 return 0;
1727 #endif
1728
1729         return 1;
1730 }
1731
1732 void BKE_track_unique_name(MovieTracking *tracking, MovieTrackingTrack *track)
1733 {
1734         BLI_uniquename(&tracking->tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
1735 }
1736
1737 MovieTrackingTrack *BKE_tracking_named_track(MovieTracking *tracking, const char *name)
1738 {
1739         MovieTrackingTrack *track= tracking->tracks.first;
1740
1741         while(track) {
1742                 if(!strcmp(track->name, name))
1743                         return track;
1744
1745                 track= track->next;
1746         }
1747
1748         return NULL;
1749 }
1750
1751 static int reconstruction_camera_index(MovieTracking *tracking, int framenr, int nearest)
1752 {
1753         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1754         MovieReconstructedCamera *cameras= reconstruction->cameras;
1755         int a= 0, d= 1;
1756
1757         if(!reconstruction->camnr)
1758                 return -1;
1759
1760         if(framenr<cameras[0].framenr) {
1761                 if(nearest) return 0;
1762                 else return -1;
1763         }
1764
1765         if(framenr>cameras[reconstruction->camnr-1].framenr) {
1766                 if(nearest) return reconstruction->camnr-1;
1767                 else return -1;
1768         }
1769
1770         if(reconstruction->last_camera<reconstruction->camnr)
1771                 a= reconstruction->last_camera;
1772
1773         if(cameras[a].framenr>=framenr)
1774                 d= -1;
1775
1776         while(a>=0 && a<reconstruction->camnr) {
1777                 int cfra= cameras[a].framenr;
1778
1779                 /* check if needed framenr was "skipped" -- no data for requested frame */
1780
1781                 if(d>0 && cfra>framenr) {
1782                         /* interpolate with previous position */
1783                         if(nearest) return a-1;
1784                         else break;
1785                 }
1786
1787                 if(d<0 && cfra<framenr) {
1788                         /* interpolate with next position */
1789                         if(nearest) return a;
1790                         else break;
1791                 }
1792
1793                 if(cfra==framenr) {
1794                         reconstruction->last_camera= a;
1795
1796                         return a;
1797                 }
1798
1799                 a+= d;
1800         }
1801
1802         return -1;
1803 }
1804
1805 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking, int framenr)
1806 {
1807         int a= reconstruction_camera_index(tracking, framenr, 0);
1808
1809         if(a==-1)
1810                 return NULL;
1811
1812         return &tracking->reconstruction.cameras[a];
1813 }
1814
1815 void BKE_tracking_get_interpolated_camera(MovieTracking *tracking, int framenr, float mat[4][4])
1816 {
1817         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1818         MovieReconstructedCamera *cameras= reconstruction->cameras;
1819         int a= reconstruction_camera_index(tracking, framenr, 1);
1820
1821         if(a==-1) {
1822                 unit_m4(mat);
1823                 return;
1824         }
1825
1826         if(cameras[a].framenr!=framenr && a>0 && a<reconstruction->camnr-1) {
1827                 float t= ((float)framenr-cameras[a].framenr) / (cameras[a+1].framenr-cameras[a].framenr);
1828
1829                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a+1].mat, t);
1830         } else {
1831                 copy_m4_m4(mat, cameras[a].mat);
1832         }
1833 }
1834
1835 void BKE_get_tracking_mat(Scene *scene, Object *ob, float mat[4][4])
1836 {
1837         if(!ob) {
1838                 if(scene->camera) ob= scene->camera;
1839                 else ob= scene_find_camera(scene);
1840         }
1841
1842         if(ob)
1843                 where_is_object_mat(scene, ob, mat);
1844         else
1845                 unit_m4(mat);
1846 }
1847
1848 void BKE_tracking_camera_shift(MovieTracking *tracking, int winx, int winy, float *shiftx, float *shifty)
1849 {
1850         *shiftx= (0.5f*winx-tracking->camera.principal[0]) / winx;
1851         *shifty= (0.5f*winy-tracking->camera.principal[1]) / winx;
1852 }
1853
1854 void BKE_tracking_camera_to_blender(MovieTracking *tracking, Scene *scene, Camera *camera, int width, int height)
1855 {
1856         float focal= tracking->camera.focal;
1857
1858         camera->sensor_x= tracking->camera.sensor_width;
1859         camera->sensor_fit= CAMERA_SENSOR_FIT_AUTO;
1860         camera->lens= focal*camera->sensor_x/width;
1861
1862         scene->r.xsch= width*tracking->camera.pixel_aspect;
1863         scene->r.ysch= height;
1864
1865         scene->r.xasp= 1.0f;
1866         scene->r.yasp= 1.0f;
1867
1868         BKE_tracking_camera_shift(tracking, width, height, &camera->shiftx, &camera->shifty);
1869 }
1870
1871 void BKE_tracking_projection_matrix(MovieTracking *tracking, int framenr, int winx, int winy, float mat[4][4])
1872 {
1873         MovieReconstructedCamera *camera;
1874         float lens= tracking->camera.focal*tracking->camera.sensor_width/(float)winx;
1875         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
1876         float winmat[4][4];
1877         float ycor= 1.0f/tracking->camera.pixel_aspect;
1878         float shiftx, shifty, winside= MAX2(winx, winy);
1879
1880         BKE_tracking_camera_shift(tracking, winx, winy, &shiftx, &shifty);
1881
1882         clipsta= 0.1f;
1883         clipend= 1000.0f;
1884
1885         if(winx >= winy)
1886                 viewfac= (lens*winx)/tracking->camera.sensor_width;
1887         else
1888                 viewfac= (ycor*lens*winy)/tracking->camera.sensor_width;
1889
1890         pixsize= clipsta/viewfac;
1891
1892         left= -0.5f*(float)winx + shiftx*winside;
1893         bottom= -0.5f*(ycor)*(float)winy + shifty*winside;
1894         right=  0.5f*(float)winx + shiftx*winside;
1895         top=  0.5f*(ycor)*(float)winy + shifty*winside;
1896
1897         left *= pixsize;
1898         right *= pixsize;
1899         bottom *= pixsize;
1900         top *= pixsize;
1901
1902         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
1903
1904         camera= BKE_tracking_get_reconstructed_camera(tracking, framenr);
1905         if(camera) {
1906                 float imat[4][4];
1907
1908                 invert_m4_m4(imat, camera->mat);
1909                 mul_m4_m4m4(mat, imat, winmat);
1910         } else copy_m4_m4(mat, winmat);
1911 }
1912
1913 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
1914 {
1915         MovieTrackingCamera *camera= &tracking->camera;
1916
1917 #ifdef WITH_LIBMV
1918         double x, y;
1919         float aspy= 1.0f/tracking->camera.pixel_aspect;
1920
1921         /* normalize coords */
1922         x= (co[0]-camera->principal[0]) / camera->focal;
1923         y= (co[1]-camera->principal[1] * aspy) / camera->focal;
1924
1925         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
1926                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
1927
1928         /* result is in image coords already */
1929         nco[0]= x;
1930         nco[1]= y;
1931 #else
1932         (void)camera;
1933         (void)co;
1934         (void)nco;
1935 #endif
1936 }
1937
1938 void BKE_tracking_invert_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
1939 {
1940         MovieTrackingCamera *camera= &tracking->camera;
1941
1942 #ifdef WITH_LIBMV
1943         double x= co[0], y= co[1];
1944         float aspy= 1.0f/tracking->camera.pixel_aspect;
1945
1946         libmv_InvertIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
1947                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
1948
1949         nco[0]= x * camera->focal + camera->principal[0];
1950         nco[1]= y * camera->focal + camera->principal[1] * aspy;
1951 #else
1952         (void)camera;
1953         (void)co;
1954         (void)nco;
1955 #endif
1956 }
1957
1958 #ifdef WITH_LIBMV
1959 static int point_in_stroke(bGPDstroke *stroke, float x, float y)
1960 {
1961         int i, prev;
1962         int count= 0;
1963         bGPDspoint *points= stroke->points;
1964
1965         prev= stroke->totpoints-1;
1966
1967         for(i= 0; i<stroke->totpoints; i++) {
1968                 if((points[i].y<y && points[prev].y>=y) || (points[prev].y<y && points[i].y>=y)) {
1969                         float fac= (y-points[i].y)/(points[prev].y-points[i].y);
1970
1971                         if (points[i].x+fac*(points[prev].x-points[i].x)<x)
1972                                 count++;
1973                 }
1974
1975                 prev= i;
1976         }
1977
1978         return count%2;
1979 }
1980
1981 static int point_in_layer(bGPDlayer *layer, float x, float y)
1982 {
1983         bGPDframe *frame= layer->frames.first;
1984
1985         while(frame) {
1986                 bGPDstroke *stroke= frame->strokes.first;
1987                 while(stroke) {
1988                         if(point_in_stroke(stroke, x, y))
1989                                 return 1;
1990
1991                         stroke= stroke->next;
1992                 }
1993                 frame= frame->next;
1994         }
1995
1996         return 0;
1997 }
1998
1999 static void retrieve_libmv_features(MovieTracking *tracking, struct libmv_Features *features,
2000                         int framenr, int width, int height, bGPDlayer *layer, int place_outside_layer)
2001 {
2002         int a;
2003
2004         a= libmv_countFeatures(features);
2005         while(a--) {
2006                 MovieTrackingTrack *track;
2007                 double x, y, size, score;
2008                 int ok= 1;
2009                 float xu, yu;
2010
2011                 libmv_getFeature(features, a, &x, &y, &score, &size);
2012
2013                 xu= x/width;
2014                 yu= y/height;
2015
2016                 if(layer)
2017                         ok= point_in_layer(layer, xu, yu)!=place_outside_layer;
2018
2019                 if(ok) {
2020                         track= BKE_tracking_add_track(tracking, xu, yu, framenr, width, height);
2021                         track->flag|= SELECT;
2022                         track->pat_flag|= SELECT;
2023                         track->search_flag|= SELECT;
2024                 }
2025         }
2026 }
2027 #endif
2028
2029 void BKE_tracking_detect_fast(MovieTracking *tracking, ImBuf *ibuf,
2030                         int framenr, int margin, int min_trackness, int min_distance, bGPDlayer *layer,
2031                         int place_outside_layer)
2032 {
2033 #ifdef WITH_LIBMV
2034         struct libmv_Features *features;
2035         unsigned char *pixels= get_ucharbuf(ibuf);
2036
2037         features= libmv_detectFeaturesFAST(pixels, ibuf->x, ibuf->y, ibuf->x, margin, min_trackness, min_distance);
2038
2039         MEM_freeN(pixels);
2040
2041         retrieve_libmv_features(tracking, features, framenr, ibuf->x, ibuf->y, layer, place_outside_layer);
2042
2043         libmv_destroyFeatures(features);
2044 #else
2045         (void)tracking;
2046         (void)ibuf;
2047         (void)framenr;
2048         (void)margin;
2049         (void)min_trackness;
2050         (void)min_distance;
2051         (void)layer;
2052         (void)place_outside_layer;
2053 #endif
2054 }
2055
2056 MovieTrackingTrack *BKE_tracking_indexed_track(MovieTracking *tracking, int tracknr)
2057 {
2058         MovieTrackingTrack *track= tracking->tracks.first;
2059         int cur= 1;
2060
2061         while(track) {
2062                 if(track->flag&TRACK_HAS_BUNDLE) {
2063                         if(cur==tracknr)
2064                                 return track;
2065
2066                         cur++;
2067                 }
2068
2069                 track= track->next;
2070         }
2071
2072         return NULL;
2073 }
2074
2075 static int stabilization_median_point(MovieTracking *tracking, int framenr, float median[2])
2076 {
2077         int ok= 0;
2078         float min[2], max[2];
2079         MovieTrackingTrack *track;
2080
2081         INIT_MINMAX2(min, max);
2082
2083         track= tracking->tracks.first;
2084         while(track) {
2085                 if(track->flag&TRACK_USE_2D_STAB) {
2086                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
2087
2088                         DO_MINMAX2(marker->pos, min, max);
2089
2090                         ok= 1;
2091                 }
2092
2093                 track= track->next;
2094         }
2095
2096         median[0]= (max[0]+min[0])/2.0f;
2097         median[1]= (max[1]+min[1])/2.0f;
2098
2099         return ok;
2100 }
2101
2102 static void calculate_stabdata(MovieTracking *tracking, int framenr, float width, float height,
2103                         float firstmedian[2], float median[2], float loc[2], float *scale, float *angle)
2104 {
2105         MovieTrackingStabilization *stab= &tracking->stabilization;
2106
2107         *scale= (stab->scale-1.0f)*stab->scaleinf+1.0f;
2108         *angle= 0.0f;
2109
2110         loc[0]= (firstmedian[0]-median[0])*width*(*scale);
2111         loc[1]= (firstmedian[1]-median[1])*height*(*scale);
2112
2113         mul_v2_fl(loc, stab->locinf);
2114
2115         if((stab->flag&TRACKING_STABILIZE_ROTATION) && stab->rot_track && stab->rotinf) {
2116                 MovieTrackingMarker *marker;
2117                 float a[2], b[2];
2118                 float x0= (float)width/2.0f, y0= (float)height/2.0f;
2119                 float x= median[0]*width, y= median[1]*height;
2120
2121                 marker= BKE_tracking_get_marker(stab->rot_track, 1);
2122                 sub_v2_v2v2(a, marker->pos, firstmedian);
2123                 a[0]*= width;
2124                 a[1]*= height;
2125
2126                 marker= BKE_tracking_get_marker(stab->rot_track, framenr);
2127                 sub_v2_v2v2(b, marker->pos, median);
2128                 b[0]*= width;
2129                 b[1]*= height;
2130
2131                 *angle= -atan2(a[0]*b[1]-a[1]*b[0], a[0]*b[0]+a[1]*b[1]);
2132                 *angle*= stab->rotinf;
2133
2134                 /* convert to rotation around image center */
2135                 loc[0]-= (x0 + (x-x0)*cosf(*angle)-(y-y0)*sinf(*angle) - x)*(*scale);
2136                 loc[1]-= (y0 + (x-x0)*sinf(*angle)+(y-y0)*cosf(*angle) - y)*(*scale);
2137         }
2138 }
2139
2140 static float stabilization_auto_scale_factor(MovieTracking *tracking, int width, int height)
2141 {
2142         float firstmedian[2];
2143         MovieTrackingStabilization *stab= &tracking->stabilization;
2144
2145         if(stab->ok)
2146                 return stab->scale;
2147
2148         if(stabilization_median_point(tracking, 1, firstmedian)) {
2149                 int sfra= INT_MAX, efra= INT_MIN, cfra;
2150                 float delta[2]= {0.0f, 0.0f}, scalex= 1.0f, scaley= 1.0f;
2151                 MovieTrackingTrack *track;
2152
2153                 stab->scale= 1.0f;
2154
2155                 track= tracking->tracks.first;
2156                 while(track) {
2157                         if(track->flag&TRACK_USE_2D_STAB ||
2158                            ((stab->flag&TRACKING_STABILIZE_ROTATION) && track==stab->rot_track)) {
2159                                 sfra= MIN2(sfra, track->markers[0].framenr);
2160                                 efra= MAX2(efra, track->markers[track->markersnr-1].framenr);
2161                         }
2162
2163                         track= track->next;
2164                 }
2165
2166                 for(cfra=sfra; cfra<=efra; cfra++) {
2167                         float median[2], near[2];
2168                         float loc[2], scale, angle;
2169
2170                         stabilization_median_point(tracking, cfra, median);
2171
2172                         calculate_stabdata(tracking, cfra, width, height, firstmedian, median,
2173                                                 loc, &scale, &angle);
2174
2175                         if(angle==0.0f) {
2176                                 loc[0]= fabsf(loc[0]);
2177                                 loc[1]= fabsf(loc[1]);
2178
2179                                 delta[0]= MAX2(delta[0], loc[0]);
2180                                 delta[1]= MAX2(delta[1], loc[1]);
2181
2182                                 near[0]= MIN2(median[0], 1.0f-median[0]);
2183                                 near[1]= MIN2(median[1], 1.0f-median[1]);
2184                                 near[0]= MAX2(near[0], 0.05f);
2185                                 near[1]= MAX2(near[1], 0.05f);
2186
2187                                 scalex= 1.0f+delta[0]/(near[0]*width);
2188                                 scaley= 1.0f+delta[1]/(near[1]*height);
2189                         } else {
2190                                 int i;
2191                                 float mat[4][4];
2192                                 float points[4][2]={{0.0f, 0.0f}, {0.0f, height}, {width, height}, {width, 0.0f}};
2193
2194                                 BKE_tracking_stabdata_to_mat4(width, height, loc, scale, angle, mat);
2195
2196                                 for(i= 0; i<4; i++) {
2197                                         int j;
2198                                         float a[3]= {0.0f, 0.0f, 0.0f}, b[3]= {0.0f, 0.0f, 0.0f};
2199
2200                                         copy_v3_v3(a, points[i]);
2201                                         copy_v3_v3(b, points[(i+1)%4]);
2202
2203                                         mul_m4_v3(mat, a);
2204                                         mul_m4_v3(mat, b);
2205
2206                                         for(j= 0; j<4; j++) {
2207                                                 float point[3]= {points[j][0], points[j][1], 0.0f};
2208                                                 float v1[3], v2[3];
2209
2210                                                 sub_v3_v3v3(v1, b, a);
2211                                                 sub_v3_v3v3(v2, point, a);
2212
2213                                                 if(cross_v2v2(v1, v2) >= 0.0f) {
2214                                                         float dist= dist_to_line_v2(point, a, b);
2215                                                         if(i%2==0) {
2216                                                                 scalex= MAX2(scalex, (width+2*dist)/width);
2217                                                         } else {
2218                                                                 scaley= MAX2(scaley, (height+2*dist)/height);
2219                                                         }
2220                                                 }
2221                                         }
2222                                 }
2223                         }
2224                 }
2225
2226                 stab->scale= MAX2(scalex, scaley);
2227
2228                 if(stab->maxscale>0.0f)
2229                         stab->scale= MIN2(stab->scale, stab->maxscale);
2230         } else {
2231                 stab->scale= 1.0f;
2232         }
2233
2234         stab->ok= 1;
2235
2236         return stab->scale;
2237 }
2238
2239 static ImBuf* stabilize_alloc_ibuf(ImBuf *cacheibuf, ImBuf *srcibuf, int fill)
2240 {
2241         int flags;
2242
2243         if(cacheibuf && (cacheibuf->x != srcibuf->x || cacheibuf->y != srcibuf->y)) {
2244                 IMB_freeImBuf(cacheibuf);
2245                 cacheibuf= NULL;
2246         }
2247
2248         flags= IB_rect;
2249
2250         if(srcibuf->rect_float)
2251                 flags|= IB_rectfloat;
2252
2253         if(cacheibuf) {
2254                 if(fill) {
2255                         float col[4]= {0.0f, 0.0f, 0.0f, 0.0f};
2256                         IMB_rectfill(cacheibuf, col);
2257                 }
2258         }
2259         else {
2260                 cacheibuf= IMB_allocImBuf(srcibuf->x, srcibuf->y, srcibuf->planes, flags);
2261                 cacheibuf->profile= srcibuf->profile;
2262         }
2263
2264         return cacheibuf;
2265 }
2266
2267 void BKE_tracking_stabilization_data(MovieTracking *tracking, int framenr, int width, int height, float loc[2], float *scale, float *angle)
2268 {
2269         float firstmedian[2], median[2];
2270         MovieTrackingStabilization *stab= &tracking->stabilization;
2271
2272         if((stab->flag&TRACKING_2D_STABILIZATION)==0) {
2273                 zero_v2(loc);
2274                 *scale= 1.0f;
2275                 *angle= 0.0f;
2276
2277                 return;
2278         }
2279
2280         if(stabilization_median_point(tracking, 1, firstmedian)) {
2281                 stabilization_median_point(tracking, framenr, median);
2282
2283                 if((stab->flag&TRACKING_AUTOSCALE)==0)
2284                         stab->scale= 1.0f;
2285
2286                 if(!stab->ok) {
2287                         if(stab->flag&TRACKING_AUTOSCALE)
2288                                 stabilization_auto_scale_factor(tracking, width, height);
2289
2290                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2291
2292                         stab->ok= 1;
2293                 } else {
2294                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2295                 }
2296         } else {
2297                 zero_v2(loc);
2298                 *scale= 1.0f;
2299                 *angle= 0.0f;
2300         }
2301 }
2302
2303 ImBuf *BKE_tracking_stabilize(MovieTracking *tracking, int framenr, ImBuf *ibuf, float loc[2], float *scale, float *angle)
2304 {
2305         float tloc[2], tscale, tangle;
2306         MovieTrackingStabilization *stab= &tracking->stabilization;
2307         ImBuf *tmpibuf;
2308         float width= ibuf->x, height= ibuf->y;
2309
2310         if(loc)         copy_v2_v2(tloc, loc);
2311         if(scale)       tscale= *scale;
2312
2313         if((stab->flag&TRACKING_2D_STABILIZATION)==0) {
2314                 if(loc)         zero_v2(loc);
2315                 if(scale)       *scale= 1.0f;
2316
2317                 return ibuf;
2318         }
2319
2320         BKE_tracking_stabilization_data(tracking, framenr, width, height, tloc, &tscale, &tangle);
2321
2322         tmpibuf= stabilize_alloc_ibuf(NULL, ibuf, 1);
2323
2324         /* scale would be handled by matrix transformation when angle is non-zero */
2325         if(tscale!=1.0f && tangle==0.0f) {
2326                 ImBuf *scaleibuf;
2327
2328                 stabilization_auto_scale_factor(tracking, width, height);
2329
2330                 scaleibuf= stabilize_alloc_ibuf(stab->scaleibuf, ibuf, 0);
2331                 stab->scaleibuf= scaleibuf;
2332
2333                 IMB_rectcpy(scaleibuf, ibuf, 0, 0, 0, 0, ibuf->x, ibuf->y);
2334                 IMB_scalefastImBuf(scaleibuf, ibuf->x*tscale, ibuf->y*tscale);
2335
2336                 ibuf= scaleibuf;
2337         }
2338
2339         if(tangle==0.0f) {
2340                 /* if angle is zero, then it's much faster to use rect copy
2341                    but could be issues with subpixel precisions */
2342                 IMB_rectcpy(tmpibuf, ibuf, tloc[0]-(tscale-1.0f)*width/2.0f, tloc[1]-(tscale-1.0f)*height/2.0f, 0, 0, ibuf->x, ibuf->y);
2343         } else {
2344                 float mat[4][4];
2345                 int i, j;
2346
2347                 BKE_tracking_stabdata_to_mat4(ibuf->x, ibuf->y, tloc, tscale, tangle, mat);
2348                 invert_m4(mat);
2349
2350                 for(j=0; j<tmpibuf->y; j++) {
2351                         for(i=0; i<tmpibuf->x;i++) {
2352                                 float vec[3]= {i, j, 0};
2353
2354                                 mul_v3_m4v3(vec, mat, vec);
2355
2356                                 /* TODO: add selector for interpolation method */
2357                                 neareast_interpolation(ibuf, tmpibuf, vec[0], vec[1], i, j);
2358                         }
2359                 }
2360         }
2361
2362         tmpibuf->userflags|= IB_MIPMAP_INVALID;
2363
2364         if(tmpibuf->rect_float)
2365                 tmpibuf->userflags|= IB_RECT_INVALID;
2366
2367         if(loc)         copy_v2_v2(loc, tloc);
2368         if(scale)       *scale= tscale;
2369         if(angle)       *angle= tangle;
2370
2371         return tmpibuf;
2372 }
2373
2374 void BKE_tracking_stabdata_to_mat4(int width, int height, float loc[2], float scale, float angle, float mat[4][4])
2375 {
2376         float lmat[4][4], rmat[4][4], smat[4][4], cmat[4][4], icmat[4][4];
2377         float svec[3]= {scale, scale, scale};
2378
2379         unit_m4(rmat);
2380         unit_m4(lmat);
2381         unit_m4(smat);
2382         unit_m4(cmat);
2383
2384         /* image center as rotation center */
2385         cmat[3][0]= (float)width/2.0f;
2386         cmat[3][1]= (float)height/2.0f;
2387         invert_m4_m4(icmat, cmat);
2388
2389         size_to_mat4(smat, svec);               /* scale matrix */
2390         add_v2_v2(lmat[3], loc);                /* tranlation matrix */
2391         rotate_m4(rmat, 'Z', angle);    /* rotation matrix */
2392
2393         /* compose transformation matrix */
2394         mul_serie_m4(mat, lmat, cmat, rmat, smat, icmat, NULL, NULL, NULL);
2395 }
2396
2397 MovieDistortion *BKE_tracking_distortion_create(void)
2398 {
2399         MovieDistortion *distortion;
2400
2401         distortion= MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2402
2403         return distortion;
2404 }
2405
2406 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
2407 {
2408         MovieDistortion *new_distortion;
2409
2410         new_distortion= MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2411
2412 #ifdef WITH_LIBMV
2413         new_distortion->intrinsics= libmv_CameraIntrinsicsCopy(distortion->intrinsics);
2414 #else
2415         (void)distortion;
2416 #endif
2417
2418         return new_distortion;
2419 }
2420
2421 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking, int width, int height)
2422 {
2423         MovieTrackingCamera *camera= &tracking->camera;
2424         float aspy= 1.0f/tracking->camera.pixel_aspect;
2425
2426 #ifdef WITH_LIBMV
2427         if(!distortion->intrinsics) {
2428                 distortion->intrinsics= libmv_CameraIntrinsicsNew(camera->focal,
2429                                 camera->principal[0], camera->principal[1] * aspy,
2430                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2431         } else {
2432                 libmv_CameraIntrinsicsUpdate(distortion->intrinsics, camera->focal,
2433                                 camera->principal[0], camera->principal[1] * aspy,
2434                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2435         }
2436 #else
2437         (void)distortion;
2438         (void)width;
2439         (void)height;
2440         (void)camera;
2441         (void)aspy;
2442 #endif
2443 }
2444
2445 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking,
2446                         ImBuf *ibuf, int width, int height, float overscan, int undistort)
2447 {
2448         ImBuf *resibuf;
2449
2450         BKE_tracking_distortion_update(distortion, tracking, width, height);
2451
2452         resibuf= IMB_dupImBuf(ibuf);
2453
2454         if(ibuf->rect_float) {
2455 #ifdef WITH_LIBMV
2456                 if(undistort) {
2457                         libmv_CameraIntrinsicsUndistortFloat(distortion->intrinsics,
2458                                                 ibuf->rect_float, resibuf->rect_float,
2459                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2460                 } else {
2461                         libmv_CameraIntrinsicsDistortFloat(distortion->intrinsics,
2462                                                 ibuf->rect_float, resibuf->rect_float,
2463                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2464                 }
2465 #endif
2466
2467                 ibuf->userflags|= IB_RECT_INVALID;
2468         } else {
2469 #ifdef WITH_LIBMV
2470                 if(undistort) {
2471                                 libmv_CameraIntrinsicsUndistortByte(distortion->intrinsics,
2472                                                         (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2473                                                         ibuf->x, ibuf->y, overscan, ibuf->channels);
2474                 } else {
2475                         libmv_CameraIntrinsicsDistortByte(distortion->intrinsics,
2476                                                 (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2477                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2478                 }
2479 #endif
2480         }
2481
2482 #ifndef WITH_LIBMV
2483         (void)overscan;
2484         (void)undistort;
2485 #endif
2486
2487         return resibuf;
2488 }
2489
2490 void BKE_tracking_distortion_destroy(MovieDistortion *distortion)
2491 {
2492 #ifdef WITH_LIBMV
2493         libmv_CameraIntrinsicsDestroy(distortion->intrinsics);
2494 #endif
2495
2496         MEM_freeN(distortion);
2497 }
2498
2499 ImBuf *BKE_tracking_undistort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2500 {
2501         MovieTrackingCamera *camera= &tracking->camera;
2502
2503         if(camera->intrinsics == NULL)
2504                 camera->intrinsics= BKE_tracking_distortion_create();
2505
2506         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 1);
2507 }
2508
2509 ImBuf *BKE_tracking_distort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2510 {
2511         MovieTrackingCamera *camera= &tracking->camera;
2512
2513         if(camera->intrinsics == NULL)
2514                 camera->intrinsics= BKE_tracking_distortion_create();
2515
2516         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 0);
2517 }
2518
2519 /* area - which part of marker should be selected. see TRACK_AREA_* constants */
2520 void BKE_tracking_select_track(MovieTracking *tracking, MovieTrackingTrack *track, int area, int extend)
2521 {
2522         if(extend) {
2523                 BKE_tracking_track_flag(track, area, SELECT, 0);
2524         } else {
2525                 MovieTrackingTrack *cur= tracking->tracks.first;
2526
2527                 while(cur) {
2528                         if(cur==track) {
2529                                 BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2530                                 BKE_tracking_track_flag(cur, area, SELECT, 0);
2531                         }
2532                         else {
2533                                 BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2534                         }
2535
2536                         cur= cur->next;
2537                 }
2538         }
2539 }
2540
2541 void BKE_tracking_deselect_track(MovieTrackingTrack *track, int area)
2542 {
2543         BKE_tracking_track_flag(track, area, SELECT, 1);
2544 }