From 521e724eddc9bfcc3f4aaeac184ae6974bb922a4 Mon Sep 17 00:00:00 2001 From: Nicholas Bishop Date: Wed, 14 Mar 2012 06:32:03 +0000 Subject: Skip hidden elements in PBVH iterator, raycast, and drawing. --- source/blender/blenkernel/BKE_multires.h | 11 +- source/blender/blenkernel/BKE_subsurf.h | 10 +- source/blender/blenkernel/intern/multires.c | 239 +++++++++++++++++++++- source/blender/blenkernel/intern/subsurf_ccg.c | 16 +- source/blender/blenlib/BLI_pbvh.h | 6 +- source/blender/blenlib/intern/pbvh.c | 10 +- source/blender/editors/sculpt_paint/sculpt.c | 3 +- source/blender/editors/sculpt_paint/sculpt_undo.c | 3 +- 8 files changed, 275 insertions(+), 23 deletions(-) (limited to 'source') diff --git a/source/blender/blenkernel/BKE_multires.h b/source/blender/blenkernel/BKE_multires.h index e966991c35a..1816943f32a 100644 --- a/source/blender/blenkernel/BKE_multires.h +++ b/source/blender/blenkernel/BKE_multires.h @@ -32,17 +32,19 @@ * \ingroup bke */ +enum MultiresModifiedFlags; struct DerivedMesh; -struct Mesh; +struct GridHidden; +struct MDisps; struct MFace; +struct Mesh; +struct ModifierData; struct Multires; struct MultiresModifierData; -struct ModifierData; struct Object; struct Scene; -struct MDisps; -void multires_mark_as_modified(struct Object *ob); +void multires_mark_as_modified(struct Object *ob, enum MultiresModifiedFlags flags); void multires_force_update(struct Object *ob); void multires_force_render_update(struct Object *ob); @@ -50,6 +52,7 @@ void multires_force_external_reload(struct Object *ob); /* internal, only called in subsurf_ccg.c */ void multires_modifier_update_mdisps(struct DerivedMesh *dm); +void multires_modifier_update_hidden(struct DerivedMesh *dm); void multiresModifier_set_levels_from_disps(struct MultiresModifierData *mmd, struct Object *ob); diff --git a/source/blender/blenkernel/BKE_subsurf.h b/source/blender/blenkernel/BKE_subsurf.h index 4b80e2ec9df..9c0160025a3 100644 --- a/source/blender/blenkernel/BKE_subsurf.h +++ b/source/blender/blenkernel/BKE_subsurf.h @@ -71,6 +71,14 @@ int ccg_gridsize(int level); of this function to convert to grid coordinates at 'high_level' */ int ccg_factor(int low_level, int high_level); +typedef enum MultiresModifiedFlags { + /* indicates the grids have been sculpted on, so MDisps + have to be updated */ + MULTIRES_COORDS_MODIFIED = 1, + /* indicates elements have been hidden or unhidden */ + MULTIRES_HIDDEN_MODIFIED = 2 +} MultiresModifiedFlags; + /**************************** Internal *****************************/ typedef struct CCGDerivedMesh { @@ -112,7 +120,7 @@ typedef struct CCGDerivedMesh { float (*orco)[3]; struct Object *ob; - int modified; + MultiresModifiedFlags modified_flags; } multires; struct EdgeHash *ehash; diff --git a/source/blender/blenkernel/intern/multires.c b/source/blender/blenkernel/intern/multires.c index b708f33537f..d0900b50f0a 100644 --- a/source/blender/blenkernel/intern/multires.c +++ b/source/blender/blenkernel/intern/multires.c @@ -40,6 +40,7 @@ #include "DNA_object_types.h" #include "DNA_scene_types.h" +#include "BLI_bitmap.h" #include "BLI_blenlib.h" #include "BLI_math.h" #include "BLI_pbvh.h" @@ -76,6 +77,180 @@ typedef enum { static void multires_mvert_to_ss(DerivedMesh *dm, MVert *mvert); static void multiresModifier_disp_run(DerivedMesh *dm, Mesh *me, DerivedMesh *dm2, DispOp op, DMGridData **oldGridData, int totlvl); +/** Grid hiding **/ +static BLI_bitmap multires_mdisps_upsample_hidden(BLI_bitmap lo_hidden, + int lo_level, + int hi_level, + + /* assumed to be at hi_level (or + null) */ + BLI_bitmap prev_hidden) +{ + BLI_bitmap subd; + int hi_gridsize = ccg_gridsize(hi_level); + int lo_gridsize = ccg_gridsize(lo_level); + int yh, xh, xl, yl, xo, yo, hi_ndx; + int offset, factor; + + BLI_assert(lo_level <= hi_level); + + /* fast case */ + if(lo_level == hi_level) + return MEM_dupallocN(lo_hidden); + + subd = BLI_BITMAP_NEW(hi_gridsize * hi_gridsize, "MDisps.hidden upsample"); + + factor = ccg_factor(lo_level, hi_level); + offset = 1 << (hi_level - lo_level - 1); + + /* low-res blocks */ + for(yl = 0; yl < lo_gridsize; yl++) { + for(xl = 0; xl < lo_gridsize; xl++) { + int lo_val = BLI_BITMAP_GET(lo_hidden, yl * lo_gridsize + xl); + + /* high-res blocks */ + for(yo = -offset; yo <= offset; yo++) { + yh = yl * factor + yo; + if(yh < 0 || yh >= hi_gridsize) + continue; + + for(xo = -offset; xo <= offset; xo++) { + xh = xl * factor + xo; + if(xh < 0 || xh >= hi_gridsize) + continue; + + hi_ndx = yh * hi_gridsize + xh; + + if(prev_hidden) { + /* If prev_hidden is available, copy it to + subd, except when the equivalent element in + lo_hidden is different */ + if(lo_val != prev_hidden[hi_ndx]) + BLI_BITMAP_MODIFY(subd, hi_ndx, lo_val); + else + BLI_BITMAP_MODIFY(subd, hi_ndx, prev_hidden[hi_ndx]); + } + else { + BLI_BITMAP_MODIFY(subd, hi_ndx, lo_val); + } + } + } + } + } + + return subd; +} + +static BLI_bitmap multires_mdisps_downsample_hidden(BLI_bitmap old_hidden, + int old_level, + int new_level) +{ + BLI_bitmap new_hidden; + int new_gridsize = ccg_gridsize(new_level); + int old_gridsize = ccg_gridsize(old_level); + int x, y, factor, old_value; + + BLI_assert(new_level <= old_level); + factor = ccg_factor(new_level, old_level); + new_hidden = BLI_BITMAP_NEW(new_gridsize * new_gridsize, + "downsample hidden"); + + + + for(y = 0; y < new_gridsize; y++) { + for(x = 0; x < new_gridsize; x++) { + old_value = BLI_BITMAP_GET(old_hidden, + factor*y*old_gridsize + x*factor); + + BLI_BITMAP_MODIFY(new_hidden, y*new_gridsize + x, old_value); + } + } + + return new_hidden; +} + +static void multires_output_hidden_to_ccgdm(CCGDerivedMesh *ccgdm, + Mesh *me, int level) +{ + const MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS); + BLI_bitmap *grid_hidden = ccgdm->gridHidden; + int *gridOffset; + int i, j; + + gridOffset = ccgdm->dm.getGridOffset(&ccgdm->dm); + + for (i = 0; i < me->totpoly; i++) { + for (j = 0; j < me->mpoly[i].totloop; j++) { + int g = gridOffset[i] + j; + const MDisps *md = &mdisps[g]; + BLI_bitmap gh = md->hidden; + + if (gh) { + grid_hidden[g] = + multires_mdisps_downsample_hidden(gh, md->level, level); + } + } + } +} + +/* subdivide mdisps.hidden if needed (assumes that md.level reflects + the current level of md.hidden) */ +static void multires_mdisps_subdivide_hidden(MDisps *md, int new_level) +{ + BLI_bitmap subd; + + BLI_assert(md->hidden); + + /* nothing to do if already subdivided enough */ + if(md->level >= new_level) + return; + + subd = multires_mdisps_upsample_hidden(md->hidden, + md->level, + new_level, + NULL); + + /* swap in the subdivided data */ + MEM_freeN(md->hidden); + md->hidden = subd; +} + +static MDisps *multires_mdisps_initialize_hidden(Mesh *me, int level) +{ + MDisps *mdisps = CustomData_add_layer(&me->ldata, CD_MDISPS, + CD_CALLOC, 0, me->totloop); + int gridsize = ccg_gridsize(level); + int gridarea = gridsize * gridsize; + int i, j, k; + + for (i = 0; i < me->totpoly; i++) { + int hide = 0; + + for (j = 0; j < me->mpoly[i].totloop; j++) { + if(me->mvert[me->mloop[me->mpoly[i].loopstart + j].v].flag & ME_HIDE) { + hide = 1; + break; + } + } + + if(!hide) + continue; + + for (j = 0; j < me->mpoly[i].totloop; j++) { + MDisps *md = &mdisps[me->mpoly[i].loopstart + j]; + + BLI_assert(!md->hidden); + + md->hidden = BLI_BITMAP_NEW(gridarea, "MDisps.hidden initialize"); + + for(k = 0; k < gridarea; k++) + BLI_BITMAP_SET(md->hidden, k); + } + } + + return mdisps; +} + DerivedMesh *get_multires_dm(Scene *scene, MultiresModifierData *mmd, Object *ob) { ModifierData *md= (ModifierData *)mmd; @@ -156,16 +331,16 @@ static void multires_set_tot_level(Object *ob, MultiresModifierData *mmd, int lv mmd->renderlvl = CLAMPIS(MAX2(mmd->renderlvl, lvl), 0, mmd->totlvl); } -static void multires_dm_mark_as_modified(DerivedMesh *dm) +static void multires_dm_mark_as_modified(DerivedMesh *dm, MultiresModifiedFlags flags) { CCGDerivedMesh *ccgdm = (CCGDerivedMesh*)dm; - ccgdm->multires.modified = 1; + ccgdm->multires.modified_flags |= flags; } -void multires_mark_as_modified(Object *ob) +void multires_mark_as_modified(Object *ob, MultiresModifiedFlags flags) { if (ob && ob->derivedFinal) - multires_dm_mark_as_modified(ob->derivedFinal); + multires_dm_mark_as_modified(ob->derivedFinal, flags); } void multires_force_update(Object *ob) @@ -205,7 +380,7 @@ int multiresModifier_reshapeFromDM(Scene *scene, MultiresModifierData *mmd, if (mrdm && srcdm && mrdm->getNumVerts(mrdm) == srcdm->getNumVerts(srcdm)) { multires_mvert_to_ss(mrdm, srcdm->getVertArray(srcdm)); - multires_dm_mark_as_modified(mrdm); + multires_dm_mark_as_modified(mrdm, MULTIRES_COORDS_MODIFIED); multires_force_update(ob); mrdm->release(mrdm); @@ -336,6 +511,9 @@ static void multires_reallocate_mdisps(int totloop, MDisps *mdisps, int lvl) if (mdisps[i].disps) MEM_freeN(mdisps[i].disps); + + if (mdisps[i].level && mdisps[i].hidden) + multires_mdisps_subdivide_hidden(&mdisps[i], lvl); mdisps[i].disps = disps; mdisps[i].totdisp = totdisp; @@ -421,6 +599,14 @@ static void multires_del_higher(MultiresModifierData *mmd, Object *ob, int lvl) hdisps = mdisp->disps; multires_copy_grid(ndisps, hdisps, nsize, hsize); + if (mdisp->hidden) { + BLI_bitmap gh = + multires_mdisps_downsample_hidden(mdisp->hidden, + mdisp->level, + lvl); + MEM_freeN(mdisp->hidden); + mdisp->hidden = gh; + } ndisps += nsize*nsize; hdisps += hsize*hsize; @@ -637,7 +823,7 @@ static void multires_subdivide(MultiresModifierData *mmd, Object *ob, int totlvl mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS); if (!mdisps) - mdisps = CustomData_add_layer(&me->ldata, CD_MDISPS, CD_DEFAULT, NULL, me->totloop); + mdisps = multires_mdisps_initialize_hidden(me, totlvl); if (mdisps->disps && !updateblock && totlvl > 1) { /* upsample */ @@ -940,6 +1126,37 @@ void multires_modifier_update_mdisps(struct DerivedMesh *dm) } } +void multires_modifier_update_hidden(DerivedMesh *dm) +{ + CCGDerivedMesh *ccgdm= (CCGDerivedMesh*)dm; + BLI_bitmap *grid_hidden= ccgdm->gridHidden; + Mesh *me = ccgdm->multires.ob->data; + MDisps *mdisps = CustomData_get_layer(&me->ldata, CD_MDISPS); + int totlvl = ccgdm->multires.totlvl; + int lvl = ccgdm->multires.lvl; + + if(mdisps) { + int i; + + for(i = 0; i < me->totloop; i++) { + MDisps *md = &mdisps[i]; + BLI_bitmap gh = grid_hidden[i]; + + if(!gh && md->hidden) { + MEM_freeN(md->hidden); + md->hidden = NULL; + } + else if(gh) { + gh = multires_mdisps_upsample_hidden(gh, lvl, totlvl, + md->hidden); + if(md->hidden) + MEM_freeN(md->hidden); + + md->hidden = gh; + } + } + } +} void multires_set_space(DerivedMesh *dm, Object *ob, int from, int to) { @@ -1092,7 +1309,7 @@ DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int loca { Mesh *me= ob->data; DerivedMesh *result; - CCGDerivedMesh *ccgdm; + CCGDerivedMesh *ccgdm = NULL; DMGridData **gridData, **subGridData; int lvl= multires_get_level(ob, mmd, useRenderParams); int i, gridSize, numGrids; @@ -1112,7 +1329,7 @@ DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int loca ccgdm->multires.local_mmd = local_mmd; ccgdm->multires.lvl = lvl; ccgdm->multires.totlvl = mmd->totlvl; - ccgdm->multires.modified = 0; + ccgdm->multires.modified_flags = 0; } numGrids = result->getNumGrids(result); @@ -1132,6 +1349,10 @@ DerivedMesh *multires_dm_create_from_derived(MultiresModifierData *mmd, int loca /*run displacement*/ multiresModifier_disp_run(result, ob->data, dm, APPLY_DISPLACEMENTS, subGridData, mmd->totlvl); + /* copy hidden elements for this level */ + if(ccgdm) + multires_output_hidden_to_ccgdm(ccgdm, me, lvl); + for (i = 0; i < numGrids; i++) MEM_freeN(subGridData[i]); MEM_freeN(subGridData); @@ -1753,7 +1974,7 @@ void multires_load_old(Object *ob, Mesh *me) multires_load_old_dm(dm, me, mmd->totlvl+1); - multires_dm_mark_as_modified(dm); + multires_dm_mark_as_modified(dm, MULTIRES_COORDS_MODIFIED); dm->release(dm); orig->release(orig); diff --git a/source/blender/blenkernel/intern/subsurf_ccg.c b/source/blender/blenkernel/intern/subsurf_ccg.c index ba7394c9e91..d8fabcbea7a 100644 --- a/source/blender/blenkernel/intern/subsurf_ccg.c +++ b/source/blender/blenkernel/intern/subsurf_ccg.c @@ -2341,12 +2341,18 @@ static void ccgDM_release(DerivedMesh *dm) if (DM_release(dm)) { /* Before freeing, need to update the displacement map */ - if(ccgdm->multires.modified) { + if(ccgdm->multires.modified_flags) { /* Check that mmd still exists */ - if(!ccgdm->multires.local_mmd && BLI_findindex(&ccgdm->multires.ob->modifiers, ccgdm->multires.mmd) < 0) + if(!ccgdm->multires.local_mmd && + BLI_findindex(&ccgdm->multires.ob->modifiers, ccgdm->multires.mmd) < 0) ccgdm->multires.mmd = NULL; - if(ccgdm->multires.mmd) - multires_modifier_update_mdisps(dm); + + if(ccgdm->multires.mmd) { + if(ccgdm->multires.modified_flags & MULTIRES_COORDS_MODIFIED) + multires_modifier_update_mdisps(dm); + if(ccgdm->multires.modified_flags & MULTIRES_HIDDEN_MODIFIED) + multires_modifier_update_hidden(dm); + } } if (ccgdm->ehash) @@ -2815,7 +2821,7 @@ static struct PBVH *ccgDM_getPBVH(Object *ob, DerivedMesh *dm) ob->sculpt->pbvh= ccgdm->pbvh = BLI_pbvh_new(); BLI_pbvh_build_grids(ccgdm->pbvh, ccgdm->gridData, ccgdm->gridAdjacency, - numGrids, gridSize, (void**)ccgdm->gridFaces, ccgdm->gridFlagMats); + numGrids, gridSize, (void**)ccgdm->gridFaces, ccgdm->gridFlagMats, ccgdm->gridHidden); } else if(ob->type == OB_MESH) { Mesh *me= ob->data; ob->sculpt->pbvh= ccgdm->pbvh = BLI_pbvh_new(); diff --git a/source/blender/blenlib/BLI_pbvh.h b/source/blender/blenlib/BLI_pbvh.h index ed763498687..a1137009e3d 100644 --- a/source/blender/blenlib/BLI_pbvh.h +++ b/source/blender/blenlib/BLI_pbvh.h @@ -57,7 +57,8 @@ void BLI_pbvh_build_mesh(PBVH *bvh, struct MFace *faces, struct MVert *verts, int totface, int totvert); void BLI_pbvh_build_grids(PBVH *bvh, struct DMGridData **grids, struct DMGridAdjacency *gridadj, int totgrid, - int gridsize, void **gridfaces, struct DMFlagMat *flagmats); + int gridsize, void **gridfaces, struct DMFlagMat *flagmats, + unsigned int **grid_hidden); void BLI_pbvh_free(PBVH *bvh); /* Hierarchical Search in the BVH, two methods: @@ -97,6 +98,9 @@ typedef enum { PBVHType BLI_pbvh_type(const PBVH *bvh); +/* multires hidden data, only valid for type == PBVH_GRIDS */ +unsigned int **BLI_pbvh_grid_hidden(const PBVH *bvh); + /* Node Access */ typedef enum { diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c index 952a3df7109..a986896e0d2 100644 --- a/source/blender/blenlib/intern/pbvh.c +++ b/source/blender/blenlib/intern/pbvh.c @@ -141,6 +141,7 @@ struct PBVH { const DMFlagMat *grid_flag_mats; int totgrid; int gridsize; + BLI_bitmap *grid_hidden; /* Only used during BVH build and update, * don't need to remain valid after */ @@ -639,7 +640,7 @@ void BLI_pbvh_build_mesh(PBVH *bvh, MFace *faces, MVert *verts, int totface, int /* Do a full rebuild with on Grids data structure */ void BLI_pbvh_build_grids(PBVH *bvh, DMGridData **grids, DMGridAdjacency *gridadj, - int totgrid, int gridsize, void **gridfaces, DMFlagMat *flagmats) + int totgrid, int gridsize, void **gridfaces, DMFlagMat *flagmats, BLI_bitmap *grid_hidden) { BBC *prim_bbc = NULL; BB cb; @@ -652,6 +653,7 @@ void BLI_pbvh_build_grids(PBVH *bvh, DMGridData **grids, DMGridAdjacency *gridad bvh->grid_flag_mats= flagmats; bvh->totgrid= totgrid; bvh->gridsize= gridsize; + bvh->grid_hidden= grid_hidden; bvh->leaf_limit = MAX2(LEAF_LIMIT/((gridsize-1)*(gridsize-1)), 1); BB_reset(&cb); @@ -1284,6 +1286,12 @@ PBVHType BLI_pbvh_type(const PBVH *bvh) return bvh->type; } +BLI_bitmap *BLI_pbvh_grid_hidden(const PBVH *bvh) +{ + BLI_assert(bvh->type == PBVH_GRIDS); + return bvh->grid_hidden; +} + /***************************** Node Access ***********************************/ void BLI_pbvh_node_mark_update(PBVHNode *node) diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c index c7b27742969..f75610dbbe3 100644 --- a/source/blender/editors/sculpt_paint/sculpt.c +++ b/source/blender/editors/sculpt_paint/sculpt.c @@ -64,6 +64,7 @@ #include "BKE_report.h" #include "BKE_lattice.h" /* for armature_deform_verts */ #include "BKE_node.h" +#include "BKE_subsurf.h" #include "BIF_glutil.h" @@ -3346,7 +3347,7 @@ static void sculpt_flush_update(bContext *C) MultiresModifierData *mmd = ss->multires; if(mmd) - multires_mark_as_modified(ob); + multires_mark_as_modified(ob, MULTIRES_COORDS_MODIFIED); if(ob->derivedFinal) /* VBO no longer valid */ GPU_drawobject_free(ob->derivedFinal); diff --git a/source/blender/editors/sculpt_paint/sculpt_undo.c b/source/blender/editors/sculpt_paint/sculpt_undo.c index 84b8b5a8bce..6de6621b44f 100644 --- a/source/blender/editors/sculpt_paint/sculpt_undo.c +++ b/source/blender/editors/sculpt_paint/sculpt_undo.c @@ -55,6 +55,7 @@ #include "BKE_paint.h" #include "BKE_key.h" #include "BKE_mesh.h" +#include "BKE_subsurf.h" #include "WM_api.h" #include "WM_types.h" @@ -209,7 +210,7 @@ static void sculpt_undo_restore(bContext *C, ListBase *lb) BLI_pbvh_update(ss->pbvh, PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateRedraw, NULL); if((mmd=sculpt_multires_active(scene, ob))) - multires_mark_as_modified(ob); + multires_mark_as_modified(ob, MULTIRES_COORDS_MODIFIED); tag_update= ((Mesh*)ob->data)->id.us > 1; -- cgit v1.2.3