Skip hidden elements in PBVH iterator, raycast, and drawing.

8 files changed, 275 insertions, 23 deletions

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;