Split tracking.c into several files
[blender.git] / source / blender / blenkernel / intern / tracking_solver.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_solver.c
29  *  \ingroup bke
30  *
31  * This file contains blender-side implementation of camera solver.
32  */
33
34 #include <limits.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_anim_types.h"
39 #include "DNA_movieclip_types.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_math.h"
43 #include "BLI_listbase.h"
44 #include "BLI_string.h"
45
46 #include "BLF_translation.h"
47
48 #include "BKE_fcurve.h"
49 #include "BKE_tracking.h"
50 #include "BKE_movieclip.h"
51
52 #include "RNA_access.h"
53
54 #include "libmv-capi.h"
55 #include "tracking_private.h"
56
57 typedef struct MovieReconstructContext {
58         struct libmv_Tracks *tracks;
59         bool select_keyframes;
60         int keyframe1, keyframe2;
61         int refine_flags;
62
63         struct libmv_Reconstruction *reconstruction;
64
65         char object_name[MAX_NAME];
66         bool is_camera;
67         short motion_flag;
68
69         float focal_length;
70         float principal_point[2];
71         float k1, k2, k3;
72
73         int width, height;
74
75         float reprojection_error;
76
77         TracksMap *tracks_map;
78
79         int sfra, efra;
80 } MovieReconstructContext;
81
82 typedef struct ReconstructProgressData {
83         short *stop;
84         short *do_update;
85         float *progress;
86         char *stats_message;
87         int message_size;
88 } ReconstructProgressData;
89
90 /* Create new libmv Tracks structure from blender's tracks list. */
91 static struct libmv_Tracks *libmv_tracks_new(MovieClip *clip, ListBase *tracksbase, int width, int height)
92 {
93         int tracknr = 0;
94         MovieTrackingTrack *track;
95         struct libmv_Tracks *tracks = libmv_tracksNew();
96
97         track = tracksbase->first;
98         while (track) {
99                 FCurve *weight_fcurve;
100                 int a = 0;
101
102                 weight_fcurve = id_data_find_fcurve(&clip->id, track, &RNA_MovieTrackingTrack,
103                                                     "weight", 0, NULL);
104
105                 for (a = 0; a < track->markersnr; a++) {
106                         MovieTrackingMarker *marker = &track->markers[a];
107
108                         if ((marker->flag & MARKER_DISABLED) == 0) {
109                                 float weight = track->weight;
110
111                                 if (weight_fcurve) {
112                                         int scene_framenr =
113                                                 BKE_movieclip_remap_clip_to_scene_frame(clip, marker->framenr);
114                                         weight = evaluate_fcurve(weight_fcurve, scene_framenr);
115                                 }
116
117                                 libmv_tracksInsert(tracks, marker->framenr, tracknr,
118                                                    (marker->pos[0] + track->offset[0]) * width,
119                                                    (marker->pos[1] + track->offset[1]) * height,
120                                                    weight);
121                         }
122                 }
123
124                 track = track->next;
125                 tracknr++;
126         }
127
128         return tracks;
129 }
130
131 /* Retrieve refined camera intrinsics from libmv to blender. */
132 static void reconstruct_retrieve_libmv_intrinsics(MovieReconstructContext *context, MovieTracking *tracking)
133 {
134         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
135         struct libmv_CameraIntrinsics *libmv_intrinsics = libmv_reconstructionExtractIntrinsics(libmv_reconstruction);
136
137         float aspy = 1.0f / tracking->camera.pixel_aspect;
138
139         double focal_length, principal_x, principal_y, k1, k2, k3;
140         int width, height;
141
142         libmv_cameraIntrinsicsExtract(libmv_intrinsics, &focal_length, &principal_x, &principal_y,
143                                       &k1, &k2, &k3, &width, &height);
144
145         tracking->camera.focal = focal_length;
146
147         tracking->camera.principal[0] = principal_x;
148         tracking->camera.principal[1] = principal_y / (double)aspy;
149
150         tracking->camera.k1 = k1;
151         tracking->camera.k2 = k2;
152         tracking->camera.k3 = k3;
153 }
154
155 /* Retrieve reconstructed tracks from libmv to blender.
156  * Actually, this also copies reconstructed cameras
157  * from libmv to movie clip datablock.
158  */
159 static bool reconstruct_retrieve_libmv_tracks(MovieReconstructContext *context, MovieTracking *tracking)
160 {
161         struct libmv_Reconstruction *libmv_reconstruction = context->reconstruction;
162         MovieTrackingReconstruction *reconstruction = NULL;
163         MovieReconstructedCamera *reconstructed;
164         MovieTrackingTrack *track;
165         ListBase *tracksbase =  NULL;
166         int tracknr = 0, a;
167         bool ok = true;
168         bool origin_set = false;
169         int sfra = context->sfra, efra = context->efra;
170         float imat[4][4];
171
172         if (context->is_camera) {
173                 tracksbase = &tracking->tracks;
174                 reconstruction = &tracking->reconstruction;
175         }
176         else {
177                 MovieTrackingObject *object = BKE_tracking_object_get_named(tracking, context->object_name);
178
179                 tracksbase = &object->tracks;
180                 reconstruction = &object->reconstruction;
181         }
182
183         unit_m4(imat);
184
185         track = tracksbase->first;
186         while (track) {
187                 double pos[3];
188
189                 if (libmv_reprojectionPointForTrack(libmv_reconstruction, tracknr, pos)) {
190                         track->bundle_pos[0] = pos[0];
191                         track->bundle_pos[1] = pos[1];
192                         track->bundle_pos[2] = pos[2];
193
194                         track->flag |= TRACK_HAS_BUNDLE;
195                         track->error = libmv_reprojectionErrorForTrack(libmv_reconstruction, tracknr);
196                 }
197                 else {
198                         track->flag &= ~TRACK_HAS_BUNDLE;
199                         ok = false;
200
201                         printf("Unable to reconstruct position for track #%d '%s'\n", tracknr, track->name);
202                 }
203
204                 track = track->next;
205                 tracknr++;
206         }
207
208         if (reconstruction->cameras)
209                 MEM_freeN(reconstruction->cameras);
210
211         reconstruction->camnr = 0;
212         reconstruction->cameras = NULL;
213         reconstructed = MEM_callocN((efra - sfra + 1) * sizeof(MovieReconstructedCamera),
214                                     "temp reconstructed camera");
215
216         for (a = sfra; a <= efra; a++) {
217                 double matd[4][4];
218
219                 if (libmv_reprojectionCameraForImage(libmv_reconstruction, a, matd)) {
220                         int i, j;
221                         float mat[4][4];
222                         float error = libmv_reprojectionErrorForImage(libmv_reconstruction, a);
223
224                         for (i = 0; i < 4; i++) {
225                                 for (j = 0; j < 4; j++)
226                                         mat[i][j] = matd[i][j];
227                         }
228
229                         /* Ensure first camera has got zero rotation and transform.
230                          * This is essential for object tracking to work -- this way
231                          * we'll always know object and environment are properly
232                          * oriented.
233                          *
234                          * There's one weak part tho, which is requirement object
235                          * motion starts at the same frame as camera motion does,
236                          * otherwise that;' be a russian roulette whether object is
237                          * aligned correct or not.
238                          */
239                         if (!origin_set) {
240                                 invert_m4_m4(imat, mat);
241                                 unit_m4(mat);
242                                 origin_set = true;
243                         }
244                         else {
245                                 mul_m4_m4m4(mat, imat, mat);
246                         }
247
248                         copy_m4_m4(reconstructed[reconstruction->camnr].mat, mat);
249                         reconstructed[reconstruction->camnr].framenr = a;
250                         reconstructed[reconstruction->camnr].error = error;
251                         reconstruction->camnr++;
252                 }
253                 else {
254                         ok = false;
255                         printf("No camera for frame %d\n", a);
256                 }
257         }
258
259         if (reconstruction->camnr) {
260                 int size = reconstruction->camnr * sizeof(MovieReconstructedCamera);
261                 reconstruction->cameras = MEM_callocN(size, "reconstructed camera");
262                 memcpy(reconstruction->cameras, reconstructed, size);
263         }
264
265         if (origin_set) {
266                 track = tracksbase->first;
267                 while (track) {
268                         if (track->flag & TRACK_HAS_BUNDLE)
269                                 mul_v3_m4v3(track->bundle_pos, imat, track->bundle_pos);
270
271                         track = track->next;
272                 }
273         }
274
275         MEM_freeN(reconstructed);
276
277         return ok;
278 }
279
280 /* Retrieve all the libmv data from context to blender's side data blocks. */
281 static int reconstruct_retrieve_libmv(MovieReconstructContext *context, MovieTracking *tracking)
282 {
283         /* take the intrinsics back from libmv */
284         reconstruct_retrieve_libmv_intrinsics(context, tracking);
285
286         return reconstruct_retrieve_libmv_tracks(context, tracking);
287 }
288
289 /* Convert blender's refinement flags to libmv's. */
290 static int reconstruct_refine_intrinsics_get_flags(MovieTracking *tracking, MovieTrackingObject *object)
291 {
292         int refine = tracking->settings.refine_camera_intrinsics;
293         int flags = 0;
294
295         if ((object->flag & TRACKING_OBJECT_CAMERA) == 0)
296                 return 0;
297
298         if (refine & REFINE_FOCAL_LENGTH)
299                 flags |= LIBMV_REFINE_FOCAL_LENGTH;
300
301         if (refine & REFINE_PRINCIPAL_POINT)
302                 flags |= LIBMV_REFINE_PRINCIPAL_POINT;
303
304         if (refine & REFINE_RADIAL_DISTORTION_K1)
305                 flags |= LIBMV_REFINE_RADIAL_DISTORTION_K1;
306
307         if (refine & REFINE_RADIAL_DISTORTION_K2)
308                 flags |= LIBMV_REFINE_RADIAL_DISTORTION_K2;
309
310         return flags;
311 }
312
313 /* Count tracks which has markers at both of keyframes. */
314 static int reconstruct_count_tracks_on_both_keyframes(MovieTracking *tracking, MovieTrackingObject *object)
315 {
316         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
317         int tot = 0;
318         int frame1 = object->keyframe1, frame2 = object->keyframe2;
319         MovieTrackingTrack *track;
320
321         track = tracksbase->first;
322         while (track) {
323                 if (BKE_tracking_track_has_enabled_marker_at_frame(track, frame1)) {
324                         if (BKE_tracking_track_has_enabled_marker_at_frame(track, frame2)) {
325                                 tot++;
326                         }
327                 }
328
329                 track = track->next;
330         }
331
332         return tot;
333 }
334
335 /* Perform early check on whether everything is fine to start reconstruction. */
336 bool BKE_tracking_reconstruction_check(MovieTracking *tracking, MovieTrackingObject *object,
337                                        char *error_msg, int error_size)
338 {
339         if (tracking->settings.motion_flag & TRACKING_MOTION_MODAL) {
340                 /* TODO: check for number of tracks? */
341                 return true;
342         }
343         else if ((tracking->settings.reconstruction_flag & TRACKING_USE_KEYFRAME_SELECTION) == 0) {
344                 /* automatic keyframe selection does not require any pre-process checks */
345                 if (reconstruct_count_tracks_on_both_keyframes(tracking, object) < 8) {
346                         BLI_strncpy(error_msg,
347                                     N_("At least 8 common tracks on both of keyframes are needed for reconstruction"),
348                                     error_size);
349
350                         return false;
351                 }
352         }
353
354 #ifndef WITH_LIBMV
355         BLI_strncpy(error_msg, N_("Blender is compiled without motion tracking library"), error_size);
356         return false;
357 #endif
358
359         return true;
360 }
361
362 /* Create context for camera/object motion reconstruction.
363  * Copies all data needed for reconstruction from movie
364  * clip datablock, so editing this clip is safe during
365  * reconstruction job is in progress.
366  */
367 MovieReconstructContext *BKE_tracking_reconstruction_context_new(MovieClip *clip, MovieTrackingObject *object,
368                                                                  int keyframe1, int keyframe2, int width, int height)
369 {
370         MovieTracking *tracking = &clip->tracking;
371         MovieReconstructContext *context = MEM_callocN(sizeof(MovieReconstructContext), "MovieReconstructContext data");
372         MovieTrackingCamera *camera = &tracking->camera;
373         ListBase *tracksbase = BKE_tracking_object_get_tracks(tracking, object);
374         float aspy = 1.0f / tracking->camera.pixel_aspect;
375         int num_tracks = BLI_countlist(tracksbase);
376         int sfra = INT_MAX, efra = INT_MIN;
377         MovieTrackingTrack *track;
378
379         BLI_strncpy(context->object_name, object->name, sizeof(context->object_name));
380         context->is_camera = object->flag & TRACKING_OBJECT_CAMERA;
381         context->motion_flag = tracking->settings.motion_flag;
382
383         context->select_keyframes =
384                 (tracking->settings.reconstruction_flag & TRACKING_USE_KEYFRAME_SELECTION) != 0;
385
386         context->focal_length = camera->focal;
387         context->principal_point[0] = camera->principal[0];
388         context->principal_point[1] = camera->principal[1] * aspy;
389
390         context->width = width;
391         context->height = height;
392
393         context->k1 = camera->k1;
394         context->k2 = camera->k2;
395         context->k3 = camera->k3;
396
397         context->tracks_map = tracks_map_new(context->object_name, context->is_camera, num_tracks, 0);
398
399         track = tracksbase->first;
400         while (track) {
401                 int first = 0, last = track->markersnr - 1;
402                 MovieTrackingMarker *first_marker = &track->markers[0];
403                 MovieTrackingMarker *last_marker = &track->markers[track->markersnr - 1];
404
405                 /* find first not-disabled marker */
406                 while (first <= track->markersnr - 1 && first_marker->flag & MARKER_DISABLED) {
407                         first++;
408                         first_marker++;
409                 }
410
411                 /* find last not-disabled marker */
412                 while (last >= 0 && last_marker->flag & MARKER_DISABLED) {
413                         last--;
414                         last_marker--;
415                 }
416
417                 if (first < track->markersnr - 1)
418                         sfra = min_ii(sfra, first_marker->framenr);
419
420                 if (last >= 0)
421                         efra = max_ii(efra, last_marker->framenr);
422
423                 tracks_map_insert(context->tracks_map, track, NULL);
424
425                 track = track->next;
426         }
427
428         context->sfra = sfra;
429         context->efra = efra;
430
431         context->tracks = libmv_tracks_new(clip, tracksbase, width, height * aspy);
432         context->keyframe1 = keyframe1;
433         context->keyframe2 = keyframe2;
434         context->refine_flags = reconstruct_refine_intrinsics_get_flags(tracking, object);
435
436         return context;
437 }
438
439 /* Free memory used by a reconstruction process. */
440 void BKE_tracking_reconstruction_context_free(MovieReconstructContext *context)
441 {
442         if (context->reconstruction)
443                 libmv_reconstructionDestroy(context->reconstruction);
444
445         libmv_tracksDestroy(context->tracks);
446
447         tracks_map_free(context->tracks_map, NULL);
448
449         MEM_freeN(context);
450 }
451
452 /* Callback which is called from libmv side to update progress in the interface. */
453 static void reconstruct_update_solve_cb(void *customdata, double progress, const char *message)
454 {
455         ReconstructProgressData *progressdata = customdata;
456
457         if (progressdata->progress) {
458                 *progressdata->progress = progress;
459                 *progressdata->do_update = TRUE;
460         }
461
462         BLI_snprintf(progressdata->stats_message, progressdata->message_size, "Solving camera | %s", message);
463 }
464 /* FIll in camera intrinsics structure from reconstruction context. */
465 static void camraIntrincicsOptionsFromContext(libmv_CameraIntrinsicsOptions *camera_intrinsics_options,
466                                               MovieReconstructContext *context)
467 {
468         camera_intrinsics_options->focal_length = context->focal_length;
469
470         camera_intrinsics_options->principal_point_x = context->principal_point[0];
471         camera_intrinsics_options->principal_point_y = context->principal_point[1];
472
473         camera_intrinsics_options->k1 = context->k1;
474         camera_intrinsics_options->k2 = context->k2;
475         camera_intrinsics_options->k3 = context->k3;
476
477         camera_intrinsics_options->image_width = context->width;
478         camera_intrinsics_options->image_height = context->height;
479 }
480
481 /* Fill in reconstruction options structure from reconstruction context. */
482 static void reconstructionOptionsFromContext(libmv_ReconstructionOptions *reconstruction_options,
483                                              MovieReconstructContext *context)
484 {
485         reconstruction_options->select_keyframes = context->select_keyframes;
486
487         reconstruction_options->keyframe1 = context->keyframe1;
488         reconstruction_options->keyframe2 = context->keyframe2;
489
490         reconstruction_options->refine_intrinsics = context->refine_flags;
491 }
492
493 /* Solve camera/object motion and reconstruct 3D markers position
494  * from a prepared reconstruction context.
495  *
496  * stop is not actually used at this moment, so reconstruction
497  * job could not be stopped.
498  *
499  * do_update, progress and stat_message are set by reconstruction
500  * callback in libmv side and passing to an interface.
501  */
502 void BKE_tracking_reconstruction_solve(MovieReconstructContext *context, short *stop, short *do_update,
503                                        float *progress, char *stats_message, int message_size)
504 {
505         float error;
506
507         ReconstructProgressData progressdata;
508
509         libmv_CameraIntrinsicsOptions camera_intrinsics_options;
510         libmv_ReconstructionOptions reconstruction_options;
511
512         progressdata.stop = stop;
513         progressdata.do_update = do_update;
514         progressdata.progress = progress;
515         progressdata.stats_message = stats_message;
516         progressdata.message_size = message_size;
517
518         camraIntrincicsOptionsFromContext(&camera_intrinsics_options, context);
519         reconstructionOptionsFromContext(&reconstruction_options, context);
520
521         if (context->motion_flag & TRACKING_MOTION_MODAL) {
522                 context->reconstruction = libmv_solveModal(context->tracks,
523                                                            &camera_intrinsics_options,
524                                                            &reconstruction_options,
525                                                            reconstruct_update_solve_cb, &progressdata);
526         }
527         else {
528                 context->reconstruction = libmv_solveReconstruction(context->tracks,
529                                                                     &camera_intrinsics_options,
530                                                                     &reconstruction_options,
531                                                                     reconstruct_update_solve_cb, &progressdata);
532
533                 if (context->select_keyframes) {
534                         /* store actual keyframes used for reconstruction to update them in the interface later */
535                         context->keyframe1 = reconstruction_options.keyframe1;
536                         context->keyframe2 = reconstruction_options.keyframe2;
537                 }
538         }
539
540         error = libmv_reprojectionError(context->reconstruction);
541
542         context->reprojection_error = error;
543 }
544
545 /* Finish reconstruction process by copying reconstructed data
546  * to an actual movie clip datablock.
547  */
548 bool BKE_tracking_reconstruction_finish(MovieReconstructContext *context, MovieTracking *tracking)
549 {
550         MovieTrackingReconstruction *reconstruction;
551         MovieTrackingObject *object;
552
553         tracks_map_merge(context->tracks_map, tracking);
554         BKE_tracking_dopesheet_tag_update(tracking);
555
556         object = BKE_tracking_object_get_named(tracking, context->object_name);
557         
558         if (context->is_camera)
559                 reconstruction = &tracking->reconstruction;
560         else
561                 reconstruction = &object->reconstruction;
562
563         /* update keyframe in the interface */
564         if (context->select_keyframes) {
565                 object->keyframe1 = context->keyframe1;
566                 object->keyframe2 = context->keyframe2;
567         }
568
569         reconstruction->error = context->reprojection_error;
570         reconstruction->flag |= TRACKING_RECONSTRUCTED;
571
572         if (!reconstruct_retrieve_libmv(context, tracking))
573                 return false;
574
575         return true;
576 }
577
578 static void tracking_scale_reconstruction(ListBase *tracksbase, MovieTrackingReconstruction *reconstruction,
579                                           float scale[3])
580 {
581         MovieTrackingTrack *track;
582         int i;
583         float first_camera_delta[3] = {0.0f, 0.0f, 0.0f};
584
585         if (reconstruction->camnr > 0) {
586                 mul_v3_v3v3(first_camera_delta, reconstruction->cameras[0].mat[3], scale);
587         }
588
589         for (i = 0; i < reconstruction->camnr; i++) {
590                 MovieReconstructedCamera *camera = &reconstruction->cameras[i];
591                 mul_v3_v3(camera->mat[3], scale);
592                 sub_v3_v3(camera->mat[3], first_camera_delta);
593         }
594
595         for (track = tracksbase->first; track; track = track->next) {
596                 if (track->flag & TRACK_HAS_BUNDLE) {
597                         mul_v3_v3(track->bundle_pos, scale);
598                         sub_v3_v3(track->bundle_pos, first_camera_delta);
599                 }
600         }
601 }
602
603 /* Apply scale on all reconstructed cameras and bundles,
604  * used by camera scale apply operator.
605  */
606 void BKE_tracking_reconstruction_scale(MovieTracking *tracking, float scale[3])
607 {
608         MovieTrackingObject *object;
609
610         for (object = tracking->objects.first; object; object = object->next) {
611                 ListBase *tracksbase;
612                 MovieTrackingReconstruction *reconstruction;
613
614                 tracksbase = BKE_tracking_object_get_tracks(tracking, object);
615                 reconstruction = BKE_tracking_object_get_reconstruction(tracking, object);
616
617                 tracking_scale_reconstruction(tracksbase, reconstruction, scale);
618         }
619 }