diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-08-20 12:09:20 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-08-20 12:13:14 +0300 |
commit | 179a2e1b98b048e5b9f607eee23f94f22d8234aa (patch) | |
tree | da0eb4600bbcb20e1961a96e6469e495bb998477 /source | |
parent | 66365589ff4c18ad06f6ff268351773833f02bea (diff) |
Use BVH-overlap for mesh self-intersection display
Add BKE_bmbvh_overlap, remove BKE_bmbvh_find_face_segment
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/BKE_editmesh_bvh.h | 5 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/editderivedmesh.c | 60 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/editmesh_bvh.c | 152 |
3 files changed, 81 insertions, 136 deletions
diff --git a/source/blender/blenkernel/BKE_editmesh_bvh.h b/source/blender/blenkernel/BKE_editmesh_bvh.h index 3736efff146..b21c5db2118 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 8f251b774cf..8158411c2e4 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 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 |