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