code cleanup: spelling
[blender.git] / source / blender / blenkernel / intern / bvhutils.c
index 4cade876d09aae6c4d36cee4fd71aa83b44cb56d..dba7a291a460b8e510e9e9c9a25cde57a23aa4c4 100644 (file)
 
 #include "BLI_utildefines.h"
 #include "BLI_linklist.h"
+#include "BLI_math.h"
 
 #include "BKE_DerivedMesh.h"
-#include "BKE_tessmesh.h"
+#include "BKE_editmesh.h"
 
-#include "BLI_math.h"
 #include "MEM_guardedalloc.h"
 
 /* Math stuff for ray casting on mesh faces and for nearest surface */
@@ -51,7 +51,7 @@ float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_d
 {
        float dist;
 
-       if(isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
+       if (isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
                return dist;
 
        return FLT_MAX;
@@ -101,12 +101,12 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
        sub_v3_v3v3(e1, v2, v0);
        
        A00 = dot_v3v3(e0, e0);
-       A01 = dot_v3v3(e0, e1 );
-       A11 = dot_v3v3(e1, e1 );
-       B0 = dot_v3v3(diff, e0 );
-       B1 = dot_v3v3(diff, e1 );
-       C = dot_v3v3(diff, diff );
-       Det = fabs( A00 * A11 - A01 * A01 );
+       A01 = dot_v3v3(e0, e1);
+       A11 = dot_v3v3(e1, e1);
+       B0 = dot_v3v3(diff, e0);
+       B1 = dot_v3v3(diff, e1);
+       C = dot_v3v3(diff, diff);
+       Det = fabs(A00 * A11 - A01 * A01);
        S = A01 * B1 - A11 * B0;
        T = A01 * B0 - A00 * B1;
 
@@ -121,8 +121,8 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                                                lv = 1;
                                        }
                                        else {
-                                               if(fabsf(A00) > FLT_EPSILON)
-                                                       S = -B0/A00;
+                                               if (fabsf(A00) > FLT_EPSILON)
+                                                       S = -B0 / A00;
                                                else
                                                        S = 0.0f;
                                                sqrDist = B0 * S + C;
@@ -142,7 +142,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                                                lv = 2;
                                        }
                                        else {
-                                               if(fabsf(A11) > FLT_EPSILON)
+                                               if (fabsf(A11) > FLT_EPSILON)
                                                        T = -B1 / A11;
                                                else
                                                        T = 0.0f;
@@ -164,7 +164,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                                        lv = 2;
                                }
                                else {
-                                       if(fabsf(A11) > FLT_EPSILON)
+                                       if (fabsf(A11) > FLT_EPSILON)
                                                T = -B1 / A11;
                                        else
                                                T = 0.0;
@@ -195,16 +195,16 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                        }
                }
                else { /* Region 0 */
-                       // Minimum at interior lv
+                       /* Minimum at interior lv */
                        float invDet;
-                       if(fabsf(Det) > FLT_EPSILON)
+                       if (fabsf(Det) > FLT_EPSILON)
                                invDet = 1.0f / Det;
                        else
                                invDet = 0.0f;
                        S *= invDet;
                        T *= invDet;
-                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0) +
-                                 T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
+                       sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) +
+                                 T * (A01 * S + A11 * T + 2.0f * B1) + C;
                }
        }
        else {
@@ -213,29 +213,29 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                if (S < 0.0f) { /* Region 2 */
                        tmp0 = A01 + B0;
                        tmp1 = A11 + B1;
-                       if ( tmp1 > tmp0 ) {
+                       if (tmp1 > tmp0) {
                                numer = tmp1 - tmp0;
                                denom = A00 - 2.0f * A01 + A11;
-                               if ( numer >= denom ) {
+                               if (numer >= denom) {
                                        S = 1.0f;
                                        T = 0.0f;
                                        sqrDist = A00 + 2.0f * B0 + C;
                                        lv = 1;
                                }
                                else {
-                                       if(fabsf(denom) > FLT_EPSILON)
+                                       if (fabsf(denom) > FLT_EPSILON)
                                                S = numer / denom;
                                        else
                                                S = 0.0f;
                                        T = 1.0f - S;
-                                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
-                                                 T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
+                                       sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) +
+                                                 T * (A01 * S + A11 * T + 2.0f * B1) + C;
                                        le = 2;
                                }
                        }
                        else {
                                S = 0.0f;
-                               if ( tmp1 <= 0.0f ) {
+                               if (tmp1 <= 0.0f) {
                                        T = 1.0f;
                                        sqrDist = A11 + 2.0f * B1 + C;
                                        lv = 2;
@@ -246,7 +246,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                                        lv = 0;
                                }
                                else {
-                                       if(fabsf(A11) > FLT_EPSILON)
+                                       if (fabsf(A11) > FLT_EPSILON)
                                                T = -B1 / A11;
                                        else
                                                T = 0.0f;
@@ -258,23 +258,23 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                else if (T < 0.0f) { /* Region 6 */
                        tmp0 = A01 + B1;
                        tmp1 = A00 + B0;
-                       if ( tmp1 > tmp0 ) {
+                       if (tmp1 > tmp0) {
                                numer = tmp1 - tmp0;
                                denom = A00 - 2.0f * A01 + A11;
-                               if ( numer >= denom ) {
+                               if (numer >= denom) {
                                        T = 1.0f;
                                        S = 0.0f;
                                        sqrDist = A11 + 2.0f * B1 + C;
                                        lv = 2;
                                }
                                else {
-                                       if(fabsf(denom) > FLT_EPSILON)
+                                       if (fabsf(denom) > FLT_EPSILON)
                                                T = numer / denom;
                                        else
                                                T = 0.0f;
                                        S = 1.0f - T;
-                                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
-                                                 T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
+                                       sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) +
+                                                 T * (A01 * S + A11 * T + 2.0f * B1) + C;
                                        le = 2;
                                }
                        }
@@ -291,7 +291,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                                        lv = 0;
                                }
                                else {
-                                       if(fabsf(A00) > FLT_EPSILON)
+                                       if (fabsf(A00) > FLT_EPSILON)
                                                S = -B0 / A00;
                                        else
                                                S = 0.0f;
@@ -302,7 +302,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                }
                else { /* Region 1 */
                        numer = A11 + B1 - A01 - B0;
-                       if ( numer <= 0.0f ) {
+                       if (numer <= 0.0f) {
                                S = 0.0f;
                                T = 1.0f;
                                sqrDist = A11 + 2.0f * B1 + C;
@@ -310,28 +310,28 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                        }
                        else {
                                denom = A00 - 2.0f * A01 + A11;
-                               if ( numer >= denom ) {
+                               if (numer >= denom) {
                                        S = 1.0f;
                                        T = 0.0f;
                                        sqrDist = A00 + 2.0f * B0 + C;
                                        lv = 1;
                                }
                                else {
-                                       if(fabsf(denom) > FLT_EPSILON)
+                                       if (fabsf(denom) > FLT_EPSILON)
                                                S = numer / denom;
                                        else
                                                S = 0.0f;
                                        T = 1.0f - S;
-                                       sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
-                                                 T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
+                                       sqrDist = S * (A00 * S + A01 * T + 2.0f * B0) +
+                                                 T * (A01 * S + A11 * T + 2.0f * B1) + C;
                                        le = 2;
                                }
                        }
                }
        }
 
-       // Account for numerical round-off error
-       if ( sqrDist < FLT_EPSILON )
+       /* Account for numerical round-off error */
+       if (sqrDist < FLT_EPSILON)
                sqrDist = 0.0f;
        
        {
@@ -345,7 +345,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                add_v3_v3v3(z, z, y);
                //sub_v3_v3v3(d, p, z);
                copy_v3_v3(nearest, z);
-               // d = p - ( v0 + S * e0 + T * e1 );
+               //d = p - ( v0 + S * e0 + T * e1 );
        }
        *v = lv;
        *e = le;
@@ -355,26 +355,25 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
 
 
 /*
- * BVH from meshs callbacks
+ * BVH from meshes callbacks
  */
 
-// Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
-// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
+/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
 static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 {
-       const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
-       MVert *vert     = data->vert;
+       const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
+       MVert *vert = data->vert;
        MFace *face = data->face + index;
 
        float *t0, *t1, *t2, *t3;
-       t0 = vert[ face->v1 ].co;
-       t1 = vert[ face->v2 ].co;
-       t2 = vert[ face->v3 ].co;
-       t3 = face->v4 ? vert[ face->v4].co : NULL;
+       t0 = vert[face->v1].co;
+       t1 = vert[face->v2].co;
+       t2 = vert[face->v3].co;
+       t3 = face->v4 ? vert[face->v4].co : NULL;
 
        
-       do
-       {       
+       do {
                float nearest_tmp[3], dist;
                int vertex, edge;
                
@@ -383,35 +382,62 @@ static void mesh_faces_nearest_point(void *userdata, int index, const float co[3
                        nearest->index = index;
                        nearest->dist = dist;
                        copy_v3_v3(nearest->co, nearest_tmp);
-                       normal_tri_v3( nearest->no,t0, t1, t2);
+                       normal_tri_v3(nearest->no, t0, t1, t2);
+
+                       if (t1 == vert[face->v3].co)
+                               nearest->flags |= BVH_ONQUAD;
                }
 
                t1 = t2;
                t2 = t3;
                t3 = NULL;
 
-       } while(t2);
+       } while (t2);
 }
+/* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
+static void editmesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
+{
+       const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
+       BMEditMesh *em = data->em_evil;
+       const BMLoop **ltri = (const BMLoop **)em->looptris[index];
+
+       float *t0, *t1, *t2;
+       t0 = ltri[0]->v->co;
+       t1 = ltri[1]->v->co;
+       t2 = ltri[2]->v->co;
 
-// Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
-// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
+       {
+               float nearest_tmp[3], dist;
+               int vertex, edge;
+
+               dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, nearest_tmp);
+               if (dist < nearest->dist) {
+                       nearest->index = index;
+                       nearest->dist = dist;
+                       copy_v3_v3(nearest->co, nearest_tmp);
+                       normal_tri_v3(nearest->no, t0, t1, t2);
+               }
+       }
+}
+
+/* Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
 static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
 {
-       const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
-       MVert *vert     = data->vert;
+       const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
+       MVert *vert = data->vert;
        MFace *face = data->face + index;
 
        float *t0, *t1, *t2, *t3;
-       t0 = vert[ face->v1 ].co;
-       t1 = vert[ face->v2 ].co;
-       t2 = vert[ face->v3 ].co;
-       t3 = face->v4 ? vert[ face->v4].co : NULL;
+       t0 = vert[face->v1].co;
+       t1 = vert[face->v2].co;
+       t2 = vert[face->v3].co;
+       t3 = face->v4 ? vert[face->v4].co : NULL;
 
        
-       do
-       {       
+       do {
                float dist;
-               if(data->sphere_radius == 0.0f)
+               if (data->sphere_radius == 0.0f)
                        dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
                else
                        dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
@@ -421,28 +447,60 @@ static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *r
                        hit->dist = dist;
                        madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
 
-                       normal_tri_v3( hit->no,t0, t1, t2);
+                       normal_tri_v3(hit->no, t0, t1, t2);
+
+                       if (t1 == vert[face->v3].co)
+                               hit->flags |= BVH_ONQUAD;
                }
 
                t1 = t2;
                t2 = t3;
                t3 = NULL;
 
-       } while(t2);
+       } while (t2);
+}
+/* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
+static void editmesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+       const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
+       BMEditMesh *em = data->em_evil;
+       const BMLoop **ltri = (const BMLoop **)em->looptris[index];
+
+       float *t0, *t1, *t2;
+       t0 = ltri[0]->v->co;
+       t1 = ltri[1]->v->co;
+       t2 = ltri[2]->v->co;
+
+
+       {
+               float dist;
+               if (data->sphere_radius == 0.0f)
+                       dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
+               else
+                       dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
+
+               if (dist >= 0 && dist < hit->dist) {
+                       hit->index = index;
+                       hit->dist = dist;
+                       madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
+
+                       normal_tri_v3(hit->no, t0, t1, t2);
+               }
+       }
 }
 
-// Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges.
-// userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
+/* Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges.
+ * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
 static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 {
-       const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
-       MVert *vert     = data->vert;
+       const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
+       MVert *vert = data->vert;
        MEdge *edge = data->edge + index;
        float nearest_tmp[3], dist;
 
        float *t0, *t1;
-       t0 = vert[ edge->v1 ].co;
-       t1 = vert[ edge->v2 ].co;
+       t0 = vert[edge->v1].co;
+       t1 = vert[edge->v2].co;
 
        closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
        dist = len_squared_v3v3(nearest_tmp, co);
@@ -459,16 +517,16 @@ static void mesh_edges_nearest_point(void *userdata, int index, const float co[3
 /*
  * BVH builders
  */
-// Builds a bvh tree.. where nodes are the vertexs of the given mesh
-BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
+/* Builds a bvh tree.. where nodes are the vertexs of the given mesh */
+BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
 {
-       BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_VERTICES);
+       BVHTree *tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_VERTICES);
 
-       //Not in cache
-       if(tree == NULL) {
+       /* Not in cache */
+       if (tree == NULL) {
                int i;
-               int numVerts= mesh->getNumVerts(mesh);
-               MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
+               int numVerts = dm->getNumVerts(dm);
+               MVert *vert = dm->getVertDataArray(dm, CD_MVERT);
 
                if (vert != NULL) {
                        tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
@@ -480,9 +538,9 @@ BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float
 
                                BLI_bvhtree_balance(tree);
 
-                               //Save on cache for later use
+                               /* Save on cache for later use */
 //                             printf("BVHTree built and saved on cache\n");
-                               bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_VERTICES);
+                               bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_VERTICES);
                        }
                }
        }
@@ -491,21 +549,20 @@ BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float
        }
 
 
-       //Setup BVHTreeFromMesh
+       /* Setup BVHTreeFromMesh */
        memset(data, 0, sizeof(*data));
        data->tree = tree;
 
        if (data->tree) {
-               data->cached = TRUE;
+               data->cached = true;
 
-               //a NULL nearest callback works fine
-               //remeber the min distance to point is the same as the min distance to BV of point
+               /a NULL nearest callback works fine
+                * remember the min distance to point is the same as the min distance to BV of point */
                data->nearest_callback = NULL;
                data->raycast_callback = NULL;
 
-               data->mesh = mesh;
-               data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
-               data->face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
+               data->vert = dm->getVertDataArray(dm, CD_MVERT);
+               data->face = dm->getTessFaceDataArray(dm, CD_MFACE);
 
                data->sphere_radius = epsilon;
        }
@@ -513,98 +570,109 @@ BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float
        return data->tree;
 }
 
-// Builds a bvh tree.. where nodes are the faces of the given mesh.
-BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
+/* Builds a bvh tree.. where nodes are the faces of the given dm. */
+BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
 {
-       BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_FACES);
+       BVHTree *tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_FACES);
+       BMEditMesh *em = data->em_evil;
 
-       //Not in cache
+       /* Not in cache */
        if (tree == NULL) {
                int i;
-               int numFaces= mesh->getNumTessFaces(mesh);
+               int numFaces;
 
-               /* BMESH spesific check that we have tessfaces,
-                * we _could_ tesselate here but rather not - campbell
+               /* BMESH specific check that we have tessfaces,
+                * we _could_ tessellate here but rather not - campbell
                 *
                 * this assert checks we have tessfaces,
                 * if not caller should use DM_ensure_tessface() */
-               BLI_assert(!(numFaces == 0 && mesh->getNumPolys(mesh) != 0));
+               if (em) {
+                       numFaces = em->tottri;
+               }
+               else {
+                       numFaces = dm->getNumTessFaces(dm);
+                       BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0));
+               }
 
-               if(numFaces != 0) {
+               if (numFaces != 0) {
                        /* Create a bvh-tree of the given target */
+                       // printf("%s: building BVH, total=%d\n", __func__, numFaces);
                        tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis);
                        if (tree != NULL) {
-                               BMEditMesh *em= data->em_evil;
-                               if(em) {
+                               if (em) {
+                                       const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
+
+                                       /* avoid double-up on face searches for quads-ngons */
+                                       bool insert_prev = false;
+                                       BMFace *f_prev = NULL;
+
                                        /* data->em_evil is only set for snapping, and only for the mesh of the object
                                         * which is currently open in edit mode. When set, the bvhtree should not contain
                                         * faces that will interfere with snapping (e.g. faces that are hidden/selected
                                         * or faces that have selected verts).*/
 
-                                       /* XXX, for snap only, em & dm are assumed to be aligned, since dm is the em's cage */
-
                                        /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
                                         * and/or selected. Even if the faces themselves are not selected for the snapped
-                                        * transform, having a vertex selected means the face (and thus it's tesselated
+                                        * transform, having a vertex selected means the face (and thus it's tessellated
                                         * triangles) will be moving and will not be a good snap targets.*/
                                        for (i = 0; i < em->tottri; i++) {
-                                               BMLoop **tri = em->looptris[i];
-                                               BMFace *f;
-                                               BMVert *v;
-                                               BMIter iter;
-                                               int insert;
-
-                                               /* Each loop of the triangle points back to the BMFace it was tesselated from.
-                                                * All three should point to the same face, so just use the face from the first
-                                                * loop.*/
-                                               f = tri[0]->f;
-
-                                               /* If the looptris is ordered such that all triangles tesselated from a single
-                                                * faces are consecutive elements in the array, then we could speed up the tests
-                                                * below by using the insert value from the previous iteration.*/
-
-                                               /*Start with the assumption the triangle should be included for snapping.*/
-                                               insert = 1;
-
-                                               if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
-                                                       /* Don't insert triangles tesselated from faces that are hidden
-                                                        * or selected*/
-                                                       insert = 0;
+                                               const BMLoop **ltri = looptris[i];
+                                               BMFace *f = ltri[0]->f;
+                                               bool insert;
+
+                                               /* Start with the assumption the triangle should be included for snapping. */
+                                               if (f == f_prev) {
+                                                       insert = insert_prev;
                                                }
                                                else {
-                                                       BM_ITER(v, &iter, em->bm, BM_VERTS_OF_FACE, f) {
-                                                               if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
-                                                                       /* Don't insert triangles tesselated from faces that have
-                                                                        * any selected verts.*/
-                                                                       insert = 0;
-                                                               }
+                                                       if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
+                                                               /* Don't insert triangles tessellated from faces that are hidden
+                                                                * or selected*/
+                                                               insert = false;
+                                                       }
+                                                       else {
+                                                               BMLoop *l_iter, *l_first;
+                                                               insert = true;
+                                                               l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+                                                               do {
+                                                                       if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
+                                                                               /* Don't insert triangles tessellated from faces that have
+                                                                                * any selected verts.*/
+                                                                               insert = false;
+                                                                               break;
+                                                                       }
+                                                               } while ((l_iter = l_iter->next) != l_first);
                                                        }
+
+                                                       /* skip if face doesn't change */
+                                                       f_prev = f;
+                                                       insert_prev = insert;
                                                }
 
                                                if (insert) {
                                                        /* No reason found to block hit-testing the triangle for snap,
                                                         * so insert it now.*/
-                                                       float co[4][3];
-                                                       copy_v3_v3(co[0], tri[0]->v->co);
-                                                       copy_v3_v3(co[1], tri[1]->v->co);
-                                                       copy_v3_v3(co[2], tri[2]->v->co);
+                                                       float co[3][3];
+                                                       copy_v3_v3(co[0], ltri[0]->v->co);
+                                                       copy_v3_v3(co[1], ltri[1]->v->co);
+                                                       copy_v3_v3(co[2], ltri[2]->v->co);
                                        
                                                        BLI_bvhtree_insert(tree, i, co[0], 3);
                                                }
                                        }
                                }
                                else {
-                                       MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
-                                       MFace *face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
+                                       MVert *vert = dm->getVertDataArray(dm, CD_MVERT);
+                                       MFace *face = dm->getTessFaceDataArray(dm, CD_MFACE);
 
                                        if (vert != NULL && face != NULL) {
-                                               for(i = 0; i < numFaces; i++) {
+                                               for (i = 0; i < numFaces; i++) {
                                                        float co[4][3];
-                                                       copy_v3_v3(co[0], vert[ face[i].v1 ].co);
-                                                       copy_v3_v3(co[1], vert[ face[i].v2 ].co);
-                                                       copy_v3_v3(co[2], vert[ face[i].v3 ].co);
-                                                       if(face[i].v4)
-                                                               copy_v3_v3(co[3], vert[ face[i].v4 ].co);
+                                                       copy_v3_v3(co[0], vert[face[i].v1].co);
+                                                       copy_v3_v3(co[1], vert[face[i].v2].co);
+                                                       copy_v3_v3(co[2], vert[face[i].v3].co);
+                                                       if (face[i].v4)
+                                                               copy_v3_v3(co[3], vert[face[i].v4].co);
                                        
                                                        BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
                                                }
@@ -612,9 +680,9 @@ BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float
                                }
                                BLI_bvhtree_balance(tree);
 
-                               //Save on cache for later use
+                               /* Save on cache for later use */
 //                             printf("BVHTree built and saved on cache\n");
-                               bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_FACES);
+                               bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_FACES);
                        }
                }
        }
@@ -623,19 +691,25 @@ BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float
        }
 
 
-       //Setup BVHTreeFromMesh
+       /* Setup BVHTreeFromMesh */
        memset(data, 0, sizeof(*data));
        data->tree = tree;
+       data->em_evil = em;
 
-       if(data->tree) {
-               data->cached = TRUE;
+       if (data->tree) {
+               data->cached = true;
 
-               data->nearest_callback = mesh_faces_nearest_point;
-               data->raycast_callback = mesh_faces_spherecast;
+               if (em) {
+                       data->nearest_callback = editmesh_faces_nearest_point;
+                       data->raycast_callback = editmesh_faces_spherecast;
+               }
+               else {
+                       data->nearest_callback = mesh_faces_nearest_point;
+                       data->raycast_callback = mesh_faces_spherecast;
 
-               data->mesh = mesh;
-               data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
-               data->face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
+                       data->vert = dm->getVertDataArray(dm, CD_MVERT);
+                       data->face = dm->getTessFaceDataArray(dm, CD_MFACE);
+               }
 
                data->sphere_radius = epsilon;
        }
@@ -643,18 +717,17 @@ BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float
 
 }
 
-// Builds a bvh tree.. where nodes are the faces of the given mesh.
-BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
+/* Builds a bvh tree.. where nodes are the faces of the given dm. */
+BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
 {
-       BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_EDGES);
+       BVHTree *tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_EDGES);
 
-       //Not in cache
-       if(tree == NULL)
-       {
+       /* Not in cache */
+       if (tree == NULL) {
                int i;
-               int numEdges= mesh->getNumEdges(mesh);
-               MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
-               MEdge *edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
+               int numEdges = dm->getNumEdges(dm);
+               MVert *vert = dm->getVertDataArray(dm, CD_MVERT);
+               MEdge *edge = dm->getEdgeDataArray(dm, CD_MEDGE);
 
                if (vert != NULL && edge != NULL) {
                        /* Create a bvh-tree of the given target */
@@ -662,38 +735,36 @@ BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float
                        if (tree != NULL) {
                                for (i = 0; i < numEdges; i++) {
                                        float co[4][3];
-                                       copy_v3_v3(co[0], vert[ edge[i].v1 ].co);
-                                       copy_v3_v3(co[1], vert[ edge[i].v2 ].co);
+                                       copy_v3_v3(co[0], vert[edge[i].v1].co);
+                                       copy_v3_v3(co[1], vert[edge[i].v2].co);
                        
                                        BLI_bvhtree_insert(tree, i, co[0], 2);
                                }
                                BLI_bvhtree_balance(tree);
 
-                               //Save on cache for later use
+                               /* Save on cache for later use */
 //                             printf("BVHTree built and saved on cache\n");
-                               bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_EDGES);
+                               bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_EDGES);
                        }
                }
        }
-       else
-       {
+       else {
 //             printf("BVHTree is already build, using cached tree\n");
        }
 
 
-       //Setup BVHTreeFromMesh
+       /* Setup BVHTreeFromMesh */
        memset(data, 0, sizeof(*data));
        data->tree = tree;
 
-       if(data->tree) {
-               data->cached = TRUE;
+       if (data->tree) {
+               data->cached = true;
 
                data->nearest_callback = mesh_edges_nearest_point;
                data->raycast_callback = NULL;
 
-               data->mesh = mesh;
-               data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
-               data->edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
+               data->vert = dm->getVertDataArray(dm, CD_MVERT);
+               data->edge = dm->getEdgeDataArray(dm, CD_MEDGE);
 
                data->sphere_radius = epsilon;
        }
@@ -701,21 +772,20 @@ BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float
 
 }
 
-// Frees data allocated by a call to bvhtree_from_mesh_*.
+/* Frees data allocated by a call to bvhtree_from_mesh_*. */
 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
 {
-       if(data->tree) {
-               if(!data->cached)
+       if (data->tree) {
+               if (!data->cached)
                        BLI_bvhtree_free(data->tree);
 
-               memset( data, 0, sizeof(*data) );
+               memset(data, 0, sizeof(*data));
        }
 }
 
 
 /* BVHCache */
-typedef struct BVHCacheItem
-{
+typedef struct BVHCacheItem {
        int type;
        BVHTree *tree;
 
@@ -723,11 +793,11 @@ typedef struct BVHCacheItem
 
 static void bvhcacheitem_set_if_match(void *_cached, void *_search)
 {
-       BVHCacheItem * cached = (BVHCacheItem *)_cached;
-       BVHCacheItem * search = (BVHCacheItem *)_search;
+       BVHCacheItem *cached = (BVHCacheItem *)_cached;
+       BVHCacheItem *search = (BVHCacheItem *)_search;
 
-       if(search->type == cached->type) {
-               search->tree = cached->tree;            
+       if (search->type == cached->type) {
+               search->tree = cached->tree;
        }
 } 
 
@@ -745,16 +815,16 @@ void bvhcache_insert(BVHCache *cache, BVHTree *tree, int type)
 {
        BVHCacheItem *item = NULL;
 
-       assert( tree != NULL );
-       assert( bvhcache_find(cache, type) == NULL );
+       assert(tree != NULL);
+       assert(bvhcache_find(cache, type) == NULL);
 
        item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
-       assert( item != NULL );
+       assert(item != NULL);
 
        item->type = type;
        item->tree = tree;
 
-       BLI_linklist_prepend( cache, item );
+       BLI_linklist_prepend(cache, item);
 }