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  *                 Keir Mierle
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 /** \file blender/blenkernel/intern/tracking.c
  29  *  \ingroup bke
  30  */
  31
  32 #include <stddef.h>
  33 #include <limits.h>
  34 #include <math.h>
  35 #include <memory.h>
  36
  37 #include "MEM_guardedalloc.h"
  38
  39 #include "DNA_gpencil_types.h"
  40 #include "DNA_camera_types.h"
  41 #include "DNA_movieclip_types.h"
  42 #include "DNA_object_types.h"   /* SELECT */
  43 #include "DNA_scene_types.h"
  44
  45 #include "BLI_utildefines.h"
  46 #include "BLI_math.h"
  47 #include "BLI_math_base.h"
  48 #include "BLI_listbase.h"
  49 #include "BLI_ghash.h"
  50 #include "BLI_path_util.h"
  51 #include "BLI_string.h"
  52 #include "BLI_threads.h"
  53
  54 #include "BKE_global.h"
  55 #include "BKE_tracking.h"
  56 #include "BKE_movieclip.h"
  57 #include "BKE_object.h"
  58 #include "BKE_scene.h"
  59
  60 #include "IMB_imbuf_types.h"
  61 #include "IMB_imbuf.h"
  62
  63 #include "raskter.h"
  64
  65 #ifdef WITH_LIBMV
  66 #  include "libmv-capi.h"
  67 #else
  68 struct libmv_Features;
  69 #endif
  70
  71 typedef struct MovieDistortion {
  72         struct libmv_CameraIntrinsics *intrinsics;
  73 } MovieDistortion;
  74
  75 static struct {
  76         ListBase tracks;
  77 } tracking_clipboard;
  78
  79 /*********************** space transformation functions  *************************/
  80
  81 /* Three coordinate frames: Frame, Search, and Marker
  82  * Two units: Pixels, Unified
  83  * Notation: {coordinate frame}_{unit}; for example, "search_pixel" are search
  84  * window relative coordinates in pixels, and "frame_unified" are unified 0..1
  85  * coordinates relative to the entire frame.
  86  */
  87 static void unified_to_pixel(int frame_width, int frame_height,
  88                              const float unified_coords[2], float pixel_coords[2])
  89 {
  90         pixel_coords[0] = unified_coords[0] * frame_width;
  91         pixel_coords[1] = unified_coords[1] * frame_height;
  92 }
  93
  94 static void marker_to_frame_unified(const MovieTrackingMarker *marker, const float marker_unified_coords[2],
  95                                     float frame_unified_coords[2])
  96 {
  97         frame_unified_coords[0] = marker_unified_coords[0] + marker->pos[0];
  98         frame_unified_coords[1] = marker_unified_coords[1] + marker->pos[1];
  99 }
 100
 101 static void marker_unified_to_frame_pixel_coordinates(int frame_width, int frame_height,
 102                                                       const MovieTrackingMarker *marker,
 103                                                       const float marker_unified_coords[2], float frame_pixel_coords[2])
 104 {
 105         marker_to_frame_unified(marker, marker_unified_coords, frame_pixel_coords);
 106         unified_to_pixel(frame_width, frame_height, frame_pixel_coords, frame_pixel_coords);
 107 }
 108
 109 static void get_search_origin_frame_pixel(int frame_width, int frame_height,
 110                                           const MovieTrackingMarker *marker, float frame_pixel[2])
 111 {
 112         /* Get the lower left coordinate of the search window and snap to pixel coordinates */
 113         marker_unified_to_frame_pixel_coordinates(frame_width, frame_height, marker, marker->search_min, frame_pixel);
 114         frame_pixel[0] = (int)frame_pixel[0];
 115         frame_pixel[1] = (int)frame_pixel[1];
 116 }
 117
 118 #ifdef WITH_LIBMV
 119 static void pixel_to_unified(int frame_width, int frame_height, const float pixel_coords[2], float unified_coords[2])
 120 {
 121         unified_coords[0] = pixel_coords[0] / frame_width;
 122         unified_coords[1] = pixel_coords[1] / frame_height;
 123 }
 124
 125 static void marker_unified_to_search_pixel(int frame_width, int frame_height,
 126                                            const MovieTrackingMarker *marker,
 127                                            const float marker_unified[2], float search_pixel[2])
 128 {
 129         float frame_pixel[2];
 130         float search_origin_frame_pixel[2];
 131
 132         marker_unified_to_frame_pixel_coordinates(frame_width, frame_height, marker, marker_unified, frame_pixel);
 133         get_search_origin_frame_pixel(frame_width, frame_height, marker, search_origin_frame_pixel);
 134         sub_v2_v2v2(search_pixel, frame_pixel, search_origin_frame_pixel);
 135 }
 136
 137 static void search_pixel_to_marker_unified(int frame_width, int frame_height,
 138                                            const MovieTrackingMarker *marker,
 139                                            const float search_pixel[2], float marker_unified[2])
 140 {
 141         float frame_unified[2];
 142         float search_origin_frame_pixel[2];
 143
 144         get_search_origin_frame_pixel(frame_width, frame_height, marker, search_origin_frame_pixel);
 145         add_v2_v2v2(frame_unified, search_pixel, search_origin_frame_pixel);
 146         pixel_to_unified(frame_width, frame_height, frame_unified, frame_unified);
 147
 148         /* marker pos is in frame unified */
 149         sub_v2_v2v2(marker_unified, frame_unified, marker->pos);
 150 }
 151
 152 /* Each marker has 5 coordinates associated with it that get warped with
 153  * tracking: the four corners ("pattern_corners"), and the cernter ("pos").
 154  * This function puts those 5 points into the appropriate frame for tracking
 155  * (the "search" coordinate frame).
 156  */
 157 static void get_marker_coords_for_tracking(int frame_width, int frame_height,
 158                                            const MovieTrackingMarker *marker,
 159                                            double search_pixel_x[5], double search_pixel_y[5])
 160 {
 161         int i;
 162         float unified_coords[2];
 163         float pixel_coords[2];
 164
 165         /* Convert the corners into search space coordinates. */
 166         for (i = 0; i < 4; i++) {
 167                 marker_unified_to_search_pixel(frame_width, frame_height, marker, marker->pattern_corners[i], pixel_coords);
 168                 search_pixel_x[i] = pixel_coords[0];
 169                 search_pixel_y[i] = pixel_coords[1];
 170         }
 171         /* Convert the center position (aka "pos"); this is the origin */
 172         unified_coords[0] = 0.0;
 173         unified_coords[1] = 0.0;
 174         marker_unified_to_search_pixel(frame_width, frame_height, marker, unified_coords, pixel_coords);
 175
 176         search_pixel_x[4] = pixel_coords[0];
 177         search_pixel_y[4] = pixel_coords[1];
 178 }
 179
 180 /* Inverse of above. */
 181 static void set_marker_coords_from_tracking(int frame_width, int frame_height, MovieTrackingMarker *marker,
 182                                             const double search_pixel_x[5], const double search_pixel_y[5])
 183 {
 184         int i;
 185         float marker_unified[2];
 186         float search_pixel[2];
 187
 188         /* Convert the corners into search space coordinates. */
 189         for (i = 0; i < 4; i++) {
 190                 search_pixel[0] = search_pixel_x[i];
 191                 search_pixel[1] = search_pixel_y[i];
 192                 search_pixel_to_marker_unified(frame_width, frame_height, marker, search_pixel, marker->pattern_corners[i]);
 193         }
 194
 195         /* Convert the center position (aka "pos"); this is the origin */
 196         search_pixel[0] = search_pixel_x[4];
 197         search_pixel[1] = search_pixel_y[4];
 198         search_pixel_to_marker_unified(frame_width, frame_height, marker, search_pixel, marker_unified);
 199
 200         /* If the tracker tracked nothing, then "marker_unified" would be zero.
 201          * Otherwise, the entire patch shifted, and that delta should be applied to
 202          * all the coordinates.
 203          */
 204         for (i = 0; i < 4; i++) {
 205                 marker->pattern_corners[i][0] -= marker_unified[0];
 206                 marker->pattern_corners[i][1] -= marker_unified[1];
 207         }
 208
 209         marker->pos[0] += marker_unified[0];
 210         marker->pos[1] += marker_unified[1];
 211 }
 212 #endif
 213
 214 /*********************** common functions *************************/
 215
 216 void BKE_tracking_init_settings(MovieTracking *tracking)
 217 {
 218         tracking->camera.sensor_width = 35.0f;
 219         tracking->camera.pixel_aspect = 1.0f;
 220         tracking->camera.units = CAMERA_UNITS_MM;
 221
 222         tracking->settings.default_motion_model = TRACK_MOTION_MODEL_TRANSLATION;
 223         tracking->settings.default_minimum_correlation = 0.75;
 224         tracking->settings.default_pattern_size = 11;
 225         tracking->settings.default_search_size = 61;
 226         tracking->settings.keyframe1 = 1;
 227         tracking->settings.keyframe2 = 30;
 228         tracking->settings.dist = 1;
 229         tracking->settings.object_distance = 1;
 230
 231         tracking->stabilization.scaleinf = 1.0f;
 232         tracking->stabilization.locinf = 1.0f;
 233         tracking->stabilization.rotinf = 1.0f;
 234         tracking->stabilization.maxscale = 2.0f;
 235
 236         BKE_tracking_new_object(tracking, "Camera");
 237 }
 238
 239 void BKE_tracking_clamp_marker(MovieTrackingMarker *marker, int event)
 240 {
 241         int a;
 242         float pat_min[2], pat_max[2];
 243
 244         BKE_tracking_marker_pattern_minmax(marker, pat_min, pat_max);
 245
 246         if (event == CLAMP_PAT_DIM) {
 247                 for (a = 0; a < 2; a++) {
 248                         /* search shouldn't be resized smaller than pattern */
 249                         marker->search_min[a] = MIN2(pat_min[a], marker->search_min[a]);
 250                         marker->search_max[a] = MAX2(pat_max[a], marker->search_max[a]);
 251                 }
 252         }
 253         else if (event == CLAMP_PAT_POS) {
 254                 float dim[2];
 255
 256                 sub_v2_v2v2(dim, pat_max, pat_min);
 257
 258                 for (a = 0; a < 2; a++) {
 259                         int b;
 260                         /* pattern shouldn't be moved outside of search */
 261                         if (pat_min[a] < marker->search_min[a]) {
 262                                 for (b = 0; b < 4; b++)
 263                                         marker->pattern_corners[b][a] += marker->search_min[a] - pat_min[a];
 264                         }
 265                         if (pat_max[a] > marker->search_max[a]) {
 266                                 for (b = 0; b < 4; b++)
 267                                         marker->pattern_corners[b][a] -= pat_max[a] - marker->search_max[a];
 268                         }
 269                 }
 270         }
 271         else if (event == CLAMP_SEARCH_DIM) {
 272                 for (a = 0; a < 2; a++) {
 273                         /* search shouldn't be resized smaller than pattern */
 274                         marker->search_min[a] = MIN2(pat_min[a], marker->search_min[a]);
 275                         marker->search_max[a] = MAX2(pat_max[a], marker->search_max[a]);
 276                 }
 277         }
 278         else if (event == CLAMP_SEARCH_POS) {
 279                 float dim[2];
 280
 281                 sub_v2_v2v2(dim, marker->search_max, marker->search_min);
 282
 283                 for (a = 0; a < 2; a++) {
 284                         /* search shouldn't be moved inside pattern */
 285                         if (marker->search_min[a] > pat_min[a]) {
 286                                 marker->search_min[a] = pat_min[a];
 287                                 marker->search_max[a] = marker->search_min[a] + dim[a];
 288                         }
 289                         if (marker->search_max[a] < pat_max[a]) {
 290                                 marker->search_max[a] = pat_max[a];
 291                                 marker->search_min[a] = marker->search_max[a] - dim[a];
 292                         }
 293                 }
 294         }
 295         else if (event == CLAMP_SEARCH_DIM) {
 296                 float dim[2];
 297                 sub_v2_v2v2(dim, pat_max, pat_min);
 298                 for (a = 0; a < 2; a++) {
 299                         marker->search_min[a] = pat_min[a];
 300                         marker->search_max[a] = pat_max[a];
 301                 }
 302         }
 303 }
 304
 305 void BKE_tracking_track_flag(MovieTrackingTrack *track, int area, int flag, int clear)
 306 {
 307         if (area == TRACK_AREA_NONE)
 308                 return;
 309
 310         if (clear) {
 311                 if (area & TRACK_AREA_POINT)
 312                         track->flag &= ~flag;
 313                 if (area & TRACK_AREA_PAT)
 314                         track->pat_flag &= ~flag;
 315                 if (area & TRACK_AREA_SEARCH)
 316                         track->search_flag &= ~flag;
 317         }
 318         else {
 319                 if (area & TRACK_AREA_POINT)
 320                         track->flag |= flag;
 321                 if (area & TRACK_AREA_PAT)
 322                         track->pat_flag |= flag;
 323                 if (area & TRACK_AREA_SEARCH)
 324                         track->search_flag |= flag;
 325         }
 326 }
 327
 328 MovieTrackingTrack *BKE_tracking_add_track(MovieTracking *tracking, ListBase *tracksbase, float x, float y,
 329                                            int framenr, int width, int height)
 330 {
 331         MovieTrackingTrack *track;
 332         MovieTrackingMarker marker;
 333         MovieTrackingSettings *settings = &tracking->settings;
 334
 335         float half_pattern = (float)settings->default_pattern_size / 2.0f;
 336         float half_search = (float)settings->default_search_size / 2.0f;
 337         float pat[2], search[2];
 338
 339         pat[0] = half_pattern / (float)width;
 340         pat[1] = half_pattern / (float)height;
 341
 342         search[0] = half_search / (float)width;
 343         search[1] = half_search / (float)height;
 344
 345         track = MEM_callocN(sizeof(MovieTrackingTrack), "add_marker_exec track");
 346         strcpy(track->name, "Track");
 347
 348         track->motion_model = settings->default_motion_model;
 349         track->minimum_correlation = settings->default_minimum_correlation;
 350         track->margin = settings->default_margin;
 351         track->pattern_match = settings->default_pattern_match;
 352         track->frames_limit = settings->default_frames_limit;
 353         track->flag = settings->default_flag;
 354         track->algorithm_flag = settings->default_algorithm_flag;
 355
 356         memset(&marker, 0, sizeof(marker));
 357         marker.pos[0] = x;
 358         marker.pos[1] = y;
 359         marker.framenr = framenr;
 360
 361         marker.pattern_corners[0][0] = -pat[0];
 362         marker.pattern_corners[0][1] = -pat[1];
 363
 364         marker.pattern_corners[1][0] = pat[0];
 365         marker.pattern_corners[1][1] = -pat[1];
 366
 367         negate_v2_v2(marker.pattern_corners[2], marker.pattern_corners[0]);
 368         negate_v2_v2(marker.pattern_corners[3], marker.pattern_corners[1]);
 369
 370         copy_v2_v2(marker.search_max, search);
 371         negate_v2_v2(marker.search_min, search);
 372
 373         BKE_tracking_insert_marker(track, &marker);
 374
 375         BLI_addtail(tracksbase, track);
 376         BKE_track_unique_name(tracksbase, track);
 377
 378         return track;
 379 }
 380
 381 MovieTrackingMarker *BKE_tracking_insert_marker(MovieTrackingTrack *track, MovieTrackingMarker *marker)
 382 {
 383         MovieTrackingMarker *old_marker = NULL;
 384
 385         if (track->markersnr)
 386                 old_marker = BKE_tracking_exact_marker(track, marker->framenr);
 387
 388         if (old_marker) {
 389                 *old_marker = *marker;
 390
 391                 return old_marker;
 392         }
 393         else {
 394                 int a = track->markersnr;
 395
 396                 while (a--) {
 397                         if (track->markers[a].framenr < marker->framenr)
 398                                 break;
 399                 }
 400
 401                 track->markersnr++;
 402
 403                 if (track->markers)
 404                         track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
 405                 else
 406                         track->markers = MEM_callocN(sizeof(MovieTrackingMarker), "MovieTracking markers");
 407
 408                 memmove(track->markers + a + 2, track->markers + a + 1,
 409                         (track->markersnr - a - 2) * sizeof(MovieTrackingMarker));
 410                 track->markers[a + 1] = *marker;
 411
 412                 track->last_marker = a + 1;
 413
 414                 return &track->markers[a + 1];
 415         }
 416 }
 417
 418 void BKE_tracking_delete_marker(MovieTrackingTrack *track, int framenr)
 419 {
 420         int a = 0;
 421
 422         while (a < track->markersnr) {
 423                 if (track->markers[a].framenr == framenr) {
 424                         if (track->markersnr > 1) {
 425                                 memmove(track->markers + a, track->markers + a + 1,
 426                                         (track->markersnr - a - 1) * sizeof(MovieTrackingMarker));
 427                                 track->markersnr--;
 428                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
 429                         }
 430                         else {
 431                                 MEM_freeN(track->markers);
 432                                 track->markers = NULL;
 433                                 track->markersnr = 0;
 434                         }
 435
 436                         break;
 437                 }
 438
 439                 a++;
 440         }
 441 }
 442
 443 void BKE_tracking_marker_pattern_minmax(const MovieTrackingMarker *marker, float min[2], float max[2])
 444 {
 445         INIT_MINMAX2(min, max);
 446
 447         DO_MINMAX2(marker->pattern_corners[0], min, max);
 448         DO_MINMAX2(marker->pattern_corners[1], min, max);
 449         DO_MINMAX2(marker->pattern_corners[2], min, max);
 450         DO_MINMAX2(marker->pattern_corners[3], min, max);
 451 }
 452
 453 MovieTrackingMarker *BKE_tracking_get_marker(MovieTrackingTrack *track, int framenr)
 454 {
 455         int a = track->markersnr - 1;
 456
 457         if (!track->markersnr)
 458                 return NULL;
 459
 460         /* approximate pre-first framenr marker with first marker */
 461         if (framenr < track->markers[0].framenr)
 462                 return &track->markers[0];
 463
 464         if (track->last_marker < track->markersnr)
 465                 a = track->last_marker;
 466
 467         if (track->markers[a].framenr <= framenr) {
 468                 while (a < track->markersnr && track->markers[a].framenr <= framenr) {
 469                         if (track->markers[a].framenr == framenr) {
 470                                 track->last_marker = a;
 471
 472                                 return &track->markers[a];
 473                         }
 474                         a++;
 475                 }
 476
 477                 /* if there's no marker for exact position, use nearest marker from left side */
 478                 return &track->markers[a - 1];
 479         }
 480         else {
 481                 while (a >= 0 && track->markers[a].framenr >= framenr) {
 482                         if (track->markers[a].framenr == framenr) {
 483                                 track->last_marker = a;
 484
 485                                 return &track->markers[a];
 486                         }
 487
 488                         a--;
 489                 }
 490
 491                 /* if there's no marker for exact position, use nearest marker from left side */
 492                 return &track->markers[a];
 493         }
 494
 495         return NULL;
 496 }
 497
 498 MovieTrackingMarker *BKE_tracking_ensure_marker(MovieTrackingTrack *track, int framenr)
 499 {
 500         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
 501
 502         if (marker->framenr != framenr) {
 503                 MovieTrackingMarker marker_new;
 504
 505                 marker_new = *marker;
 506                 marker_new.framenr = framenr;
 507
 508                 BKE_tracking_insert_marker(track, &marker_new);
 509                 marker = BKE_tracking_get_marker(track, framenr);
 510         }
 511
 512         return marker;
 513 }
 514
 515 MovieTrackingMarker *BKE_tracking_exact_marker(MovieTrackingTrack *track, int framenr)
 516 {
 517         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
 518
 519         if (marker->framenr != framenr)
 520                 return NULL;
 521
 522         return marker;
 523 }
 524
 525 int BKE_tracking_has_marker(MovieTrackingTrack *track, int framenr)
 526 {
 527         return BKE_tracking_exact_marker(track, framenr) != 0;
 528 }
 529
 530 int BKE_tracking_has_enabled_marker(MovieTrackingTrack *track, int framenr)
 531 {
 532         MovieTrackingMarker *marker = BKE_tracking_exact_marker(track, framenr);
 533
 534         return marker && (marker->flag & MARKER_DISABLED) == 0;
 535 }
 536
 537 void BKE_tracking_free_track(MovieTrackingTrack *track)
 538 {
 539         if (track->markers)
 540                 MEM_freeN(track->markers);
 541 }
 542
 543 static void put_disabled_marker(MovieTrackingTrack *track, MovieTrackingMarker *ref_marker, int before, int overwrite)
 544 {
 545         MovieTrackingMarker marker_new;
 546
 547         marker_new = *ref_marker;
 548         marker_new.flag &= ~MARKER_TRACKED;
 549         marker_new.flag |= MARKER_DISABLED;
 550
 551         if (before)
 552                 marker_new.framenr--;
 553         else
 554                 marker_new.framenr++;
 555
 556         if (!BKE_tracking_has_marker(track, marker_new.framenr) || overwrite)
 557                 BKE_tracking_insert_marker(track, &marker_new);
 558 }
 559
 560 void BKE_tracking_clear_path(MovieTrackingTrack *track, int ref_frame, int action)
 561 {
 562         int a;
 563
 564         if (action == TRACK_CLEAR_REMAINED) {
 565                 a = 1;
 566
 567                 while (a < track->markersnr) {
 568                         if (track->markers[a].framenr > ref_frame) {
 569                                 track->markersnr = a;
 570                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
 571
 572                                 break;
 573                         }
 574
 575                         a++;
 576                 }
 577
 578                 if (track->markersnr)
 579                         put_disabled_marker(track, &track->markers[track->markersnr - 1], 0, 1);
 580         }
 581         else if (action == TRACK_CLEAR_UPTO) {
 582                 a = track->markersnr - 1;
 583
 584                 while (a >= 0) {
 585                         if (track->markers[a].framenr <= ref_frame) {
 586                                 memmove(track->markers, track->markers + a, (track->markersnr - a) * sizeof(MovieTrackingMarker));
 587
 588                                 track->markersnr = track->markersnr - a;
 589                                 track->markers = MEM_reallocN(track->markers, sizeof(MovieTrackingMarker) * track->markersnr);
 590
 591                                 break;
 592                         }
 593
 594                         a--;
 595                 }
 596
 597                 if (track->markersnr)
 598                         put_disabled_marker(track, &track->markers[0], 1, 1);
 599         }
 600         else if (action == TRACK_CLEAR_ALL) {
 601                 MovieTrackingMarker *marker, marker_new;
 602
 603                 marker = BKE_tracking_get_marker(track, ref_frame);
 604                 marker_new = *marker;
 605
 606                 MEM_freeN(track->markers);
 607                 track->markers = NULL;
 608                 track->markersnr = 0;
 609
 610                 BKE_tracking_insert_marker(track, &marker_new);
 611
 612                 put_disabled_marker(track, &marker_new, 1, 1);
 613                 put_disabled_marker(track, &marker_new, 0, 1);
 614         }
 615 }
 616
 617 void BKE_tracking_join_tracks(MovieTrackingTrack *dst_track, MovieTrackingTrack *src_track)
 618 {
 619         int i = 0, a = 0, b = 0, tot;
 620         MovieTrackingMarker *markers;
 621
 622         tot = dst_track->markersnr + src_track->markersnr;
 623         markers = MEM_callocN(tot * sizeof(MovieTrackingMarker), "tmp tracking joined tracks");
 624
 625         while (a < src_track->markersnr || b < dst_track->markersnr) {
 626                 if (b >= dst_track->markersnr) {
 627                         markers[i] = src_track->markers[a++];
 628                 }
 629                 else if (a >= src_track->markersnr) {
 630                         markers[i] = dst_track->markers[b++];
 631                 }
 632                 else if (src_track->markers[a].framenr < dst_track->markers[b].framenr) {
 633                         markers[i] = src_track->markers[a++];
 634                 }
 635                 else if (src_track->markers[a].framenr > dst_track->markers[b].framenr) {
 636                         markers[i] = dst_track->markers[b++];
 637                 }
 638                 else {
 639                         if ((src_track->markers[a].flag & MARKER_DISABLED) == 0) {
 640                                 if ((dst_track->markers[b].flag & MARKER_DISABLED) == 0) {
 641                                         /* both tracks are enabled on this frame, so find the whole segment
 642                                          * on which tracks are intersecting and blend tracks using linear
 643                                          * interpolation to prevent jumps
 644                                          */
 645
 646                                         MovieTrackingMarker *marker_a, *marker_b;
 647                                         int start_a = a, start_b = b, len = 0, frame = src_track->markers[a].framenr;
 648                                         int j, inverse = 0;
 649
 650                                         inverse = (b == 0) ||
 651                                                   (dst_track->markers[b - 1].flag & MARKER_DISABLED) ||
 652                                                   (dst_track->markers[b - 1].framenr != frame - 1);
 653
 654                                         /* find length of intersection */
 655                                         while (a < src_track->markersnr && b < dst_track->markersnr) {
 656                                                 marker_a = &src_track->markers[a];
 657                                                 marker_b = &dst_track->markers[b];
 658
 659                                                 if (marker_a->flag & MARKER_DISABLED || marker_b->flag & MARKER_DISABLED)
 660                                                         break;
 661
 662                                                 if (marker_a->framenr != frame || marker_b->framenr != frame)
 663                                                         break;
 664
 665                                                 frame++;
 666                                                 len++;
 667                                                 a++;
 668                                                 b++;
 669                                         }
 670
 671                                         a = start_a;
 672                                         b = start_b;
 673
 674                                         /* linear interpolation for intersecting frames */
 675                                         for (j = 0; j < len; j++) {
 676                                                 float fac = 0.5f;
 677
 678                                                 if (len > 1)
 679                                                         fac = 1.0f / (len - 1) * j;
 680
 681                                                 if (inverse)
 682                                                         fac = 1.0f - fac;
 683
 684                                                 marker_a = &src_track->markers[a];
 685                                                 marker_b = &dst_track->markers[b];
 686
 687                                                 markers[i] = dst_track->markers[b];
 688                                                 interp_v2_v2v2(markers[i].pos, marker_b->pos, marker_a->pos, fac);
 689                                                 a++;
 690                                                 b++;
 691                                                 i++;
 692                                         }
 693
 694                                         /* this values will be incremented at the end of the loop cycle */
 695                                         a--; b--; i--;
 696                                 }
 697                                 else markers[i] = src_track->markers[a];
 698                         }
 699                         else markers[i] = dst_track->markers[b];
 700
 701                         a++;
 702                         b++;
 703                 }
 704
 705                 i++;
 706         }
 707
 708         MEM_freeN(dst_track->markers);
 709
 710         dst_track->markers = MEM_callocN(i * sizeof(MovieTrackingMarker), "tracking joined tracks");
 711         memcpy(dst_track->markers, markers, i * sizeof(MovieTrackingMarker));
 712
 713         dst_track->markersnr = i;
 714
 715         MEM_freeN(markers);
 716 }
 717
 718 static void tracking_tracks_free(ListBase *tracks)
 719 {
 720         MovieTrackingTrack *track;
 721
 722         for (track = tracks->first; track; track = track->next) {
 723                 BKE_tracking_free_track(track);
 724         }
 725
 726         BLI_freelistN(tracks);
 727 }
 728
 729 static void tracking_reconstruction_free(MovieTrackingReconstruction *reconstruction)
 730 {
 731         if (reconstruction->cameras)
 732                 MEM_freeN(reconstruction->cameras);
 733 }
 734
 735 static void tracking_object_free(MovieTrackingObject *object)
 736 {
 737         tracking_tracks_free(&object->tracks);
 738         tracking_reconstruction_free(&object->reconstruction);
 739 }
 740
 741 static void tracking_objects_free(ListBase *objects)
 742 {
 743         MovieTrackingObject *object;
 744
 745         for (object = objects->first; object; object = object->next)
 746                 tracking_object_free(object);
 747
 748         BLI_freelistN(objects);
 749 }
 750
 751 static void tracking_dopesheet_free(MovieTrackingDopesheet *dopesheet)
 752 {
 753         MovieTrackingDopesheetChannel *channel;
 754
 755         channel = dopesheet->channels.first;
 756         while (channel) {
 757                 if (channel->segments) {
 758                         MEM_freeN(channel->segments);
 759                 }
 760
 761                 channel = channel->next;
 762         }
 763
 764         BLI_freelistN(&dopesheet->channels);
 765
 766         dopesheet->channels.first = dopesheet->channels.last = NULL;
 767         dopesheet->tot_channel = 0;
 768 }
 769
 770 void BKE_tracking_free(MovieTracking *tracking)
 771 {
 772         tracking_tracks_free(&tracking->tracks);
 773         tracking_reconstruction_free(&tracking->reconstruction);
 774         tracking_objects_free(&tracking->objects);
 775
 776         if (tracking->stabilization.scaleibuf)
 777                 IMB_freeImBuf(tracking->stabilization.scaleibuf);
 778
 779         if (tracking->camera.intrinsics)
 780                 BKE_tracking_distortion_destroy(tracking->camera.intrinsics);
 781
 782         tracking_dopesheet_free(&tracking->dopesheet);
 783 }
 784
 785 static MovieTrackingTrack *duplicate_track(MovieTrackingTrack *track)
 786 {
 787         MovieTrackingTrack *new_track;
 788
 789         new_track = MEM_callocN(sizeof(MovieTrackingTrack), "tracksMapMerge new_track");
 790
 791         *new_track = *track;
 792         new_track->next = new_track->prev = NULL;
 793
 794         new_track->markers = MEM_dupallocN(new_track->markers);
 795
 796         return new_track;
 797 }
 798
 799 /*********************** clipboard *************************/
 800
 801 void BKE_tracking_free_clipboard(void)
 802 {
 803         MovieTrackingTrack *track = tracking_clipboard.tracks.first, *next_track;
 804
 805         while (track) {
 806                 next_track = track->next;
 807
 808                 BKE_tracking_free_track(track);
 809                 MEM_freeN(track);
 810
 811                 track = next_track;
 812         }
 813 }
 814
 815 void BKE_tracking_clipboard_copy_tracks(MovieTracking *tracking, MovieTrackingObject *object)
 816 {
 817         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
 818         MovieTrackingTrack *track = tracksbase->first;
 819
 820         BKE_tracking_free_clipboard();
 821
 822         while (track) {
 823                 if (TRACK_SELECTED(track) && (track->flag & TRACK_HIDDEN) == 0) {
 824                         MovieTrackingTrack *new_track = duplicate_track(track);
 825
 826                         BLI_addtail(&tracking_clipboard.tracks, new_track);
 827                 }
 828
 829                 track = track->next;
 830         }
 831 }
 832
 833 int BKE_tracking_clipboard_has_tracks(void)
 834 {
 835         return tracking_clipboard.tracks.first != NULL;
 836 }
 837
 838 void BKE_tracking_clipboard_paste_tracks(MovieTracking *tracking, MovieTrackingObject *object)
 839 {
 840         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
 841         MovieTrackingTrack *track = tracking_clipboard.tracks.first;
 842
 843         while (track) {
 844                 MovieTrackingTrack *new_track = duplicate_track(track);
 845
 846                 BLI_addtail(tracksbase, new_track);
 847                 BKE_track_unique_name(tracksbase, new_track);
 848
 849                 track = track->next;
 850         }
 851 }
 852
 853 /*********************** tracks map *************************/
 854
 855 typedef struct TracksMap {
 856         char object_name[MAX_NAME];
 857         int is_camera;
 858
 859         int num_tracks;
 860         int customdata_size;
 861
 862         char *customdata;
 863         MovieTrackingTrack *tracks;
 864
 865         GHash *hash;
 866
 867         int ptr;
 868 } TracksMap;
 869
 870 static TracksMap *tracks_map_new(const char *object_name, int is_camera, int num_tracks, int customdata_size)
 871 {
 872         TracksMap *map = MEM_callocN(sizeof(TracksMap), "TrackingsMap");
 873
 874         BLI_strncpy(map->object_name, object_name, sizeof(map->object_name));
 875         map->is_camera = is_camera;
 876
 877         map->num_tracks = num_tracks;
 878         map->customdata_size = customdata_size;
 879
 880         map->tracks = MEM_callocN(sizeof(MovieTrackingTrack) * num_tracks, "TrackingsMap tracks");
 881
 882         if (customdata_size)
 883                 map->customdata = MEM_callocN(customdata_size * num_tracks, "TracksMap customdata");
 884
 885         map->hash = BLI_ghash_ptr_new("TracksMap hash");
 886
 887         return map;
 888 }
 889
 890 static int tracks_map_size(TracksMap *map)
 891 {
 892         return map->num_tracks;
 893 }
 894
 895 static void tracks_map_get(TracksMap *map, int index, MovieTrackingTrack **track, void **customdata)
 896 {
 897         *track = &map->tracks[index];
 898
 899         if (map->customdata)
 900                 *customdata = &map->customdata[index * map->customdata_size];
 901 }
 902
 903 static void tracks_map_insert(TracksMap *map, MovieTrackingTrack *track, void *customdata)
 904 {
 905         MovieTrackingTrack new_track = *track;
 906
 907         new_track.markers = MEM_dupallocN(new_track.markers);
 908
 909         map->tracks[map->ptr] = new_track;
 910
 911         if (customdata)
 912                 memcpy(&map->customdata[map->ptr * map->customdata_size], customdata, map->customdata_size);
 913
 914         BLI_ghash_insert(map->hash, &map->tracks[map->ptr], track);
 915
 916         map->ptr++;
 917 }
 918
 919 static void tracks_map_merge(TracksMap *map, MovieTracking *tracking)
 920 {
 921         MovieTrackingTrack *track;
 922         MovieTrackingTrack *act_track = BKE_tracking_active_track(tracking);
 923         MovieTrackingTrack *rot_track = tracking->stabilization.rot_track;
 924         ListBase tracks = {NULL, NULL}, new_tracks = {NULL, NULL};
 925         ListBase *old_tracks;
 926         int a;
 927
 928         if (map->is_camera) {
 929                 old_tracks = &tracking->tracks;
 930         }
 931         else {
 932                 MovieTrackingObject *object = BKE_tracking_named_object(tracking, map->object_name);
 933
 934                 if (!object) {
 935                         /* object was deleted by user, create new one */
 936                         object = BKE_tracking_new_object(tracking, map->object_name);
 937                 }
 938
 939                 old_tracks = &object->tracks;
 940         }
 941
 942         /* duplicate currently operating tracks to temporary list.
 943          * this is needed to keep names in unique state and it's faster to change names
 944          * of currently operating tracks (if needed)
 945          */
 946         for (a = 0; a < map->num_tracks; a++) {
 947                 int replace_sel = 0, replace_rot = 0;
 948                 MovieTrackingTrack *new_track, *old;
 949
 950                 track = &map->tracks[a];
 951
 952                 /* find original of operating track in list of previously displayed tracks */
 953                 old = BLI_ghash_lookup(map->hash, track);
 954                 if (old) {
 955                         MovieTrackingTrack *cur = old_tracks->first;
 956
 957                         while (cur) {
 958                                 if (cur == old)
 959                                         break;
 960
 961                                 cur = cur->next;
 962                         }
 963
 964                         /* original track was found, re-use flags and remove this track */
 965                         if (cur) {
 966                                 if (cur == act_track)
 967                                         replace_sel = 1;
 968                                 if (cur == rot_track)
 969                                         replace_rot = 1;
 970
 971                                 track->flag = cur->flag;
 972                                 track->pat_flag = cur->pat_flag;
 973                                 track->search_flag = cur->search_flag;
 974
 975                                 BKE_tracking_free_track(cur);
 976                                 BLI_freelinkN(old_tracks, cur);
 977                         }
 978                 }
 979
 980                 new_track = duplicate_track(track);
 981
 982                 BLI_ghash_remove(map->hash, track, NULL, NULL); /* XXX: are we actually need this */
 983                 BLI_ghash_insert(map->hash, track, new_track);
 984
 985                 if (replace_sel)  /* update current selection in clip */
 986                         tracking->act_track = new_track;
 987
 988                 if (replace_rot)  /* update track used for rotation stabilization */
 989                         tracking->stabilization.rot_track = new_track;
 990
 991                 BLI_addtail(&tracks, new_track);
 992         }
 993
 994         /* move all tracks, which aren't operating */
 995         track = old_tracks->first;
 996         while (track) {
 997                 MovieTrackingTrack *next = track->next;
 998
 999                 track->next = track->prev = NULL;
1000                 BLI_addtail(&new_tracks, track);
1001
1002                 track = next;
1003         }
1004
1005         /* now move all tracks which are currently operating and keep their names unique */
1006         track = tracks.first;
1007         while (track) {
1008                 MovieTrackingTrack *next = track->next;
1009
1010                 BLI_remlink(&tracks, track);
1011
1012                 track->next = track->prev = NULL;
1013                 BLI_addtail(&new_tracks, track);
1014
1015                 BLI_uniquename(&new_tracks, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
1016
1017                 track = next;
1018         }
1019
1020         *old_tracks = new_tracks;
1021 }
1022
1023 static void tracks_map_free(TracksMap *map, void (*customdata_free)(void *customdata))
1024 {
1025         int i = 0;
1026
1027         BLI_ghash_free(map->hash, NULL, NULL);
1028
1029         for (i = 0; i < map->num_tracks; i++) {
1030                 if (map->customdata && customdata_free)
1031                         customdata_free(&map->customdata[i * map->customdata_size]);
1032
1033                 BKE_tracking_free_track(&map->tracks[i]);
1034         }
1035
1036         if (map->customdata)
1037                 MEM_freeN(map->customdata);
1038
1039         MEM_freeN(map->tracks);
1040         MEM_freeN(map);
1041 }
1042
1043 /*********************** tracking *************************/
1044
1045 typedef struct TrackContext {
1046 #ifdef WITH_LIBMV
1047         /* the reference marker and cutout search area */
1048         MovieTrackingMarker marker;
1049
1050         /* keyframed patch. This is the search area */
1051         float *search_area;
1052         int search_area_height;
1053         int search_area_width;
1054         int framenr;
1055
1056         float *mask;
1057 #else
1058         int pad;
1059 #endif
1060 } TrackContext;
1061
1062 typedef struct MovieTrackingContext {
1063         MovieClipUser user;
1064         MovieClip *clip;
1065         int clip_flag;
1066
1067         int first_time, frames;
1068
1069         MovieTrackingSettings settings;
1070         TracksMap *tracks_map;
1071
1072         short backwards, sequence;
1073         int sync_frame;
1074 } MovieTrackingContext;
1075
1076 MovieTrackingContext *BKE_tracking_context_new(MovieClip *clip, MovieClipUser *user, short backwards, short sequence)
1077 {
1078         MovieTrackingContext *context = MEM_callocN(sizeof(MovieTrackingContext), "trackingContext");
1079         MovieTracking *tracking = &clip->tracking;
1080         MovieTrackingSettings *settings = &tracking->settings;
1081         ListBase *tracksbase = BKE_tracking_get_tracks(tracking);
1082         MovieTrackingTrack *track;
1083         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
1084         int num_tracks = 0;
1085
1086         context->settings = *settings;
1087         context->backwards = backwards;
1088         context->sync_frame = user->framenr;
1089         context->first_time = TRUE;
1090         context->sequence = sequence;
1091
1092         /* count */
1093         track = tracksbase->first;
1094         while (track) {
1095                 if (TRACK_SELECTED(track) && (track->flag & (TRACK_LOCKED | TRACK_HIDDEN)) == 0) {
1096                         int framenr = BKE_movieclip_remap_scene_to_clip_frame(clip, user->framenr);
1097                         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
1098
1099                         if ((marker->flag & MARKER_DISABLED) == 0)
1100                                 num_tracks++;
1101                 }
1102
1103                 track = track->next;
1104         }
1105
1106         if (num_tracks) {
1107                 int width, height;
1108
1109                 context->tracks_map = tracks_map_new(object->name, object->flag & TRACKING_OBJECT_CAMERA,
1110                                                      num_tracks, sizeof(TrackContext));
1111
1112                 BKE_movieclip_get_size(clip, user, &width, &height);
1113
1114                 /* create tracking data */
1115                 track = tracksbase->first;
1116                 while (track) {
1117                         if (TRACK_SELECTED(track) && (track->flag & (TRACK_HIDDEN | TRACK_LOCKED)) == 0) {
1118                                 int framenr = BKE_movieclip_remap_scene_to_clip_frame(clip, user->framenr);
1119                                 MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
1120
1121                                 if ((marker->flag & MARKER_DISABLED) == 0) {
1122                                         TrackContext track_context;
1123                                         memset(&track_context, 0, sizeof(TrackContext));
1124                                         tracks_map_insert(context->tracks_map, track, &track_context);
1125                                 }
1126                         }
1127
1128                         track = track->next;
1129                 }
1130         }
1131
1132         context->clip = clip;
1133
1134         /* store needed clip flags passing to get_buffer functions
1135          * - MCLIP_USE_PROXY is needed to because timecode affects on movie clip
1136          *   only in case Proxy/Timecode flag is set, so store this flag to use
1137          *   timecodes properly but reset render size to SIZE_FULL so correct resolution
1138          *   would be used for images
1139          * - MCLIP_USE_PROXY_CUSTOM_DIR is needed because proxy/timecode files might
1140          *   be stored in a different location
1141          * ignore all the rest possible flags for now
1142          */
1143         context->clip_flag = clip->flag & MCLIP_TIMECODE_FLAGS;
1144
1145         context->user = *user;
1146         context->user.render_size = MCLIP_PROXY_RENDER_SIZE_FULL;
1147         context->user.render_flag = 0;
1148
1149         if (!sequence)
1150                 BLI_begin_threaded_malloc();
1151
1152         return context;
1153 }
1154
1155 static void track_context_free(void *customdata)
1156 {
1157         TrackContext *track_context = (TrackContext *)customdata;
1158
1159 #if WITH_LIBMV
1160         if (track_context->search_area)
1161                 MEM_freeN(track_context->search_area);
1162
1163         if (track_context->mask)
1164                 MEM_freeN(track_context->mask);
1165
1166 #else
1167         (void)track_context;
1168 #endif
1169 }
1170
1171 void BKE_tracking_context_free(MovieTrackingContext *context)
1172 {
1173         if (!context->sequence)
1174                 BLI_end_threaded_malloc();
1175
1176         tracks_map_free(context->tracks_map, track_context_free);
1177
1178         MEM_freeN(context);
1179 }
1180
1181 /* zap channels from the imbuf that are disabled by the user. this can lead to
1182  * better tracks sometimes. however, instead of simply zeroing the channels
1183  * out, do a partial grayscale conversion so the display is better.
1184  */
1185 void BKE_tracking_disable_imbuf_channels(ImBuf *ibuf, int disable_red, int disable_green, int disable_blue,
1186                                          int grayscale)
1187 {
1188         int x, y;
1189         float scale;
1190
1191         if (!disable_red && !disable_green && !disable_blue && !grayscale)
1192                 return;
1193
1194         /* If only some components are selected, it's important to rescale the result
1195          * appropriately so that e.g. if only blue is selected, it's not zeroed out.
1196          */
1197         scale = (disable_red   ? 0.0f : 0.2126f) +
1198                 (disable_green ? 0.0f : 0.7152f) +
1199                 (disable_blue  ? 0.0f : 0.0722f);
1200
1201         for (y = 0; y < ibuf->y; y++) {
1202                 for (x = 0; x < ibuf->x; x++) {
1203                         int pixel = ibuf->x * y + x;
1204
1205                         if (ibuf->rect_float) {
1206                                 float *rrgbf = ibuf->rect_float + pixel * 4;
1207                                 float r = disable_red   ? 0.0f : rrgbf[0];
1208                                 float g = disable_green ? 0.0f : rrgbf[1];
1209                                 float b = disable_blue  ? 0.0f : rrgbf[2];
1210
1211                                 if (grayscale) {
1212                                         float gray = (0.2126f * r + 0.7152f * g + 0.0722f * b) / scale;
1213
1214                                         rrgbf[0] = rrgbf[1] = rrgbf[2] = gray;
1215                                 }
1216                                 else {
1217                                         rrgbf[0] = r;
1218                                         rrgbf[1] = g;
1219                                         rrgbf[2] = b;
1220                                 }
1221                         }
1222                         else {
1223                                 char *rrgb = (char *)ibuf->rect + pixel * 4;
1224                                 char r = disable_red   ? 0 : rrgb[0];
1225                                 char g = disable_green ? 0 : rrgb[1];
1226                                 char b = disable_blue  ? 0 : rrgb[2];
1227
1228                                 if (grayscale) {
1229                                         float gray = (0.2126f * r + 0.7152f * g + 0.0722f * b) / scale;
1230
1231                                         rrgb[0] = rrgb[1] = rrgb[2] = gray;
1232                                 }
1233                                 else {
1234                                         rrgb[0] = r;
1235                                         rrgb[1] = g;
1236                                         rrgb[2] = b;
1237                                 }
1238                         }
1239                 }
1240         }
1241
1242         if (ibuf->rect_float)
1243                 ibuf->userflags |= IB_RECT_INVALID;
1244 }
1245
1246 static void disable_imbuf_channels(ImBuf *ibuf, MovieTrackingTrack *track, int grayscale)
1247 {
1248         BKE_tracking_disable_imbuf_channels(ibuf, track->flag & TRACK_DISABLE_RED,
1249                                             track->flag & TRACK_DISABLE_GREEN, track->flag & TRACK_DISABLE_BLUE, grayscale);
1250 }
1251
1252 ImBuf *BKE_tracking_sample_pattern_imbuf(int frame_width, int frame_height, ImBuf *search_ibuf,
1253                                          MovieTrackingTrack *track, MovieTrackingMarker *marker,
1254                                          int use_mask, int num_samples_x, int num_samples_y,
1255                                          float pos[2])
1256 {
1257 #ifdef WITH_LIBMV
1258         ImBuf *pattern_ibuf;
1259         double src_pixel_x[5], src_pixel_y[5];
1260         double warped_position_x, warped_position_y;
1261         float *mask = NULL;
1262
1263         pattern_ibuf = IMB_allocImBuf(num_samples_x, num_samples_y, 32, IB_rectfloat);
1264         pattern_ibuf->profile = IB_PROFILE_LINEAR_RGB;
1265
1266         if (!search_ibuf->rect_float) {
1267                 IMB_float_from_rect(search_ibuf);
1268         }
1269
1270         get_marker_coords_for_tracking(frame_width, frame_height, marker, src_pixel_x, src_pixel_y);
1271
1272         if (use_mask) {
1273                 mask = BKE_tracking_track_mask_get(frame_width, frame_height, track, marker);
1274         }
1275
1276         libmv_samplePlanarPatch(search_ibuf->rect_float, search_ibuf->x, search_ibuf->y, 4,
1277                                 src_pixel_x, src_pixel_y, num_samples_x,
1278                                 num_samples_y, mask, pattern_ibuf->rect_float,
1279                                 &warped_position_x, &warped_position_y);
1280
1281         if (pos) {
1282                 pos[0] = warped_position_x;
1283                 pos[1] = warped_position_y;
1284         }
1285
1286         if (mask) {
1287                 MEM_freeN(mask);
1288         }
1289
1290         return pattern_ibuf;
1291 #else
1292         ImBuf *pattern_ibuf;
1293
1294         /* real sampling requires libmv, but areas are supposing pattern would be
1295          * sampled if search area does exists, so we'll need to create empty
1296          * pattern area here to prevent adding NULL-checks all over just to deal
1297          * with situation when lubmv is disabled
1298          */
1299
1300         (void) frame_width;
1301         (void) frame_height;
1302         (void) search_ibuf;
1303         (void) marker;
1304         (void) track;
1305         (void) use_mask;
1306
1307         pattern_ibuf = IMB_allocImBuf(num_samples_x, num_samples_y, 32, IB_rectfloat);
1308
1309         pos[0] = num_samples_x / 2.0f;
1310         pos[1] = num_samples_y / 2.0f;
1311
1312         return pattern_ibuf;
1313 #endif
1314 }
1315
1316 ImBuf *BKE_tracking_get_pattern_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1317                                       int anchored, int disable_channels)
1318 {
1319         ImBuf *pattern_ibuf, *search_ibuf;
1320         float pat_min[2], pat_max[2];
1321         int num_samples_x, num_samples_y;
1322
1323         BKE_tracking_marker_pattern_minmax(marker, pat_min, pat_max);
1324
1325         num_samples_x = (pat_max[0] - pat_min[0]) * ibuf->x;
1326         num_samples_y = (pat_max[1] - pat_min[1]) * ibuf->y;
1327
1328         search_ibuf = BKE_tracking_get_search_imbuf(ibuf, track, marker, anchored, disable_channels);
1329
1330         pattern_ibuf = BKE_tracking_sample_pattern_imbuf(ibuf->x, ibuf->y, search_ibuf, track, marker,
1331                                                          FALSE, num_samples_x, num_samples_y, NULL);
1332
1333         IMB_freeImBuf(search_ibuf);
1334
1335         return pattern_ibuf;
1336 }
1337
1338 ImBuf *BKE_tracking_get_search_imbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1339                                      int anchored, int disable_channels)
1340 {
1341         ImBuf *searchibuf;
1342         int x, y, w, h;
1343         float search_origin[2];
1344
1345         get_search_origin_frame_pixel(ibuf->x, ibuf->y, marker, search_origin);
1346
1347         x = search_origin[0];
1348         y = search_origin[1];
1349
1350         if (anchored) {
1351                 x += track->offset[0] * ibuf->x;
1352                 y += track->offset[1] * ibuf->y;
1353         }
1354
1355         w = (marker->search_max[0] - marker->search_min[0]) * ibuf->x;
1356         h = (marker->search_max[1] - marker->search_min[1]) * ibuf->y;
1357
1358         searchibuf = IMB_allocImBuf(w, h, 32, ibuf->rect_float ? IB_rectfloat : IB_rect);
1359         searchibuf->profile = ibuf->profile;
1360
1361         IMB_rectcpy(searchibuf, ibuf, 0, 0, x, y, w, h);
1362
1363         if (disable_channels) {
1364                 if ((track->flag & TRACK_PREVIEW_GRAYSCALE) ||
1365                     (track->flag & TRACK_DISABLE_RED)       ||
1366                     (track->flag & TRACK_DISABLE_GREEN)     ||
1367                     (track->flag & TRACK_DISABLE_BLUE))
1368                 {
1369                         disable_imbuf_channels(searchibuf, track, TRUE);
1370                 }
1371         }
1372
1373         return searchibuf;
1374 }
1375
1376 static bGPDlayer *track_mask_gpencil_layer_get(MovieTrackingTrack *track)
1377 {
1378         bGPDlayer *layer;
1379
1380         if (!track->gpd)
1381                 return NULL;
1382
1383         layer = track->gpd->layers.first;
1384
1385         while (layer) {
1386                 if (layer->flag & GP_LAYER_ACTIVE) {
1387                         bGPDframe *frame = layer->frames.first;
1388                         int ok = FALSE;
1389
1390                         while (frame) {
1391                                 if (frame->strokes.first) {
1392                                         ok = TRUE;
1393                                 }
1394
1395                                 frame = frame->next;
1396                         }
1397
1398                         if (ok)
1399                                 return layer;
1400                 }
1401
1402                 layer = layer->next;
1403         }
1404
1405         return NULL;
1406 }
1407
1408 static void track_mask_gpencil_layer_rasterize(int frame_width, int frame_height,
1409                                                                                            MovieTrackingMarker *marker, bGPDlayer *layer,
1410                                                float *mask, int mask_width, int mask_height)
1411 {
1412         bGPDframe *frame = layer->frames.first;
1413
1414         while (frame) {
1415                 bGPDstroke *stroke = frame->strokes.first;
1416
1417                 while (stroke) {
1418                         bGPDspoint *stroke_points = stroke->points;
1419                         float *mask_points, *fp;
1420                         int i;
1421
1422                         if (stroke->flag & GP_STROKE_2DSPACE) {
1423                                 fp = mask_points = MEM_callocN(2 * stroke->totpoints * sizeof(float),
1424                                                                "track mask rasterization points");
1425
1426                                 for (i = 0; i < stroke->totpoints; i++, fp += 2) {
1427                                         fp[0] = (stroke_points[i].x - marker->search_min[0]) * frame_width / mask_width;
1428                                         fp[1] = (stroke_points[i].y - marker->search_min[1]) * frame_height / mask_height;
1429                                 }
1430
1431                                 PLX_raskterize((float (*)[2])mask_points, stroke->totpoints, mask, mask_width, mask_height, FALSE /* XXX- TODO: make on/off for AA*/);
1432
1433                                 MEM_freeN(mask_points);
1434                         }
1435
1436                         stroke = stroke->next;
1437                 }
1438
1439                 frame = frame->next;
1440         }
1441 }
1442
1443 float *BKE_tracking_track_mask_get(int frame_width, int frame_height,
1444                                    MovieTrackingTrack *track, MovieTrackingMarker *marker)
1445 {
1446         float *mask = NULL;
1447         bGPDlayer *layer = track_mask_gpencil_layer_get(track);
1448         int mask_width, mask_height;
1449
1450         mask_width = (marker->search_max[0] - marker->search_min[0]) * frame_width;
1451         mask_height = (marker->search_max[1] - marker->search_min[1]) * frame_height;
1452
1453         if (layer) {
1454                 mask = MEM_callocN(mask_width * mask_height * sizeof(float), "track mask");
1455
1456                 track_mask_gpencil_layer_rasterize(frame_width, frame_height, marker, layer,
1457                                                    mask, mask_width, mask_height);
1458         }
1459
1460         return mask;
1461 }
1462
1463 #ifdef WITH_LIBMV
1464
1465 /* Convert from float and byte RGBA to grayscale. Supports different coefficients for RGB. */
1466 static void float_rgba_to_gray(const float *rgba, float *gray, int num_pixels,
1467                                float weight_red, float weight_green, float weight_blue)
1468 {
1469         int i;
1470
1471         for (i = 0; i < num_pixels; i++) {
1472                 const float *pixel = rgba + 4 * i;
1473
1474                 gray[i] = weight_red * pixel[0] + weight_green * pixel[1] + weight_blue * pixel[2];
1475         }
1476 }
1477
1478 static void uint8_rgba_to_float_gray(const unsigned char *rgba, float *gray, int num_pixels,
1479                                      float weight_red, float weight_green, float weight_blue)
1480 {
1481         int i;
1482
1483         for (i = 0; i < num_pixels; i++) {
1484                 const unsigned char *pixel = rgba + i * 4;
1485
1486                 *gray++ = (weight_red * pixel[0] + weight_green * pixel[1] + weight_blue * pixel[2]) / 255.0f;
1487         }
1488 }
1489
1490 static float *get_search_floatbuf(ImBuf *ibuf, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1491                                   int *width_r, int *height_r)
1492 {
1493         ImBuf *searchibuf;
1494         float *gray_pixels;
1495         int width, height;
1496
1497         searchibuf = BKE_tracking_get_search_imbuf(ibuf, track, marker, FALSE, TRUE);
1498
1499         width = searchibuf->x;
1500         height = searchibuf->y;
1501
1502         *width_r = searchibuf->x;
1503         *height_r = searchibuf->y;
1504
1505         gray_pixels = MEM_callocN(width * height * sizeof(float), "tracking floatBuf");
1506
1507         if (searchibuf->rect_float) {
1508                 float_rgba_to_gray(searchibuf->rect_float, gray_pixels, width * height,
1509                                    0.2126f, 0.7152f, 0.0722f);
1510         }
1511         else {
1512                 uint8_rgba_to_float_gray((unsigned char *)searchibuf->rect, gray_pixels, width * height,
1513                                          0.2126f, 0.7152f, 0.0722f);
1514         }
1515
1516         IMB_freeImBuf(searchibuf);
1517
1518         return gray_pixels;
1519 }
1520
1521 static unsigned char *get_ucharbuf(ImBuf *ibuf)
1522 {
1523         int x, y;
1524         unsigned char *pixels, *cp;
1525
1526         cp = pixels = MEM_callocN(ibuf->x * ibuf->y * sizeof(unsigned char), "tracking ucharBuf");
1527         for (y = 0; y < ibuf->y; y++) {
1528                 for (x = 0; x < ibuf->x; x++) {
1529                         int pixel = ibuf->x * y + x;
1530
1531                         if (ibuf->rect_float) {
1532                                 const float *rrgbf = ibuf->rect_float + pixel * 4;
1533                                 const float grey_f = 0.2126f * rrgbf[0] + 0.7152f * rrgbf[1] + 0.0722f * rrgbf[2];
1534
1535                                 *cp = FTOCHAR(grey_f);
1536                         }
1537                         else {
1538                                 const unsigned char *rrgb = (unsigned char *)ibuf->rect + pixel * 4;
1539
1540                                 *cp = 0.2126f * rrgb[0] + 0.7152f * rrgb[1] + 0.0722f * rrgb[2];
1541                         }
1542
1543                         cp++;
1544                 }
1545         }
1546
1547         return pixels;
1548 }
1549
1550 static ImBuf *get_frame_ibuf(MovieTrackingContext *context, int framenr)
1551 {
1552         ImBuf *ibuf;
1553         MovieClipUser user = context->user;
1554
1555         user.framenr = BKE_movieclip_remap_clip_to_scene_frame(context->clip, framenr);
1556
1557         ibuf = BKE_movieclip_get_ibuf_flag(context->clip, &user, context->clip_flag, MOVIECLIP_CACHE_SKIP);
1558
1559         return ibuf;
1560 }
1561
1562 static ImBuf *get_keyframed_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track,
1563                                  MovieTrackingMarker *marker, MovieTrackingMarker **marker_keyed)
1564 {
1565         int framenr = marker->framenr;
1566         int a = marker - track->markers;
1567
1568         *marker_keyed = marker;
1569
1570         while (a >= 0 && a < track->markersnr) {
1571                 int next = (context->backwards) ? a + 1 : a - 1;
1572                 int is_keyframed = FALSE;
1573                 MovieTrackingMarker *cur_marker = &track->markers[a];
1574                 MovieTrackingMarker *next_marker = NULL;
1575
1576                 if (next >= 0 && next < track->markersnr)
1577                         next_marker = &track->markers[next];
1578
1579                 /* if next mrker is disabled, stop searching keyframe and use current frame as keyframe */
1580                 if (next_marker && next_marker->flag & MARKER_DISABLED)
1581                         is_keyframed = TRUE;
1582
1583                 is_keyframed |= (cur_marker->flag & MARKER_TRACKED) == 0;
1584
1585                 if (is_keyframed) {
1586                         framenr = cur_marker->framenr;
1587                         *marker_keyed = cur_marker;
1588
1589                         break;
1590                 }
1591
1592                 a = next;
1593         }
1594
1595         return get_frame_ibuf(context, framenr);
1596 }
1597
1598 static ImBuf *get_adjust_ibuf(MovieTrackingContext *context, MovieTrackingTrack *track, MovieTrackingMarker *marker,
1599                               int curfra, MovieTrackingMarker **marker_keyed)
1600 {
1601         ImBuf *ibuf = NULL;
1602
1603         if (track->pattern_match == TRACK_MATCH_KEYFRAME) {
1604                 ibuf = get_keyframed_ibuf(context, track, marker, marker_keyed);
1605         }
1606         else {
1607                 ibuf = get_frame_ibuf(context, curfra);
1608
1609                 /* use current marker as keyframed position */
1610                 *marker_keyed = marker;
1611         }
1612
1613         return ibuf;
1614 }
1615
1616 static void marker_search_scale_after_tracking(const MovieTrackingMarker *old_marker, MovieTrackingMarker *new_marker)
1617 {
1618         float old_pat_min[2], old_pat_max[2];
1619         float new_pat_min[2], new_pat_max[2];
1620         float scale_x, scale_y;
1621
1622         BKE_tracking_marker_pattern_minmax(old_marker, old_pat_min, old_pat_max);
1623         BKE_tracking_marker_pattern_minmax(new_marker, new_pat_min, new_pat_max);
1624
1625         scale_x = (new_pat_max[0] - new_pat_min[0]) / (old_pat_max[0] - old_pat_min[0]);
1626         scale_y = (new_pat_max[1] - new_pat_min[1]) / (old_pat_max[1] - old_pat_min[1]);
1627
1628         new_marker->search_min[0] *= scale_x;
1629         new_marker->search_min[1] *= scale_y;
1630
1631         new_marker->search_max[0] *= scale_x;
1632         new_marker->search_max[1] *= scale_y;
1633 }
1634
1635 #endif
1636
1637 void BKE_tracking_sync(MovieTrackingContext *context)
1638 {
1639         MovieTracking *tracking = &context->clip->tracking;
1640         int newframe;
1641
1642         tracks_map_merge(context->tracks_map, tracking);
1643
1644         if (context->backwards)
1645                 newframe = context->user.framenr + 1;
1646         else
1647                 newframe = context->user.framenr - 1;
1648
1649         context->sync_frame = newframe;
1650
1651         tracking->dopesheet.ok = FALSE;
1652 }
1653
1654 void BKE_tracking_sync_user(MovieClipUser *user, MovieTrackingContext *context)
1655 {
1656         user->framenr = context->sync_frame;
1657 }
1658
1659 int BKE_tracking_next(MovieTrackingContext *context)
1660 {
1661         ImBuf *destination_ibuf;
1662         int curfra =  BKE_movieclip_remap_scene_to_clip_frame(context->clip, context->user.framenr);
1663         int a, ok = FALSE, map_size;
1664
1665         int frame_width, frame_height;
1666
1667         map_size = tracks_map_size(context->tracks_map);
1668
1669         /* nothing to track, avoid unneeded frames reading to save time and memory */
1670         if (!map_size)
1671                 return FALSE;
1672
1673         if (context->backwards)
1674                 context->user.framenr--;
1675         else
1676                 context->user.framenr++;
1677
1678         destination_ibuf = BKE_movieclip_get_ibuf_flag(context->clip, &context->user,
1679                                                        context->clip_flag, MOVIECLIP_CACHE_SKIP);
1680         if (!destination_ibuf)
1681                 return FALSE;
1682
1683         frame_width = destination_ibuf->x;
1684         frame_height = destination_ibuf->y;
1685
1686         //#pragma omp parallel for private(a) shared(destination_ibuf, ok) if (map_size>1)
1687         for (a = 0; a < map_size; a++) {
1688                 TrackContext *track_context = NULL;
1689                 MovieTrackingTrack *track;
1690                 MovieTrackingMarker *marker;
1691
1692                 tracks_map_get(context->tracks_map, a, &track, (void **)&track_context);
1693
1694                 marker = BKE_tracking_exact_marker(track, curfra);
1695
1696                 if (marker && (marker->flag & MARKER_DISABLED) == 0) {
1697 #ifdef WITH_LIBMV
1698                         int width, height, tracked = 0, need_readjust = 0;
1699                         float margin[2], dim[2], pat_min[2], pat_max[2];
1700                         MovieTrackingMarker marker_new, *marker_keyed;
1701                         int onbound = FALSE, nextfra;
1702                         double dst_pixel_x[5], dst_pixel_y[5];
1703
1704                         if (track->pattern_match == TRACK_MATCH_KEYFRAME)
1705                                 need_readjust = context->first_time;
1706                         else
1707                                 need_readjust = TRUE;
1708
1709                         if (context->backwards)
1710                                 nextfra = curfra - 1;
1711                         else
1712                                 nextfra = curfra + 1;
1713
1714                         /* margin from frame boundaries */
1715                         BKE_tracking_marker_pattern_minmax(marker, pat_min, pat_max);
1716                         sub_v2_v2v2(dim, pat_max, pat_min);
1717                         margin[0] = margin[1] = MAX2(dim[0], dim[1]) / 2.0f;
1718
1719                         margin[0] = MAX2(margin[0], (float)track->margin / destination_ibuf->x);
1720                         margin[1] = MAX2(margin[1], (float)track->margin / destination_ibuf->y);
1721
1722                         /* do not track markers which are too close to boundary */
1723                         if (marker->pos[0] < margin[0] || marker->pos[0] > 1.0f - margin[0] ||
1724                             marker->pos[1] < margin[1] || marker->pos[1] > 1.0f - margin[1])
1725                         {
1726                                 onbound = TRUE;
1727                         }
1728                         else {
1729                                 /* to convert to the x/y split array format for libmv. */
1730                                 double src_pixel_x[5];
1731                                 double src_pixel_y[5];
1732
1733                                 /* settings for the tracker */
1734                                 struct libmv_trackRegionOptions options = {0};
1735                                 struct libmv_trackRegionResult result;
1736
1737                                 float *patch_new;
1738
1739                                 if (need_readjust) {
1740                                         ImBuf *reference_ibuf = NULL;
1741                                         /* calculate patch for keyframed position */
1742                                         reference_ibuf = get_adjust_ibuf(context, track, marker, curfra, &marker_keyed);
1743                                         track_context->marker = *marker_keyed;
1744
1745                                         if (track_context->search_area)
1746                                                 MEM_freeN(track_context->search_area);
1747
1748                                         track_context->search_area = get_search_floatbuf(reference_ibuf, track,
1749                                                                                          marker_keyed, &width, &height);
1750                                         track_context->search_area_height = height;
1751                                         track_context->search_area_width = width;
1752
1753                                         IMB_freeImBuf(reference_ibuf);
1754
1755                                         if ((track->algorithm_flag & TRACK_ALGORITHM_FLAG_USE_MASK) != 0) {
1756                                                 if (track_context->mask)
1757                                                         MEM_freeN(track_context->mask);
1758
1759                                                 track_context->mask = BKE_tracking_track_mask_get(frame_width, frame_height,
1760                                                                                                   track, marker);
1761                                         }
1762                                 }
1763
1764                                 /* for now track to the same search area dimension as marker has got for current frame
1765                                  * will make all tracked markers in currently tracked segment have the same search area
1766                                  * size, but it's quite close to what is actually needed
1767                                  */
1768                                 patch_new = get_search_floatbuf(destination_ibuf, track, marker, &width, &height);
1769
1770                                 /* Configure the tracker */
1771                                 options.motion_model = track->motion_model;
1772
1773                                 options.use_brute =
1774                                     ((track->algorithm_flag & TRACK_ALGORITHM_FLAG_USE_BRUTE) != 0);
1775
1776                                 options.use_normalization =
1777                                     ((track->algorithm_flag & TRACK_ALGORITHM_FLAG_USE_NORMALIZATION) != 0);
1778
1779                                 options.num_iterations = 50;
1780                                 options.minimum_correlation = track->minimum_correlation;
1781                                 options.sigma = 0.9;
1782
1783                                 if ((track->algorithm_flag & TRACK_ALGORITHM_FLAG_USE_MASK) != 0)
1784                                         options.image1_mask = track_context->mask;
1785
1786                                 /* Convert the marker corners and center into pixel coordinates in the search/destination images. */
1787                                 get_marker_coords_for_tracking(frame_width, frame_height, &track_context->marker, src_pixel_x, src_pixel_y);
1788                                 get_marker_coords_for_tracking(frame_width, frame_height, marker, dst_pixel_x, dst_pixel_y);
1789
1790                                 /* Run the tracker! */
1791                                 tracked = libmv_trackRegion(&options,
1792                                                             track_context->search_area,
1793                                                                                         track_context->search_area_width,
1794                                                                                         track_context->search_area_height,
1795                                                                                         patch_new, width, height,
1796                                                             src_pixel_x, src_pixel_y,
1797                                                             &result,
1798                                                             dst_pixel_x, dst_pixel_y);
1799                                 MEM_freeN(patch_new);
1800                         }
1801
1802                         if (tracked && !onbound) {
1803                                 memset(&marker_new, 0, sizeof(marker_new));
1804                                 marker_new = *marker;
1805                                 set_marker_coords_from_tracking(frame_width, frame_height, &marker_new, dst_pixel_x, dst_pixel_y);
1806                                 marker_new.flag |= MARKER_TRACKED;
1807                                 marker_new.framenr = nextfra;
1808
1809                                 marker_search_scale_after_tracking(marker, &marker_new);
1810
1811                                 //#pragma omp critical
1812                                 {
1813                                         if (context->first_time) {
1814                                                 /* check if there's no keyframe/tracked markers before tracking marker.
1815                                                  * if so -- create disabled marker before currently tracking "segment"
1816                                                  */
1817
1818                                                 put_disabled_marker(track, &marker_new, !context->backwards, 0);
1819                                         }
1820
1821                                         /* insert currently tracked marker */
1822                                         BKE_tracking_insert_marker(track, &marker_new);
1823
1824                                         /* make currently tracked segment be finished with disabled marker */
1825                                         put_disabled_marker(track, &marker_new, context->backwards, 0);
1826                                 }
1827                         }
1828                         else {
1829                                 marker_new = *marker;
1830
1831                                 marker_new.framenr = nextfra;
1832                                 marker_new.flag |= MARKER_DISABLED;
1833
1834                                 //#pragma omp critical
1835                                 {
1836                                         BKE_tracking_insert_marker(track, &marker_new);
1837                                 }
1838                         }
1839
1840                         ok = TRUE;
1841 #else
1842                         (void)frame_height;
1843                         (void)frame_width;
1844 #endif
1845                 }
1846         }
1847
1848         IMB_freeImBuf(destination_ibuf);
1849
1850         context->first_time = FALSE;
1851         context->frames++;
1852
1853         return ok;
1854 }
1855
1856 /*********************** camera solving *************************/
1857
1858 typedef struct MovieReconstructContext {
1859 #ifdef WITH_LIBMV
1860         struct libmv_Tracks *tracks;
1861         int keyframe1, keyframe2;
1862         short refine_flags;
1863
1864         struct libmv_Reconstruction *reconstruction;
1865 #endif
1866         char object_name[MAX_NAME];
1867         int is_camera;
1868         short motion_flag;
1869
1870         float focal_length;
1871         float principal_point[2];
1872         float k1, k2, k3;
1873
1874         float reprojection_error;
1875
1876         TracksMap *tracks_map;
1877
1878         int sfra, efra;
1879 } MovieReconstructContext;
1880
1881 typedef struct ReconstructProgressData {
1882         short *stop;
1883         short *do_update;
1884         float *progress;
1885         char *stats_message;
1886         int message_size;
1887 } ReconstructProgressData;
1888
1889 #if WITH_LIBMV
1890 static struct libmv_Tracks *create_libmv_tracks(ListBase *tracksbase, int width, int height)
1891 {
1892         int tracknr = 0;
1893         MovieTrackingTrack *track;
1894         struct libmv_Tracks *tracks = libmv_tracksNew();
1895
1896         track = tracksbase->first;
1897         while (track) {
1898                 int a = 0;
1899
1900                 for (a = 0; a < track->markersnr; a++) {
1901                         MovieTrackingMarker *marker = &track->markers[a];
1902
1903                         if ((marker->flag & MARKER_DISABLED) == 0) {
1904                                 libmv_tracksInsert(tracks, marker->framenr, tracknr,
1905                                                    marker->pos[0] * width, marker->pos[1] * height);
1906                         }
1907                 }
1908
1909                 track = track->next;
1910                 tracknr++;
1911         }
1912
1913         return tracks;
1914 }
1915
1916 static void retrieve_libmv_reconstruct_intrinscis(MovieReconstructContext *context, MovieTracking *tracking)
1917 {
1918         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
1919         struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_ReconstructionExtractIntrinsics(libmv_reconstruction);
1920
1921         float aspy = 1.0f / tracking->camera.pixel_aspect;
1922
1923         double focal_length, principal_x, principal_y, k1, k2, k3;
1924         int width, height;
1925
1926         libmv_CameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
1927                                       &k1, &k2, &k3, &width, &height);
1928
1929         tracking->camera.focal = focal_length;
1930         tracking->camera.principal[0] = principal_x;
1931
1932         tracking->camera.principal[1] = principal_y / aspy;
1933         tracking->camera.k1 = k1;
1934         tracking->camera.k2 = k2;
1935 }
1936
1937 static int retrieve_libmv_reconstruct_tracks(MovieReconstructContext *context, MovieTracking *tracking)
1938 {
1939         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
1940         MovieTrackingReconstruction *reconstruction = NULL;
1941         MovieReconstructedCamera *reconstructed;
1942         MovieTrackingTrack *track;
1943         ListBase *tracksbase =  NULL;
1944         int ok = TRUE, tracknr = 0, a, origin_set = FALSE;
1945         int sfra = context->sfra, efra = context->efra;
1946         float imat[4][4];
1947
1948         if (context->is_camera) {
1949                 tracksbase = &tracking->tracks;
1950                 reconstruction = &tracking->reconstruction;
1951         }
1952         else {
1953                 MovieTrackingObject *object = BKE_tracking_named_object(tracking, context->object_name);
1954
1955                 tracksbase = &object->tracks;
1956                 reconstruction = &object->reconstruction;
1957         }
1958
1959         unit_m4(imat);
1960
1961         track = tracksbase->first;
1962         while (track) {
1963                 double pos[3];
1964
1965                 if (libmv_reporojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
1966                         track->bundle_pos[0] = pos[0];
1967                         track->bundle_pos[1] = pos[1];
1968                         track->bundle_pos[2] = pos[2];
1969
1970                         track->flag |= TRACK_HAS_BUNDLE;
1971                         track->error = libmv_reporojectionErrorForTrack(libmv_reconstruction, tracknr);
1972                 }
1973                 else {
1974                         track->flag &= ~TRACK_HAS_BUNDLE;
1975                         ok = FALSE;
1976
1977                         printf("No bundle for track #%d '%s'\n", tracknr, track->name);
1978                 }
1979
1980                 track = track->next;
1981                 tracknr++;
1982         }
1983
1984         if (reconstruction->cameras)
1985                 MEM_freeN(reconstruction->cameras);
1986
1987         reconstruction->camnr = 0;
1988         reconstruction->cameras = NULL;
1989         reconstructed = MEM_callocN((efra - sfra + 1) * sizeof(MovieReconstructedCamera),
1990                                     "temp reconstructed camera");
1991
1992         for (a = sfra; a <= efra; a++) {
1993                 double matd[4][4];
1994
1995                 if (libmv_reporojectionCameraForImage(libmv_reconstruction, a, matd)) {
1996                         int i, j;
1997                         float mat[4][4];
1998                         float error = libmv_reporojectionErrorForImage(libmv_reconstruction, a);
1999
2000                         for (i = 0; i < 4; i++)
2001                                 for (j = 0; j < 4; j++)
2002                                         mat[i][j] = matd[i][j];
2003
2004                         if (!origin_set) {
2005                                 copy_m4_m4(imat, mat);
2006                                 invert_m4(imat);
2007                                 origin_set = TRUE;
2008                         }
2009
2010                         if (origin_set)
2011                                 mult_m4_m4m4(mat, imat, mat);
2012
2013                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
2014                         reconstructed[reconstruction->camnr].framenr = a;
2015                         reconstructed[reconstruction->camnr].error = error;
2016                         reconstruction->camnr++;
2017                 }
2018                 else {
2019                         ok = FALSE;
2020                         printf("No camera for frame %d\n", a);
2021                 }
2022         }
2023
2024         if (reconstruction->camnr) {
2025                 int size = reconstruction->camnr * sizeof(MovieReconstructedCamera);
2026                 reconstruction->cameras = MEM_callocN(size, "reconstructed camera");
2027                 memcpy(reconstruction->cameras, reconstructed, size);
2028         }
2029
2030         if (origin_set) {
2031                 track = tracksbase->first;
2032                 while (track) {
2033                         if (track->flag & TRACK_HAS_BUNDLE)
2034                                 mul_v3_m4v3(track->bundle_pos, imat, track->bundle_pos);
2035
2036                         track = track->next;
2037                 }
2038         }
2039
2040         MEM_freeN(reconstructed);
2041
2042         return ok;
2043 }
2044
2045 static int retrieve_libmv_reconstruct(MovieReconstructContext *context, MovieTracking *tracking)
2046 {
2047         /* take the intrinscis back from libmv */
2048         retrieve_libmv_reconstruct_intrinscis(context, tracking);
2049
2050         return retrieve_libmv_reconstruct_tracks(context, tracking);
2051 }
2052
2053 static int get_refine_intrinsics_flags(MovieTracking *tracking, MovieTrackingObject *object)
2054 {
2055         int refine = tracking->settings.refine_camera_intrinsics;
2056         int flags = 0;
2057
2058         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0)
2059                 return 0;
2060
2061         if (refine & REFINE_FOCAL_LENGTH)
2062                 flags |= LIBMV_REFINE_FOCAL_LENGTH;
2063
2064         if (refine & REFINE_PRINCIPAL_POINT)
2065                 flags |= LIBMV_REFINE_PRINCIPAL_POINT;
2066
2067         if (refine & REFINE_RADIAL_DISTORTION_K1)
2068                 flags |= REFINE_RADIAL_DISTORTION_K1;
2069
2070         if (refine & REFINE_RADIAL_DISTORTION_K2)
2071                 flags |= REFINE_RADIAL_DISTORTION_K2;
2072
2073         return flags;
2074 }
2075
2076 static int count_tracks_on_both_keyframes(MovieTracking *tracking, ListBase *tracksbase)
2077 {
2078         int tot = 0;
2079         int frame1 = tracking->settings.keyframe1, frame2 = tracking->settings.keyframe2;
2080         MovieTrackingTrack *track;
2081
2082         track = tracksbase->first;
2083         while (track) {
2084                 if (BKE_tracking_has_enabled_marker(track, frame1))
2085                         if (BKE_tracking_has_enabled_marker(track, frame2))
2086                                 tot++;
2087
2088                 track = track->next;
2089         }
2090
2091         return tot;
2092 }
2093 #endif
2094
2095 int BKE_tracking_can_reconstruct(MovieTracking *tracking, MovieTrackingObject *object, char *error_msg, int error_size)
2096 {
2097 #if WITH_LIBMV
2098         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2099
2100         if (tracking->settings.motion_flag & TRACKING_MOTION_MODAL) {
2101                 /* TODO: check for number of tracks? */
2102                 return TRUE;
2103         }
2104         else if (count_tracks_on_both_keyframes(tracking, tracksbase) < 8) {
2105                 BLI_strncpy(error_msg, "At least 8 common tracks on both of keyframes are needed for reconstruction",
2106                             error_size);
2107
2108                 return FALSE;
2109         }
2110
2111         return TRUE;
2112 #else
2113         BLI_strncpy(error_msg, "Blender is compiled without motion tracking library", error_size);
2114
2115         (void) tracking;
2116         (void) object;
2117
2118         return 0;
2119 #endif
2120 }
2121
2122 MovieReconstructContext *BKE_tracking_reconstruction_context_new(MovieTracking *tracking, MovieTrackingObject *object,
2123                                                                  int keyframe1, int keyframe2, int width, int height)
2124 {
2125         MovieReconstructContext *context = MEM_callocN(sizeof(MovieReconstructContext), "MovieReconstructContext data");
2126         MovieTrackingCamera *camera = &tracking->camera;
2127         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2128         float aspy = 1.0f / tracking->camera.pixel_aspect;
2129         int num_tracks = BLI_countlist(tracksbase);
2130         int sfra = INT_MAX, efra = INT_MIN;
2131         MovieTrackingTrack *track;
2132
2133         BLI_strncpy(context->object_name, object->name, sizeof(context->object_name));
2134         context->is_camera = object->flag & TRACKING_OBJECT_CAMERA;
2135         context->motion_flag = tracking->settings.motion_flag;
2136
2137         context->tracks_map = tracks_map_new(context->object_name, context->is_camera, num_tracks, 0);
2138
2139         track = tracksbase->first;
2140         while (track) {
2141                 int first = 0, last = track->markersnr - 1;
2142                 MovieTrackingMarker *first_marker = &track->markers[0];
2143                 MovieTrackingMarker *last_marker = &track->markers[track->markersnr - 1];
2144
2145                 /* find first not-disabled marker */
2146                 while (first <= track->markersnr - 1 && first_marker->flag & MARKER_DISABLED) {
2147                         first++;
2148                         first_marker++;
2149                 }
2150
2151                 /* find last not-disabled marker */
2152                 while (last >= 0 && last_marker->flag & MARKER_DISABLED) {
2153                         last--;
2154                         last_marker--;
2155                 }
2156
2157                 if (first < track->markersnr - 1)
2158                         sfra = MIN2(sfra, first_marker->framenr);
2159
2160                 if (last >= 0)
2161                         efra = MAX2(efra, last_marker->framenr);
2162
2163                 tracks_map_insert(context->tracks_map, track, NULL);
2164
2165                 track = track->next;
2166         }
2167
2168         context->sfra = sfra;
2169         context->efra = efra;
2170
2171 #ifdef WITH_LIBMV
2172         context->tracks = create_libmv_tracks(tracksbase, width, height * aspy);
2173         context->keyframe1 = keyframe1;
2174         context->keyframe2 = keyframe2;
2175         context->refine_flags = get_refine_intrinsics_flags(tracking, object);
2176 #else
2177         (void) width;
2178         (void) height;
2179         (void) keyframe1;
2180         (void) keyframe2;
2181 #endif
2182
2183         context->focal_length = camera->focal;
2184         context->principal_point[0] = camera->principal[0];
2185         context->principal_point[1] = camera->principal[1] * aspy;
2186
2187         context->k1 = camera->k1;
2188         context->k2 = camera->k2;
2189         context->k3 = camera->k3;
2190
2191         return context;
2192 }
2193
2194 void BKE_tracking_reconstruction_context_free(MovieReconstructContext *context)
2195 {
2196 #ifdef WITH_LIBMV
2197         if (context->reconstruction)
2198                 libmv_destroyReconstruction(context->reconstruction);
2199
2200         libmv_tracksDestroy(context->tracks);
2201 #endif
2202
2203         tracks_map_free(context->tracks_map, NULL);
2204
2205         MEM_freeN(context);
2206 }
2207
2208 #ifdef WITH_LIBMV
2209 static void solve_reconstruction_update_cb(void *customdata, double progress, const char *message)
2210 {
2211         ReconstructProgressData *progressdata = customdata;
2212
2213         if (progressdata->progress) {
2214                 *progressdata->progress = progress;
2215                 *progressdata->do_update = TRUE;
2216         }
2217
2218         BLI_snprintf(progressdata->stats_message, progressdata->message_size, "Solving camera | %s", message);
2219 }
2220 #endif
2221
2222 #if 0
2223 static int solve_reconstruction_testbreak_cb(void *customdata)
2224 {
2225         ReconstructProgressData *progressdata = customdata;
2226
2227         if (progressdata->stop && *progressdata->stop)
2228                 return TRUE;
2229
2230         return G.afbreek;
2231 }
2232 #endif
2233
2234 void BKE_tracking_solve_reconstruction(MovieReconstructContext *context, short *stop, short *do_update,
2235                                        float *progress, char *stats_message, int message_size)
2236 {
2237 #ifdef WITH_LIBMV
2238         float error;
2239
2240         ReconstructProgressData progressdata;
2241
2242         progressdata.stop = stop;
2243         progressdata.do_update = do_update;
2244         progressdata.progress = progress;
2245         progressdata.stats_message = stats_message;
2246         progressdata.message_size = message_size;
2247
2248         if (context->motion_flag & TRACKING_MOTION_MODAL) {
2249                 context->reconstruction = libmv_solveModal(context->tracks,
2250                                                            context->focal_length,
2251                                                            context->principal_point[0], context->principal_point[1],
2252                                                            context->k1, context->k2, context->k3,
2253                                                            solve_reconstruction_update_cb, &progressdata);
2254         }
2255         else {
2256                 context->reconstruction = libmv_solveReconstruction(context->tracks,
2257                                                                     context->keyframe1, context->keyframe2,
2258                                                                     context->refine_flags,
2259                                                                     context->focal_length,
2260                                                                     context->principal_point[0], context->principal_point[1],
2261                                                                     context->k1, context->k2, context->k3,
2262                                                                     solve_reconstruction_update_cb, &progressdata);
2263         }
2264
2265         error = libmv_reprojectionError(context->reconstruction);
2266
2267         context->reprojection_error = error;
2268 #else
2269         (void) context;
2270         (void) stop;
2271         (void) do_update;
2272         (void) progress;
2273         (void) stats_message;
2274         (void) message_size;
2275 #endif
2276 }
2277
2278 int BKE_tracking_finish_reconstruction(MovieReconstructContext *context, MovieTracking *tracking)
2279 {
2280         MovieTrackingReconstruction *reconstruction;
2281
2282         tracks_map_merge(context->tracks_map, tracking);
2283
2284         if (context->is_camera) {
2285                 reconstruction = &tracking->reconstruction;
2286         }
2287         else {
2288                 MovieTrackingObject *object;
2289
2290                 object = BKE_tracking_named_object(tracking, context->object_name);
2291                 reconstruction = &object->reconstruction;
2292         }
2293
2294         reconstruction->error = context->reprojection_error;
2295         reconstruction->flag |= TRACKING_RECONSTRUCTED;
2296
2297 #ifdef WITH_LIBMV
2298         if (!retrieve_libmv_reconstruct(context, tracking))
2299                 return FALSE;
2300 #endif
2301
2302         return TRUE;
2303 }
2304
2305 void BKE_track_unique_name(ListBase *tracksbase, MovieTrackingTrack *track)
2306 {
2307         BLI_uniquename(tracksbase, track, "Track", '.', offsetof(MovieTrackingTrack, name), sizeof(track->name));
2308 }
2309
2310 MovieTrackingTrack *BKE_tracking_named_track(MovieTracking *tracking, MovieTrackingObject *object, const char *name)
2311 {
2312         ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2313         MovieTrackingTrack *track = tracksbase->first;
2314
2315         while (track) {
2316                 if (!strcmp(track->name, name))
2317                         return track;
2318
2319                 track = track->next;
2320         }
2321
2322         return NULL;
2323 }
2324
2325 static int reconstruction_camera_index(MovieTrackingReconstruction *reconstruction, int framenr, int nearest)
2326 {
2327         MovieReconstructedCamera *cameras = reconstruction->cameras;
2328         int a = 0, d = 1;
2329
2330         if (!reconstruction->camnr)
2331                 return -1;
2332
2333         if (framenr < cameras[0].framenr) {
2334                 if (nearest)
2335                         return 0;
2336                 else
2337                         return -1;
2338         }
2339
2340         if (framenr > cameras[reconstruction->camnr - 1].framenr) {
2341                 if (nearest)
2342                         return reconstruction->camnr - 1;
2343                 else
2344                         return -1;
2345         }
2346
2347         if (reconstruction->last_camera < reconstruction->camnr)
2348                 a = reconstruction->last_camera;
2349
2350         if (cameras[a].framenr >= framenr)
2351                 d = -1;
2352
2353         while (a >= 0 && a < reconstruction->camnr) {
2354                 int cfra = cameras[a].framenr;
2355
2356                 /* check if needed framenr was "skipped" -- no data for requested frame */
2357
2358                 if (d > 0 && cfra > framenr) {
2359                         /* interpolate with previous position */
2360                         if (nearest)
2361                                 return a - 1;
2362                         else
2363                                 break;
2364                 }
2365
2366                 if (d < 0 && cfra < framenr) {
2367                         /* interpolate with next position */
2368                         if (nearest)
2369                                 return a;
2370                         else
2371                                 break;
2372                 }
2373
2374                 if (cfra == framenr) {
2375                         reconstruction->last_camera = a;
2376
2377                         return a;
2378                 }
2379
2380                 a += d;
2381         }
2382
2383         return -1;
2384 }
2385
2386 static void scale_reconstructed_camera(MovieTrackingObject *object, float mat[4][4])
2387 {
2388         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0) {
2389                 float smat[4][4];
2390
2391                 scale_m4_fl(smat, 1.0f / object->scale);
2392                 mult_m4_m4m4(mat, mat, smat);
2393         }
2394 }
2395
2396 MovieReconstructedCamera *BKE_tracking_get_reconstructed_camera(MovieTracking *tracking,
2397                                                                 MovieTrackingObject *object, int framenr)
2398 {
2399         MovieTrackingReconstruction *reconstruction;
2400         int a;
2401
2402         reconstruction = BKE_tracking_object_reconstruction(tracking, object);
2403         a = reconstruction_camera_index(reconstruction, framenr, FALSE);
2404
2405         if (a == -1)
2406                 return NULL;
2407
2408         return &reconstruction->cameras[a];
2409 }
2410
2411 void BKE_tracking_get_interpolated_camera(MovieTracking *tracking, MovieTrackingObject *object,
2412                                           int framenr, float mat[4][4])
2413 {
2414         MovieTrackingReconstruction *reconstruction;
2415         MovieReconstructedCamera *cameras;
2416         int a;
2417
2418         reconstruction = BKE_tracking_object_reconstruction(tracking, object);
2419         cameras = reconstruction->cameras;
2420         a = reconstruction_camera_index(reconstruction, framenr, 1);
2421
2422         if (a == -1) {
2423                 unit_m4(mat);
2424
2425                 return;
2426         }
2427
2428         if (cameras[a].framenr != framenr && a > 0 && a < reconstruction->camnr - 1) {
2429                 float t = ((float)framenr - cameras[a].framenr) / (cameras[a + 1].framenr - cameras[a].framenr);
2430
2431                 blend_m4_m4m4(mat, cameras[a].mat, cameras[a + 1].mat, t);
2432         }
2433         else {
2434                 copy_m4_m4(mat, cameras[a].mat);
2435         }
2436
2437         scale_reconstructed_camera(object, mat);
2438 }
2439
2440 void BKE_get_tracking_mat(Scene *scene, Object *ob, float mat[4][4])
2441 {
2442         if (!ob) {
2443                 if (scene->camera)
2444                         ob = scene->camera;
2445                 else
2446                         ob = BKE_scene_camera_find(scene);
2447         }
2448
2449         if (ob)
2450                 BKE_object_where_is_calc_mat4(scene, ob, mat);
2451         else
2452                 unit_m4(mat);
2453 }
2454
2455 void BKE_tracking_camera_shift(MovieTracking *tracking, int winx, int winy, float *shiftx, float *shifty)
2456 {
2457         /* indeed in both of cases it should be winx -- it's just how camera shift works for blender's camera */
2458         *shiftx = (0.5f * winx - tracking->camera.principal[0]) / winx;
2459         *shifty = (0.5f * winy - tracking->camera.principal[1]) / winx;
2460 }
2461
2462 void BKE_tracking_camera_to_blender(MovieTracking *tracking, Scene *scene, Camera *camera, int width, int height)
2463 {
2464         float focal = tracking->camera.focal;
2465
2466         camera->sensor_x = tracking->camera.sensor_width;
2467         camera->sensor_fit = CAMERA_SENSOR_FIT_AUTO;
2468         camera->lens = focal * camera->sensor_x / width;
2469
2470         scene->r.xsch = width * tracking->camera.pixel_aspect;
2471         scene->r.ysch = height;
2472
2473         scene->r.xasp = 1.0f;
2474         scene->r.yasp = 1.0f;
2475
2476         BKE_tracking_camera_shift(tracking, width, height, &camera->shiftx, &camera->shifty);
2477 }
2478
2479 void BKE_tracking_projection_matrix(MovieTracking *tracking, MovieTrackingObject *object,
2480                                     int framenr, int winx, int winy, float mat[4][4])
2481 {
2482         MovieReconstructedCamera *camera;
2483         float lens = tracking->camera.focal * tracking->camera.sensor_width / (float)winx;
2484         float viewfac, pixsize, left, right, bottom, top, clipsta, clipend;
2485         float winmat[4][4];
2486         float ycor =  1.0f / tracking->camera.pixel_aspect;
2487         float shiftx, shifty, winside = MAX2(winx, winy);
2488
2489         BKE_tracking_camera_shift(tracking, winx, winy, &shiftx, &shifty);
2490
2491         clipsta = 0.1f;
2492         clipend = 1000.0f;
2493
2494         if (winx >= winy)
2495                 viewfac = (lens * winx) / tracking->camera.sensor_width;
2496         else
2497                 viewfac = (ycor * lens * winy) / tracking->camera.sensor_width;
2498
2499         pixsize = clipsta / viewfac;
2500
2501         left = -0.5f * (float)winx + shiftx * winside;
2502         bottom = -0.5f * (ycor) * (float)winy + shifty * winside;
2503         right =  0.5f * (float)winx + shiftx * winside;
2504         top =  0.5f * (ycor) * (float)winy + shifty * winside;
2505
2506         left *= pixsize;
2507         right *= pixsize;
2508         bottom *= pixsize;
2509         top *= pixsize;
2510
2511         perspective_m4(winmat, left, right, bottom, top, clipsta, clipend);
2512
2513         camera = BKE_tracking_get_reconstructed_camera(tracking, object, framenr);
2514
2515         if (camera) {
2516                 float imat[4][4];
2517
2518                 invert_m4_m4(imat, camera->mat);
2519                 mult_m4_m4m4(mat, winmat, imat);
2520         }
2521         else copy_m4_m4(mat, winmat);
2522 }
2523
2524 ListBase *BKE_tracking_get_tracks(MovieTracking *tracking)
2525 {
2526         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
2527
2528         if (object && (object->flag & TRACKING_OBJECT_CAMERA) == 0) {
2529                 return &object->tracks;
2530         }
2531
2532         return &tracking->tracks;
2533 }
2534
2535 MovieTrackingTrack *BKE_tracking_active_track(MovieTracking *tracking)
2536 {
2537         ListBase *tracksbase;
2538
2539         if (!tracking->act_track)
2540                 return NULL;
2541
2542         tracksbase = BKE_tracking_get_tracks(tracking);
2543
2544         /* check that active track is in current tracks list */
2545         if (BLI_findindex(tracksbase, tracking->act_track) >= 0)
2546                 return tracking->act_track;
2547
2548         return NULL;
2549 }
2550
2551 MovieTrackingObject *BKE_tracking_active_object(MovieTracking *tracking)
2552 {
2553         return BLI_findlink(&tracking->objects, tracking->objectnr);
2554 }
2555
2556 MovieTrackingObject *BKE_tracking_get_camera_object(MovieTracking *tracking)
2557 {
2558         MovieTrackingObject *object = tracking->objects.first;
2559
2560         while (object) {
2561                 if (object->flag & TRACKING_OBJECT_CAMERA)
2562                         return object;
2563
2564                 object = object->next;
2565         }
2566
2567         return NULL;
2568 }
2569
2570 ListBase *BKE_tracking_object_tracks(MovieTracking *tracking, MovieTrackingObject *object)
2571 {
2572         if (object->flag & TRACKING_OBJECT_CAMERA) {
2573                 return &tracking->tracks;
2574         }
2575
2576         return &object->tracks;
2577 }
2578
2579 MovieTrackingReconstruction *BKE_tracking_object_reconstruction(MovieTracking *tracking, MovieTrackingObject *object)
2580 {
2581         if (object->flag & TRACKING_OBJECT_CAMERA) {
2582                 return &tracking->reconstruction;
2583         }
2584
2585         return &object->reconstruction;
2586 }
2587
2588 MovieTrackingReconstruction *BKE_tracking_get_reconstruction(MovieTracking *tracking)
2589 {
2590         MovieTrackingObject *object = BKE_tracking_active_object(tracking);
2591
2592         return BKE_tracking_object_reconstruction(tracking, object);
2593 }
2594
2595 void BKE_tracking_apply_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
2596 {
2597         MovieTrackingCamera *camera = &tracking->camera;
2598
2599 #ifdef WITH_LIBMV
2600         double x, y;
2601         float aspy = 1.0f / tracking->camera.pixel_aspect;
2602
2603         /* normalize coords */
2604         x = (co[0] - camera->principal[0]) / camera->focal;
2605         y = (co[1] - camera->principal[1] * aspy) / camera->focal;
2606
2607         libmv_applyCameraIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
2608                                     camera->k1, camera->k2, camera->k3, x, y, &x, &y);
2609
2610         /* result is in image coords already */
2611         nco[0] = x;
2612         nco[1] = y;
2613 #else
2614         (void) camera;
2615         (void) co;
2616         (void) nco;
2617 #endif
2618 }
2619
2620 void BKE_tracking_invert_intrinsics(MovieTracking *tracking, float co[2], float nco[2])
2621 {
2622         MovieTrackingCamera *camera = &tracking->camera;
2623
2624 #ifdef WITH_LIBMV
2625         double x = co[0], y = co[1];
2626         float aspy = 1.0f / tracking->camera.pixel_aspect;
2627
2628         libmv_InvertIntrinsics(camera->focal, camera->principal[0], camera->principal[1] * aspy,
2629                                camera->k1, camera->k2, camera->k3, x, y, &x, &y);
2630
2631         nco[0] = x * camera->focal + camera->principal[0];
2632         nco[1] = y * camera->focal + camera->principal[1] * aspy;
2633 #else
2634         (void) camera;
2635         (void) co;
2636         (void) nco;
2637 #endif
2638 }
2639
2640 #ifdef WITH_LIBMV
2641 static int point_in_stroke(bGPDstroke *stroke, float x, float y)
2642 {
2643         int i, prev;
2644         int count = 0;
2645         bGPDspoint *points = stroke->points;
2646
2647         prev = stroke->totpoints - 1;
2648
2649         for (i = 0; i < stroke->totpoints; i++) {
2650                 if ((points[i].y < y && points[prev].y >= y) || (points[prev].y < y && points[i].y >= y)) {
2651                         float fac = (y - points[i].y) / (points[prev].y - points[i].y);
2652
2653                         if (points[i].x + fac * (points[prev].x - points[i].x) < x)
2654                                 count++;
2655                 }
2656
2657                 prev = i;
2658         }
2659
2660         return count % 2;
2661 }
2662
2663 static int point_in_layer(bGPDlayer *layer, float x, float y)
2664 {
2665         bGPDframe *frame = layer->frames.first;
2666
2667         while (frame) {
2668                 bGPDstroke *stroke = frame->strokes.first;
2669
2670                 while (stroke) {
2671                         if (point_in_stroke(stroke, x, y))
2672                                 return TRUE;
2673
2674                         stroke = stroke->next;
2675                 }
2676                 frame = frame->next;
2677         }
2678
2679         return FALSE;
2680 }
2681
2682 static void retrieve_libmv_features(MovieTracking *tracking, ListBase *tracksbase,
2683                                     struct libmv_Features *features, int framenr, int width, int height,
2684                                     bGPDlayer *layer, int place_outside_layer)
2685 {
2686         int a;
2687
2688         a = libmv_countFeatures(features);
2689         while (a--) {
2690                 MovieTrackingTrack *track;
2691                 double x, y, size, score;
2692                 int ok = TRUE;
2693                 float xu, yu;
2694
2695                 libmv_getFeature(features, a, &x, &y, &score, &size);
2696
2697                 xu = x / width;
2698                 yu = y / height;
2699
2700                 if (layer)
2701                         ok = point_in_layer(layer, xu, yu) != place_outside_layer;
2702
2703                 if (ok) {
2704                         track = BKE_tracking_add_track(tracking, tracksbase, xu, yu, framenr, width, height);
2705                         track->flag |= SELECT;
2706                         track->pat_flag |= SELECT;
2707                         track->search_flag |= SELECT;
2708                 }
2709         }
2710 }
2711 #endif
2712
2713 void BKE_tracking_detect_fast(MovieTracking *tracking, ListBase *tracksbase, ImBuf *ibuf,
2714                               int framenr, int margin, int min_trackness, int min_distance, bGPDlayer *layer,
2715                               int place_outside_layer)
2716 {
2717 #ifdef WITH_LIBMV
2718         struct libmv_Features *features;
2719         unsigned char *pixels = get_ucharbuf(ibuf);
2720
2721         features = libmv_detectFeaturesFAST(pixels, ibuf->x, ibuf->y, ibuf->x,
2722                                             margin, min_trackness, min_distance);
2723
2724         MEM_freeN(pixels);
2725
2726         retrieve_libmv_features(tracking, tracksbase, features, framenr,
2727                                 ibuf->x, ibuf->y, layer, place_outside_layer);
2728
2729         libmv_destroyFeatures(features);
2730 #else
2731         (void) tracking;
2732         (void) tracksbase;
2733         (void) ibuf;
2734         (void) framenr;
2735         (void) margin;
2736         (void) min_trackness;
2737         (void) min_distance;
2738         (void) layer;
2739         (void) place_outside_layer;
2740 #endif
2741 }
2742
2743 MovieTrackingTrack *BKE_tracking_indexed_track(MovieTracking *tracking, int tracknr, ListBase **tracksbase_r)
2744 {
2745         MovieTrackingObject *object;
2746         int cur = 1;
2747
2748         object = tracking->objects.first;
2749         while (object) {
2750                 ListBase *tracksbase = BKE_tracking_object_tracks(tracking, object);
2751                 MovieTrackingTrack *track = tracksbase->first;
2752
2753                 while (track) {
2754                         if (track->flag & TRACK_HAS_BUNDLE) {
2755                                 if (cur == tracknr) {
2756                                         *tracksbase_r = tracksbase;
2757                                         return track;
2758                                 }
2759
2760                                 cur++;
2761                         }
2762
2763                         track = track->next;
2764                 }
2765
2766                 object = object->next;
2767         }
2768
2769         *tracksbase_r = NULL;
2770
2771         return NULL;
2772 }
2773
2774 static int stabilization_median_point(MovieTracking *tracking, int framenr, float median[2])
2775 {
2776         int ok = FALSE;
2777         float min[2], max[2];
2778         MovieTrackingTrack *track;
2779
2780         INIT_MINMAX2(min, max);
2781
2782         track = tracking->tracks.first;
2783         while (track) {
2784                 if (track->flag & TRACK_USE_2D_STAB) {
2785                         MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenr);
2786
2787                         DO_MINMAX2(marker->pos, min, max);
2788
2789                         ok = TRUE;
2790                 }
2791
2792                 track = track->next;
2793         }
2794
2795         median[0] = (max[0] + min[0]) / 2.0f;
2796         median[1] = (max[1] + min[1]) / 2.0f;
2797
2798         return ok;
2799 }
2800
2801 static void calculate_stabdata(MovieTracking *tracking, int framenr, float width, float height,
2802                                float firstmedian[2], float median[2], float loc[2], float *scale, float *angle)
2803 {
2804         MovieTrackingStabilization *stab = &tracking->stabilization;
2805
2806         *scale = (stab->scale - 1.0f) * stab->scaleinf + 1.0f;
2807         *angle = 0.0f;
2808
2809         loc[0] = (firstmedian[0] - median[0]) * width * (*scale);
2810         loc[1] = (firstmedian[1] - median[1]) * height * (*scale);
2811
2812         mul_v2_fl(loc, stab->locinf);
2813
2814         if ((stab->flag & TRACKING_STABILIZE_ROTATION) && stab->rot_track && stab->rotinf) {
2815                 MovieTrackingMarker *marker;
2816                 float a[2], b[2];
2817                 float x0 = (float)width / 2.0f, y0 = (float)height / 2.0f;
2818                 float x = median[0] * width, y = median[1] * height;
2819
2820                 marker = BKE_tracking_get_marker(stab->rot_track, 1);
2821                 sub_v2_v2v2(a, marker->pos, firstmedian);
2822                 a[0] *= width;
2823                 a[1] *= height;
2824
2825                 marker = BKE_tracking_get_marker(stab->rot_track, framenr);
2826                 sub_v2_v2v2(b, marker->pos, median);
2827                 b[0] *= width;
2828                 b[1] *= height;
2829
2830                 *angle = -atan2(a[0] * b[1] - a[1] * b[0], a[0] * b[0] + a[1] * b[1]);
2831                 *angle *= stab->rotinf;
2832
2833                 /* convert to rotation around image center */
2834                 loc[0] -= (x0 + (x - x0) * cosf(*angle) - (y - y0) * sinf(*angle) - x) * (*scale);
2835                 loc[1] -= (y0 + (x - x0) * sinf(*angle) + (y - y0) * cosf(*angle) - y) * (*scale);
2836         }
2837 }
2838
2839 static float stabilization_auto_scale_factor(MovieTracking *tracking, int width, int height)
2840 {
2841         float firstmedian[2];
2842         MovieTrackingStabilization *stab = &tracking->stabilization;
2843         float aspect = tracking->camera.pixel_aspect;
2844
2845         if (stab->ok)
2846                 return stab->scale;
2847
2848         if (stabilization_median_point(tracking, 1, firstmedian)) {
2849                 int sfra = INT_MAX, efra = INT_MIN, cfra;
2850                 float scale = 1.0f;
2851                 MovieTrackingTrack *track;
2852
2853                 stab->scale = 1.0f;
2854
2855                 track = tracking->tracks.first;
2856                 while (track) {
2857                         if (track->flag & TRACK_USE_2D_STAB ||
2858                             ((stab->flag & TRACKING_STABILIZE_ROTATION) && track == stab->rot_track))
2859                         {
2860                                 sfra = MIN2(sfra, track->markers[0].framenr);
2861                                 efra = MAX2(efra, track->markers[track->markersnr - 1].framenr);
2862                         }
2863
2864                         track = track->next;
2865                 }
2866
2867                 for (cfra = sfra; cfra <= efra; cfra++) {
2868                         float median[2];
2869                         float loc[2], angle, tmp_scale;
2870                         int i;
2871                         float mat[4][4];
2872                         float points[4][2] = {{0.0f, 0.0f}, {0.0f, height}, {width, height}, {width, 0.0f}};
2873                         float si, co;
2874
2875                         stabilization_median_point(tracking, cfra, median);
2876
2877                         calculate_stabdata(tracking, cfra, width, height, firstmedian, median, loc, &tmp_scale, &angle);
2878
2879                         BKE_tracking_stabdata_to_mat4(width, height, aspect, loc, 1.0f, angle, mat);
2880
2881                         si = sin(angle);
2882                         co = cos(angle);
2883
2884                         for (i = 0; i < 4; i++) {
2885                                 int j;
2886                                 float a[3] = {0.0f, 0.0f, 0.0f}, b[3] = {0.0f, 0.0f, 0.0f};
2887
2888                                 copy_v3_v3(a, points[i]);
2889                                 copy_v3_v3(b, points[(i + 1) % 4]);
2890
2891                                 mul_m4_v3(mat, a);
2892                                 mul_m4_v3(mat, b);
2893
2894                                 for (j = 0; j < 4; j++) {
2895                                         float point[3] = {points[j][0], points[j][1], 0.0f};
2896                                         float v1[3], v2[3];
2897
2898                                         sub_v3_v3v3(v1, b, a);
2899                                         sub_v3_v3v3(v2, point, a);
2900
2901                                         if (cross_v2v2(v1, v2) >= 0.0f) {
2902                                                 const float rotDx[4][2] = {{1.0f, 0.0f}, {0.0f, -1.0f}, {-1.0f, 0.0f}, {0.0f, 1.0f}};
2903                                                 const float rotDy[4][2] = {{0.0f, 1.0f}, {1.0f, 0.0f}, {0.0f, -1.0f}, {-1.0f, 0.0f}};
2904
2905                                                 float dx = loc[0] * rotDx[j][0] + loc[1] * rotDx[j][1],
2906                                                       dy = loc[0] * rotDy[j][0] + loc[1] * rotDy[j][1];
2907
2908                                                 float w, h, E, F, G, H, I, J, K, S;
2909
2910                                                 if (j % 2) {
2911                                                         w = (float)height / 2.0f;
2912                                                         h = (float)width / 2.0f;
2913                                                 }
2914                                                 else {
2915                                                         w = (float)width / 2.0f;
2916                                                         h = (float)height / 2.0f;
2917                                                 }
2918
2919                                                 E = -w * co + h * si;
2920                                                 F = -h * co - w * si;
2921
2922                                                 if ((i % 2) == (j % 2)) {
2923                                                         G = -w * co - h * si;
2924                                                         H = h * co - w * si;
2925                                                 }
2926                                                 else {
2927                                                         G = w * co + h * si;
2928                                                         H = -h * co + w * si;
2929                                                 }
2930
2931                                                 I = F - H;
2932                                                 J = G - E;
2933                                                 K = G * F - E * H;
2934
2935                                                 S = (-w * I - h * J) / (dx * I + dy * J + K);
2936
2937                                                 scale = MAX2(scale, S);
2938                                         }
2939                                 }
2940                         }
2941                 }
2942
2943                 stab->scale = scale;
2944
2945                 if (stab->maxscale > 0.0f)
2946                         stab->scale = MIN2(stab->scale, stab->maxscale);
2947         }
2948         else {
2949                 stab->scale = 1.0f;
2950         }
2951
2952         stab->ok = TRUE;
2953
2954         return stab->scale;
2955 }
2956
2957 static ImBuf *stabilize_alloc_ibuf(ImBuf *cacheibuf, ImBuf *srcibuf, int fill)
2958 {
2959         int flags;
2960
2961         if (cacheibuf && (cacheibuf->x != srcibuf->x || cacheibuf->y != srcibuf->y)) {
2962                 IMB_freeImBuf(cacheibuf);
2963                 cacheibuf = NULL;
2964         }
2965
2966         flags = IB_rect;
2967
2968         if (srcibuf->rect_float)
2969                 flags |= IB_rectfloat;
2970
2971         if (cacheibuf) {
2972                 if (fill) {
2973                         float col[4] = {0.0f, 0.0f, 0.0f, 0.0f};
2974
2975                         IMB_rectfill(cacheibuf, col);
2976                 }
2977         }
2978         else {
2979                 cacheibuf = IMB_allocImBuf(srcibuf->x, srcibuf->y, srcibuf->planes, flags);
2980                 cacheibuf->profile = srcibuf->profile;
2981         }
2982
2983         return cacheibuf;
2984 }
2985
2986 void BKE_tracking_stabilization_data(MovieTracking *tracking, int framenr, int width, int height,
2987                                      float loc[2], float *scale, float *angle)
2988 {
2989         float firstmedian[2], median[2];
2990         MovieTrackingStabilization *stab = &tracking->stabilization;
2991
2992         if ((stab->flag & TRACKING_2D_STABILIZATION) == 0) {
2993                 zero_v2(loc);
2994                 *scale = 1.0f;
2995                 *angle = 0.0f;
2996
2997                 return;
2998         }
2999
3000         if (stabilization_median_point(tracking, 1, firstmedian)) {
3001                 stabilization_median_point(tracking, framenr, median);
3002
3003                 if ((stab->flag & TRACKING_AUTOSCALE) == 0)
3004                         stab->scale = 1.0f;
3005
3006                 if (!stab->ok) {
3007                         if (stab->flag & TRACKING_AUTOSCALE)
3008                                 stabilization_auto_scale_factor(tracking, width, height);
3009
3010                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
3011
3012                         stab->ok = TRUE;
3013                 }
3014                 else {
3015                         calculate_stabdata(tracking, framenr, width, height, firstmedian, median, loc, scale, angle);
3016                 }
3017         }
3018         else {
3019                 zero_v2(loc);
3020                 *scale = 1.0f;
3021                 *angle = 0.0f;
3022         }
3023 }
3024
3025 ImBuf *BKE_tracking_stabilize(MovieTracking *tracking, int framenr, ImBuf *ibuf,
3026                               float loc[2], float *scale, float *angle)
3027 {
3028         float tloc[2], tscale, tangle;
3029         MovieTrackingStabilization *stab = &tracking->stabilization;
3030         ImBuf *tmpibuf;
3031         float width = ibuf->x, height = ibuf->y;
3032         float aspect = tracking->camera.pixel_aspect;
3033
3034         if (loc)
3035                 copy_v2_v2(tloc, loc);
3036
3037         if (scale)
3038                 tscale = *scale;
3039
3040         if ((stab->flag & TRACKING_2D_STABILIZATION) == 0) {
3041                 if (loc)
3042                         zero_v2(loc);
3043
3044                 if (scale)
3045                         *scale = 1.0f;
3046
3047                 return ibuf;
3048         }
3049
3050         BKE_tracking_stabilization_data(tracking, framenr, width, height, tloc, &tscale, &tangle);
3051
3052         tmpibuf = stabilize_alloc_ibuf(NULL, ibuf, TRUE);
3053
3054         /* scale would be handled by matrix transformation when angle is non-zero */
3055         if (tscale != 1.0f && tangle == 0.0f) {
3056                 ImBuf *scaleibuf;
3057
3058                 stabilization_auto_scale_factor(tracking, width, height);
3059
3060                 scaleibuf = stabilize_alloc_ibuf(stab->scaleibuf, ibuf, 0);
3061                 stab->scaleibuf = scaleibuf;
3062
3063                 IMB_rectcpy(scaleibuf, ibuf, 0, 0, 0, 0, ibuf->x, ibuf->y);
3064                 IMB_scalefastImBuf(scaleibuf, ibuf->x * tscale, ibuf->y * tscale);
3065
3066                 ibuf = scaleibuf;
3067         }
3068
3069         if (tangle == 0.0f) {
3070                 /* if angle is zero, then it's much faster to use rect copy
3071                  * but could be issues with subpixel precisions
3072                  */
3073                 IMB_rectcpy(tmpibuf, ibuf,
3074                             tloc[0] - (tscale - 1.0f) * width / 2.0f,
3075                             tloc[1] - (tscale - 1.0f) * height / 2.0f,
3076                             0, 0, ibuf->x, ibuf->y);
3077         }
3078         else {
3079                 float mat[4][4];
3080                 int i, j, filter = tracking->stabilization.filter;
3081                 void (*interpolation)(struct ImBuf *, struct ImBuf *, float, float, int, int) = NULL;
3082
3083                 BKE_tracking_stabdata_to_mat4(ibuf->x, ibuf->y, aspect, tloc, tscale, tangle, mat);
3084                 invert_m4(mat);
3085
3086                 if (filter == TRACKING_FILTER_NEAREAST)
3087                         interpolation = neareast_interpolation;
3088                 else if (filter == TRACKING_FILTER_BILINEAR)
3089                         interpolation = bilinear_interpolation;
3090                 else if (filter == TRACKING_FILTER_BICUBIC)
3091                         interpolation = bicubic_interpolation;
3092                 else
3093                         /* fallback to default interpolation method */
3094                         interpolation = neareast_interpolation;
3095
3096                 for (j = 0; j < tmpibuf->y; j++) {
3097                         for (i = 0; i < tmpibuf->x; i++) {
3098                                 float vec[3] = {i, j, 0};
3099
3100                                 mul_v3_m4v3(vec, mat, vec);
3101
3102                                 interpolation(ibuf, tmpibuf, vec[0], vec[1], i, j);
3103                         }
3104                 }
3105         }
3106
3107         tmpibuf->userflags |= IB_MIPMAP_INVALID;
3108
3109         if (tmpibuf->rect_float)
3110                 tmpibuf->userflags |= IB_RECT_INVALID;
3111
3112         if (loc)
3113                 copy_v2_v2(loc, tloc);
3114
3115         if (scale)
3116                 *scale = tscale;
3117
3118         if (angle)
3119                 *angle = tangle;
3120
3121         return tmpibuf;
3122 }
3123
3124 void BKE_tracking_stabdata_to_mat4(int width, int height, float aspect,
3125                                    float loc[2], float scale, float angle, float mat[4][4])
3126 {
3127         float lmat[4][4], rmat[4][4], smat[4][4], cmat[4][4], icmat[4][4], amat[4][4], iamat[4][4];
3128         float svec[3] = {scale, scale, scale};
3129
3130         unit_m4(rmat);
3131         unit_m4(lmat);
3132         unit_m4(smat);
3133         unit_m4(cmat);
3134         unit_m4(amat);
3135
3136         /* aspect ratio correction matrix */
3137         amat[0][0] = 1.0f / aspect;
3138         invert_m4_m4(iamat, amat);
3139
3140         /* image center as rotation center */
3141         cmat[3][0] = (float)width / 2.0f;
3142         cmat[3][1] = (float)height / 2.0f;
3143         invert_m4_m4(icmat, cmat);
3144
3145         size_to_mat4(smat, svec);       /* scale matrix */
3146         add_v2_v2(lmat[3], loc);        /* translation matrix */
3147         rotate_m4(rmat, 'Z', angle);    /* rotation matrix */
3148
3149         /* compose transformation matrix */
3150         mul_serie_m4(mat, lmat, cmat, amat, rmat, iamat, smat, icmat, NULL);
3151 }
3152
3153 MovieDistortion *BKE_tracking_distortion_create(void)
3154 {
3155         MovieDistortion *distortion;
3156
3157         distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
3158
3159         return distortion;
3160 }
3161
3162 MovieDistortion *BKE_tracking_distortion_copy(MovieDistortion *distortion)
3163 {
3164         MovieDistortion *new_distortion;
3165
3166         new_distortion = MEM_callocN(sizeof(MovieDistortion), "BKE_tracking_distortion_create");
3167
3168 #ifdef WITH_LIBMV
3169         new_distortion->intrinsics = libmv_CameraIntrinsicsCopy(distortion->intrinsics);
3170 #else
3171         (void) distortion;
3172 #endif
3173
3174         return new_distortion;
3175 }
3176
3177 void BKE_tracking_distortion_update(MovieDistortion *distortion, MovieTracking *tracking, int width, int height)
3178 {
3179         MovieTrackingCamera *camera = &tracking->camera;
3180         float aspy = 1.0f / tracking->camera.pixel_aspect;
3181
3182 #ifdef WITH_LIBMV
3183         if (!distortion->intrinsics) {
3184                 distortion->intrinsics = libmv_CameraIntrinsicsNew(camera->focal,
3185                                                                    camera->principal[0], camera->principal[1] * aspy,
3186                                                                    camera->k1, camera->k2, camera->k3, width, height * aspy);
3187         }
3188         else {
3189                 libmv_CameraIntrinsicsUpdate(distortion->intrinsics, camera->focal,
3190                                              camera->principal[0], camera->principal[1] * aspy,
3191                                              camera->k1, camera->k2, camera->k3, width, height * aspy);
3192         }
3193 #else
3194         (void) distortion;
3195         (void) width;
3196         (void) height;
3197         (void) camera;
3198         (void) aspy;
3199 #endif
3200 }
3201
3202 ImBuf *BKE_tracking_distortion_exec(MovieDistortion *distortion, MovieTracking *tracking,
3203                                     ImBuf *ibuf, int width, int height, float overscan, int undistort)
3204 {
3205         ImBuf *resibuf;
3206
3207         BKE_tracking_distortion_update(distortion, tracking, width, height);
3208
3209         resibuf = IMB_dupImBuf(ibuf);
3210
3211         if (ibuf->rect_float) {
3212 #ifdef WITH_LIBMV
3213                 if (undistort) {
3214                         libmv_CameraIntrinsicsUndistortFloat(distortion->intrinsics,
3215                                                              ibuf->rect_float, resibuf->rect_float,
3216                                                              ibuf->x, ibuf->y, overscan, ibuf->channels);
3217                 }
3218                 else {
3219                         libmv_CameraIntrinsicsDistortFloat(distortion->intrinsics,
3220                                                            ibuf->rect_float, resibuf->rect_float,
3221                                                            ibuf->x, ibuf->y, overscan, ibuf->channels);
3222                 }
3223 #endif
3224
3225                 resibuf->userflags |= IB_RECT_INVALID;
3226         }
3227         else {
3228 #ifdef WITH_LIBMV
3229                 if (undistort) {
3230                         libmv_CameraIntrinsicsUndistortByte(distortion->intrinsics,
3231                                                             (unsigned char *)ibuf->rect, (unsigned char *)resibuf->rect,
3232                                                             ibuf->x, ibuf->y, overscan, ibuf->channels);
3233                 }
3234                 else {
3235                         libmv_CameraIntrinsicsDistortByte(distortion->intrinsics,
3236                                                           (unsigned char *)ibuf->rect, (unsigned char *)resibuf->rect,
3237                                                           ibuf->x, ibuf->y, overscan, ibuf->channels);
3238                 }
3239 #endif
3240         }
3241
3242 #ifndef WITH_LIBMV
3243         (void) overscan;
3244         (void) undistort;
3245 #endif