diff options
| -rw-r--r-- | source/blender/blenkernel/BKE_pbvh.h | 61 | ||||
| -rw-r--r-- | source/blender/blenkernel/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh.c | 81 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh_bmesh.c | 1414 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh_intern.h | 47 |
5 files changed, 1582 insertions, 22 deletions
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h index 5b6acdb9752..4abeed513df 100644 --- a/source/blender/blenkernel/BKE_pbvh.h +++ b/source/blender/blenkernel/BKE_pbvh.h @@ -27,13 +27,18 @@ */ #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 \ } \ diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt index 6d53f9e7dd5..99008309498 100644 --- a/source/blender/blenkernel/CMakeLists.txt +++ b/source/blender/blenkernel/CMakeLists.txt @@ -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 diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index e9009050d4b..6e0209e7683 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -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 index 00000000000..9cc8fd09c73 --- /dev/null +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -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 diff --git a/source/blender/blenkernel/intern/pbvh_intern.h b/source/blender/blenkernel/intern/pbvh_intern.h index d3539245d11..d8365ce8006 100644 --- a/source/blender/blenkernel/intern/pbvh_intern.h +++ b/source/blender/blenkernel/intern/pbvh_intern.h @@ -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 |