Use BVH-overlap for mesh self-intersection display

Add BKE_bmbvh_overlap, remove BKE_bmbvh_find_face_segment

1 files changed, 56 insertions, 96 deletions

diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c
index 5f2660b5365..f46e158f833 100644
--- a/source/blender/blenkernel/intern/editmesh_bvh.c
+++ b/source/blender/blenkernel/intern/editmesh_bvh.c
@@ -372,102 +372,6 @@ BMFace *BKE_bmbvh_ray_cast_filter(
 	return NULL;
 }
 
-/* -------------------------------------------------------------------- */
-/* BKE_bmbvh_find_face_segment */
-
-struct SegmentUserData {
-	/* from the bmtree */
-	const BMLoop *(*looptris)[3];
-	const float (*cos_cage)[3];
-
-	/* from the hit */
-	float uv[2];
-	const float *co_a, *co_b;
-};
-
-static void bmbvh_find_face_segment_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
-{
-	struct SegmentUserData *bmcb_data = userdata;
-	const BMLoop **ltri = bmcb_data->looptris[index];
-	float dist, uv[2];
-	const float *tri_cos[3];
-
-	bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
-
-	if (equals_v3v3(bmcb_data->co_a, tri_cos[0]) ||
-	    equals_v3v3(bmcb_data->co_a, tri_cos[1]) ||
-	    equals_v3v3(bmcb_data->co_a, tri_cos[2]) ||
-
-	    equals_v3v3(bmcb_data->co_b, tri_cos[0]) ||
-	    equals_v3v3(bmcb_data->co_b, tri_cos[1]) ||
-	    equals_v3v3(bmcb_data->co_b, tri_cos[2]))
-	{
-		return;
-	}
-
-	if (isect_ray_tri_v3(ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv) &&
-	    (dist < hit->dist))
-	{
-		hit->dist = dist;
-		hit->index = index;
-
-		copy_v3_v3(hit->no, ltri[0]->f->no);
-
-		madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
-
-		copy_v2_v2(bmcb_data->uv, uv);
-	}
-}
-
-BMFace *BKE_bmbvh_find_face_segment(BMBVHTree *bmtree, const float co_a[3], const float co_b[3],
-                                    float *r_fac, float r_hitout[3], float r_cagehit[3])
-{
-	BVHTreeRayHit hit;
-	struct SegmentUserData bmcb_data;
-	const float dist = len_v3v3(co_a, co_b);
-	float dir[3];
-
-	if (bmtree->cos_cage) BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
-
-	sub_v3_v3v3(dir, co_b, co_a);
-
-	hit.dist = dist;
-	hit.index = -1;
-
-	/* ok to leave 'uv' uninitialized */
-	bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
-	bmcb_data.cos_cage = (const float (*)[3])bmtree->cos_cage;
-	bmcb_data.co_a = co_a;
-	bmcb_data.co_b = co_b;
-
-	BLI_bvhtree_ray_cast(bmtree->tree, co_a, dir, 0.0f, &hit, bmbvh_find_face_segment_cb, &bmcb_data);
-	if (hit.index != -1 && hit.dist != dist) {
-		/* duplicate of BKE_bmbvh_ray_cast() */
-		if (r_hitout) {
-			if (bmtree->flag & BMBVH_RETURN_ORIG) {
-				BMLoop **ltri = bmtree->looptris[hit.index];
-				interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, bmcb_data.uv);
-			}
-			else {
-				copy_v3_v3(r_hitout, hit.co);
-			}
-
-			if (r_cagehit) {
-				copy_v3_v3(r_cagehit, hit.co);
-			}
-		}
-		/* end duplicate */
-
-		if (r_fac) {
-			*r_fac = hit.dist / dist;
-		}
-
-		return bmtree->looptris[hit.index][0]->f;
-	}
-
-	return NULL;
-}
-
 
 /* -------------------------------------------------------------------- */
 /* BKE_bmbvh_find_vert_closest */
@@ -529,3 +433,59 @@ BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const
 
 	return NULL;
 }
+
+/* -------------------------------------------------------------------- */
+/* BKE_bmbvh_overlap */
+
+struct BMBVHTree_OverlapData {
+	const BMBVHTree *tree_pair[2];
+	float epsilon;
+};
+
+static bool bmbvh_overlap_cb(void *userdata, int index_a, int index_b, unsigned int UNUSED(thread))
+{
+	struct BMBVHTree_OverlapData *data = userdata;
+	const BMBVHTree *bmtree_a = data->tree_pair[0];
+	const BMBVHTree *bmtree_b = data->tree_pair[1];
+
+	BMLoop **tri_a = bmtree_a->looptris[index_a];
+	BMLoop **tri_b = bmtree_b->looptris[index_b];
+	const float *tri_a_co[3] = {tri_a[0]->v->co, tri_a[1]->v->co, tri_a[2]->v->co};
+	const float *tri_b_co[3] = {tri_b[0]->v->co, tri_b[1]->v->co, tri_b[2]->v->co};
+	float ix_pair[2][3];
+	int verts_shared = 0;
+
+	if (bmtree_a->looptris == bmtree_b->looptris) {
+		if (UNLIKELY(tri_a[0]->f == tri_b[0]->f)) {
+			return false;
+		}
+
+		verts_shared = (
+		        ELEM(tri_a_co[0], UNPACK3(tri_b_co)) +
+		        ELEM(tri_a_co[1], UNPACK3(tri_b_co)) +
+		        ELEM(tri_a_co[2], UNPACK3(tri_b_co)));
+
+		/* if 2 points are shared, bail out */
+		if (verts_shared >= 2) {
+			return false;
+		}
+	}
+
+	return (isect_tri_tri_epsilon_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1], data->epsilon) &&
+	        /* if we share a vertex, check the intersection isn't a 'point' */
+	        ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon)));
+}
+
+/**
+ * Overlap indices reference the looptri's
+ */
+BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a, const BMBVHTree *bmtree_b, unsigned int *r_overlap_tot)
+{
+	struct BMBVHTree_OverlapData data;
+
+	data.tree_pair[0] = bmtree_a;
+	data.tree_pair[1] = bmtree_b;
+	data.epsilon = max_ff(BLI_bvhtree_getepsilon(bmtree_a->tree), BLI_bvhtree_getepsilon(bmtree_b->tree));
+
+	return BLI_bvhtree_overlap(bmtree_a->tree, bmtree_b->tree, r_overlap_tot, bmbvh_overlap_cb, &data);
+}
\ No newline at end of file