Camera tracking integration
[blender.git] / source / blender / blenkernel / intern / tracking.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2011 Blender Foundation.
21  * All rights reserved.
22  *
23  * Contributor(s): Blender Foundation,
24  *                 Sergey Sharybin
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file blender/blenkernel/intern/tracking.c
30  *  \ingroup bke
31  */
32
33 #include <stddef.h>
34 #include <limits.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_movieclip_types.h"
39 #include "DNA_object_types.h"   /* SELECT */
40 #include "DNA_scene_types.h"
41
42 #include "BLI_utildefines.h"
43 #include "BLI_math.h"
44 #include "BLI_listbase.h"
45 #include "BLI_ghash.h"
46
47 #include "BKE_global.h"
48 #include "BKE_tracking.h"
49 #include "BKE_movieclip.h"
50 #include "BKE_object.h"
51 #include "BKE_scene.h"
52
53 #include "IMB_imbuf_types.h"
54 #include "IMB_imbuf.h"
55
56 #ifdef WITH_LIBMV
57 #include "libmv-capi.h"
58 #endif
59
60 /*********************** common functions *************************/
61
62 void BKE_tracking_clamp_track(MovieTrackingTrack *track, int event)
63 {
64         int a;
65
66         /* sort */
67         for(a= 0; a<2; a++) {
68                 if(track->pat_min[a]>track->pat_max[a])
69                         SWAP(float, track->pat_min[a], track->pat_max[a]);
70
71                 if(track->search_min[a]>track->search_max[a])
72                         SWAP(float, track->search_min[a], track->search_max[a]);
73         }
74
75         if(event==CLAMP_PAT_DIM) {
76                 for(a= 0; a<2; a++) {
77                         /* pattern shouldn't be resized bigger than search */
78                         track->pat_min[a]= MAX2(track->pat_min[a], track->search_min[a]);
79                         track->pat_max[a]= MIN2(track->pat_max[a], track->search_max[a]);
80                 }
81         }
82         else if(event==CLAMP_PAT_POS) {
83                 float dim[2];
84                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
85
86                 for(a= 0; a<2; a++) {
87                         /* pattern shouldn't be moved outside of search */
88                         if(track->pat_min[a] < track->search_min[a]) {
89                                 track->pat_min[a]= track->search_min[a];
90                                 track->pat_max[a]= track->pat_min[a]+dim[a];
91                         }
92                         if(track->pat_max[a] > track->search_max[a]) {
93                                 track->pat_max[a]= track->search_max[a];
94                                 track->pat_min[a]= track->pat_max[a]-dim[a];
95                         }
96                 }
97         }
98         else if(event==CLAMP_SEARCH_DIM) {
99                 for(a= 0; a<2; a++) {
100                         /* search shouldn't be resized smaller than pattern */
101                         track->search_min[a]= MIN2(track->pat_min[a], track->search_min[a]);
102                         track->search_max[a]= MAX2(track->pat_max[a], track->search_max[a]);
103                 }
104         }
105         else if(event==CLAMP_SEARCH_POS) {
106                 float dim[2];
107                 sub_v2_v2v2(dim, track->search_max, track->search_min);
108
109                 for(a= 0; a<2; a++) {
110                         /* search shouldn't be moved inside pattern */
111                         if(track->search_min[a] > track->pat_min[a]) {
112                                 track->search_min[a]= track->pat_min[a];
113                                 track->search_max[a]= track->search_min[a]+dim[a];
114                         }
115                         if(track->search_max[a] < track->pat_max[a]) {
116                                 track->search_max[a]= track->pat_max[a];
117                                 track->search_min[a]= track->search_max[a]-dim[a];
118                         }
119                 }
120         }
121
122         /* marker's center should be inside pattern */
123         if(event==CLAMP_PAT_DIM || event==CLAMP_PAT_POS) {
124                 float dim[2];
125                 sub_v2_v2v2(dim, track->pat_max, track->pat_min);
126
127                 for(a= 0; a<2; a++) {
128                         if(track->pat_min[a] > 0.0f) {
129                                 track->pat_min[a]= 0.0f;
130                                 track->pat_max[a]= dim[a];
131                         }
132                         if(track->pat_max[a] < 0.0f) {
133                                 track->pat_max[a]= 0.0f;
134                                 track->pat_min[a]= -dim[a];
135                         }
136                 }
137         }
138 }
139
140 void BKE_tracking_track_flag(MovieTrackingTrack *track, int area, int flag, int clear)
141 {
142         if(area==TRACK_AREA_NONE)
143                 return;
144
145         if(clear) {
146                 if(area&TRACK_AREA_POINT)       track->flag&= ~flag;
147                 if(area&TRACK_AREA_PAT)         track->pat_flag&= ~flag;
148                 if(area&TRACK_AREA_SEARCH)      track->search_flag&= ~flag;
149         } else {
150                 if(area&TRACK_AREA_POINT)       track->flag|= flag;
151                 if(area&TRACK_AREA_PAT)         track->pat_flag|= flag;
152                 if(area&TRACK_AREA_SEARCH)      track->search_flag|= flag;
153         }
154 }
155
156 MovieTrackingTrack *BKE_tracking_add_track(MovieTracking *tracking, float x, float y,
157                         int framenr, int width, int height)
158 {
159         MovieTrackingTrack *track;
160         MovieTrackingMarker marker;
161         float pat[2]= {5.5f, 5.5f}, search[2]= {80.5f, 80.5f}; /* TODO: move to default setting? */
162
163         pat[0] /= (float)width;
164         pat[1] /= (float)height;
165
166         search[0] /= (float)width;
167         search[1] /= (float)height;
168
169         track= MEM_callocN(sizeof(MovieTrackingTrack), "add_marker_exec track");
170         strcpy(track->name, "Track");
171
172         memset(&marker, 0, sizeof(marker));
173         marker.pos[0]= x;
174         marker.pos[1]= y;
175         marker.framenr= framenr;
176
177         copy_v2_v2(track->pat_max, pat);
178         negate_v2_v2(track->pat_min, pat);
179
180         copy_v2_v2(track->search_max, search);
181         negate_v2_v2(track->search_min, search);
182
183         BKE_tracking_insert_marker(track, &marker);
184
185         BLI_addtail(&tracking->tracks, track);
186         BKE_track_unique_name(tracking, track);
187
188         return track;
189 }
190
191 void BKE_tracking_insert_marker(MovieTrackingTrack *track, MovieTrackingMarker *marker)
192 {
193         MovieTrackingMarker *old_marker= BKE_tracking_get_marker(track, marker->framenr);
194
195         if(old_marker && old_marker->framenr==marker->framenr) {
196                 *old_marker= *marker;
197         } else {
198                 int a= track->markersnr;
199
200                 while(a--) {
201                         if(track->markers[a].framenr<marker->framenr)
202                                 break;
203                 }
204
205                 track->markersnr++;
206
207                 if(track->markers) track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
208                 else track->markers= MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
209
210                 memmove(track->markers+a+2, track->markers+a+1, (track->markersnr-a-2)*sizeof(MovieTrackingMarker));
211                 track->markers[a+1]= *marker;
212
213                 track->last_marker= a+1;
214         }
215 }
216
217 void BKE_tracking_delete_marker(MovieTrackingTrack *track, int framenr)
218 {
219         int a= 1;
220
221         while(a<track->markersnr) {
222                 if(track->markers[a].framenr==framenr) {
223                         if(track->markersnr>1) {
224                                 memmove(track->markers+a, track->markers+a+1, (track->markersnr-a-1)*sizeof(MovieTrackingMarker));
225                                 track->markersnr--;
226                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
227                         } else {
228                                 MEM_freeN(track->markers);
229                                 track->markers= NULL;
230                                 track->markersnr= 0;
231                         }
232
233                         break;
234                 }
235
236                 a++;
237         }}
238
239 MovieTrackingMarker *BKE_tracking_get_marker(MovieTrackingTrack *track, int framenr)
240 {
241         int a= track->markersnr-1;
242
243         if(!track->markersnr)
244                 return NULL;
245
246         /* approximate pre-first framenr marker with first marker */
247         if(framenr<track->markers[0].framenr)
248                 return &track->markers[0];
249
250         if(track->last_marker<track->markersnr)
251                 a= track->last_marker;
252
253         if(track->markers[a].framenr<=framenr) {
254                 while(a<track->markersnr && track->markers[a].framenr<=framenr) {
255                         if(track->markers[a].framenr==framenr) {
256                                 track->last_marker= a;
257                                 return &track->markers[a];
258                         }
259                         a++;
260                 }
261
262                 /* if there's no marker for exact position, use nearest marker from left side */
263                 return &track->markers[a-1];
264         } else {
265                 while(a>=0 && track->markers[a].framenr>=framenr) {
266                         if(track->markers[a].framenr==framenr) {
267                                 track->last_marker= a;
268                                 return &track->markers[a];
269                         }
270
271                         a--;
272                 }
273
274                 /* if there's no marker for exact position, use nearest marker from left side */
275                 return &track->markers[a];
276         }
277
278         return NULL;
279 }
280
281 MovieTrackingMarker *BKE_tracking_ensure_marker(MovieTrackingTrack *track, int framenr)
282 {
283         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
284
285         if(marker && marker->framenr!=framenr) {
286                 MovieTrackingMarker marker_new;
287
288                 marker_new= *marker;
289                 marker_new.framenr= framenr;
290
291                 BKE_tracking_insert_marker(track, &marker_new);
292                 marker= BKE_tracking_get_marker(track, framenr);
293         }
294
295         return marker;
296 }
297
298 MovieTrackingMarker *BKE_tracking_exact_marker(MovieTrackingTrack *track, int framenr)
299 {
300         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, framenr);
301
302         if(marker && marker->framenr!=framenr)
303                 return NULL;
304
305         return marker;
306 }
307
308 int BKE_tracking_has_marker(MovieTrackingTrack *track, int framenr)
309 {
310         return BKE_tracking_exact_marker(track, framenr) != 0;
311 }
312
313 void BKE_tracking_free_track(MovieTrackingTrack *track)
314 {
315         if(track->markers) MEM_freeN(track->markers);
316 }
317
318 MovieTrackingTrack *BKE_tracking_copy_track(MovieTrackingTrack *track)
319 {
320         MovieTrackingTrack *new_track= MEM_dupallocN(track);
321
322         new_track->next= new_track->prev= NULL;
323
324         if(new_track->markers)
325                 new_track->markers= MEM_dupallocN(new_track->markers);
326
327         return new_track;
328 }
329
330 void BKE_tracking_clear_path(MovieTrackingTrack *track, int ref_frame, int action)
331 {
332         int a;
333
334         if(action==TRACK_CLEAR_REMAINED) {
335                 a= 1;
336                 while(a<track->markersnr) {
337                         if(track->markers[a].framenr>ref_frame) {
338                                 track->markersnr= a;
339                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
340
341                                 break;
342                         }
343
344                         a++;
345                 }
346         } else if(action==TRACK_CLEAR_UPTO) {
347                 a= track->markersnr-1;
348                 while(a>=0) {
349                         if(track->markers[a].framenr<=ref_frame) {
350                                 memmove(track->markers, track->markers+a, (track->markersnr-a)*sizeof(MovieTrackingMarker));
351
352                                 track->markersnr= track->markersnr-a;
353                                 track->markers= MEM_reallocN(track->markers, sizeof(MovieTrackingMarker)*track->markersnr);
354
355                                 break;
356                         }
357
358                         a--;
359                 }
360         } else if(action==TRACK_CLEAR_ALL) {
361                 MovieTrackingMarker *marker, marker_new;
362
363                 marker= BKE_tracking_get_marker(track, ref_frame);
364                 if(marker)
365                         marker_new= *marker;
366
367                 MEM_freeN(track->markers);
368                 track->markers= NULL;
369                 track->markersnr= 0;
370
371                 if(marker)
372                         BKE_tracking_insert_marker(track, &marker_new);
373         }
374 }
375
376 void BKE_tracking_free(MovieTracking *tracking)
377 {
378         MovieTrackingTrack *track;
379
380         for(track= tracking->tracks.first; track; track= track->next) {
381                 BKE_tracking_free_track(track);
382         }
383
384         BLI_freelistN(&tracking->tracks);
385
386         if(tracking->camera.reconstructed)
387                 MEM_freeN(tracking->camera.reconstructed);
388 }
389
390 /*********************** tracking *************************/
391
392 typedef struct MovieTrackingContext {
393         MovieClipUser user;
394         MovieClip *clip;
395
396 #ifdef WITH_LIBMV
397         struct libmv_RegionTracker *region_tracker;
398 #endif
399         ListBase tracks;
400         GHash *hash;
401         MovieTrackingSettings settings;
402
403         int backwards;
404         int sync_frame;
405 } MovieTrackingContext;
406
407 MovieTrackingContext *BKE_tracking_context_new(MovieClip *clip, MovieClipUser *user, int backwards)
408 {
409         MovieTrackingContext *context= MEM_callocN(sizeof(MovieTrackingContext), "trackingContext");
410         MovieTracking *tracking= &clip->tracking;
411         MovieTrackingSettings *settings= &tracking->settings;
412         MovieTrackingTrack *track;
413
414 #ifdef WITH_LIBMV
415         context->region_tracker= libmv_regionTrackerNew(100, 4, 0.2);
416 #endif
417
418         context->settings= *settings;
419         context->backwards= backwards;
420         context->hash= BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "tracking trackHash");
421         context->sync_frame= user->framenr;
422
423         track= tracking->tracks.first;
424         while(track) {
425                 if(TRACK_VIEW_SELECTED(track) && TRACK_VISIBLE(track)) {
426                         MovieTrackingMarker *marker= BKE_tracking_get_marker(track, user->framenr);
427
428                         if((marker->flag&MARKER_DISABLED)==0) {
429                                 MovieTrackingTrack *new_track= BKE_tracking_copy_track(track);
430
431                                 BLI_addtail(&context->tracks, new_track);
432                                 BLI_ghash_insert(context->hash, new_track, track);
433                         }
434                 }
435
436                 track= track->next;
437         }
438
439         context->clip= clip;
440         context->user= *user;
441
442         return context;
443 }
444
445 void BKE_tracking_context_free(MovieTrackingContext *context)
446 {
447         MovieTrackingTrack *track;
448
449 #if WITH_LIBMV
450         libmv_regionTrackerDestroy(context->region_tracker);
451 #endif
452
453         track= context->tracks.first;
454         while(track) {
455                 BKE_tracking_free_track(track);
456                 track= track->next;
457         }
458         BLI_freelistN(&context->tracks);
459
460         BLI_ghash_free(context->hash, NULL, NULL);
461
462         MEM_freeN(context);
463 }
464
465 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track)
466 {
467         int x, y;
468
469         if((track->flag&(TRACK_DISABLE_RED|TRACK_DISABLE_GREEN|TRACK_DISABLE_BLUE))==0)
470                 return;
471
472         for(y= 0; y<ibuf->y; y++) {
473                 for (x= 0; x<ibuf->x; x++) {
474                         int pixel= ibuf->x*y + x;
475                         char *rrgb= (char*)ibuf->rect + pixel*4;
476
477                         if(track->flag&TRACK_DISABLE_RED)       rrgb[0]= 0;
478                         if(track->flag&TRACK_DISABLE_GREEN)     rrgb[1]= 0;
479                         if(track->flag&TRACK_DISABLE_BLUE)      rrgb[2]= 0;
480                 }
481         }
482 }
483
484 static ImBuf *acquire_area_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
485                         float min[2], float max[2], int margin, float pos[2], int origin[2])
486 {
487         ImBuf *tmpibuf;
488         int x, y;
489         int x1, y1, x2, y2, w, h;
490
491         x= marker->pos[0]*ibuf->x;
492         y= marker->pos[1]*ibuf->y;
493         x1= x-(int)(-min[0]*ibuf->x);
494         y1= y-(int)(-min[1]*ibuf->y);
495         x2= x+(int)(max[0]*ibuf->x);
496         y2= y+(int)(max[1]*ibuf->y);
497
498         /* dimensions should be odd */
499         w= (x2-x1)|1;
500         h= (y2-y1)|1;
501
502         /* happens due to rounding issues */
503         if(x1+w<=x) x1++;
504         if(y1+h<=y) y1++;
505
506         tmpibuf= IMB_allocImBuf(w+margin*2, h+margin*2, 32, IB_rect);
507         IMB_rectcpy(tmpibuf, ibuf, 0, 0, x1-margin, y1-margin, w+margin*2, h+margin*2);
508
509         if(pos != NULL) {
510                 pos[0]= x-x1+(marker->pos[0]*ibuf->x-x)+margin;
511                 pos[1]= y-y1+(marker->pos[1]*ibuf->y-y)+margin;
512         }
513
514         if(origin != NULL) {
515                 origin[0]= x1-margin;
516                 origin[1]= y1-margin;
517         }
518
519         disable_imbuf_channels(tmpibuf, track);
520
521         return tmpibuf;
522 }
523
524 ImBuf *BKE_tracking_acquire_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
525                         int margin, float pos[2], int origin[2])
526 {
527         return acquire_area_imbuf(ibuf, track, marker, track->pat_min, track->pat_max, margin, pos, origin);
528 }
529
530 ImBuf *BKE_tracking_acquire_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
531                         int margin, float pos[2], int origin[2])
532 {
533         return acquire_area_imbuf(ibuf, track, marker, track->search_min, track->search_max, margin, pos, origin);
534 }
535
536 #ifdef WITH_LIBMV
537 static float *acquire_search_floatbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
538                         int *width_r, int *height_r, float pos[2], int origin[2])
539 {
540         ImBuf *tmpibuf;
541         float *pixels, *fp;
542         int x, y, width, height;
543
544         width= (track->search_max[0]-track->search_min[0])*ibuf->x;
545         height= (track->search_max[1]-track->search_min[1])*ibuf->y;
546
547         tmpibuf= BKE_tracking_acquire_search_imbuf(ibuf, track, marker, 0, pos, origin);
548         disable_imbuf_channels(tmpibuf, track);
549
550         *width_r= width;
551         *height_r= height;
552
553         fp= pixels= MEM_callocN(width*height*sizeof(float), "tracking floatBuf");
554         for(y= 0; y<(int)height; y++) {
555                 for (x= 0; x<(int)width; x++) {
556                         int pixel= tmpibuf->x*y + x;
557                         char *rrgb= (char*)tmpibuf->rect + pixel*4;
558
559                         *fp= (0.2126*rrgb[0] + 0.7152*rrgb[1] + 0.0722*rrgb[2])/255;
560                         fp++;
561                 }
562         }
563
564         IMB_freeImBuf(tmpibuf);
565
566         return pixels;
567 }
568 #endif
569
570 void BKE_tracking_sync(MovieTrackingContext *context)
571 {
572         MovieTrackingTrack *track;
573         ListBase tracks= {NULL, NULL};
574         ListBase *old_tracks= &context->clip->tracking.tracks;
575         int sel_type, newframe;
576         void *sel;
577
578         BKE_movieclip_last_selection(context->clip, &sel_type, &sel);
579
580         /* duplicate currently tracking tracks to list of displaying tracks */
581         track= context->tracks.first;
582         while(track) {
583                 int replace_sel= 0;
584                 MovieTrackingTrack *new_track, *old;
585
586                 /* find original of tracking track in list of previously displayed tracks */
587                 old= BLI_ghash_lookup(context->hash, track);
588                 if(old) {
589                         MovieTrackingTrack *cur= old_tracks->first;
590
591                         while(cur) {
592                                 if(cur==old)
593                                         break;
594
595                                 cur= cur->next;
596                         }
597
598                         /* original track was found, re-use flags and remove this track */
599                         if(cur) {
600                                 if(sel_type==MCLIP_SEL_TRACK && sel==cur)
601                                         replace_sel= 1;
602
603                                 track->flag= cur->flag;
604                                 track->pat_flag= cur->pat_flag;
605                                 track->search_flag= cur->search_flag;
606
607                                 BKE_tracking_free_track(cur);
608                                 BLI_freelinkN(old_tracks, cur);
609                         }
610                 }
611
612                 new_track= BKE_tracking_copy_track(track);
613
614                 BLI_ghash_remove(context->hash, track, NULL, NULL); /* XXX: are we actually need this */
615                 BLI_ghash_insert(context->hash, track, new_track);
616
617                 if(replace_sel)         /* update current selection in clip */
618                         BKE_movieclip_set_selection(context->clip, MCLIP_SEL_TRACK, new_track);
619
620                 BLI_addtail(&tracks, new_track);
621
622                 track= track->next;
623         }
624
625         /* move tracks, which could be added by user during tracking */
626         track= old_tracks->first;
627         while(track) {
628                 MovieTrackingTrack *next= track->next;
629
630                 track->next= track->prev= NULL;
631                 BLI_addtail(&tracks, track);
632
633                 track= next;
634         }
635
636         context->clip->tracking.tracks= tracks;
637
638         if(context->backwards) newframe= context->user.framenr+1;
639         else newframe= context->user.framenr-1;
640
641         context->sync_frame= newframe;
642 }
643
644 void BKE_tracking_sync_user(MovieClipUser *user, MovieTrackingContext *context)
645 {
646         user->framenr= context->sync_frame;
647 }
648
649 int BKE_tracking_next(MovieTrackingContext *context)
650 {
651         ImBuf *ibuf, *ibuf_new;
652         MovieTrackingTrack *track;
653         int curfra= context->user.framenr;
654         int ok= 0;
655
656         /* nothing to track, avoid unneeded frames reading to save time and memory */
657         if(!context->tracks.first)
658                 return 0;
659
660         ibuf= BKE_movieclip_acquire_ibuf(context->clip, &context->user);
661         if(!ibuf) return 0;
662
663         if(context->backwards) context->user.framenr--;
664         else context->user.framenr++;
665
666         ibuf_new= BKE_movieclip_acquire_ibuf(context->clip, &context->user);
667         if(!ibuf_new) {
668                 IMB_freeImBuf(ibuf);
669                 return 0;
670         }
671
672         track= context->tracks.first;
673         while(track) {
674                 MovieTrackingMarker *marker= BKE_tracking_get_marker(track, curfra);
675
676                 if(marker && (marker->flag&MARKER_DISABLED)==0 && marker->framenr==curfra) {
677 #ifdef WITH_LIBMV
678                         int width, height, origin[2];
679                         float pos[2];
680                         float *patch= acquire_search_floatbuf(ibuf, track, marker, &width, &height, pos, origin);
681                         float *patch_new= acquire_search_floatbuf(ibuf_new, track, marker, &width, &height, pos, origin);
682                         double x1= pos[0], y1= pos[1];
683                         double x2= x1, y2= y1;
684                         int wndx, wndy;
685                         MovieTrackingMarker marker_new;
686
687                         wndx= (int)((track->pat_max[0]-track->pat_min[0])*ibuf->x)/2;
688                         wndy= (int)((track->pat_max[1]-track->pat_min[1])*ibuf->y)/2;
689
690                         if(libmv_regionTrackerTrack(context->region_tracker, patch, patch_new,
691                                                 width, height, MAX2(wndx, wndy),
692                                                 x1, y1, &x2, &y2)) {
693                                 memset(&marker_new, 0, sizeof(marker_new));
694                                 marker_new.pos[0]= (origin[0]+x2)/ibuf_new->x;
695                                 marker_new.pos[1]= (origin[1]+y2)/ibuf_new->y;
696
697                                 if(context->backwards) marker_new.framenr= curfra-1;
698                                 else marker_new.framenr= curfra+1;
699
700                                 BKE_tracking_insert_marker(track, &marker_new);
701
702                         } else {
703                                 marker_new= *marker;
704
705                                 if(context->backwards) marker_new.framenr--;
706                                 else marker_new.framenr++;;
707
708                                 marker_new.flag|= MARKER_DISABLED;
709
710                                 BKE_tracking_insert_marker(track, &marker_new);
711                         }
712
713                         ok= 1;
714
715                         MEM_freeN(patch);
716                         MEM_freeN(patch_new);
717 #endif
718                 }
719
720                 track= track->next;
721         }
722
723         IMB_freeImBuf(ibuf);
724         IMB_freeImBuf(ibuf_new);
725
726         return ok;
727 }
728
729 #if WITH_LIBMV
730 static struct libmv_Tracks *create_libmv_tracks(MovieClip *clip)
731 {
732         int width, height;
733         int tracknr= 0;
734         MovieTrackingTrack *track;
735         struct libmv_Tracks *tracks= libmv_tracksNew();;
736
737         /* XXX: could fail if footage uses images with different sizes */
738         BKE_movieclip_acquire_size(clip, NULL, &width, &height);
739
740         track= clip->tracking.tracks.first;
741         while(track) {
742                 int a= 0;
743
744                 for(a= 0; a<track->markersnr; a++) {
745                         MovieTrackingMarker *marker= &track->markers[a];
746
747                         if((marker->flag&MARKER_DISABLED)==0)
748                                 libmv_tracksInsert(tracks, marker->framenr, tracknr, marker->pos[0]*width, marker->pos[1]*height);
749                 }
750
751                 track= track->next;
752                 tracknr++;
753         }
754
755         return tracks;
756 }
757
758 static void retrive_libmv_reconstruct(MovieClip *clip, struct libmv_Reconstruction *reconstruction)
759 {
760         int tracknr= 0;
761         int sfra= INT_MAX, efra= INT_MIN, a, origin_set= 0;
762         MovieTracking *tracking= &clip->tracking;
763         MovieTrackingTrack *track;
764         MovieTrackingCamera *camera;
765         MovieReconstructedCamera *reconstructed;
766         float origin[3]= {0.0f, 0.f, 0.0f};
767
768         track= tracking->tracks.first;
769         while(track) {
770                 double pos[3];
771
772                 if(libmv_reporojectionPointForTrack(reconstruction, tracknr, pos)) {
773                         track->bundle_pos[0]= pos[0];
774                         track->bundle_pos[1]= pos[1];
775                         track->bundle_pos[2]= pos[2];
776
777                         track->flag|= TRACK_HAS_BUNDLE;
778                 } else {
779                         track->flag&= ~TRACK_HAS_BUNDLE;
780
781                         if (G.f & G_DEBUG)
782                                 printf("No bundle for track #%d '%s'\n", tracknr, track->name);
783                 }
784
785                 if(track->markersnr) {
786                         if(track->markers[0].framenr<sfra) sfra= track->markers[0].framenr;
787                         if(track->markers[track->markersnr-1].framenr>efra) efra= track->markers[track->markersnr-1].framenr;
788                 }
789
790                 track= track->next;
791                 tracknr++;
792         }
793
794         camera= &tracking->camera;
795
796         if(camera->reconstructed)
797                 MEM_freeN(camera->reconstructed);
798
799         camera->reconnr= 0;
800         camera->reconstructed= NULL;
801         reconstructed= MEM_callocN((efra-sfra+1)*sizeof(MovieReconstructedCamera), "temp reconstructed camera");
802
803         for(a= sfra; a<=efra; a++) {
804                 double matd[4][4];
805
806                 if(libmv_reporojectionCameraForImage(reconstruction, a, matd)) {
807                         int i, j;
808                         float mat[4][4];
809
810                         for(i=0; i<4; i++)
811                                 for(j= 0; j<4; j++)
812                                         mat[i][j]= matd[i][j];
813
814                         if(!origin_set) {
815                                 copy_v3_v3(origin, mat[3]);
816                                 origin_set= 1;
817                         }
818
819                         if(origin_set)
820                                 sub_v3_v3(mat[3], origin);
821
822                         copy_m4_m4(reconstructed[camera->reconnr].mat, mat);
823                         reconstructed[camera->reconnr].framenr= a;
824                         camera->reconnr++;
825                 } else if (G.f & G_DEBUG) {
826                         printf("No camera for image %d\n", a);
827                 }
828         }
829
830         if(camera->reconnr) {
831                 camera->reconstructed= MEM_callocN(camera->reconnr*sizeof(MovieReconstructedCamera), "reconstructed camera");
832                 memcpy(camera->reconstructed, reconstructed, camera->reconnr*sizeof(MovieReconstructedCamera));
833         }
834
835         if(origin_set) {
836                 track= tracking->tracks.first;
837                 while(track) {
838                         if(track->flag&TRACK_HAS_BUNDLE)
839                                 sub_v3_v3(track->bundle_pos, origin);
840
841                         track= track->next;
842                 }
843         }
844
845         MEM_freeN(reconstructed);
846 }
847
848 #endif
849
850 void BKE_tracking_solve_reconstruction(MovieClip *clip)
851 {
852 #if WITH_LIBMV
853         {
854                 MovieTrackingCamera *camera= &clip->tracking.camera;
855                 MovieTracking *tracking= &clip->tracking;
856                 struct libmv_Tracks *tracks= create_libmv_tracks(clip);
857                 struct libmv_Reconstruction *reconstruction = libmv_solveReconstruction(tracks,
858                         tracking->settings.keyframe1, tracking->settings.keyframe2,
859                         camera->focal, camera->principal[0], camera->principal[1],
860                         camera->k1, camera->k2, camera->k3);
861
862                 retrive_libmv_reconstruct(clip, reconstruction);
863
864                 libmv_destroyReconstruction(reconstruction);
865                 libmv_tracksDestroy(tracks);
866         }
867 #endif
868 }
869
870 void BKE_track_unique_name(MovieTracking *tracking, MovieTrackingTrack *track)
871 {
872         BLI_uniquename(&tracking->tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
873 }
874
875 MovieTrackingTrack *BKE_find_track_by_name(MovieTracking *tracking, const char *name)
876 {
877         MovieTrackingTrack *track= tracking->tracks.first;
878
879         while(track) {
880                 if(!strcmp(track->name, name))
881                         return track;
882
883                 track= track->next;
884         }
885
886         return NULL;
887 }
888
889 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking, int framenr)
890 {
891         MovieTrackingCamera *camera= &tracking->camera;
892         int a= 0, d= 1;
893
894         if(!camera->reconnr)
895                 return NULL;
896
897         if(camera->last_camera<camera->reconnr)
898                 a= camera->last_camera;
899
900         if(camera->reconstructed[a].framenr>=framenr)
901                 d= -1;
902
903         while(a>=0 && a<camera->reconnr) {
904                 if(camera->reconstructed[a].framenr==framenr) {
905                         camera->last_camera= a;
906                         return &camera->reconstructed[a];
907
908                         break;
909                 }
910
911                 a+= d;
912         }
913
914         return NULL;
915 }
916
917 void BKE_get_tracking_mat(Scene *scene, float mat[4][4])
918 {
919         if(!scene->camera)
920                 scene->camera= scene_find_camera(scene);
921
922         if(scene->camera)
923                 where_is_object_mat(scene, scene->camera, mat);
924         else
925                 unit_m4(mat);
926 }
927
928 void BKE_tracking_projection_matrix(MovieTracking *tracking, int framenr, int winx, int winy, float mat[4][4])
929 {
930         MovieReconstructedCamera *camera;
931         float lens= tracking->camera.focal*32.0f/(float)winx;
932         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
933         float winmat[4][4];
934
935         clipsta= 0.1f;
936         clipend= 1000.0f;
937
938         if(winx >= winy)
939                 viewfac= (lens*winx)/32.0f;
940         else
941                 viewfac= (lens*winy)/32.0f;
942
943         pixsize= clipsta/viewfac;
944
945         left= -0.5f*(float)winx*pixsize;
946         bottom= -0.5f*(float)winy*pixsize;
947         right=  0.5f*(float)winx*pixsize;
948         top=  0.5f*(float)winy*pixsize;
949
950         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
951
952         camera= BKE_tracking_get_reconstructed_camera(tracking, framenr);
953         if(camera) {
954                 float imat[4][4];
955
956                 invert_m4_m4(imat, camera->mat);
957                 mul_m4_m4m4(mat, imat, winmat);
958         } else copy_m4_m4(mat, winmat);
959 }
960
961 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float width, float height, float nco[2])
962 {
963         MovieTrackingCamera *camera= &tracking->camera;
964
965 #ifdef WITH_LIBMV
966         double x= nco[0], y= nco[1];
967
968         /* normalize coords */
969         x= (co[0]-camera->principal[0]) / camera->focal;
970         y= (co[1]-camera->principal[1]) / camera->focal;
971
972         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1],
973                                 camera->k1, camera->k2, camera->k3, x, y, &x, &y);
974
975         /* result is in image coords already */
976         nco[0]= x;
977         nco[1]= y;
978 #endif
979 }
980
981 #ifdef WITH_LIBMV
982 /* flips upside-down */
983 static unsigned char *acquire_ucharbuf(ImBuf *ibuf)
984 {
985         int x, y;
986         unsigned char *pixels, *fp;
987
988         fp= pixels= MEM_callocN(ibuf->x*ibuf->y*sizeof(unsigned char), "tracking ucharBuf");
989         for(y= 0; y<ibuf->y; y++) {
990                 for (x= 0; x<ibuf->x; x++) {
991                         int pixel= ibuf->x*(ibuf->y-y-1) + x;
992                         char *rrgb= (char*)ibuf->rect + pixel*4;
993
994                         //*fp= 0.2126f*rrgb[0] + 0.7152f*rrgb[1] + 0.0722f*rrgb[2];
995                         *fp= (11*rrgb[0]+16*rrgb[1]+5*rrgb[2])/32;
996
997                         fp++;
998                 }
999         }
1000
1001         return pixels;
1002 }
1003 #endif
1004
1005 void BKE_tracking_detect(MovieTracking *tracking, ImBuf *ibuf, int framenr)
1006 {
1007 #ifdef WITH_LIBMV
1008         struct libmv_Corners *corners;
1009         unsigned char *pixels= acquire_ucharbuf(ibuf);
1010         int a;
1011
1012         corners= libmv_detectCorners(pixels, ibuf->x, ibuf->y, ibuf->x);
1013         MEM_freeN(pixels);
1014
1015         a= libmv_countCorners(corners);
1016         while(a--) {
1017                 MovieTrackingTrack *track;
1018
1019                 float x, y, size, score;
1020
1021                 libmv_getCorner(corners, a, &x, &y, &score, &size);
1022
1023                 track= BKE_tracking_add_track(tracking, x/ibuf->x, 1.0f-(y/ibuf->y), framenr, ibuf->x, ibuf->y);
1024                 track->flag|= SELECT;
1025                 track->pat_flag|= SELECT;
1026                 track->search_flag|= SELECT;
1027         }
1028
1029         libmv_destroyCorners(corners);
1030 #endif
1031 }