[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