4989e8f1b550711d322ad35d21de706cb7caf9a4
[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                 float max_pyramid_level_factor = 1.0;
124                 if (track->tracker == TRACKER_KLT) {
125                         max_pyramid_level_factor = 1 << (track->pyramid_levels - 1);
126                 }
127                 for(a= 0; a<2; a++) {
128                         /* search shouldn't be resized smaller than pattern */
129                         track->search_min[a]= MIN2(pat_min[a], track->search_min[a]);
130                         track->search_max[a]= MAX2(pat_max[a], track->search_max[a]);
131                 }
132         }
133         else if(event==CLAMP_SEARCH_POS) {
134                 float dim[2];
135                 sub_v2_v2v2(dim, track->search_max, track->search_min);
136
137                 for(a= 0; a<2; a++) {
138                         /* search shouldn't be moved inside pattern */
139                         if(track->search_min[a] > pat_min[a]) {
140                                 track->search_min[a]= pat_min[a];
141                                 track->search_max[a]= track->search_min[a]+dim[a];
142                         }
143                         if(track->search_max[a] < pat_max[a]) {
144                                 track->search_max[a]= pat_max[a];
145                                 track->search_min[a]= track->search_max[a]-dim[a];
146                         }
147                 }
148         }
149
150         else if(event==CLAMP_PYRAMID_LEVELS || (event==CLAMP_SEARCH_DIM && track->tracker == TRACKER_KLT))  {
151                 float dim[2];
152                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
153                 {
154                         float search_ratio = 2.3f * max_pyramid_level_factor;
155
156                         /* resize the search area to something sensible based
157                          * on the number of pyramid levels */
158                         for(a= 0; a<2; a++) {
159                                 track->search_min[a]= search_ratio * track->pat_min[a];
160                                 track->search_max[a]= search_ratio * track->pat_max[a];
161                         }
162                 }
163         }
164
165         /* marker's center should be in center of pattern */
166         if(event==CLAMP_PAT_DIM || event==CLAMP_PAT_POS) {
167                 float dim[2];
168                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
169
170                 for(a= 0; a<2; a++) {
171                         track->pat_min[a]= -dim[a]/2.0f;
172                         track->pat_max[a]= dim[a]/2.0f;
173                 }
174         }
175 }
176
177 void BKE_tracking_track_flag(MovieTrackingTrack *track, int area, int flag, int clear)
178 {
179         if(area==TRACK_AREA_NONE)
180                 return;
181
182         if(clear) {
183                 if(area&TRACK_AREA_POINT)       track->flag&= ~flag;
184                 if(area&TRACK_AREA_PAT)         track->pat_flag&= ~flag;
185                 if(area&TRACK_AREA_SEARCH)      track->search_flag&= ~flag;
186         } else {
187                 if(area&TRACK_AREA_POINT)       track->flag|= flag;
188                 if(area&TRACK_AREA_PAT)         track->pat_flag|= flag;
189                 if(area&TRACK_AREA_SEARCH)      track->search_flag|= flag;
190         }
191 }
192
193 MovieTrackingTrack *BKE_tracking_add_track(MovieTracking *tracking, float x, float y,
194                         int framenr, int width, int height)
195 {
196         MovieTrackingTrack *track;
197         MovieTrackingMarker marker;
198
199         /* pick reasonable defaults */
200         float pat[2]= {5.5f, 5.5f}, search[2]= {25.5f, 25.5f}; /* TODO: move to default setting? */
201
202         pat[0] /= (float)width;
203         pat[1] /= (float)height;
204
205         search[0] /= (float)width;
206         search[1] /= (float)height;
207
208         track= MEM_callocN(sizeof(MovieTrackingTrack), "add_marker_exec track");
209         strcpy(track->name, "Track");
210
211         /* default to KLT tracker */
212         track->tracker = TRACKER_KLT;
213         track->pyramid_levels = 2;
214
215         /* set SAD defaults even though it's not selected by default */
216         track->minimum_correlation= 0.75f;
217
218         memset(&marker, 0, sizeof(marker));
219         marker.pos[0]= x;
220         marker.pos[1]= y;
221         marker.framenr= framenr;
222
223         copy_v2_v2(track->pat_max, pat);
224         negate_v2_v2(track->pat_min, pat);
225
226         copy_v2_v2(track->search_max, search);
227         negate_v2_v2(track->search_min, search);
228
229         BKE_tracking_insert_marker(track, &marker);
230
231         BLI_addtail(&tracking->tracks, track);
232         BKE_track_unique_name(tracking, track);
233
234         return track;
235 }
236
237 void BKE_tracking_insert_marker(MovieTrackingTrack *track, MovieTrackingMarker *marker)
238 {
239         MovieTrackingMarker *old_marker= BKE_tracking_get_marker(track, marker->framenr);
240
241         if(old_marker && old_marker->framenr==marker->framenr) {
242                 *old_marker= *marker;
243         } else {
244                 int a= track->markersnr;
245
246                 while(a--) {
247                         if(track->markers[a].framenr<marker->framenr)
248                                 break;
249                 }
250
251                 track->markersnr++;
252
253                 if(track->markers) track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
254                 else track->markers= MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
255
256                 memmove(track->markers+a+2, track->markers+a+1, (track->markersnr-a-2)*sizeof(MovieTrackingMarker));
257                 track->markers[a+1]= *marker;
258
259                 track->last_marker= a+1;
260         }
261 }
262
263 void BKE_tracking_delete_marker(MovieTrackingTrack *track, int framenr)
264 {
265         int a= 0;
266
267         while(a<track->markersnr) {
268                 if(track->markers[a].framenr==framenr) {
269                         if(track->markersnr>1) {
270                                 memmove(track->markers+a, track->markers+a+1, (track->markersnr-a-1)*sizeof(MovieTrackingMarker));
271                                 track->markersnr--;
272                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
273                         } else {
274                                 MEM_freeN(track->markers);
275                                 track->markers= NULL;
276                                 track->markersnr= 0;
277                         }
278
279                         break;
280                 }
281
282                 a++;
283         }
284 }
285
286 MovieTrackingMarker *BKE_tracking_get_marker(MovieTrackingTrack *track, int framenr)
287 {
288         int a= track->markersnr-1;
289
290         if(!track->markersnr)
291                 return NULL;
292
293         /* approximate pre-first framenr marker with first marker */
294         if(framenr<track->markers[0].framenr)
295                 return &track->markers[0];
296
297         if(track->last_marker<track->markersnr)
298                 a= track->last_marker;
299
300         if(track->markers[a].framenr<=framenr) {
301                 while(a<track->markersnr && track->markers[a].framenr<=framenr) {
302                         if(track->markers[a].framenr==framenr) {
303                                 track->last_marker= a;
304                                 return &track->markers[a];
305                         }
306                         a++;
307                 }
308
309                 /* if there's no marker for exact position, use nearest marker from left side */
310                 return &track->markers[a-1];
311         } else {
312                 while(a>=0 && track->markers[a].framenr>=framenr) {
313                         if(track->markers[a].framenr==framenr) {
314                                 track->last_marker= a;
315                                 return &track->markers[a];
316                         }
317
318                         a--;
319                 }
320
321                 /* if there's no marker for exact position, use nearest marker from left side */
322                 return &track->markers[a];
323         }
324
325         return NULL;
326 }
327
328 MovieTrackingMarker *BKE_tracking_ensure_marker(MovieTrackingTrack *track, int framenr)
329 {
330         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
331
332         if(marker && marker->framenr!=framenr) {
333                 MovieTrackingMarker marker_new;
334
335                 marker_new= *marker;
336                 marker_new.framenr= framenr;
337
338                 BKE_tracking_insert_marker(track, &marker_new);
339                 marker= BKE_tracking_get_marker(track, framenr);
340         }
341
342         return marker;
343 }
344
345 MovieTrackingMarker *BKE_tracking_exact_marker(MovieTrackingTrack *track, int framenr)
346 {
347         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
348
349         if(marker && marker->framenr!=framenr)
350                 return NULL;
351
352         return marker;
353 }
354
355 int BKE_tracking_has_marker(MovieTrackingTrack *track, int framenr)
356 {
357         return BKE_tracking_exact_marker(track, framenr) != 0;
358 }
359
360 void BKE_tracking_free_track(MovieTrackingTrack *track)
361 {
362         if(track->markers) MEM_freeN(track->markers);
363 }
364
365 MovieTrackingTrack *BKE_tracking_copy_track(MovieTrackingTrack *track)
366 {
367         MovieTrackingTrack *new_track= MEM_dupallocN(track);
368
369         new_track->next= new_track->prev= NULL;
370
371         if(new_track->markers)
372                 new_track->markers= MEM_dupallocN(new_track->markers);
373
374         return new_track;
375 }
376
377 static void put_disabled_marker(MovieTrackingTrack *track, MovieTrackingMarker *ref_marker, int before, int overwrite)
378 {
379         MovieTrackingMarker marker_new;
380
381         marker_new= *ref_marker;
382         marker_new.flag&= ~MARKER_TRACKED;
383         marker_new.flag|= MARKER_DISABLED;
384
385         if(before) marker_new.framenr--;
386         else marker_new.framenr++;
387
388         if(!BKE_tracking_has_marker(track, marker_new.framenr) || overwrite)
389                 BKE_tracking_insert_marker(track, &marker_new);
390 }
391
392 void BKE_tracking_clear_path(MovieTrackingTrack *track, int ref_frame, int action)
393 {
394         int a;
395
396         if(action==TRACK_CLEAR_REMAINED) {
397                 a= 1;
398                 while(a<track->markersnr) {
399                         if(track->markers[a].framenr>ref_frame) {
400                                 track->markersnr= a;
401                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
402
403                                 break;
404                         }
405
406                         a++;
407                 }
408
409                 if(track->markersnr)
410                         put_disabled_marker(track, &track->markers[track->markersnr-1], 0, 1);
411         } else if(action==TRACK_CLEAR_UPTO) {
412                 a= track->markersnr-1;
413                 while(a>=0) {
414                         if(track->markers[a].framenr<=ref_frame) {
415                                 memmove(track->markers, track->markers+a, (track->markersnr-a)*sizeof(MovieTrackingMarker));
416
417                                 track->markersnr= track->markersnr-a;
418                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
419
420                                 break;
421                         }
422
423                         a--;
424                 }
425
426                 if(track->markersnr)
427                         put_disabled_marker(track, &track->markers[0], 1, 1);
428         } else if(action==TRACK_CLEAR_ALL) {
429                 MovieTrackingMarker *marker, marker_new;
430
431                 marker= BKE_tracking_get_marker(track, ref_frame);
432                 marker_new= *marker;
433
434                 MEM_freeN(track->markers);
435                 track->markers= NULL;
436                 track->markersnr= 0;
437
438                 BKE_tracking_insert_marker(track, &marker_new);
439
440                 put_disabled_marker(track, &marker_new, 1, 1);
441                 put_disabled_marker(track, &marker_new, 0, 1);
442         }
443 }
444
445 int BKE_tracking_test_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
446 {
447         int a= 0, b= 0;
448         /* int tot= dst_track->markersnr+src_track->markersnr; */ /* UNUSED */
449         int count= 0;
450
451         while(a<src_track->markersnr || b<dst_track->markersnr) {
452                 if(b>=dst_track->markersnr) {
453                         a++;
454                         count++;
455                 }
456                 else if(a>=src_track->markersnr) {
457                         b++;
458                         count++;
459                 }
460                 else if(src_track->markers[a].framenr<dst_track->markers[b].framenr) {
461                         a++;
462                         count++;
463                 } else if(src_track->markers[a].framenr>dst_track->markers[b].framenr) {
464                         b++;
465                         count++;
466                 } else {
467                         if((src_track->markers[a].flag&MARKER_DISABLED)==0 && (dst_track->markers[b].flag&MARKER_DISABLED)==0)
468                                 return 0;
469
470                         a++;
471                         b++;
472                         count++;
473                 }
474         }
475
476         return count;
477 }
478
479 void BKE_tracking_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
480 {
481         int i, a= 0, b= 0, tot;
482         MovieTrackingMarker *markers;
483
484         tot= BKE_tracking_test_join_tracks(dst_track, src_track);
485
486         markers= MEM_callocN(tot*sizeof(MovieTrackingMarker), "tracking joined tracks");
487
488         for(i= 0; i<tot; i++) {
489                 if(b>=dst_track->markersnr) {
490                         markers[i]= src_track->markers[a++];
491                 }
492                 else if(a>=src_track->markersnr) {
493                         markers[i]= dst_track->markers[b++];
494                 }
495                 else if(src_track->markers[a].framenr<dst_track->markers[b].framenr) {
496                         markers[i]= src_track->markers[a++];
497                 } else if(src_track->markers[a].framenr>dst_track->markers[b].framenr) {
498                         markers[i]= dst_track->markers[b++];
499                 } else {
500                         if((src_track->markers[a].flag&MARKER_DISABLED)) markers[i]= dst_track->markers[b];
501                         else markers[i]= src_track->markers[a++];
502
503                         a++;
504                         b++;
505                 }
506         }
507
508         MEM_freeN(dst_track->markers);
509
510         dst_track->markers= markers;
511         dst_track->markersnr= tot;
512 }
513
514 void BKE_tracking_free(MovieTracking *tracking)
515 {
516         MovieTrackingTrack *track;
517
518         for(track= tracking->tracks.first; track; track= track->next) {
519                 BKE_tracking_free_track(track);
520         }
521
522         BLI_freelistN(&tracking->tracks);
523
524         if(tracking->reconstruction.cameras)
525                 MEM_freeN(tracking->reconstruction.cameras);
526
527         if(tracking->stabilization.scaleibuf)
528                 IMB_freeImBuf(tracking->stabilization.scaleibuf);
529
530         if(tracking->camera.intrinsics)
531                 BKE_tracking_distortion_destroy(tracking->camera.intrinsics);
532 }
533
534 /*********************** tracking *************************/
535
536 typedef struct TrackContext {
537         MovieTrackingTrack *track;
538
539 #ifdef WITH_LIBMV
540         float keyframed_pos[2];
541
542         /* ** KLT tracker ** */
543         struct libmv_RegionTracker *region_tracker;
544         float *patch;                   /* keyframed patch */
545
546         /* ** SAD tracker ** */
547         int patsize;                    /* size of pattern (currently only 16x16 due to libmv side) */
548         unsigned char *pattern; /* keyframed pattern */
549         unsigned char *warped;  /* warped version of reference */
550 #endif
551 } TrackContext;
552
553 typedef struct MovieTrackingContext {
554         MovieClipUser user;
555         MovieClip *clip;
556
557         int first_time, frames;
558
559         TrackContext *track_context;
560         int num_tracks;
561
562         GHash *hash;
563         MovieTrackingSettings settings;
564
565         short backwards, disable_failed;
566         int sync_frame;
567 } MovieTrackingContext;
568
569 MovieTrackingContext *BKE_tracking_context_new(MovieClip *clip, MovieClipUser *user, short backwards, short disable_failed)
570 {
571         MovieTrackingContext *context= MEM_callocN(sizeof(MovieTrackingContext), "trackingContext");
572         MovieTracking *tracking= &clip->tracking;
573         MovieTrackingSettings *settings= &tracking->settings;
574         MovieTrackingTrack *track;
575         TrackContext *track_context;
576
577         context->settings= *settings;
578         context->backwards= backwards;
579         context->disable_failed= disable_failed;
580         context->hash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "tracking trackHash");
581         context->sync_frame= user->framenr;
582         context->first_time= 1;
583
584         /* count */
585         track= tracking->tracks.first;
586         while(track) {
587                 if(TRACK_SELECTED(track) && (track->flag&TRACK_LOCKED)==0) {
588                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
589
590                         if((marker->flag&MARKER_DISABLED)==0)
591                                 context->num_tracks++;
592                 }
593
594                 track= track->next;
595         }
596
597         if(context->num_tracks) {
598                 int width, height;
599
600                 BKE_movieclip_get_size(clip, user, &width, &height);
601
602                 /* create tracking data */
603                 context->track_context= MEM_callocN(sizeof(TrackContext)*context->num_tracks, "tracking track_context");
604
605                 track_context= context->track_context;
606                 track= tracking->tracks.first;
607                 while(track) {
608                         if(TRACK_SELECTED(track) && (track->flag&TRACK_LOCKED)==0) {
609                                 MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
610
611                                 if((marker->flag&MARKER_DISABLED)==0) {
612                                         MovieTrackingTrack *new_track= BKE_tracking_copy_track(track);
613
614                                         track_context->track= new_track;
615 #ifdef WITH_LIBMV
616                                         {
617                                                 if(track_context->track->tracker==TRACKER_KLT) {
618                                                         float search_size_x= (track->search_max[0]-track->search_min[0])*width;
619                                                         float search_size_y= (track->search_max[1]-track->search_min[1])*height;
620                                                         float pattern_size_x= (track->pat_max[0]-track->pat_min[0])*width;
621                                                         float pattern_size_y= (track->pat_max[1]-track->pat_min[1])*height;
622
623                                                         /* compute the maximum pyramid size */
624                                                         double search_to_pattern_ratio= MIN2(search_size_x,  search_size_y)
625                                                                 / MAX2(pattern_size_x, pattern_size_y);
626                                                         double log2_search_to_pattern_ratio = log(floor(search_to_pattern_ratio)) / M_LN2;
627                                                         int max_pyramid_levels= floor(log2_search_to_pattern_ratio + 1);
628
629                                                         /* try to accomodate the user's choice of pyramid level in a way
630                                                          * that doesn't cause the coarsest pyramid pattern to be larger
631                                                          * than the search size */
632                                                         int level= MIN2(track_context->track->pyramid_levels, max_pyramid_levels);
633                                                         track_context->region_tracker= libmv_regionTrackerNew(100, level);
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 *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|= (marker->flag&MARKER_TRACKED)==0;
894
895                 if(is_keyframed) {
896                         framenr= marker->framenr;
897                         *marker_keyed= 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                                 int wndx, wndy;
1084                                 float *patch_new;
1085
1086                                 if(need_readjust) {
1087                                         /* calculate patch for keyframed position */
1088                                         ibuf= get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1089
1090                                         if(track_context->patch)
1091                                                 MEM_freeN(track_context->patch);
1092
1093                                         track_context->patch= get_search_floatbuf(ibuf, track, marker_keyed, &width, &height, track_context->keyframed_pos, origin);
1094
1095                                         IMB_freeImBuf(ibuf);
1096                                 }
1097
1098                                 patch_new= get_search_floatbuf(ibuf_new, track, marker, &width, &height, pos, origin);
1099
1100                                 x1= track_context->keyframed_pos[0];
1101                                 y1= track_context->keyframed_pos[1];
1102
1103                                 x2= pos[0];
1104                                 y2= pos[1];
1105
1106                                 wndx= (int)((track->pat_max[0]-track->pat_min[0])*ibuf_new->x)/2;
1107                                 wndy= (int)((track->pat_max[1]-track->pat_min[1])*ibuf_new->y)/2;
1108
1109                                 tracked= libmv_regionTrackerTrack(track_context->region_tracker, track_context->patch, patch_new,
1110                                                         width, height, MAX2(wndx, wndy), x1, y1, &x2, &y2);
1111
1112                                 MEM_freeN(patch_new);
1113                         }
1114                         else if(track_context->track->tracker==TRACKER_SAD) {
1115                                 unsigned char *image_new;
1116                                 float correlation;
1117                                 float warp[3][2]={{0}};
1118
1119                                 if(need_readjust) {
1120                                         unsigned char *image;
1121
1122                                         /* calculate pattern for keyframed position */
1123                                         ibuf= get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1124
1125                                         image= get_search_bytebuf(ibuf, track, marker_keyed, &width, &height, pos, origin);
1126
1127                                         memset(warp, 0, sizeof(warp));
1128                                         warp[0][0]= 1;
1129                                         warp[1][1]= 1;
1130                                         warp[2][0]= pos[0];
1131                                         warp[2][1]= pos[1];
1132
1133                                         /* pattern size is hardcoded to 16x16px in libmv */
1134                                         track_context->patsize= 16;
1135
1136                                         if(!track_context->pattern)
1137                                                 track_context->pattern= MEM_callocN(sizeof(unsigned char)*track_context->patsize*track_context->patsize, "trackking pattern");
1138
1139                                         libmv_SADSamplePattern(image, width, warp, track_context->pattern);
1140
1141                                         MEM_freeN(image);
1142                                         IMB_freeImBuf(ibuf);
1143                                 }
1144
1145                                 image_new= get_search_bytebuf(ibuf_new, track, marker, &width, &height, pos, origin);
1146
1147                                 if(track_context->warped==NULL) {
1148                                         unsigned char *image_old;
1149
1150                                         ibuf= get_frame_ibuf(context, curfra);
1151
1152                                         if(track_context->warped==NULL)
1153                                                 track_context->warped= MEM_callocN(sizeof(unsigned char)*track_context->patsize*track_context->patsize, "trackking warped");
1154
1155                                         image_old= get_search_bytebuf(ibuf, track, marker, &width, &height, pos, origin);
1156                                         get_warped(track_context, pos[0], pos[1], width, image_old);
1157                                         IMB_freeImBuf(ibuf);
1158                                         MEM_freeN(image_old);
1159                                 }
1160
1161                                 memset(warp, 0, sizeof(warp));
1162                                 warp[0][0]= 1;
1163                                 warp[1][1]= 1;
1164                                 warp[2][0]= pos[0];
1165                                 warp[2][1]= pos[1];
1166
1167                                 correlation= libmv_SADTrackerTrack(track_context->pattern, track_context->warped, image_new, width, width, height, warp);
1168
1169                                 x2= warp[2][0];
1170                                 y2= warp[2][1];
1171
1172                                 tracked= track_context->track->minimum_correlation < correlation;
1173
1174                                 if(tracked)
1175                                         get_warped(track_context, x2, y2, width, image_new);
1176
1177                                 MEM_freeN(image_new);
1178                         }
1179
1180                         coords_correct= !isnan(x2) && !isnan(y2) && finite(x2) && finite(y2);
1181                         if(coords_correct && (tracked || !context->disable_failed)) {
1182                                 if(context->first_time) {
1183                                         #pragma omp critical
1184                                         {
1185                                                 /* check if there's no keyframe/tracked markers before tracking marker.
1186                                                     if so -- create disabled marker before currently tracking "segment" */
1187                                                 put_disabled_marker(track, marker, 1, 0);
1188                                         }
1189                                 }
1190
1191                                 memset(&marker_new, 0, sizeof(marker_new));
1192
1193                                 if(!onbound) {
1194                                         marker_new.pos[0]= (origin[0]+x2)/ibuf_new->x;
1195                                         marker_new.pos[1]= (origin[1]+y2)/ibuf_new->y;
1196                                 } else {
1197                                         copy_v2_v2(marker_new.pos, marker->pos);
1198                                 }
1199
1200                                 marker_new.flag|= MARKER_TRACKED;
1201                                 marker_new.framenr= nextfra;
1202
1203                                 #pragma omp critical
1204                                 {
1205                                         BKE_tracking_insert_marker(track, &marker_new);
1206                                 }
1207
1208                                 /* make currently tracked segment be finished with disabled marker */
1209                                 #pragma omp critical
1210                                 {
1211                                         put_disabled_marker(track, &marker_new, 0, 0);
1212                                 }
1213                         } else {
1214                                 marker_new= *marker;
1215
1216                                 marker_new.framenr= nextfra;
1217                                 marker_new.flag|= MARKER_DISABLED;
1218
1219                                 #pragma omp critical
1220                                 {
1221                                         BKE_tracking_insert_marker(track, &marker_new);
1222                                 }
1223                         }
1224
1225                         ok= 1;
1226 #endif
1227                 }
1228         }
1229
1230         IMB_freeImBuf(ibuf_new);
1231
1232         context->first_time= 0;
1233         context->frames++;
1234
1235         return ok;
1236 }
1237
1238 #if WITH_LIBMV
1239 static struct libmv_Tracks *create_libmv_tracks(MovieTracking *tracking, int width, int height)
1240 {
1241         int tracknr= 0;
1242         MovieTrackingTrack *track;
1243         struct libmv_Tracks *tracks= libmv_tracksNew();
1244
1245         track= tracking->tracks.first;
1246         while(track) {
1247                 int a= 0;
1248
1249                 for(a= 0; a<track->markersnr; a++) {
1250                         MovieTrackingMarker *marker= &track->markers[a];
1251
1252                         if((marker->flag&MARKER_DISABLED)==0)
1253                                 libmv_tracksInsert(tracks, marker->framenr, tracknr,
1254                                                         marker->pos[0]*width, marker->pos[1]*height);
1255                 }
1256
1257                 track= track->next;
1258                 tracknr++;
1259         }
1260
1261         return tracks;
1262 }
1263
1264 static void retrieve_libmv_reconstruct_intrinscis(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
1265 {
1266         struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_ReconstructionExtractIntrinsics(libmv_reconstruction);
1267
1268         float aspy= 1.0f/tracking->camera.pixel_aspect;
1269
1270         double focal_length, principal_x, principal_y, k1, k2, k3;
1271         int width, height;
1272
1273         libmv_CameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
1274                         &k1, &k2, &k3, &width, &height);
1275
1276         tracking->camera.focal= focal_length;
1277         tracking->camera.principal[0]= principal_x;
1278
1279         /* todo: verify divide by aspy is correct */
1280         tracking->camera.principal[1]= principal_y / aspy;
1281         tracking->camera.k1= k1;
1282         tracking->camera.k2= k2;
1283 }
1284
1285 static int retrieve_libmv_reconstruct_tracks(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
1286 {
1287         int tracknr= 0;
1288         int sfra= INT_MAX, efra= INT_MIN, a, origin_set= 0;
1289         MovieTrackingTrack *track;
1290         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1291         MovieReconstructedCamera *reconstructed;
1292         float origin[3]= {0.0f, 0.0f, 0.0f};
1293         int ok= 1;
1294
1295         track= tracking->tracks.first;
1296         while(track) {
1297                 double pos[3];
1298
1299                 if(libmv_reporojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
1300                         track->bundle_pos[0]= pos[0];
1301                         track->bundle_pos[1]= pos[1];
1302                         track->bundle_pos[2]= pos[2];
1303
1304                         track->flag|= TRACK_HAS_BUNDLE;
1305                         track->error= libmv_reporojectionErrorForTrack(libmv_reconstruction, tracknr);
1306                 } else {
1307                         track->flag&= ~TRACK_HAS_BUNDLE;
1308                         ok= 0;
1309
1310                         printf("No bundle for track #%d '%s'\n", tracknr, track->name);
1311                 }
1312
1313                 if(track->markersnr) {
1314                         int first= 0, last= track->markersnr;
1315                         MovieTrackingMarker *first_marker= &track->markers[0];
1316                         MovieTrackingMarker *last_marker= &track->markers[track->markersnr-1];
1317
1318                         /* find first not-disabled marker */
1319                         while(first<track->markersnr-1 && first_marker->flag&MARKER_DISABLED) {
1320                                 first++;
1321                                 first_marker++;
1322                         }
1323
1324                         /* find last not-disabled marker */
1325                         while(last>=0 && last_marker->flag&MARKER_DISABLED) {
1326                                 last--;
1327                                 last_marker--;
1328                         }
1329
1330                         if(first<track->markersnr-1)
1331                                 sfra= MIN2(sfra, first_marker->framenr);
1332
1333                         if(last>=0)
1334                                 efra= MAX2(efra, last_marker->framenr);
1335                 }
1336
1337                 track= track->next;
1338                 tracknr++;
1339         }
1340
1341         if(reconstruction->cameras)
1342                 MEM_freeN(reconstruction->cameras);
1343
1344         reconstruction->camnr= 0;
1345         reconstruction->cameras= NULL;
1346         reconstructed= MEM_callocN((efra-sfra+1)*sizeof(MovieReconstructedCamera), "temp reconstructed camera");
1347
1348         for(a= sfra; a<=efra; a++) {
1349                 double matd[4][4];
1350
1351                 if(libmv_reporojectionCameraForImage(libmv_reconstruction, a, matd)) {
1352                         int i, j;
1353                         float mat[4][4];
1354                         float error= libmv_reporojectionErrorForImage(libmv_reconstruction, a);
1355
1356                         for(i=0; i<4; i++)
1357                                 for(j= 0; j<4; j++)
1358                                         mat[i][j]= matd[i][j];
1359
1360                         if(!origin_set) {
1361                                 copy_v3_v3(origin, mat[3]);
1362                                 origin_set= 1;
1363                         }
1364
1365                         if(origin_set)
1366                                 sub_v3_v3(mat[3], origin);
1367
1368                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
1369                         reconstructed[reconstruction->camnr].framenr= a;
1370                         reconstructed[reconstruction->camnr].error= error;
1371                         reconstruction->camnr++;
1372                 } else {
1373                         ok= 0;
1374                         printf("No camera for frame %d\n", a);
1375                 }
1376         }
1377
1378         if(reconstruction->camnr) {
1379                 reconstruction->cameras= MEM_callocN(reconstruction->camnr*sizeof(MovieReconstructedCamera), "reconstructed camera");
1380                 memcpy(reconstruction->cameras, reconstructed, reconstruction->camnr*sizeof(MovieReconstructedCamera));
1381         }
1382
1383         if(origin_set) {
1384                 track= tracking->tracks.first;
1385                 while(track) {
1386                         if(track->flag&TRACK_HAS_BUNDLE)
1387                                 sub_v3_v3(track->bundle_pos, origin);
1388
1389                         track= track->next;
1390                 }
1391         }
1392
1393         MEM_freeN(reconstructed);
1394
1395         return ok;
1396 }
1397
1398 static int retrieve_libmv_reconstruct(MovieTracking *tracking, struct libmv_Reconstruction *libmv_reconstruction)
1399 {
1400         /* take the intrinscis back from libmv */
1401         retrieve_libmv_reconstruct_intrinscis(tracking, libmv_reconstruction);
1402
1403         return retrieve_libmv_reconstruct_tracks(tracking, libmv_reconstruction);
1404 }
1405
1406 static int get_refine_intrinsics_flags(MovieTracking *tracking)
1407 {
1408         int refine= tracking->settings.refine_camera_intrinsics;
1409         int flags= 0;
1410
1411         if(refine&REFINE_FOCAL_LENGTH)
1412                 flags|= LIBMV_REFINE_FOCAL_LENGTH;
1413
1414         if(refine&REFINE_PRINCIPAL_POINT)
1415                 flags|= LIBMV_REFINE_PRINCIPAL_POINT;
1416
1417         if(refine&REFINE_RADIAL_DISTORTION_K1)
1418                 flags|= REFINE_RADIAL_DISTORTION_K1;
1419
1420         if(refine&REFINE_RADIAL_DISTORTION_K2)
1421                 flags|= REFINE_RADIAL_DISTORTION_K2;
1422
1423         return flags;
1424 }
1425
1426 static int count_tracks_on_both_keyframes(MovieTracking *tracking)
1427 {
1428         int tot= 0;
1429         int frame1= tracking->settings.keyframe1, frame2= tracking->settings.keyframe2;
1430         MovieTrackingTrack *track;
1431
1432         track= tracking->tracks.first;
1433         while(track) {
1434                 if(BKE_tracking_has_marker(track, frame1))
1435                         if(BKE_tracking_has_marker(track, frame2))
1436                                 tot++;
1437
1438                 track= track->next;
1439         }
1440
1441         return tot;
1442 }
1443 #endif
1444
1445 int BKE_tracking_can_solve(MovieTracking *tracking, char *error_msg, int error_size)
1446 {
1447 #if WITH_LIBMV
1448         if(count_tracks_on_both_keyframes(tracking)<8) {
1449                 BLI_strncpy(error_msg, "At least 8 tracks on both of keyframes are needed for reconstruction", error_size);
1450                 return 0;
1451         }
1452
1453         return 1;
1454 #else
1455         BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
1456
1457         return 0;
1458 #endif
1459 }
1460
1461 float BKE_tracking_solve_reconstruction(MovieTracking *tracking, int width, int height)
1462 {
1463 #if WITH_LIBMV
1464         {
1465                 MovieTrackingCamera *camera= &tracking->camera;
1466                 float aspy= 1.0f/tracking->camera.pixel_aspect;
1467                 struct libmv_Tracks *tracks= create_libmv_tracks(tracking, width, height*aspy);
1468                 struct libmv_Reconstruction *reconstruction = libmv_solveReconstruction(tracks,
1469                         tracking->settings.keyframe1, tracking->settings.keyframe2,
1470                         get_refine_intrinsics_flags(tracking),
1471                         camera->focal,
1472                         camera->principal[0], camera->principal[1]*aspy,
1473                         camera->k1, camera->k2, camera->k3);
1474                 float error= libmv_reprojectionError(reconstruction);
1475
1476                 tracking->reconstruction.error= error;
1477
1478                 if(!retrieve_libmv_reconstruct(tracking, reconstruction))
1479                         error= -1.0f;
1480
1481                 libmv_destroyReconstruction(reconstruction);
1482                 libmv_tracksDestroy(tracks);
1483
1484                 tracking->reconstruction.flag|= TRACKING_RECONSTRUCTED;
1485
1486                 return error;
1487         }
1488 #else
1489         (void)tracking;
1490         (void)width;
1491         (void)height;
1492
1493         return -1.0f;
1494 #endif
1495 }
1496
1497 void BKE_track_unique_name(MovieTracking *tracking, MovieTrackingTrack *track)
1498 {
1499         BLI_uniquename(&tracking->tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
1500 }
1501
1502 MovieTrackingTrack *BKE_tracking_named_track(MovieTracking *tracking, const char *name)
1503 {
1504         MovieTrackingTrack *track= tracking->tracks.first;
1505
1506         while(track) {
1507                 if(!strcmp(track->name, name))
1508                         return track;
1509
1510                 track= track->next;
1511         }
1512
1513         return NULL;
1514 }
1515
1516 static int reconstruction_camera_index(MovieTracking *tracking, int framenr, int nearest)
1517 {
1518         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1519         MovieReconstructedCamera *cameras= reconstruction->cameras;
1520         int a= 0, d= 1;
1521
1522         if(!reconstruction->camnr)
1523                 return -1;
1524
1525         if(framenr<cameras[0].framenr) {
1526                 if(nearest) return 0;
1527                 else return -1;
1528         }
1529
1530         if(framenr>cameras[reconstruction->camnr-1].framenr) {
1531                 if(nearest) return reconstruction->camnr-1;
1532                 else return -1;
1533         }
1534
1535         if(reconstruction->last_camera<reconstruction->camnr)
1536                 a= reconstruction->last_camera;
1537
1538         if(cameras[a].framenr>=framenr)
1539                 d= -1;
1540
1541         while(a>=0 && a<reconstruction->camnr) {
1542                 int cfra= cameras[a].framenr;
1543
1544                 /* check if needed framenr was "skipped" -- no data for requested frame */
1545
1546                 if(d>0 && cfra>framenr) {
1547                         /* interpolate with previous position */
1548                         if(nearest) return a-1;
1549                         else break;
1550                 }
1551
1552                 if(d<0 && cfra<framenr) {
1553                         /* interpolate with next position */
1554                         if(nearest) return a;
1555                         else break;
1556                 }
1557
1558                 if(cfra==framenr) {
1559                         reconstruction->last_camera= a;
1560
1561                         return a;
1562                 }
1563
1564                 a+= d;
1565         }
1566
1567         return -1;
1568 }
1569
1570 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking, int framenr)
1571 {
1572         int a= reconstruction_camera_index(tracking, framenr, 0);
1573
1574         if(a==-1)
1575                 return NULL;
1576
1577         return &tracking->reconstruction.cameras[a];
1578 }
1579
1580 void BKE_tracking_get_interpolated_camera(MovieTracking *tracking, int framenr, float mat[4][4])
1581 {
1582         MovieTrackingReconstruction *reconstruction= &tracking->reconstruction;
1583         MovieReconstructedCamera *cameras= reconstruction->cameras;
1584         int a= reconstruction_camera_index(tracking, framenr, 1);
1585
1586         if(a==-1) {
1587                 unit_m4(mat);
1588                 return;
1589         }
1590
1591         if(cameras[a].framenr!=framenr && a>0 && a<reconstruction->camnr-1) {
1592                 float t= ((float)framenr-cameras[a].framenr) / (cameras[a+1].framenr-cameras[a].framenr);
1593
1594                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a+1].mat, t);
1595         } else {
1596                 copy_m4_m4(mat, cameras[a].mat);
1597         }
1598 }
1599
1600 void BKE_get_tracking_mat(Scene *scene, Object *ob, float mat[4][4])
1601 {
1602         if(!ob) {
1603                 if(scene->camera) ob= scene->camera;
1604                 else ob= scene_find_camera(scene);
1605         }
1606
1607         if(ob)
1608                 where_is_object_mat(scene, ob, mat);
1609         else
1610                 unit_m4(mat);
1611 }
1612
1613 void BKE_tracking_camera_shift(MovieTracking *tracking, int winx, int winy, float *shiftx, float *shifty)
1614 {
1615         *shiftx= (0.5f*winx-tracking->camera.principal[0]) / winx;
1616         *shifty= (0.5f*winy-tracking->camera.principal[1]) / winx;
1617 }
1618
1619 void BKE_tracking_camera_to_blender(MovieTracking *tracking, Scene *scene, Camera *camera, int width, int height)
1620 {
1621         float focal= tracking->camera.focal;
1622
1623         camera->sensor_x= tracking->camera.sensor_width;
1624         camera->sensor_fit= CAMERA_SENSOR_FIT_AUTO;
1625         camera->lens= focal*camera->sensor_x/width;
1626
1627         scene->r.xsch= width*tracking->camera.pixel_aspect;
1628         scene->r.ysch= height;
1629
1630         scene->r.xasp= 1.0f;
1631         scene->r.yasp= 1.0f;
1632
1633         BKE_tracking_camera_shift(tracking, width, height, &camera->shiftx, &camera->shifty);
1634 }
1635
1636 void BKE_tracking_projection_matrix(MovieTracking *tracking, int framenr, int winx, int winy, float mat[4][4])
1637 {
1638         MovieReconstructedCamera *camera;
1639         float lens= tracking->camera.focal*tracking->camera.sensor_width/(float)winx;
1640         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
1641         float winmat[4][4];
1642         float ycor= 1.0f/tracking->camera.pixel_aspect;
1643         float shiftx, shifty, winside= MAX2(winx, winy);
1644
1645         BKE_tracking_camera_shift(tracking, winx, winy, &shiftx, &shifty);
1646
1647         clipsta= 0.1f;
1648         clipend= 1000.0f;
1649
1650         if(winx >= winy)
1651                 viewfac= (lens*winx)/tracking->camera.sensor_width;
1652         else
1653                 viewfac= (ycor*lens*winy)/tracking->camera.sensor_width;
1654
1655         pixsize= clipsta/viewfac;
1656
1657         left= -0.5f*(float)winx + shiftx*winside;
1658         bottom= -0.5f*(ycor)*(float)winy + shifty*winside;
1659         right=  0.5f*(float)winx + shiftx*winside;
1660         top=  0.5f*(ycor)*(float)winy + shifty*winside;
1661
1662         left *= pixsize;
1663         right *= pixsize;
1664         bottom *= pixsize;
1665         top *= pixsize;
1666
1667         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
1668
1669         camera= BKE_tracking_get_reconstructed_camera(tracking, framenr);
1670         if(camera) {
1671                 float imat[4][4];
1672
1673                 invert_m4_m4(imat, camera->mat);
1674                 mul_m4_m4m4(mat, imat, winmat);
1675         } else copy_m4_m4(mat, winmat);
1676 }
1677
1678 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
1679 {
1680         MovieTrackingCamera *camera= &tracking->camera;
1681
1682 #ifdef WITH_LIBMV
1683         double x, y;
1684         float aspy= 1.0f/tracking->camera.pixel_aspect;
1685
1686         /* normalize coords */
1687         x= (co[0]-camera->principal[0]) / camera->focal;
1688         y= (co[1]-camera->principal[1] * aspy) / camera->focal;
1689
1690         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
1691                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
1692
1693         /* result is in image coords already */
1694         nco[0]= x;
1695         nco[1]= y;
1696 #else
1697         (void)camera;
1698         (void)co;
1699         (void)nco;
1700 #endif
1701 }
1702
1703 void BKE_tracking_invert_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
1704 {
1705         MovieTrackingCamera *camera= &tracking->camera;
1706
1707 #ifdef WITH_LIBMV
1708         double x= co[0], y= co[1];
1709         float aspy= 1.0f/tracking->camera.pixel_aspect;
1710
1711         libmv_InvertIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
1712                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
1713
1714         nco[0]= x * camera->focal + camera->principal[0];
1715         nco[1]= y * camera->focal + camera->principal[1] * aspy;
1716 #else
1717         (void)camera;
1718         (void)co;
1719         (void)nco;
1720 #endif
1721 }
1722
1723 #ifdef WITH_LIBMV
1724 static int point_in_stroke(bGPDstroke *stroke, float x, float y)
1725 {
1726         int i, prev;
1727         int count= 0;
1728         bGPDspoint *points= stroke->points;
1729
1730         prev= stroke->totpoints-1;
1731
1732         for(i= 0; i<stroke->totpoints; i++) {
1733                 if((points[i].y<y && points[prev].y>=y) || (points[prev].y<y && points[i].y>=y)) {
1734                         float fac= (y-points[i].y)/(points[prev].y-points[i].y);
1735
1736                         if (points[i].x+fac*(points[prev].x-points[i].x)<x)
1737                                 count++;
1738                 }
1739
1740                 prev= i;
1741         }
1742
1743         return count%2;
1744 }
1745
1746 static int point_in_layer(bGPDlayer *layer, float x, float y)
1747 {
1748         bGPDframe *frame= layer->frames.first;
1749
1750         while(frame) {
1751                 bGPDstroke *stroke= frame->strokes.first;
1752                 while(stroke) {
1753                         if(point_in_stroke(stroke, x, y))
1754                                 return 1;
1755
1756                         stroke= stroke->next;
1757                 }
1758                 frame= frame->next;
1759         }
1760
1761         return 0;
1762 }
1763
1764 static void retrieve_libmv_features(MovieTracking *tracking, struct libmv_Features *features,
1765                         int framenr, int width, int height, bGPDlayer *layer, int place_outside_layer)
1766 {
1767         int a;
1768
1769         a= libmv_countFeatures(features);
1770         while(a--) {
1771                 MovieTrackingTrack *track;
1772                 double x, y, size, score;
1773                 int ok= 1;
1774                 float xu, yu;
1775
1776                 libmv_getFeature(features, a, &x, &y, &score, &size);
1777
1778                 xu= x/width;
1779                 yu= y/height;
1780
1781                 if(layer)
1782                         ok= point_in_layer(layer, xu, yu)!=place_outside_layer;
1783
1784                 if(ok) {
1785                         track= BKE_tracking_add_track(tracking, xu, yu, framenr, width, height);
1786                         track->flag|= SELECT;
1787                         track->pat_flag|= SELECT;
1788                         track->search_flag|= SELECT;
1789                 }
1790         }
1791 }
1792 #endif
1793
1794 void BKE_tracking_detect_fast(MovieTracking *tracking, ImBuf *ibuf,
1795                         int framenr, int margin, int min_trackness, int min_distance, bGPDlayer *layer,
1796                         int place_outside_layer)
1797 {
1798 #ifdef WITH_LIBMV
1799         struct libmv_Features *features;
1800         unsigned char *pixels= get_ucharbuf(ibuf);
1801
1802         features= libmv_detectFeaturesFAST(pixels, ibuf->x, ibuf->y, ibuf->x, margin, min_trackness, min_distance);
1803
1804         MEM_freeN(pixels);
1805
1806         retrieve_libmv_features(tracking, features, framenr, ibuf->x, ibuf->y, layer, place_outside_layer);
1807
1808         libmv_destroyFeatures(features);
1809 #else
1810         (void)tracking;
1811         (void)ibuf;
1812         (void)framenr;
1813         (void)margin;
1814         (void)min_trackness;
1815         (void)min_distance;
1816         (void)layer;
1817         (void)place_outside_layer;
1818 #endif
1819 }
1820
1821 MovieTrackingTrack *BKE_tracking_indexed_track(MovieTracking *tracking, int tracknr)
1822 {
1823         MovieTrackingTrack *track= tracking->tracks.first;
1824         int cur= 1;
1825
1826         while(track) {
1827                 if(track->flag&TRACK_HAS_BUNDLE) {
1828                         if(cur==tracknr)
1829                                 return track;
1830
1831                         cur++;
1832                 }
1833
1834                 track= track->next;
1835         }
1836
1837         return NULL;
1838 }
1839
1840 static int stabilization_median_point(MovieTracking *tracking, int framenr, float median[2])
1841 {
1842         int ok= 0;
1843         float min[2], max[2];
1844         MovieTrackingTrack *track;
1845
1846         INIT_MINMAX2(min, max);
1847
1848         track= tracking->tracks.first;
1849         while(track) {
1850                 if(track->flag&TRACK_USE_2D_STAB) {
1851                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
1852
1853                         DO_MINMAX2(marker->pos, min, max);
1854
1855                         ok= 1;
1856                 }
1857
1858                 track= track->next;
1859         }
1860
1861         median[0]= (max[0]+min[0])/2.0f;
1862         median[1]= (max[1]+min[1])/2.0f;
1863
1864         return ok;
1865 }
1866
1867 static void calculate_stabdata(MovieTracking *tracking, int framenr, float width, float height,
1868                         float firstmedian[2], float median[2], float loc[2], float *scale, float *angle)
1869 {
1870         MovieTrackingStabilization *stab= &tracking->stabilization;
1871
1872         *scale= (stab->scale-1.0f)*stab->scaleinf+1.0f;
1873         *angle= 0.0f;
1874
1875         loc[0]= (firstmedian[0]-median[0])*width*(*scale);
1876         loc[1]= (firstmedian[1]-median[1])*height*(*scale);
1877
1878         mul_v2_fl(loc, stab->locinf);
1879
1880         if(stab->rot_track && stab->rotinf) {
1881                 MovieTrackingMarker *marker;
1882                 float a[2], b[2];
1883                 float x0= (float)width/2.0f, y0= (float)height/2.0f;
1884                 float x= median[0]*width, y= median[1]*height;
1885
1886                 marker= BKE_tracking_get_marker(stab->rot_track, 1);
1887                 sub_v2_v2v2(a, marker->pos, firstmedian);
1888                 a[0]*= width;
1889                 a[1]*= height;
1890
1891                 marker= BKE_tracking_get_marker(stab->rot_track, framenr);
1892                 sub_v2_v2v2(b, marker->pos, median);
1893                 b[0]*= width;
1894                 b[1]*= height;
1895
1896                 *angle= -atan2(a[0]*b[1]-a[1]*b[0], a[0]*b[0]+a[1]*b[1]);
1897                 *angle*= stab->rotinf;
1898
1899                 /* convert to rotation around image center */
1900                 loc[0]-= (x0 + (x-x0)*cosf(*angle)-(y-y0)*sinf(*angle) - x)*(*scale);
1901                 loc[1]-= (y0 + (x-x0)*sinf(*angle)+(y-y0)*cosf(*angle) - y)*(*scale);
1902         }
1903 }
1904
1905 static float stabilization_auto_scale_factor(MovieTracking *tracking, int width, int height)
1906 {
1907         float firstmedian[2];
1908         MovieTrackingStabilization *stab= &tracking->stabilization;
1909
1910         if(stab->ok)
1911                 return stab->scale;
1912
1913         if(stabilization_median_point(tracking, 1, firstmedian)) {
1914                 int sfra= INT_MAX, efra= INT_MIN, cfra;
1915                 float delta[2]= {0.0f, 0.0f}, scalex= 1.0f, scaley= 1.0f;
1916                 MovieTrackingTrack *track;
1917
1918                 stab->scale= 1.0f;
1919
1920                 track= tracking->tracks.first;
1921                 while(track) {
1922                         if(track->flag&TRACK_USE_2D_STAB || track==stab->rot_track) {
1923                                 if(track->markersnr) {
1924                                         sfra= MIN2(sfra, track->markers[0].framenr);
1925                                         efra= MAX2(efra, track->markers[track->markersnr-1].framenr);
1926                                 }
1927                         }
1928
1929                         track= track->next;
1930                 }
1931
1932                 for(cfra=sfra; cfra<=efra; cfra++) {
1933                         float median[2], near[2];
1934                         float loc[2], scale, angle;
1935
1936                         stabilization_median_point(tracking, cfra, median);
1937
1938                         calculate_stabdata(tracking, cfra, width, height, firstmedian, median,
1939                                                 loc, &scale, &angle);
1940
1941                         if(angle==0.0f) {
1942                                 loc[0]= fabsf(loc[0]);
1943                                 loc[1]= fabsf(loc[1]);
1944
1945                                 delta[0]= MAX2(delta[0], loc[0]);
1946                                 delta[1]= MAX2(delta[1], loc[1]);
1947
1948                                 near[0]= MIN2(median[0], 1.0f-median[0]);
1949                                 near[1]= MIN2(median[1], 1.0f-median[1]);
1950                                 near[0]= MAX2(near[0], 0.05f);
1951                                 near[1]= MAX2(near[1], 0.05f);
1952
1953                                 scalex= 1.0f+delta[0]/(near[0]*width);
1954                                 scaley= 1.0f+delta[1]/(near[1]*height);
1955                         } else {
1956                                 int i;
1957                                 float mat[4][4];
1958                                 float points[4][2]={{0.0f, 0.0f}, {0.0f, height}, {width, height}, {width, 0.0f}};
1959
1960                                 BKE_tracking_stabdata_to_mat4(width, height, loc, scale, angle, mat);
1961
1962                                 for(i= 0; i<4; i++) {
1963                                         int j;
1964                                         float a[3]= {0.0f, 0.0f, 0.0f}, b[3]= {0.0f, 0.0f, 0.0f};
1965
1966                                         copy_v3_v3(a, points[i]);
1967                                         copy_v3_v3(b, points[(i+1)%4]);
1968
1969                                         mul_m4_v3(mat, a);
1970                                         mul_m4_v3(mat, b);
1971
1972                                         for(j= 0; j<4; j++) {
1973                                                 float point[3]= {points[j][0], points[j][1], 0.0f};
1974                                                 float v1[3], v2[3];
1975
1976                                                 sub_v3_v3v3(v1, b, a);
1977                                                 sub_v3_v3v3(v2, point, a);
1978
1979                                                 if(cross_v2v2(v1, v2) >= 0.0f) {
1980                                                         float dist= dist_to_line_v2(point, a, b);
1981                                                         if(i%2==0) {
1982                                                                 scalex= MAX2(scalex, (width+2*dist)/width);
1983                                                         } else {
1984                                                                 scaley= MAX2(scaley, (height+2*dist)/height);
1985                                                         }
1986                                                 }
1987                                         }
1988                                 }
1989                         }
1990                 }
1991
1992                 stab->scale= MAX2(scalex, scaley);
1993
1994                 if(stab->maxscale>0.0f)
1995                         stab->scale= MIN2(stab->scale, stab->maxscale);
1996         } else {
1997                 stab->scale= 1.0f;
1998         }
1999
2000         stab->ok= 1;
2001
2002         return stab->scale;
2003 }
2004
2005 static ImBuf* stabilize_alloc_ibuf(ImBuf *cacheibuf, ImBuf *srcibuf, int fill)
2006 {
2007         int flags;
2008
2009         if(cacheibuf && (cacheibuf->x != srcibuf->x || cacheibuf->y != srcibuf->y)) {
2010                 IMB_freeImBuf(cacheibuf);
2011                 cacheibuf= NULL;
2012         }
2013
2014         flags= IB_rect;
2015
2016         if(srcibuf->rect_float)
2017                 flags|= IB_rectfloat;
2018
2019         if(cacheibuf) {
2020                 if(fill) {
2021                         float col[4]= {0.0f, 0.0f, 0.0f, 0.0f};
2022                         IMB_rectfill(cacheibuf, col);
2023                 }
2024         }
2025         else {
2026                 cacheibuf= IMB_allocImBuf(srcibuf->x, srcibuf->y, srcibuf->depth, flags);
2027                 cacheibuf->profile= srcibuf->profile;
2028         }
2029
2030         return cacheibuf;
2031 }
2032
2033 void BKE_tracking_stabilization_data(MovieTracking *tracking, int framenr, int width, int height, float loc[2], float *scale, float *angle)
2034 {
2035         float firstmedian[2], median[2];
2036         MovieTrackingStabilization *stab= &tracking->stabilization;
2037
2038         if((stab->flag&TRACKING_2D_STABILIZATION)==0) {
2039                 zero_v2(loc);
2040                 *scale= 1.0f;
2041                 *angle= 0.0f;
2042
2043                 return;
2044         }
2045
2046         if(stabilization_median_point(tracking, 1, firstmedian)) {
2047                 stabilization_median_point(tracking, framenr, median);
2048
2049                 if((stab->flag&TRACKING_AUTOSCALE)==0)
2050                         stab->scale= 1.0f;
2051
2052                 if(!stab->ok) {
2053                         if(stab->flag&TRACKING_AUTOSCALE)
2054                                 stabilization_auto_scale_factor(tracking, width, height);
2055
2056                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2057
2058                         stab->ok= 1;
2059                 } else {
2060                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
2061                 }
2062         } else {
2063                 zero_v2(loc);
2064                 *scale= 1.0f;
2065                 *angle= 0.0f;
2066         }
2067 }
2068
2069 ImBuf *BKE_tracking_stabilize(MovieTracking *tracking, int framenr, ImBuf *ibuf, float loc[2], float *scale, float *angle)
2070 {
2071         float tloc[2], tscale, tangle;
2072         MovieTrackingStabilization *stab= &tracking->stabilization;
2073         ImBuf *tmpibuf;
2074         float width= ibuf->x, height= ibuf->y;
2075
2076         if(loc)         copy_v2_v2(tloc, loc);
2077         if(scale)       tscale= *scale;
2078
2079         if((stab->flag&TRACKING_2D_STABILIZATION)==0) {
2080                 if(loc)         zero_v2(loc);
2081                 if(scale)       *scale= 1.0f;
2082
2083                 return ibuf;
2084         }
2085
2086         BKE_tracking_stabilization_data(tracking, framenr, width, height, tloc, &tscale, &tangle);
2087
2088         tmpibuf= stabilize_alloc_ibuf(NULL, ibuf, 1);
2089
2090         /* scale would be handled by matrix transformation when angle is non-zero */
2091         if(tscale!=1.0f && tangle==0.0f) {
2092                 ImBuf *scaleibuf;
2093
2094                 stabilization_auto_scale_factor(tracking, width, height);
2095
2096                 scaleibuf= stabilize_alloc_ibuf(stab->scaleibuf, ibuf, 0);
2097                 stab->scaleibuf= scaleibuf;
2098
2099                 IMB_rectcpy(scaleibuf, ibuf, 0, 0, 0, 0, ibuf->x, ibuf->y);
2100                 IMB_scalefastImBuf(scaleibuf, ibuf->x*tscale, ibuf->y*tscale);
2101
2102                 ibuf= scaleibuf;
2103         }
2104
2105         if(tangle==0.0f) {
2106                 /* if angle is zero, then it's much faster to use rect copy
2107                    but could be issues with subpixel precisions */
2108                 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);
2109         } else {
2110                 float mat[4][4];
2111                 int i, j;
2112
2113                 BKE_tracking_stabdata_to_mat4(ibuf->x, ibuf->y, tloc, tscale, tangle, mat);
2114                 invert_m4(mat);
2115
2116                 for(j=0; j<tmpibuf->y; j++) {
2117                         for(i=0; i<tmpibuf->x;i++) {
2118                                 float vec[3]= {i, j, 0};
2119
2120                                 mul_v3_m4v3(vec, mat, vec);
2121
2122                                 /* TODO: add selector for interpolation method */
2123                                 neareast_interpolation(ibuf, tmpibuf, vec[0], vec[1], i, j);
2124                         }
2125                 }
2126         }
2127
2128         tmpibuf->userflags|= IB_MIPMAP_INVALID;
2129
2130         if(tmpibuf->rect_float)
2131                 tmpibuf->userflags|= IB_RECT_INVALID;
2132
2133         if(loc)         copy_v2_v2(loc, tloc);
2134         if(scale)       *scale= tscale;
2135         if(angle)       *angle= tangle;
2136
2137         return tmpibuf;
2138 }
2139
2140 void BKE_tracking_stabdata_to_mat4(int width, int height, float loc[2], float scale, float angle, float mat[4][4])
2141 {
2142         float lmat[4][4], rmat[4][4], smat[4][4], cmat[4][4], icmat[4][4];
2143         float svec[3]= {scale, scale, scale};
2144
2145         unit_m4(rmat);
2146         unit_m4(lmat);
2147         unit_m4(smat);
2148         unit_m4(cmat);
2149
2150         /* image center as rotation center */
2151         cmat[3][0]= (float)width/2.0f;
2152         cmat[3][1]= (float)height/2.0f;
2153         invert_m4_m4(icmat, cmat);
2154
2155         size_to_mat4(smat, svec);               /* scale matrix */
2156         add_v2_v2(lmat[3], loc);                /* tranlation matrix */
2157         rotate_m4(rmat, 'Z', angle);    /* rotation matrix */
2158
2159         /* compose transformation matrix */
2160         mul_serie_m4(mat, lmat, cmat, rmat, smat, icmat, NULL, NULL, NULL);
2161 }
2162
2163 MovieDistortion *BKE_tracking_distortion_create(void)
2164 {
2165         MovieDistortion *distortion;
2166
2167         distortion= MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2168
2169         return distortion;
2170 }
2171
2172 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
2173 {
2174         MovieDistortion *new_distortion;
2175
2176         new_distortion= MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
2177
2178 #ifdef WITH_LIBMV
2179         new_distortion->intrinsics= libmv_CameraIntrinsicsCopy(distortion->intrinsics);
2180 #else
2181         (void)distortion;
2182 #endif
2183
2184         return new_distortion;
2185 }
2186
2187 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking, int width, int height)
2188 {
2189         MovieTrackingCamera *camera= &tracking->camera;
2190         float aspy= 1.0f/tracking->camera.pixel_aspect;
2191
2192 #ifdef WITH_LIBMV
2193         if(!distortion->intrinsics) {
2194                 distortion->intrinsics= libmv_CameraIntrinsicsNew(camera->focal,
2195                                 camera->principal[0], camera->principal[1] * aspy,
2196                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2197         } else {
2198                 libmv_CameraIntrinsicsUpdate(distortion->intrinsics, camera->focal,
2199                                 camera->principal[0], camera->principal[1] * aspy,
2200                                 camera->k1, camera->k2, camera->k3, width, height * aspy);
2201         }
2202 #else
2203         (void)distortion;
2204         (void)width;
2205         (void)height;
2206         (void)camera;
2207         (void)aspy;
2208 #endif
2209 }
2210
2211 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking,
2212                         ImBuf *ibuf, int width, int height, float overscan, int undistort)
2213 {
2214         ImBuf *resibuf;
2215
2216         BKE_tracking_distortion_update(distortion, tracking, width, height);
2217
2218         resibuf= IMB_dupImBuf(ibuf);
2219
2220         if(ibuf->rect_float) {
2221 #ifdef WITH_LIBMV
2222                 if(undistort) {
2223                         libmv_CameraIntrinsicsUndistortFloat(distortion->intrinsics,
2224                                                 ibuf->rect_float, resibuf->rect_float,
2225                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2226                 } else {
2227                         libmv_CameraIntrinsicsDistortFloat(distortion->intrinsics,
2228                                                 ibuf->rect_float, resibuf->rect_float,
2229                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2230                 }
2231 #endif
2232
2233                 ibuf->userflags|= IB_RECT_INVALID;
2234         } else {
2235 #ifdef WITH_LIBMV
2236                 if(undistort) {
2237                                 libmv_CameraIntrinsicsUndistortByte(distortion->intrinsics,
2238                                                         (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2239                                                         ibuf->x, ibuf->y, overscan, ibuf->channels);
2240                 } else {
2241                         libmv_CameraIntrinsicsDistortByte(distortion->intrinsics,
2242                                                 (unsigned char*)ibuf->rect, (unsigned char*)resibuf->rect,
2243                                                 ibuf->x, ibuf->y, overscan, ibuf->channels);
2244                 }
2245 #endif
2246         }
2247
2248 #ifndef WITH_LIBMV
2249         (void)overscan;
2250         (void)undistort;
2251 #endif
2252
2253         return resibuf;
2254 }
2255
2256 void BKE_tracking_distortion_destroy(MovieDistortion *distortion)
2257 {
2258 #ifdef WITH_LIBMV
2259         libmv_CameraIntrinsicsDestroy(distortion->intrinsics);
2260 #endif
2261
2262         MEM_freeN(distortion);
2263 }
2264
2265 ImBuf *BKE_tracking_undistort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2266 {
2267         MovieTrackingCamera *camera= &tracking->camera;
2268
2269         if(camera->intrinsics == NULL)
2270                 camera->intrinsics= BKE_tracking_distortion_create();
2271
2272         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 1);
2273 }
2274
2275 ImBuf *BKE_tracking_distort(MovieTracking *tracking, ImBuf *ibuf, int width, int height, float overscan)
2276 {
2277         MovieTrackingCamera *camera= &tracking->camera;
2278
2279         if(camera->intrinsics == NULL)
2280                 camera->intrinsics= BKE_tracking_distortion_create();
2281
2282         return BKE_tracking_distortion_exec(camera->intrinsics, tracking, ibuf, width, height, overscan, 0);
2283 }
2284
2285 /* area - which part of marker should be selected. see TRACK_AREA_* constants */
2286 void BKE_tracking_select_track(MovieTracking *tracking, MovieTrackingTrack *track, int area, int extend)
2287 {
2288         if(extend) {
2289                 BKE_tracking_track_flag(track, area, SELECT, 0);
2290         } else {
2291                 MovieTrackingTrack *cur= tracking->tracks.first;
2292
2293                 while(cur) {
2294                         if(cur==track) {
2295                                 BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2296                                 BKE_tracking_track_flag(cur, area, SELECT, 0);
2297                         }
2298                         else {
2299                                 BKE_tracking_track_flag(cur, TRACK_AREA_ALL, SELECT, 1);
2300                         }
2301
2302                         cur= cur->next;
2303                 }
2304         }
2305 }
2306
2307 void BKE_tracking_deselect_track(MovieTrackingTrack *track, int area)
2308 {
2309         BKE_tracking_track_flag(track, area, SELECT, 1);
2310 }