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

2 files changed, 119 insertions, 16 deletions

diff --git a/source/blender/blenlib/BLI_pbvh.h b/source/blender/blenlib/BLI_pbvh.h
index a1137009e3d..210238efcfd 100644
--- a/source/blender/blenlib/BLI_pbvh.h
+++ b/source/blender/blenlib/BLI_pbvh.h
@@ -26,6 +26,8 @@
  *  \brief A BVH for high poly meshes.
  */
 
+#include "BLI_bitmap.h"
+
 struct DMFlagMat;
 struct DMGridAdjacency;
 struct DMGridData;
@@ -86,7 +88,6 @@ int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
 /* Drawing */
 
 void BLI_pbvh_node_draw(PBVHNode *node, void *data);
-int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
 				   int (*setMaterial)(int, void *attribs));
 
@@ -110,10 +111,15 @@ typedef enum {
 	PBVH_UpdateBB = 4,
 	PBVH_UpdateOriginalBB = 8,
 	PBVH_UpdateDrawBuffers = 16,
-	PBVH_UpdateRedraw = 32
+	PBVH_UpdateRedraw = 32,
+
+	PBVH_RebuildDrawBuffers = 64,
+	PBVH_FullyHidden = 128
 } PBVHNodeFlags;
 
 void BLI_pbvh_node_mark_update(PBVHNode *node);
+void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node);
+void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden);
 
 void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
 	int **grid_indices, int *totgrid, int *maxgrid, int *gridsize,
@@ -128,6 +134,11 @@ void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max
 
 float BLI_pbvh_node_get_tmin(PBVHNode* node);
 
+/* test if AABB is at least partially inside the planes' volume */
+int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data);
+/* test if AABB is at least partially outside the planes' volume */
+int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data);
+
 /* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
 
 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
@@ -148,6 +159,8 @@ int BLI_pbvh_isDeformed(struct PBVH *pbvh);
  * - allow the compiler to eliminate dead code and variables
  * - spend most of the time in the relatively simple inner loop */
 
+/* note: PBVH_ITER_ALL does not skip hidden vertices,
+   PBVH_ITER_UNIQUE does */
 #define PBVH_ITER_ALL		0
 #define PBVH_ITER_UNIQUE	1
 
@@ -163,6 +176,7 @@ typedef struct PBVHVertexIter {
 	/* grid */
 	struct DMGridData **grids;
 	struct DMGridData *grid;
+	BLI_bitmap *grid_hidden, gh;
 	int *grid_indices;
 	int totgrid;
 	int gridsize;
@@ -195,6 +209,8 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
 			vi.width= vi.gridsize; \
 			vi.height= vi.gridsize; \
 			vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
+			if(mode == PBVH_ITER_UNIQUE) \
+				vi.gh= vi.grid_hidden[vi.grid_indices[vi.g]];	\
 		} \
 		else { \
 			vi.width= vi.totvert; \
@@ -207,9 +223,15 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
 					vi.co= vi.grid->co; \
 					vi.fno= vi.grid->no; \
 					vi.grid++; \
+					if(vi.gh) { \
+						if(BLI_BITMAP_GET(vi.gh, vi.gy * vi.gridsize + vi.gx)) \
+							continue; \
+					} \
 				} \
 				else { \
 					vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
+					if(mode == PBVH_ITER_UNIQUE && vi.mvert->flag & ME_HIDE) \
+						continue; \
 					vi.co= vi.mvert->co; \
 					vi.no= vi.mvert->no; \
 				} \
diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c
index a986896e0d2..1987cbeedac 100644
--- a/source/blender/blenlib/intern/pbvh.c
+++ b/source/blender/blenlib/intern/pbvh.c
@@ -37,6 +37,8 @@
 #include "BKE_DerivedMesh.h"
 #include "BKE_mesh.h" /* for mesh_calc_normals */
 #include "BKE_global.h" /* for mesh_calc_normals */
+#include "BKE_paint.h"
+#include "BKE_subsurf.h"
 
 #include "GPU_buffers.h"
 
@@ -430,7 +432,7 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node)
 	if(!G.background) {
 		node->draw_buffers =
 			GPU_build_mesh_buffers(node->face_vert_indices,
-					bvh->faces,
+					bvh->faces, bvh->verts,
 					node->prim_indices,
 					node->totprim);
 	}
@@ -444,7 +446,8 @@ static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node)
 {
 	if(!G.background) {
 		node->draw_buffers =
-			GPU_build_grid_buffers(node->totprim, bvh->gridsize);
+			GPU_build_grid_buffers(node->prim_indices,
+				node->totprim, bvh->grid_hidden, bvh->gridsize);
 	}
 	node->flag |= PBVH_UpdateDrawBuffers;
 }
@@ -1129,6 +1132,24 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
 	for(n = 0; n < totnode; n++) {
 		node= nodes[n];
 
+		if(node->flag & PBVH_RebuildDrawBuffers) {
+			GPU_free_buffers(node->draw_buffers);
+			if(bvh->grids) {
+				node->draw_buffers =
+					GPU_build_grid_buffers(node->prim_indices,
+						   node->totprim, bvh->grid_hidden, bvh->gridsize);
+			}
+			else {
+				node->draw_buffers =
+					GPU_build_mesh_buffers(node->face_vert_indices,
+						   bvh->faces, bvh->verts,
+						   node->prim_indices,
+						   node->totprim);
+			}
+ 
+			node->flag &= ~PBVH_RebuildDrawBuffers;
+		}
+
 		if(node->flag & PBVH_UpdateDrawBuffers) {
 			switch(bvh->type) {
 			case PBVH_GRIDS:
@@ -1299,6 +1320,21 @@ void BLI_pbvh_node_mark_update(PBVHNode *node)
 	node->flag |= PBVH_UpdateNormals|PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateDrawBuffers|PBVH_UpdateRedraw;
 }
 
+void BLI_pbvh_node_mark_rebuild_draw(PBVHNode *node)
+{
+	node->flag |= PBVH_RebuildDrawBuffers|PBVH_UpdateDrawBuffers|PBVH_UpdateRedraw;
+}
+
+void BLI_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
+{
+	BLI_assert(node->flag & PBVH_Leaf);
+	
+	if(fully_hidden)
+		node->flag |= PBVH_FullyHidden;
+	else
+		node->flag &= ~PBVH_FullyHidden;
+}
+
 void BLI_pbvh_node_get_verts(PBVH *bvh, PBVHNode *node, int **vert_indices, MVert **verts)
 {
 	if(vert_indices) *vert_indices= node->vert_indices;
@@ -1461,9 +1497,13 @@ int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
 	float ray_start[3], float ray_normal[3], float *dist)
 {
 	MVert *vert;
+	BLI_bitmap gh;
 	int *faces, totface, gridsize, totgrid;
 	int i, x, y, hit= 0;
 
+	if(node->flag & PBVH_FullyHidden)
+		return 0;
+
 	switch(bvh->type) {
 	case PBVH_FACES:
 		vert = bvh->verts;
@@ -1471,9 +1511,12 @@ int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
 		totface= node->totprim;
 
 		for(i = 0; i < totface; ++i) {
-			MFace *f = bvh->faces + faces[i];
+			const MFace *f = bvh->faces + faces[i];
 			int *face_verts = node->face_vert_indices[i];
 
+			if(paint_is_face_hidden(f, vert))
+				continue;
+
 			if(origco) {
 				/* intersect with backuped original coordinates */
 				hit |= ray_face_intersection(ray_start, ray_normal,
@@ -1503,8 +1546,16 @@ int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
 			if (!grid)
 				continue;
 
+			gh= bvh->grid_hidden[node->prim_indices[i]];
+
 			for(y = 0; y < gridsize-1; ++y) {
 				for(x = 0; x < gridsize-1; ++x) {
+					/* check if grid face is hidden */
+					if(gh) {
+						if(paint_is_grid_face_hidden(gh, gridsize, x, y))
+							continue;
+					}
+
 					if(origco) {
 						hit |= ray_face_intersection(ray_start, ray_normal,
 									 origco[y*gridsize + x],
@@ -1553,39 +1604,65 @@ void BLI_pbvh_node_draw(PBVHNode *node, void *setMaterial)
 
 	glColor3f(1, 0, 0);
 #endif
-	GPU_draw_buffers(node->draw_buffers, setMaterial);
+
+	if(!(node->flag & PBVH_FullyHidden))
+		GPU_draw_buffers(node->draw_buffers, setMaterial);
 }
 
+typedef enum {
+	ISECT_INSIDE,
+	ISECT_OUTSIDE,
+	ISECT_INTERSECT
+} PlaneAABBIsect;
+
 /* Adapted from:
  * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
  * Returns true if the AABB is at least partially within the frustum
  * (ok, not a real frustum), false otherwise.
  */
-int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
+static PlaneAABBIsect test_planes_aabb(const float bb_min[3],
+									   const float bb_max[3],
+									   const float (*planes)[4])
 {
-	float (*planes)[4] = data;
+	float vmin[3], vmax[3];
+	PlaneAABBIsect ret = ISECT_INSIDE;
 	int i, axis;
-	float vmin[3] /*, vmax[3]*/, bb_min[3], bb_max[3];
-
-	BLI_pbvh_node_get_BB(node, bb_min, bb_max);
-
+	
 	for(i = 0; i < 4; ++i) { 
 		for(axis = 0; axis < 3; ++axis) {
 			if(planes[i][axis] > 0) { 
 				vmin[axis] = bb_min[axis];
-				/*vmax[axis] = bb_max[axis];*/ /*UNUSED*/
+				vmax[axis] = bb_max[axis];
 			}
 			else {
 				vmin[axis] = bb_max[axis];
-				/*vmax[axis] = bb_min[axis];*/ /*UNUSED*/
+				vmax[axis] = bb_min[axis];
 			}
 		}
 		
 		if(dot_v3v3(planes[i], vmin) + planes[i][3] > 0)
-			return 0;
+			return ISECT_OUTSIDE;
+		else if(dot_v3v3(planes[i], vmax) + planes[i][3] >= 0)
+			ret = ISECT_INTERSECT;
 	} 
 
-	return 1;
+	return ret;
+}
+
+int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data)
+{
+	float bb_min[3], bb_max[3];
+	
+	BLI_pbvh_node_get_BB(node, bb_min, bb_max);
+	return test_planes_aabb(bb_min, bb_max, data) != ISECT_OUTSIDE;
+}
+
+int BLI_pbvh_node_planes_exclude_AABB(PBVHNode *node, void *data)
+{
+	float bb_min[3], bb_max[3];
+	
+	BLI_pbvh_node_get_BB(node, bb_min, bb_max);
+	return test_planes_aabb(bb_min, bb_max, data) != ISECT_INSIDE;
 }
 
 void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3],
@@ -1791,4 +1868,8 @@ void pbvh_vertex_iter_init(PBVH *bvh, PBVHNode *node,
 		vi->totvert= uniq_verts;
 	vi->vert_indices= vert_indices;
 	vi->mverts= verts;
+
+	vi->gh= NULL;
+	if(vi->grids && mode == PBVH_ITER_UNIQUE)
+		vi->grid_hidden= bvh->grid_hidden;
 }