New math util funcitons:

- equals_v2v2
- project_v2_v2v2
- isect_seg_seg_v2_point
which would be necessery for my further multires interpolation commit

M_Geometry_LineIntersect2D now uses isect_seg_seg_v2_point(). Behaviour of this
function was changed a bit -- it haven't returned intersection point in several
cases when two segments are making angle.

5 files changed, 93 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index 7d06bbce43d..7dae49f067d 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -73,6 +73,7 @@ void closest_to_line_segment_v3(float r[3], float p[3], float l1[3], float l2[3]
 
 int isect_line_line_v2(float a1[2], float a2[2], float b1[2], float b2[2]);
 int isect_line_line_v2_short(short a1[2], short a2[2], short b1[2], short b2[2]);
+int isect_seg_seg_v2_point(float v1[2], float v2[2], float v3[2], float v4[2], float vi[2]);
 
 /* Returns the number of point of interests
  * 0 - lines are colinear
diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index ec62954149c..3a63e87ac76 100644
--- a/source/blender/blenlib/BLI_math_vector.h
+++ b/source/blender/blenlib/BLI_math_vector.h
@@ -124,6 +124,7 @@ void mid_v3_v3v3(float r[3], const float a[3], const float b[3]);
 MINLINE int is_zero_v3(const float a[3]);
 MINLINE int is_one_v3(const float a[3]);
 
+MINLINE int equals_v2v2(const float *v1, const float *v2);
 MINLINE int equals_v3v3(const float a[3], const float b[3]);
 MINLINE int compare_v3v3(const float a[3], const float b[3], const float limit);
 MINLINE int compare_len_v3v3(const float a[3], const float b[3], const float limit);
@@ -149,6 +150,7 @@ void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const
 
 /********************************* Geometry **********************************/
 
+void project_v2_v2v2(float c[2], const float v1[2], const float v2[2]);
 void project_v3_v3v3(float r[3], const float p[3], const float n[3]);
 void reflect_v3_v3v3(float r[3], const float v[3], const float n[3]);
 void ortho_basis_v3v3_v3(float r1[3], float r2[3], const float a[3]);
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index bab48c722dc..ac62eb71e97 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -282,6 +282,81 @@ int isect_line_line_v2(float *v1, float *v2, float *v3, float *v4)
 	return 0;
 }
 
+/* get intersection point of two 2D segments and return intersection type:
+    -1: colliniar
+     1: intersection */
+int isect_seg_seg_v2_point(float v1[2], float v2[2], float v3[2], float v4[2], float vi[2])
+{
+	float a1, a2, b1, b2, c1, c2, d;
+	float u, v;
+	const float eps= 0.000001f;
+
+	a1= v2[0]-v1[0];
+	b1= v4[0]-v3[0];
+	c1= v1[0]-v4[0];
+
+	a2= v2[1]-v1[1];
+	b2= v4[1]-v3[1];
+	c2= v1[1]-v4[1];
+
+	d= a1*b2-a2*b1;
+
+	if(d==0) {
+		if(a1*c2-a2*c1==0.0f && b1*c2-b2*c1==0.0f) { /* equal lines */
+			float a[2], b[2], c[2];
+			float u2;
+
+			if(len_v2v2(v1, v2)==0.0f) {
+				if(len_v2v2(v3, v4)>eps) {
+					/* use non-point segment as basis */
+					SWAP(float, v1[0], v3[0]);
+					SWAP(float, v1[1], v3[1]);
+					SWAP(float, v2[0], v4[0]);
+					SWAP(float, v2[1], v4[1]);
+				} else { /* both of segments are points */
+					if(equals_v2v2(v1, v3)) { /* points are equal */
+						copy_v2_v2(vi, v1);
+						return 1;
+					}
+
+					/* two different points */
+					return -1;
+				}
+			}
+
+			sub_v2_v2v2(a, v3, v1);
+			sub_v2_v2v2(b, v2, v1);
+			sub_v2_v2v2(c, v2, v1);
+			u= dot_v2v2(a, b) / dot_v2v2(c, c);
+
+			sub_v2_v2v2(a, v4, v1);
+			u2= dot_v2v2(a, b) / dot_v2v2(c, c);
+
+			if(u>u2) SWAP(float, u, u2);
+
+			if(u>1.0f+eps || u2<-eps) return -1; /* non-ovlerlapping segments */
+			else if(maxf(0.0f, u) == minf(1.0f, u2)){ /* one common point: can return result */
+				interp_v2_v2v2(vi, v1, v2, maxf(0, u));
+				return 1;
+			}
+		}
+
+		/* lines are colliniar */
+		return -1;
+	}
+
+	u= (c2*b1-b2*c1)/d;
+	v= (c1*a2-a1*c2)/d;
+
+	if(u>=-eps && u<=1.0f+eps && v>=-eps && v<=1.0f+eps) { /* intersection */
+		interp_v2_v2v2(vi, v1, v2, u);
+		return 1;
+	}
+
+	/* out of segment intersection */
+	return -1;
+}
+
 /*
 -1: colliniar
  1: intersection
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index 35476a8aba9..6ac1fcfab7e 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -231,6 +231,16 @@ void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const
 /********************************* Geometry **********************************/
 
 /* Project v1 on v2 */
+void project_v2_v2v2(float c[2], const float v1[2], const float v2[2])
+{
+	float mul;
+	mul = dot_v2v2(v1, v2) / dot_v2v2(v2, v2);
+
+	c[0] = mul * v2[0];
+	c[1] = mul * v2[1];
+}
+
+/* Project v1 on v2 */
 void project_v3_v3v3(float c[3], const float v1[3], const float v2[3])
 {
 	float mul;
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index 9718b37ee8a..b0666d2ed5d 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -429,6 +429,11 @@ MINLINE int is_one_v3(const float *v)
 	return (v[0] == 1 && v[1] == 1 && v[2] == 1);
 }
 
+MINLINE int equals_v2v2(const float *v1, const float *v2)
+{
+	return ((v1[0]==v2[0]) && (v1[1]==v2[1]));
+}
+
 MINLINE int equals_v3v3(const float *v1, const float *v2)
 {
 	return ((v1[0]==v2[0]) && (v1[1]==v2[1]) && (v1[2]==v2[2]));