[Bf-blender-cvs] [179a2e1] master: Use BVH-overlap for mesh self-intersection display
Campbell Barton
noreply at git.blender.org
Thu Aug 20 11:20:24 CEST 2015
Commit: 179a2e1b98b048e5b9f607eee23f94f22d8234aa
Author: Campbell Barton
Date: Thu Aug 20 19:09:20 2015 +1000
Branches: master
https://developer.blender.org/rB179a2e1b98b048e5b9f607eee23f94f22d8234aa
Use BVH-overlap for mesh self-intersection display
Add BKE_bmbvh_overlap, remove BKE_bmbvh_find_face_segment
===================================================================
M source/blender/blenkernel/BKE_editmesh_bvh.h
M source/blender/blenkernel/intern/editderivedmesh.c
M source/blender/blenkernel/intern/editmesh_bvh.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_editmesh_bvh.h b/source/blender/blenkernel/BKE_editmesh_bvh.h
index 3736eff..b21c5db 100644
--- a/source/blender/blenkernel/BKE_editmesh_bvh.h
+++ b/source/blender/blenkernel/BKE_editmesh_bvh.h
@@ -66,12 +66,11 @@ struct BMFace *BKE_bmbvh_ray_cast_filter(
float *r_dist, float r_hitout[3], float r_cagehit[3],
BMBVHTree_FaceFilter filter, void *filter_cb);
-/* find a face intersecting a segment (but not apart of the segment) */
-struct BMFace *BKE_bmbvh_find_face_segment(BMBVHTree *tree, const float co_a[3], const float co_b[3],
- float *r_fac, float r_hitout[3], float r_cagehit[3]);
/* find a vert closest to co in a sphere of radius dist_max */
struct BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *tree, const float co[3], const float dist_max);
+struct BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a, const BMBVHTree *bmtree_b, unsigned int *r_overlap_tot);
+
/* BKE_bmbvh_new flag parameter */
enum {
BMBVH_RETURN_ORIG = (1 << 0), /* use with 'cos_cage', returns hits in relation to original geometry */
diff --git a/source/blender/blenkernel/intern/editderivedmesh.c b/source/blender/blenkernel/intern/editderivedmesh.c
index 8f251b7..8158411 100644
--- a/source/blender/blenkernel/intern/editderivedmesh.c
+++ b/source/blender/blenkernel/intern/editderivedmesh.c
@@ -2125,15 +2125,17 @@ static void statvis_calc_intersect(
/* result */
unsigned char (*r_face_colors)[4])
{
- BMIter iter;
BMesh *bm = em->bm;
- BMEdge *e;
- int index;
+ int i;
/* fallback */
// const char col_fallback[4] = {64, 64, 64, 255};
+ float fcol[3];
+ unsigned char col[3];
struct BMBVHTree *bmtree;
+ BVHTreeOverlap *overlap;
+ unsigned int overlap_len;
memset(r_face_colors, 64, sizeof(int) * em->bm->totface);
@@ -2144,46 +2146,30 @@ static void statvis_calc_intersect(
bmtree = BKE_bmbvh_new_from_editmesh(em, 0, vertexCos, false);
- BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
- BMFace *f_hit;
- float cos[2][3];
- float cos_mid[3];
- float ray_no[3];
+ overlap = BKE_bmbvh_overlap(bmtree, bmtree, &overlap_len);
- if (e->l == NULL)
- continue;
+ /* same for all faces */
+ weight_to_rgb(fcol, 1.0f);
+ rgb_float_to_uchar(col, fcol);
- if (vertexCos) {
- copy_v3_v3(cos[0], vertexCos[BM_elem_index_get(e->v1)]);
- copy_v3_v3(cos[1], vertexCos[BM_elem_index_get(e->v2)]);
- }
- else {
- copy_v3_v3(cos[0], e->v1->co);
- copy_v3_v3(cos[1], e->v2->co);
- }
-
- mid_v3_v3v3(cos_mid, cos[0], cos[1]);
- sub_v3_v3v3(ray_no, cos[1], cos[0]);
-
- f_hit = BKE_bmbvh_find_face_segment(bmtree, cos[0], cos[1],
- NULL, NULL, NULL);
+ if (overlap) {
+ for (i = 0; i < overlap_len; i++) {
+ BMFace *f_hit_pair[2] = {
+ em->looptris[overlap[i].indexA][0]->f,
+ em->looptris[overlap[i].indexB][0]->f,
+ };
+ int j;
- if (f_hit) {
- BMLoop *l_iter, *l_first;
- float fcol[3];
+ for (j = 0; j < 2; j++) {
+ BMFace *f_hit = f_hit_pair[j];
+ int index;
- index = BM_elem_index_get(f_hit);
- weight_to_rgb(fcol, 1.0f);
- rgb_float_to_uchar(r_face_colors[index], fcol);
+ index = BM_elem_index_get(f_hit);
- l_iter = l_first = e->l;
- do {
- index = BM_elem_index_get(l_iter->f);
- weight_to_rgb(fcol, 1.0f);
- rgb_float_to_uchar(r_face_colors[index], fcol);
- } while ((l_iter = l_iter->radial_next) != l_first);
+ copy_v3_v3_char((char *)r_face_colors[index], (const char *)col);
+ }
}
-
+ MEM_freeN(overlap);
}
BKE_bmbvh_free(bmtree);
diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c
index 5f2660b..f46e158 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
More information about the Bf-blender-cvs
mailing list