diff options
Diffstat (limited to 'source/blender/blenlib/intern/pbvh.c')
-rw-r--r-- | source/blender/blenlib/intern/pbvh.c | 468 |
1 files changed, 383 insertions, 85 deletions
diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c index 9e1dd096528..4c5177a403e 100644 --- a/source/blender/blenlib/intern/pbvh.c +++ b/source/blender/blenlib/intern/pbvh.c @@ -20,11 +20,7 @@ * ***** END GPL LICENSE BLOCK ***** */ -#include <float.h> -#include <stdlib.h> -#include <string.h> -#include "MEM_guardedalloc.h" #include "DNA_meshdata_types.h" @@ -33,10 +29,10 @@ #include "BLI_pbvh.h" #include "BKE_DerivedMesh.h" -#include "BKE_mesh.h" -#include "BKE_utildefines.h" +#include "BKE_mesh.h" /* for mesh_calc_normals */ +#include "BKE_global.h" /* for mesh_calc_normals */ -#include "gpu_buffers.h" +#include "GPU_buffers.h" #define LEAF_LIMIT 10000 @@ -96,6 +92,11 @@ struct PBVHNode { unsigned int uniq_verts, face_verts; char flag; + + float tmin; // used for raycasting, is how close bb is to the ray point + + int proxy_count; + PBVHProxyNode* proxies; }; struct PBVH { @@ -126,6 +127,9 @@ struct PBVH { #ifdef PERFCNTRS int perf_modified; #endif + + /* flag are verts/faces deformed */ + int deformed; }; #define STACK_FIXED_DEPTH 100 @@ -228,10 +232,21 @@ static void update_node_vb(PBVH *bvh, PBVHNode *node) node->vb= vb; } +//void BLI_pbvh_node_BB_reset(PBVHNode* node) +//{ +// BB_reset(&node->vb); +//} +// +//void BLI_pbvh_node_BB_expand(PBVHNode* node, float co[3]) +//{ +// BB_expand(&node->vb, co); +//} + + /* Adapted from BLI_kdopbvh.c */ /* Returns the index of the first element on the right of the partition */ static int partition_indices(int *prim_indices, int lo, int hi, int axis, - float mid, BBC *prim_bbc) + float mid, BBC *prim_bbc) { int i=lo, j=hi; for(;;) { @@ -247,7 +262,7 @@ static int partition_indices(int *prim_indices, int lo, int hi, int axis, } void check_partitioning(int *prim_indices, int lo, int hi, int axis, - float mid, BBC *prim_bbc, int index_of_2nd_partition) + float mid, BBC *prim_bbc, int index_of_2nd_partition) { int i; for(i = lo; i <= hi; ++i) { @@ -279,8 +294,8 @@ static void grow_nodes(PBVH *bvh, int totnode) /* Add a vertex to the map, with a positive value for unique vertices and a negative value for additional vertices */ static int map_insert_vert(PBVH *bvh, GHash *map, - unsigned int *face_verts, - unsigned int *uniq_verts, int vertex) + unsigned int *face_verts, + unsigned int *uniq_verts, int vertex) { void *value, *key = SET_INT_IN_POINTER(vertex); @@ -309,7 +324,7 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) GHash *map; int i, j, totface; - map = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp); + map = BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp, "build_mesh_leaf_node gh"); node->uniq_verts = node->face_verts = 0; totface= node->totprim; @@ -334,8 +349,8 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) /* Build the vertex list, unique verts first */ for(iter = BLI_ghashIterator_new(map), i = 0; - !BLI_ghashIterator_isDone(iter); - BLI_ghashIterator_step(iter), ++i) { + !BLI_ghashIterator_isDone(iter); + BLI_ghashIterator_step(iter), ++i) { void *value = BLI_ghashIterator_getValue(iter); int ndx = GET_INT_FROM_POINTER(value); @@ -352,21 +367,28 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) if(node->face_vert_indices[i] < 0) node->face_vert_indices[i]= -node->face_vert_indices[i] + node->uniq_verts - 1; - node->draw_buffers = - GPU_build_mesh_buffers(map, bvh->verts, bvh->faces, - node->prim_indices, - node->totprim, node->vert_indices, - node->uniq_verts, - node->uniq_verts + node->face_verts); + if(!G.background) { + node->draw_buffers = + GPU_build_mesh_buffers(map, bvh->verts, bvh->faces, + node->prim_indices, + node->totprim, node->vert_indices, + node->uniq_verts, + node->uniq_verts + node->face_verts); + } + + node->flag |= PBVH_UpdateDrawBuffers; BLI_ghash_free(map, NULL, NULL); } static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node) { - node->draw_buffers = - GPU_build_grid_buffers(bvh->grids, node->prim_indices, + if(!G.background) { + node->draw_buffers = + GPU_build_grid_buffers(bvh->grids, node->prim_indices, node->totprim, bvh->gridsize); + } + node->flag |= PBVH_UpdateDrawBuffers; } /* Recursively build a node in the tree @@ -381,7 +403,7 @@ static void build_grids_leaf_node(PBVH *bvh, PBVHNode *node) */ void build_sub(PBVH *bvh, int node_index, BB *cb, BBC *prim_bbc, - int offset, int count) + int offset, int count) { int i, axis, end; BB cb_backing; @@ -578,6 +600,15 @@ void BLI_pbvh_free(PBVH *bvh) } } + if (bvh->deformed) { + if (bvh->verts) { + /* if pbvh was deformed, new memory was allocated for verts/faces -- free it */ + + MEM_freeN(bvh->verts); + MEM_freeN(bvh->faces); + } + } + MEM_freeN(bvh->nodes); MEM_freeN(bvh->prim_indices); MEM_freeN(bvh); @@ -626,13 +657,12 @@ static PBVHNode *pbvh_iter_next(PBVHIter *iter) { 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 */ + /* pop node */ iter->stacksize--; node= iter->stack[iter->stacksize].node; @@ -647,10 +677,7 @@ static PBVHNode *pbvh_iter_next(PBVHIter *iter) if(revisiting) return node; - /* check search callback */ - search_data= iter->search_data; - - if(iter->scb && !iter->scb(node, search_data)) + if(iter->scb && !iter->scb(node, iter->search_data)) continue; /* don't traverse, outside of search zone */ if(node->flag & PBVH_Leaf) { @@ -670,6 +697,34 @@ static PBVHNode *pbvh_iter_next(PBVHIter *iter) return NULL; } +static PBVHNode *pbvh_iter_next_occluded(PBVHIter *iter) +{ + PBVHNode *node; + + while(iter->stacksize) { + /* pop node */ + iter->stacksize--; + node= iter->stack[iter->stacksize].node; + + /* on a mesh with no faces this can happen + * can remove this check if we know meshes have at least 1 face */ + if(node==NULL) return NULL; + + if(iter->scb && !iter->scb(node, iter->search_data)) continue; /* don't traverse, outside of search zone */ + + if(node->flag & PBVH_Leaf) { + /* immediately hit leaf node */ + return node; + } + else { + 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) @@ -721,12 +776,105 @@ void BLI_pbvh_search_callback(PBVH *bvh, pbvh_iter_begin(&iter, bvh, scb, search_data); while((node=pbvh_iter_next(&iter))) - if(node->flag & PBVH_Leaf) + if (node->flag & PBVH_Leaf) hcb(node, hit_data); pbvh_iter_end(&iter); } +typedef struct node_tree { + PBVHNode* data; + + struct node_tree* left; + struct node_tree* right; +} node_tree; + +static void node_tree_insert(node_tree* tree, node_tree* new_node) +{ + if (new_node->data->tmin < tree->data->tmin) { + if (tree->left) { + node_tree_insert(tree->left, new_node); + } + else { + tree->left = new_node; + } + } + else { + if (tree->right) { + node_tree_insert(tree->right, new_node); + } + else { + tree->right = new_node; + } + } +} + +static void traverse_tree(node_tree* tree, BLI_pbvh_HitOccludedCallback hcb, void* hit_data, float* tmin) +{ + if (tree->left) traverse_tree(tree->left, hcb, hit_data, tmin); + + hcb(tree->data, hit_data, tmin); + + if (tree->right) traverse_tree(tree->right, hcb, hit_data, tmin); +} + +static void free_tree(node_tree* tree) +{ + if (tree->left) { + free_tree(tree->left); + tree->left = 0; + } + + if (tree->right) { + free_tree(tree->right); + tree->right = 0; + } + + free(tree); +} + +float BLI_pbvh_node_get_tmin(PBVHNode* node) +{ + return node->tmin; +} + +void BLI_pbvh_search_callback_occluded(PBVH *bvh, + BLI_pbvh_SearchCallback scb, void *search_data, + BLI_pbvh_HitOccludedCallback hcb, void *hit_data) +{ + PBVHIter iter; + PBVHNode *node; + node_tree *tree = 0; + + pbvh_iter_begin(&iter, bvh, scb, search_data); + + while((node=pbvh_iter_next_occluded(&iter))) { + if(node->flag & PBVH_Leaf) { + node_tree* new_node = malloc(sizeof(node_tree)); + + new_node->data = node; + + new_node->left = NULL; + new_node->right = NULL; + + if (tree) { + node_tree_insert(tree, new_node); + } + else { + tree = new_node; + } + } + } + + pbvh_iter_end(&iter); + + if (tree) { + float tmin = FLT_MAX; + traverse_tree(tree, hcb, hit_data, &tmin); + free_tree(tree); + } +} + static int update_search_cb(PBVHNode *node, void *data_v) { int flag= GET_INT_FROM_POINTER(data_v); @@ -752,11 +900,11 @@ static void pbvh_update_normals(PBVH *bvh, PBVHNode **nodes, /* subtle assumptions: - We know that for all edited vertices, the nodes with faces - adjacent to these vertices have been marked with PBVH_UpdateNormals. + adjacent to these vertices have been marked with PBVH_UpdateNormals. This is true because if the vertex is inside the brush radius, the bounding box of it's adjacent faces will be as well. - However this is only true for the vertices that have actually been - edited, not for all vertices in the nodes marked for update, so we + edited, not for all vertices in the nodes marked for update, so we can only update vertices marked with ME_VERT_PBVH_UPDATE. */ @@ -861,7 +1009,7 @@ static void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, } } -static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) +static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode, int smooth) { PBVHNode *node; int n; @@ -876,7 +1024,8 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) bvh->grids, node->prim_indices, node->totprim, - bvh->gridsize); + bvh->gridsize, + smooth); } else { GPU_update_mesh_buffers(node->draw_buffers, @@ -936,9 +1085,6 @@ void BLI_pbvh_update(PBVH *bvh, int flag, float (*face_nors)[3]) if(flag & (PBVH_UpdateBB|PBVH_UpdateOriginalBB|PBVH_UpdateRedraw)) pbvh_update_BB_redraw(bvh, nodes, totnode, flag); - if(flag & PBVH_UpdateDrawBuffers) - pbvh_update_draw_buffers(bvh, nodes, totnode); - if(flag & (PBVH_UpdateBB|PBVH_UpdateOriginalBB)) pbvh_flush_bb(bvh, bvh->nodes, flag); @@ -972,9 +1118,10 @@ void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *tot GHashIterator *hiter; GHash *map; void *face, **faces; - int i, tot; + unsigned i; + int tot; - map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); + map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "pbvh_get_grid_updates gh"); pbvh_iter_begin(&iter, bvh, NULL, NULL); @@ -1004,8 +1151,8 @@ void BLI_pbvh_get_grid_updates(PBVH *bvh, int clear, void ***gridfaces, int *tot faces= MEM_callocN(sizeof(void*)*tot, "PBVH Grid Faces"); for(hiter = BLI_ghashIterator_new(map), i = 0; - !BLI_ghashIterator_isDone(hiter); - BLI_ghashIterator_step(hiter), ++i) + !BLI_ghashIterator_isDone(hiter); + BLI_ghashIterator_step(hiter), ++i) faces[i]= BLI_ghashIterator_getKey(hiter); BLI_ghashIterator_free(hiter); @@ -1073,6 +1220,18 @@ void BLI_pbvh_node_get_original_BB(PBVHNode *node, float bb_min[3], float bb_max copy_v3_v3(bb_max, node->orig_vb.bmax); } +void BLI_pbvh_node_get_proxies(PBVHNode* node, PBVHProxyNode** proxies, int* proxy_count) +{ + if (node->proxy_count > 0) { + if (proxies) *proxies = node->proxies; + if (proxy_count) *proxy_count = node->proxy_count; + } + else { + if (proxies) *proxies = 0; + if (proxy_count) *proxy_count = 0; + } +} + /********************************* Raycast ***********************************/ typedef struct { @@ -1087,16 +1246,13 @@ typedef struct { static int ray_aabb_intersect(PBVHNode *node, void *data_v) { RaycastData *ray = data_v; - float bb_min[3], bb_max[3], bbox[2][3]; + float bbox[2][3]; float tmin, tmax, tymin, tymax, tzmin, tzmax; if(ray->original) - BLI_pbvh_node_get_original_BB(node, bb_min, bb_max); + BLI_pbvh_node_get_original_BB(node, bbox[0], bbox[1]); else - BLI_pbvh_node_get_BB(node, bb_min, bb_max); - - copy_v3_v3(bbox[0], bb_min); - copy_v3_v3(bbox[1], bb_max); + BLI_pbvh_node_get_BB(node, bbox[0], bbox[1]); tmin = (bbox[ray->sign[0]][0] - ray->start[0]) * ray->inv_dir[0]; tmax = (bbox[1-ray->sign[0]][0] - ray->start[0]) * ray->inv_dir[0]; @@ -1106,8 +1262,10 @@ static int ray_aabb_intersect(PBVHNode *node, void *data_v) if((tmin > tymax) || (tymin > tmax)) return 0; + if(tymin > tmin) tmin = tymin; + if(tymax < tmax) tmax = tymax; @@ -1116,21 +1274,21 @@ static int ray_aabb_intersect(PBVHNode *node, void *data_v) if((tmin > tzmax) || (tzmin > tmax)) return 0; - - return 1; - /* XXX: Not sure about this? - if(tzmin > tmin) - tmin = tzmin; - if(tzmax < tmax) - tmax = tzmax; - return ((tmin < t1) && (tmax > t0)); - */ + if(tzmin > tmin) + tmin = tzmin; + + // XXX jwilkins: tmax does not need to be updated since we don't use it + // keeping this here for future reference + //if(tzmax < tmax) tmax = tzmax; + node->tmin = tmin; + + return 1; } -void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data, - float ray_start[3], float ray_normal[3], int original) +void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitOccludedCallback cb, void *data, + float ray_start[3], float ray_normal[3], int original) { RaycastData rcd; @@ -1143,37 +1301,24 @@ void BLI_pbvh_raycast(PBVH *bvh, BLI_pbvh_HitCallback cb, void *data, rcd.sign[2] = rcd.inv_dir[2] < 0; rcd.original = original; - BLI_pbvh_search_callback(bvh, ray_aabb_intersect, &rcd, cb, data); + BLI_pbvh_search_callback_occluded(bvh, ray_aabb_intersect, &rcd, cb, data); } -/* XXX: Code largely copied from bvhutils.c, could be unified */ -/* Returns 1 if a better intersection has been found */ static int ray_face_intersection(float ray_start[3], float ray_normal[3], float *t0, float *t1, float *t2, float *t3, float *fdist) { - int hit = 0; - - do - { - float dist = FLT_MAX; - - if(!isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, - &dist, NULL, 0.1f)) - dist = FLT_MAX; - - if(dist >= 0 && dist < *fdist) { - hit = 1; - *fdist = dist; - } - - t1 = t2; - t2 = t3; - t3 = NULL; - - } while(t2); - - return hit; + float dist; + + if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist, NULL, 0.1f) && dist < *fdist) || + (t3 && isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &dist, NULL, 0.1f) && dist < *fdist)) + { + *fdist = dist; + return 1; + } + else { + return 0; + } } int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], @@ -1218,6 +1363,8 @@ int BLI_pbvh_node_raycast(PBVH *bvh, PBVHNode *node, float (*origco)[3], for(i = 0; i < totgrid; ++i) { DMGridData *grid= bvh->grids[node->prim_indices[i]]; + if (!grid) + continue; for(y = 0; y < gridsize-1; ++y) { for(x = 0; x < gridsize-1; ++x) { @@ -1304,9 +1451,18 @@ int BLI_pbvh_node_planes_contain_AABB(PBVHNode *node, void *data) return 1; } -void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3]) +void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3], int smooth) { - BLI_pbvh_update(bvh, PBVH_UpdateNormals|PBVH_UpdateDrawBuffers, face_nors); + PBVHNode **nodes; + int totnode; + + BLI_pbvh_search_gather(bvh, update_search_cb, SET_INT_IN_POINTER(PBVH_UpdateNormals|PBVH_UpdateDrawBuffers), + &nodes, &totnode); + + pbvh_update_normals(bvh, nodes, totnode, face_nors); + pbvh_update_draw_buffers(bvh, nodes, totnode, smooth); + + if(nodes) MEM_freeN(nodes); if(planes) { BLI_pbvh_search_callback(bvh, BLI_pbvh_node_planes_contain_AABB, @@ -1317,3 +1473,145 @@ void BLI_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*face_nors)[3]) } } +void BLI_pbvh_grids_update(PBVH *bvh, DMGridData **grids, DMGridAdjacency *gridadj, void **gridfaces) +{ + bvh->grids= grids; + bvh->gridadj= gridadj; + bvh->gridfaces= gridfaces; +} + +float (*BLI_pbvh_get_vertCos(PBVH *pbvh))[3] +{ + int a; + float (*vertCos)[3]= NULL; + + if (pbvh->verts) { + float *co; + MVert *mvert= pbvh->verts; + + vertCos= MEM_callocN(3*pbvh->totvert*sizeof(float), "BLI_pbvh_get_vertCoords"); + co= (float*)vertCos; + + for (a= 0; a<pbvh->totvert; a++, mvert++, co+= 3) { + copy_v3_v3(co, mvert->co); + } + } + + return vertCos; +} + +void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) +{ + int a; + + if (!pbvh->deformed) { + if (pbvh->verts) { + /* if pbvh is not already deformed, verts/faces points to the */ + /* original data and applying new coords to this arrays would lead to */ + /* unneeded deformation -- duplicate verts/faces to avoid this */ + + pbvh->verts= MEM_dupallocN(pbvh->verts); + pbvh->faces= MEM_dupallocN(pbvh->faces); + + pbvh->deformed= 1; + } + } + + if (pbvh->verts) { + /* copy new verts coords */ + for (a= 0; a < pbvh->totvert; ++a) { + copy_v3_v3(pbvh->verts[a].co, vertCos[a]); + } + + /* coordinates are new -- normals should also be updated */ + mesh_calc_normals(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); + } +} + +int BLI_pbvh_isDeformed(PBVH *pbvh) +{ + return pbvh->deformed; +} +/* Proxies */ + +PBVHProxyNode* BLI_pbvh_node_add_proxy(PBVH* bvh, PBVHNode* node) +{ + int index, totverts; + + #pragma omp critical + { + + index = node->proxy_count; + + node->proxy_count++; + + if (node->proxies) + node->proxies= MEM_reallocN(node->proxies, node->proxy_count*sizeof(PBVHProxyNode)); + else + node->proxies= MEM_mallocN(sizeof(PBVHProxyNode), "PBVHNodeProxy"); + + if (bvh->grids) + totverts = node->totprim*bvh->gridsize*bvh->gridsize; + else + totverts = node->uniq_verts; + + node->proxies[index].co= MEM_callocN(sizeof(float[3])*totverts, "PBVHNodeProxy.co"); + } + + return node->proxies + index; +} + +void BLI_pbvh_node_free_proxies(PBVHNode* node) +{ + #pragma omp critical + { + int p; + + for (p= 0; p < node->proxy_count; p++) { + MEM_freeN(node->proxies[p].co); + node->proxies[p].co= 0; + } + + MEM_freeN(node->proxies); + node->proxies = 0; + + node->proxy_count= 0; + } +} + +void BLI_pbvh_gather_proxies(PBVH* pbvh, PBVHNode*** r_array, int* r_tot) +{ + PBVHNode **array= NULL, **newarray, *node; + int tot= 0, space= 0; + int n; + + for (n= 0; n < pbvh->totnode; n++) { + node = pbvh->nodes + n; + + if(node->proxy_count > 0) { + if(tot == space) { + /* resize array if needed */ + space= (tot == 0)? 32: space*2; + newarray= MEM_callocN(sizeof(PBVHNode)*space, "BLI_pbvh_gather_proxies"); + + if (array) { + memcpy(newarray, array, sizeof(PBVHNode)*tot); + MEM_freeN(array); + } + + array= newarray; + } + + array[tot]= node; + tot++; + } + } + + if(tot == 0 && array) { + MEM_freeN(array); + array= NULL; + } + + *r_array= array; + *r_tot= tot; +} |