code cleanup: spelling
[blender.git] / source / blender / blenkernel / intern / bvhutils.c
index 752bdab2c00773411e91f271528fbfcc5b4aac26..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 */
@@ -330,7 +330,7 @@ float nearest_point_in_tri_surface(const float v0[3], const float v1[3], const f
                }
        }
 
-       // Account for numerical round-off error
+       /* 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,11 +355,11 @@ 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;
@@ -394,9 +394,34 @@ static void mesh_faces_nearest_point(void *userdata, int index, const float co[3
 
        } 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;
+
+       {
+               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.
+/* 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;
@@ -434,9 +459,38 @@ static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *r
 
        } 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;
+
 
-// 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.
+       {
+               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. */
 static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 {
        const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
@@ -463,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
+       /* 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);
@@ -484,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);
                        }
                }
        }
@@ -495,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;
        }
@@ -517,89 +570,100 @@ 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 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) {
                        /* 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) {
+                                       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 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 tessellated 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 tessellated 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 tessellated 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_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
-                                                               if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
-                                                                       /* Don't insert triangles tessellated 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++) {
@@ -616,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);
                        }
                }
        }
@@ -627,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;
+               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;
        }
@@ -647,17 +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
+       /* 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 */
@@ -672,9 +742,9 @@ BVHTree *bvhtree_from_mesh_edges(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_EDGES);
+                               bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_EDGES);
                        }
                }
        }
@@ -683,19 +753,18 @@ BVHTree *bvhtree_from_mesh_edges(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;
 
                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;
        }
@@ -703,7 +772,7 @@ 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) {
@@ -728,7 +797,7 @@ static void bvhcacheitem_set_if_match(void *_cached, void *_search)
        BVHCacheItem *search = (BVHCacheItem *)_search;
 
        if (search->type == cached->type) {
-               search->tree = cached->tree;            
+               search->tree = cached->tree;
        }
 }