[Bf-blender-cvs] [9519afd] soc-2016-uv_tools: Working intersection test

Phil Gosch noreply at git.blender.org
Tue Jun 28 13:09:53 CEST 2016


Commit: 9519afdec75c2d23530936ea665e00b377991ef7
Author: Phil Gosch
Date:   Tue Jun 28 13:05:48 2016 +0200
Branches: soc-2016-uv_tools
https://developer.blender.org/rB9519afdec75c2d23530936ea665e00b377991ef7

Working intersection test

Wrote my own intersection function for line segments, includes taking care of float precision issues (especially important when checking for parallel lines)

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

M	source/blender/editors/uvedit/uvedit_parametrizer.c

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

diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c
index f20fa30..8ef36b0 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.c
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.c
@@ -587,6 +587,26 @@ static PBool p_intersect_line_2d(float *v1, float *v2, float *v3, float *v4, flo
 	return P_TRUE;
 }
 
+static PBool p_intersect_line_segments_2d(float *a, float *b, float *c, float *d)
+{
+	float D = (b[0] - a[0]) * (d[1] - c[1]) - (b[1] - a[1]) * (d[0] - c[0]);
+
+	if (compare_ff(D, 0.0f, FLT_EPSILON)) {
+		/* Line segments are parallel */
+		return P_FALSE;
+	}
+
+	float r = ((a[1] - c[1]) * (d[0] - c[0]) - (a[0] - c[0]) * (d[1] - c[1])) / D;
+	float s = ((a[1] - c[1]) * (b[0] - a[0]) - (a[0] - c[0]) * (b[1] - a[1])) / D;
+
+	if ((-FLT_EPSILON <= r <= (1.0f + FLT_EPSILON)) && (-FLT_EPSILON <= s <= (1.0f + FLT_EPSILON))) {
+		/* ToDo (SaphireS): fill isect with intersection data ?*/
+		return P_TRUE;
+	}
+
+	return P_FALSE;
+}
+
 /* Topological Utilities */
 
 static PEdge *p_wheel_edge_next(PEdge *e)
@@ -4682,35 +4702,29 @@ void p_convex_hull_delete(PConvexHull *c_hull)
 
 bool p_convex_hull_intersect(PConvexHull *chull_a, PConvexHull *chull_b)
 {
-	printf("reached p_chart_intersect()\n");
-
+	/* Preliminary bounds check */
 	if (chull_a->min_v[0] > chull_b->max_v[0] ||
 		chull_a->max_v[0] < chull_b->min_v[0] ||
 		chull_a->min_v[1] > chull_b->max_v[1] ||
 		chull_a->max_v[1] < chull_b->min_v[1]) {
-		printf("no overlapping UVs found - bounds don't overlap\n");
 		return false;
 	}
 	
-	
-
 	PEdge *e1, *e2;
 	int i, j;
-	float isec;
 
+	/* Check edges for intersctions */
 	for (i = 0; i < chull_a->nverts; i++) {
 		for (j = 0; j < chull_b->nverts; j++) {
-			if (p_intersect_line_2d(chull_a->h_verts[i],
-									chull_a->h_verts[i++],
-									chull_b->h_verts[j],
-									chull_b->h_verts[j++],
-									&isec)) {
-				printf("Overlapping UVs found\n");
+			if (p_intersect_line_segments_2d(chull_a->h_verts[i]->uv,
+									chull_a->h_verts[i+1]->uv,
+									chull_b->h_verts[j]->uv,
+									chull_b->h_verts[j+1]->uv)) {
 				return true;
 			}
 		}
 	}
-	printf("no overlapping UVs found - intersection tests negative\n");
+
 	return false;
 }




More information about the Bf-blender-cvs mailing list