Camera tracking integration

===========================

Commiting camera tracking integration gsoc project into trunk.

This commit includes:

- Bundled version of libmv library (with some changes against official repo,
  re-sync with libmv repo a bit later)
- New datatype ID called MovieClip which is optimized to work with movie
  clips (both of movie files and image sequences) and doing camera/motion
  tracking operations.
- New editor called Clip Editor which is currently used for motion/tracking
  stuff only, but which can be easily extended to work with masks too.

  This editor supports:
  * Loading movie files/image sequences
  * Build proxies with different size for loaded movie clip, also supports
    building undistorted proxies to increase speed of playback in
    undistorted mode.
  * Manual lens distortion mode calibration using grid and grease pencil
  * Supervised 2D tracking using two different algorithms KLT and SAD.
  * Basic algorithm for feature detection
  * Camera motion solving. scene orientation

- New constraints to "link" scene objects with solved motions from clip:

  * Follow Track (make object follow 2D motion of track with given name
    or parent object to reconstructed 3D position of track)
  * Camera Solver to make camera moving in the same way as reconstructed camera

This commit NOT includes changes from tomato branch:

- New nodes (they'll be commited as separated patch)
- Automatic image offset guessing for image input node and image editor
  (need to do more tests and gather more feedback)
- Code cleanup in libmv-capi. It's not so critical cleanup, just increasing
  readability and understanadability of code. Better to make this chaneg when
  Keir will finish his current patch.

More details about this project can be found on this page:
    http://wiki.blender.org/index.php/User:Nazg-gul/GSoC-2011

Further development of small features would be done in trunk, bigger/experimental
features would first be implemented in tomato branch.

5 files changed, 342 insertions, 4 deletions

diff --git a/source/blender/editors/transform/transform.c b/source/blender/editors/transform/transform.c
index 591bb99ae22..13d686508de 100644
--- a/source/blender/editors/transform/transform.c
+++ b/source/blender/editors/transform/transform.c
@@ -48,6 +48,7 @@
 #include "DNA_armature_types.h"
 #include "DNA_constraint_types.h"
 #include "DNA_meshdata_types.h"
+#include "DNA_movieclip_types.h"
 #include "DNA_scene_types.h"		/* PET modes			*/
 
 #include "RNA_access.h"
@@ -71,6 +72,7 @@
 #include "ED_markers.h"
 #include "ED_view3d.h"
 #include "ED_mesh.h"
+#include "ED_clip.h"
 
 #include "UI_view2d.h"
 #include "WM_types.h"
@@ -155,6 +157,17 @@ void convertViewVec(TransInfo *t, float *vec, int dx, int dy)
 	else if(ELEM(t->spacetype, SPACE_NODE, SPACE_SEQ)) {
 		convertViewVec2D(&t->ar->v2d, vec, dx, dy);
 	}
+	else if(t->spacetype==SPACE_CLIP) {
+		View2D *v2d = t->view;
+		float divx, divy;
+
+		divx= v2d->mask.xmax-v2d->mask.xmin;
+		divy= v2d->mask.ymax-v2d->mask.ymin;
+
+		vec[0]= (v2d->cur.xmax-v2d->cur.xmin)*(dx)/divx;
+		vec[1]= (v2d->cur.ymax-v2d->cur.ymin)*(dy)/divy;
+		vec[2]= 0.0f;
+	}
 }
 
 void projectIntView(TransInfo *t, float *vec, int *adr)
@@ -205,6 +218,9 @@ void projectIntView(TransInfo *t, float *vec, int *adr)
 		adr[0]= out[0];
 		adr[1]= out[1];
 	}
+	else if(t->spacetype==SPACE_CLIP) {
+		UI_view2d_to_region_no_clip(t->view, vec[0], vec[1], adr, adr+1);
+	}
 }
 
 void projectFloatView(TransInfo *t, float *vec, float *adr)
@@ -213,7 +229,7 @@ void projectFloatView(TransInfo *t, float *vec, float *adr)
 		if(t->ar->regiontype == RGN_TYPE_WINDOW)
 			project_float_noclip(t->ar, vec, adr);
 	}
-	else if(t->spacetype==SPACE_IMAGE) {
+	else if(ELEM(t->spacetype, SPACE_IMAGE, SPACE_CLIP)) {
 		int a[2];
 
 		projectIntView(t, vec, a);
@@ -311,6 +327,15 @@ static void viewRedrawForce(const bContext *C, TransInfo *t)
 		if(sima->lock) WM_event_add_notifier(C, NC_GEOM|ND_DATA, t->obedit->data);
 		else ED_area_tag_redraw(t->sa);
 	}
+	else if (t->spacetype==SPACE_CLIP) {
+		SpaceClip *sc= (SpaceClip*)t->sa->spacedata.first;
+		MovieClip *clip= ED_space_clip(sc);
+
+		/* objects could be parented to tracking data, so send this for viewport refresh */
+		WM_event_add_notifier(C, NC_OBJECT|ND_TRANSFORM, NULL);
+
+		WM_event_add_notifier(C, NC_MOVIECLIP|NA_EDITED, clip);
+	}
 }
 
 static void viewRedrawPost(bContext *C, TransInfo *t)
@@ -579,10 +604,18 @@ int transformEvent(TransInfo *t, wmEvent *event)
 					initSnapping(t, NULL); // need to reinit after mode change
 					t->redraw |= TREDRAW_HARD;
 				}
+				else if(t->mode == TFM_TRANSLATION) {
+					if(t->options&CTX_MOVIECLIP) {
+						restoreTransObjects(t);
+
+						t->flag^= T_ALT_TRANSFORM;
+						t->redraw |= TREDRAW_HARD;
+					}
+				}
 				break;
 			case TFM_MODAL_ROTATE:
 				/* only switch when... */
-				if(!(t->options & CTX_TEXTURE)) {
+				if(!(t->options & CTX_TEXTURE) && !(t->options & CTX_MOVIECLIP)) {
 					if( ELEM4(t->mode, TFM_ROTATION, TFM_RESIZE, TFM_TRACKBALL, TFM_TRANSLATION) ) {
 						
 						resetTransRestrictions(t);
@@ -837,7 +870,7 @@ int transformEvent(TransInfo *t, wmEvent *event)
 			break;
 		case RKEY:
 			/* only switch when... */
-			if(!(t->options & CTX_TEXTURE)) {
+			if(!(t->options & CTX_TEXTURE) && !(t->options & CTX_MOVIECLIP)) {
 				if( ELEM4(t->mode, TFM_ROTATION, TFM_RESIZE, TFM_TRACKBALL, TFM_TRANSLATION) ) {
 
 					resetTransRestrictions(t);
@@ -1502,6 +1535,11 @@ int initTransform(bContext *C, TransInfo *t, wmOperator *op, wmEvent *event, int
 		t->draw_handle_view = ED_region_draw_cb_activate(t->ar->type, drawTransformView, t, REGION_DRAW_POST_VIEW);
 		//t->draw_handle_pixel = ED_region_draw_cb_activate(t->ar->type, drawTransformPixel, t, REGION_DRAW_POST_PIXEL);
 	}
+	else if(t->spacetype == SPACE_CLIP) {
+		unit_m3(t->spacemtx);
+		t->draw_handle_view = ED_region_draw_cb_activate(t->ar->type, drawTransformView, t, REGION_DRAW_POST_VIEW);
+		t->options |= CTX_MOVIECLIP;
+	}
 	else
 		unit_m3(t->spacemtx);
 
@@ -3293,7 +3331,7 @@ void initTranslation(TransInfo *t)
 			t->snap[2] = t->snap[1] * 0.1f;
 		}
 	}
-	else if(t->spacetype == SPACE_IMAGE) {
+	else if(ELEM(t->spacetype, SPACE_IMAGE, SPACE_CLIP)) {
 		t->snap[0] = 0.0f;
 		t->snap[1] = 0.125f;
 		t->snap[2] = 0.0625f;
diff --git a/source/blender/editors/transform/transform.h b/source/blender/editors/transform/transform.h
index 77e7cfb4d12..8b8ae95631c 100644
--- a/source/blender/editors/transform/transform.h
+++ b/source/blender/editors/transform/transform.h
@@ -382,6 +382,9 @@ typedef struct TransInfo {
 
 #define T_RELEASE_CONFIRM	(1 << 23)
 
+	/* alternative transformation. used to add offset to tracking markers */
+#define T_ALT_TRANSFORM		(1 << 24)
+
 /* TransInfo->modifiers */
 #define	MOD_CONSTRAINT_SELECT	0x01
 #define	MOD_PRECISION			0x02
@@ -546,6 +549,7 @@ void flushTransParticles(TransInfo *t);
 int clipUVTransform(TransInfo *t, float *vec, int resize);
 void flushTransNodes(TransInfo *t);
 void flushTransSeq(TransInfo *t);
+void flushTransTracking(TransInfo *t);
 
 /*********************** exported from transform_manipulator.c ********** */
 int gimbal_axis(struct Object *ob, float gmat[][3]); /* return 0 when no gimbal for selection */
diff --git a/source/blender/editors/transform/transform_conversions.c b/source/blender/editors/transform/transform_conversions.c
index 7eb8dc11a43..0a6f49f7c9f 100644
--- a/source/blender/editors/transform/transform_conversions.c
+++ b/source/blender/editors/transform/transform_conversions.c
@@ -51,6 +51,7 @@
 #include "DNA_scene_types.h"
 #include "DNA_meshdata_types.h"
 #include "DNA_gpencil_types.h"
+#include "DNA_movieclip_types.h"
 
 #include "MEM_guardedalloc.h"
 
@@ -74,6 +75,9 @@
 #include "BKE_bmesh.h"
 #include "BKE_scene.h"
 #include "BKE_report.h"
+#include "BKE_tracking.h"
+#include "BKE_movieclip.h"
+#include "BKE_node.h"
 
 
 #include "ED_anim_api.h"
@@ -88,8 +92,12 @@
 #include "ED_node.h"
 #include "ED_types.h"
 #include "ED_uvedit.h"
+#include "ED_clip.h"
 #include "ED_util.h"  /* for crazyspace correction */
 
+#include "WM_api.h"		/* for WM_event_add_notifier to deal with stabilization nodes */
+#include "WM_types.h"
+
 #include "UI_view2d.h"
 
 #include "BLI_math.h"
@@ -4796,6 +4804,17 @@ void special_aftertrans_update(bContext *C, TransInfo *t)
 		/* clear link line */
 		ED_node_link_intersect_test(t->sa, 0);
 	}
+	else if (t->spacetype == SPACE_CLIP) {
+		SpaceClip *sc= t->sa->spacedata.first;
+		MovieClip *clip= ED_space_clip(sc);
+
+		if(t->scene->nodetree) {
+			/* tracks can be used for stabilization nodes,
+			   flush update for such nodes */
+			nodeUpdateID(t->scene->nodetree, &clip->id);
+			WM_event_add_notifier(C, NC_SCENE|ND_NODES, NULL);
+		}
+	}
 	else if (t->spacetype == SPACE_ACTION) {
 		SpaceAction *saction= (SpaceAction *)t->sa->spacedata.first;
 		bAnimContext ac;
@@ -5264,6 +5283,229 @@ static void createTransNodeData(bContext *C, TransInfo *t)
 	CTX_DATA_END
 }
 
+/* *** CLIP EDITOR *** */
+
+typedef struct TransDataTracking {
+	int area;
+	float *relative, *loc;
+	float soffset[2], srelative[2];
+	float offset[2];
+
+	float (*smarkers)[2];
+	int markersnr;
+	MovieTrackingMarker *markers;
+} TransDataTracking;
+
+static void markerToTransDataInit(TransData *td, TransData2D *td2d,
+			TransDataTracking *tdt, MovieTrackingTrack *track, int area, float *loc, float *rel, float *off)
+{
+	int anchor = area==TRACK_AREA_POINT && off;
+
+	if(anchor) {
+		td2d->loc[0] = rel[0]; /* hold original location */
+		td2d->loc[1] = rel[1];
+
+		tdt->loc= loc;
+		td2d->loc2d = loc; /* current location */
+	} else {
+		td2d->loc[0] = loc[0]; /* hold original location */
+		td2d->loc[1] = loc[1];
+
+		td2d->loc2d = loc; /* current location */
+	}
+	td2d->loc[2] = 0.0f;
+
+	tdt->relative= rel;
+	tdt->area= area;
+
+	tdt->markersnr= track->markersnr;
+	tdt->markers= track->markers;
+
+	if(rel) {
+		if(!anchor) {
+			td2d->loc[0]+= rel[0];
+			td2d->loc[1]+= rel[1];
+		}
+
+		copy_v2_v2(tdt->srelative, rel);
+	}
+
+	if(off)
+		copy_v2_v2(tdt->soffset, off);
+
+	td->flag = 0;
+	td->loc = td2d->loc;
+	VECCOPY(td->center, td->loc);
+	VECCOPY(td->iloc, td->loc);
+
+	memset(td->axismtx, 0, sizeof(td->axismtx));
+	td->axismtx[2][2] = 1.0f;
+
+	td->ext= NULL; td->val= NULL;
+
+	td->flag |= TD_SELECTED;
+	td->dist= 0.0;
+
+	unit_m3(td->mtx);
+	unit_m3(td->smtx);
+}
+
+static void trackToTransData(SpaceClip *sc, TransData *td, TransData2D *td2d,
+			TransDataTracking *tdt, MovieTrackingTrack *track)
+{
+	MovieTrackingMarker *marker= BKE_tracking_ensure_marker(track, sc->user.framenr);
+
+	track->transflag= marker->flag;
+
+	marker->flag&= ~(MARKER_DISABLED|MARKER_TRACKED);
+
+	markerToTransDataInit(td++, td2d++, tdt++, track, TRACK_AREA_POINT, track->offset, marker->pos, track->offset);
+
+	if(track->flag&SELECT)
+		markerToTransDataInit(td++, td2d++, tdt++, track, TRACK_AREA_POINT, marker->pos, NULL, NULL);
+
+	if(track->pat_flag&SELECT) {
+		markerToTransDataInit(td++, td2d++, tdt++, track, TRACK_AREA_PAT, track->pat_min, marker->pos, NULL);
+		markerToTransDataInit(td++, td2d++, tdt++, track, TRACK_AREA_PAT, track->pat_max, marker->pos, NULL);
+	}
+
+	if(track->search_flag&SELECT) {
+		markerToTransDataInit(td++, td2d++, tdt++, track, TRACK_AREA_SEARCH, track->search_min, marker->pos, NULL);
+		markerToTransDataInit(td++, td2d++, tdt++, track, TRACK_AREA_SEARCH, track->search_max, marker->pos, NULL);
+	}
+}
+
+static void transDataTrackingFree(TransInfo *t)
+{
+	TransDataTracking *tdt= t->customData;
+
+	if(tdt) {
+		if(tdt->smarkers) MEM_freeN(tdt->smarkers);
+		MEM_freeN(tdt);
+	}
+}
+
+static void createTransTrackingData(bContext *C, TransInfo *t)
+{
+	TransData *td;
+	TransData2D *td2d;
+	SpaceClip *sc = CTX_wm_space_clip(C);
+	MovieClip *clip = ED_space_clip(sc);
+	MovieTrackingTrack *track;
+	MovieTrackingMarker *marker;
+	TransDataTracking *tdt;
+	int framenr = sc->user.framenr;
+
+	if(clip && !BKE_movieclip_has_frame(clip, &sc->user)) {
+		t->total = 0;
+		return;
+	}
+
+	/* count */
+	t->total = 0;
+
+	track = clip->tracking.tracks.first;
+	while(track) {
+		if(TRACK_VIEW_SELECTED(sc, track) && (track->flag&TRACK_LOCKED)==0) {
+			marker= BKE_tracking_get_marker(track, framenr);
+
+			if(marker) {
+				t->total++;	/* offset */
+
+				if(track->flag&SELECT) t->total++;
+				if(track->pat_flag&SELECT) t->total+= 2;
+				if(track->search_flag&SELECT) t->total+= 2;
+			}
+		}
+
+		track = track->next;
+	}
+
+	if(t->total==0)
+		return;
+
+	td = t->data = MEM_callocN(t->total*sizeof(TransData), "TransTracking TransData");
+	td2d = t->data2d = MEM_callocN(t->total*sizeof(TransData2D), "TransTracking TransData2D");
+	tdt = t->customData = MEM_callocN(t->total*sizeof(TransDataTracking), "TransTracking TransDataTracking");
+
+	t->customFree= transDataTrackingFree;
+
+	/* create actual data */
+	track = clip->tracking.tracks.first;
+	while(track) {
+		if(TRACK_VIEW_SELECTED(sc, track) && (track->flag&TRACK_LOCKED)==0) {
+			marker= BKE_tracking_get_marker(track, framenr);
+
+			trackToTransData(sc, td, td2d, tdt, track);
+
+			/* offset */
+			td++;
+			td2d++;
+			tdt++;
+
+			if((marker->flag&MARKER_DISABLED)==0) {
+				if(track->flag&SELECT) {td++; td2d++; tdt++;}
+				if(track->pat_flag&SELECT) {td+= 2; td2d+= 2;tdt+=2;}
+			}
+
+			if(track->search_flag&SELECT) {
+				td+= 2;
+				td2d+= 2;
+				tdt+= 2;
+
+				if(marker->flag&MARKER_DISABLED) {
+					td+= 3;
+					td2d+= 3;
+					tdt+= 3;
+				};
+			}
+		}
+
+		track = track->next;
+	}
+}
+
+void flushTransTracking(TransInfo *t)
+{
+	TransData *td;
+	TransData2D *td2d;
+	TransDataTracking *tdt;
+	int a;
+
+	/* flush to 2d vector from internally used 3d vector */
+	for(a=0, td= t->data, td2d= t->data2d, tdt= t->customData; a<t->total; a++, td2d++, td++, tdt++) {
+		if(t->flag&T_ALT_TRANSFORM) {
+			if(tdt->area==TRACK_AREA_POINT && tdt->relative) {
+				float d[2], d2[2];
+
+				if(!tdt->smarkers) {
+					tdt->smarkers= MEM_callocN(sizeof(*tdt->smarkers)*tdt->markersnr, "flushTransTracking markers");
+					for(a= 0; a<tdt->markersnr; a++)
+						copy_v2_v2(tdt->smarkers[a], tdt->markers[a].pos);
+				}
+
+				sub_v2_v2v2(d, td2d->loc, tdt->soffset);
+				sub_v2_v2(d, tdt->srelative);
+
+				sub_v2_v2v2(d2, td2d->loc, tdt->srelative);
+
+				for(a= 0; a<tdt->markersnr; a++)
+					add_v2_v2v2(tdt->markers[a].pos, tdt->smarkers[a], d2);
+
+				negate_v2_v2(td2d->loc2d, d);
+			}
+		}
+
+		if(tdt->area!=TRACK_AREA_POINT || tdt->relative==0) {
+			td2d->loc2d[0] = td2d->loc[0];
+			td2d->loc2d[1] = td2d->loc[1];
+
+			if(tdt->relative)
+				sub_v2_v2(td2d->loc2d, tdt->relative);
+		}
+	}
+}
+
 void createTransData(bContext *C, TransInfo *t)
 {
 	Scene *scene = t->scene;
@@ -5329,6 +5571,10 @@ void createTransData(bContext *C, TransInfo *t)
 			sort_trans_data_dist(t);
 		}
 	}
+	else if (t->spacetype == SPACE_CLIP) {
+		t->flag |= T_POINTS|T_2D_EDIT;
+		createTransTrackingData(C, t);
+	}
 	else if (t->obedit) {
 		t->ext = NULL;
 		if (t->obedit->type == OB_MESH) {
diff --git a/source/blender/editors/transform/transform_generics.c b/source/blender/editors/transform/transform_generics.c
index 0c3e045d5ce..53e379a2d27 100644
--- a/source/blender/editors/transform/transform_generics.c
+++ b/source/blender/editors/transform/transform_generics.c
@@ -47,6 +47,7 @@
 #include "DNA_meshdata_types.h"
 #include "DNA_view3d_types.h"
 #include "DNA_modifier_types.h"
+#include "DNA_movieclip_types.h"
 
 #include "RNA_access.h"
 
@@ -70,6 +71,7 @@
 #include "BKE_mesh.h"
 #include "BKE_nla.h"
 #include "BKE_context.h"
+#include "BKE_tracking.h"
 
 #include "ED_anim_api.h"
 #include "ED_armature.h"
@@ -83,6 +85,7 @@
 #include "ED_uvedit.h"
 #include "ED_view3d.h"
 #include "ED_curve.h" /* for curve_editnurbs */
+#include "ED_clip.h"
 
 //#include "BDR_unwrapper.h"
 
@@ -863,6 +866,48 @@ void recalcData(TransInfo *t)
 	else if (t->spacetype == SPACE_VIEW3D) {
 		recalcData_view3d(t);
 	}
+	else if (t->spacetype == SPACE_CLIP) {
+		SpaceClip *sc= t->sa->spacedata.first;
+		MovieClip *clip= ED_space_clip(sc);
+		MovieTrackingTrack *track;
+
+		if(t->state == TRANS_CANCEL) {
+			track= clip->tracking.tracks.first;
+			while(track) {
+				if(TRACK_VIEW_SELECTED(sc, track)) {
+					MovieTrackingMarker *marker= BKE_tracking_ensure_marker(track, sc->user.framenr);
+
+					marker->flag= track->transflag;
+				}
+
+				track= track->next;
+			}
+		}
+
+		flushTransTracking(t);
+
+		track= clip->tracking.tracks.first;
+		while(track) {
+			if(TRACK_VIEW_SELECTED(sc, track)) {
+				if (t->mode == TFM_TRANSLATION) {
+					if(TRACK_AREA_SELECTED(track, TRACK_AREA_PAT))
+						BKE_tracking_clamp_track(track, CLAMP_PAT_POS);
+					if(TRACK_AREA_SELECTED(track, TRACK_AREA_SEARCH))
+						BKE_tracking_clamp_track(track, CLAMP_SEARCH_POS);
+				}
+				else if (t->mode == TFM_RESIZE) {
+					if(TRACK_AREA_SELECTED(track, TRACK_AREA_PAT))
+						BKE_tracking_clamp_track(track, CLAMP_PAT_DIM);
+					if(TRACK_AREA_SELECTED(track, TRACK_AREA_SEARCH))
+						BKE_tracking_clamp_track(track, CLAMP_SEARCH_DIM);
+				}
+			}
+
+			track= track->next;
+		}
+
+		DAG_id_tag_update(&clip->id, 0);
+	}
 }
 
 void drawLine(TransInfo *t, float *center, float *dir, char axis, short options)
diff --git a/source/blender/editors/transform/transform_ops.c b/source/blender/editors/transform/transform_ops.c
index f926f442830..7951fe0ee02 100644
--- a/source/blender/editors/transform/transform_ops.c
+++ b/source/blender/editors/transform/transform_ops.c
@@ -973,6 +973,11 @@ void transform_keymap_for_space(wmKeyConfig *keyconf, wmKeyMap *keymap, int spac
 			km = WM_keymap_add_item(keymap, "WM_OT_context_toggle", TABKEY, KM_PRESS, KM_SHIFT, 0);
 			RNA_string_set(km->ptr, "data_path", "tool_settings.use_snap");
 			break;
+		case SPACE_CLIP:
+			WM_keymap_add_item(keymap, OP_TRANSLATION, GKEY, KM_PRESS, 0, 0);
+			WM_keymap_add_item(keymap, OP_TRANSLATION, EVT_TWEAK_S, KM_ANY, 0, 0);
+			WM_keymap_add_item(keymap, OP_RESIZE, SKEY, KM_PRESS, 0, 0);
+			break;
 		default:
 			break;
 	}