[Bf-blender-cvs] [010c10febe4] master: Sculpt: Ensure faces are uniquely assigned to PBVHNodes
Joseph Eagar
noreply at git.blender.org
Sat Oct 15 07:12:58 CEST 2022
Commit: 010c10febe46c1c24ca3e32ee8b03e2da2eea4fe
Author: Joseph Eagar
Date: Fri Oct 14 22:08:36 2022 -0700
Branches: master
https://developer.blender.org/rB010c10febe46c1c24ca3e32ee8b03e2da2eea4fe
Sculpt: Ensure faces are uniquely assigned to PBVHNodes
PBVH_FACES and PBVH_GRIDS do not store faces directly in nodes;
instead they store 'primitives', which are tesselation triangles
for PBVH_FACES and grids (which are per-loop) for PBVH_GRIDS.
Primitives from the same face could sometimes end up in different
PBVH nodes. This is now prevented in two ways:
* All primitives of the same face are given the same boundary
during PBVH build. This prevents them from being swapped
away from each other during partitioning.
* build_sub adjusts the final partition midpoint to fall
between primitives of different faces.
===================================================================
M source/blender/blenkernel/BKE_pbvh.h
M source/blender/blenkernel/intern/paint.cc
M source/blender/blenkernel/intern/pbvh.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 89743f1d2b4..42cd1536dcf 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -267,7 +267,8 @@ void BKE_pbvh_build_grids(PBVH *pbvh,
void **gridfaces,
struct DMFlagMat *flagmats,
unsigned int **grid_hidden,
- struct Mesh *me);
+ struct Mesh *me,
+ struct SubdivCCG *subdiv_ccg);
/**
* Build a PBVH from a BMesh.
*/
diff --git a/source/blender/blenkernel/intern/paint.cc b/source/blender/blenkernel/intern/paint.cc
index d45ce776b64..934cfb3cc46 100644
--- a/source/blender/blenkernel/intern/paint.cc
+++ b/source/blender/blenkernel/intern/paint.cc
@@ -2237,7 +2237,8 @@ static PBVH *build_pbvh_from_ccg(Object *ob, SubdivCCG *subdiv_ccg, bool respect
(void **)subdiv_ccg->grid_faces,
subdiv_ccg->grid_flag_mats,
subdiv_ccg->grid_hidden,
- base_mesh);
+ base_mesh,
+ subdiv_ccg);
pbvh_show_mask_set(pbvh, ob->sculpt->show_mask);
pbvh_show_face_sets_set(pbvh, ob->sculpt->show_face_sets);
return pbvh;
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index b73f0746621..65a906e6580 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -39,8 +39,10 @@
#define LEAF_LIMIT 10000
-//#define PERFCNTRS
+/* Uncomment to test that faces are only assigned to one PBVHNode */
+//#define VALIDATE_UNIQUE_NODE_FACES
+//#define PERFCNTRS
#define STACK_FIXED_DEPTH 100
typedef struct PBVHStack {
@@ -422,6 +424,56 @@ 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)
+{
+ 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--;
+ }
+
+ /* 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]);
+
+ /* 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;
+ }
+
+ mid--;
+ }
+
+ /* 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;
+ }
+
+ mid++;
+ }
+
+ return mid;
+}
+
/* Recursively build a node in the tree
*
* vb is the voxel box around all of the primitives contained in
@@ -478,6 +530,13 @@ static void build_sub(PBVH *pbvh, int node_index, BB *cb, BBC *prim_bbc, int off
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,
@@ -587,6 +646,73 @@ static void pbvh_draw_args_init(PBVH *pbvh, PBVH_GPU_Args *args, PBVHNode *node)
}
}
+#ifdef VALIDATE_UNIQUE_NODE_FACES
+static void pbvh_validate_node_prims(PBVH *pbvh)
+{
+ int totface = 0;
+
+ if (pbvh->header.type == PBVH_BMESH) {
+ return;
+ }
+
+ for (int i = 0; i < pbvh->totnode; i++) {
+ PBVHNode *node = pbvh->nodes + i;
+
+ if (!(node->flag & PBVH_Leaf)) {
+ continue;
+ }
+
+ for (int j = 0; j < node->totprim; j++) {
+ int poly;
+
+ if (pbvh->header.type == PBVH_FACES) {
+ poly = pbvh->looptri[node->prim_indices[j]].poly;
+ }
+ else {
+ poly = BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, node->prim_indices[j]);
+ }
+
+ totface = max_ii(totface, poly + 1);
+ }
+ }
+
+ int *facemap = (int *)MEM_malloc_arrayN(totface, sizeof(*facemap), __func__);
+
+ for (int i = 0; i < totface; i++) {
+ facemap[i] = -1;
+ }
+
+ for (int i = 0; i < pbvh->totnode; i++) {
+ PBVHNode *node = pbvh->nodes + i;
+
+ if (!(node->flag & PBVH_Leaf)) {
+ continue;
+ }
+
+ for (int j = 0; j < node->totprim; j++) {
+ int poly;
+
+ if (pbvh->header.type == PBVH_FACES) {
+ poly = pbvh->looptri[node->prim_indices[j]].poly;
+ }
+ else {
+ poly = BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, node->prim_indices[j]);
+ }
+
+ if (facemap[poly] != -1 && facemap[poly] != i) {
+ printf("%s: error: face spanned multiple nodes (old: %d new: %d)\n",
+ __func__,
+ facemap[poly],
+ i);
+ }
+
+ facemap[poly] = i;
+ }
+ }
+ MEM_SAFE_FREE(facemap);
+}
+#endif
+
void BKE_pbvh_build_mesh(PBVH *pbvh,
Mesh *mesh,
const MPoly *mpoly,
@@ -645,6 +771,32 @@ void BKE_pbvh_build_mesh(PBVH *pbvh,
BB_expand(&cb, bbc->bcentroid);
}
+ /* Ensure all primitives belonging to the same base face
+ * have the same bounds. This is needed to prevent them
+ * from being swapped away from each other inside the partition
+ * array.
+ */
+ for (int i = 0; i < looptri_num; i++) {
+ const MLoopTri *lt = &looptri[i];
+ int poly = lt->poly;
+ BBC *bbc = prim_bbc + i;
+ int j = i + 1;
+
+ while (j < looptri_num && looptri[j].poly == poly) {
+ BBC *bbc2 = prim_bbc + j;
+
+ BB_expand((BB *)bbc, bbc2->bmin);
+ BB_expand((BB *)bbc, bbc2->bmax);
+ j++;
+ }
+
+ j = i + 1;
+ while (j < looptri_num && looptri[j].poly == poly) {
+ prim_bbc[j] = prim_bbc[i];
+ j++;
+ }
+ }
+
if (looptri_num) {
pbvh_build(pbvh, &cb, prim_bbc, looptri_num);
}
@@ -655,6 +807,10 @@ void BKE_pbvh_build_mesh(PBVH *pbvh,
memset(pbvh->vert_bitmap, 0, sizeof(bool) * totvert);
BKE_pbvh_update_active_vcol(pbvh, mesh);
+
+#ifdef VALIDATE_UNIQUE_NODE_FACES
+ pbvh_validate_node_prims(pbvh);
+#endif
}
void BKE_pbvh_build_grids(PBVH *pbvh,
@@ -664,7 +820,8 @@ void BKE_pbvh_build_grids(PBVH *pbvh,
void **gridfaces,
DMFlagMat *flagmats,
BLI_bitmap **grid_hidden,
- Mesh *me)
+ Mesh *me,
+ SubdivCCG *subdiv_ccg)
{
const int gridsize = key->grid_size;
@@ -675,6 +832,7 @@ void BKE_pbvh_build_grids(PBVH *pbvh,
pbvh->totgrid = totgrid;
pbvh->gridkey = *key;
pbvh->grid_hidden = grid_hidden;
+ pbvh->subdiv_ccg = subdiv_ccg;
pbvh->leaf_limit = max_ii(LEAF_LIMIT / (gridsize * gridsize), 1);
/* We need the base mesh attribute layout for PBVH draw. */
@@ -706,11 +864,40 @@ void BKE_pbvh_build_grids(PBVH *pbvh,
BB_expand(&cb, bbc->bcentroid);
}
+ /* Ensure all primitives belonging to the same base face
+ * have the same bounds. This is needed to prevent them
+ * from being swapped away from each other inside the partition
+ * array.
+ */
+ for (int i = 0; i < totgrid; i++) {
+ int poly = BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, i);
+
+ BBC *bbc = prim_bbc + i;
+ int j = i + 1;
+
+ while (j < totgrid && BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, j) == poly) {
+ BBC *bbc2 = prim_bbc + j;
+
+ BB_expand((BB *)bbc, bbc2->bmin);
+ BB_expand((BB *)bbc, bbc2->bmax);
+ j++;
+ }
+
+ j = i + 1;
+ while (j < totgrid && BKE_subdiv_ccg_grid_to_face_index(pbvh->subdiv_ccg, j) == poly) {
+ prim_bbc[j] = prim_bbc[i];
+ j++;
+ }
+ }
+
if (totgrid) {
pbvh_build(pbvh, &cb, prim_bbc, totgrid);
}
MEM_freeN(prim_bbc);
+#ifdef VALIDATE_UNIQUE_NODE_FACES
+ pbvh_validate_node_prims(pbvh);
+#endif
}
PBVH *BKE_pbvh_new(PBVHType type)
More information about the Bf-blender-cvs
mailing list