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/blender/blenkernel/intern/editmesh_bvh.c | |
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/blender/blenkernel/intern/editmesh_bvh.c')
-rw-r--r-- | source/blender/blenkernel/intern/editmesh_bvh.c | 152 |
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 |