Sculpt: Grid based PBVH

* PBVH can now be created contain both from face grids or standard
  meshes. The former is much quicker to build for high res meshes.
* Moved some drawing code into pbvh (mostly for the frustum test).
* Moved ray intersection code into pbvh.
* GPU buffers also can be built from either mesh or grids now.
* Updated sculpt code to work with this. The ugly part is that there
  is now a macro for iterating over vertices, to handle both cases,
  and some duplicated code for e.g. undo.
* Smooth brush does not work yet with grids.

1 files changed, 102 insertions, 8 deletions

diff --git a/source/blender/blenlib/BLI_pbvh.h b/source/blender/blenlib/BLI_pbvh.h
index 360a9937498..5c5277dc091 100644
--- a/source/blender/blenlib/BLI_pbvh.h
+++ b/source/blender/blenlib/BLI_pbvh.h
@@ -27,6 +27,7 @@
 
 struct MFace;
 struct MVert;
+struct DMGridData;
 struct PBVH;
 struct PBVHNode;
 struct ListBase;
@@ -44,12 +45,12 @@ typedef void (*BLI_pbvh_HitCallback)(PBVHNode *node, void *data);
 /* Building */
 
 PBVH *BLI_pbvh_new(void);
-void BLI_pbvh_build(PBVH *bvh, struct MFace *faces, struct MVert *verts,
+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, int totgrid,
+	int gridsize, void **gridfaces);
 void BLI_pbvh_free(PBVH *bvh);
 
-void BLI_pbvh_set_source(PBVH *bvh, struct MVert *, struct MFace *mface);
-
 /* Hierarchical Search in the BVH, two methods:
    * for each hit calling a callback
    * gather nodes in an array (easy to multithread) */
@@ -69,6 +70,14 @@ void BLI_pbvh_search_gather(PBVH *bvh,
 
 void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
 		      float ray_start[3], float ray_normal[3], int original);
+int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3],
+	float ray_start[3], float ray_normal[3], float *dist);
+
+/* 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]);
 
 /* Node Access */
 
@@ -84,11 +93,11 @@ typedef enum {
 
 void BLI_pbvh_node_mark_update(PBVHNode *node);
 
-void BLI_pbvh_node_get_verts(PBVHNode *node, int **vert_indices,
-	int *totvert, int *allverts);
-void BLI_pbvh_node_get_faces(PBVHNode *node, int **face_indices,
-	int **face_vert_indices, int *totface);
-void *BLI_pbvh_node_get_draw_buffers(PBVHNode *node);
+void BLI_pbvh_node_get_grids(PBVH *bvh, PBVHNode *node,
+	int **grid_indices, int *totgrid, int *maxgrid, int *gridsize);
+void BLI_pbvh_node_num_verts(PBVH *bvh, PBVHNode *node,
+	int *uniquevert, int *totvert);
+
 void BLI_pbvh_node_get_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
 void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max[3]);
 
@@ -96,6 +105,91 @@ void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max
 
 void BLI_pbvh_update(PBVH *bvh, int flags, float (*face_nors)[3]);
 void BLI_pbvh_redraw_BB(PBVH *bvh, float bb_min[3], float bb_max[3]);
+void BLI_pbvh_get_grid_updates(PBVH *bvh, void ***gridfaces, int *totface);
+
+/* Vertex Iterator */
+
+/* this iterator has quite a lot of code, but it's designed to:
+   - allow the compiler to eliminate dead code and variables
+   - spend most of the time in the relatively simple inner loop */
+
+#define PBVH_ITER_ALL		0
+#define PBVH_ITER_UNIQUE	1
+
+typedef struct PBVHVertexIter {
+	/* iteration */
+	int g;
+	int width;
+	int height;
+	int skip;
+	int gx;
+	int gy;
+	int i;
+
+	/* grid */
+	struct DMGridData **grids;
+	struct DMGridData *grid;
+	int *grid_indices;
+	int totgrid;
+	int gridsize;
+
+	/* mesh */
+	struct MVert *mverts;
+	int totvert;
+	int *vert_indices;
+
+	/* result: these are all computed in the macro, but we assume
+	   that compiler optimizations will skip the ones we don't use */
+	struct MVert *mvert;
+	float *co;
+	short *no;
+	float *fno;
+} PBVHVertexIter;
+
+void BLI_pbvh_node_verts_iter_init(PBVH *bvh, PBVHNode *node, PBVHVertexIter *vi, int mode);
+
+#define BLI_pbvh_vertex_iter_begin(bvh, node, vi, mode) \
+	/* XXX breaks aliasing! */ \
+	BLI_pbvh_node_verts_iter_init(bvh, node, &vi, mode); \
+	\
+	for(vi.i=0, vi.g=0; vi.g<vi.totgrid; vi.g++) { \
+		if(vi.grids) { \
+			vi.width= vi.gridsize; \
+			vi.height= vi.gridsize; \
+			vi.grid= vi.grids[vi.grid_indices[vi.g]]; \
+			vi.skip= 0; \
+		 	\
+			/*if(mode == PVBH_ITER_UNIQUE) { \
+				vi.grid += subm->grid.offset; \
+				vi.skip= subm->grid.skip; \
+				vi.grid -= skip; \
+			}*/ \
+		} \
+		else { \
+			vi.width= vi.totvert; \
+			vi.height= 1; \
+		} \
+	 	\
+		for(vi.gy=0; vi.gy<vi.height; vi.gy++) { \
+			if(vi.grid) vi.grid += vi.skip; \
+			\
+			for(vi.gx=0; vi.gx<vi.width; vi.gx++, vi.i++) { \
+				if(vi.grid) { \
+					vi.co= vi.grid->co; \
+					vi.fno= vi.grid->no; \
+					vi.grid++; \
+				} \
+				else { \
+					vi.mvert= &vi.mverts[vi.vert_indices[vi.gx]]; \
+					vi.co= vi.mvert->co; \
+					vi.no= vi.mvert->no; \
+				} \
+
+#define BLI_pbvh_vertex_iter_end \
+			} \
+		} \
+	}
+
 
 #endif /* BLI_PBVH_H */