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