[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [24129] branches/sculpt25/source/blender/ blenlib: Added the PBVH files, forgot these in the last commit
Nicholas Bishop
nicholasbishop at gmail.com
Wed Oct 28 00:43:21 CET 2009
Revision: 24129
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=24129
Author: nicholasbishop
Date: 2009-10-28 00:43:20 +0100 (Wed, 28 Oct 2009)
Log Message:
-----------
Added the PBVH files, forgot these in the last commit
Added Paths:
-----------
branches/sculpt25/source/blender/blenlib/BLI_pbvh.h
branches/sculpt25/source/blender/blenlib/intern/pbvh.c
Added: branches/sculpt25/source/blender/blenlib/BLI_pbvh.h
===================================================================
--- branches/sculpt25/source/blender/blenlib/BLI_pbvh.h (rev 0)
+++ branches/sculpt25/source/blender/blenlib/BLI_pbvh.h 2009-10-27 23:43:20 UTC (rev 24129)
@@ -0,0 +1,62 @@
+struct MFace;
+struct MVert;
+struct PBVH;
+
+/* 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 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);
+
+typedef enum {
+ PBVH_SEARCH_NORMAL,
+
+ /* 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,
+
+
+ PBVH_SEARCH_UPDATE
+} PBVH_SearchMode;
+
+/* 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(struct PBVH *bvh, BLI_pbvh_SearchCallback scb,
+ void *search_data, BLI_pbvh_HitCallback hcb,
+ void *hit_data, PBVH_SearchMode mode);
+
+/* 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,
+ float ray_start[3], float ray_normal[3]);
+
+
+int BLI_pbvh_update_search_cb(float bb_min[3], float bb_max[3], void *data_v);
+
+/* 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);
+
+/* 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);
+
+
+
+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_set_source(struct PBVH *bvh, struct MVert *, struct MFace *mface);
Added: branches/sculpt25/source/blender/blenlib/intern/pbvh.c
===================================================================
--- branches/sculpt25/source/blender/blenlib/intern/pbvh.c (rev 0)
+++ branches/sculpt25/source/blender/blenlib/intern/pbvh.c 2009-10-27 23:43:20 UTC (rev 24129)
@@ -0,0 +1,665 @@
+#include "MEM_guardedalloc.h"
+
+#include "DNA_meshdata_types.h"
+
+#include "BLI_arithb.h"
+#include "BLI_ghash.h"
+#include "BLI_pbvh.h"
+
+#include "BKE_utildefines.h"
+
+#include "gpu_buffers.h"
+
+#include <float.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define LEAF_LIMIT 10000
+
+//#define PERFCNTRS
+
+/* Bitmap */
+typedef char* BLI_bitmap;
+
+BLI_bitmap BLI_bitmap_new(int tot)
+{
+ return MEM_callocN((tot >> 3) + 1, "BLI bitmap");
+}
+
+int BLI_bitmap_get(BLI_bitmap b, int index)
+{
+ return b[index >> 3] & (1 << (index & 7));
+}
+
+void BLI_bitmap_set(BLI_bitmap b, int index)
+{
+ b[index >> 3] |= (1 << (index & 7));
+}
+
+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];
+} BB;
+
+/* Axis-aligned bounding box with centroid */
+typedef struct {
+ float bmin[3], bmax[3], bcentroid[3];
+} BBC;
+
+typedef struct {
+ /* Opaque handle for drawing code */
+ void *draw_buffers;
+
+ int *vert_indices;
+
+ /* Voxel bounds */
+ BB vb;
+
+ /* For internal nodes */
+ int children_offset;
+
+ /* Range of faces used in the node */
+ int face_offset;
+
+ unsigned short totface;
+ unsigned short uniq_verts, face_verts;
+
+ char flag;
+} Node;
+
+typedef struct PBVH {
+ Node *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;
+
+#ifdef PERFCNTRS
+ int perf_modified;
+#endif
+} PBVH;
+
+static void BB_reset(BB *bb)
+{
+ bb->bmin[0] = bb->bmin[1] = bb->bmin[2] = FLT_MAX;
+ bb->bmax[0] = bb->bmax[1] = bb->bmax[2] = -FLT_MAX;
+}
+
+/* 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];
+}
+
+/* Expand the bounding box to include another bounding box */
+static void BB_expand_with_bb(BB *bb, BB *bb2)
+{
+ int i;
+ for(i = 0; i < 3; ++i) {
+ bb->bmin[i] = MIN2(bb->bmin[i], bb2->bmin[i]);
+ bb->bmax[i] = MAX2(bb->bmax[i], bb2->bmax[i]);
+ }
+}
+
+/* Return 0, 1, or 2 to indicate the widest axis of the bounding box */
+static int BB_widest_axis(BB *bb)
+{
+ float dim[3];
+ int i;
+
+ for(i = 0; i < 3; ++i)
+ dim[i] = bb->bmax[i] - bb->bmin[i];
+
+ if(dim[0] > dim[1]) {
+ if(dim[0] > dim[2])
+ return 0;
+ else
+ return 2;
+ }
+ else {
+ if(dim[1] > dim[2])
+ return 1;
+ else
+ return 2;
+ }
+}
+
+static void BBC_update_centroid(BBC *bbc)
+{
+ int i;
+ for(i = 0; i < 3; ++i)
+ bbc->bcentroid[i] = (bbc->bmin[i] + bbc->bmax[i]) * 0.5f;
+}
+
+/* Not recursive */
+static void update_node_vb(PBVH *bvh, Node *node)
+{
+ BB_reset(&node->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);
+ }
+ }
+ else {
+ BB_expand_with_bb(&node->vb,
+ &bvh->nodes[node->children_offset].vb);
+ BB_expand_with_bb(&node->vb,
+ &bvh->nodes[node->children_offset + 1].vb);
+ }
+}
+
+/* Adapted from BLI_kdopbvh.c */
+/* Returns the index of the first element on the right of the partition */
+static int partition_indices(int *face_indices, int lo, int hi, int axis,
+ float mid, BBC *prim_bbc)
+{
+ int i=lo, j=hi;
+ for(;;) {
+ for(; prim_bbc[face_indices[i]].bcentroid[axis] < mid; i++);
+ for(; mid < prim_bbc[face_indices[j]].bcentroid[axis]; j--);
+
+ if(!(i < j))
+ return i;
+
+ SWAP(int, face_indices[i], face_indices[j]);
+ i++;
+ }
+}
+
+void check_partitioning(int *face_indices, int lo, int hi, int axis,
+ float mid, BBC *prim_bbc, int index_of_2nd_partition)
+{
+ int i;
+ for(i = lo; i <= hi; ++i) {
+ const float c = prim_bbc[face_indices[i]].bcentroid[axis];
+
+ if((i < index_of_2nd_partition && c > mid) ||
+ (i > index_of_2nd_partition && c < mid)) {
+ printf("fail\n");
+ }
+ }
+}
+
+static void grow_nodes(PBVH *bvh, int totnode)
+{
+ if(totnode > bvh->node_mem_count) {
+ Node *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");
+ memcpy(bvh->nodes, prev, bvh->totnode * sizeof(Node));
+ MEM_freeN(prev);
+ }
+
+ bvh->totnode = totnode;
+}
+
+/* Add a vertex to the map, with a positive value for unique vertices and
+ a negative value for additional vertices */
+static void map_insert_vert(PBVH *bvh, GHash *map,
+ unsigned short *face_verts,
+ unsigned short *uniq_verts, int vertex)
+{
+ void *value, *key = SET_INT_IN_POINTER(vertex);
+
+ if(!BLI_ghash_haskey(map, key)) {
+ if(BLI_bitmap_get(bvh->vert_bitmap, vertex)) {
+ value = SET_INT_IN_POINTER(-(*face_verts) - 1);
+ ++(*face_verts);
+ }
+ else {
+ BLI_bitmap_set(bvh->vert_bitmap, vertex);
+ value = SET_INT_IN_POINTER(*uniq_verts);
+ ++(*uniq_verts);
+ }
+
+ BLI_ghash_insert(map, key, value);
+ }
+}
+
+/* Find vertices used by the faces in this node and update the draw buffers */
+static void build_leaf_node(PBVH *bvh, Node *node)
+{
+ GHashIterator *iter;
+ GHash *map;
+ int i, j;
+
+ map = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
+
+ node->uniq_verts = node->face_verts = 0;
+
+ for(i = node->face_offset + node->totface - 1;
+ i >= node->face_offset; --i) {
+ MFace *f = bvh->faces + bvh->face_indices[i];
+ int sides = f->v4 ? 4 : 3;
+
+ for(j = 0; j < sides; ++j) {
+ map_insert_vert(bvh, map, &node->face_verts,
+ &node->uniq_verts, (&f->v1)[j]);
+ }
+ }
+
+ node->vert_indices = MEM_callocN(sizeof(int) *
+ (node->uniq_verts + node->face_verts),
+ "bvh node vert indices");
+
+ /* Build the vertex list, unique verts first */
+ for(iter = BLI_ghashIterator_new(map), i = 0;
+ !BLI_ghashIterator_isDone(iter);
+ BLI_ghashIterator_step(iter), ++i) {
+ void *value = BLI_ghashIterator_getValue(iter);
+ int ndx = GET_INT_FROM_POINTER(value);
+
+ if(ndx < 0)
+ ndx = -ndx + node->uniq_verts - 1;
+
+ node->vert_indices[ndx] =
+ GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(iter));
+ }
+
+ node->draw_buffers =
+ GPU_build_buffers(map, bvh->verts, bvh->faces,
+ bvh->face_indices + node->face_offset,
+ node->totface, node->vert_indices,
+ node->uniq_verts,
+ node->uniq_verts + node->face_verts);
+
+ BLI_ghash_free(map, NULL, NULL);
+}
+
+/* Recursively build a node in the tree
+
+ vb is the voxel box around all of the primitives contained in
+ this node.
+
+ cb is the bounding box around all the centroids of the primitives
+ contained in this node
+
+ offset and start indicate a range in the array of primitive indices
+*/
+
+void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc,
+ int offset, int count)
+{
+ int i, axis, end;
+ BB cb_backing;
+
+ /* Decide whether this is a leaf or not */
+ if(count <= LEAF_LIMIT) {
+ bvh->nodes[node_index].flag |= PBVH_Leaf;
+
+ bvh->nodes[node_index].face_offset = offset;
+ bvh->nodes[node_index].totface = count;
+
+ /* Still need vb for searches */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list