Commit: 4aac5b92c1bbef77edaa50f460cba8350c56eaea Author: Joseph Eagar Date: Wed Nov 30 13:16:17 2022 -0800 Branches: master https://developer.blender.org/rB4aac5b92c1bbef77edaa50f460cba8350c56eaea
Sculpt: Fix T102824: broken face primitive partitioning in pbvh nodes The code I wrote to group triangles or multires quads that belonging to single faces into single PBVH nodes had edge cases that failed. The code is now much simpler and simply assigns groups of primitives to nodes. =================================================================== M source/blender/blenkernel/intern/pbvh.c M source/blender/editors/sculpt_paint/sculpt_ops.c =================================================================== diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index 145ceb143ea..0322b7135cb 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -39,6 +39,11 @@ #define LEAF_LIMIT 10000 +/* Uncomment to test if triangles of the same face are + * properly clustered into single nodes. + */ +//#define TEST_PBVH_FACE_SPLIT + /* Uncomment to test that faces are only assigned to one PBVHNode */ //#define VALIDATE_UNIQUE_NODE_FACES @@ -164,24 +169,65 @@ static bool grid_materials_match(const DMFlagMat *f1, const DMFlagMat *f2) /* Adapted from BLI_kdopbvh.c */ /* Returns the index of the first element on the right of the partition */ -static int partition_indices(int *prim_indices, int lo, int hi, int axis, float mid, BBC *prim_bbc) +static int partition_indices_faces(int *prim_indices, + int *prim_scratch, + int lo, + int hi, + int axis, + float mid, + BBC *prim_bbc, + const MLoopTri *looptri, + const MPoly *mpoly) { - int i = lo, j = hi; - for (;;) { - for (; prim_bbc[prim_indices[i]].bcentroid[axis] < mid; i++) { - /* pass */ - } - for (; mid < prim_bbc[prim_indices[j]].bcentroid[axis]; j--) { - /* pass */ - } + for (int i = lo; i < hi; i++) { + prim_scratch[i - lo] = prim_indices[i]; + } - if (!(i < j)) { - return i; + int lo2 = lo, hi2 = hi - 1; + int i1 = lo, i2 = 0; + + while (i1 < hi) { + int poly = looptri[prim_scratch[i2]].poly; + bool side = prim_bbc[prim_scratch[i2]].bcentroid[axis] >= mid; + + while (i1 < hi && looptri[prim_scratch[i2]].poly == poly) { + prim_indices[side ? hi2-- : lo2++] = prim_scratch[i2]; + i1++; + i2++; } + } - SWAP(int, prim_indices[i], prim_indices[j]); - i++; + return lo2; +} + +static int partition_indices_grids(int *prim_indices, + int *prim_scratch, + int lo, + int hi, + int axis, + float mid, + BBC *prim_bbc, + SubdivCCG *subdiv_ccg) +{ + for (int i = lo; i < hi; i++) { + prim_scratch[i - lo] = prim_indices[i]; + } + + int lo2 = lo, hi2 = hi - 1; + int i1 = lo, i2 = 0; + + while (i1 < hi) { + int poly = BKE_subdiv_ccg_grid_to_face_index(subdiv_ccg, prim_scratch[i2]); + bool side = prim_bbc[prim_scratch[i2]].bcentroid[axis] >= mid; + + while (i1 < hi && BKE_subdiv_ccg_grid_to_face_index(subdiv_ccg, prim_scratch[i2]) == poly) { + prim_indices[side ? hi2-- : lo2++] = prim_scratch[i2]; + i1++; + i2++; + } } + + return lo2; } /* Returns the index of the first element on the right of the partition */ @@ -424,55 +470,53 @@ static bool leaf_needs_material_split(PBVH *pbvh, int offset, int count) return false; } -static int adjust_partition_faces(PBVH *pbvh, int offset, int mid, int count) +#ifdef TEST_PBVH_FACE_SPLIT +static void test_face_boundaries(PBVH *pbvh) { - int poly = pbvh->looptri[pbvh->prim_indices[mid]].poly; - - /* Scan backwards. */ - while (mid > offset + 2) { /* First node should have at least 1 primitive */ - if (pbvh->looptri[pbvh->prim_indices[mid - 1]].poly != poly) { - return mid; - } - - mid--; + int faces_num = BKE_pbvh_num_faces(pbvh); + int *node_map = MEM_calloc_arrayN(faces_num, sizeof(int), __func__); + for (int i = 0; i < faces_num; i++) { + node_map[i] = -1; } - /* If that didn't work try scanning forward. */ - while (mid < pbvh->totprim + count) { - if (pbvh->looptri[pbvh->prim_indices[mid]].poly != poly) { - break; - } - - mid++; - } - - return mid; -} - -static int adjust_partition_grids(PBVH *pbvh, int offset, int mid, int count) -{ - int poly = BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, pbvh->prim_indices[mid]); + for (int i = 0; i < pbvh->totnode; i++) { + PBVHNode *node = pbvh->nodes + i; - /* Scan backwards. */ - while (mid > offset + 2) { /* First node should have at least 1 primitive */ - if (BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, pbvh->prim_indices[mid - 1]) != poly) { - return mid; + if (!(node->flag & PBVH_Leaf)) { + continue; } - mid--; - } + switch (BKE_pbvh_type(pbvh)) { + case PBVH_FACES: { + for (int j = 0; j < node->totprim; j++) { + int poly = pbvh->looptri[node->prim_indices[j]].poly; + + if (node_map[poly] >= 0 && node_map[poly] != i) { + int old_i = node_map[poly]; + int prim_i = node->prim_indices - pbvh->prim_indices + j; + + printf("PBVH split error; poly: %d, prim_i: %d, node1: %d, node2: %d, totprim: %d\n", + poly, + prim_i, + old_i, + i, + node->totprim); + } - /* If that didn't work try scanning forward. */ - while (mid < pbvh->totprim + count) { - if (BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, pbvh->prim_indices[mid]) != poly) { - break; + node_map[poly] = i; + } + break; + } + case PBVH_GRIDS: + break; + case PBVH_BMESH: + break; } - - mid++; } - return mid; + MEM_SAFE_FREE(node_map); } +#endif /* Recursively build a node in the tree * @@ -485,16 +529,32 @@ static int adjust_partition_grids(PBVH *pbvh, int offset, int mid, int count) * offset and start indicate a range in the array of primitive indices */ -static void build_sub(PBVH *pbvh, int node_index, BB *cb, BBC *prim_bbc, int offset, int count) +static void build_sub(PBVH *pbvh, + int node_index, + BB *cb, + BBC *prim_bbc, + int offset, + int count, + int *prim_scratch, + int depth) { int end; BB cb_backing; + if (!prim_scratch) { + prim_scratch = MEM_malloc_arrayN(pbvh->totprim, sizeof(int), __func__); + } + /* Decide whether this is a leaf or not */ - const bool below_leaf_limit = count <= pbvh->leaf_limit; + const bool below_leaf_limit = count <= pbvh->leaf_limit || depth == STACK_FIXED_DEPTH - 1; if (below_leaf_limit) { if (!leaf_needs_material_split(pbvh, offset, count)) { build_leaf(pbvh, node_index, prim_bbc, offset, count); + + if (node_index == 0) { + MEM_SAFE_FREE(prim_scratch); + } + return; } } @@ -518,33 +578,54 @@ static void build_sub(PBVH *pbvh, int node_index, BB *cb, BBC *prim_bbc, int off const int axis = BB_widest_axis(cb); /* Partition primitives along that axis */ - end = partition_indices(pbvh->prim_indices, - offset, - offset + count - 1, - axis, - (cb->bmax[axis] + cb->bmin[axis]) * 0.5f, - prim_bbc); + if (pbvh->header.type == PBVH_FACES) { + end = partition_indices_faces(pbvh->prim_indices, + prim_scratch, + offset, + offset + count, + axis, + (cb->bmax[axis] + cb->bmin[axis]) * 0.5f, + prim_bbc, + pbvh->looptri, + pbvh->mpoly); + } + else { + end = partition_indices_grids(pbvh->prim_indices, + prim_scratch, + offset, + offset + count, + axis, + (cb->bmax[axis] + cb->bmin[axis]) * 0.5f, + prim_bbc, + pbvh->subdiv_ccg); + } } else { /* Partition primitives by material */ end = partition_indices_material(pbvh, offset, offset + count - 1); } - if (pbvh->header.type == PBVH_FACES) { - end = adjust_partition_faces(pbvh, offset, end, count); - } - else { - end = adjust_partition_grids(pbvh, offset, end, count); - } - /* Build children */ - build_sub(pbvh, pbvh->nodes[node_index].children_offset, NULL, prim_bbc, offset, end - offset); + build_sub(pbvh, + pbvh->nodes[node_index].children_offset, + NULL, + prim_bbc, + offset, + end - offset, + prim_scratch, + depth + 1); build_sub(pbvh, pbvh->nodes[node_index].children_offset + 1, NULL, prim_bbc, end, - offset + count - end); + offset + count - end, + prim_scratch, + depth + 1); + + if (node_index == 0) { + MEM_SAFE_FREE(prim_scratch); + } } static void pbvh_build(PBVH *pbvh, BB *cb, BBC *prim_bbc, int totprim) @@ -569,7 +650,7 @@ static void pbvh_build(PBVH *pbvh, BB *cb, BBC *prim_bbc, int totprim) } pbvh->totnode = 1; - build_sub(pbvh, 0, cb, prim_bbc, 0, totprim); + build_sub(pbvh, 0, cb, prim_bbc, 0, totprim, NULL, 0); } static void pbvh_draw_args_init(PBVH *pbvh, PBVH_GPU_Args *args, PBVHNode *node) @@ -742,7 +823,16 @@ void BKE_pbvh_build_mesh(PBVH *pbvh, pbvh->hide_vert = (bool *)CustomData_get_layer_named(&mesh->vdata, CD_PROP_BOOL, ".hide_vert"); pbvh->vert_bitmap = MEM_calloc_arrayN(totvert, sizeof(bool), "bvh->vert_bitmap"); pbvh->totvert = totvert; + +#ifdef TEST_PBVH_FACE_SPLIT + /* Use lower limit to increase probability of + * edge cases. + */ + pbvh->leaf_limit = 100; +#else pbvh->leaf_limit = LEAF_LIMIT; +#endif + pbvh->vdata = vdata; pbvh->ldata = ldata; pbvh->pdata = pdata; @@ -772 @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org List details, subscription details or unsubscribe: https://lists.blender.org/mailman/listinfo/bf-blender-cvs