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