Camera tracking: code cleanup
[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= BKE_tracking_get_marker(track, marker->framenr);
235
236         if(old_marker && old_marker->framenr==marker->framenr) {
237                 *old_marker= *marker;
238         } else {
239                 int a= track->markersnr;
240
241                 while(a--) {
242                         if(track->markers[a].framenr<marker->framenr)
243                                 break;
244                 }
245
246                 track->markersnr++;
247
248                 if(track->markers) track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
249                 else track->markers= MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
250
251                 memmove(track->markers+a+2, track->markers+a+1, (track->markersnr-a-2)*sizeof(MovieTrackingMarker));
252                 track->markers[a+1]= *marker;
253
254                 track->last_marker= a+1;
255         }
256 }
257
258 void BKE_tracking_delete_marker(MovieTrackingTrack *track, int framenr)
259 {
260         int a= 0;
261
262         while(a<track->markersnr) {
263                 if(track->markers[a].framenr==framenr) {
264                         if(track->markersnr>1) {
265                                 memmove(track->markers+a, track->markers+a+1, (track->markersnr-a-1)*sizeof(MovieTrackingMarker));
266                                 track->markersnr--;
267                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
268                         } else {
269                                 MEM_freeN(track->markers);
270                                 track->markers= NULL;
271                                 track->markersnr= 0;
272                         }
273
274                         break;
275                 }
276
277                 a++;
278         }
279 }
280
281 MovieTrackingMarker *BKE_tracking_get_marker(MovieTrackingTrack *track, int framenr)
282 {
283         int a= track->markersnr-1;
284
285         if(!track->markersnr)
286                 return NULL;
287
288         /* approximate pre-first framenr marker with first marker */
289         if(framenr<track->markers[0].framenr)
290                 return &track->markers[0];
291
292         if(track->last_marker<track->markersnr)
293                 a= track->last_marker;
294
295         if(track->markers[a].framenr<=framenr) {
296                 while(a<track->markersnr && track->markers[a].framenr<=framenr) {
297                         if(track->markers[a].framenr==framenr) {
298                                 track->last_marker= a;
299                                 return &track->markers[a];
300                         }
301                         a++;
302                 }
303
304                 /* if there's no marker for exact position, use nearest marker from left side */
305                 return &track->markers[a-1];
306         } else {
307                 while(a>=0 && track->markers[a].framenr>=framenr) {
308                         if(track->markers[a].framenr==framenr) {
309                                 track->last_marker= a;
310                                 return &track->markers[a];
311                         }
312
313                         a--;
314                 }
315
316                 /* if there's no marker for exact position, use nearest marker from left side */
317                 return &track->markers[a];
318         }
319
320         return NULL;
321 }
322
323 MovieTrackingMarker *BKE_tracking_ensure_marker(MovieTrackingTrack *track, int framenr)
324 {
325         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
326
327         if(marker && marker->framenr!=framenr) {
328                 MovieTrackingMarker marker_new;
329
330                 marker_new= *marker;
331                 marker_new.framenr= framenr;
332
333                 BKE_tracking_insert_marker(track, &marker_new);
334                 marker= BKE_tracking_get_marker(track, framenr);
335         }
336
337         return marker;
338 }
339
340 MovieTrackingMarker *BKE_tracking_exact_marker(MovieTrackingTrack *track, int framenr)
341 {
342         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
343
344         if(marker && marker->framenr!=framenr)
345                 return NULL;
346
347         return marker;
348 }
349
350 int BKE_tracking_has_marker(MovieTrackingTrack *track, int framenr)
351 {
352         return BKE_tracking_exact_marker(track, framenr) != 0;
353 }
354
355 void BKE_tracking_free_track(MovieTrackingTrack *track)
356 {
357         if(track->markers) MEM_freeN(track->markers);
358 }
359
360 MovieTrackingTrack *BKE_tracking_copy_track(MovieTrackingTrack *track)
361 {
362         MovieTrackingTrack *new_track= MEM_dupallocN(track);
363
364         new_track->next= new_track->prev= NULL;
365
366         if(new_track->markers)
367                 new_track->markers= MEM_dupallocN(new_track->markers);
368
369         return new_track;
370 }
371
372 static void put_disabled_marker(MovieTrackingTrack *track, MovieTrackingMarker *ref_marker, int before, int overwrite)
373 {
374         MovieTrackingMarker marker_new;
375
376         marker_new= *ref_marker;
377         marker_new.flag&= ~MARKER_TRACKED;
378         marker_new.flag|= MARKER_DISABLED;
379
380         if(before) marker_new.framenr--;
381         else marker_new.framenr++;
382
383         if(!BKE_tracking_has_marker(track, marker_new.framenr) || overwrite)
384                 BKE_tracking_insert_marker(track, &marker_new);
385 }
386
387 void BKE_tracking_clear_path(MovieTrackingTrack *track, int ref_frame, int action)
388 {
389         int a;
390
391         if(action==TRACK_CLEAR_REMAINED) {
392                 a= 1;
393                 while(a<track->markersnr) {
394                         if(track->markers[a].framenr>ref_frame) {
395                                 track->markersnr= a;
396                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
397
398                                 break;
399                         }
400
401                         a++;
402                 }
403
404                 if(track->markersnr)
405                         put_disabled_marker(track, &track->markers[track->markersnr-1], 0, 1);
406         } else if(action==TRACK_CLEAR_UPTO) {
407                 a= track->markersnr-1;
408                 while(a>=0) {
409                         if(track->markers[a].framenr<=ref_frame) {
410                                 memmove(track->markers, track->markers+a, (track->markersnr-a)*sizeof(MovieTrackingMarker));
411
412                                 track->markersnr= track->markersnr-a;
413                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
414
415                                 break;
416                         }
417
418                         a--;
419                 }
420
421                 if(track->markersnr)
422                         put_disabled_marker(track, &track->markers[0], 1, 1);
423         } else if(action==TRACK_CLEAR_ALL) {
424                 MovieTrackingMarker *marker, marker_new;
425
426                 marker= BKE_tracking_get_marker(track, ref_frame);
427                 marker_new= *marker;
428
429                 MEM_freeN(track->markers);
430                 track->markers= NULL;
431                 track->markersnr= 0;
432
433                 BKE_tracking_insert_marker(track, &marker_new);
434
435                 put_disabled_marker(track, &marker_new, 1, 1);
436                 put_disabled_marker(track, &marker_new, 0, 1);
437         }
438 }
439
440 int BKE_tracking_test_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
441 {
442         int a= 0, b= 0;
443         /* int tot= dst_track->markersnr+src_track->markersnr; */ /* UNUSED */
444         int count= 0;
445
446         while(a<src_track->markersnr || b<dst_track->markersnr) {
447                 if(b>=dst_track->markersnr) {
448                         a++;
449                         count++;
450                 }
451                 else if(a>=src_track->markersnr) {
452                         b++;
453                         count++;
454                 }
455                 else if(src_track->markers[a].framenr<dst_track->markers[b].framenr) {
456                         a++;
457                         count++;
458                 } else if(src_track->markers[a].framenr>dst_track->markers[b].framenr) {
459                         b++;
460                         count++;
461                 } else {
462                         if((src_track->markers[a].flag&MARKER_DISABLED)==0 && (dst_track->markers[b].flag&MARKER_DISABLED)==0)
463                                 return 0;
464
465                         a++;
466                         b++;
467                         count++;
468                 }
469         }
470
471         return count;
472 }
473
474 void BKE_tracking_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
475 {
476         int i, a= 0, b= 0, tot;
477         MovieTrackingMarker *markers;
478
479         tot= BKE_tracking_test_join_tracks(dst_track, src_track);
480
481         markers= MEM_callocN(tot*sizeof(MovieTrackingMarker), "tracking joined tracks");
482
483         for(i= 0; i<tot; i++) {
484                 if(b>=dst_track->markersnr) {
485                         markers[i]= src_track->markers[a++];
486                 }
487                 else if(a>=src_track->markersnr) {
488                         markers[i]= dst_track->markers[b++];
489                 }
490                 else if(src_track->markers[a].framenr<dst_track->markers[b].framenr) {
491                         markers[i]= src_track->markers[a++];
492                 } else if(src_track->markers[a].framenr>dst_track->markers[b].framenr) {
493                         markers[i]= dst_track->markers[b++];
494                 } else {
495                         if((src_track->markers[a].flag&MARKER_DISABLED)) markers[i]= dst_track->markers[b];
496                         else markers[i]= src_track->markers[a++];
497
498                         a++;
499                         b++;
500                 }
501         }
502
503         MEM_freeN(dst_track->markers);
504
505         dst_track->markers= markers;
506         dst_track->markersnr= tot;
507 }
508
509 void BKE_tracking_free(MovieTracking *tracking)
510 {
511         MovieTrackingTrack *track;
512
513         for(track= tracking->tracks.first; track; track= track->next) {
514                 BKE_tracking_free_track(track);
515         }
516
517         BLI_freelistN(&tracking->tracks);
518
519         if(tracking->reconstruction.cameras)
520                 MEM_freeN(tracking->reconstruction.cameras);
521
522         if(tracking->stabilization.scaleibuf)
523                 IMB_freeImBuf(tracking->stabilization.scaleibuf);
524
525         if(tracking->camera.intrinsics)
526                 BKE_tracking_distortion_destroy(tracking->camera.intrinsics);
527 }
528
529 /*********************** tracking *************************/
530
531 typedef struct TrackContext {
532         MovieTrackingTrack *track;
533
534 #ifdef WITH_LIBMV
535         float keyframed_pos[2];
536
537         /* ** KLT tracker ** */
538         struct libmv_RegionTracker *region_tracker;
539         float *patch;                   /* keyframed patch */
540
541         /* ** SAD tracker ** */
542         int patsize;                    /* size of pattern (currently only 16x16 due to libmv side) */
543         unsigned char *pattern; /* keyframed pattern */
544         unsigned char *warped;  /* warped version of reference */
545 #endif
546 } TrackContext;
547
548 typedef struct MovieTrackingContext {
549         MovieClipUser user;
550         MovieClip *clip;
551
552         int first_time, frames;
553
554         TrackContext *track_context;
555         int num_tracks;
556
557         GHash *hash;
558         MovieTrackingSettings settings;
559
560         short backwards, disable_failed;
561         int sync_frame;
562 } MovieTrackingContext;
563
564 MovieTrackingContext *BKE_tracking_context_new(MovieClip *clip, MovieClipUser *user, short backwards, short disable_failed)
565 {
566         MovieTrackingContext *context= MEM_callocN(sizeof(MovieTrackingContext), "trackingContext");
567         MovieTracking *tracking= &clip->tracking;
568         MovieTrackingSettings *settings= &tracking->settings;
569         MovieTrackingTrack *track;
570         TrackContext *track_context;
571
572         context->settings= *settings;
573         context->backwards= backwards;
574         context->disable_failed= disable_failed;
575         context->hash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "tracking trackHash");
576         context->sync_frame= user->framenr;
577         context->first_time= 1;
578
579         /* count */
580         track= tracking->tracks.first;
581         while(track) {
582                 if(TRACK_SELECTED(track) && (track->flag&TRACK_LOCKED)==0) {
583                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
584
585                         if((marker->flag&MARKER_DISABLED)==0)
586                                 context->num_tracks++;
587                 }
588
589                 track= track->next;
590         }
591
592         if(context->num_tracks) {
593                 int width, height;
594
595                 BKE_movieclip_get_size(clip, user, &width, &height);
596
597                 /* create tracking data */
598                 context->track_context= MEM_callocN(sizeof(TrackContext)*context->num_tracks, "tracking track_context");
599
600                 track_context= context->track_context;
601                 track= tracking->tracks.first;
602                 while(track) {
603                         if(TRACK_SELECTED(track) && (track->flag&TRACK_LOCKED)==0) {
604                                 MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
605
606                                 if((marker->flag&MARKER_DISABLED)==0) {
607                                         MovieTrackingTrack *new_track= BKE_tracking_copy_track(track);
608
609                                         track_context->track= new_track;
610 #ifdef WITH_LIBMV
611                                         {
612                                                 if(track_context->track->tracker==TRACKER_KLT) {
613                                                         float search_size_x= (track->search_max[0]-track->search_min[0])*width;
614                                                         float search_size_y= (track->search_max[1]-track->search_min[1])*height;
615                                                         float pattern_size_x= (track->pat_max[0]-track->pat_min[0])*width;
616                                                         float pattern_size_y= (track->pat_max[1]-track->pat_min[1])*height;
617                                                         int wndx, wndy;
618
619                                                         /* compute the maximum pyramid size */
620                                                         float search_to_pattern_ratio= MIN2(search_size_x,  search_size_y)
621                                                                 / MAX2(pattern_size_x, pattern_size_y);
622                                                         float log2_search_to_pattern_ratio = log(floor(search_to_pattern_ratio)) / M_LN2;
623                                                         int max_pyramid_levels= floor(log2_search_to_pattern_ratio + 1);
624
625                                                         /* try to accomodate the user's choice of pyramid level in a way
626                                                          * that doesn't cause the coarsest pyramid pattern to be larger
627                                                          * than the search size */
628                                                         int level= MIN2(track_context->track->pyramid_levels, max_pyramid_levels);
629
630                                                         wndx= (int)((track->pat_max[0]-track->pat_min[0])*width)/2;
631                                                         wndy= (int)((track->pat_max[1]-track->pat_min[1])*height)/2;
632
633                                                         track_context->region_tracker= libmv_regionTrackerNew(100, level, MAX2(wndx, wndy));
634                                                 }
635                                                 else if(track_context->track->tracker==TRACKER_SAD) {
636                                                         /* nothing to initialize */
637                                                 }
638                                         }
639 #endif
640
641                                         BLI_ghash_insert(context->hash, new_track, track);
642
643                                         track_context++;
644                                 }
645                         }
646
647                         track= track->next;
648                 }
649         }
650
651         context->clip= clip;
652         context->user= *user;
653
654         return context;
655 }
656
657 void BKE_tracking_context_free(MovieTrackingContext *context)
658 {
659         int a;
660         TrackContext *track_context;
661
662         for(a= 0, track_context= context->track_context; a<context->num_tracks; a++, track_context++) {
663                 BKE_tracking_free_track(context->track_context[a].track);
664
665 #if WITH_LIBMV
666                 if(track_context->region_tracker)
667                         libmv_regionTrackerDestroy(track_context->region_tracker);
668
669                 if(track_context->patch)
670                         MEM_freeN(track_context->patch);
671
672                 if(track_context->pattern)
673                         MEM_freeN(track_context->pattern);
674
675                 if(track_context->warped)
676                         MEM_freeN(track_context->warped);
677 #endif
678
679                 MEM_freeN(track_context->track);
680         }
681
682         if(context->track_context)
683                 MEM_freeN(context->track_context);
684
685         BLI_ghash_free(context->hash, NULL, NULL);
686
687         MEM_freeN(context);
688 }
689
690 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track)
691 {
692         int x, y;
693
694         if((track->flag&(TRACK_DISABLE_RED|TRACK_DISABLE_GREEN|TRACK_DISABLE_BLUE))==0)
695                 return;
696
697         for(y= 0; y<ibuf->y; y++) {
698                 for (x= 0; x<ibuf->x; x++) {
699                         int pixel= ibuf->x*y + x;
700
701                         if(ibuf->rect_float) {
702                                 float *rrgbf= ibuf->rect_float + pixel*4;
703
704                                 if(track->flag&TRACK_DISABLE_RED)       rrgbf[0]= 0;
705                                 if(track->flag&TRACK_DISABLE_GREEN)     rrgbf[1]= 0;
706                                 if(track->flag&TRACK_DISABLE_BLUE)      rrgbf[2]= 0;
707                         } else {
708                                 char *rrgb= (char*)ibuf->rect + pixel*4;
709
710                                 if(track->flag&TRACK_DISABLE_RED)       rrgb[0]= 0;
711                                 if(track->flag&TRACK_DISABLE_GREEN)     rrgb[1]= 0;
712                                 if(track->flag&TRACK_DISABLE_BLUE)      rrgb[2]= 0;
713                         }
714                 }
715         }
716 }
717
718 static ImBuf *get_area_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
719                         float min[2], float max[2], int margin, int anchored, float pos[2], int origin[2])
720 {
721         ImBuf *tmpibuf;
722         int x, y;
723         int x1, y1, x2, y2, w, h;
724         float mpos[2];
725
726         copy_v2_v2(mpos, marker->pos);
727         if(anchored)
728                 add_v2_v2(mpos, track->offset);
729
730         x= mpos[0]*ibuf->x;
731         y= mpos[1]*ibuf->y;
732         x1= x-(int)(-min[0]*ibuf->x);
733         y1= y-(int)(-min[1]*ibuf->y);
734         x2= x+(int)(max[0]*ibuf->x);
735         y2= y+(int)(max[1]*ibuf->y);
736
737         /* dimensions should be odd */
738         w= (x2-x1)|1;
739         h= (y2-y1)|1;
740
741         tmpibuf= IMB_allocImBuf(w+margin*2, h+margin*2, 32, IB_rect);
742         IMB_rectcpy(tmpibuf, ibuf, 0, 0, x1-margin, y1-margin, w+margin*2, h+margin*2);
743
744         if(pos != NULL) {
745                 pos[0]= mpos[0]*ibuf->x-x1+margin;
746                 pos[1]= mpos[1]*ibuf->y-y1+margin;
747         }
748
749         if(origin != NULL) {
750                 origin[0]= x1-margin;
751                 origin[1]= y1-margin;
752         }
753
754         disable_imbuf_channels(tmpibuf, track);
755
756         return tmpibuf;
757 }
758
759 ImBuf *BKE_tracking_get_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
760                         int margin, int anchored, float pos[2], int origin[2])
761 {
762         return get_area_imbuf(ibuf, track, marker, track->pat_min, track->pat_max, margin, anchored, pos, origin);
763 }
764
765 ImBuf *BKE_tracking_get_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
766                         int margin, int anchored, float pos[2], int origin[2])
767 {
768         return get_area_imbuf(ibuf, track, marker, track->search_min, track->search_max, margin, anchored, pos, origin);
769 }
770
771 #ifdef WITH_LIBMV
772 static float *get_search_floatbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
773                         int *width_r, int *height_r, float pos[2], int origin[2])
774 {
775         ImBuf *tmpibuf;
776         float *pixels, *fp;
777         int x, y, width, height;
778
779         width= (track->search_max[0]-track->search_min[0])*ibuf->x;
780         height= (track->search_max[1]-track->search_min[1])*ibuf->y;
781
782         tmpibuf= BKE_tracking_get_search_imbuf(ibuf, track, marker, 0, 0, pos, origin);
783         disable_imbuf_channels(tmpibuf, track);
784
785         *width_r= width;
786         *height_r= height;
787
788         fp= pixels= MEM_callocN(width*height*sizeof(float), "tracking floatBuf");
789         for(y= 0; y<(int)height; y++) {
790                 for (x= 0; x<(int)width; x++) {
791                         int pixel= tmpibuf->x*y + x;
792
793                         if(tmpibuf->rect_float) {
794                                 float *rrgbf= tmpibuf->rect_float + pixel*4;
795
796                                 *fp= 0.2126*rrgbf[0] + 0.7152*rrgbf[1] + 0.0722*rrgbf[2];
797                         } else {
798                                 unsigned char *rrgb= (unsigned char*)tmpibuf->rect + pixel*4;
799
800                                 *fp= (0.2126*rrgb[0] + 0.7152*rrgb[1] + 0.0722*rrgb[2])/255.0f;
801                         }
802
803                         fp++;
804                 }
805         }
806
807         IMB_freeImBuf(tmpibuf);
808
809         return pixels;
810 }
811
812 static unsigned char *get_ucharbuf(ImBuf *ibuf)
813 {
814         int x, y;
815         unsigned char *pixels, *cp;
816
817         cp= pixels= MEM_callocN(ibuf->x*ibuf->y*sizeof(unsigned char), "tracking ucharBuf");
818         for(y= 0; y<ibuf->y; y++) {
819                 for (x= 0; x<ibuf->x; x++) {
820                         int pixel= ibuf->x*y + x;
821
822                         if(ibuf->rect_float) {
823                                 float *rrgbf= ibuf->rect_float + pixel*4;
824
825                                 *cp= FTOCHAR(0.2126f*rrgbf[0] + 0.7152f*rrgbf[1] + 0.0722f*rrgbf[2]);
826                         } else {
827                                 unsigned char *rrgb= (unsigned char*)ibuf->rect + pixel*4;
828
829                                 *cp= 0.2126f*rrgb[0] + 0.7152f*rrgb[1] + 0.0722f*rrgb[2];
830                         }
831
832                         cp++;
833                 }
834         }
835
836         return pixels;
837 }
838
839 static unsigned char *get_search_bytebuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
840                         int *width_r, int *height_r, float pos[2], int origin[2])
841 {
842         ImBuf *tmpibuf;
843         unsigned char *pixels;
844
845         tmpibuf= BKE_tracking_get_search_imbuf(ibuf, track, marker, 0, 0, pos, origin);
846         disable_imbuf_channels(tmpibuf, track);
847
848         *width_r= tmpibuf->x;
849         *height_r= tmpibuf->y;
850
851         pixels= get_ucharbuf(tmpibuf);
852
853         IMB_freeImBuf(tmpibuf);
854
855         return pixels;
856 }
857
858 static ImBuf *get_frame_ibuf(MovieTrackingContext *context, int framenr)
859 {
860         ImBuf *ibuf;
861         int framenr_old= context->user.framenr;
862
863         context->user.framenr= framenr;
864
865         ibuf= BKE_movieclip_get_ibuf_flag(context->clip, &context->user, 0);
866
867         context->user.framenr= framenr_old;
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_get_marker(track, curfra);
1054
1055                 if(marker && (marker->flag&MARKER_DISABLED)==0 && marker->framenr==curfra) {
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         float origin[3]= {0.0f, 0.0f, 0.0f};
1289         int ok= 1;
1290
1291         track= tracking->tracks.first;
1292         while(track) {
1293                 double pos[3];
1294
1295                 if(libmv_reporojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
1296                         track->bundle_pos[0]= pos[0];
1297                         track->bundle_pos[1]= pos[1];
1298                         track->bundle_pos[2]= pos[2];
1299
1300                         track->flag|= TRACK_HAS_BUNDLE;
1301                         track->error= libmv_reporojectionErrorForTrack(libmv_reconstruction, tracknr);
1302                 } else {
1303                         track->flag&= ~TRACK_HAS_BUNDLE;
1304                         ok= 0;
1305
1306                         printf("No bundle for track #%d '%s'\n", tracknr, track->name);
1307                 }
1308
1309                 if(track->markersnr) {
1310                         int first= 0, last= track->markersnr;
1311                         MovieTrackingMarker *first_marker= &track->markers[0];
1312                         MovieTrackingMarker *last_marker= &track->markers[track->markersnr-1];
1313
1314                         /* find first not-disabled marker */
1315                         while(first<track->markersnr-1 && first_marker->flag&MARKER_DISABLED) {
1316                                 first++;
1317                                 first_marker++;
1318                         }
1319
1320                         /* find last not-disabled marker */
1321                         while(last>=0 && last_marker->flag&MARKER_DISABLED) {
1322                                 last--;
1323                                 last_marker--;
1324                         }
1325
1326                         if(first<track->markersnr-1)
1327                                 sfra= MIN2(sfra, first_marker->framenr);
1328
1329                         if(last>=0)
1330                                 efra= MAX2(efra, last_marker->framenr);
1331                 }
1332
1333                 track= track->next;
1334                 tracknr++;
1335         }
1336
1337         if(reconstruction->cameras)
1338                 MEM_freeN(reconstruction->cameras);
1339
1340         reconstruction->camnr= 0;
1341         reconstruction->cameras= NULL;
1342         reconstructed= MEM_callocN((efra-sfra+1)*sizeof(MovieReconstructedCamera), "temp reconstructed camera");
1343
1344         for(a= sfra; a<=efra; a++) {
1345                 double matd[4][4];
1346
1347                 if(libmv_reporojectionCameraForImage(libmv_reconstruction, a, matd)) {
1348                         int i, j;
1349                         float mat[4][4];
1350                         float error= libmv_reporojectionErrorForImage(libmv_reconstruction, a);
1351
1352                         for(i=0; i<4; i++)
1353                                 for(j= 0; j<4; j++)
1354                                         mat[i][j]= matd[i][j];
1355
1356                         if(!origin_set) {
1357                                 copy_v3_v3(origin, mat[3]);
1358                                 origin_set= 1;
1359                         }
1360
1361                         if(origin_set)
1362                                 sub_v3_v3(mat[3], origin);
1363
1364                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
1365                         reconstructed[reconstruction->camnr].framenr= a;
1366                         reconstructed[reconstruction->camnr].error= error;
1367                         reconstruction->camnr++;
1368                 } else {
1369                         ok= 0;
1370                         printf("No camera for frame %d\n", a);
1371                 }
1372         }
1373
1374         if(reconstruction->camnr) {
1375                 reconstruction->cameras= MEM_callocN(reconstruction->camnr*sizeof(MovieReconstructedCamera), "reconstructed camera");
1376                 memcpy(reconstruction->cameras, reconstructed, reconstruction->camnr*sizeof(MovieReconstructedCamera));
1377         }
1378
1379         if(origin_set) {
1380                 track= tracking->tracks.first;
1381                 while(track) {
1382                         if(track->flag&TRACK_HAS_BUNDLE)
1383                                 sub_v3_v3(track->bundle_pos, origin);
1384
1385                         track= track->next;
1386                 }
1387         }
1388
1389         MEM_freeN(reconstructed);
1390
1391         return ok;
1392 }
1393
1394 static int retrieve_libmv_reconstruct(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
1395 {
1396         /* take the intrinscis back from libmv */
1397         retrieve_libmv_reconstruct_intrinscis(tracking, libmv_reconstruction);
1398
1399         return retrieve_libmv_reconstruct_tracks(tracking, libmv_reconstruction);
1400 }
1401
1402 static int get_refine_intrinsics_flags(MovieTracking *tracking)
1403 {
1404         int refine= tracking->settings.refine_camera_intrinsics;
1405         int flags= 0;
1406
1407         if(refine&REFINE_FOCAL_LENGTH)
1408                 flags|= LIBMV_REFINE_FOCAL_LENGTH;
1409
1410         if(refine&REFINE_PRINCIPAL_POINT)
1411                 flags|= LIBMV_REFINE_PRINCIPAL_POINT;
1412
1413         if(refine&REFINE_RADIAL_DISTORTION_K1)
1414                 flags|= REFINE_RADIAL_DISTORTION_K1;
1415
1416         if(refine&REFINE_RADIAL_DISTORTION_K2)
1417                 flags|= REFINE_RADIAL_DISTORTION_K2;
1418
1419         return flags;
1420 }
1421
1422 static int count_tracks_on_both_keyframes(MovieTracking *tracking)
1423 {
1424         int tot= 0;
1425         int frame1= tracking->settings.keyframe1, frame2= tracking->settings.keyframe2;
1426         MovieTrackingTrack *track;
1427
1428         track= tracking->tracks.first;
1429         while(track) {
1430                 if(BKE_tracking_has_marker(track, frame1))
1431                         if(BKE_tracking_has_marker(track, frame2))
1432                                 tot++;
1433
1434                 track= track->next;
1435         }
1436
1437         return tot;
1438 }
1439 #endif
1440
1441 int BKE_tracking_can_solve(MovieTracking *tracking, char *error_msg, int error_size)
1442 {
1443 #if WITH_LIBMV
1444         if(count_tracks_on_both_keyframes(tracking)<8) {
1445                 BLI_strncpy(error_msg, "At least 8 tracks on both of keyframes are needed for reconstruction", error_size);
1446                 return 0;
1447         }
1448
1449         return 1;
1450 #else
1451         BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
1452
1453         return 0;
1454 #endif
1455 }
1456
1457 float BKE_tracking_solve_reconstruction(MovieTracking *tracking, int width, int height)
1458 {
1459 #if WITH_LIBMV
1460         {
1461                 MovieTrackingCamera *camera= &tracking->camera;
1462                 float aspy= 1.0f/tracking->camera.pixel_aspect;
1463                 struct libmv_Tracks *tracks= create_libmv_tracks(tracking, width, height*aspy);
1464                 struct libmv_Reconstruction *reconstruction = libmv_solveReconstruction(tracks,
1465                         tracking->settings.keyframe1, tracking->settings.keyframe2,
1466                         get_refine_intrinsics_flags(tracking),
1467                         camera->focal,
1468                         camera->principal[0], camera->principal[1]*aspy,
1469                         camera->k1, camera->k2, camera->k3);
1470                 float error= libmv_reprojectionError(reconstruction);
1471
1472                 tracking->reconstruction.error= error;
1473
1474                 if(!retrieve_libmv_reconstruct(tracking, reconstruction))
1475                         error= -1.0f;
1476
1477                 libmv_destroyReconstruction(reconstruction);
1478                 libmv_tracksDestroy(tracks);
1479
1480                 tracking->reconstruction.flag|= TRACKING_RECONSTRUCTED;
1481
1482                 return error;
1483         }
1484 #else
1485         (void)tracking;
1486         (void)width;
1487         (void)height;
1488
1489         return -1.0f;
1490 #endif
1491 }
1492
1493 void BKE_track_unique_name(MovieTracking *tracking, MovieTrackingTrack *track)
1494 {
1495         BLI_uniquename(&tracking->tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
1496 }
1497
1498 MovieTrackingTrack *BKE_tracking_named_track(MovieTracking *tracking, const char *name)
1499 {
1500         MovieTrackingTrack *track= tracking->tracks.first;
1501
1502         while(track) {
1503                 if(!strcmp(track->name, name))
1504                         return track;
1505
1506                 track= track->next;
1507         }
1508
1509         return NULL;
1510 }
1511
1512 static int reconstruction_camera_index(MovieTracking *tracking, int framenr, int nearest)
1513 {
1514         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1515         MovieReconstructedCamera *cameras= reconstruction->cameras;
1516         int a= 0, d= 1;
1517
1518         if(!reconstruction->camnr)
1519                 return -1;
1520
1521         if(framenr<cameras[0].framenr) {
1522                 if(nearest) return 0;
1523                 else return -1;
1524         }
1525
1526         if(framenr>cameras[reconstruction->camnr-1].framenr) {
1527                 if(nearest) return reconstruction->camnr-1;
1528                 else return -1;
1529         }
1530
1531         if(reconstruction->last_camera<reconstruction->camnr)
1532                 a= reconstruction->last_camera;
1533
1534         if(cameras[a].framenr>=framenr)
1535                 d= -1;
1536
1537         while(a>=0 && a<reconstruction->camnr) {
1538                 int cfra= cameras[a].framenr;
1539
1540                 /* check if needed framenr was "skipped" -- no data for requested frame */
1541
1542                 if(d>0 && cfra>framenr) {
1543                         /* interpolate with previous position */
1544                         if(nearest) return a-1;
1545                         else break;
1546                 }
1547
1548                 if(d<0 && cfra<framenr) {
1549                         /* interpolate with next position */
1550                         if(nearest) return a;
1551                         else break;
1552                 }
1553
1554                 if(cfra==framenr) {
1555                         reconstruction->last_camera= a;
1556
1557                         return a;
1558                 }
1559
1560                 a+= d;
1561         }
1562
1563         return -1;
1564 }
1565
1566 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking, int framenr)
1567 {
1568         int a= reconstruction_camera_index(tracking, framenr, 0);
1569
1570         if(a==-1)
1571                 return NULL;
1572
1573         return &tracking->reconstruction.cameras[a];
1574 }
1575
1576 void BKE_tracking_get_interpolated_camera(MovieTracking *tracking, int framenr, float mat[4][4])
1577 {
1578         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1579         MovieReconstructedCamera *cameras= reconstruction->cameras;
1580         int a= reconstruction_camera_index(tracking, framenr, 1);
1581
1582         if(a==-1) {
1583                 unit_m4(mat);
1584                 return;
1585         }
1586
1587         if(cameras[a].framenr!=framenr && a>0 && a<reconstruction->camnr-1) {
1588                 float t= ((float)framenr-cameras[a].framenr) / (cameras[a+1].framenr-cameras[a].framenr);
1589
1590                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a+1].mat, t);
1591         } else {
1592                 copy_m4_m4(mat, cameras[a].mat);
1593         }
1594 }
1595
1596 void BKE_get_tracking_mat(Scene *scene, Object *ob, float mat[4][4])
1597 {
1598         if(!ob) {
1599                 if(scene->camera) ob= scene->camera;
1600                 else ob= scene_find_camera(scene);
1601         }
1602
1603         if(ob)
1604                 where_is_object_mat(scene, ob, mat);
1605         else
1606                 unit_m4(mat);
1607 }
1608
1609 void BKE_tracking_camera_shift(MovieTracking *tracking, int winx, int winy, float *shiftx, float *shifty)
1610 {
1611         *shiftx= (0.5f*winx-tracking->camera.principal[0]) / winx;
1612         *shifty= (0.5f*winy-tracking->camera.principal[1]) / winx;
1613 }
1614
1615 void BKE_tracking_camera_to_blender(MovieTracking *tracking, Scene *scene, Camera *camera, int width, int height)
1616 {
1617         float focal= tracking->camera.focal;
1618
1619         camera->sensor_x= tracking->camera.sensor_width;
1620         camera->sensor_fit= CAMERA_SENSOR_FIT_AUTO;
1621         camera->lens= focal*camera->sensor_x/width;
1622
1623         scene->r.xsch= width*tracking->camera.pixel_aspect;
1624         scene->r.ysch= height;
1625
1626         scene->r.xasp= 1.0f;
1627         scene->r.yasp= 1.0f;
1628
1629         BKE_tracking_camera_shift(tracking, width, height, &camera->shiftx, &camera->shifty);
1630 }
1631
1632 void BKE_tracking_projection_matrix(MovieTracking *tracking, int framenr, int winx, int winy, float mat[4][4])
1633 {
1634         MovieReconstructedCamera *camera;
1635         float lens= tracking->camera.focal*tracking->camera.sensor_width/(float)winx;
1636         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
1637         float winmat[4][4];
1638         float ycor= 1.0f/tracking->camera.pixel_aspect;
1639         float shiftx, shifty, winside= MAX2(winx, winy);
1640
1641         BKE_tracking_camera_shift(tracking, winx, winy, &shiftx, &shifty);
1642
1643         clipsta= 0.1f;
1644         clipend= 1000.0f;
1645
1646         if(winx >= winy)
1647                 viewfac= (lens*winx)/tracking->camera.sensor_width;
1648         else
1649                 viewfac= (ycor*lens*winy)/tracking->camera.sensor_width;
1650
1651         pixsize= clipsta/viewfac;
1652
1653         left= -0.5f*(float)winx + shiftx*winside;
1654         bottom= -0.5f*(ycor)*(float)winy + shifty*winside;
1655         right=  0.5f*(float)winx + shiftx*winside;
1656         top=  0.5f*(ycor)*(float)winy + shifty*winside;
1657
1658         left *= pixsize;
1659         right *= pixsize;
1660         bottom *= pixsize;
1661         top *= pixsize;
1662
1663         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
1664
1665         camera= BKE_tracking_get_reconstructed_camera(tracking, framenr);
1666         if(camera) {
1667                 float imat[4][4];
1668
1669                 invert_m4_m4(imat, camera->mat);
1670                 mul_m4_m4m4(mat, imat, winmat);
1671         } else copy_m4_m4(mat, winmat);
1672 }
1673
1674 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
1675 {
1676         MovieTrackingCamera *camera= &tracking->camera;
1677
1678 #ifdef WITH_LIBMV
1679         double x, y;
1680         float aspy= 1.0f/tracking->camera.pixel_aspect;
1681
1682         /* normalize coords */
1683         x= (co[0]-camera->principal[0]) / camera->focal;
1684         y= (co[1]-camera->principal[1] * aspy) / camera->focal;
1685
1686         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
1687                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
1688
1689         /* result is in image coords already */
1690         nco[0]= x;
1691         nco[1]= y;
1692 #else
1693         (void)camera;
1694         (void)co;
1695         (void)nco;
1696 #endif
1697 }
1698
1699 void BKE_tracking_invert_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
1700 {
1701         MovieTrackingCamera *camera= &tracking->camera;
1702
1703 #ifdef WITH_LIBMV
1704         double x= co[0], y= co[1];
1705         float aspy= 1.0f/tracking->camera.pixel_aspect;
1706
1707         libmv_InvertIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
1708                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
1709
1710         nco[0]= x * camera->focal + camera->principal[0];
1711         nco[1]= y * camera->focal + camera->principal[1] * aspy;
1712 #else
1713         (void)camera;
1714         (void)co;
1715         (void)nco;
1716 #endif
1717 }
1718
1719 #ifdef WITH_LIBMV
1720 static int point_in_stroke(bGPDstroke *stroke, float x, float y)
1721 {
1722         int i, prev;
1723         int count= 0;
1724         bGPDspoint *points= stroke->points;
1725
1726         prev= stroke->totpoints-1;
1727
1728         for(i= 0; i<stroke->totpoints; i++) {
1729                 if((points[i].y<y && points[prev].y>=y) || (points[prev].y<y && points[i].y>=y)) {
1730                         float fac= (y-points[i].y)/(points[prev].y-points[i].y);
1731
1732                         if (points[i].x+fac*(points[prev].x-points[i].x)<x)
1733                                 count++;
1734                 }
1735
1736                 prev= i;
1737         }
1738
1739         return count%2;
1740 }
1741
1742 static int point_in_layer(bGPDlayer *layer, float x, float y)
1743 {
1744         bGPDframe *frame= layer->frames.first;
1745
1746         while(frame) {
1747                 bGPDstroke *stroke= frame->strokes.first;
1748                 while(stroke) {
1749                         if(point_in_stroke(stroke, x, y))
1750                                 return 1;
1751
1752                         stroke= stroke->next;
1753                 }
1754                 frame= frame->next;
1755         }
1756
1757         return 0;
1758 }
1759
1760 static void retrieve_libmv_features(MovieTracking *tracking, struct libmv_Features *features,
1761                         int framenr, int width, int height, bGPDlayer *layer, int place_outside_layer)
1762 {
1763         int a;
1764
1765         a= libmv_countFeatures(features);
1766         while(a--) {
1767                 MovieTrackingTrack *track;
1768                 double x, y, size, score;
1769                 int ok= 1;
1770                 float xu, yu;
1771
1772                 libmv_getFeature(features, a, &x, &y, &score, &size);
1773
1774                 xu= x/width;
1775                 yu= y/height;
1776
1777                 if(layer)
1778                         ok= point_in_layer(layer, xu, yu)!=place_outside_layer;
1779
1780                 if(ok) {
1781                         track= BKE_tracking_add_track(tracking, xu, yu, framenr, width, height);
1782                         track->flag|= SELECT;
1783                         track->pat_flag|= SELECT;
1784                         track->search_flag|= SELECT;
1785                 }
1786         }
1787 }
1788 #endif
1789
1790 void BKE_tracking_detect_fast(MovieTracking *tracking, ImBuf *ibuf,
1791                         int framenr, int margin, int min_trackness, int min_distance, bGPDlayer *layer,
1792                         int place_outside_layer)
1793 {
1794 #ifdef WITH_LIBMV
1795         struct libmv_Features *features;
1796         unsigned char *pixels= get_ucharbuf(ibuf);
1797
1798         features= libmv_detectFeaturesFAST(pixels, ibuf->x, ibuf->y, ibuf->x, margin, min_trackness, min_distance);
1799
1800         MEM_freeN(pixels);
1801
1802         retrieve_libmv_features(tracking, features, framenr, ibuf->x, ibuf->y, layer, place_outside_layer);
1803
1804         libmv_destroyFeatures(features);
1805 #else
1806         (void)tracking;
1807         (void)ibuf;
1808         (void)framenr;
1809         (void)margin;
1810         (void)min_trackness;
1811         (void)min_distance;
1812         (void)layer;
1813         (void)place_outside_layer;
1814 #endif
1815 }
1816
1817 MovieTrackingTrack *BKE_tracking_indexed_track(MovieTracking *tracking, int tracknr)
1818 {
1819         MovieTrackingTrack *track= tracking->tracks.first;
1820         int cur= 1;
1821
1822         while(track) {
1823                 if(track->flag&TRACK_HAS_BUNDLE) {
1824                         if(cur==tracknr)
1825                                 return track;
1826
1827                         cur++;
1828                 }
1829
1830                 track= track->next;
1831         }
1832
1833         return NULL;
1834 }
1835
1836 static int stabilization_median_point(MovieTracking *tracking, int framenr, float median[2])
1837 {
1838         int ok= 0;
1839         float min[2], max[2];
1840         MovieTrackingTrack *track;
1841
1842         INIT_MINMAX2(min, max);
1843
1844         track= tracking->tracks.first;
1845         while(track) {
1846                 if(track->flag&TRACK_USE_2D_STAB) {
1847                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
1848
1849                         DO_MINMAX2(marker->pos, min, max);
1850
1851                         ok= 1;
1852                 }
1853
1854                 track= track->next;
1855         }
1856
1857         median[0]= (max[0]+min[0])/2.0f;
1858         median[1]= (max[1]+min[1])/2.0f;
1859
1860         return ok;
1861 }
1862
1863 static void calculate_stabdata(MovieTracking *tracking, int framenr, float width, float height,
1864                         float firstmedian[2], float median[2], float loc[2], float *scale, float *angle)
1865 {
1866         MovieTrackingStabilization *stab= &tracking->stabilization;
1867
1868         *scale= (stab->scale-1.0f)*stab->scaleinf+1.0f;
1869         *angle= 0.0f;
1870
1871         loc[0]= (firstmedian[0]-median[0])*width*(*scale);
1872         loc[1]= (firstmedian[1]-median[1])*height*(*scale);
1873
1874         mul_v2_fl(loc, stab->locinf);
1875
1876         if(stab->rot_track && stab->rotinf) {
1877                 MovieTrackingMarker *marker;
1878                 float a[2], b[2];
1879                 float x0= (float)width/2.0f, y0= (float)height/2.0f;
1880                 float x= median[0]*width, y= median[1]*height;
1881
1882                 marker= BKE_tracking_get_marker(stab->rot_track, 1);
1883                 sub_v2_v2v2(a, marker->pos, firstmedian);
1884                 a[0]*= width;
1885                 a[1]*= height;
1886
1887                 marker= BKE_tracking_get_marker(stab->rot_track, framenr);
1888                 sub_v2_v2v2(b, marker->pos, median);
1889                 b[0]*= width;
1890                 b[1]*= height;
1891
1892                 *angle= -atan2(a[0]*b[1]-a[1]*b[0], a[0]*b[0]+a[1]*b[1]);
1893                 *angle*= stab->rotinf;
1894
1895                 /* convert to rotation around image center */
1896                 loc[0]-= (x0 + (x-x0)*cosf(*angle)-(y-y0)*sinf(*angle) - x)*(*scale);
1897                 loc[1]-= (y0 + (x-x0)*sinf(*angle)+(y-y0)*cosf(*angle) - y)*(*scale);
1898         }
1899 }
1900
1901 static float stabilization_auto_scale_factor(MovieTracking *tracking, int width, int height)
1902 {
1903         float firstmedian[2];
1904         MovieTrackingStabilization *stab= &tracking->stabilization;
1905
1906         if(stab->ok)
1907                 return stab->scale;
1908
1909         if(stabilization_median_point(tracking, 1, firstmedian)) {
1910                 int sfra= INT_MAX, efra= INT_MIN, cfra;
1911                 float delta[2]= {0.0f, 0.0f}, scalex= 1.0f, scaley= 1.0f;
1912                 MovieTrackingTrack *track;
1913
1914                 stab->scale= 1.0f;
1915
1916                 track= tracking->tracks.first;
1917                 while(track) {
1918                         if(track->flag&TRACK_USE_2D_STAB || track==stab->rot_track) {
1919                                 if(track->markersnr) {
1920                                         sfra= MIN2(sfra, track->markers[0].framenr);
1921                                         efra= MAX2(efra, track->markers[track->markersnr-1].framenr);
1922                                 }
1923                         }
1924
1925                         track= track->next;
1926                 }
1927
1928                 for(cfra=sfra; cfra<=efra; cfra++) {
1929                         float median[2], near[2];
1930                         float loc[2], scale, angle;
1931
1932                         stabilization_median_point(tracking, cfra, median);
1933
1934                         calculate_stabdata(tracking, cfra, width, height, firstmedian, median,
1935                                                 loc, &scale, &angle);
1936
1937                         if(angle==0.0f) {
1938                                 loc[0]= fabsf(loc[0]);
1939                                 loc[1]= fabsf(loc[1]);
1940
1941                                 delta[0]= MAX2(delta[0], loc[0]);
1942                                 delta[1]= MAX2(delta[1], loc[1]);
1943
1944                                 near[0]= MIN2(median[0], 1.0f-median[0]);
1945                                 near[1]= MIN2(median[1], 1.0f-median[1]);
1946                                 near[0]= MAX2(near[0], 0.05f);
1947                                 near[1]= MAX2(near[1], 0.05f);
1948
1949                                 scalex= 1.0f+delta[0]/(near[0]*width);
1950                                 scaley= 1.0f+delta[1]/(near[1]*height);
1951                         } else {
1952                                 int i;
1953                                 float mat[4][4];
1954                                 float points[4][2]={{0.0f, 0.0f}, {0.0f, height}, {width, height}, {width, 0.0f}};
1955
1956                                 BKE_tracking_stabdata_to_mat4(width, height, loc, scale, angle, mat);
1957
1958                                 for(i= 0; i<4; i++) {
1959                                         int j;
1960                                         float a[3]= {0.0f, 0.0f, 0.0f}, b[3]= {0.0f, 0.0f, 0.0f};
1961
1962                                         copy_v3_v3(a, points[i]);
1963                                         copy_v3_v3(b, points[(i+1)%4]);
1964
1965                                         mul_m4_v3(mat, a);
1966                                         mul_m4_v3(mat, b);
1967
1968                                         for(j= 0; j<4; j++) {
1969                                                 float point[3]= {points[j][0], points[j][1], 0.0f};
1970                                                 float v1[3], v2[3];
1971
1972                                                 sub_v3_v3v3(v1, b, a);
1973                                                 sub_v3_v3v3(v2, point, a);
1974
1975                                                 if(cross_v2v2(v1, v2) >= 0.0f) {
1976                                                         float dist= dist_to_line_v2(point, a, b);
1977                                                         if(i%2==0) {
1978                                                                 scalex= MAX2(scalex, (width+2*dist)/width);
1979                                                         } else {
1980                                                                 scaley= MAX2(scaley, (height+2*dist)/height);
1981                                                         }
1982                                                 }
1983                                         }
1984                                 }
1985                         }
1986                 }
1987
1988                 stab->scale= MAX2(scalex, scaley);
1989
1990                 if(stab->maxscale>0.0f)
1991                         stab->scale= MIN2(stab->scale, stab->maxscale);
1992         } else {
1993                 stab->scale= 1.0f;
1994         }
1995
1996         stab->ok= 1;
1997
1998         return stab->scale;
1999 }
2000
2001 static ImBuf* stabilize_alloc_ibuf(ImBuf *cacheibuf, ImBuf *srcibuf, int fill)
2002 {
2003         int flags;
2004
2005         if(cacheibuf && (cacheibuf->x != srcibuf->x || cacheibuf->y != srcibuf->y)) {
2006                 IMB_freeImBuf(cacheibuf);
2007                 cacheibuf= NULL;
2008         }
2009
2010         flags= IB_rect;
2011
2012         if(srcibuf->rect_float)
2013                 flags|= IB_rectfloat;
2014
2015         if(cacheibuf) {
2016                 if(fill) {
2017                         float col[4]= {0.0f, 0.0f, 0.0f, 0.0f};
2018                         IMB_rectfill(cacheibuf, col);
2019                 }
2020         }
2021         else {
2022                 cacheibuf= IMB_allocImBuf(srcibuf->x, srcibuf->y, srcibuf->depth, flags);
2023                 cacheibuf->profile= srcibuf->profile;
2024         }
2025
2026         return cacheibuf;
2027 }
2028
2029 void BKE_tracking_stabilization_data(MovieTracking *tracking, int framenr, int width, int height, float loc[2], float *scale, float *angle)
2030 {
2031         float firstmedian[2], median[2];
2032         MovieTrackingStabilization *stab= &tracking->stabilization;
2033
2034         if((stab->flag&TRACKING_2D_STABILIZATION)==0) {
2035                 zero_v2(loc);
2036                 *scale= 1.0f;
2037                 *angle= 0.0f;
2038
2039                 return;
2040         }
2041
2042         if(stabilization_median_point(tracking, 1, firstmedian)) {
2043                 stabilization_median_point(tracking, framenr, median);
2044
2045                 if((stab->flag&TRACKING_AUTOSCALE)==0)
2046                         stab->scale= 1.0f;
2047
2048                 if(!stab->ok) {
2049                         if(stab->flag&TRACKING_AUTOSCALE)
2050                                 stabilization_auto_scale_factor(tracking, width, height);
2051
2052                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2053
2054                         stab->ok= 1;
2055                 } else {
2056                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2057                 }
2058         } else {
2059                 zero_v2(loc);
2060                 *scale= 1.0f;
2061                 *angle= 0.0f;
2062         }
2063 }
2064
2065 ImBuf *BKE_tracking_stabilize(MovieTracking *tracking, int framenr, ImBuf *ibuf, float loc[2], float *scale, float *angle)
2066 {
2067         float tloc[2], tscale, tangle;
2068         MovieTrackingStabilization *stab= &tracking->stabilization;
2069         ImBuf *tmpibuf;
2070         float width= ibuf->x, height= ibuf->y;
2071
2072         if(loc)         copy_v2_v2(tloc, loc);
2073         if(scale)       tscale= *scale;
2074
2075         if((stab->flag&TRACKING_2D_STABILIZATION)==0) {
2076                 if(loc)         zero_v2(loc);
2077                 if(scale)       *scale= 1.0f;
2078
2079                 return ibuf;
2080         }
2081
2082         BKE_tracking_stabilization_data(tracking, framenr, width, height, tloc, &tscale, &tangle);
2083
2084         tmpibuf= stabilize_alloc_ibuf(NULL, ibuf, 1);
2085
2086         /* scale would be handled by matrix transformation when angle is non-zero */
2087         if(tscale!=1.0f && tangle==0.0f) {
2088                 ImBuf *scaleibuf;
2089
2090                 stabilization_auto_scale_factor(tracking, width, height);
2091
2092                 scaleibuf= stabilize_alloc_ibuf(stab->scaleibuf, ibuf, 0);
2093                 stab->scaleibuf= scaleibuf;
2094
2095                 IMB_rectcpy(scaleibuf, ibuf, 0, 0, 0, 0, ibuf->x, ibuf->y);
2096                 IMB_scalefastImBuf(scaleibuf, ibuf->x*tscale, ibuf->y*tscale);
2097
2098                 ibuf= scaleibuf;
2099         }
2100
2101         if(tangle==0.0f) {
2102                 /* if angle is zero, then it's much faster to use rect copy
2103                    but could be issues with subpixel precisions */
2104                 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);
2105         } else {
2106                 float mat[4][4];
2107                 int i, j;
2108
2109                 BKE_tracking_stabdata_to_mat4(ibuf->x, ibuf->y, tloc, tscale, tangle, mat);
2110                 invert_m4(mat);
2111
2112                 for(j=0; j<tmpibuf->y; j++) {
2113                         for(i=0; i<tmpibuf->x;i++) {
2114                                 float vec[3]= {i, j, 0};
2115
2116                                 mul_v3_m4v3(vec, mat, vec);
2117
2118                                 /* TODO: add selector for interpolation method */
2119                                 neareast_interpolation(ibuf, tmpibuf, vec[0], vec[1], i, j);
2120                         }
2121                 }
2122         }
2123
2124         tmpibuf->userflags|= IB_MIPMAP_INVALID;
2125
2126         if(tmpibuf->rect_float)
2127                 tmpibuf->userflags|= IB_RECT_INVALID;
2128
2129         if(loc)         copy_v2_v2(loc, tloc);
2130         if(scale)       *scale= tscale;
2131         if(angle)       *angle= tangle;
2132
2133         return tmpibuf;
2134 }
2135
2136 void BKE_tracking_stabdata_to_mat4(int width, int height, float loc[2], float scale, float angle, float mat[4][4])
2137 {
2138         float lmat[4][4], rmat[4][4], smat[4][4], cmat[4][4], icmat[4][4];
2139         float svec[3]= {scale, scale, scale};
2140
2141         unit_m4(rmat);
2142         unit_m4(lmat);
2143         unit_m4(smat);
2144         unit_m4(cmat);
2145
2146         /* image center as rotation center */
2147         cmat[3][0]= (float)width/2.0f;
2148         cmat[3][1]= (float)height/2.0f;
2149         invert_m4_m4(icmat, cmat);
2150
2151         size_to_mat4(smat, svec);               /* scale matrix */
2152         add_v2_v2(lmat[3], loc);                /* tranlation matrix */
2153         rotate_m4(rmat, 'Z', angle);    /* rotation matrix */
2154
2155         /* compose transformation matrix */
2156         mul_serie_m4(mat, lmat, cmat, rmat, smat, icmat, NULL, NULL, NULL);
2157 }
2158
2159 MovieDistortion *BKE_tracking_distortion_create(void)
2160 {
2161         MovieDistortion *distortion;
2162
2163         distortion= MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2164
2165         return distortion;
2166 }
2167
2168 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
2169 {
2170         MovieDistortion *new_distortion;
2171
2172         new_distortion= MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2173
2174 #ifdef WITH_LIBMV
2175         new_distortion->intrinsics= libmv_CameraIntrinsicsCopy(distortion->intrinsics);
2176 #else
2177         (void)distortion;
2178 #endif
2179
2180         return new_distortion;
2181 }
2182
2183 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking, int width, int height)
2184 {
2185         MovieTrackingCamera *camera= &tracking->camera;
2186         float aspy= 1.0f/tracking->camera.pixel_aspect;
2187
2188 #ifdef WITH_LIBMV
2189         if(!distortion->intrinsics) {
2190                 distortion->intrinsics= libmv_CameraIntrinsicsNew(camera->focal,
2191                                 camera->principal[0], camera->principal[1] * aspy,
2192                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2193         } else {
2194                 libmv_CameraIntrinsicsUpdate(distortion->intrinsics, camera->focal,
2195                                 camera->principal[0], camera->principal[1] * aspy,
2196                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2197         }
2198 #else
2199         (void)distortion;
2200         (void)width;
2201         (void)height;
2202         (void)camera;
2203         (void)aspy;
2204 #endif
2205 }
2206
2207 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking,
2208                         ImBuf *ibuf, int width, int height, float overscan, int undistort)
2209 {
2210         ImBuf *resibuf;
2211
2212         BKE_tracking_distortion_update(distortion, tracking, width, height);
2213
2214         resibuf= IMB_dupImBuf(ibuf);
2215
2216         if(ibuf->rect_float) {
2217 #ifdef WITH_LIBMV
2218                 if(undistort) {
2219                         libmv_CameraIntrinsicsUndistortFloat(distortion->intrinsics,
2220                                                 ibuf->rect_float, resibuf->rect_float,
2221                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2222                 } else {
2223                         libmv_CameraIntrinsicsDistortFloat(distortion->intrinsics,
2224                                                 ibuf->rect_float, resibuf->rect_float,
2225                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2226                 }
2227 #endif
2228
2229                 ibuf->userflags|= IB_RECT_INVALID;
2230         } else {
2231 #ifdef WITH_LIBMV
2232                 if(undistort) {
2233                                 libmv_CameraIntrinsicsUndistortByte(distortion->intrinsics,
2234                                                         (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2235                                                         ibuf->x, ibuf->y, overscan, ibuf->channels);
2236                 } else {
2237                         libmv_CameraIntrinsicsDistortByte(distortion->intrinsics,
2238                                                 (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2239                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2240                 }
2241 #endif
2242         }
2243
2244 #ifndef WITH_LIBMV
2245         (void)overscan;
2246         (void)undistort;
2247 #endif
2248
2249         return resibuf;
2250 }
2251
2252 void BKE_tracking_distortion_destroy(MovieDistortion *distortion)
2253 {
2254 #ifdef WITH_LIBMV
2255         libmv_CameraIntrinsicsDestroy(distortion->intrinsics);
2256 #endif
2257
2258         MEM_freeN(distortion);
2259 }
2260
2261 ImBuf *BKE_tracking_undistort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2262 {
2263         MovieTrackingCamera *camera= &tracking->camera;
2264
2265         if(camera->intrinsics == NULL)
2266                 camera->intrinsics= BKE_tracking_distortion_create();
2267
2268         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 1);
2269 }
2270
2271 ImBuf *BKE_tracking_distort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2272 {
2273         MovieTrackingCamera *camera= &tracking->camera;
2274
2275         if(camera->intrinsics == NULL)
2276                 camera->intrinsics= BKE_tracking_distortion_create();
2277
2278         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 0);
2279 }
2280
2281 /* area - which part of marker should be selected. see TRACK_AREA_* constants */
2282 void BKE_tracking_select_track(MovieTracking *tracking, MovieTrackingTrack *track, int area, int extend)
2283 {
2284         if(extend) {
2285                 BKE_tracking_track_flag(track, area, SELECT, 0);
2286         } else {
2287                 MovieTrackingTrack *cur= tracking->tracks.first;
2288
2289                 while(cur) {
2290                         if(cur==track) {
2291                                 BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2292                                 BKE_tracking_track_flag(cur, area, SELECT, 0);
2293                         }
2294                         else {
2295                                 BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2296                         }
2297
2298                         cur= cur->next;
2299                 }
2300         }
2301 }
2302
2303 void BKE_tracking_deselect_track(MovieTrackingTrack *track, int area)
2304 {
2305         BKE_tracking_track_flag(track, area, SELECT, 1);
2306 }