Sculpt: Multithreading & PBVH Changes

* Sculpting, normal update and bounding box code is now multithreaded
  using OpenMP.
* Fix a number of update issues: normals on node boundaries, outdated
  bounding boxes, partial redraw, .. . There's probably still a few
  left, but should be better now.
* Clicking once now does a single paint instead of two (was also
  painting on mouse up event).
* Smooth shading now is enabled for the full mesh when the first face
  uses it (so it can be tested at least).

Implementation Notes:

* PBVH search can now be done either using a callback or bt gathering the
  nodes in an array. The latter makes multithreading with OpenMP easier.
* Normals update code is now inside PBVH, was doing it per node before but
  should do all faces first and only then vertices.
* Instead of using search modes + 1 modified flag, now nodes get 4 flags
  to indicate what needs to be updated for them, found that this makes it
  easier for me to understand the code and fix update bugs.
* PBVHNode is now exposed as an abstract type, I think this makes it more
  clear what is happening than having it's data passed as part of callback
  functions.
* Active_verts list was replaced by looping over nodes and the vertices
  inside them. However the grab brush still uses the active_verts system,
  will fix that later.
* Some micro-optimizations, like avoiding a few multiplications/divisions,
  using local variables instead of pointers, or looping over fewer vertices
  to update the bounding boxes.

8 files changed, 1030 insertions, 655 deletions

diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h
index 09c1ab9f7d6..edb4e2cf2a9 100644
--- a/source/blender/blenkernel/BKE_mesh.h
+++ b/source/blender/blenkernel/BKE_mesh.h
@@ -47,6 +47,7 @@ struct Object;
 struct MTFace;
 struct VecNor;
 struct CustomData;
+struct Scene;
 
 #ifdef __cplusplus
 extern "C" {
diff --git a/source/blender/blenkernel/intern/brush.c b/source/blender/blenkernel/intern/brush.c
index 115d31b587c..8a4ffca8244 100644
--- a/source/blender/blenkernel/intern/brush.c
+++ b/source/blender/blenkernel/intern/brush.c
@@ -83,7 +83,7 @@ Brush *add_brush(const char *name)
 	brush->clone.alpha= 0.5;
 	brush->sculpt_tool = SCULPT_TOOL_DRAW;
 
-	brush_curve_preset(brush, BRUSH_PRESET_SHARP);
+	brush_curve_preset(brush, BRUSH_PRESET_SMOOTH);
 
 	/* enable fake user by default */
 	brush->id.flag |= LIB_FAKEUSER;
diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c
index 66e09022ff5..b7234a86af9 100644
--- a/source/blender/blenkernel/intern/cdderivedmesh.c
+++ b/source/blender/blenkernel/intern/cdderivedmesh.c
@@ -177,55 +177,6 @@ static void cdDM_getVertNo(DerivedMesh *dm, int index, float no_r[3])
 	no_r[2] = no[2]/32767.f;
 }
 
-/* Updates all the face and vertex normals in a node
-
-   Note: the correctness of some vertex normals will be a little
-   off, not sure if this will be noticeable or not */
-static void update_node_normals(const int *face_indices,
-				const int *vert_indices,
-				int totface, int totvert, void *data)
-{
-	DerivedMesh *dm = data;
-	CDDerivedMesh *cddm = data;
-	float (*face_nors)[3];
-	int i;
-
-	/* make a face normal layer if not present */
-	face_nors = CustomData_get_layer(&dm->faceData, CD_NORMAL);
-	if(!face_nors)
-		face_nors = CustomData_add_layer(&dm->faceData, CD_NORMAL, CD_CALLOC,
-		                                 NULL, dm->numFaceData);
-
-	/* Update face normals */
-	for(i = 0; i < totface; ++i) {
-		MFace *f = cddm->mface + face_indices[i];
-		float *fn = face_nors[face_indices[i]];
-
-		if(f->v4)
-			CalcNormFloat4(cddm->mvert[f->v1].co, cddm->mvert[f->v2].co,
-			               cddm->mvert[f->v3].co, cddm->mvert[f->v4].co, fn);
-		else
-			CalcNormFloat(cddm->mvert[f->v1].co, cddm->mvert[f->v2].co,
-			              cddm->mvert[f->v3].co, fn);
-	}
-
-	/* Update vertex normals */
-	for(i = 0; i < totvert; ++i) {
-		const int v = vert_indices[i];
-		float no[3] = {0,0,0};
-		IndexNode *face;
-
-		for(face = cddm->fmap[v].first; face; face = face->next)
-			VecAddf(no, no, face_nors[face->index]);
-
-		Normalize(no);
-		
-		cddm->mvert[v].no[0] = no[0] * 32767;
-		cddm->mvert[v].no[1] = no[1] * 32767;
-		cddm->mvert[v].no[2] = no[2] * 32767;
-	}
-}
-
 static ListBase *cdDM_getFaceMap(DerivedMesh *dm)
 {
 	CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
@@ -244,7 +195,7 @@ static struct PBVH *cdDM_getPBVH(DerivedMesh *dm)
 	CDDerivedMesh *cddm = (CDDerivedMesh*) dm;
 
 	if(!cddm->pbvh) {
-		cddm->pbvh = BLI_pbvh_new(update_node_normals, cddm);
+		cddm->pbvh = BLI_pbvh_new();
 		BLI_pbvh_build(cddm->pbvh, cddm->mface, cddm->mvert,
 			       dm->getNumFaces(dm), dm->getNumVerts(dm));
 		printf("rebuild pbvh\n");
@@ -445,9 +396,7 @@ static void cdDM_drawLooseEdges(DerivedMesh *dm)
 static int nodes_drawn = 0;
 static int is_partial = 0;
 /* XXX: Just a temporary replacement for the real drawing code */
-static void draw_partial_cb(const int *face_indices,
-			    const int *vert_indices,
-			    int totface, int totvert, void *data_v)
+static void draw_partial_cb(PBVHNode *node, void *data)
 {
 	/* XXX: Just some quick code to show leaf nodes in different colors */
 	/*float col[3]; int i;
@@ -462,21 +411,16 @@ static void draw_partial_cb(const int *face_indices,
 	glMaterialfv(GL_FRONT_AND_BACK, GL_DIFFUSE, col);
 
 	glColor3f(1, 0, 0);*/
-	GPU_draw_buffers(data_v);
+	GPU_draw_buffers(BLI_pbvh_node_get_draw_buffers(node));
 	++nodes_drawn;
 }
 
-int find_all(float bb_min[3], float bb_max[3], void *data)
-{
-	return 1;
-}
-
 /* 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 planes_contain_AABB(float bb_min[3], float bb_max[3], void *data)
+int planes_contain_AABB(PBVHNode *node, float bb_min[3], float bb_max[3], void *data)
 {
 	float (*planes)[4] = data;
 	int i, axis;
@@ -520,21 +464,28 @@ static void cdDM_drawFacesSolid(DerivedMesh *dm,
 }
 
 	if(cddm->pbvh) {
-		BLI_pbvh_search(cddm->pbvh, BLI_pbvh_update_search_cb,
-				PBVH_NodeData, NULL, NULL,
-				PBVH_SEARCH_UPDATE);
+		float (*face_nors)[3];
+
+		/* make a face normal layer if not present */
+		face_nors = CustomData_get_layer(&dm->faceData, CD_NORMAL);
+		if(!face_nors)
+			face_nors = CustomData_add_layer(&dm->faceData, CD_NORMAL, CD_CALLOC,
+											 NULL, dm->numFaceData);
+
+		BLI_pbvh_update(cddm->pbvh, PBVH_UpdateNormals|PBVH_UpdateDrawBuffers,
+			face_nors, cdDM_getFaceMap(dm));
+
+		/* should be per face */
+		if(dm->numFaceData && mface->flag & ME_SMOOTH)
+			glShadeModel(GL_SMOOTH);
 
 		if(partial_redraw_planes) {
-			BLI_pbvh_search(cddm->pbvh, planes_contain_AABB,
-					partial_redraw_planes,
-					draw_partial_cb, PBVH_DrawData,
-					PBVH_SEARCH_MODIFIED);
+			BLI_pbvh_search_callback(cddm->pbvh, planes_contain_AABB,
+					partial_redraw_planes, draw_partial_cb, NULL);
 		}
 		else {
-			BLI_pbvh_search(cddm->pbvh, find_all, NULL,
-					draw_partial_cb, PBVH_DrawData,
-					PBVH_SEARCH_NORMAL);
-
+			BLI_pbvh_search_callback(cddm->pbvh, NULL, NULL,
+					draw_partial_cb, NULL);
 		}
 
 		is_partial = !!partial_redraw_planes;
@@ -542,6 +493,8 @@ static void cdDM_drawFacesSolid(DerivedMesh *dm,
 		//printf("nodes drawn=%d\n", nodes_drawn);
 		nodes_drawn = 0;
 
+		glShadeModel(GL_FLAT);
+
 		return;
 	}
 
diff --git a/source/blender/blenlib/BLI_pbvh.h b/source/blender/blenlib/BLI_pbvh.h
index edc363e65a3..78e2a9b8745 100644
--- a/source/blender/blenlib/BLI_pbvh.h
+++ b/source/blender/blenlib/BLI_pbvh.h
@@ -1,62 +1,98 @@
+/**
+ * A BVH for high poly meshes.
+ * 
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef BLI_PBVH_H
+#define BLI_PBVH_H
+
 struct MFace;
 struct MVert;
 struct PBVH;
+struct PBVHNode;
+struct ListBase;
 
-/* Returns 1 if the search should continue from this node, 0 otherwise */
-typedef int (*BLI_pbvh_SearchCallback)(float bb_min[3], float bb_max[3],
-				       void *data);
+typedef struct PBVH PBVH;
+typedef struct PBVHNode PBVHNode;
 
-typedef void (*BLI_pbvh_HitCallback)(const int *face_indices,
-				     const int *vert_indices,
-				     int totface, int totvert, void *data);
-int BLI_pbvh_search_range(float bb_min[3], float bb_max[3], void *data_v);
+/* Callbacks */
 
-typedef enum {
-	PBVH_SEARCH_NORMAL,
+/* returns 1 if the search should continue from this node, 0 otherwise */
+typedef int (*BLI_pbvh_SearchCallback)(PBVHNode *node,
+	float bb_min[3], float bb_max[3], void *data);
+
+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,
+		    int totface, int totvert);
+void BLI_pbvh_free(PBVH *bvh);
 
-	/* When the callback returns a 1 for a leaf node, that node will be
-	   marked as modified */
-	PBVH_SEARCH_MARK_MODIFIED,
-	
-	/* Update gpu data for modified nodes. Also clears the Modified flag. */
-	PBVH_SEARCH_MODIFIED,
+void BLI_pbvh_set_source(PBVH *bvh, struct MVert *, struct MFace *mface);
 
-	
-	PBVH_SEARCH_UPDATE
-} PBVH_SearchMode;
+/* Hierarchical Search in the BVH, two methods:
+   * for each hit calling a callback
+   * gather nodes in an array (easy to multithread) */
 
-/* Pass the node as data to the callback */
-#define PBVH_NodeData (void*)0xa
-/* Pass the draw buffers as data to the callback */
-#define PBVH_DrawData (void*)0xb
+void BLI_pbvh_search_callback(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	BLI_pbvh_HitCallback hcb, void *hit_data);
 
-void BLI_pbvh_search(struct PBVH *bvh, BLI_pbvh_SearchCallback scb,
-		     void *search_data, BLI_pbvh_HitCallback hcb,
-		     void *hit_data, PBVH_SearchMode mode);
+void BLI_pbvh_search_gather(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	PBVHNode ***array, int *tot);
 
-/* The hit callback is called for all leaf nodes intersecting the ray;
+/* Raycast
+   the hit callback is called for all leaf nodes intersecting the ray;
    it's up to the callback to find the primitive within the leaves that is
    hit first */
-void BLI_pbvh_raycast(struct PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
+
+void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
 		      float ray_start[3], float ray_normal[3]);
 
+/* Node Access */
 
-int BLI_pbvh_update_search_cb(float bb_min[3], float bb_max[3], void *data_v);
+typedef enum {
+	PBVH_Leaf = 1,
 
-/* Get the bounding box around all nodes that have been marked as modified. */
-void BLI_pbvh_modified_bounding_box(struct PBVH *bvh,
-				    float bb_min[3], float bb_max[3]);
-void BLI_pbvh_reset_modified_bounding_box(struct PBVH *bvh);
+	PBVH_UpdateNormals = 2,
+	PBVH_UpdateBB = 4,
+	PBVH_UpdateDrawBuffers = 8,
+	PBVH_UpdateRedraw = 16
+} PBVHNodeFlags;
 
-/* Lock is off by default, turn on to stop redraw from clearing the modified
-   flag from nodes */
-void BLI_pbvh_toggle_modified_lock(struct PBVH *bvh);
+void BLI_pbvh_node_mark_update(PBVHNode *node);
 
+void BLI_pbvh_node_get_verts(PBVHNode *node, int **vert_indices, int *totvert);
+void BLI_pbvh_node_get_faces(PBVHNode *node, int **face_indices, int *totface);
+void *BLI_pbvh_node_get_draw_buffers(PBVHNode *node);
 
+/* Update Normals/Bounding Box/Draw Buffers/Redraw and clear flags */
 
-struct PBVH *BLI_pbvh_new(BLI_pbvh_HitCallback update_cb, void *update_cb_data);
-void BLI_pbvh_build(struct PBVH *bvh, struct MFace *faces, struct MVert *verts,
-		    int totface, int totvert);
-void BLI_pbvh_free(struct PBVH *bvh);
+void BLI_pbvh_update(PBVH *bvh, int flags,
+	float (*face_nors)[3], struct ListBase *fmap);
+void BLI_pbvh_redraw_bounding_box(PBVH *bvh, float bb_min[3], float bb_max[3]);
+
+#endif /* BLI_PBVH_H */
 
-void BLI_pbvh_set_source(struct PBVH *bvh, struct MVert *, struct MFace *mface);
diff --git a/source/blender/blenlib/intern/arithb.c b/source/blender/blenlib/intern/arithb.c
index f353a90ab21..20c2b6d95be 100644
--- a/source/blender/blenlib/intern/arithb.c
+++ b/source/blender/blenlib/intern/arithb.c
@@ -114,16 +114,17 @@ float sasqrtf(float fac)
 
 float Normalize(float *n)
 {
-	float d;
+	float d, invd;
 	
 	d= n[0]*n[0]+n[1]*n[1]+n[2]*n[2];
 	/* A larger value causes normalize errors in a scaled down models with camera xtreme close */
 	if(d>1.0e-35f) {
 		d= (float)sqrt(d);
+		invd= 1.0f/d;
 
-		n[0]/=d; 
-		n[1]/=d; 
-		n[2]/=d;
+		n[0]*=invd; 
+		n[1]*=invd; 
+		n[2]*=invd;
 	} else {
 		n[0]=n[1]=n[2]= 0.0f;
 		d= 0.0f;
diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c
index 98492a8f429..b707343bebb 100644
--- a/source/blender/blenlib/intern/pbvh.c
+++ b/source/blender/blenlib/intern/pbvh.c
@@ -1,3 +1,29 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <float.h>
+#include <stdlib.h>
+#include <string.h>
+
 #include "MEM_guardedalloc.h"
 
 #include "DNA_meshdata_types.h"
@@ -6,14 +32,11 @@
 #include "BLI_ghash.h"
 #include "BLI_pbvh.h"
 
+#include "BKE_mesh.h"
 #include "BKE_utildefines.h"
 
 #include "gpu_buffers.h"
 
-#include <float.h>
-#include <stdlib.h>
-#include <string.h>
-
 #define LEAF_LIMIT 10000
 
 //#define PERFCNTRS
@@ -41,11 +64,6 @@ void BLI_bitmap_clear(BLI_bitmap b, int index)
 	b[index >> 3] &= ~(1 << (index & 7));
 }
 
-typedef enum {
-	PBVH_Leaf = 1,
-	PBVH_Modified = 2
-} NodeFlags;
-
 /* Axis-aligned bounding box */
 typedef struct {
 	float bmin[3], bmax[3];
@@ -56,7 +74,7 @@ typedef struct {
 	float bmin[3], bmax[3], bcentroid[3];
 } BBC;
 
-typedef struct {
+struct PBVHNode {
 	/* Opaque handle for drawing code */
 	void *draw_buffers;
 
@@ -68,33 +86,26 @@ typedef struct {
 	/* For internal nodes */
 	int children_offset;
 
-	/* Range of faces used in the node */
-	int face_offset;
+	/* Pointer into bvh face_indices */
+	int *face_indices;
 
 	unsigned short totface;
 	unsigned short uniq_verts, face_verts;
 
 	char flag;
-} Node;
+};
 
-typedef struct PBVH {
-	Node *nodes;
+struct PBVH {
+	PBVHNode *nodes;
 	int node_mem_count, totnode;
 
 	int *face_indices;
 	int totface;
 
-	BB modified_bb;
-
-	BLI_pbvh_HitCallback update_cb;
-	void *update_cb_data;
-
 	/* Mesh data */
 	MVert *verts;
 	MFace *faces;
 
-	int modified_lock;
-
 	/* Only used during BVH build and update,
 	   don't need to remain valid after */
 	BLI_bitmap vert_bitmap;
@@ -102,7 +113,26 @@ typedef struct PBVH {
 #ifdef PERFCNTRS
 	int perf_modified;
 #endif
-} PBVH;
+};
+
+#define STACK_FIXED_DEPTH	100
+
+typedef struct PBVHStack {
+	PBVHNode *node;
+	int revisiting;
+} PBVHStack;
+
+typedef struct PBVHIter {
+	PBVH *bvh;
+	BLI_pbvh_SearchCallback scb;
+	void *search_data;
+
+	PBVHStack *stack;
+	int stacksize;
+
+	PBVHStack stackfixed[STACK_FIXED_DEPTH];
+	int stackspace;
+} PBVHIter;
 
 static void BB_reset(BB *bb)
 {
@@ -113,13 +143,11 @@ static void BB_reset(BB *bb)
 /* Expand the bounding box to include a new coordinate */
 static void BB_expand(BB *bb, float co[3])
 {
-	if(co[0] < bb->bmin[0]) bb->bmin[0] = co[0];
-	if(co[1] < bb->bmin[1]) bb->bmin[1] = co[1];
-	if(co[2] < bb->bmin[2]) bb->bmin[2] = co[2];
-
-	if(co[0] > bb->bmax[0]) bb->bmax[0] = co[0];
-	if(co[1] > bb->bmax[1]) bb->bmax[1] = co[1];
-	if(co[2] > bb->bmax[2]) bb->bmax[2] = co[2];
+	int i;
+	for(i = 0; i < 3; ++i) {
+		bb->bmin[i] = MIN2(bb->bmin[i], co[i]);
+		bb->bmax[i] = MAX2(bb->bmax[i], co[i]);
+	}
 }
 
 /* Expand the bounding box to include another bounding box */
@@ -163,28 +191,28 @@ static void BBC_update_centroid(BBC *bbc)
 }
 
 /* Not recursive */
-static void update_node_vb(PBVH *bvh, Node *node)
+static void update_node_vb(PBVH *bvh, PBVHNode *node)
 {
-	BB_reset(&node->vb);
+	BB vb;
+
+	BB_reset(&vb);
 	
 	if(node->flag & PBVH_Leaf) {
-		int i, j;
-		for(i = node->face_offset + node->totface - 1;
-		    i >= node->face_offset; --i) {
-			MFace *f = bvh->faces + bvh->face_indices[i];
-			const int sides = f->v4 ? 4 : 3;
-
-			for(j = 0; j < sides; ++j)
-				BB_expand(&node->vb,
-					  bvh->verts[*((&f->v1) + j)].co);
+		int i, totvert= node->uniq_verts + node->face_verts;
+
+		for(i = 0; i < totvert; ++i) {
+			float *co= bvh->verts[node->vert_indices[i]].co;
+			BB_expand(&vb, co);
 		}
 	}
 	else {
-		BB_expand_with_bb(&node->vb,
+		BB_expand_with_bb(&vb,
 				  &bvh->nodes[node->children_offset].vb);
-		BB_expand_with_bb(&node->vb,
+		BB_expand_with_bb(&vb,
 				  &bvh->nodes[node->children_offset + 1].vb);
 	}
+
+	node->vb= vb;
 }
 
 /* Adapted from BLI_kdopbvh.c */
@@ -222,13 +250,13 @@ void check_partitioning(int *face_indices, int lo, int hi, int axis,
 static void grow_nodes(PBVH *bvh, int totnode)
 {
 	if(totnode > bvh->node_mem_count) {
-		Node *prev = bvh->nodes;
+		PBVHNode *prev = bvh->nodes;
 		bvh->node_mem_count *= 1.33;
 		if(bvh->node_mem_count < totnode)
 			bvh->node_mem_count = totnode;
-		bvh->nodes = MEM_callocN(sizeof(Node) * bvh->node_mem_count,
+		bvh->nodes = MEM_callocN(sizeof(PBVHNode) * bvh->node_mem_count,
 					 "bvh nodes");
-		memcpy(bvh->nodes, prev, bvh->totnode * sizeof(Node));
+		memcpy(bvh->nodes, prev, bvh->totnode * sizeof(PBVHNode));
 		MEM_freeN(prev);
 	}
 
@@ -259,19 +287,19 @@ static void map_insert_vert(PBVH *bvh, GHash *map,
 }
 
 /* Find vertices used by the faces in this node and update the draw buffers */
-static void build_leaf_node(PBVH *bvh, Node *node)
+static void build_leaf_node(PBVH *bvh, PBVHNode *node)
 {
 	GHashIterator *iter;
 	GHash *map;
-	int i, j;
+	int i, j, totface;
 
 	map = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
 	
 	node->uniq_verts = node->face_verts = 0;
+	totface= node->totface;
 
-	for(i = node->face_offset + node->totface - 1;
-	    i >= node->face_offset; --i) {
-		MFace *f = bvh->faces + bvh->face_indices[i];
+	for(i = 0; i < totface; ++i) {
+		MFace *f = bvh->faces + node->face_indices[i];
 		int sides = f->v4 ? 4 : 3;
 
 		for(j = 0; j < sides; ++j) {
@@ -300,7 +328,7 @@ static void build_leaf_node(PBVH *bvh, Node *node)
 
 	node->draw_buffers =
 		GPU_build_buffers(map, bvh->verts, bvh->faces,
-				  bvh->face_indices + node->face_offset,
+				  node->face_indices,
 				  node->totface, node->vert_indices,
 				  node->uniq_verts,
 				  node->uniq_verts + node->face_verts);
@@ -329,7 +357,7 @@ void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc,
 	if(count <= LEAF_LIMIT) {
 		bvh->nodes[node_index].flag |= PBVH_Leaf;
 
-		bvh->nodes[node_index].face_offset = offset;
+		bvh->nodes[node_index].face_indices = bvh->face_indices + offset;
 		bvh->nodes[node_index].totface = count;
 
 		/* Still need vb for searches */
@@ -398,7 +426,7 @@ void BLI_pbvh_build(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totv
 		bvh->totnode = 0;
 		if(bvh->node_mem_count < 100) {
 			bvh->node_mem_count = 100;
-			bvh->nodes = MEM_callocN(sizeof(Node) *
+			bvh->nodes = MEM_callocN(sizeof(PBVHNode) *
 						 bvh->node_mem_count,
 						 "bvh initial nodes");
 		}
@@ -408,8 +436,6 @@ void BLI_pbvh_build(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totv
 	bvh->verts = verts;
 	bvh->vert_bitmap = BLI_bitmap_new(totvert);
 
-	BB_reset(&bvh->modified_bb);
-
 	BB_reset(&cb);
 
 	/* For each face, store the AABB and the AABB centroid */
@@ -437,12 +463,9 @@ void BLI_pbvh_build(PBVH *bvh, MFace *faces, MVert *verts, int totface, int totv
 	MEM_freeN(bvh->vert_bitmap);
 }
 
-PBVH *BLI_pbvh_new(BLI_pbvh_HitCallback update_cb, void *update_cb_data)
+PBVH *BLI_pbvh_new(void)
 {
 	PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh");
-	
-	bvh->update_cb = update_cb;
-	bvh->update_cb_data = update_cb_data;
 
 	return bvh;
 }
@@ -469,113 +492,339 @@ void BLI_pbvh_set_source(PBVH *bvh, MVert *mvert, MFace *mface)
 	bvh->faces = mface;
 }
 
-static void do_hit_callback(PBVH *bvh, Node *node,
+static void do_hit_callback(PBVH *bvh, PBVHNode *node,
 			    BLI_pbvh_HitCallback cb, void *data)
 {
-	if(cb) {
-		cb(bvh->face_indices + node->face_offset, node->vert_indices,
-		   node->totface, node->uniq_verts, data);
+	if(cb)
+		cb(node, data);
+}
+
+static void pbvh_iter_begin(PBVHIter *iter, PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data)
+{
+	iter->bvh= bvh;
+	iter->scb= scb;
+	iter->search_data= search_data;
+
+	iter->stack= iter->stackfixed;
+	iter->stackspace= STACK_FIXED_DEPTH;
+
+	iter->stack[0].node= bvh->nodes;
+	iter->stack[0].revisiting= 0;
+	iter->stacksize= 1;
+}
+
+static void pbvh_iter_end(PBVHIter *iter)
+{
+	if(iter->stackspace > STACK_FIXED_DEPTH)
+		MEM_freeN(iter->stack);
+}
+
+static void pbvh_stack_push(PBVHIter *iter, PBVHNode *node, int revisiting)
+{
+	if(iter->stacksize == iter->stackspace) {
+		PBVHStack *newstack;
+
+		iter->stackspace *= 2;
+		newstack= MEM_callocN(sizeof(PBVHStack)*iter->stackspace, "PBVHStack");
+		memcpy(newstack, iter->stack, sizeof(PBVHStack)*iter->stacksize);
+
+		if(iter->stackspace > STACK_FIXED_DEPTH)
+			MEM_freeN(iter->stack);
+		iter->stack= newstack;
 	}
+
+	iter->stack[iter->stacksize].node= node;
+	iter->stack[iter->stacksize].revisiting= revisiting;
+	iter->stacksize++;
 }
 
-static int search_sub(PBVH *bvh, Node *node,
-		      BLI_pbvh_SearchCallback scb, void *search_data_f,
-		      BLI_pbvh_HitCallback hcb, void *hit_data_f,
-		      PBVH_SearchMode mode)
+static PBVHNode *pbvh_iter_next(PBVHIter *iter)
 {
-	void *search_data = search_data_f;
-	void *hit_data = hit_data_f;
+	PBVHNode *node;
+	int revisiting;
+	void *search_data;
+
+	/* purpose here is to traverse tree, visiting child nodes before their
+	   parents, this order is necessary for e.g. computing bounding boxes */
+
+	while(iter->stacksize) {
+		/* pop node */
+		iter->stacksize--;
+		node= iter->stack[iter->stacksize].node;
+		revisiting= iter->stack[iter->stacksize].revisiting;
 
-	if(search_data_f == PBVH_NodeData)
-		search_data = &node->flag;
-	if(hit_data_f == PBVH_DrawData)
-		hit_data = node->draw_buffers;
+		/* revisiting node already checked */
+		if(revisiting)
+			return node;
+
+		/* check search callback */
+		search_data= iter->search_data;
+
+		if(iter->scb && !iter->scb(node, node->vb.bmin, node->vb.bmax, search_data))
+			continue; /* don't traverse, outside of search zone */
 
-	if(scb(node->vb.bmin, node->vb.bmax, search_data)) {
 		if(node->flag & PBVH_Leaf) {
-			switch(mode) {
-			case PBVH_SEARCH_MARK_MODIFIED:
-				node->flag |= PBVH_Modified;
-#ifdef PERFCNTRS
-				++bvh->perf_modified;
-#endif
-				break;
-			case PBVH_SEARCH_MODIFIED:
-				if(node->flag & PBVH_Modified) {
-					if(bvh->update_cb) {
-						do_hit_callback
-							(bvh, node,
-							 bvh->update_cb,
-							 bvh->update_cb_data);
-					}
-
-					GPU_update_buffers(node->draw_buffers,
-							   bvh->verts,
-							   node->vert_indices,
-							   node->uniq_verts +
-							   node->face_verts);
+			/* immediately hit leaf node */
+			return node;
+		}
+		else {
+			/* come back later when children are done */
+			pbvh_stack_push(iter, node, 1);
+
+			/* push two child nodes on the stack */
+			pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset+1, 0);
+			pbvh_stack_push(iter, iter->bvh->nodes+node->children_offset, 0);
+		}
+	}
+
+	return NULL;
+}
+
+void BLI_pbvh_search_gather(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	PBVHNode ***r_array, int *r_tot)
+{
+	PBVHIter iter;
+	PBVHNode **array= NULL, **newarray, *node;
+	int tot= 0, space= 0;
+
+	pbvh_iter_begin(&iter, bvh, scb, search_data);
+
+	while((node=pbvh_iter_next(&iter))) {
+		if(node->flag & PBVH_Leaf) {
+			if(tot == space) {
+				/* resize array if needed */
+				space= (tot == 0)? 32: space*2;
+				newarray= MEM_callocN(sizeof(PBVHNode)*space, "PBVHNodeSearch");
+
+				if(array) {
+					memcpy(newarray, array, sizeof(PBVHNode)*tot);
+					MEM_freeN(array);
 				}
-			default:
-				break;
+
+				array= newarray;
 			}
 
+			array[tot]= node;
+			tot++;
+		}
+	}
+
+	pbvh_iter_end(&iter);
+
+	*r_array= array;
+	*r_tot= tot;
+}
+
+void BLI_pbvh_search_callback(PBVH *bvh,
+	BLI_pbvh_SearchCallback scb, void *search_data,
+	BLI_pbvh_HitCallback hcb, void *hit_data)
+{
+	PBVHIter iter;
+	PBVHNode *node;
+
+	pbvh_iter_begin(&iter, bvh, scb, search_data);
+
+	while((node=pbvh_iter_next(&iter)))
+		if(node->flag & PBVH_Leaf)
 			do_hit_callback(bvh, node, hcb, hit_data);
+
+	pbvh_iter_end(&iter);
+}
+
+static int update_search_cb(PBVHNode *node,
+	float bb_min[3], float bb_max[3], void *data_v)
+{
+	if(node->flag & PBVH_Leaf)
+		return (node->flag & (PBVH_UpdateNormals|PBVH_UpdateBB|PBVH_UpdateDrawBuffers|PBVH_UpdateRedraw));
+	
+	return 1;
+}
+
+static void pbvh_update_face_normals(PBVH *bvh, PBVHNode **nodes,
+	int totnode, float (*face_nors)[3])
+{
+	PBVHNode *node;
+	int n;
+
+	#pragma omp parallel for private(n) schedule(static)
+	for(n = 0; n < totnode; n++) {
+		node= nodes[n];
+
+		if((node->flag & PBVH_UpdateNormals)) {
+			int i, totface, *faces;
+
+			BLI_pbvh_node_get_faces(node, &faces, &totface);
+
+			for(i = 0; i < totface; ++i) {
+				MFace *f = bvh->faces + faces[i];
+				float *fn = face_nors[faces[i]];
+
+				if(f->v4)
+					CalcNormFloat4(bvh->verts[f->v1].co, bvh->verts[f->v2].co,
+								   bvh->verts[f->v3].co, bvh->verts[f->v4].co, fn);
+				else
+					CalcNormFloat(bvh->verts[f->v1].co, bvh->verts[f->v2].co,
+								  bvh->verts[f->v3].co, fn);
+			}
 		}
-		else {
-			int mod = 0;
-			if(search_sub(bvh, bvh->nodes + node->children_offset,
-				      scb, search_data_f, hcb,hit_data_f, mode))
-				mod = 1;
-			if(search_sub(bvh,
-				      bvh->nodes + node->children_offset + 1,
-				      scb, search_data_f, hcb,hit_data_f, mode))
-				mod = 1;
-
-			if(mod)
-				node->flag |= PBVH_Modified;
+	}
+}
+
+static void pbvh_update_BB_normals(PBVH *bvh, PBVHNode **nodes,
+	int totnode, int flag, float (*face_nors)[3], ListBase *fmap)
+{
+	PBVHNode *node;
+	int n;
+
+	/* update BB, vertex normals, redraw flag */
+	#pragma omp parallel for private(n) schedule(static)
+	for(n = 0; n < totnode; n++) {
+		node= nodes[n];
+
+		if((flag & PBVH_UpdateBB) && (node->flag & PBVH_UpdateBB)) {
+			update_node_vb(bvh, node);
+			/* don't clear flag yet, leave it for flushing later */
+		}
+
+		if((flag & PBVH_UpdateNormals) && (node->flag & PBVH_UpdateNormals)) {
+			int i, *verts, totvert;
+
+			BLI_pbvh_node_get_verts(node, &verts, &totvert);
+
+			for(i = 0; i < totvert; ++i) {
+				const int v = verts[i];
+				float no[3] = {0,0,0};
+				IndexNode *face;
+
+				for(face = fmap[v].first; face; face = face->next)
+					VecAddf(no, no, face_nors[face->index]);
+
+				Normalize(no);
+				
+				bvh->verts[v].no[0] = no[0] * 32767;
+				bvh->verts[v].no[1] = no[1] * 32767;
+				bvh->verts[v].no[2] = no[2] * 32767;
+			}
+
+			node->flag &= ~PBVH_UpdateNormals;
 		}
+
+		if((flag & PBVH_UpdateRedraw) && (node->flag & PBVH_UpdateRedraw))
+			node->flag &= ~PBVH_UpdateRedraw;
 	}
+}
 
-	if(mode == PBVH_SEARCH_MODIFIED) {
-#ifdef PERFCNTRS
-		if(node->flag & PBVH_Modified && node->flag & PBVH_Leaf)
-			--bvh->perf_modified;
-#endif
-		if(!bvh->modified_lock)
-			node->flag &= ~PBVH_Modified;
+static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode)
+{
+	PBVHNode *node;
+	int n;
+
+	/* can't be done in parallel with OpenGL */
+	for(n = 0; n < totnode; n++) {
+		node= nodes[n];
+
+		if(node->flag & PBVH_UpdateDrawBuffers) {
+			GPU_update_buffers(node->draw_buffers,
+					   bvh->verts,
+					   node->vert_indices,
+					   node->uniq_verts +
+					   node->face_verts);
+
+			node->flag &= ~PBVH_UpdateDrawBuffers;
+		}
 	}
-	else if(mode == PBVH_SEARCH_UPDATE) {
-		if(node->flag & PBVH_Modified) {
+}
+
+static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node)
+{
+	int update= 0;
+
+	/* difficult to multithread well, we just do single threaded recursive */
+	if(node->flag & PBVH_Leaf) {
+		update= (node->flag & PBVH_UpdateBB);
+		node->flag &= ~PBVH_UpdateBB;
+		return update;
+	}
+	else {
+		update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset);
+		update |= pbvh_flush_bb(bvh, bvh->nodes + node->children_offset + 1);
+
+		if(update)
 			update_node_vb(bvh, node);
-			if(node->flag & PBVH_Leaf)
-				BB_expand_with_bb(&bvh->modified_bb, &node->vb);
-		}
 	}
 
-	return node->flag & PBVH_Modified;
+	return update;
 }
 
-void BLI_pbvh_search(PBVH *bvh, BLI_pbvh_SearchCallback scb, void *search_data,
-		     BLI_pbvh_HitCallback hcb, void *hit_data,
-		     PBVH_SearchMode mode)
+void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3], ListBase *fmap)
 {
-#ifdef PERFCNTRS
-	printf("search mode=%s\n",
-	       mode==PBVH_SEARCH_MARK_MODIFIED?"mark-modified":
-	       mode==PBVH_SEARCH_MODIFIED?"modified":
-	       mode==PBVH_SEARCH_UPDATE?"update":
-	       mode==PBVH_SEARCH_NORMAL?"normal":"unknown-mode");
-	if(mode == PBVH_SEARCH_MARK_MODIFIED)
-		bvh->perf_modified = 0;
-#endif
+	PBVHNode **nodes;
+	int totnode;
 
-	search_sub(bvh, bvh->nodes, scb, search_data, hcb, hit_data, mode);
-#ifdef PERFCNTRS
-	printf("%d nodes marked modified\n", bvh->perf_modified);
-	printf("search complete\n\n");
-#endif
+	BLI_pbvh_search_gather(bvh, update_search_cb, NULL, &nodes, &totnode);
+
+	if(flag & PBVH_UpdateNormals)
+		pbvh_update_face_normals(bvh, nodes, totnode, face_nors);
+
+	if(flag & (PBVH_UpdateNormals|PBVH_UpdateBB|PBVH_UpdateRedraw))
+		pbvh_update_BB_normals(bvh, nodes, totnode, flag, face_nors, fmap);
+
+	if(flag & PBVH_UpdateDrawBuffers)
+		pbvh_update_draw_buffers(bvh, nodes, totnode);
+
+	if(flag & PBVH_UpdateBB)
+		pbvh_flush_bb(bvh, bvh->nodes);
+
+	if(nodes) MEM_freeN(nodes);
 }
 
+void BLI_pbvh_redraw_bounding_box(PBVH *bvh, float bb_min[3], float bb_max[3])
+{
+	PBVHIter iter;
+	PBVHNode *node;
+	BB bb;
+
+	BB_reset(&bb);
+
+	pbvh_iter_begin(&iter, bvh, NULL, NULL);
+
+	while((node=pbvh_iter_next(&iter)))
+		if(node->flag & PBVH_UpdateRedraw)
+			BB_expand_with_bb(&bb, &node->vb);
+
+	pbvh_iter_end(&iter);
+
+	VecCopyf(bb_min, bb.bmin);
+	VecCopyf(bb_max, bb.bmax);
+}
+
+/***************************** Node Access ***********************************/
+
+void BLI_pbvh_node_mark_update(PBVHNode *node)
+{
+	node->flag |= PBVH_UpdateNormals|PBVH_UpdateBB|PBVH_UpdateDrawBuffers|PBVH_UpdateRedraw;
+}
+
+void BLI_pbvh_node_get_verts(PBVHNode *node, int **vert_indices, int *totvert)
+{
+	*vert_indices= node->vert_indices;
+	*totvert= node->uniq_verts;
+}
+
+void BLI_pbvh_node_get_faces(PBVHNode *node, int **face_indices, int *totface)
+{
+	*face_indices= node->face_indices;
+	*totface= node->totface;
+}
+
+void *BLI_pbvh_node_get_draw_buffers(PBVHNode *node)
+{
+	return node->draw_buffers;
+}
+
+/********************************* Raycast ***********************************/
+
 typedef struct {
 	/* Ray */
 	float start[3];
@@ -584,7 +833,7 @@ typedef struct {
 } RaycastData;
 
 /* Adapted from here: http://www.gamedev.net/community/forums/topic.asp?topic_id=459973 */
-static int ray_aabb_intersect(float bb_min[3], float bb_max[3], void *data_v)
+static int ray_aabb_intersect(PBVHNode *node, float bb_min[3], float bb_max[3], void *data_v)
 {
 	RaycastData *ray = data_v;
 	float bbox[2][3];
@@ -637,29 +886,6 @@ void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data,
 	rcd.sign[1] = rcd.inv_dir[1] < 0;
 	rcd.sign[2] = rcd.inv_dir[2] < 0;
 
-	BLI_pbvh_search(bvh, ray_aabb_intersect, &rcd, cb, data,
-			PBVH_SEARCH_NORMAL);
-}
-
-int BLI_pbvh_update_search_cb(float bb_min[3], float bb_max[3], void *data_v)
-{
-	int *data = data_v;
-
-	return ((*data) & PBVH_Modified);
-}
-
-void BLI_pbvh_modified_bounding_box(PBVH *bvh, float bb_min[3], float bb_max[3])
-{
-	VecCopyf(bb_min, bvh->modified_bb.bmin);
-	VecCopyf(bb_max, bvh->modified_bb.bmax);
+	BLI_pbvh_search_callback(bvh, ray_aabb_intersect, &rcd, cb, data);
 }
 
-void BLI_pbvh_reset_modified_bounding_box(PBVH *bvh)
-{
-	BB_reset(&bvh->modified_bb);	
-}
-
-void BLI_pbvh_toggle_modified_lock(PBVH *bvh)
-{
-	bvh->modified_lock = !bvh->modified_lock;
-}
diff --git a/source/blender/editors/sculpt_paint/paint_stroke.c b/source/blender/editors/sculpt_paint/paint_stroke.c
index f8ffaacc0b7..c2d22089442 100644
--- a/source/blender/editors/sculpt_paint/paint_stroke.c
+++ b/source/blender/editors/sculpt_paint/paint_stroke.c
@@ -234,9 +234,7 @@ int paint_stroke_modal(bContext *C, wmOperator *op, wmEvent *event)
 {
 	PaintStroke *stroke = op->customdata;
 	float mouse[2];
-
-	if(event->type == TIMER && (event->customdata != stroke->timer))
-		return OPERATOR_RUNNING_MODAL;
+	int first= 0;
 
 	if(!stroke->stroke_started) {
 		stroke->last_mouse_position[0] = event->x;
@@ -251,26 +249,27 @@ int paint_stroke_modal(bContext *C, wmOperator *op, wmEvent *event)
 				stroke->timer = WM_event_add_timer(CTX_wm_manager(C), CTX_wm_window(C), TIMER, stroke->brush->rate);
 		}
 
+		first= 1;
 		//ED_region_tag_redraw(ar);
 	}
 
-	if(stroke->stroke_started) {
-		if(paint_smooth_stroke(stroke, mouse, event)) {
-			if(paint_space_stroke_enabled(stroke->brush)) {
-				if(!paint_space_stroke(C, op, event, mouse))
-					;//ED_region_tag_redraw(ar);
+	/* TODO: fix hardcoded event here */
+	if(first || event->type == MOUSEMOVE || (event->type == TIMER && (event->customdata == stroke->timer))) {
+		if(stroke->stroke_started) {
+			if(paint_smooth_stroke(stroke, mouse, event)) {
+				if(paint_space_stroke_enabled(stroke->brush)) {
+					if(!paint_space_stroke(C, op, event, mouse))
+						;//ED_region_tag_redraw(ar);
+				}
+				else
+					paint_brush_stroke_add_step(C, op, event, mouse);
 			}
 			else
-				paint_brush_stroke_add_step(C, op, event, mouse);
+				;//ED_region_tag_redraw(ar);
 		}
-		else
-			;//ED_region_tag_redraw(ar);
 	}
-
-	/* TODO: fix hardcoded event here */
-	if(event->type == LEFTMOUSE && event->val == KM_RELEASE) {
-		/* Exit stroke, free data */
-
+	else if(event->type == LEFTMOUSE && event->val == KM_RELEASE) {
+		/* exit stroke, free data */
 		if(stroke->smooth_stroke_cursor)
 			WM_paint_cursor_end(CTX_wm_manager(C), stroke->smooth_stroke_cursor);
 
@@ -281,8 +280,8 @@ int paint_stroke_modal(bContext *C, wmOperator *op, wmEvent *event)
 		MEM_freeN(stroke);
 		return OPERATOR_FINISHED;
 	}
-	else
-		return OPERATOR_RUNNING_MODAL;
+
+	return OPERATOR_RUNNING_MODAL;
 }
 
 int paint_stroke_exec(bContext *C, wmOperator *op)
diff --git a/source/blender/editors/sculpt_paint/sculpt.c b/source/blender/editors/sculpt_paint/sculpt.c
index 2f4d2d9e8bf..e29f0d56ba2 100644
--- a/source/blender/editors/sculpt_paint/sculpt.c
+++ b/source/blender/editors/sculpt_paint/sculpt.c
@@ -142,6 +142,7 @@ typedef struct StrokeCache {
 	float flip;
 	float pressure;
 	float mouse[2];
+	float bstrength;
 
 	/* The rest is temporary storage that isn't saved as a property */
 
@@ -158,6 +159,8 @@ typedef struct StrokeCache {
 	float rotation; /* Texture rotation (radians) for anchored and rake modes */
 	int pixel_radius, previous_pixel_radius;
 	ListBase grab_active_verts[8]; /* The same list of verts is used throught grab stroke */
+	PBVHNode **grab_active_nodes[8];
+	int grab_active_totnode[8];
 	float grab_delta[3], grab_delta_symmetry[3];
 	float old_grab_location[3];
 	int symmetry; /* Symmetry index between 0 and 7 */
@@ -202,7 +205,7 @@ int sculpt_get_redraw_rect(ARegion *ar, RegionView3D *rv3d,
 
 	view3d_get_object_project_mat(rv3d, ob, pmat);
 
-	BLI_pbvh_modified_bounding_box(ob->sculpt->tree, bb_min, bb_max);
+	BLI_pbvh_redraw_bounding_box(ob->sculpt->tree, bb_min, bb_max);
 
 	rect->xmin = rect->ymin = INT_MAX;
 	rect->xmax = rect->ymax = INT_MIN;
@@ -239,13 +242,21 @@ void sculpt_get_redraw_planes(float planes[4][4], ARegion *ar,
 
 	view3d_get_transformation(ar, rv3d, ob, &mats);
 	sculpt_get_redraw_rect(ar, rv3d,ob, &rect);
-	BLI_pbvh_reset_modified_bounding_box(ob->sculpt->tree);
-
 
+#if 1
+	/* use some extra space just in case */
+	rect.xmin -= 2;
+	rect.xmax += 2;
+	rect.ymin -= 2;
+	rect.ymax += 2;
+#else
+	/* it was doing this before, allows to redraw a smaller
+	   part of the screen but also gives artifaces .. */
 	rect.xmin += 2;
 	rect.xmax -= 2;
 	rect.ymin += 2;
 	rect.ymax -= 2;
+#endif
 
 	view3d_calculate_clipping(bb, planes, &mats, &rect);
 
@@ -253,8 +264,55 @@ void sculpt_get_redraw_planes(float planes[4][4], ARegion *ar,
 		((float*)planes)[i] = -((float*)planes)[i];
 
 	MEM_freeN(bb);
+
+	/* clear redraw flag from nodes */
+	BLI_pbvh_update(ob->sculpt->tree, PBVH_UpdateRedraw, NULL, NULL);
+}
+
+/*** Looping Over Nodes in a BVH Node ***/
+
+typedef struct SculptVertexData {
+	float radius_squared;
+	float location[3];
+
+	MVert *mvert;
+	int *verts;
+	int i, index, totvert;
+
+	float *co;
+	short *no;
+	float dist;
+} SculptVertexData;
+
+static void sculpt_node_verts_init(Sculpt *sd, SculptSession *ss, PBVHNode *node, SculptVertexData *vd)
+{
+	vd->radius_squared= ss->cache->radius*ss->cache->radius;
+	VecCopyf(vd->location, ss->cache->location);
+
+	vd->mvert= ss->mvert;
+	vd->i= 0;
+	BLI_pbvh_node_get_verts(node, &vd->verts, &vd->totvert);
 }
 
+static int sculpt_node_verts_next(SculptVertexData *vd)
+{
+	while(vd->i < vd->totvert) {
+		float delta[3], dsq;
+
+		vd->index= vd->verts[vd->i++];
+		vd->co= vd->mvert[vd->index].co;
+		vd->no= vd->mvert[vd->index].no;
+		VECSUB(delta, vd->co, vd->location);
+		dsq = INPR(delta, delta);
+
+		if(dsq < vd->radius_squared) {
+			vd->dist = sqrt(dsq);
+			return 1;
+		}
+	}
+	
+	return 0;
+}
 
 /* ===== Sculpting =====
  *
@@ -294,6 +352,168 @@ static float brush_strength(Sculpt *sd, StrokeCache *cache)
 	}
 }
 
+/* Uses symm to selectively flip any axis of a coordinate. */
+static void flip_coord(float out[3], float in[3], const char symm)
+{
+	if(symm & SCULPT_SYMM_X)
+		out[0]= -in[0];
+	else
+		out[0]= in[0];
+	if(symm & SCULPT_SYMM_Y)
+		out[1]= -in[1];
+	else
+		out[1]= in[1];
+	if(symm & SCULPT_SYMM_Z)
+		out[2]= -in[2];
+	else
+		out[2]= in[2];
+}
+
+/* Get a pixel from the texcache at (px, py) */
+static unsigned char get_texcache_pixel(const SculptSession *ss, int px, int py)
+{
+	unsigned *p;
+	p = ss->texcache + py * ss->texcache_side + px;
+	return ((unsigned char*)(p))[0];
+}
+
+static float get_texcache_pixel_bilinear(const SculptSession *ss, float u, float v)
+{
+	int x, y, x2, y2;
+	const int tc_max = ss->texcache_side - 1;
+	float urat, vrat, uopp;
+
+	if(u < 0) u = 0;
+	else if(u >= ss->texcache_side) u = tc_max;
+	if(v < 0) v = 0;
+	else if(v >= ss->texcache_side) v = tc_max;
+
+	x = floor(u);
+	y = floor(v);
+	x2 = x + 1;
+	y2 = y + 1;
+
+	if(x2 > ss->texcache_side) x2 = tc_max;
+	if(y2 > ss->texcache_side) y2 = tc_max;
+	
+	urat = u - x;
+	vrat = v - y;
+	uopp = 1 - urat;
+		
+	return ((get_texcache_pixel(ss, x, y) * uopp +
+		 get_texcache_pixel(ss, x2, y) * urat) * (1 - vrat) + 
+		(get_texcache_pixel(ss, x, y2) * uopp +
+		 get_texcache_pixel(ss, x2, y2) * urat) * vrat) / 255.0;
+}
+
+/* Return a multiplier for brush strength on a particular vertex. */
+static float tex_strength(SculptSession *ss, Brush *br, float *point, const float len)
+{
+	MTex *tex = NULL;
+	float avg= 1;
+
+	if(br->texact >= 0)
+		tex = br->mtex[br->texact];
+
+	if(!tex) {
+		avg= 1;
+	}
+	else if(tex->brush_map_mode == MTEX_MAP_MODE_3D) {
+		float jnk;
+
+		/* Get strength by feeding the vertex 
+		   location directly into a texture */
+		externtex(tex, point, &avg,
+			  &jnk, &jnk, &jnk, &jnk);
+	}
+	else if(ss->texcache) {
+		const float bsize= ss->cache->pixel_radius * 2;
+		const float rot= tex->rot + ss->cache->rotation;
+		int px, py;
+		float flip[3], point_2d[2];
+
+		/* If the active area is being applied for symmetry, flip it
+		   across the symmetry axis in order to project it. This insures
+		   that the brush texture will be oriented correctly. */
+		VecCopyf(flip, point);
+		flip_coord(flip, flip, ss->cache->symmetry);
+		projectf(ss->cache->mats, flip, point_2d);
+
+		/* For Tile and Drag modes, get the 2D screen coordinates of the
+		   and scale them up or down to the texture size. */
+		if(tex->brush_map_mode == MTEX_MAP_MODE_TILED) {
+			const int sx= (const int)tex->size[0];
+			const int sy= (const int)tex->size[1];
+			
+			float fx= point_2d[0];
+			float fy= point_2d[1];
+			
+			float angle= atan2(fy, fx) - rot;
+			float flen= sqrtf(fx*fx + fy*fy);
+			
+			if(rot<0.001 && rot>-0.001) {
+				px= point_2d[0];
+				py= point_2d[1];
+			} else {
+				px= flen * cos(angle) + 2000;
+				py= flen * sin(angle) + 2000;
+			}
+			if(sx != 1)
+				px %= sx-1;
+			if(sy != 1)
+				py %= sy-1;
+			avg= get_texcache_pixel_bilinear(ss, ss->texcache_side*px/sx, ss->texcache_side*py/sy);
+		}
+		else if(tex->brush_map_mode == MTEX_MAP_MODE_FIXED) {
+			float fx= (point_2d[0] - ss->cache->mouse[0]) / bsize;
+			float fy= (point_2d[1] - ss->cache->mouse[1]) / bsize;
+
+			float angle= atan2(fy, fx) - rot;
+			float flen= sqrtf(fx*fx + fy*fy);
+			
+			fx = flen * cos(angle) + 0.5;
+			fy = flen * sin(angle) + 0.5;
+
+			avg= get_texcache_pixel_bilinear(ss, fx * ss->texcache_side, fy * ss->texcache_side);
+		}
+	}
+
+	avg*= brush_curve_strength(br, len, ss->cache->radius); /* Falloff curve */
+
+	return avg;
+}
+
+typedef struct {
+	Sculpt *sd;
+	SculptSession *ss;
+	float radius_squared;
+	ListBase *active_verts;
+	float area_normal[3];
+} SculptSearchSphereData;
+
+/* Test AABB against sphere */
+static int sculpt_search_sphere_cb(PBVHNode *node,
+	float bb_min[3], float bb_max[3], void *data_v)
+{
+	SculptSearchSphereData *data = data_v;
+	float *center = data->ss->cache->location, nearest[3];
+	float t[3];
+	int i;
+
+	for(i = 0; i < 3; ++i) {
+		if(bb_min[i] > center[i])
+			nearest[i] = bb_min[i];
+		else if(bb_max[i] < center[i])
+			nearest[i] = bb_max[i];
+		else
+			nearest[i] = center[i]; 
+	}
+	
+	VecSubf(t, center, nearest);
+
+	return t[0] * t[0] + t[1] * t[1] + t[2] * t[2] < data->radius_squared;
+}
+
 /* Handles clipping against a mirror modifier and SCULPT_LOCK axis flags */
 static void sculpt_clip(Sculpt *sd, SculptSession *ss, float *co, const float val[3])
 {
@@ -323,26 +543,41 @@ static void add_norm_if(float view_vec[3], float out[3], float out_flip[3], cons
 	}
 }
 
-/* Currently only for the draw brush; finds average normal for all active
-   vertices */
-static void calc_area_normal(Sculpt *sd, SculptSession *ss, float out[3], const ListBase* active_verts)
+/* For draw/layer/flatten; finds average normal for all active vertices */
+static void calc_area_normal(Sculpt *sd, SculptSession *ss, float area_normal[3], PBVHNode **nodes, int totnode)
 {
 	Brush *brush = paint_brush(&sd->paint);
 	StrokeCache *cache = ss->cache;
-	ActiveData *node = active_verts->first;
 	const int view = 0; /* XXX: should probably be a flag, not number: brush_type==SCULPT_TOOL_DRAW ? sculptmode_brush()->view : 0; */
-	float out_flip[3];
-	float *out_dir = cache->view_normal_symmetry;
-	
-	out[0]=out[1]=out[2] = out_flip[0]=out_flip[1]=out_flip[2] = 0;
+	float out[3] = {0.0f, 0.0f, 0.0f};
+	float out_flip[3] = {0.0f, 0.0f, 0.0f};
+	float out_dir[3];
+	int n;
+
+	VecCopyf(out_dir, cache->view_normal_symmetry);
+
+	/* threaded loop over nodes */
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
+		float nout[3] = {0.0f, 0.0f, 0.0f};
+		float nout_flip[3] = {0.0f, 0.0f, 0.0f};
+		
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
 
-	if(brush->flag & BRUSH_ANCHORED) {
-		for(; node; node = node->next)
-			add_norm_if(out_dir, out, out_flip, cache->orig_norms[node->Index]);
-	}
-	else {
-		for(; node; node = node->next)
-			add_norm_if(out_dir, out, out_flip, ss->mvert[node->Index].no);
+		if(brush->flag & BRUSH_ANCHORED) {
+			while(sculpt_node_verts_next(&vd))
+				add_norm_if(out_dir, nout, nout_flip, cache->orig_norms[vd.index]);
+		}
+		else {
+			while(sculpt_node_verts_next(&vd))
+				add_norm_if(out_dir, nout, nout_flip, ss->mvert[vd.index].no);
+		}
+
+		/* we sum per node and add together later for threads */
+		#pragma omp critical
+		VecAddf(out, out, nout);
+		VecAddf(out_flip, out_flip, nout_flip);
 	}
 
 	if (out[0]==0.0 && out[1]==0.0 && out[2]==0.0) {
@@ -351,32 +586,47 @@ static void calc_area_normal(Sculpt *sd, SculptSession *ss, float out[3], const
 	
 	Normalize(out);
 
-	if(out_dir) {
-		out[0] = out_dir[0] * view + out[0] * (10-view);
-		out[1] = out_dir[1] * view + out[1] * (10-view);
-		out[2] = out_dir[2] * view + out[2] * (10-view);
-	}
+	out[0] = out_dir[0] * view + out[0] * (10-view);
+	out[1] = out_dir[1] * view + out[1] * (10-view);
+	out[2] = out_dir[2] * view + out[2] * (10-view);
 	
 	Normalize(out);
+	VecCopyf(area_normal, out);
 }
 
-static void do_draw_brush(Sculpt *sd, SculptSession *ss, const ListBase* active_verts)
+static void do_draw_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
 {
-	float area_normal[3];
-	ActiveData *node= active_verts->first;
-
-	calc_area_normal(sd, ss, area_normal, active_verts);
-	
-	while(node){
-		float *co= ss->mvert[node->Index].co;
+	Brush *brush = paint_brush(&sd->paint);
+	float offset[3], area_normal[3];
+	float bstrength= ss->cache->bstrength;
+	int n;
+
+	/* area normal */
+	calc_area_normal(sd, ss, area_normal, nodes, totnode);
+
+	/* offset with as much as possible factored in already */
+	offset[0]= area_normal[0]*ss->cache->radius*ss->cache->scale[0]*bstrength;
+	offset[1]= area_normal[1]*ss->cache->radius*ss->cache->scale[1]*bstrength;
+	offset[2]= area_normal[2]*ss->cache->radius*ss->cache->scale[2]*bstrength;
+
+	/* threaded loop over nodes */
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
+		
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
 
-		const float val[3]= {co[0]+area_normal[0]*ss->cache->radius*node->Fade*ss->cache->scale[0],
-		                     co[1]+area_normal[1]*ss->cache->radius*node->Fade*ss->cache->scale[1],
-		                     co[2]+area_normal[2]*ss->cache->radius*node->Fade*ss->cache->scale[2]};
+		while(sculpt_node_verts_next(&vd)) {
+			/* offset vertex */
+			const float fade = tex_strength(ss, brush, vd.co, vd.dist);
+			const float val[3]= {vd.co[0] + offset[0]*fade,
+								 vd.co[1] + offset[1]*fade,
+								 vd.co[2] + offset[2]*fade};
 
-		sculpt_clip(sd, ss, co, val);
+			sculpt_clip(sd, ss, vd.co, val);
+		}
 
-		node= node->next;
+		BLI_pbvh_node_mark_update(nodes[n]);
 	}
 }
 
@@ -424,48 +674,67 @@ static void neighbor_average(SculptSession *ss, float avg[3], const int vert)
 		VecCopyf(avg, ss->mvert[vert].co);
 }
 
-static void do_smooth_brush(Sculpt *s, SculptSession *ss, const ListBase* active_verts)
+static void do_smooth_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
 {
-	ActiveData *node= active_verts->first;
-	int i;
-	
-	for(i = 0; i < 2; ++i) {
-		while(node){
-			float *co= ss->mvert[node->Index].co;
-			float avg[3], val[3];
-			
-			neighbor_average(ss, avg, node->Index);
-			val[0] = co[0]+(avg[0]-co[0])*node->Fade;
-			val[1] = co[1]+(avg[1]-co[1])*node->Fade;
-			val[2] = co[2]+(avg[2]-co[2])*node->Fade;
+	Brush *brush = paint_brush(&sd->paint);
+	float bstrength= ss->cache->bstrength;
+	int iteration, n;
+
+	for(iteration = 0; iteration < 2; ++iteration) {
+		#pragma omp parallel for private(n) schedule(static)
+		for(n=0; n<totnode; n++) {
+			SculptVertexData vd;
 			
-			sculpt_clip(s, ss, co, val);			
+			sculpt_node_verts_init(sd, ss, nodes[n], &vd);
+
+			while(sculpt_node_verts_next(&vd)) {
+				const float fade = tex_strength(ss, brush, vd.co, vd.dist)*bstrength;
+				float avg[3], val[3];
+				
+				neighbor_average(ss, avg, vd.index);
+				val[0] = vd.co[0]+(avg[0]-vd.co[0])*fade;
+				val[1] = vd.co[1]+(avg[1]-vd.co[1])*fade;
+				val[2] = vd.co[2]+(avg[2]-vd.co[2])*fade;
+				
+				sculpt_clip(sd, ss, vd.co, val);			
+			}
 
-			node= node->next;
+			BLI_pbvh_node_mark_update(nodes[n]);
 		}
 	}
 }
 
-static void do_pinch_brush(Sculpt *s, SculptSession *ss, const ListBase* active_verts)
+static void do_pinch_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
 {
- 	ActiveData *node= active_verts->first;
+	Brush *brush = paint_brush(&sd->paint);
+	float bstrength= ss->cache->bstrength;
+	int n;
 
-	while(node) {
-		float *co= ss->mvert[node->Index].co;
-		const float val[3]= {co[0]+(ss->cache->location[0]-co[0])*node->Fade,
-		                     co[1]+(ss->cache->location[1]-co[1])*node->Fade,
-		                     co[2]+(ss->cache->location[2]-co[2])*node->Fade};
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
+		
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
 
-		sculpt_clip(s, ss, co, val);
-		node= node->next;
+		while(sculpt_node_verts_next(&vd)) {
+			const float fade = tex_strength(ss, brush, vd.co, vd.dist)*bstrength;
+			const float val[3]= {vd.co[0]+(vd.location[0]-vd.co[0])*fade,
+								 vd.co[1]+(vd.location[1]-vd.co[1])*fade,
+								 vd.co[2]+(vd.location[2]-vd.co[2])*fade};
+			
+			sculpt_clip(sd, ss, vd.co, val);			
+		}
+
+		BLI_pbvh_node_mark_update(nodes[n]);
 	}
 }
 
-static void do_grab_brush(Sculpt *sd, SculptSession *ss)
+static void do_grab_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
 {
 	ActiveData *node= ss->cache->grab_active_verts[ss->cache->symmetry].first;
 	float add[3];
 	float grab_delta[3];
+	int n;
 	
 	VecCopyf(grab_delta, ss->cache->grab_delta_symmetry);
 	
@@ -480,84 +749,116 @@ static void do_grab_brush(Sculpt *sd, SculptSession *ss)
 
 		node= node->next;
 	}
+
+	for(n=0; n<totnode; n++)
+		BLI_pbvh_node_mark_update(nodes[n]);
 }
 
-static void do_layer_brush(Sculpt *sd, SculptSession *ss, const ListBase *active_verts)
+static void do_layer_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
 {
+	Brush *brush = paint_brush(&sd->paint);
+	float bstrength= ss->cache->bstrength;
 	float area_normal[3];
-	ActiveData *node= active_verts->first;
 	float lim= ss->cache->radius / 4;
+	int n;
 
 	if(ss->cache->flip)
 		lim = -lim;
 
-	calc_area_normal(sd, ss, area_normal, active_verts);
+	calc_area_normal(sd, ss, area_normal, nodes, totnode);
 
-	while(node){
-		float *disp= &ss->layer_disps[node->Index];
-		float *co= ss->mvert[node->Index].co;
-		float val[3];
-		
-		*disp+= node->Fade;
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
 		
-		/* Don't let the displacement go past the limit */
-		if((lim < 0 && *disp < lim) || (lim > 0 && *disp > lim))
-			*disp = lim;
-		
-		val[0] = ss->mesh_co_orig[node->Index][0]+area_normal[0] * *disp*ss->cache->scale[0];
-		val[1] = ss->mesh_co_orig[node->Index][1]+area_normal[1] * *disp*ss->cache->scale[1];
-		val[2] = ss->mesh_co_orig[node->Index][2]+area_normal[2] * *disp*ss->cache->scale[2];
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
 
-		sculpt_clip(sd, ss, co, val);
+		while(sculpt_node_verts_next(&vd)) {
+			const float fade = tex_strength(ss, brush, vd.co, vd.dist)*bstrength;
+			float *disp= &ss->layer_disps[vd.index];
+			float val[3];
+			
+			*disp+= fade;
+			
+			/* Don't let the displacement go past the limit */
+			if((lim < 0 && *disp < lim) || (lim > 0 && *disp > lim))
+				*disp = lim;
+			
+			val[0] = ss->mesh_co_orig[vd.index][0]+area_normal[0] * *disp*ss->cache->scale[0];
+			val[1] = ss->mesh_co_orig[vd.index][1]+area_normal[1] * *disp*ss->cache->scale[1];
+			val[2] = ss->mesh_co_orig[vd.index][2]+area_normal[2] * *disp*ss->cache->scale[2];
 
-		node= node->next;
+			sculpt_clip(sd, ss, vd.co, val);
+		}
+
+		BLI_pbvh_node_mark_update(nodes[n]);
 	}
 }
 
-static void do_inflate_brush(Sculpt *s, SculptSession *ss, const ListBase *active_verts)
+static void do_inflate_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode)
 {
-	ActiveData *node= active_verts->first;
-	float add[3];
+	Brush *brush = paint_brush(&sd->paint);
+	float bstrength= ss->cache->bstrength;
+	int n;
 
-	while(node) {
-		float *co= ss->mvert[node->Index].co;
-		short *no= ss->mvert[node->Index].no;
-
-		add[0]= no[0]/ 32767.0f;
-		add[1]= no[1]/ 32767.0f;
-		add[2]= no[2]/ 32767.0f;
-		VecMulf(add, node->Fade * ss->cache->radius);
-		add[0]*= ss->cache->scale[0];
-		add[1]*= ss->cache->scale[1];
-		add[2]*= ss->cache->scale[2];
-		VecAddf(add, add, co);
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
 		
-		sculpt_clip(s, ss, co, add);
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
 
-		node= node->next;
+		while(sculpt_node_verts_next(&vd)) {
+			const float fade = tex_strength(ss, brush, vd.co, vd.dist)*bstrength;
+			float add[3];
+			
+			add[0]= vd.no[0]/32767.0f;
+			add[1]= vd.no[1]/32767.0f;
+			add[2]= vd.no[2]/32767.0f;
+			VecMulf(add, fade * ss->cache->radius);
+			add[0]*= ss->cache->scale[0];
+			add[1]*= ss->cache->scale[1];
+			add[2]*= ss->cache->scale[2];
+			VecAddf(add, add, vd.co);
+			
+			sculpt_clip(sd, ss, vd.co, add);
+		}
+
+		BLI_pbvh_node_mark_update(nodes[n]);
 	}
 }
 
-static void calc_flatten_center(SculptSession *ss, ActiveData *node, float co[3])
+static void calc_flatten_center(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode, float co[3])
 {
-	ActiveData *outer[FLATTEN_SAMPLE_SIZE];
-	int i;
+	float outer_dist[FLATTEN_SAMPLE_SIZE];
+	int outer_index[FLATTEN_SAMPLE_SIZE];
+	int i, n;
 	
-	for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i)
-		outer[i] = node;
+	for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i) {
+		outer_index[i] = 0;
+		outer_dist[i]= -1.0f;
+	}
+		
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
 		
-	for(; node; node = node->next) {
-		for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i) {
-			if(node->dist > outer[i]->dist) {
-				outer[i] = node;
-				break;
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
+
+		while(sculpt_node_verts_next(&vd)) {
+			for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i) {
+				if(vd.dist > outer_dist[i]) {
+					outer_index[i] = vd.index;
+					break;
+				}
 			}
 		}
+
+		BLI_pbvh_node_mark_update(nodes[n]);
 	}
 	
 	co[0] = co[1] = co[2] = 0.0f;
 	for(i = 0; i < FLATTEN_SAMPLE_SIZE; ++i)
-		VecAddf(co, co, ss->mvert[outer[i]->Index].co);
+		VecAddf(co, co, ss->mvert[outer_index[i]].co);
 	VecMulf(co, 1.0f / FLATTEN_SAMPLE_SIZE);
 }
 
@@ -589,15 +890,17 @@ static int plane_point_side(float co[3], float plane_normal[3], float plane_cent
 	return d <= 0.0f;
 }
 
-static void do_flatten_clay_brush(Sculpt *sd, SculptSession *ss, const ListBase *active_verts, int clay)
+static void do_flatten_clay_brush(Sculpt *sd, SculptSession *ss, PBVHNode **nodes, int totnode, int clay)
 {
-	ActiveData *node= active_verts->first;
 	/* area_normal and cntr define the plane towards which vertices are squashed */
+	Brush *brush = paint_brush(&sd->paint);
+	float bstrength= ss->cache->bstrength;
 	float area_normal[3];
 	float cntr[3], cntr2[3], bstr = 0;
-	int flip = 0;
-	calc_area_normal(sd, ss, area_normal, active_verts);
-	calc_flatten_center(ss, node, cntr);
+	int n, flip = 0;
+
+	calc_area_normal(sd, ss, area_normal, nodes, totnode);
+	calc_flatten_center(sd, ss, nodes, totnode, cntr);
 
 	if(clay) {
 		bstr= brush_strength(sd, ss->cache);
@@ -608,211 +911,58 @@ static void do_flatten_clay_brush(Sculpt *sd, SculptSession *ss, const ListBase
 		flip = bstr < 0;
 	}
 
-	while(node){
-		float *co= ss->mvert[node->Index].co;
-		float intr[3], val[3];
+	#pragma omp parallel for private(n) schedule(static)
+	for(n=0; n<totnode; n++) {
+		SculptVertexData vd;
 		
-		if(!clay || plane_point_side(co, area_normal, cntr2, flip)) {
-			/* Find the intersection between squash-plane and vertex (along the area normal) */		
-			point_plane_project(intr, co, area_normal, cntr);
+		sculpt_node_verts_init(sd, ss, nodes[n], &vd);
 
-			VecSubf(val, intr, co);
-
-			if(clay) {
-				if(bstr > FLT_EPSILON)
-					VecMulf(val, node->Fade / bstr);
+		while(sculpt_node_verts_next(&vd)) {
+			float intr[3], val[3];
+			
+			if(!clay || plane_point_side(vd.co, area_normal, cntr2, flip)) {
+				const float fade = tex_strength(ss, brush, vd.co, vd.dist)*bstrength;
+
+				/* Find the intersection between squash-plane and vertex (along the area normal) */		
+				point_plane_project(intr, vd.co, area_normal, cntr);
+
+				VecSubf(val, intr, vd.co);
+
+				if(clay) {
+					if(bstr > FLT_EPSILON)
+						VecMulf(val, fade / bstr);
+					else
+						VecMulf(val, fade);
+					/* Clay displacement */
+					val[0]+=area_normal[0] * ss->cache->scale[0]*fade;
+					val[1]+=area_normal[1] * ss->cache->scale[1]*fade;
+					val[2]+=area_normal[2] * ss->cache->scale[2]*fade;
+				}
 				else
-					VecMulf(val, node->Fade);
-				/* Clay displacement */
-				val[0]+=area_normal[0] * ss->cache->scale[0]*node->Fade;
-				val[1]+=area_normal[1] * ss->cache->scale[1]*node->Fade;
-				val[2]+=area_normal[2] * ss->cache->scale[2]*node->Fade;
-			}
-			else
-				VecMulf(val, fabs(node->Fade));
-
-			VecAddf(val, val, co);
-
-			sculpt_clip(sd, ss, co, val);
-
-		}
-		
-		node= node->next;
-	}
-}
-
-/* Uses symm to selectively flip any axis of a coordinate. */
-static void flip_coord(float out[3], float in[3], const char symm)
-{
-	if(symm & SCULPT_SYMM_X)
-		out[0]= -in[0];
-	else
-		out[0]= in[0];
-	if(symm & SCULPT_SYMM_Y)
-		out[1]= -in[1];
-	else
-		out[1]= in[1];
-	if(symm & SCULPT_SYMM_Z)
-		out[2]= -in[2];
-	else
-		out[2]= in[2];
-}
-
-/* Get a pixel from the texcache at (px, py) */
-static unsigned char get_texcache_pixel(const SculptSession *ss, int px, int py)
-{
-	unsigned *p;
-	p = ss->texcache + py * ss->texcache_side + px;
-	return ((unsigned char*)(p))[0];
-}
-
-static float get_texcache_pixel_bilinear(const SculptSession *ss, float u, float v)
-{
-	int x, y, x2, y2;
-	const int tc_max = ss->texcache_side - 1;
-	float urat, vrat, uopp;
-
-	if(u < 0) u = 0;
-	else if(u >= ss->texcache_side) u = tc_max;
-	if(v < 0) v = 0;
-	else if(v >= ss->texcache_side) v = tc_max;
-
-	x = floor(u);
-	y = floor(v);
-	x2 = x + 1;
-	y2 = y + 1;
-
-	if(x2 > ss->texcache_side) x2 = tc_max;
-	if(y2 > ss->texcache_side) y2 = tc_max;
-	
-	urat = u - x;
-	vrat = v - y;
-	uopp = 1 - urat;
-		
-	return ((get_texcache_pixel(ss, x, y) * uopp +
-		 get_texcache_pixel(ss, x2, y) * urat) * (1 - vrat) + 
-		(get_texcache_pixel(ss, x, y2) * uopp +
-		 get_texcache_pixel(ss, x2, y2) * urat) * vrat) / 255.0;
-}
-
-/* Return a multiplier for brush strength on a particular vertex. */
-static float tex_strength(SculptSession *ss, Brush *br, float *point, const float len)
-{
-	MTex *tex = NULL;
-	float avg= 1;
-
-	if(br->texact >= 0)
-		tex = br->mtex[br->texact];
-
-	if(!tex) {
-		avg= 1;
-	}
-	else if(tex->brush_map_mode == MTEX_MAP_MODE_3D) {
-		float jnk;
+					VecMulf(val, fabs(fade));
 
-		/* Get strength by feeding the vertex 
-		   location directly into a texture */
-		externtex(tex, point, &avg,
-			  &jnk, &jnk, &jnk, &jnk);
-	}
-	else if(ss->texcache) {
-		const float bsize= ss->cache->pixel_radius * 2;
-		const float rot= tex->rot + ss->cache->rotation;
-		int px, py;
-		float flip[3], point_2d[2];
-
-		/* If the active area is being applied for symmetry, flip it
-		   across the symmetry axis in order to project it. This insures
-		   that the brush texture will be oriented correctly. */
-		VecCopyf(flip, point);
-		flip_coord(flip, flip, ss->cache->symmetry);
-		projectf(ss->cache->mats, flip, point_2d);
+				VecAddf(val, val, vd.co);
 
-		/* For Tile and Drag modes, get the 2D screen coordinates of the
-		   and scale them up or down to the texture size. */
-		if(tex->brush_map_mode == MTEX_MAP_MODE_TILED) {
-			const int sx= (const int)tex->size[0];
-			const int sy= (const int)tex->size[1];
-			
-			float fx= point_2d[0];
-			float fy= point_2d[1];
-			
-			float angle= atan2(fy, fx) - rot;
-			float flen= sqrtf(fx*fx + fy*fy);
-			
-			if(rot<0.001 && rot>-0.001) {
-				px= point_2d[0];
-				py= point_2d[1];
-			} else {
-				px= flen * cos(angle) + 2000;
-				py= flen * sin(angle) + 2000;
+				sculpt_clip(sd, ss, vd.co, val);
 			}
-			if(sx != 1)
-				px %= sx-1;
-			if(sy != 1)
-				py %= sy-1;
-			avg= get_texcache_pixel_bilinear(ss, ss->texcache_side*px/sx, ss->texcache_side*py/sy);
 		}
-		else if(tex->brush_map_mode == MTEX_MAP_MODE_FIXED) {
-			float fx= (point_2d[0] - ss->cache->mouse[0]) / bsize;
-			float fy= (point_2d[1] - ss->cache->mouse[1]) / bsize;
-
-			float angle= atan2(fy, fx) - rot;
-			float flen= sqrtf(fx*fx + fy*fy);
-			
-			fx = flen * cos(angle) + 0.5;
-			fy = flen * sin(angle) + 0.5;
 
-			avg= get_texcache_pixel_bilinear(ss, fx * ss->texcache_side, fy * ss->texcache_side);
-		}
+		BLI_pbvh_node_mark_update(nodes[n]);
 	}
-
-	avg*= brush_curve_strength(br, len, ss->cache->radius); /* Falloff curve */
-
-	return avg;
 }
 
-typedef struct {
-	SculptSession *ss;
-	float radius_squared;
-	ListBase *active_verts;
-} SculptSearchSphereData;
-
-/* Test AABB against sphere */
-static int sculpt_search_sphere_cb(float bb_min[3], float bb_max[3],
-				   void *data_v)
+static void sculpt_brush_hit_cb(PBVHNode *node, void *data_v)
 {
 	SculptSearchSphereData *data = data_v;
-	float *center = data->ss->cache->location, nearest[3];
-	float t[3];
-	int i;
-
-	for(i = 0; i < 3; ++i) {
-		if(bb_min[i] > center[i])
-			nearest[i] = bb_min[i];
-		else if(bb_max[i] < center[i])
-			nearest[i] = bb_max[i];
-		else
-			nearest[i] = center[i]; 
-	}
-	
-	VecSubf(t, center, nearest);
+	int i, totvert, *verts;
 
-	return t[0] * t[0] + t[1] * t[1] + t[2] * t[2] < data->radius_squared;
-}
+	BLI_pbvh_node_get_verts(node, &verts, &totvert);
 
-static void sculpt_brush_hit_cb(const int *face_indices,
-				const int *vert_indices,
-				int totface, int totvert, void *data_v)
-{
-	SculptSearchSphereData *data = data_v;
-	int i;
-
-	/* XXX: for now we still make an active vert list,
-	   can be fixed later */
+	/* XXX: for now grab brush still uses an active vert list,
+	   will be fixed later */
 
 	for(i = 0; i < totvert; ++i) {
-		int v = vert_indices[i];
+		int v = verts[i];
 		float delta[3], dsq;
 		
 		VecSubf(delta, data->ss->mvert[v].co,
@@ -828,65 +978,82 @@ static void sculpt_brush_hit_cb(const int *face_indices,
 			BLI_addtail(data->active_verts, adata);
 		}
 	}
+
+	BLI_pbvh_node_mark_update(node);
 }
 
 static void do_brush_action(Sculpt *sd, SculptSession *ss, StrokeCache *cache)
 {
 	Brush *brush = paint_brush(&sd->paint);
-	ListBase local_active_verts = {0, 0};
-	ListBase *grab_active_verts = &ss->cache->grab_active_verts[ss->cache->symmetry];
-	ListBase *active_verts = &local_active_verts;
-	const float bstrength= brush_strength(sd, cache);
 	//KeyBlock *keyblock= NULL; /*XXX: ob_get_keyblock(OBACT); */
-	ActiveData *adata;
-	
-	/* For grab brush, only find active vertices once */
-	if(brush->sculpt_tool == SCULPT_TOOL_GRAB)
-		active_verts = grab_active_verts;
+	PBVHNode **nodes= NULL;
+	int totnode;
+	SculptSearchSphereData data;
+
+	data.ss = ss;
+	data.sd = sd;
+	data.radius_squared = ss->cache->radius * ss->cache->radius;
 
 	/* Build a list of all vertices that are potentially within the brush's
 	   area of influence */
-	if(brush->sculpt_tool != SCULPT_TOOL_GRAB || cache->first_time) {
-		SculptSearchSphereData data;
-		data.ss = ss;
-		data.radius_squared = ss->cache->radius * ss->cache->radius;
-		data.active_verts = active_verts;
-		BLI_pbvh_search(ss->tree, sculpt_search_sphere_cb, &data,
-			    sculpt_brush_hit_cb, &data,
-			    PBVH_SEARCH_MARK_MODIFIED);
-
-		/* Update brush strength for each vertex */
-		for(adata = active_verts->first; adata; adata = adata->next)
-			adata->Fade = tex_strength(ss, brush, ss->mvert[adata->Index].co, adata->dist) * bstrength;
+	if(brush->sculpt_tool == SCULPT_TOOL_GRAB) {
+		if(cache->first_time) {
+			const float bstrength= brush_strength(sd, cache);
+			ListBase *grab_active_verts = &ss->cache->grab_active_verts[ss->cache->symmetry];
+			ActiveData *adata;
+
+			data.active_verts = grab_active_verts;
+			BLI_pbvh_search_callback(ss->tree, sculpt_search_sphere_cb, &data,
+					sculpt_brush_hit_cb, &data);
+
+			BLI_pbvh_search_gather(ss->tree, sculpt_search_sphere_cb, &data,
+				&nodes, &totnode);
+			
+			ss->cache->grab_active_nodes[ss->cache->symmetry]= nodes;
+			ss->cache->grab_active_totnode[ss->cache->symmetry]= totnode;
+
+			/* Update brush strength for each vertex */
+			for(adata = data.active_verts->first; adata; adata = adata->next)
+				adata->Fade = tex_strength(ss, brush, ss->mvert[adata->Index].co, adata->dist) * bstrength;
+		}
+		else {
+			nodes= ss->cache->grab_active_nodes[ss->cache->symmetry];
+			totnode= ss->cache->grab_active_totnode[ss->cache->symmetry];
+		}
+	}
+	else {
+		BLI_pbvh_search_gather(ss->tree, sculpt_search_sphere_cb, &data,
+			&nodes, &totnode);
 	}
 
 	/* Only act if some verts are inside the brush area */
-	if(active_verts->first) {
+	if(totnode) {
 		/* Apply one type of brush action */
 		switch(brush->sculpt_tool){
 		case SCULPT_TOOL_DRAW:
-			do_draw_brush(sd, ss, active_verts);
+			do_draw_brush(sd, ss, nodes, totnode);
 			break;
 		case SCULPT_TOOL_SMOOTH:
-			do_smooth_brush(sd, ss, active_verts);
+			do_smooth_brush(sd, ss, nodes, totnode);
 			break;
 		case SCULPT_TOOL_PINCH:
-			do_pinch_brush(sd, ss, active_verts);
+			do_pinch_brush(sd, ss, nodes, totnode);
 			break;
 		case SCULPT_TOOL_INFLATE:
-			do_inflate_brush(sd, ss, active_verts);
+			do_inflate_brush(sd, ss, nodes, totnode);
 			break;
 		case SCULPT_TOOL_GRAB:
-			do_grab_brush(sd, ss);
+			do_grab_brush(sd, ss, nodes, totnode);
 			break;
 		case SCULPT_TOOL_LAYER:
-			do_layer_brush(sd, ss, active_verts);
+			do_layer_brush(sd, ss, nodes, totnode);
 			break;
 		case SCULPT_TOOL_FLATTEN:
-			do_flatten_clay_brush(sd, ss, active_verts, 0);
+			do_flatten_clay_brush(sd, ss, nodes, totnode, 0);
 			break;
 		case SCULPT_TOOL_CLAY:
-			do_flatten_clay_brush(sd, ss, active_verts, 1);
+			do_flatten_clay_brush(sd, ss, nodes, totnode, 1);
+			break;
 		}
 	
 #if 0
@@ -912,9 +1079,10 @@ static void do_brush_action(Sculpt *sd, SculptSession *ss, StrokeCache *cache)
 				addlisttolist(&ss->modified_verts, &active_verts);
 		}
 #endif
-
-		BLI_freelistN(&local_active_verts);
-
+		
+		if(brush->sculpt_tool != SCULPT_TOOL_GRAB)
+			if(nodes)
+				MEM_freeN(nodes);
 	}	
 }
 
@@ -937,6 +1105,7 @@ static void do_symmetrical_brush_actions(Sculpt *sd, SculptSession *ss)
 	VecCopyf(cache->location, cache->true_location);
 	VecCopyf(cache->grab_delta_symmetry, cache->grab_delta);
 	cache->symmetry = 0;
+	cache->bstrength = brush_strength(sd, cache);
 	do_brush_action(sd, ss, cache);
 
 	for(i = 1; i <= symm; ++i) {
@@ -1133,8 +1302,11 @@ static void sculpt_cache_free(StrokeCache *cache)
 		MEM_freeN(cache->face_norms);
 	if(cache->mats)
 		MEM_freeN(cache->mats);
-	for(i = 0; i < 8; ++i) 
+	for(i = 0; i < 8; ++i) {
 		BLI_freelistN(&cache->grab_active_verts[i]);
+		if(cache->grab_active_nodes[i])
+			MEM_freeN(cache->grab_active_nodes[i]);
+	}
 	MEM_freeN(cache);
 }
 
@@ -1310,23 +1482,23 @@ typedef struct {
 	float dist;
 } SculptRaycastData;
 
-void sculpt_raycast_cb(const int *face_indices,
-		       const int *vert_indices,
-		       int totface, int totvert, void *data_v)
+void sculpt_raycast_cb(PBVHNode *node, void *data_v)
 {
 	SculptRaycastData *srd = data_v;
 	MVert *vert = srd->ss->mvert;
-	int i;
+	int i, totface, *faces;
+
+	BLI_pbvh_node_get_faces(node, &faces, &totface);
 
 	for(i = 0; i < totface; ++i) {
-		MFace *f = srd->ss->mface + face_indices[i];
+		MFace *f = srd->ss->mface + faces[i];
 		if(ray_face_intersection(srd->ray_start, srd->ray_normal,
 					 vert[f->v1].co,
 					 vert[f->v2].co,
 					 vert[f->v3].co,
 					 f->v4 ? vert[f->v4].co : NULL,
 					 &srd->dist)) {
-			srd->hit = face_indices[i];
+			srd->hit = faces[i];
 		}
 	}
 }
@@ -1352,7 +1524,7 @@ int sculpt_stroke_get_location(bContext *C, struct PaintStroke *stroke, float ou
 	srd.hit = -1;
 	BLI_pbvh_raycast(vc->obact->sculpt->tree, sculpt_raycast_cb, &srd,
 		     ray_start, ray_normal);
-
+	
 	VecCopyf(out, ray_normal);
 	VecMulf(out, srd.dist);
 	VecAddf(out, out, ray_start);
@@ -1459,17 +1631,9 @@ static void sculpt_flush_update(bContext *C)
 		multires_mark_as_modified(ob);
 	}
 
+	BLI_pbvh_update(ss->tree, PBVH_UpdateBB, NULL, NULL);
 	redraw = sculpt_get_redraw_rect(ar, CTX_wm_region_view3d(C), ob, &r);
 
-	if(!redraw) {
-		BLI_pbvh_search(ss->tree, BLI_pbvh_update_search_cb,
-				PBVH_NodeData, NULL, NULL,
-				PBVH_SEARCH_UPDATE);
-		
-		redraw = sculpt_get_redraw_rect(ar, CTX_wm_region_view3d(C),
-						ob, &r);
-	}
-
 	if(redraw) {
 		r.xmin += ar->winrct.xmin + 1;
 		r.xmax += ar->winrct.xmin - 1;
@@ -1493,9 +1657,6 @@ static int sculpt_stroke_test_start(bContext *C, struct wmOperator *op, wmEvent
 		Object *ob = CTX_data_active_object(C);
 		SculptSession *ss = ob->sculpt;
 
-		if(paint_brush(&CTX_data_tool_settings(C)->sculpt->paint)->sculpt_tool == SCULPT_TOOL_GRAB)
-			BLI_pbvh_toggle_modified_lock(ss->tree);
-		
 		ED_view3d_init_mats_rv3d(ob, CTX_wm_region_view3d(C));
 
 		sculpt_brush_stroke_init_properties(C, op, event, ss);
@@ -1527,9 +1688,6 @@ static void sculpt_stroke_done(bContext *C, struct PaintStroke *stroke)
 	if(ss->cache) {
 		Sculpt *sd = CTX_data_tool_settings(C)->sculpt;
 
-		if(paint_brush(&CTX_data_tool_settings(C)->sculpt->paint)->sculpt_tool == SCULPT_TOOL_GRAB)
-			BLI_pbvh_toggle_modified_lock(ss->tree);
-
 		sculpt_cache_free(ss->cache);
 		ss->cache = NULL;
 		sculpt_undo_push(C, sd);
@@ -1707,3 +1865,4 @@ void ED_operatortypes_sculpt()
 	WM_operatortype_append(SCULPT_OT_sculptmode_toggle);
 	WM_operatortype_append(SCULPT_OT_set_persistent_base);
 }
+