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.

1 files changed, 76 insertions, 40 deletions

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);