Add dynamic topology support to the PBVH
authorNicholas Bishop <nicholasbishop@gmail.com>
Sun, 30 Dec 2012 18:28:36 +0000 (18:28 +0000)
committerNicholas Bishop <nicholasbishop@gmail.com>
Sun, 30 Dec 2012 18:28:36 +0000 (18:28 +0000)
* Add BLI_pbvh_build_bmesh(), similar to the other PBVH builders but
  specialized for BMesh. Whereas the PBVH leaf nodes for mesh and
  grids only store a start-index and count into the primitive indices
  array, the BMesh version uses GHashes to store the full set of faces
  and vertices in leaf nodes

* Update PBVH iterator to handle BMesh

* Make some of the pbvh.c functions non-static so they can be used by
  the new pbvh_bmesh code

* The BLI_pbvh_bmesh_update_topology() function is the main reason for
  adding BMesh support to the PBVH. This function is used during a
  sculpt stroke to dynamically collapse edges that are particular
  short and subdivide edges that are particularly long.

source/blender/blenkernel/BKE_pbvh.h
source/blender/blenkernel/CMakeLists.txt
source/blender/blenkernel/intern/pbvh.c
source/blender/blenkernel/intern/pbvh_bmesh.c [new file with mode: 0644]
source/blender/blenkernel/intern/pbvh_intern.h

index 5b6acdb97528cbda66a578c83a855c88903d364d..4abeed513df8dbc8760ee04f55a54e87273b2a21 100644 (file)
  */
 
 #include "BLI_bitmap.h"
+#include "BLI_ghash.h"
+#include "BLI_utildefines.h"
+
+/* Needed for BMesh functions used in the PBVH iterator macro */
+#include "bmesh.h"
 
 struct CCGElem;
 struct CCGKey;
 struct CustomData;
 struct DMFlagMat;
 struct DMGridAdjacency;
-struct ListBase;
+struct GHash;
 struct MFace;
 struct MVert;
 struct PBVH;
@@ -63,6 +68,9 @@ void BLI_pbvh_build_grids(PBVH *bvh, struct CCGElem **grid_elems,
                           struct DMGridAdjacency *gridadj, int totgrid,
                           struct CCGKey *key, void **gridfaces, struct DMFlagMat *flagmats,
                           unsigned int **grid_hidden);
+void BLI_pbvh_build_bmesh(PBVH *bvh, struct BMesh *bm, int smooth_shading,
+                                                 struct BMLog *log);
+
 void BLI_pbvh_free(PBVH *bvh);
 
 /* Hierarchical Search in the BVH, two methods:
@@ -86,7 +94,7 @@ void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data,
                       const float ray_start[3], const float ray_normal[3],
                       int original);
 
-int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
+int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], int use_origco,
                           const float ray_start[3], const float ray_normal[3],
                           float *dist);
 
@@ -100,6 +108,7 @@ void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
 typedef enum {
        PBVH_FACES,
        PBVH_GRIDS,
+       PBVH_BMESH
 } PBVHType;
 
 PBVHType BLI_pbvh_type(const PBVH *bvh);
@@ -110,6 +119,17 @@ unsigned int **BLI_pbvh_grid_hidden(const PBVH *bvh);
 /* multires level, only valid for type == PBVH_GRIDS */
 void BLI_pbvh_get_grid_key(const PBVH *pbvh, struct CCGKey *key);
 
+/* Only valid for type == PBVH_BMESH */
+BMesh *BLI_pbvh_get_bmesh(PBVH *pbvh);
+void BLI_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size);
+
+typedef enum {
+       PBVH_Subdivide = 1,
+       PBVH_Collapse = 2,
+} PBVHTopologyUpdateMode;
+int BLI_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
+                                                                  const float center[3], float radius);
+
 /* Node Access */
 
 typedef enum {
@@ -122,12 +142,15 @@ typedef enum {
        PBVH_UpdateRedraw = 32,
 
        PBVH_RebuildDrawBuffers = 64,
-       PBVH_FullyHidden = 128
+       PBVH_FullyHidden = 128,
+
+       PBVH_UpdateTopology = 256,
 } PBVHNodeFlags;
 
 void BLI_pbvh_node_mark_update(PBVHNode *node);
 void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node);
 void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden);
+void BLI_pbvh_node_mark_topology_update(PBVHNode *node);
 
 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
                              int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
@@ -147,6 +170,11 @@ int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
 /* test if AABB is at least partially outside the planes' volume */
 int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data);
 
+struct GHash *BLI_pbvh_bmesh_node_unique_verts(PBVHNode *node);
+struct GHash *BLI_pbvh_bmesh_node_other_verts(PBVHNode *node); 
+void BLI_pbvh_bmesh_node_save_orig(PBVHNode *node);
+void BLI_pbvh_bmesh_after_stroke(PBVH *bvh);
+
 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
 
 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
@@ -169,7 +197,6 @@ float (*BLI_pbvh_get_vertCos(struct PBVH *pbvh))[3];
 void BLI_pbvh_apply_vertCos(struct PBVH *pbvh, float (*vertCos)[3]);
 int BLI_pbvh_isDeformed(struct PBVH *pbvh);
 
-
 /* Vertex Iterator */
 
 /* this iterator has quite a lot of code, but it's designed to:
@@ -205,9 +232,15 @@ typedef struct PBVHVertexIter {
        int *vert_indices;
        float *vmask;
 
+       /* bmesh */
+       struct GHashIterator bm_unique_verts;
+       struct GHashIterator bm_other_verts;
+       struct CustomData *bm_vdata;
+
        /* result: these are all computed in the macro, but we assume
         * that compiler optimization's will skip the ones we don't use */
        struct MVert *mvert;
+       struct BMVert *bm_vert;
        float *co;
        short *no;
        float *fno;
@@ -249,7 +282,7 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
                                                        continue; \
                                        } \
                                } \
-                               else { \
+                               else if (vi.mverts) { \
                                        vi.mvert = &vi.mverts[vi.vert_indices[vi.gx]]; \
                                        if (mode == PBVH_ITER_UNIQUE && vi.mvert->flag & ME_HIDE) \
                                                continue; \
@@ -258,6 +291,24 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
                                        if (vi.vmask) \
                                                vi.mask = &vi.vmask[vi.vert_indices[vi.gx]]; \
                                } \
+                               else { \
+                                       if (!BLI_ghashIterator_isDone(&vi.bm_unique_verts)) {\
+                                               vi.bm_vert = BLI_ghashIterator_getKey(&vi.bm_unique_verts); \
+                                               BLI_ghashIterator_step(&vi.bm_unique_verts); \
+                                       } \
+                                       else { \
+                                               vi.bm_vert = BLI_ghashIterator_getKey(&vi.bm_other_verts); \
+                                               BLI_ghashIterator_step(&vi.bm_other_verts); \
+                                       } \
+                                       if (mode == PBVH_ITER_UNIQUE && \
+                                               BM_elem_flag_test(vi.bm_vert, BM_ELEM_HIDDEN)) \
+                                               continue; \
+                                       vi.co = vi.bm_vert->co; \
+                                       vi.fno = vi.bm_vert->no; \
+                                       vi.mask = CustomData_bmesh_get(vi.bm_vdata, \
+                                                                                                  vi.bm_vert->head.data, \
+                                                                                                  CD_PAINT_MASK); \
+                               }
 
 #define BLI_pbvh_vertex_iter_end \
                        } \
index 6d53f9e7dd5951258bf8f4c28830f1ac9947d8b2..990083094986f019b94d190998e620474c0ef621 100644 (file)
@@ -124,6 +124,7 @@ set(SRC
        intern/particle.c
        intern/particle_system.c
        intern/pbvh.c
+       intern/pbvh_bmesh.c
        intern/pointcache.c
        intern/property.c
        intern/report.c
index e9009050d4bc6dd5d61fb4a337f4058eba3a3757..6e0209e768382bc051bc9ae8a1c1e4f21fbb13a1 100644 (file)
@@ -66,14 +66,14 @@ typedef struct PBVHIter {
        int stackspace;
 } PBVHIter;
 
-static void BB_reset(BB *bb)
+void BB_reset(BB *bb)
 {
        bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
        bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
 }
 
 /* Expand the bounding box to include a new coordinate */
-static void BB_expand(BB *bb, float co[3])
+void BB_expand(BB *bb, const float co[3])
 {
        int i;
        for (i = 0; i < 3; ++i) {
@@ -83,7 +83,7 @@ static void BB_expand(BB *bb, float co[3])
 }
 
 /* Expand the bounding box to include another bounding box */
-static void BB_expand_with_bb(BB *bb, BB *bb2)
+void BB_expand_with_bb(BB *bb, BB *bb2)
 {
        int i;
        for (i = 0; i < 3; ++i) {
@@ -93,7 +93,7 @@ static void BB_expand_with_bb(BB *bb, BB *bb2)
 }
 
 /* Return 0, 1, or 2 to indicate the widest axis of the bounding box */
-static int BB_widest_axis(BB *bb)
+int BB_widest_axis(const BB *bb)
 {
        float dim[3];
        int i;
@@ -115,7 +115,7 @@ static int BB_widest_axis(BB *bb)
        }
 }
 
-static void BBC_update_centroid(BBC *bbc)
+void BBC_update_centroid(BBC *bbc)
 {
        int i;
        for (i = 0; i < 3; ++i)
@@ -220,7 +220,7 @@ static int partition_indices_material(PBVH *bvh, int lo, int hi)
        }
 }
 
-static void grow_nodes(PBVH *bvh, int totnode)
+void pbvh_grow_nodes(PBVH *bvh, int totnode)
 {
        if (totnode > bvh->node_mem_count) {
                PBVHNode *prev = bvh->nodes;
@@ -433,7 +433,7 @@ static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc,
 
        /* Add two child nodes */
        bvh->nodes[node_index].children_offset = bvh->totnode;
-       grow_nodes(bvh, bvh->totnode + 2);
+       pbvh_grow_nodes(bvh, bvh->totnode + 2);
 
        /* Update parent node bounding box */
        update_vb(bvh, &bvh->nodes[node_index], prim_bbc, offset, count);
@@ -601,6 +601,13 @@ void BLI_pbvh_free(PBVH *bvh)
                        if (node->face_vert_indices)
                                MEM_freeN(node->face_vert_indices);
                        BLI_pbvh_node_layer_disp_free(node);
+
+                       if (node->bm_faces)
+                               BLI_ghash_free(node->bm_faces, NULL, NULL);
+                       if (node->bm_unique_verts)
+                               BLI_ghash_free(node->bm_unique_verts, NULL, NULL);
+                       if (node->bm_other_verts)
+                               BLI_ghash_free(node->bm_other_verts, NULL, NULL);
                }
        }
 
@@ -620,6 +627,11 @@ void BLI_pbvh_free(PBVH *bvh)
        if (bvh->prim_indices)
                MEM_freeN(bvh->prim_indices);
 
+       if (bvh->bm_vert_to_node)
+               BLI_ghash_free(bvh->bm_vert_to_node, NULL, NULL);
+       if (bvh->bm_face_to_node)
+               BLI_ghash_free(bvh->bm_face_to_node, NULL, NULL);
+
        MEM_freeN(bvh);
 }
 
@@ -900,6 +912,11 @@ static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes,
        float (*vnor)[3];
        int n;
 
+       if (bvh->type == PBVH_BMESH) {
+               pbvh_bmesh_normals_update(nodes, totnode);
+               return;
+       }
+
        if (bvh->type != PBVH_FACES)
                return;
 
@@ -993,8 +1010,7 @@ static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes,
        MEM_freeN(vnor);
 }
 
-static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes,
-                                  int totnode, int flag)
+void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, int totnode, int flag)
 {
        int n;
 
@@ -1041,6 +1057,11 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
                                                                   node->prim_indices,
                                                                   node->totprim);
                                        break;
+                               case PBVH_BMESH:
+                                       node->draw_buffers =
+                                               GPU_build_bmesh_buffers(bvh->flags &
+                                                                           PBVH_DYNTOPO_SMOOTH_SHADING);
+                                       break;
                        }
  
                        node->flag &= ~PBVH_RebuildDrawBuffers;
@@ -1068,6 +1089,13 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
                                                                node->face_vert_indices,
                                                                bvh->show_diffuse_color);
                                        break;
+                               case PBVH_BMESH:
+                                       GPU_update_bmesh_buffers(node->draw_buffers,
+                                                    bvh->bm,
+                                                                                        node->bm_faces,
+                                                                                        node->bm_unique_verts,
+                                                                                        node->bm_other_verts);
+                                       break;
                        }
 
                        node->flag &= ~PBVH_UpdateDrawBuffers;
@@ -1222,6 +1250,12 @@ void BLI_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key)
        *key = bvh->gridkey;
 }
 
+BMesh *BLI_pbvh_get_bmesh(PBVH *bvh)
+{
+       BLI_assert(bvh->type == PBVH_BMESH);
+       return bvh->bm;
+}
+
 /***************************** Node Access ***********************************/
 
 void BLI_pbvh_node_mark_update(PBVHNode *node)
@@ -1264,6 +1298,11 @@ void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node, int *uniquevert, int *to
                        if (totvert) *totvert = node->uniq_verts + node->face_verts;
                        if (uniquevert) *uniquevert = node->uniq_verts;
                        break;
+               case PBVH_BMESH:
+                       tot = BLI_ghash_size(node->bm_unique_verts);
+                       if (totvert) *totvert = tot + BLI_ghash_size(node->bm_other_verts);
+                       if (uniquevert) *uniquevert = tot;
+                       break;
        }
 }
 
@@ -1279,6 +1318,7 @@ void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node, int **grid_indices, int
                        if (gridadj) *gridadj = bvh->gridadj;
                        break;
                case PBVH_FACES:
+               case PBVH_BMESH:
                        if (grid_indices) *grid_indices = NULL;
                        if (totgrid) *totgrid = 0;
                        if (maxgrid) *maxgrid = 0;
@@ -1345,11 +1385,11 @@ void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data,
        BLI_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data);
 }
 
-static int ray_face_intersection(const float ray_start[3],
-                                 const float ray_normal[3],
-                                 const float *t0, const float *t1,
-                                 const float *t2, const float *t3,
-                                 float *fdist)
+int ray_face_intersection(const float ray_start[3],
+                                                 const float ray_normal[3],
+                                                 const float *t0, const float *t1,
+                                                 const float *t2, const float *t3,
+                                                 float *fdist)
 {
        float dist;
 
@@ -1455,7 +1495,7 @@ static int pbvh_grids_node_raycast(PBVH *bvh, PBVHNode *node,
        return hit;
 }
 
-int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
+int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], int use_origco,
                           const float ray_start[3], const float ray_normal[3],
                           float *dist)
 {
@@ -1473,6 +1513,9 @@ int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
                        hit |= pbvh_grids_node_raycast(bvh, node, origco,
                                                       ray_start, ray_normal, dist);
                        break;
+               case PBVH_BMESH:
+                       hit = pbvh_bmesh_node_raycast(node, ray_start, ray_normal, dist, use_origco);
+                       break;
        }
 
        return hit;
@@ -1803,12 +1846,18 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
        vi->vert_indices = vert_indices;
        vi->mverts = verts;
 
+       if (bvh->type == PBVH_BMESH) {
+               BLI_ghashIterator_init(&vi->bm_unique_verts, node->bm_unique_verts);
+               BLI_ghashIterator_init(&vi->bm_other_verts, node->bm_other_verts);
+               vi->bm_vdata = &bvh->bm->vdata;
+       }
+
        vi->gh = NULL;
        if (vi->grids && mode == PBVH_ITER_UNIQUE)
                vi->grid_hidden = bvh->grid_hidden;
 
        vi->mask = NULL;
-       if (!vi->grids)
+       if (bvh->type == PBVH_FACES)
                vi->vmask = CustomData_get_layer(bvh->vdata, CD_PAINT_MASK);
 }
 
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
new file mode 100644 (file)
index 0000000..9cc8fd0
--- /dev/null
@@ -0,0 +1,1414 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_object_types.h"
+
+#include "BLI_array.h"
+#include "BLI_buffer.h"
+#include "BLI_ghash.h"
+#include "BLI_heap.h"
+#include "BLI_math.h"
+
+#include "BKE_ccg.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_global.h"
+#include "BKE_pbvh.h"
+
+#include "GPU_buffers.h"
+
+#include "bmesh.h"
+#include "pbvh_intern.h"
+
+#include <assert.h>
+
+/****************************** Building ******************************/
+
+/* Update node data after splitting */
+static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index)
+{
+       GHashIterator gh_iter;
+       PBVHNode *n = &bvh->nodes[node_index];
+
+       /* Create vert hash sets */
+       n->bm_unique_verts = BLI_ghash_ptr_new("bm_unique_verts");
+       n->bm_other_verts = BLI_ghash_ptr_new("bm_other_verts");
+
+       BB_reset(&n->vb);
+
+       GHASH_ITER (gh_iter, n->bm_faces) {
+               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               BMIter bm_iter;
+               BMVert *v;
+               void *node_val = SET_INT_IN_POINTER(node_index);
+
+               /* Update ownership of faces */
+               BLI_ghash_insert(bvh->bm_face_to_node, f, node_val);
+
+               /* Update vertices */
+               BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
+                       if (!BLI_ghash_haskey(n->bm_unique_verts, v)) {
+                               if (BLI_ghash_haskey(bvh->bm_vert_to_node, v)) {
+                                       if (!BLI_ghash_haskey(n->bm_other_verts, v))
+                                               BLI_ghash_insert(n->bm_other_verts, v, NULL);
+                               }
+                               else {
+                                       BLI_ghash_insert(n->bm_unique_verts, v, NULL);
+                                       BLI_ghash_insert(bvh->bm_vert_to_node, v, node_val);
+                               }
+                       }
+                       /* Update node bounding box */
+                       BB_expand(&n->vb, v->co);
+               }
+       }
+
+       BLI_assert(n->vb.bmin[0] <= n->vb.bmax[0] &&
+                          n->vb.bmin[1] <= n->vb.bmax[1] &&
+                          n->vb.bmin[2] <= n->vb.bmax[2]);
+
+       n->orig_vb = n->vb;
+
+       /* Build GPU buffers */
+       if (!G.background) {
+               int smooth = bvh->flags & PBVH_DYNTOPO_SMOOTH_SHADING;
+               n->draw_buffers = GPU_build_bmesh_buffers(smooth);
+               n->flag |= PBVH_UpdateDrawBuffers;
+       }
+}
+
+/* Recursively split the node if it exceeds the leaf_limit */
+static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
+{
+       GHash *empty, *other;
+       GHashIterator gh_iter;
+       PBVHNode *n, *c1, *c2;
+       BB cb;
+       float mid;
+       int axis, children;
+
+       n = &bvh->nodes[node_index];
+
+       if (BLI_ghash_size(n->bm_faces) <= bvh->leaf_limit) {
+               /* Node limit not exceeded */
+               pbvh_bmesh_node_finalize(bvh, node_index);
+               return;
+       }
+
+       /* Calculate bounding box around primitive centroids */
+       BB_reset(&cb);
+       GHASH_ITER (gh_iter, n->bm_faces) {
+               const BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               const BBC *bbc = BLI_ghash_lookup(prim_bbc, f);
+
+               BB_expand(&cb, bbc->bcentroid);
+       }
+
+       /* Find widest axis and its midpoint */
+       axis = BB_widest_axis(&cb);
+       mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f;
+
+       /* Add two new child nodes */
+       children = bvh->totnode;
+       n->children_offset = children;
+       pbvh_grow_nodes(bvh, bvh->totnode + 2);
+
+       /* Array reallocated, update current node pointer */
+       n = &bvh->nodes[node_index];
+
+       /* Initialize children */
+       c1 = &bvh->nodes[children];
+       c2 = &bvh->nodes[children + 1];
+       c1->flag |= PBVH_Leaf;
+       c2->flag |= PBVH_Leaf;
+       c1->bm_faces = BLI_ghash_ptr_new("bm_faces");
+       c2->bm_faces = BLI_ghash_ptr_new("bm_faces");
+
+       /* Partition the parent node's faces between the two children */
+       GHASH_ITER (gh_iter, n->bm_faces) {
+               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               const BBC *bbc = BLI_ghash_lookup(prim_bbc, f);
+
+               if (bbc->bcentroid[axis] < mid)
+                       BLI_ghash_insert(c1->bm_faces, f, NULL);
+               else
+                       BLI_ghash_insert(c2->bm_faces, f, NULL);
+       }
+
+       /* Enforce at least one primitive in each node */
+       empty = NULL;
+       if (BLI_ghash_size(c1->bm_faces) == 0) {
+               empty = c1->bm_faces;
+               other = c2->bm_faces;
+       }
+       else if (BLI_ghash_size(c2->bm_faces) == 0) {
+               empty = c2->bm_faces;
+               other = c1->bm_faces;
+       }
+       if (empty) {
+               GHASH_ITER (gh_iter, other) {
+                       void *key = BLI_ghashIterator_getKey(&gh_iter);
+                       BLI_ghash_insert(empty, key, NULL);
+                       BLI_ghash_remove(other, key, NULL, NULL);
+                       break;
+               }
+       }
+       
+       /* Clear this node */
+
+       /* Mark this node's unique verts as unclaimed */
+       if (n->bm_unique_verts) {
+               GHASH_ITER (gh_iter, n->bm_unique_verts) {
+                       BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
+                       BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
+               }
+               BLI_ghash_free(n->bm_unique_verts, NULL, NULL);
+       }
+
+       /* Unclaim faces */
+       GHASH_ITER (gh_iter, n->bm_faces) {
+               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               BLI_ghash_remove(bvh->bm_face_to_node, f, NULL, NULL);
+       }
+       BLI_ghash_free(n->bm_faces, NULL, NULL);
+
+       if (n->bm_other_verts)
+               BLI_ghash_free(n->bm_other_verts, NULL, NULL);
+
+       if (n->layer_disp)
+               MEM_freeN(n->layer_disp);
+       
+       n->bm_faces = NULL;
+       n->bm_unique_verts = NULL;
+       n->bm_other_verts = NULL;
+       n->layer_disp = NULL;
+       
+       if (n->draw_buffers) {
+               GPU_free_buffers(n->draw_buffers);
+               n->draw_buffers = NULL;
+       }
+       n->flag &= ~PBVH_Leaf;
+       
+       /* Recurse */
+       c1 = c2 = NULL;
+       pbvh_bmesh_node_split(bvh, prim_bbc, children);
+       pbvh_bmesh_node_split(bvh, prim_bbc, children + 1);
+
+       /* Array maybe reallocated, update current node pointer */
+       n = &bvh->nodes[node_index];
+
+       /* Update bounding box */
+       BB_reset(&n->vb);
+       BB_expand_with_bb(&n->vb, &bvh->nodes[n->children_offset].vb);
+       BB_expand_with_bb(&n->vb, &bvh->nodes[n->children_offset + 1].vb);
+       n->orig_vb = n->vb;
+}
+
+/* Recursively split the node if it exceeds the leaf_limit */
+static int pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index)
+{
+       GHash *prim_bbc;
+       GHashIterator gh_iter;
+
+       if (BLI_ghash_size(bvh->nodes[node_index].bm_faces) <= bvh->leaf_limit) {
+               /* Node limit not exceeded */
+               return FALSE;
+       }
+
+       /* For each BMFace, store the AABB and AABB centroid */
+       prim_bbc = BLI_ghash_ptr_new("prim_bbc");
+
+       GHASH_ITER (gh_iter, bvh->nodes[node_index].bm_faces) {
+               BMIter bm_iter;
+               BMVert *v;
+               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               BBC *bbc = MEM_callocN(sizeof(BBC), "BBC");
+
+               BB_reset((BB *)bbc);
+               BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
+                       BB_expand((BB *)bbc, v->co);
+               }
+               BBC_update_centroid(bbc);
+
+               BLI_ghash_insert(prim_bbc, f, bbc);
+       }
+
+       pbvh_bmesh_node_split(bvh, prim_bbc, node_index);
+
+       BLI_ghash_free(prim_bbc, NULL, (void*)MEM_freeN);
+
+       return TRUE;
+}
+
+/**********************************************************************/
+
+static PBVHNode *pbvh_bmesh_node_lookup(PBVH *bvh, GHash *map, void *key)
+{
+       int node_index;
+
+       BLI_assert(BLI_ghash_haskey(map, key));
+
+       node_index = GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key));
+       BLI_assert(node_index < bvh->totnode);
+
+       return &bvh->nodes[node_index];
+}
+
+static BMVert *pbvh_bmesh_vert_create(PBVH *bvh, int node_index,
+                                                                         const float co[3],
+                                                                         const BMVert *example)
+{
+       BMVert *v = BM_vert_create(bvh->bm, co, example, 0);
+       void *val = SET_INT_IN_POINTER(node_index);
+
+       BLI_assert((bvh->totnode == 1 || node_index) && node_index <= bvh->totnode);
+
+       BLI_ghash_insert(bvh->nodes[node_index].bm_unique_verts, v, NULL);
+       BLI_ghash_insert(bvh->bm_vert_to_node, v, val);
+
+       /* Log the new vertex */
+       BM_log_vert_added(bvh->bm, bvh->bm_log, v);
+
+       return v;
+}
+
+static BMFace *pbvh_bmesh_face_create(PBVH *bvh, int node_index, BMVert *v1,
+                                                                         BMVert *v2, BMVert *v3,
+                                                                         const BMFace *UNUSED(example))
+{
+       BMFace *f;
+       void *val = SET_INT_IN_POINTER(node_index);
+
+       /* Note: passing NULL for the 'example' parameter, profiling shows
+        * a small performance bump */
+       f = BM_face_create_quad_tri(bvh->bm, v1, v2, v3, NULL, NULL, TRUE);
+       if (!BLI_ghash_haskey(bvh->bm_face_to_node, f)) {
+
+               BLI_ghash_insert(bvh->nodes[node_index].bm_faces, f, NULL);
+               BLI_ghash_insert(bvh->bm_face_to_node, f, val);
+
+               /* Log the new face */
+               BM_log_face_added(bvh->bm_log, f);
+       }
+
+       return f;
+}
+
+/* Return the number of faces in 'node' that use vertex 'v' */
+static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v)
+{
+       BMIter bm_iter;
+       BMFace *f;
+       int count = 0;
+
+       BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
+               PBVHNode *f_node;
+
+               f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+
+               if (f_node == node)
+                       count++;
+       }
+
+       return count;
+}
+
+/* Return a node that uses vertex 'v' other than its current owner */
+static PBVHNode *pbvh_bmesh_vert_other_node_find(PBVH *bvh, BMVert *v)
+{
+       BMIter bm_iter;
+       BMFace *f;
+       PBVHNode *current_node;
+
+       current_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+
+       BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
+               PBVHNode *f_node;
+
+               f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+
+               if (f_node != current_node)
+                       return f_node;
+       }
+
+       return NULL;
+}
+
+static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner,
+                                                                                          BMVert *v)
+{
+       PBVHNode *current_owner;
+
+       current_owner = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+       BLI_assert(current_owner != new_owner);
+
+       /* Remove current ownership */
+       BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
+       BLI_ghash_remove(current_owner->bm_unique_verts, v, NULL, NULL);
+
+       /* Set new ownership */
+       BLI_ghash_insert(bvh->bm_vert_to_node, v,
+                                        SET_INT_IN_POINTER(new_owner - bvh->nodes));
+       BLI_ghash_insert(new_owner->bm_unique_verts, v, NULL);
+       BLI_ghash_remove(new_owner->bm_other_verts, v, NULL, NULL);
+       BLI_assert(!BLI_ghash_haskey(new_owner->bm_other_verts, v));
+}
+
+static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v)
+{
+       PBVHNode *v_node;
+       BMIter bm_iter;
+       BMFace *f;
+
+       BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
+       v_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+       BLI_ghash_remove(v_node->bm_unique_verts, v, NULL, NULL);
+       BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
+
+       /* Have to check each neighboring face's node */
+       BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
+               PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+
+               BLI_ghash_remove(f_node->bm_unique_verts, v, NULL, NULL);
+               BLI_ghash_remove(f_node->bm_other_verts, v, NULL, NULL);
+
+               BLI_assert(!BLI_ghash_haskey(f_node->bm_unique_verts, v));
+               BLI_assert(!BLI_ghash_haskey(f_node->bm_other_verts, v));
+       }
+}
+
+static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f)
+{
+       PBVHNode *f_node;
+       BMIter bm_iter;
+       BMVert *v;
+
+       f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+
+       /* Check if any of this face's vertices need to be removed
+        * from the node */
+       BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
+               if (pbvh_bmesh_node_vert_use_count(bvh, f_node, v) == 1) {
+                       if (BLI_ghash_lookup(f_node->bm_unique_verts, v)) {
+                               /* Find a different node that uses 'v' */
+                               PBVHNode *new_node;
+
+                               new_node = pbvh_bmesh_vert_other_node_find(bvh, v);
+                               BLI_assert(new_node || BM_vert_face_count(v) == 1);
+
+                               if (new_node) {
+                                       pbvh_bmesh_vert_ownership_transfer(bvh, new_node, v);
+                               }
+                       }
+                       else {
+                               /* Remove from other verts */
+                               BLI_ghash_remove(f_node->bm_other_verts, v, NULL, NULL);
+                       }
+               }
+       }
+
+       /* Remove face from node and top level */
+       BLI_ghash_remove(f_node->bm_faces, f, NULL, NULL);
+       BLI_ghash_remove(bvh->bm_face_to_node, f, NULL, NULL);
+
+       /* Log removed face */
+       BM_log_face_removed(bvh->bm_log, f);
+}
+
+static BMVert *bm_triangle_other_vert_find(BMFace *triangle, const BMVert *v1,
+                                                                                  const BMVert *v2)
+{
+       BLI_assert(triangle->len == 3);
+       BLI_assert(v1 != v2);
+
+       if (triangle->len == 3) {
+               BMIter iter;
+               BMVert *v, *other = NULL;
+               int found_v1 = FALSE, found_v2 = FALSE;
+
+               BM_ITER_ELEM (v, &iter, triangle, BM_VERTS_OF_FACE) {
+                       if (v == v1)
+                               found_v1 = TRUE;
+                       else if (v == v2)
+                               found_v2 = TRUE;
+                       else
+                               other = v;
+               }
+
+               if (found_v1 && found_v2)
+                       return other;
+       }
+
+       BLI_assert(0);
+       return NULL;
+}
+
+static void pbvh_bmesh_edge_faces(BLI_Buffer *buf, BMEdge *e)
+{
+       BLI_buffer_resize(buf, BM_edge_face_count(e));
+       BM_iter_as_array(NULL, BM_FACES_OF_EDGE, e, buf->data, buf->count);
+}
+
+/* TODO: maybe a better way to do this, if not then this should go to
+ * bmesh_queries */
+static int bm_face_edge_backwards(BMFace *f, BMEdge *e)
+{
+       BMIter bm_iter;
+       BMLoop *l, *l1 = NULL, *l2 = NULL;
+
+       BM_ITER_ELEM (l, &bm_iter, f, BM_LOOPS_OF_FACE) {
+               if (l->v == e->v1)
+                       l1 = l;
+               else if (l->v == e->v2)
+                       l2 = l;
+       }
+
+       BLI_assert(l1 && l2);
+       BLI_assert(l1->next == l2 || l2->next == l1);
+       return l2->next == l1;
+}
+
+static void pbvh_bmesh_node_drop_orig(PBVHNode *node)
+{
+       if (node->bm_orco)
+               MEM_freeN(node->bm_orco);
+       if (node->bm_ortri)
+               MEM_freeN(node->bm_ortri);
+       node->bm_orco = NULL;
+       node->bm_ortri = NULL;
+       node->bm_tot_ortri = 0;
+}
+
+/****************************** EdgeQueue *****************************/
+
+typedef struct {
+       Heap *heap;
+       const float *center;
+       float radius_squared;
+       float limit_len_squared;
+} EdgeQueue;
+
+static int edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
+{
+       BMVert *v[3];
+       float c[3];
+
+       /* Get closest point in triangle to sphere center */
+       BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v, 3);
+       closest_on_tri_to_point_v3(c, q->center, v[0]->co, v[1]->co, v[2]->co);
+
+       /* Check if triangle intersects the sphere */
+       return ((len_squared_v3v3(q->center, c) <= q->radius_squared));
+}
+
+static void edge_queue_insert(EdgeQueue *q, BLI_mempool *pool, BMEdge *e,
+                                                         float priority)
+{
+       BMVert **pair;
+
+       pair = BLI_mempool_alloc(pool);
+       pair[0] = e->v1;
+       pair[1] = e->v2;
+       BLI_heap_insert(q->heap, priority, pair);
+}
+
+static void long_edge_queue_edge_add(EdgeQueue *q, BLI_mempool *pool,
+                                                                        BMEdge *e)
+{
+       const float len_sq = BM_edge_calc_squared_length(e);
+       if (len_sq > q->limit_len_squared)
+               edge_queue_insert(q, pool, e, 1.0f / len_sq);
+}
+
+static void short_edge_queue_edge_add(EdgeQueue *q, BLI_mempool *pool,
+                                                                         BMEdge *e)
+{
+       const float len_sq = BM_edge_calc_squared_length(e);
+       if (len_sq < q->limit_len_squared)
+               edge_queue_insert(q, pool, e, len_sq);
+}
+
+static int long_edge_queue_face_add(EdgeQueue *q, BLI_mempool *pool,
+                                                                       BMFace *f)
+{
+       BMIter bm_iter;
+       BMEdge *e;
+
+       if (edge_queue_tri_in_sphere(q, f)) {
+               /* Check each edge of the face */
+               BM_ITER_ELEM (e, &bm_iter, f, BM_EDGES_OF_FACE) {
+                       long_edge_queue_edge_add(q, pool, e);
+               }
+       }
+
+       return TRUE;
+}
+
+static int short_edge_queue_face_add(EdgeQueue *q, BLI_mempool *pool,
+                                                                        BMFace *f)
+{
+       BMIter bm_iter;
+       BMEdge *e;
+
+       if (edge_queue_tri_in_sphere(q, f)) {
+               /* Check each edge of the face */
+               BM_ITER_ELEM (e, &bm_iter, f, BM_EDGES_OF_FACE) {
+                       short_edge_queue_edge_add(q, pool, e);
+               }
+       }
+
+       return TRUE;
+}
+
+/* Create a priority queue containing vertex pairs connected by a long
+ * edge as defined by PBVH.bm_max_edge_len.
+ *
+ * Only nodes marked for topology update are checked, and in those
+ * nodes only edges used by a face intersecting the (center, radius)
+ * sphere are checked.
+ *
+ * The highest priority (lowest number) is given to the longest edge.
+ */
+static void long_edge_queue_create(EdgeQueue *q, BLI_mempool *pool,
+                                                                  PBVH *bvh, const float center[3],
+                                                                  float radius)
+{
+       int n;
+
+       q->heap = BLI_heap_new();
+       q->center = center;
+       q->radius_squared = radius * radius;
+       q->limit_len_squared = bvh->bm_max_edge_len * bvh->bm_max_edge_len;
+
+       for (n = 0; n < bvh->totnode; n++) {
+               PBVHNode *node = &bvh->nodes[n];
+
+               /* Check leaf nodes marked for topology update */
+               if ((node->flag & PBVH_Leaf) &&
+                       (node->flag & PBVH_UpdateTopology))
+               {
+                       GHashIterator gh_iter;
+
+                       /* Check each face */
+                       GHASH_ITER (gh_iter, node->bm_faces) {
+                               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+
+                               long_edge_queue_face_add(q, pool, f);
+                       }
+               }
+       }
+}
+
+/* Create a priority queue containing vertex pairs connected by a
+ * short edge as defined by PBVH.bm_min_edge_len.
+ *
+ * Only nodes marked for topology update are checked, and in those
+ * nodes only edges used by a face intersecting the (center, radius)
+ * sphere are checked.
+ *
+ * The highest priority (lowest number) is given to the shortest edge.
+ */
+static void short_edge_queue_create(EdgeQueue *q, BLI_mempool *pool,
+                                                                       PBVH *bvh, const float center[3],
+                                                                       float radius)
+{
+       int n;
+
+       q->heap = BLI_heap_new();
+       q->center = center;
+       q->radius_squared = radius * radius;
+       q->limit_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len;
+
+       for (n = 0; n < bvh->totnode; n++) {
+               PBVHNode *node = &bvh->nodes[n];
+
+               /* Check leaf nodes marked for topology update */
+               if ((node->flag & PBVH_Leaf) &&
+                       (node->flag & PBVH_UpdateTopology))
+               {
+                       GHashIterator gh_iter;
+
+                       /* Check each face */
+                       GHASH_ITER (gh_iter, node->bm_faces) {
+                               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+
+                               short_edge_queue_face_add(q, pool, f);
+                       }
+               }
+       }
+}
+
+/*************************** Topology update **************************/
+
+static void pbvh_bmesh_split_edge(PBVH *bvh, EdgeQueue *q, BLI_mempool *pool,
+                                                                 BMEdge *e, BLI_Buffer *edge_faces)
+{
+       BMVert *v_new;
+       float mid[3];
+       int i, node_index;
+
+       /* Get all faces adjacent to the edge */
+       pbvh_bmesh_edge_faces(edge_faces, e);
+
+       /* Create a new vertex in current node at the edge's midpoint */
+       mid_v3_v3v3(mid, e->v1->co, e->v2->co);
+
+       node_index = GET_INT_FROM_POINTER(BLI_ghash_lookup(bvh->bm_vert_to_node,
+                                                                                                          e->v1));
+       v_new = pbvh_bmesh_vert_create(bvh, node_index, mid, e->v1);
+
+       /* For each face, add two new triangles and delete the original */
+       for (i = 0; i < edge_faces->count; i++) {
+               BMFace *f_adj = BLI_buffer_at(edge_faces, BMFace *, i);
+               BMFace *f_new;
+               BMVert *opp, *v1, *v2;
+               void *nip;
+               int ni;
+
+               BLI_assert(f_adj->len == 3);
+               nip = BLI_ghash_lookup(bvh->bm_face_to_node, f_adj);
+               ni = GET_INT_FROM_POINTER(nip);
+
+               /* Ensure node gets redrawn */
+               bvh->nodes[ni].flag |= PBVH_UpdateDrawBuffers;
+
+               /* Find the vertex not in the edge */
+               opp = bm_triangle_other_vert_find(f_adj, e->v1, e->v2);
+
+               /* Get e->v1 and e->v2 in the order they appear in the
+                * existing face so that the new faces' winding orders
+                * match */
+               v1 = e->v1;
+               v2 = e->v2;
+               if (bm_face_edge_backwards(f_adj, e))
+                       SWAP(BMVert *, v1, v2);
+
+               if (ni != node_index && i == 0)
+                       pbvh_bmesh_vert_ownership_transfer(bvh, &bvh->nodes[ni], v_new);
+
+               /* Create two new faces */
+               f_new = pbvh_bmesh_face_create(bvh, ni, v1, v_new, opp, f_adj);
+               long_edge_queue_face_add(q, pool, f_new);
+               f_new = pbvh_bmesh_face_create(bvh, ni, v_new, v2, opp, f_adj);
+               long_edge_queue_face_add(q, pool, f_new);
+
+               /* Delete original */
+               pbvh_bmesh_face_remove(bvh, f_adj);
+               BM_face_kill(bvh->bm, f_adj);
+
+               /* Ensure new vertex is in the node */
+               if (!BLI_ghash_haskey(bvh->nodes[ni].bm_unique_verts, v_new) &&
+                       !BLI_ghash_haskey(bvh->nodes[ni].bm_other_verts, v_new))
+               {
+                       BLI_ghash_insert(bvh->nodes[ni].bm_other_verts, v_new, NULL);
+               }
+
+               if (BM_vert_edge_count(opp) >= 9) {
+                       BMIter bm_iter;
+                       BMEdge *e2;
+
+                       BM_ITER_ELEM (e2, &bm_iter, opp, BM_EDGES_OF_VERT) {
+                               long_edge_queue_edge_add(q, pool, e2);
+                       }
+               }
+       }
+
+       BM_edge_kill(bvh->bm, e);
+}
+
+static int pbvh_bmesh_subdivide_long_edges(PBVH *bvh, EdgeQueue *q,
+                                                                                  BLI_mempool *pool,
+                                                                                  BLI_Buffer *edge_faces)
+{
+       int any_subdivided = FALSE;
+
+       while (!BLI_heap_is_empty(q->heap)) {
+               BMVert **pair = BLI_heap_popmin(q->heap);
+               BMEdge *e;
+
+               /* Check that the edge still exists */
+               if (!(e = BM_edge_exists(pair[0], pair[1]))) {
+                       BLI_mempool_free(pool, pair);
+                       continue;
+               }
+
+               BLI_mempool_free(pool, pair);
+               pair = NULL;
+
+               /* Check that the edge's vertices are still in the PBVH. It's
+                * possible that an edge collapse has deleted adjacent faces
+                * and the node has been split, thus leaving wire edges and
+                * associated vertices. */
+               if (!BLI_ghash_haskey(bvh->bm_vert_to_node, e->v1) ||
+                       !BLI_ghash_haskey(bvh->bm_vert_to_node, e->v2))
+               {
+                       continue;
+               }
+
+               if (BM_edge_calc_squared_length(e) <= q->limit_len_squared)
+                       continue;
+
+               any_subdivided = TRUE;
+
+               pbvh_bmesh_split_edge(bvh, q, pool, e, edge_faces);
+       }
+
+       return any_subdivided;
+}
+
+static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e, BMVert *v1,
+                                                                        BMVert *v2, GHash *deleted_verts,
+                                                                        BLI_Buffer *edge_faces,
+                                                                        BLI_Buffer *deleted_faces)
+{
+       BMIter bm_iter;
+       BMFace *f;
+       int i;
+
+       /* Get all faces adjacent to the edge */
+       pbvh_bmesh_edge_faces(edge_faces, e);
+
+       /* Remove the merge vertex from the PBVH */
+       pbvh_bmesh_vert_remove(bvh, v2);
+
+       /* Remove all faces adjacent to the edge */
+       for (i = 0; i < edge_faces->count; i++) {
+               BMFace *f_adj = BLI_buffer_at(edge_faces, BMFace *, i);
+
+               pbvh_bmesh_face_remove(bvh, f_adj);
+               BM_face_kill(bvh->bm, f_adj);
+       }
+
+       /* Kill the edge */
+       BLI_assert(BM_edge_face_count(e) == 0);
+       BM_edge_kill(bvh->bm, e);
+
+       /* For all remaining faces of v2, create a new face that is the
+          same except it uses v1 instead of v2 */
+       /* Note: this could be done with BM_vert_splice(), but that
+        * requires handling other issues like duplicate edges, so doesn't
+        * really buy anything. */
+       deleted_faces->count = 0;
+       BM_ITER_ELEM (f, &bm_iter, v2, BM_FACES_OF_VERT) {
+               BMVert *v[3];
+               BMFace *existing_face;
+               PBVHNode *n;
+               int ni;
+
+               /* Get vertices, replace use of v2 with v1 */
+               BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v, 3);
+               for (i = 0; i < 3; i++) {
+                       if (v[i] == v2)
+                               v[i] = v1;
+               }
+
+               /* Check if a face using these vertices already exists. If so,
+                * skip adding this face and mark the existing one for
+                * deletion as well. Prevents extraneous "flaps" from being
+                * created. */
+               if (BM_face_exists(v, 3, &existing_face)) {
+                       BLI_assert(existing_face);
+                       BLI_buffer_append(deleted_faces, BMFace *, existing_face);
+               }
+               else {
+                       n = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
+                       ni = n - bvh->nodes;
+                       pbvh_bmesh_face_create(bvh, ni, v[0], v[1], v[2], f);
+
+                       /* Ensure that v1 is in the new face's node */
+                       if (!BLI_ghash_haskey(n->bm_unique_verts, v1) &&
+                               !BLI_ghash_haskey(n->bm_other_verts, v1)) {
+                               BLI_ghash_insert(n->bm_other_verts, v1, NULL);
+                       }
+               }
+
+               BLI_buffer_append(deleted_faces, BMFace *, f);
+       }
+
+       /* Delete the tagged faces */
+       for (i = 0; i < deleted_faces->count; i++) {
+               BMFace *f_del = BLI_buffer_at(deleted_faces, BMFace *, i);
+               BMVert *v[3];
+               int j;
+
+               BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f_del, (void **)v, 3);
+
+               /* Check if any of the face's vertices are now unused, if so
+                  remove them from the PBVH */
+               for (j = 0; j < 3; j++) {
+                       if (v[j] != v2 && BM_vert_face_count(v[j]) == 0) {
+                               BLI_ghash_insert(deleted_verts, v[j], NULL);
+                               pbvh_bmesh_vert_remove(bvh, v[j]);
+                       }
+                       else {
+                               v[j] = NULL;
+                       }
+               }
+
+               /* Remove the face */
+               pbvh_bmesh_face_remove(bvh, f_del);
+               BM_face_kill(bvh->bm, f_del);
+
+               /* Delete unused vertices */
+               for (j = 0; j < 3; j++) {
+                       if (v[j]) {
+                               BM_log_vert_removed(bvh->bm, bvh->bm_log, v[j]);
+                               BM_vert_kill(bvh->bm, v[j]);
+                       }
+               }
+       }
+
+       /* Move v1 to the midpoint of v1 and v2 */
+       BM_log_vert_before_modified(bvh->bm, bvh->bm_log, v1);
+       mid_v3_v3v3(v1->co, v1->co, v2->co);
+
+       /* Delete v2 */
+       BLI_assert(BM_vert_face_count(v2) == 0);
+       BLI_ghash_insert(deleted_verts, v2, NULL);
+       BM_log_vert_removed(bvh->bm, bvh->bm_log, v2);
+       BM_vert_kill(bvh->bm, v2);
+}
+
+static int pbvh_bmesh_collapse_short_edges(PBVH *bvh, EdgeQueue *q,
+                                                                                  BLI_mempool *pool,
+                                                                                  BLI_Buffer *edge_faces,
+                                                                                  BLI_Buffer *deleted_faces)
+{
+       float min_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len;
+       GHash *deleted_verts;
+       int any_collapsed = FALSE;
+
+       deleted_verts = BLI_ghash_ptr_new("deleted_verts");
+
+       while (!BLI_heap_is_empty(q->heap)) {
+               BMVert **pair = BLI_heap_popmin(q->heap);
+               BMEdge *e;
+               BMVert *v1, *v2;
+
+               v1 = pair[0];
+               v2 = pair[1];
+               BLI_mempool_free(pool, pair);
+               pair = NULL;
+
+               /* Check that the vertices/edge still exist */
+               if (BLI_ghash_haskey(deleted_verts, v1) ||
+                       BLI_ghash_haskey(deleted_verts, v2) ||
+                       !(e = BM_edge_exists(v1, v2)))
+                       continue;
+
+               /* Check that the edge's vertices are still in the PBVH. It's
+                * possible that an edge collapse has deleted adjacent faces
+                * and the node has been split, thus leaving wire edges and
+                * associated vertices. */
+               if (!BLI_ghash_haskey(bvh->bm_vert_to_node, e->v1) ||
+                       !BLI_ghash_haskey(bvh->bm_vert_to_node, e->v2))
+               {
+                       continue;
+               }
+
+               if (BM_edge_calc_squared_length(e) >= min_len_squared)
+                       continue;
+
+               any_collapsed = TRUE;
+
+               pbvh_bmesh_collapse_edge(bvh, e, v1, v2,
+                                                                deleted_verts, edge_faces,
+                                                                deleted_faces);
+       }
+
+       BLI_ghash_free(deleted_verts, NULL, NULL);
+
+       return any_collapsed;
+}
+
+/************************* Called from pbvh.c *************************/
+
+int pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3],
+                                                       const float ray_normal[3], float *dist,
+                                                       int use_original)
+{
+       GHashIterator gh_iter;
+       int hit = 0;
+
+       if (use_original && node->bm_tot_ortri) {
+               int i;
+               for (i = 0; i < node->bm_tot_ortri; i++) {
+                       const int *t = node->bm_ortri[i];
+                       hit |= ray_face_intersection(ray_start, ray_normal,
+                                                                                node->bm_orco[t[0]],
+                                                                                node->bm_orco[t[1]],
+                                                                                node->bm_orco[t[2]],
+                                                                                NULL, dist);
+               }
+       }
+       else {
+               GHASH_ITER (gh_iter, node->bm_faces) {
+                       BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+
+                       BLI_assert(f->len == 3);
+                       if (f->len == 3) {
+                               BMVert *v[3];
+
+                               BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v, 3);
+                               hit |= ray_face_intersection(ray_start, ray_normal,
+                                                                                        v[0]->co,
+                                                                                        v[1]->co,
+                                                                                        v[2]->co,
+                                                                                        NULL, dist);
+                       }
+               }
+       }
+
+       return hit;
+}
+
+void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode)
+{
+       int n;
+
+       for (n = 0; n < totnode; n++) {
+               PBVHNode *node = nodes[n];
+               GHashIterator gh_iter;
+
+               GHASH_ITER (gh_iter, node->bm_faces) {
+                       BM_face_normal_update(BLI_ghashIterator_getKey(&gh_iter));
+               }
+               GHASH_ITER (gh_iter, node->bm_unique_verts) {
+                       BM_vert_normal_update(BLI_ghashIterator_getKey(&gh_iter));
+               }
+       }
+}
+
+/***************************** Public API *****************************/
+
+/* Build a PBVH from a BMesh */
+void BLI_pbvh_build_bmesh(PBVH *bvh, BMesh *bm, int smooth_shading,
+                                                 BMLog *log)
+{
+       BMIter iter;
+       BMFace *f;
+       PBVHNode *n;
+       int node_index = 0;
+
+       bvh->bm = bm;
+
+       BLI_pbvh_bmesh_detail_size_set(bvh, 0.75);
+
+       bvh->type = PBVH_BMESH;
+       bvh->bm_face_to_node = BLI_ghash_ptr_new("bm_face_to_node");
+       bvh->bm_vert_to_node = BLI_ghash_ptr_new("bm_vert_to_node");
+       bvh->bm_log = log;
+
+       /* TODO: choose leaf limit better */
+       bvh->leaf_limit = 100;
+
+       if (smooth_shading)
+               bvh->flags |= PBVH_DYNTOPO_SMOOTH_SHADING;
+
+       /* Start with all faces in the root node */
+       n = bvh->nodes = MEM_callocN(sizeof(PBVHNode), "PBVHNode");
+       bvh->totnode = 1;
+       n->flag = PBVH_Leaf;
+       n->bm_faces = BLI_ghash_ptr_new("bm_faces");
+       BM_ITER_MESH (f, &iter, bvh->bm, BM_FACES_OF_MESH) {
+               BLI_ghash_insert(n->bm_faces, f, NULL);
+       }
+
+       /* Recursively split the node until it is under the limit; if no
+        * splitting occurs then finalize the existing leaf node */
+       if (!pbvh_bmesh_node_limit_ensure(bvh, node_index))
+               pbvh_bmesh_node_finalize(bvh, 0);
+}
+
+/* Collapse short edges, subdivide long edges */
+int BLI_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
+                                                                  const float center[3], float radius)
+{
+       BLI_buffer_declare(BMFace*, edge_faces, 8);
+       BLI_buffer_declare(BMFace*, deleted_faces, 32);
+       int modified = FALSE;
+       int n;
+
+       if (mode & PBVH_Collapse) {
+               EdgeQueue q;
+               BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert) * 2,
+                                                                                                        128, 128, 0);
+               short_edge_queue_create(&q, queue_pool, bvh, center, radius);
+               pbvh_bmesh_collapse_short_edges(bvh, &q, queue_pool, &edge_faces,
+                                                                               &deleted_faces);
+               BLI_heap_free(q.heap, NULL);
+               BLI_mempool_destroy(queue_pool);
+       }
+
+       if (mode & PBVH_Subdivide) {
+               EdgeQueue q;
+               BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert) * 2,
+                                                                                                        128, 128, 0);
+               long_edge_queue_create(&q, queue_pool, bvh, center, radius);
+               pbvh_bmesh_subdivide_long_edges(bvh, &q, queue_pool, &edge_faces);
+               BLI_heap_free(q.heap, NULL);
+               BLI_mempool_destroy(queue_pool);
+       }
+       
+       /* Unmark nodes */
+       for (n = 0; n < bvh->totnode; n++) {
+               PBVHNode *node = &bvh->nodes[n];
+
+               if (node->flag & PBVH_Leaf &&
+                       node->flag & PBVH_UpdateTopology)
+               {
+                       node->flag &= ~PBVH_UpdateTopology;
+               }
+       }
+       BLI_buffer_free(&edge_faces);
+       BLI_buffer_free(&deleted_faces);
+
+       return modified;
+}
+
+/* In order to perform operations on the original node coordinates
+ * (such as raycast), store the node's triangles and vertices.*/
+void BLI_pbvh_bmesh_node_save_orig(PBVHNode *node)
+{
+       GHashIterator gh_iter;
+       int i, totvert, tottri;
+
+       /* Skip if original coords/triangles are already saved */
+       if (node->bm_orco)
+               return;
+
+       totvert = (BLI_ghash_size(node->bm_unique_verts) +
+                          BLI_ghash_size(node->bm_other_verts));
+
+       tottri = BLI_ghash_size(node->bm_faces);
+
+       node->bm_orco = MEM_mallocN(sizeof(*node->bm_orco) * totvert, AT);
+       node->bm_ortri = MEM_mallocN(sizeof(*node->bm_ortri) * tottri, AT);
+
+       /* Copy out the vertices and assign a temporary index */
+       i = 0;
+       GHASH_ITER (gh_iter, node->bm_unique_verts) {
+               BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
+               copy_v3_v3(node->bm_orco[i], v->co);
+               BM_elem_index_set(v, i); /* set_dirty! */
+               i++;
+       }
+       GHASH_ITER (gh_iter, node->bm_other_verts) {
+               BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
+               copy_v3_v3(node->bm_orco[i], v->co);
+               BM_elem_index_set(v, i); /* set_dirty! */
+               i++;
+       }
+
+       /* Copy the triangles */
+       i = 0;
+       GHASH_ITER (gh_iter, node->bm_faces) {
+               BMIter bm_iter;
+               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               BMVert *v;
+               int j = 0;
+
+               BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
+                       node->bm_ortri[i][j] = BM_elem_index_get(v);
+                       j++;
+               }
+               i++;
+       }
+       node->bm_tot_ortri = i;
+}
+
+void BLI_pbvh_bmesh_after_stroke(PBVH *bvh)
+{
+       int i;
+       for (i = 0; i < bvh->totnode; i++) {
+               PBVHNode *n = &bvh->nodes[i];
+               if (n->flag & PBVH_Leaf) {
+                       /* Free orco/ortri data */
+                       pbvh_bmesh_node_drop_orig(n);
+
+                       /* Recursively split nodes that have gotten too many
+                        * elements */
+                       pbvh_bmesh_node_limit_ensure(bvh, i);
+               }
+       }
+}
+
+void BLI_pbvh_bmesh_detail_size_set(PBVH *bvh, float detail_size)
+{
+       bvh->bm_max_edge_len = detail_size;
+       bvh->bm_min_edge_len = bvh->bm_max_edge_len * 0.4;
+}
+
+void BLI_pbvh_node_mark_topology_update(PBVHNode *node)
+{
+       node->flag |= PBVH_UpdateTopology;
+}
+
+GHash *BLI_pbvh_bmesh_node_unique_verts(PBVHNode *node)
+{
+       return node->bm_unique_verts;
+}
+
+GHash *BLI_pbvh_bmesh_node_other_verts(PBVHNode *node)
+{
+       return node->bm_other_verts;
+}
+
+/****************************** Debugging *****************************/
+
+#if 0
+void bli_ghash_duplicate_key_check(GHash *gh)
+{
+       GHashIterator gh_iter1, gh_iter2;
+
+       GHASH_ITER (gh_iter1, gh) {
+               void *key1 = BLI_ghashIterator_getKey(&gh_iter1);
+               int dup = -1;
+
+               GHASH_ITER (gh_iter2, gh) {
+                       void *key2 = BLI_ghashIterator_getKey(&gh_iter2);
+
+                       if (key1 == key2) {
+                               dup++;
+                               if (dup > 0) {
+                                       BLI_assert(!"duplicate in hash");
+                               }
+                       }
+               }
+       }
+}
+
+void bmesh_print(BMesh *bm)
+{
+       BMIter iter, siter;
+       BMVert *v;
+       BMEdge *e;
+       BMFace *f;
+       BMLoop *l;
+
+       fprintf(stderr, "\nbm=%p, totvert=%d, totedge=%d, "
+                       "totloop=%d, totface=%d\n",
+                       bm, bm->totvert, bm->totedge,
+                       bm->totloop, bm->totface);
+
+       fprintf(stderr, "vertices:\n");
+       BM_ITER_MESH(v, &iter, bm, BM_VERTS_OF_MESH) {
+               fprintf(stderr, "  %d co=(%.3f %.3f %.3f) oflag=%x\n",
+                               BM_elem_index_get(v), v->co[0], v->co[1], v->co[2],
+                               v->oflags[bm->stackdepth - 1].f);
+       }
+
+       fprintf(stderr, "edges:\n");
+       BM_ITER_MESH(e, &iter, bm, BM_EDGES_OF_MESH) {
+               fprintf(stderr, "  %d v1=%d, v2=%d, oflag=%x\n",
+                               BM_elem_index_get(e),
+                               BM_elem_index_get(e->v1),
+                               BM_elem_index_get(e->v2),
+                               e->oflags[bm->stackdepth - 1].f);
+       }
+
+       fprintf(stderr, "faces:\n");
+       BM_ITER_MESH(f, &iter, bm, BM_FACES_OF_MESH) {
+               fprintf(stderr, "  %d len=%d, oflag=%x\n",
+                               BM_elem_index_get(f), f->len,
+                               f->oflags[bm->stackdepth - 1].f);
+
+               fprintf(stderr, "    v: ");
+               BM_ITER_ELEM(v, &siter, f, BM_VERTS_OF_FACE) {
+                       fprintf(stderr, "%d ", BM_elem_index_get(v));
+               }
+               fprintf(stderr, "\n");
+
+               fprintf(stderr, "    e: ");
+               BM_ITER_ELEM(e, &siter, f, BM_EDGES_OF_FACE) {
+                       fprintf(stderr, "%d ", BM_elem_index_get(e));
+               }
+               fprintf(stderr, "\n");
+
+               fprintf(stderr, "    l: ");
+               BM_ITER_ELEM(l, &siter, f, BM_LOOPS_OF_FACE) {
+                       fprintf(stderr, "%d(v=%d, e=%d) ",
+                                       BM_elem_index_get(l),
+                                       BM_elem_index_get(l->v),
+                                       BM_elem_index_get(l->e));
+               }
+               fprintf(stderr, "\n");
+       }       
+}
+
+void pbvh_bmesh_print(PBVH *bvh)
+{
+       GHashIterator gh_iter;
+       int n;
+
+       fprintf(stderr, "\npbvh=%p\n", bvh);
+       fprintf(stderr, "bm_face_to_node:\n");
+       GHASH_ITER (gh_iter, bvh->bm_face_to_node) {
+               fprintf(stderr, "  %d -> %d\n",
+                               BM_elem_index_get((BMFace*)BLI_ghashIterator_getKey(&gh_iter)),
+                               GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter)));
+       }
+
+       fprintf(stderr, "bm_vert_to_node:\n");
+       GHASH_ITER (gh_iter, bvh->bm_vert_to_node) {
+               fprintf(stderr, "  %d -> %d\n",
+                               BM_elem_index_get((BMVert*)BLI_ghashIterator_getKey(&gh_iter)),
+                               GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter)));
+       }
+
+       for (n = 0; n < bvh->totnode; n++) {
+               PBVHNode *node = &bvh->nodes[n];
+               if (!(node->flag & PBVH_Leaf))
+                       continue;
+
+               fprintf(stderr, "node %d\n  faces:\n", n);
+               GHASH_ITER (gh_iter, node->bm_faces)
+                       fprintf(stderr, "    %d\n",
+                                       BM_elem_index_get((BMFace*)BLI_ghashIterator_getKey(&gh_iter)));
+               fprintf(stderr, "  unique verts:\n");
+               GHASH_ITER (gh_iter, node->bm_unique_verts)
+                       fprintf(stderr, "    %d\n",
+                                       BM_elem_index_get((BMVert*)BLI_ghashIterator_getKey(&gh_iter)));
+               fprintf(stderr, "  other verts:\n");
+               GHASH_ITER (gh_iter, node->bm_other_verts)
+                       fprintf(stderr, "    %d\n",
+                                       BM_elem_index_get((BMVert*)BLI_ghashIterator_getKey(&gh_iter)));
+       }
+}
+
+void print_flag_factors(int flag)
+{
+       int i;
+       printf("flag=0x%x:\n", flag);
+       for (i = 0; i < 32; i++) {
+               if (flag & (1 << i)) {
+                       printf("  %d (1 << %d)\n", 1 << i, i);
+               }
+       }
+}
+
+void pbvh_bmesh_verify(PBVH *bvh)
+{
+       GHashIterator gh_iter;
+       int i;
+
+       /* Check faces */
+       BLI_assert(bvh->bm->totface == BLI_ghash_size(bvh->bm_face_to_node));
+       GHASH_ITER (gh_iter, bvh->bm_face_to_node) {
+               BMIter bm_iter;
+               BMVert *v;
+               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+               void *nip = BLI_ghashIterator_getValue(&gh_iter);
+               int ni = GET_INT_FROM_POINTER(nip);
+               PBVHNode *n = &bvh->nodes[ni];
+
+               /* Check that the face's node is a leaf */
+               BLI_assert(n->flag & PBVH_Leaf);
+
+               /* Check that the face's node knows it owns the face */
+               BLI_assert(BLI_ghash_haskey(n->bm_faces, f));
+
+               /* Check the face's vertices... */
+               BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
+                       PBVHNode *nv;
+
+                       /* Check that the vertex is in the node */
+                       BLI_assert(BLI_ghash_haskey(n->bm_unique_verts, v) ^
+                                          BLI_ghash_haskey(n->bm_other_verts, v));
+
+                       /* Check that the vertex has a node owner */
+                       nv = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
+
+                       /* Check that the vertex's node knows it owns the vert */
+                       BLI_assert(BLI_ghash_haskey(nv->bm_unique_verts, v));
+
+                       /* Check that the vertex isn't duplicated as an 'other' vert */
+                       BLI_assert(!BLI_ghash_haskey(nv->bm_other_verts, v));
+               }
+       }
+
+       /* Check verts */
+       BLI_assert(bvh->bm->totvert == BLI_ghash_size(bvh->bm_vert_to_node));
+       GHASH_ITER (gh_iter, bvh->bm_vert_to_node) {
+               BMIter bm_iter;
+               BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
+               BMFace *f;
+               void *nip = BLI_ghashIterator_getValue(&gh_iter);
+               int ni = GET_INT_FROM_POINTER(nip);
+               PBVHNode *n = &bvh->nodes[ni];
+               int found;
+
+               /* Check that the vert's node is a leaf */
+               BLI_assert(n->flag & PBVH_Leaf);
+
+               /* Check that the vert's node knows it owns the vert */
+               BLI_assert(BLI_ghash_haskey(n->bm_unique_verts, v));
+
+               /* Check that the vertex isn't duplicated as an 'other' vert */
+               BLI_assert(!BLI_ghash_haskey(n->bm_other_verts, v));
+
+               /* Check that the vert's node also contains one of the vert's
+                * adjacent faces */
+               BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
+                       if (BLI_ghash_lookup(bvh->bm_face_to_node, f) == nip) {
+                               found = TRUE;
+                               break;
+                       }
+               }
+               BLI_assert(found);
+       }
+
+       /* Check that node elements are recorded in the top level */
+       for (i = 0; i < bvh->totnode; i++) {
+               PBVHNode *n = &bvh->nodes[i];
+               if (n->flag & PBVH_Leaf) {
+                       /* Check for duplicate entries */
+                       /* Slow */
+                       #if 0
+                       bli_ghash_duplicate_key_check(n->bm_faces);
+                       bli_ghash_duplicate_key_check(n->bm_unique_verts);
+                       bli_ghash_duplicate_key_check(n->bm_other_verts);
+                       #endif
+
+                       GHASH_ITER (gh_iter, n->bm_faces) {
+                               BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
+                               void *nip = BLI_ghash_lookup(bvh->bm_face_to_node, f);
+                               BLI_assert(BLI_ghash_haskey(bvh->bm_face_to_node, f));
+                               BLI_assert(GET_INT_FROM_POINTER(nip) == (n - bvh->nodes));
+                       }
+
+                       GHASH_ITER (gh_iter, n->bm_unique_verts) {
+                               BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
+                               void *nip = BLI_ghash_lookup(bvh->bm_vert_to_node, v);
+                               BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
+                               BLI_assert(!BLI_ghash_haskey(n->bm_other_verts, v));
+                               BLI_assert(GET_INT_FROM_POINTER(nip) == (n - bvh->nodes));
+                       }
+
+                       GHASH_ITER (gh_iter, n->bm_other_verts) {
+                               BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
+                               BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
+                               BLI_assert(BM_vert_face_count(v) > 0);
+                       }
+               }
+       }
+}
+
+#endif
index d3539245d11e23875f7788553cff54d07e411920..d8365ce800672e071b1584011afc740224caacaa 100644 (file)
@@ -31,6 +31,8 @@ typedef struct {
        float bmin[3], bmax[3], bcentroid[3];
 } BBC;
 
+/* Note: this structure is getting large, might want to split it into
+ * union'd structs */
 struct PBVHNode {
        /* Opaque handle for drawing code */
        GPU_Buffers *draw_buffers;
@@ -86,7 +88,7 @@ struct PBVHNode {
 
        /* Indicates whether this node is a leaf or not; also used for
         * marking various updates that need to be applied. */
-       PBVHNodeFlags flag : 8;
+       PBVHNodeFlags flag : 16;
 
        /* Used for raycasting: how close bb is to the ray point. */
        float tmin;
@@ -96,10 +98,25 @@ struct PBVHNode {
 
        int proxy_count;
        PBVHProxyNode *proxies;
+
+       /* Dyntopo */
+       GHash *bm_faces;
+       GHash *bm_unique_verts;
+       GHash *bm_other_verts;
+       float (*bm_orco)[3];
+       int (*bm_ortri)[3];
+       int bm_tot_ortri;
 };
 
+typedef enum {
+       PBVH_DYNTOPO_SMOOTH_SHADING = 1
+} PBVHFlags;
+
+typedef struct PBVHBMeshLog PBVHBMeshLog;
+
 struct PBVH {
        PBVHType type;
+       PBVHFlags flags;
 
        PBVHNode *nodes;
        int node_mem_count, totnode;
@@ -136,6 +153,34 @@ struct PBVH {
        int deformed;
 
        int show_diffuse_color;
+
+       /* Dynamic topology */
+       BMesh *bm;
+       GHash *bm_face_to_node;
+       GHash *bm_vert_to_node;
+       float bm_max_edge_len;
+       float bm_min_edge_len;
+
+       struct BMLog *bm_log;
 };
 
+/* pbvh.c */
+void BB_reset(BB *bb);
+void BB_expand(BB *bb, const float co[3]);
+void BB_expand_with_bb(BB *bb, BB *bb2);
+void BBC_update_centroid(BBC *bbc);
+int BB_widest_axis(const BB *bb);
+void pbvh_grow_nodes(PBVH *bvh, int totnode);
+int ray_face_intersection(const float ray_start[3], const float ray_normal[3],
+                                                 const float *t0, const float *t1, const float *t2,
+                                                 const float *t3, float *fdist);
+void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, int totnode, int flag);
+
+/* pbvh_bmesh.c */
+int pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3],
+                                                       const float ray_normal[3], float *dist,
+                                                       int use_original);
+
+void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode);
+
 #endif