diff options
Diffstat (limited to 'source/blender/blenkernel/intern/pbvh.c')
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh.c | 364 |
1 files changed, 310 insertions, 54 deletions
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index 4fe4d6e75a6..aa8ab07518f 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -34,6 +34,7 @@ #include "BKE_pbvh.h" #include "BKE_ccg.h" +#include "BKE_subsurf.h" #include "BKE_DerivedMesh.h" #include "BKE_global.h" #include "BKE_mesh.h" /* for BKE_mesh_calc_normals */ @@ -606,6 +607,11 @@ void BKE_pbvh_build_grids(PBVH *bvh, CCGElem **grids, MEM_freeN(prim_bbc); } +void BKE_pbvh_set_ccgdm(PBVH *bvh, CCGDerivedMesh *ccgdm) +{ + bvh->ccgdm = ccgdm; +} + PBVH *BKE_pbvh_new(void) { PBVH *bvh = MEM_callocN(sizeof(PBVH), "pbvh"); @@ -620,7 +626,7 @@ void BKE_pbvh_free(PBVH *bvh) if (node->flag & PBVH_Leaf) { if (node->draw_buffers) - GPU_free_pbvh_buffers(node->draw_buffers); + GPU_pbvh_buffers_free(node->draw_buffers); if (node->vert_indices) MEM_freeN((void *)node->vert_indices); if (node->face_vert_indices) @@ -635,7 +641,7 @@ void BKE_pbvh_free(PBVH *bvh) BLI_gset_free(node->bm_other_verts, NULL); } } - GPU_free_pbvh_buffer_multires(&bvh->grid_common_gpu_buffer); + GPU_pbvh_multires_buffers_free(&bvh->grid_common_gpu_buffer); if (bvh->deformed) { if (bvh->verts) { @@ -1090,11 +1096,11 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) PBVHNode *node = nodes[n]; if (node->flag & PBVH_RebuildDrawBuffers) { - GPU_free_pbvh_buffers(node->draw_buffers); + GPU_pbvh_buffers_free(node->draw_buffers); switch (bvh->type) { case PBVH_GRIDS: node->draw_buffers = - GPU_build_grid_pbvh_buffers(node->prim_indices, + GPU_pbvh_grid_buffers_build(node->prim_indices, node->totprim, bvh->grid_hidden, bvh->gridkey.grid_size, @@ -1102,7 +1108,7 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) break; case PBVH_FACES: node->draw_buffers = - GPU_build_mesh_pbvh_buffers(node->face_vert_indices, + GPU_pbvh_mesh_buffers_build(node->face_vert_indices, bvh->mpoly, bvh->mloop, bvh->looptri, bvh->verts, node->prim_indices, @@ -1110,42 +1116,44 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) break; case PBVH_BMESH: node->draw_buffers = - GPU_build_bmesh_pbvh_buffers(bvh->flags & PBVH_DYNTOPO_SMOOTH_SHADING); + GPU_pbvh_bmesh_buffers_build(bvh->flags & PBVH_DYNTOPO_SMOOTH_SHADING); break; } - + node->flag &= ~PBVH_RebuildDrawBuffers; } if (node->flag & PBVH_UpdateDrawBuffers) { switch (bvh->type) { case PBVH_GRIDS: - GPU_update_grid_pbvh_buffers(node->draw_buffers, - bvh->grids, - bvh->grid_flag_mats, - node->prim_indices, - node->totprim, - &bvh->gridkey, - bvh->show_diffuse_color); + GPU_pbvh_grid_buffers_update( + node->draw_buffers, + bvh->grids, + bvh->grid_flag_mats, + node->prim_indices, + node->totprim, + &bvh->gridkey, + bvh->show_diffuse_color); break; case PBVH_FACES: - GPU_update_mesh_pbvh_buffers(node->draw_buffers, - bvh->verts, - node->vert_indices, - node->uniq_verts + - node->face_verts, - CustomData_get_layer(bvh->vdata, - CD_PAINT_MASK), - node->face_vert_indices, - bvh->show_diffuse_color); + GPU_pbvh_mesh_buffers_update( + node->draw_buffers, + bvh->verts, + node->vert_indices, + node->uniq_verts + + node->face_verts, + CustomData_get_layer(bvh->vdata, CD_PAINT_MASK), + node->face_vert_indices, + bvh->show_diffuse_color); break; case PBVH_BMESH: - GPU_update_bmesh_pbvh_buffers(node->draw_buffers, - bvh->bm, - node->bm_faces, - node->bm_unique_verts, - node->bm_other_verts, - bvh->show_diffuse_color); + GPU_pbvh_bmesh_buffers_update( + node->draw_buffers, + bvh->bm, + node->bm_faces, + node->bm_unique_verts, + node->bm_other_verts, + bvh->show_diffuse_color); break; } @@ -1154,17 +1162,17 @@ static void pbvh_update_draw_buffers(PBVH *bvh, PBVHNode **nodes, int totnode) } } -static void pbvh_draw_BB(PBVH *bvh) +void BKE_pbvh_draw_BB(PBVH *bvh) { - GPU_init_draw_pbvh_BB(); + GPU_pbvh_BB_draw_init(); for (int a = 0; a < bvh->totnode; a++) { PBVHNode *node = &bvh->nodes[a]; - GPU_draw_pbvh_BB(node->vb.bmin, node->vb.bmax, ((node->flag & PBVH_Leaf) != 0)); + GPU_pbvh_BB_draw(node->vb.bmin, node->vb.bmax, ((node->flag & PBVH_Leaf) != 0)); } - GPU_end_draw_pbvh_BB(); + GPU_pbvh_BB_draw_end(); } static int pbvh_flush_bb(PBVH *bvh, PBVHNode *node, int flag) @@ -1327,6 +1335,12 @@ void BKE_pbvh_get_grid_key(const PBVH *bvh, CCGKey *key) *key = bvh->gridkey; } +CCGDerivedMesh *BKE_pbvh_get_ccgdm(const PBVH *bvh) +{ + return bvh->ccgdm; +} + + BMesh *BKE_pbvh_get_bmesh(PBVH *bvh) { BLI_assert(bvh->type == PBVH_BMESH); @@ -1525,14 +1539,16 @@ void BKE_pbvh_raycast( bool ray_face_intersection_quad( const float ray_start[3], const float ray_normal[3], const float t0[3], const float t1[3], const float t2[3], const float t3[3], - float *dist) + float *depth) { - float dist_test; + float depth_test; - if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist_test, NULL, 0.1f) && (dist_test < *dist)) || - (isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t2, t3, &dist_test, NULL, 0.1f) && (dist_test < *dist))) + if ((isect_ray_tri_epsilon_v3( + ray_start, ray_normal, t0, t1, t2, &depth_test, NULL, 0.1f) && (depth_test < *depth)) || + (isect_ray_tri_epsilon_v3( + ray_start, ray_normal, t0, t2, t3, &depth_test, NULL, 0.1f) && (depth_test < *depth))) { - *dist = dist_test; + *depth = depth_test; return true; } else { @@ -1543,12 +1559,82 @@ bool ray_face_intersection_quad( bool ray_face_intersection_tri( const float ray_start[3], const float ray_normal[3], const float t0[3], const float t1[3], const float t2[3], - float *dist) + float *depth) +{ + float depth_test; + + if ((isect_ray_tri_epsilon_v3( + ray_start, ray_normal, t0, t1, t2, &depth_test, NULL, 0.1f) && (depth_test < *depth))) + { + *depth = depth_test; + return true; + } + else { + return false; + } +} + +/* Take advantage of the fact we know this wont be an intersection. + * Just handle ray-tri edges. */ +static float dist_squared_ray_to_tri_v3_fast( + const float ray_origin[3], const float ray_direction[3], + const float v0[3], const float v1[3], const float v2[3], + float r_point[3], float *r_depth) +{ + const float *tri[3] = {v0, v1, v2}; + float dist_sq_best = FLT_MAX; + for (int i = 0, j = 2; i < 3; j = i++) { + float point_test[3], depth_test = FLT_MAX; + const float dist_sq_test = dist_squared_ray_to_seg_v3( + ray_origin, ray_direction, tri[i], tri[j], point_test, &depth_test); + if (dist_sq_test < dist_sq_best || i == 0) { + copy_v3_v3(r_point, point_test); + *r_depth = depth_test; + dist_sq_best = dist_sq_test; + } + } + return dist_sq_best; +} + +bool ray_face_nearest_quad( + const float ray_start[3], const float ray_normal[3], + const float t0[3], const float t1[3], const float t2[3], const float t3[3], + float *depth, float *dist_sq) +{ + float dist_sq_test; + float co[3], depth_test; + + if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast( + ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)) + { + *dist_sq = dist_sq_test; + *depth = depth_test; + if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast( + ray_start, ray_normal, t0, t2, t3, co, &depth_test)) < *dist_sq)) + { + *dist_sq = dist_sq_test; + *depth = depth_test; + } + return true; + } + else { + return false; + } +} + +bool ray_face_nearest_tri( + const float ray_start[3], const float ray_normal[3], + const float t0[3], const float t1[3], const float t2[3], + float *depth, float *dist_sq) { - float dist_test; + float dist_sq_test; + float co[3], depth_test; - if ((isect_ray_tri_epsilon_v3(ray_start, ray_normal, t0, t1, t2, &dist_test, NULL, 0.1f) && (dist_test < *dist))) { - *dist = dist_test; + if (((dist_sq_test = dist_squared_ray_to_tri_v3_fast( + ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)) + { + *dist_sq = dist_sq_test; + *depth = depth_test; return true; } else { @@ -1560,7 +1646,7 @@ static bool pbvh_faces_node_raycast( PBVH *bvh, const PBVHNode *node, float (*origco)[3], const float ray_start[3], const float ray_normal[3], - float *dist) + float *depth) { const MVert *vert = bvh->verts; const MLoop *mloop = bvh->mloop; @@ -1582,7 +1668,7 @@ static bool pbvh_faces_node_raycast( origco[face_verts[0]], origco[face_verts[1]], origco[face_verts[2]], - dist); + depth); } else { /* intersect with current coordinates */ @@ -1591,7 +1677,7 @@ static bool pbvh_faces_node_raycast( vert[mloop[lt->tri[0]].v].co, vert[mloop[lt->tri[1]].v].co, vert[mloop[lt->tri[2]].v].co, - dist); + depth); } } @@ -1602,7 +1688,7 @@ static bool pbvh_grids_node_raycast( PBVH *bvh, PBVHNode *node, float (*origco)[3], const float ray_start[3], const float ray_normal[3], - float *dist) + float *depth) { const int totgrid = node->totprim; const int gridsize = bvh->gridkey.grid_size; @@ -1632,7 +1718,7 @@ static bool pbvh_grids_node_raycast( origco[y * gridsize + x + 1], origco[(y + 1) * gridsize + x + 1], origco[(y + 1) * gridsize + x], - dist); + depth); } else { hit |= ray_face_intersection_quad( @@ -1641,7 +1727,7 @@ static bool pbvh_grids_node_raycast( CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y), CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1), CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1), - dist); + depth); } } } @@ -1656,7 +1742,7 @@ static bool pbvh_grids_node_raycast( bool BKE_pbvh_node_raycast( PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco, const float ray_start[3], const float ray_normal[3], - float *dist) + float *depth) { bool hit = false; @@ -1667,16 +1753,16 @@ bool BKE_pbvh_node_raycast( case PBVH_FACES: hit |= pbvh_faces_node_raycast( bvh, node, origco, - ray_start, ray_normal, dist); + ray_start, ray_normal, depth); break; case PBVH_GRIDS: hit |= pbvh_grids_node_raycast( bvh, node, origco, - ray_start, ray_normal, dist); + ray_start, ray_normal, depth); break; case PBVH_BMESH: hit = pbvh_bmesh_node_raycast( - node, ray_start, ray_normal, dist, use_origco); + node, ray_start, ray_normal, depth, use_origco); break; } @@ -1727,6 +1813,176 @@ void BKE_pbvh_raycast_project_ray_root( } } +/* -------------------------------------------------------------------- */ + +typedef struct { + struct DistRayAABB_Precalc dist_ray_to_aabb_precalc; + bool original; +} FindNearestRayData; + +static bool nearest_to_ray_aabb_dist_sq(PBVHNode *node, void *data_v) +{ + FindNearestRayData *rcd = data_v; + const float *bb_min, *bb_max; + + if (rcd->original) { + /* BKE_pbvh_node_get_original_BB */ + bb_min = node->orig_vb.bmin; + bb_max = node->orig_vb.bmax; + } + else { + /* BKE_pbvh_node_get_BB */ + bb_min = node->vb.bmin; + bb_max = node->vb.bmax; + } + + float co_dummy[3], depth; + node->tmin = dist_squared_ray_to_aabb_v3(&rcd->dist_ray_to_aabb_precalc, bb_min, bb_max, co_dummy, &depth); + /* Ideally we would skip distances outside the range. */ + return depth > 0.0f; +} + +void BKE_pbvh_find_nearest_to_ray( + PBVH *bvh, BKE_pbvh_SearchNearestCallback cb, void *data, + const float ray_start[3], const float ray_normal[3], + bool original) +{ + FindNearestRayData ncd; + + dist_squared_ray_to_aabb_v3_precalc(&ncd.dist_ray_to_aabb_precalc, ray_start, ray_normal); + ncd.original = original; + + BKE_pbvh_search_callback_occluded(bvh, nearest_to_ray_aabb_dist_sq, &ncd, cb, data); +} + + +static bool pbvh_faces_node_nearest_to_ray( + PBVH *bvh, const PBVHNode *node, + float (*origco)[3], + const float ray_start[3], const float ray_normal[3], + float *depth, float *dist_sq) +{ + const MVert *vert = bvh->verts; + const MLoop *mloop = bvh->mloop; + const int *faces = node->prim_indices; + int i, totface = node->totprim; + bool hit = false; + + for (i = 0; i < totface; ++i) { + const MLoopTri *lt = &bvh->looptri[faces[i]]; + const int *face_verts = node->face_vert_indices[i]; + + if (paint_is_face_hidden(lt, vert, mloop)) + continue; + + if (origco) { + /* intersect with backuped original coordinates */ + hit |= ray_face_nearest_tri( + ray_start, ray_normal, + origco[face_verts[0]], + origco[face_verts[1]], + origco[face_verts[2]], + depth, dist_sq); + } + else { + /* intersect with current coordinates */ + hit |= ray_face_nearest_tri( + ray_start, ray_normal, + vert[mloop[lt->tri[0]].v].co, + vert[mloop[lt->tri[1]].v].co, + vert[mloop[lt->tri[2]].v].co, + depth, dist_sq); + } + } + + return hit; +} + +static bool pbvh_grids_node_nearest_to_ray( + PBVH *bvh, PBVHNode *node, + float (*origco)[3], + const float ray_start[3], const float ray_normal[3], + float *depth, float *dist_sq) +{ + const int totgrid = node->totprim; + const int gridsize = bvh->gridkey.grid_size; + bool hit = false; + + for (int i = 0; i < totgrid; ++i) { + CCGElem *grid = bvh->grids[node->prim_indices[i]]; + BLI_bitmap *gh; + + if (!grid) + continue; + + gh = bvh->grid_hidden[node->prim_indices[i]]; + + for (int y = 0; y < gridsize - 1; ++y) { + for (int x = 0; x < gridsize - 1; ++x) { + /* check if grid face is hidden */ + if (gh) { + if (paint_is_grid_face_hidden(gh, gridsize, x, y)) + continue; + } + + if (origco) { + hit |= ray_face_nearest_quad( + ray_start, ray_normal, + origco[y * gridsize + x], + origco[y * gridsize + x + 1], + origco[(y + 1) * gridsize + x + 1], + origco[(y + 1) * gridsize + x], + depth, dist_sq); + } + else { + hit |= ray_face_nearest_quad( + ray_start, ray_normal, + CCG_grid_elem_co(&bvh->gridkey, grid, x, y), + CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y), + CCG_grid_elem_co(&bvh->gridkey, grid, x + 1, y + 1), + CCG_grid_elem_co(&bvh->gridkey, grid, x, y + 1), + depth, dist_sq); + } + } + } + + if (origco) + origco += gridsize * gridsize; + } + + return hit; +} + +bool BKE_pbvh_node_find_nearest_to_ray( + PBVH *bvh, PBVHNode *node, float (*origco)[3], bool use_origco, + const float ray_start[3], const float ray_normal[3], + float *depth, float *dist_sq) +{ + bool hit = false; + + if (node->flag & PBVH_FullyHidden) + return false; + + switch (bvh->type) { + case PBVH_FACES: + hit |= pbvh_faces_node_nearest_to_ray( + bvh, node, origco, + ray_start, ray_normal, depth, dist_sq); + break; + case PBVH_GRIDS: + hit |= pbvh_grids_node_nearest_to_ray( + bvh, node, origco, + ray_start, ray_normal, depth, dist_sq); + break; + case PBVH_BMESH: + hit = pbvh_bmesh_node_nearest_to_ray( + node, ray_start, ray_normal, depth, dist_sq, use_origco); + break; + } + + return hit; +} + typedef struct { DMSetMaterial setMaterial; bool wireframe; @@ -1756,7 +2012,7 @@ void BKE_pbvh_node_draw(PBVHNode *node, void *data_v) #endif if (!(node->flag & PBVH_FullyHidden)) { - GPU_draw_pbvh_buffers(node->draw_buffers, + GPU_pbvh_buffers_draw(node->draw_buffers, data->setMaterial, data->wireframe, data->fast); @@ -1858,7 +2114,7 @@ void BKE_pbvh_draw(PBVH *bvh, float (*planes)[4], float (*fnors)[3], } if (G.debug_value == 14) - pbvh_draw_BB(bvh); + BKE_pbvh_draw_BB(bvh); } void BKE_pbvh_grids_update(PBVH *bvh, CCGElem **grids, void **gridfaces, |