2.50: svn merge https://svn.blender.org/svnroot/bf-blender/trunk/blender -r18677:19317

Notes:
* Sequence transform strip uses G.scene global, this is commented
  out now, should be fixed.
* Etch-a-ton code was most difficult to merge. The files already in
  2.5 got merged, but no new files were added. Calls to these files
  are commented out with "XXX etch-a-ton". editarmature.c and
  transform_snap.c were complex to merge. Martin, please check?
* Game engine compiles and links again here for scons/make/cmake
  (player still fails to link).

5 files changed, 207 insertions, 2 deletions

diff --git a/source/blender/blenlib/BLI_arithb.h b/source/blender/blenlib/BLI_arithb.h
index 5acee360872..30bb4d11450 100644
--- a/source/blender/blenlib/BLI_arithb.h
+++ b/source/blender/blenlib/BLI_arithb.h
@@ -392,8 +392,10 @@ void tubemap(float x, float y, float z, float *u, float *v);
 void spheremap(float x, float y, float z, float *u, float *v);
 
 int LineIntersectLine(float v1[3], float v2[3], float v3[3], float v4[3], float i1[3], float i2[3]);
+int LineIntersectLineStrict(float v1[3], float v2[3], float v3[3], float v4[3], float vi[3], float *lambda);
 int LineIntersectsTriangle(float p1[3], float p2[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv);
 int RayIntersectsTriangle(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv);
+int RayIntersectsTriangleThreshold(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float threshold);
 int SweepingSphereIntersectsTriangleUV(float p1[3], float p2[3], float radius, float v0[3], float v1[3], float v2[3], float *lambda, float *ipoint);
 int AxialLineIntersectsTriangle(int axis, float co1[3], float co2[3], float v0[3], float v1[3], float v2[3], float *lambda);
 int AabbIntersectAabb(float min1[3], float max1[3], float min2[3], float max2[3]);
diff --git a/source/blender/blenlib/BLI_graph.h b/source/blender/blenlib/BLI_graph.h
index 160c2e04cf5..f4fccfcbb2c 100644
--- a/source/blender/blenlib/BLI_graph.h
+++ b/source/blender/blenlib/BLI_graph.h
@@ -60,6 +60,39 @@ typedef struct BArc {
 	int symmetry_flag;
 } BArc;
 
+struct BArcIterator;
+
+void* IT_head(void* iter);
+void* IT_tail(void* iter);
+void* IT_peek(void* iter, int n);
+void* IT_next(void* iter);
+void* IT_nextN(void* iter, int n);
+void* IT_previous(void* iter);
+int   IT_stopped(void* iter);
+
+typedef void* (*HeadFct)(void* iter);
+typedef void* (*TailFct)(void* iter);
+typedef void* (*PeekFct)(void* iter, int n);
+typedef void* (*NextFct)(void* iter);
+typedef void* (*NextNFct)(void* iter, int n);
+typedef void* (*PreviousFct)(void* iter);
+typedef int   (*StoppedFct)(void* iter);
+
+typedef struct BArcIterator {
+	HeadFct		head;
+	TailFct		tail;
+	PeekFct		peek;
+	NextFct		next;
+	NextNFct	nextN;
+	PreviousFct	previous;
+	StoppedFct	stopped;
+	
+	float *p, *no;
+	
+	int length;
+	int index;
+} BArcIterator;
+
 /* Helper structure for radial symmetry */
 typedef struct RadialArc
 {
diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c
index 0df4792cd3d..2368f0cd2ba 100644
--- a/source/blender/blenlib/intern/arithb.c
+++ b/source/blender/blenlib/intern/arithb.c
@@ -3896,6 +3896,57 @@ int RayIntersectsTriangle(float p1[3], float d[3], float v0[3], float v1[3], flo
 	return 1;
 }
 
+int RayIntersectsTriangleThreshold(float p1[3], float d[3], float v0[3], float v1[3], float v2[3], float *lambda, float *uv, float threshold)
+{
+	float p[3], s[3], e1[3], e2[3], q[3];
+	float a, f, u, v;
+	float du = 0, dv = 0;
+	
+	VecSubf(e1, v1, v0);
+	VecSubf(e2, v2, v0);
+	
+	Crossf(p, d, e2);
+	a = Inpf(e1, p);
+	if ((a > -0.000001) && (a < 0.000001)) return 0;
+	f = 1.0f/a;
+	
+	VecSubf(s, p1, v0);
+	
+	Crossf(q, s, e1);
+	*lambda = f * Inpf(e2, q);
+	if ((*lambda < 0.0)) return 0;
+	
+	u = f * Inpf(s, p);
+	v = f * Inpf(d, q);
+	
+	if (u < 0) du = u;
+	if (u > 1) du = u - 1;
+	if (v < 0) dv = v;
+	if (v > 1) dv = v - 1;
+	if (u > 0 && v > 0 && u + v > 1)
+	{
+		float t = u + v - 1;
+		du = u - t/2;
+		dv = v - t/2;
+	}
+
+	VecMulf(e1, du);
+	VecMulf(e2, dv);
+	
+	if (Inpf(e1, e1) + Inpf(e2, e2) > threshold * threshold)
+	{
+		return 0;
+	}
+
+	if(uv) {
+		uv[0]= u;
+		uv[1]= v;
+	}
+	
+	return 1;
+}
+
+
 /* Adapted from the paper by Kasper Fauerby */
 /* "Improved Collision detection and Response" */
 static int getLowestRoot(float a, float b, float c, float maxR, float* root)
@@ -4245,6 +4296,67 @@ int LineIntersectLine(float v1[3], float v2[3], float v3[3], float v4[3], float
 	}
 } 
 
+/* Intersection point strictly between the two lines
+ * 0 when no intersection is found 
+ * */
+int LineIntersectLineStrict(float v1[3], float v2[3], float v3[3], float v4[3], float vi[3], float *lambda)
+{
+	float a[3], b[3], c[3], ab[3], cb[3], ca[3], dir1[3], dir2[3];
+	float d;
+	float d1;
+	
+	VecSubf(c, v3, v1);
+	VecSubf(a, v2, v1);
+	VecSubf(b, v4, v3);
+
+	VecCopyf(dir1, a);
+	Normalize(dir1);
+	VecCopyf(dir2, b);
+	Normalize(dir2);
+	d = Inpf(dir1, dir2);
+	if (d == 1.0f || d == -1.0f || d == 0) {
+		/* colinear or one vector is zero-length*/
+		return 0;
+	}
+	
+	d1 = d;
+
+	Crossf(ab, a, b);
+	d = Inpf(c, ab);
+
+	/* test if the two lines are coplanar */
+	if (d > -0.000001f && d < 0.000001f) {
+		float f1, f2;
+		Crossf(cb, c, b);
+		Crossf(ca, c, a);
+
+		f1 = Inpf(cb, ab) / Inpf(ab, ab);
+		f2 = Inpf(ca, ab) / Inpf(ab, ab);
+		
+		if (f1 >= 0 && f1 <= 1 &&
+			f2 >= 0 && f2 <= 1)
+		{
+			VecMulf(a, f1);
+			VecAddf(vi, v1, a);
+			
+			if (lambda != NULL)
+			{
+				*lambda = f1;
+			}
+			
+			return 1; /* intersection found */
+		}
+		else
+		{
+			return 0;
+		}
+	}
+	else
+	{
+		return 0;
+	}
+} 
+
 int AabbIntersectAabb(float min1[3], float max1[3], float min2[3], float max2[3])
 {
 	return (min1[0]<max2[0] && min1[1]<max2[1] && min1[2]<max2[2] &&
diff --git a/source/blender/blenlib/intern/bpath.c b/source/blender/blenlib/intern/bpath.c
index f1057ff3efe..85a95fa6e66 100644
--- a/source/blender/blenlib/intern/bpath.c
+++ b/source/blender/blenlib/intern/bpath.c
@@ -341,9 +341,9 @@ void BLI_bpathIterator_step( struct BPathIterator *bpi) {
 				bSound *snd = (bSound *)bpi->data;
 				
 				bpi->lib = snd->id.lib ? snd->id.lib->filename : NULL;
-				bpi->path = snd->sample->name;
+				bpi->path = snd->name;
 				bpi->name = snd->id.name+2;
-				bpi->len = sizeof(snd->sample->name);
+				bpi->len = sizeof(snd->name);
 				
 				/* we are done, advancing to the next item, this type worked fine */
 				break;
diff --git a/source/blender/blenlib/intern/graph.c b/source/blender/blenlib/intern/graph.c
index 11bb8ea8964..cc15c499290 100644
--- a/source/blender/blenlib/intern/graph.c
+++ b/source/blender/blenlib/intern/graph.c
@@ -1031,6 +1031,11 @@ void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit)
 	BNode *node;
 	BArc *arc;
 	
+	if (root_node == NULL)
+	{
+		return;
+	}
+	
 	if (BLI_isGraphCyclic(graph))
 	{
 		return;
@@ -1083,3 +1088,56 @@ void BLI_markdownSymmetry(BGraph *graph, BNode *root_node, float limit)
 	}
 }
 
+void* IT_head(void* arg)
+{
+	BArcIterator *iter = (BArcIterator*)arg; 
+	return iter->head(iter);
+}
+
+void* IT_tail(void* arg)
+{
+	BArcIterator *iter = (BArcIterator*)arg; 
+	return iter->tail(iter); 
+}
+
+void* IT_peek(void* arg, int n)
+{
+	BArcIterator *iter = (BArcIterator*)arg;
+	
+	if (iter->index + n < 0)
+	{
+		return iter->head(iter);
+	}
+	else if (iter->index + n >= iter->length)
+	{
+		return iter->tail(iter);
+	}
+	else
+	{
+		return iter->peek(iter, n);
+	}
+}
+
+void* IT_next(void* arg)
+{
+	BArcIterator *iter = (BArcIterator*)arg; 
+	return iter->next(iter);
+}
+
+void* IT_nextN(void* arg, int n)
+{
+	BArcIterator *iter = (BArcIterator*)arg; 
+	return iter->nextN(iter, n);
+}
+
+void* IT_previous(void* arg)
+{
+	BArcIterator *iter = (BArcIterator*)arg; 
+	return iter->previous(iter);
+}
+
+int   IT_stopped(void* arg)
+{
+	BArcIterator *iter = (BArcIterator*)arg; 
+	return iter->stopped(iter);
+}