From 5b6deea647572539fd23902559fed091f6603ffb Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 20 Aug 2015 12:14:02 +1000 Subject: Transform: Use BVH for volume-snap (optimization) Was performing ray-tri intersection checks on all faces. Note, this isn't using isect_ray_tri_threshold_v3 which was used to prevent ray-casts slipping through between faces. Instead we'll move to using watertight intersections by default. --- source/blender/editors/transform/transform_snap.c | 124 ++++++++++++---------- 1 file changed, 70 insertions(+), 54 deletions(-) (limited to 'source/blender/editors/transform/transform_snap.c') diff --git a/source/blender/editors/transform/transform_snap.c b/source/blender/editors/transform/transform_snap.c index 3b488fde2b3..55ac166d861 100644 --- a/source/blender/editors/transform/transform_snap.c +++ b/source/blender/editors/transform/transform_snap.c @@ -2056,21 +2056,62 @@ static void addDepthPeel(ListBase *depth_peels, float depth, float p[3], float n peel->flag = 0; } -static bool peelDerivedMesh(Object *ob, DerivedMesh *dm, float obmat[4][4], - const float ray_start[3], const float ray_normal[3], const float UNUSED(mval[2]), - ListBase *depth_peels) +struct PeelRayCast_Data { + BVHTreeFromMesh bvhdata; + + /* internal vars for adding peel */ + Object *ob; + const float (*obmat)[4]; + const float (*timat)[3]; + + const float *ray_start; /* globalspace */ + + const MLoopTri *looptri; + const float (*polynors)[3]; /* optional, can be NULL */ + + /* output list */ + ListBase *depth_peels; +}; + +static void peelRayCast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + struct PeelRayCast_Data *data = userdata; + + data->bvhdata.raycast_callback(&data->bvhdata, index, ray, hit); + + if (hit->index != -1) { + /* get all values in worldspace */ + float location[3], normal[3]; + float depth; + + /* worldspace location */ + mul_v3_m4v3(location, (float (*)[4])data->obmat, hit->co); + depth = len_v3v3(location, data->ray_start); + + /* worldspace normal */ + copy_v3_v3(normal, data->polynors ? data->polynors[data->looptri[hit->index].poly] : hit->no); + mul_m3_v3((float (*)[3])data->timat, normal); + normalize_v3(normal); + + addDepthPeel(data->depth_peels, depth, location, normal, data->ob); + } +} + +static bool peelDerivedMesh( + Object *ob, DerivedMesh *dm, BMEditMesh *em, float obmat[4][4], + const float ray_start[3], const float ray_normal[3], const float UNUSED(mval[2]), + ListBase *depth_peels) { bool retval = false; int totvert = dm->getNumVerts(dm); if (totvert > 0) { const MLoopTri *looptri = dm->getLoopTriArray(dm); - const MLoop *mloop = dm->getLoopArray(dm); - int looptri_num = dm->getNumLoopTri(dm); + const int looptri_num = dm->getNumLoopTri(dm); float imat[4][4]; float timat[3][3]; /* transpose inverse matrix for normals */ float ray_start_local[3], ray_normal_local[3]; - int test = 1; + bool test = true; invert_m4_m4(imat, obmat); @@ -2087,51 +2128,26 @@ static bool peelDerivedMesh(Object *ob, DerivedMesh *dm, float obmat[4][4], test = BKE_boundbox_ray_hit_check(bb, ray_start_local, ray_normal_local, NULL); } - if (test == 1) { - const MLoopTri *lt; - MVert *verts = dm->getVertArray(dm); - float (*polynors)[3] = dm->getPolyDataArray(dm, CD_NORMAL); - int i; - - for (i = 0, lt = looptri; i < looptri_num; i++, lt++) { - const unsigned int vtri[3] = {mloop[lt->tri[0]].v, mloop[lt->tri[1]].v, mloop[lt->tri[2]].v}; - float lambda; - int result; - - - result = isect_ray_tri_threshold_v3( - ray_start_local, ray_normal_local, - verts[vtri[0]].co, verts[vtri[1]].co, verts[vtri[2]].co, - &lambda, NULL, 0.001); - - if (result) { - float location[3], normal[3]; - float intersect[3]; - float new_depth; - - copy_v3_v3(intersect, ray_normal_local); - mul_v3_fl(intersect, lambda); - add_v3_v3(intersect, ray_start_local); - - copy_v3_v3(location, intersect); - - if (polynors) { - copy_v3_v3(normal, polynors[lt->poly]); - } - else { - normal_tri_v3(normal, verts[vtri[0]].co, verts[vtri[1]].co, verts[vtri[2]].co); - } - - mul_m4_v3(obmat, location); - - new_depth = len_v3v3(location, ray_start); - - mul_m3_v3(timat, normal); - normalize_v3(normal); - - addDepthPeel(depth_peels, new_depth, location, normal, ob); - } + if (test == true) { + struct PeelRayCast_Data data; + + data.bvhdata.em_evil = em; + bvhtree_from_mesh_looptri(&data.bvhdata, dm, 0.0f, 4, 6); + + if (data.bvhdata.tree != NULL) { + data.ob = ob; + data.obmat = obmat; + data.timat = timat; + data.ray_start = ray_start; + data.looptri = looptri; + data.polynors = dm->getPolyDataArray(dm, CD_NORMAL); /* can be NULL */ + data.depth_peels = depth_peels; + + BLI_bvhtree_ray_cast_all(data.bvhdata.tree, ray_start_local, ray_normal_local, 0.0f, + peelRayCast_cb, &data); } + + free_bvhtree_from_mesh(&data.bvhdata); } } @@ -2168,13 +2184,13 @@ static bool peelObjects(Scene *scene, View3D *v3d, ARegion *ar, Object *obedit, if (dob != obedit) { dm = mesh_get_derived_final(scene, dob, CD_MASK_BAREMESH); - val = peelDerivedMesh(dob, dm, dob->obmat, ray_start, ray_normal, mval, depth_peels); + val = peelDerivedMesh(dob, dm, NULL, dob->obmat, ray_start, ray_normal, mval, depth_peels); } else { em = BKE_editmesh_from_object(dob); dm = editbmesh_get_derived_cage(scene, obedit, em, CD_MASK_BAREMESH); - val = peelDerivedMesh(dob, dm, dob->obmat, ray_start, ray_normal, mval, depth_peels); + val = peelDerivedMesh(dob, dm, em, dob->obmat, ray_start, ray_normal, mval, depth_peels); } retval = retval || val; @@ -2192,14 +2208,14 @@ static bool peelObjects(Scene *scene, View3D *v3d, ARegion *ar, Object *obedit, if (ob != obedit && ((mode == SNAP_NOT_SELECTED && (base->flag & (SELECT | BA_WAS_SEL)) == 0) || ELEM(mode, SNAP_ALL, SNAP_NOT_OBEDIT))) { DerivedMesh *dm = mesh_get_derived_final(scene, ob, CD_MASK_BAREMESH); - val = peelDerivedMesh(ob, dm, ob->obmat, ray_start, ray_normal, mval, depth_peels); + val = peelDerivedMesh(ob, dm, NULL, ob->obmat, ray_start, ray_normal, mval, depth_peels); dm->release(dm); } else if (ob == obedit && mode != SNAP_NOT_OBEDIT) { BMEditMesh *em = BKE_editmesh_from_object(ob); DerivedMesh *dm = editbmesh_get_derived_cage(scene, obedit, em, CD_MASK_BAREMESH); - val = peelDerivedMesh(ob, dm, ob->obmat, ray_start, ray_normal, mval, depth_peels); + val = peelDerivedMesh(ob, dm, NULL, ob->obmat, ray_start, ray_normal, mval, depth_peels); dm->release(dm); } -- cgit v1.2.3