diff options
Diffstat (limited to 'source/blender/blenkernel/intern/pbvh.c')
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh.c | 611 |
1 files changed, 307 insertions, 304 deletions
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index 311e928c348..330b5922c9a 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -30,6 +30,7 @@ #include "BLI_math.h" #include "BLI_utildefines.h" #include "BLI_ghash.h" +#include "BLI_task.h" #include "BKE_pbvh.h" #include "BKE_ccg.h" @@ -42,6 +43,8 @@ #include "bmesh.h" +#include "atomic_ops.h" + #include "pbvh_intern.h" #include <limits.h> @@ -52,18 +55,11 @@ #define STACK_FIXED_DEPTH 100 -/* Setting zero so we can catch bugs in OpenMP/PBVH. */ -#ifdef _OPENMP -# ifdef DEBUG -# define PBVH_OMP_LIMIT 0 -# else -# define PBVH_OMP_LIMIT 8 -# endif -#endif +#define PBVH_THREADED_LIMIT 4 typedef struct PBVHStack { PBVHNode *node; - int revisiting; + bool revisiting; } PBVHStack; typedef struct PBVHIter { @@ -87,8 +83,7 @@ void BB_reset(BB *bb) /* Expand the bounding box to include a new coordinate */ void BB_expand(BB *bb, const float co[3]) { - int i; - for (i = 0; i < 3; ++i) { + for (int i = 0; i < 3; ++i) { bb->bmin[i] = min_ff(bb->bmin[i], co[i]); bb->bmax[i] = max_ff(bb->bmax[i], co[i]); } @@ -97,8 +92,7 @@ void BB_expand(BB *bb, const float co[3]) /* Expand the bounding box to include another bounding box */ void BB_expand_with_bb(BB *bb, BB *bb2) { - int i; - for (i = 0; i < 3; ++i) { + for (int i = 0; i < 3; ++i) { bb->bmin[i] = min_ff(bb->bmin[i], bb2->bmin[i]); bb->bmax[i] = max_ff(bb->bmax[i], bb2->bmax[i]); } @@ -108,9 +102,8 @@ void BB_expand_with_bb(BB *bb, BB *bb2) int BB_widest_axis(const BB *bb) { float dim[3]; - int i; - for (i = 0; i < 3; ++i) + for (int i = 0; i < 3; ++i) dim[i] = bb->bmax[i] - bb->bmin[i]; if (dim[0] > dim[1]) { @@ -129,8 +122,7 @@ int BB_widest_axis(const BB *bb) void BBC_update_centroid(BBC *bbc) { - int i; - for (i = 0; i < 3; ++i) + for (int i = 0; i < 3; ++i) bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f; } @@ -170,13 +162,13 @@ static void update_node_vb(PBVH *bvh, PBVHNode *node) // BB_expand(&node->vb, co); //} -static int face_materials_match(const MPoly *f1, const MPoly *f2) +static bool face_materials_match(const MPoly *f1, const MPoly *f2) { return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && (f1->mat_nr == f2->mat_nr)); } -static int grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2) +static bool grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2) { return ((f1->flag & ME_SMOOTH) == (f2->flag & ME_SMOOTH) && (f1->mat_nr == f2->mat_nr)); @@ -254,22 +246,19 @@ static int map_insert_vert(PBVH *bvh, GHash *map, void *key, **value_p; key = SET_INT_IN_POINTER(vertex); - value_p = BLI_ghash_lookup_p(map, key); - - if (value_p == NULL) { - void *value; - if (BLI_BITMAP_TEST(bvh->vert_bitmap, vertex)) { - value = SET_INT_IN_POINTER(~(*face_verts)); - ++(*face_verts); + if (!BLI_ghash_ensure_p(map, key, &value_p)) { + int value_i; + if (BLI_BITMAP_TEST(bvh->vert_bitmap, vertex) == 0) { + BLI_BITMAP_ENABLE(bvh->vert_bitmap, vertex); + value_i = *uniq_verts; + (*uniq_verts)++; } else { - BLI_BITMAP_ENABLE(bvh->vert_bitmap, vertex); - value = SET_INT_IN_POINTER(*uniq_verts); - ++(*uniq_verts); + value_i = ~(*face_verts); + (*face_verts)++; } - - BLI_ghash_insert(map, key, value); - return GET_INT_FROM_POINTER(value); + *value_p = SET_INT_IN_POINTER(value_i); + return value_i; } else { return GET_INT_FROM_POINTER(*value_p); @@ -279,29 +268,24 @@ static int map_insert_vert(PBVH *bvh, GHash *map, /* Find vertices used by the faces in this node and update the draw buffers */ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) { - GHashIterator gh_iter; - GHash *map; - int i, j, totface; bool has_visible = false; - int (*face_vert_indices)[4]; - int *vert_indices; node->uniq_verts = node->face_verts = 0; - totface = node->totprim; + const int totface = node->totprim; /* reserve size is rough guess */ - map = BLI_ghash_int_new_ex("build_mesh_leaf_node gh", 2 * totface); + GHash *map = BLI_ghash_int_new_ex("build_mesh_leaf_node gh", 2 * totface); - face_vert_indices = MEM_callocN(sizeof(int[4]) * totface, - "bvh node face vert indices"); + int (*face_vert_indices)[4] = MEM_callocN(sizeof(int[4]) * totface, + "bvh node face vert indices"); node->face_vert_indices = (const int (*)[4])face_vert_indices; - for (i = 0; i < totface; ++i) { + for (int i = 0; i < totface; ++i) { const MLoopTri *lt = &bvh->looptri[node->prim_indices[i]]; const int sides = 3; - for (j = 0; j < sides; ++j) { + for (int j = 0; j < sides; ++j) { face_vert_indices[i][j] = map_insert_vert(bvh, map, &node->face_verts, &node->uniq_verts, bvh->mloop[lt->tri[j]].v); @@ -312,12 +296,12 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) } } - vert_indices = MEM_callocN(sizeof(int) * - (node->uniq_verts + node->face_verts), - "bvh node vert indices"); + int *vert_indices = MEM_callocN(sizeof(int) * (node->uniq_verts + node->face_verts), + "bvh node vert indices"); node->vert_indices = vert_indices; /* Build the vertex list, unique verts first */ + GHashIterator gh_iter; GHASH_ITER (gh_iter, map) { void *value = BLI_ghashIterator_getValue(&gh_iter); int ndx = GET_INT_FROM_POINTER(value); @@ -329,10 +313,10 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(&gh_iter)); } - for (i = 0; i < totface; ++i) { + for (int i = 0; i < totface; ++i) { const int sides = 3; - for (j = 0; j < sides; ++j) { + for (int j = 0; j < sides; ++j) { if (face_vert_indices[i][j] < 0) face_vert_indices[i][j] = -face_vert_indices[i][j] + @@ -350,10 +334,8 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) static void update_vb(PBVH *bvh, PBVHNode *node, BBC *prim_bbc, int offset, int count) { - int i; - BB_reset(&node->vb); - for (i = offset + count - 1; i >= offset; --i) { + for (int i = offset + count - 1; i >= offset; --i) { BB_expand_with_bb(&node->vb, (BB *)(&prim_bbc[bvh->prim_indices[i]])); } node->orig_vb = node->vb; @@ -364,19 +346,19 @@ int BKE_pbvh_count_grid_quads(BLI_bitmap **grid_hidden, int *grid_indices, int totgrid, int gridsize) { - int gridarea = (gridsize - 1) * (gridsize - 1); - int i, x, y, totquad; + const int gridarea = (gridsize - 1) * (gridsize - 1); + int totquad = 0; /* grid hidden layer is present, so have to check each grid for * visibility */ - for (i = 0, totquad = 0; i < totgrid; i++) { + for (int i = 0; i < totgrid; i++) { const BLI_bitmap *gh = grid_hidden[grid_indices[i]]; if (gh) { /* grid hidden are present, have to check each element */ - for (y = 0; y < gridsize - 1; y++) { - for (x = 0; x < gridsize - 1; x++) { + for (int y = 0; y < gridsize - 1; y++) { + for (int x = 0; x < gridsize - 1; x++) { if (!paint_is_grid_face_hidden(gh, gridsize, x, y)) totquad++; } @@ -418,36 +400,34 @@ static void build_leaf(PBVH *bvh, int node_index, BBC *prim_bbc, /* Return zero if all primitives in the node can be drawn with the * same material (including flat/smooth shading), non-zero otherwise */ -static int leaf_needs_material_split(PBVH *bvh, int offset, int count) +static bool leaf_needs_material_split(PBVH *bvh, int offset, int count) { - int i; - if (count <= 1) - return 0; + return false; if (bvh->looptri) { const MLoopTri *first = &bvh->looptri[bvh->prim_indices[offset]]; const MPoly *mp = &bvh->mpoly[first->poly]; - for (i = offset + count - 1; i > offset; --i) { + for (int i = offset + count - 1; i > offset; --i) { int prim = bvh->prim_indices[i]; const MPoly *mp_other = &bvh->mpoly[bvh->looptri[prim].poly]; if (!face_materials_match(mp, mp_other)) { - return 1; + return true; } } } else { const DMFlagMat *first = &bvh->grid_flag_mats[bvh->prim_indices[offset]]; - for (i = offset + count - 1; i > offset; --i) { + for (int i = offset + count - 1; i > offset; --i) { int prim = bvh->prim_indices[i]; if (!grid_materials_match(first, &bvh->grid_flag_mats[prim])) - return 1; + return true; } } - return 0; + return false; } @@ -465,11 +445,11 @@ static int leaf_needs_material_split(PBVH *bvh, int offset, int count) static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, int offset, int count) { - int i, axis, end, below_leaf_limit; + int end; BB cb_backing; /* Decide whether this is a leaf or not */ - below_leaf_limit = count <= bvh->leaf_limit; + const bool below_leaf_limit = count <= bvh->leaf_limit; if (below_leaf_limit) { if (!leaf_needs_material_split(bvh, offset, count)) { build_leaf(bvh, node_index, prim_bbc, offset, count); @@ -489,10 +469,10 @@ static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, if (!cb) { cb = &cb_backing; BB_reset(cb); - for (i = offset + count - 1; i >= offset; --i) + for (int i = offset + count - 1; i >= offset; --i) BB_expand(cb, prim_bbc[bvh->prim_indices[i]].bcentroid); } - axis = BB_widest_axis(cb); + const int axis = BB_widest_axis(cb); /* Partition primitives along that axis */ end = partition_indices(bvh->prim_indices, @@ -515,15 +495,13 @@ static void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim) { - int i; - if (totprim != bvh->totprim) { bvh->totprim = totprim; if (bvh->nodes) MEM_freeN(bvh->nodes); if (bvh->prim_indices) MEM_freeN(bvh->prim_indices); - bvh->prim_indices = MEM_callocN(sizeof(int) * totprim, + bvh->prim_indices = MEM_mallocN(sizeof(int) * totprim, "bvh prim indices"); - for (i = 0; i < totprim; ++i) + for (int i = 0; i < totprim; ++i) bvh->prim_indices[i] = i; bvh->totnode = 0; if (bvh->node_mem_count < 100) { @@ -538,7 +516,12 @@ static void pbvh_build(PBVH *bvh, BB *cb, BBC *prim_bbc, int totprim) build_sub(bvh, 0, cb, prim_bbc, 0, totprim); } -/* Do a full rebuild with on Mesh data structure */ +/** + * Do a full rebuild with on Mesh data structure. + * + * \note Unlike mpoly/mloop/verts, looptri is **totally owned** by PBVH (which means it may rewrite it if needed, + * see BKE_pbvh_apply_vertCos(). + */ void BKE_pbvh_build_mesh( PBVH *bvh, const MPoly *mpoly, const MLoop *mloop, MVert *verts, int totvert, struct CustomData *vdata, @@ -546,7 +529,6 @@ void BKE_pbvh_build_mesh( { BBC *prim_bbc = NULL; BB cb; - int i, j; bvh->type = PBVH_FACES; bvh->mpoly = mpoly; @@ -563,14 +545,14 @@ void BKE_pbvh_build_mesh( /* For each face, store the AABB and the AABB centroid */ prim_bbc = MEM_mallocN(sizeof(BBC) * looptri_num, "prim_bbc"); - for (i = 0; i < looptri_num; ++i) { + for (int i = 0; i < looptri_num; ++i) { const MLoopTri *lt = &looptri[i]; const int sides = 3; BBC *bbc = prim_bbc + i; BB_reset((BB *)bbc); - for (j = 0; j < sides; ++j) + for (int j = 0; j < sides; ++j) BB_expand((BB *)bbc, verts[bvh->mloop[lt->tri[j]].v].co); BBC_update_centroid(bbc); @@ -589,10 +571,7 @@ void BKE_pbvh_build_mesh( void BKE_pbvh_build_grids(PBVH *bvh, CCGElem **grids, int totgrid, CCGKey *key, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap **grid_hidden) { - BBC *prim_bbc = NULL; - BB cb; - int gridsize = key->grid_size; - int i, j; + const int gridsize = key->grid_size; bvh->type = PBVH_GRIDS; bvh->grids = grids; @@ -603,18 +582,19 @@ void BKE_pbvh_build_grids(PBVH *bvh, CCGElem **grids, bvh->grid_hidden = grid_hidden; bvh->leaf_limit = max_ii(LEAF_LIMIT / ((gridsize - 1) * (gridsize - 1)), 1); + BB cb; BB_reset(&cb); /* For each grid, store the AABB and the AABB centroid */ - prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc"); + BBC *prim_bbc = MEM_mallocN(sizeof(BBC) * totgrid, "prim_bbc"); - for (i = 0; i < totgrid; ++i) { + for (int i = 0; i < totgrid; ++i) { CCGElem *grid = grids[i]; BBC *bbc = prim_bbc + i; BB_reset((BB *)bbc); - for (j = 0; j < gridsize * gridsize; ++j) + for (int j = 0; j < gridsize * gridsize; ++j) BB_expand((BB *)bbc, CCG_elem_offset_co(key, grid, j)); BBC_update_centroid(bbc); @@ -637,11 +617,8 @@ PBVH *BKE_pbvh_new(void) void BKE_pbvh_free(PBVH *bvh) { - PBVHNode *node; - int i; - - for (i = 0; i < bvh->totnode; ++i) { - node = &bvh->nodes[i]; + for (int i = 0; i < bvh->totnode; ++i) { + PBVHNode *node = &bvh->nodes[i]; if (node->flag & PBVH_Leaf) { if (node->draw_buffers) @@ -684,8 +661,7 @@ void BKE_pbvh_free(PBVH *bvh) void BKE_pbvh_free_layer_disp(PBVH *bvh) { - int i; - for (i = 0; i < bvh->totnode; ++i) + for (int i = 0; i < bvh->totnode; ++i) BKE_pbvh_node_layer_disp_free(&bvh->nodes[i]); } @@ -699,7 +675,7 @@ static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BKE_pbvh_SearchCallback s iter->stackspace = STACK_FIXED_DEPTH; iter->stack[0].node = bvh->nodes; - iter->stack[0].revisiting = 0; + iter->stack[0].revisiting = false; iter->stacksize = 1; } @@ -709,7 +685,7 @@ static void pbvh_iter_end(PBVHIter *iter) MEM_freeN(iter->stack); } -static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting) +static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, bool revisiting) { if (UNLIKELY(iter->stacksize == iter->stackspace)) { iter->stackspace *= 2; @@ -730,23 +706,20 @@ static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting) static PBVHNode *pbvh_iter_next(PBVHIter *iter) { - PBVHNode *node; - int revisiting; - /* purpose here is to traverse tree, visiting child nodes before their * parents, this order is necessary for e.g. computing bounding boxes */ while (iter->stacksize) { /* pop node */ iter->stacksize--; - node = iter->stack[iter->stacksize].node; + PBVHNode *node = iter->stack[iter->stacksize].node; /* on a mesh with no faces this can happen * can remove this check if we know meshes have at least 1 face */ if (node == NULL) return NULL; - revisiting = iter->stack[iter->stacksize].revisiting; + bool revisiting = iter->stack[iter->stacksize].revisiting; /* revisiting node already checked */ if (revisiting) @@ -761,11 +734,11 @@ static PBVHNode *pbvh_iter_next(PBVHIter *iter) } else { /* come back later when children are done */ - pbvh_stack_push(iter, node, 1); + pbvh_stack_push(iter, node, true); /* push two child nodes on the stack */ - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0); - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0); + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, false); + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, false); } } @@ -774,12 +747,10 @@ static PBVHNode *pbvh_iter_next(PBVHIter *iter) static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter) { - PBVHNode *node; - while (iter->stacksize) { /* pop node */ iter->stacksize--; - node = iter->stack[iter->stacksize].node; + PBVHNode *node = iter->stack[iter->stacksize].node; /* on a mesh with no faces this can happen * can remove this check if we know meshes have at least 1 face */ @@ -792,8 +763,8 @@ static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter) return node; } else { - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, 0); - pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, 0); + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset + 1, false); + pbvh_stack_push(iter, iter->bvh->nodes + node->children_offset, false); } } @@ -953,14 +924,113 @@ static bool update_search_cb(PBVHNode *node, void *data_v) return true; } +typedef struct PBVHUpdateData { + PBVH *bvh; + PBVHNode **nodes; + int totnode; + + float (*fnors)[3]; + float (*vnors)[3]; + int flag; +} PBVHUpdateData; + +static void pbvh_update_normals_accum_task_cb(void *userdata, const int n) +{ + PBVHUpdateData *data = userdata; + + PBVH *bvh = data->bvh; + PBVHNode *node = data->nodes[n]; + float (*fnors)[3] = data->fnors; + float (*vnors)[3] = data->vnors; + + if ((node->flag & PBVH_UpdateNormals)) { + unsigned int mpoly_prev = UINT_MAX; + float fn[3]; + + const int *faces = node->prim_indices; + const int totface = node->totprim; + + for (int i = 0; i < totface; ++i) { + const MLoopTri *lt = &bvh->looptri[faces[i]]; + const unsigned int vtri[3] = { + bvh->mloop[lt->tri[0]].v, + bvh->mloop[lt->tri[1]].v, + bvh->mloop[lt->tri[2]].v, + }; + const int sides = 3; + + /* Face normal and mask */ + if (lt->poly != mpoly_prev) { + const MPoly *mp = &bvh->mpoly[lt->poly]; + BKE_mesh_calc_poly_normal(mp, &bvh->mloop[mp->loopstart], bvh->verts, fn); + mpoly_prev = lt->poly; + + if (fnors) { + /* We can assume a face is only present in one node ever. */ + copy_v3_v3(fnors[lt->poly], fn); + } + } + + for (int j = sides; j--; ) { + const int v = vtri[j]; + + if (bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) { + /* Note: This avoids `lock, add_v3_v3, unlock` and is five to ten times quicker than a spinlock. + * Not exact equivalent though, since atomicity is only ensured for one component + * of the vector at a time, but here it shall not make any sensible difference. */ + for (int k = 3; k--; ) { + /* Atomic float addition. + * Note that since collision are unlikely, loop will nearly always run once. */ + float oldval, newval; + uint32_t prevval; + do { + oldval = vnors[v][k]; + newval = oldval + fn[k]; + prevval = atomic_cas_uint32( + (uint32_t *)&vnors[v][k], *(uint32_t *)(&oldval), *(uint32_t *)(&newval)); + } while (UNLIKELY(prevval != *(uint32_t *)(&oldval))); + } + } + } + } + } +} + +static void pbvh_update_normals_store_task_cb(void *userdata, const int n) +{ + PBVHUpdateData *data = userdata; + PBVH *bvh = data->bvh; + PBVHNode *node = data->nodes[n]; + float (*vnors)[3] = data->vnors; + + if (node->flag & PBVH_UpdateNormals) { + const int *verts = node->vert_indices; + const int totvert = node->uniq_verts; + + for (int i = 0; i < totvert; ++i) { + const int v = verts[i]; + MVert *mvert = &bvh->verts[v]; + + /* mvert is shared between nodes, hence between threads. */ + if (atomic_fetch_and_and_uint8( + (uint8_t *)&mvert->flag, (uint8_t)~ME_VERT_PBVH_UPDATE) & ME_VERT_PBVH_UPDATE) + { + normalize_v3(vnors[v]); + normal_float_to_short_v3(mvert->no, vnors[v]); + } + } + + node->flag &= ~PBVH_UpdateNormals; + } +} + static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, - int totnode, float (*face_nors)[3]) + int totnode, float (*fnors)[3]) { - float (*vnor)[3]; - int n; + float (*vnors)[3]; if (bvh->type == PBVH_BMESH) { - BLI_assert(face_nors == NULL); + BLI_assert(fnors == NULL); pbvh_bmesh_normals_update(nodes, totnode); return; } @@ -970,7 +1040,7 @@ static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, /* could be per node to save some memory, but also means * we have to store for each vertex which node it is in */ - vnor = MEM_callocN(sizeof(float) * 3 * bvh->totvert, "bvh temp vnors"); + vnors = MEM_callocN(sizeof(*vnors) * bvh->totvert, __func__); /* subtle assumptions: * - We know that for all edited vertices, the nodes with faces @@ -982,118 +1052,53 @@ static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, * can only update vertices marked with ME_VERT_PBVH_UPDATE. */ -#pragma omp parallel for private(n) schedule(static) if (totnode > PBVH_OMP_LIMIT) - for (n = 0; n < totnode; n++) { - PBVHNode *node = nodes[n]; + PBVHUpdateData data = { + .bvh = bvh, .nodes = nodes, + .fnors = fnors, .vnors = vnors, + }; - if ((node->flag & PBVH_UpdateNormals)) { - int i, j, totface, *faces; - unsigned int mpoly_prev = UINT_MAX; - float fn[3]; - - faces = node->prim_indices; - totface = node->totprim; - - for (i = 0; i < totface; ++i) { - const MLoopTri *lt = &bvh->looptri[faces[i]]; - const unsigned int vtri[3] = { - bvh->mloop[lt->tri[0]].v, - bvh->mloop[lt->tri[1]].v, - bvh->mloop[lt->tri[2]].v, - }; - const int sides = 3; - - /* Face normal and mask */ - if (lt->poly != mpoly_prev) { - const MPoly *mp = &bvh->mpoly[lt->poly]; - BKE_mesh_calc_poly_normal(mp, &bvh->mloop[mp->loopstart], bvh->verts, fn); - mpoly_prev = lt->poly; - - if (face_nors) { - copy_v3_v3(face_nors[lt->poly], fn); - } - } + BLI_task_parallel_range(0, totnode, &data, pbvh_update_normals_accum_task_cb, totnode > PBVH_THREADED_LIMIT); - for (j = 0; j < sides; ++j) { - int v = vtri[j]; - - if (bvh->verts[v].flag & ME_VERT_PBVH_UPDATE) { - /* this seems like it could be very slow but profile - * does not show this, so just leave it for now? */ -#pragma omp atomic - vnor[v][0] += fn[0]; -#pragma omp atomic - vnor[v][1] += fn[1]; -#pragma omp atomic - vnor[v][2] += fn[2]; - } - } - } - } - } + BLI_task_parallel_range(0, totnode, &data, pbvh_update_normals_store_task_cb, totnode > PBVH_THREADED_LIMIT); -#pragma omp parallel for private(n) schedule(static) if (totnode > PBVH_OMP_LIMIT) - for (n = 0; n < totnode; n++) { - PBVHNode *node = nodes[n]; - - if (node->flag & PBVH_UpdateNormals) { - const int *verts; - int i, totvert; - - verts = node->vert_indices; - totvert = node->uniq_verts; - - for (i = 0; i < totvert; ++i) { - const int v = verts[i]; - MVert *mvert = &bvh->verts[v]; + MEM_freeN(vnors); +} - if (mvert->flag & ME_VERT_PBVH_UPDATE) { - float no[3]; +static void pbvh_update_BB_redraw_task_cb(void *userdata, const int n) +{ + PBVHUpdateData *data = userdata; + PBVH *bvh = data->bvh; + PBVHNode *node = data->nodes[n]; + const int flag = data->flag; - copy_v3_v3(no, vnor[v]); - normalize_v3(no); - normal_float_to_short_v3(mvert->no, no); + if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB)) + /* don't clear flag yet, leave it for flushing later */ + /* Note that bvh usage is read-only here, so no need to thread-protect it. */ + update_node_vb(bvh, node); - mvert->flag &= ~ME_VERT_PBVH_UPDATE; - } - } + if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB)) + node->orig_vb = node->vb; - node->flag &= ~PBVH_UpdateNormals; - } - } - - MEM_freeN(vnor); + if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw)) + node->flag &= ~PBVH_UpdateRedraw; } void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, int totnode, int flag) { - int n; - /* update BB, redraw flag */ -#pragma omp parallel for private(n) schedule(static) if (totnode > PBVH_OMP_LIMIT) - for (n = 0; n < totnode; n++) { - PBVHNode *node = nodes[n]; - - if ((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB)) - /* don't clear flag yet, leave it for flushing later */ - update_node_vb(bvh, node); + PBVHUpdateData data = { + .bvh = bvh, .nodes = nodes, + .flag = flag, + }; - if ((flag & PBVH_UpdateOriginalBB) && (node->flag & PBVH_UpdateOriginalBB)) - node->orig_vb = node->vb; - - if ((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw)) - node->flag &= ~PBVH_UpdateRedraw; - } + BLI_task_parallel_range(0, totnode, &data, pbvh_update_BB_redraw_task_cb, totnode > PBVH_THREADED_LIMIT); } static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) { - PBVHNode *node; - int n; - /* can't be done in parallel with OpenGL */ - for (n = 0; n < totnode; n++) { - node = nodes[n]; + for (int n = 0; n < totnode; n++) { + PBVHNode *node = nodes[n]; if (node->flag & PBVH_RebuildDrawBuffers) { GPU_free_pbvh_buffers(node->draw_buffers); @@ -1116,8 +1121,7 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) break; case PBVH_BMESH: node->draw_buffers = - GPU_build_bmesh_pbvh_buffers(bvh->flags & - PBVH_DYNTOPO_SMOOTH_SHADING); + GPU_build_bmesh_pbvh_buffers(bvh->flags & PBVH_DYNTOPO_SMOOTH_SHADING); break; } @@ -1163,13 +1167,10 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) static void pbvh_draw_BB(PBVH *bvh) { - PBVHNode *node; - int a; - GPU_init_draw_pbvh_BB(); - for (a = 0; a < bvh->totnode; a++) { - node = &bvh->nodes[a]; + for (int a = 0; a < bvh->totnode; a++) { + PBVHNode *node = &bvh->nodes[a]; GPU_draw_pbvh_BB(node->vb.bmin, node->vb.bmax, ((node->flag & PBVH_Leaf) != 0)); } @@ -1208,19 +1209,19 @@ static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag) return update; } -void BKE_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3]) +void BKE_pbvh_update(PBVH *bvh, int flag, float (*fnors)[3]) { - PBVHNode **nodes; - int totnode; - if (!bvh->nodes) return; + PBVHNode **nodes; + int totnode; + BKE_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(flag), &nodes, &totnode); if (flag & PBVH_UpdateNormals) - pbvh_update_normals(bvh, nodes, totnode, face_nors); + pbvh_update_normals(bvh, nodes, totnode, fnors); if (flag & (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw)) pbvh_update_BB_redraw(bvh, nodes, totnode, flag); @@ -1251,26 +1252,19 @@ void BKE_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]) copy_v3_v3(bb_max, bb.bmax); } -void BKE_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***r_gridfaces, int *r_totface) +void BKE_pbvh_get_grid_updates(PBVH *bvh, bool clear, void ***r_gridfaces, int *r_totface) { - PBVHIter iter; + GSet *face_set = BLI_gset_ptr_new(__func__); PBVHNode *node; - GSetIterator gs_iter; - GSet *face_set; - void *face, **faces; - unsigned i; - int tot; - - face_set = BLI_gset_ptr_new(__func__); + PBVHIter iter; pbvh_iter_begin(&iter, bvh, NULL, NULL); while ((node = pbvh_iter_next(&iter))) { if (node->flag & PBVH_UpdateNormals) { - for (i = 0; i < node->totprim; ++i) { - face = bvh->gridfaces[node->prim_indices[i]]; - if (!BLI_gset_haskey(face_set, face)) - BLI_gset_insert(face_set, face); + for (unsigned i = 0; i < node->totprim; ++i) { + void *face = bvh->gridfaces[node->prim_indices[i]]; + BLI_gset_add(face_set, face); } if (clear) @@ -1280,7 +1274,7 @@ void BKE_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***r_gridfaces, int *r pbvh_iter_end(&iter); - tot = BLI_gset_size(face_set); + const int tot = BLI_gset_size(face_set); if (tot == 0) { *r_totface = 0; *r_gridfaces = NULL; @@ -1288,8 +1282,10 @@ void BKE_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***r_gridfaces, int *r return; } - faces = MEM_mallocN(sizeof(*faces) * tot, "PBVH Grid Faces"); + void **faces = MEM_mallocN(sizeof(*faces) * tot, "PBVH Grid Faces"); + GSetIterator gs_iter; + int i; GSET_ITER_INDEX (gs_iter, face_set, i) { faces[i] = BLI_gsetIterator_getKey(&gs_iter); } @@ -1474,10 +1470,34 @@ void BKE_pbvh_node_get_bm_orco_data( *r_orco_coords = node->bm_orco; } +/** + * \note doing a full search on all vertices here seems expensive, + * however this is important to avoid having to recalculate boundbox & sync the buffers to the GPU + * (which is far more expensive!) See: T47232. + */ +bool BKE_pbvh_node_vert_update_check_any(PBVH *bvh, PBVHNode *node) +{ + BLI_assert(bvh->type == PBVH_FACES); + const int *verts = node->vert_indices; + const int totvert = node->uniq_verts + node->face_verts; + + for (int i = 0; i < totvert; ++i) { + const int v = verts[i]; + const MVert *mvert = &bvh->verts[v]; + + if (mvert->flag & ME_VERT_PBVH_UPDATE) { + return true; + } + } + + return false; +} + + /********************************* Raycast ***********************************/ typedef struct { - IsectRayAABBData ray; + struct IsectRayAABB_Precalc ray; bool original; } RaycastData; @@ -1491,7 +1511,7 @@ static bool ray_aabb_intersect(PBVHNode *node, void *data_v) else BKE_pbvh_node_get_BB(node, bb_min, bb_max); - return isect_ray_aabb(&rcd->ray, bb_min, bb_max, &node->tmin); + return isect_ray_aabb_v3(&rcd->ray, bb_min, bb_max, &node->tmin); } void BKE_pbvh_raycast( @@ -1501,7 +1521,7 @@ void BKE_pbvh_raycast( { RaycastData rcd; - isect_ray_aabb_initialize(&rcd.ray, ray_start, ray_normal); + isect_ray_aabb_v3_precalc(&rcd.ray, ray_start, ray_normal); rcd.original = original; BKE_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data); @@ -1589,12 +1609,11 @@ static bool pbvh_grids_node_raycast( const float ray_start[3], const float ray_normal[3], float *dist) { - int totgrid = node->totprim; - int gridsize = bvh->gridkey.grid_size; - int i, x, y; + const int totgrid = node->totprim; + const int gridsize = bvh->gridkey.grid_size; bool hit = false; - for (i = 0; i < totgrid; ++i) { + for (int i = 0; i < totgrid; ++i) { CCGElem *grid = bvh->grids[node->prim_indices[i]]; BLI_bitmap *gh; @@ -1603,8 +1622,8 @@ static bool pbvh_grids_node_raycast( gh = bvh->grid_hidden[node->prim_indices[i]]; - for (y = 0; y < gridsize - 1; ++y) { - for (x = 0; x < gridsize - 1; ++x) { + for (int y = 0; y < gridsize - 1; ++y) { + for (int x = 0; x < gridsize - 1; ++x) { /* check if grid face is hidden */ if (gh) { if (paint_is_grid_face_hidden(gh, gridsize, x, y)) @@ -1640,14 +1659,14 @@ static bool pbvh_grids_node_raycast( } bool BKE_pbvh_node_raycast( - PBVH *bvh, PBVHNode *node, float (*origco)[3], int use_origco, + PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco, const float ray_start[3], const float ray_normal[3], float *dist) { bool hit = false; if (node->flag & PBVH_FullyHidden) - return 0; + return false; switch (bvh->type) { case PBVH_FACES: @@ -1676,7 +1695,7 @@ void BKE_pbvh_raycast_project_ray_root( if (bvh->nodes) { float rootmin_start, rootmin_end; float bb_min_root[3], bb_max_root[3], bb_center[3], bb_diff[3]; - IsectRayAABBData ray; + struct IsectRayAABB_Precalc ray; float ray_normal_inv[3]; float offset = 1.0f + 1e-3f; float offset_vec[3] = {1e-3f, 1e-3f, 1e-3f}; @@ -1697,15 +1716,15 @@ void BKE_pbvh_raycast_project_ray_root( madd_v3_v3v3fl(bb_min_root, bb_center, bb_diff, -offset); /* first project start ray */ - isect_ray_aabb_initialize(&ray, ray_start, ray_normal); - if (!isect_ray_aabb(&ray, bb_min_root, bb_max_root, &rootmin_start)) + isect_ray_aabb_v3_precalc(&ray, ray_start, ray_normal); + if (!isect_ray_aabb_v3(&ray, bb_min_root, bb_max_root, &rootmin_start)) return; /* then the end ray */ mul_v3_v3fl(ray_normal_inv, ray_normal, -1.0); - isect_ray_aabb_initialize(&ray, ray_end, ray_normal_inv); + isect_ray_aabb_v3_precalc(&ray, ray_end, ray_normal_inv); /* unlikely to fail exiting if entering succeeded, still keep this here */ - if (!isect_ray_aabb(&ray, bb_min_root, bb_max_root, &rootmin_end)) + if (!isect_ray_aabb_v3(&ray, bb_min_root, bb_max_root, &rootmin_end)) return; madd_v3_v3v3fl(ray_start, ray_start, ray_normal, rootmin_start); @@ -1713,9 +1732,6 @@ void BKE_pbvh_raycast_project_ray_root( } } - -//#include "GPU_glew.h" - typedef struct { DMSetMaterial setMaterial; bool wireframe; @@ -1728,18 +1744,19 @@ void BKE_pbvh_node_draw(PBVHNode *node, void *data_v) #if 0 /* XXX: Just some quick code to show leaf nodes in different colors */ - float col[3]; int i; + float col[3]; + float spec[3] = {0.0f, 0.0f, 0.0f}; if (0) { //is_partial) { col[0] = (rand() / (float)RAND_MAX); col[1] = col[2] = 0.6; } else { srand((long long)node); - for (i = 0; i < 3; ++i) + for (int i = 0; i < 3; ++i) col[i] = (rand() / (float)RAND_MAX) * 0.3 + 0.7; } - glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col); + GPU_basic_shader_colors(col, spec, 0, 1.0f); glColor3f(1, 0, 0); #endif @@ -1768,10 +1785,9 @@ static PlaneAABBIsect test_planes_aabb(const float bb_min[3], { float vmin[3], vmax[3]; PlaneAABBIsect ret = ISECT_INSIDE; - int i, axis; - for (i = 0; i < 4; ++i) { - for (axis = 0; axis < 3; ++axis) { + for (int i = 0; i < 4; ++i) { + for (int axis = 0; axis < 3; ++axis) { if (planes[i][axis] > 0) { vmin[axis] = bb_min[axis]; vmax[axis] = bb_max[axis]; @@ -1816,20 +1832,20 @@ static void pbvh_node_check_diffuse_changed(PBVH *bvh, PBVHNode *node) node->flag |= PBVH_UpdateDrawBuffers; } -void BKE_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], +void BKE_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*fnors)[3], DMSetMaterial setMaterial, bool wireframe, bool fast) { PBVHNodeDrawData draw_data = {setMaterial, wireframe, fast}; PBVHNode **nodes; - int a, totnode; + int totnode; - for (a = 0; a < bvh->totnode; a++) + for (int a = 0; a < bvh->totnode; a++) pbvh_node_check_diffuse_changed(bvh, &bvh->nodes[a]); BKE_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals | PBVH_UpdateDrawBuffers), &nodes, &totnode); - pbvh_update_normals(bvh, nodes, totnode, face_nors); + pbvh_update_normals(bvh, nodes, totnode, fnors); pbvh_update_draw_buffers(bvh, nodes, totnode); if (nodes) MEM_freeN(nodes); @@ -1849,8 +1865,6 @@ void BKE_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], void BKE_pbvh_grids_update(PBVH *bvh, CCGElem **grids, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap **grid_hidden) { - int a; - bvh->grids = grids; bvh->gridfaces = gridfaces; @@ -1858,7 +1872,7 @@ void BKE_pbvh_grids_update(PBVH *bvh, CCGElem **grids, void **gridfaces, bvh->grid_flag_mats = flagmats; bvh->grid_hidden = grid_hidden; - for (a = 0; a < bvh->totnode; ++a) + for (int a = 0; a < bvh->totnode; ++a) BKE_pbvh_node_mark_rebuild_draw(&bvh->nodes[a]); } } @@ -1885,17 +1899,15 @@ void BKE_pbvh_node_layer_disp_free(PBVHNode *node) float (*BKE_pbvh_get_vertCos(PBVH *pbvh))[3] { - int a; float (*vertCos)[3] = NULL; if (pbvh->verts) { - float *co; MVert *mvert = pbvh->verts; vertCos = MEM_callocN(3 * pbvh->totvert * sizeof(float), "BKE_pbvh_get_vertCoords"); - co = (float *)vertCos; + float *co = (float *)vertCos; - for (a = 0; a < pbvh->totvert; a++, mvert++, co += 3) { + for (int a = 0; a < pbvh->totvert; a++, mvert++, co += 3) { copy_v3_v3(co, mvert->co); } } @@ -1905,8 +1917,6 @@ float (*BKE_pbvh_get_vertCos(PBVH *pbvh))[3] void BKE_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) { - int a; - if (!pbvh->deformed) { if (pbvh->verts) { /* if pbvh is not already deformed, verts/faces points to the */ @@ -1914,18 +1924,21 @@ void BKE_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) /* unneeded deformation -- duplicate verts/faces to avoid this */ pbvh->verts = MEM_dupallocN(pbvh->verts); - pbvh->looptri = MEM_dupallocN(pbvh->looptri); + /* No need to dupalloc pbvh->looptri, this one is 'totally owned' by pbvh, it's never some mesh data. */ - pbvh->deformed = 1; + pbvh->deformed = true; } } if (pbvh->verts) { MVert *mvert = pbvh->verts; /* copy new verts coords */ - for (a = 0; a < pbvh->totvert; ++a, ++mvert) { - copy_v3_v3(mvert->co, vertCos[a]); - mvert->flag |= ME_VERT_PBVH_UPDATE; + for (int a = 0; a < pbvh->totvert; ++a, ++mvert) { + /* no need for float comparison here (memory is exactly equal or not) */ + if (memcmp(mvert->co, vertCos[a], sizeof(float[3])) != 0) { + copy_v3_v3(mvert->co, vertCos[a]); + mvert->flag |= ME_VERT_PBVH_UPDATE; + } } /* coordinates are new -- normals should also be updated */ @@ -1935,7 +1948,7 @@ void BKE_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) pbvh->looptri, pbvh->totprim, NULL); - for (a = 0; a < pbvh->totnode; ++a) + for (int a = 0; a < pbvh->totnode; ++a) BKE_pbvh_node_mark_update(&pbvh->nodes[a]); BKE_pbvh_update(pbvh, PBVH_UpdateBB, NULL); @@ -1954,51 +1967,41 @@ PBVHProxyNode *BKE_pbvh_node_add_proxy(PBVH *bvh, PBVHNode *node) { int index, totverts; -#pragma omp critical - { - - index = node->proxy_count; + index = node->proxy_count; - node->proxy_count++; + node->proxy_count++; - if (node->proxies) - node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode)); - else - node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy"); + if (node->proxies) + node->proxies = MEM_reallocN(node->proxies, node->proxy_count * sizeof(PBVHProxyNode)); + else + node->proxies = MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy"); - BKE_pbvh_node_num_verts(bvh, node, &totverts, NULL); - node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co"); - } + BKE_pbvh_node_num_verts(bvh, node, &totverts, NULL); + node->proxies[index].co = MEM_callocN(sizeof(float[3]) * totverts, "PBVHNodeProxy.co"); return node->proxies + index; } void BKE_pbvh_node_free_proxies(PBVHNode *node) { -#pragma omp critical - { - int p; - - for (p = 0; p < node->proxy_count; p++) { - MEM_freeN(node->proxies[p].co); - node->proxies[p].co = NULL; - } + for (int p = 0; p < node->proxy_count; p++) { + MEM_freeN(node->proxies[p].co); + node->proxies[p].co = NULL; + } - MEM_freeN(node->proxies); - node->proxies = NULL; + MEM_freeN(node->proxies); + node->proxies = NULL; - node->proxy_count = 0; - } + node->proxy_count = 0; } void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot) { - PBVHNode **array = NULL, *node; + PBVHNode **array = NULL; int tot = 0, space = 0; - int n; - for (n = 0; n < pbvh->totnode; n++) { - node = pbvh->nodes + n; + for (int n = 0; n < pbvh->totnode; n++) { + PBVHNode *node = pbvh->nodes + n; if (node->proxy_count > 0) { if (tot == space) { |