Commit: b01a56ee5c45b51e522c54c72b327c9aba34dff3 Author: Germano Cavalcante Date: Thu Jun 30 15:43:47 2016 +1000 Branches: master https://developer.blender.org/rBb01a56ee5c45b51e522c54c72b327c9aba34dff3
Transform Snap: Optimize edge-snap using BVH tree changes in BLI_kdopbvh: - `BLI_bvhtree_find_nearest_to_ray` now takes is_ray_normalized and scale argument. - `BLI_bvhtree_find_nearest_to_ray_angle` has been added (use for perspective view). changes in BLI_bvhutils: - `bvhtree_from_editmesh_edges_ex` was added. changes in math_geom: - `dist_squared_ray_to_seg_v3` was added. other changes: - `do_ray_start_correction` is no longer necessary to snap to verts. - the way in which the test of depth was done before is being simulated in callbacks. =================================================================== M source/blender/blenkernel/BKE_bvhutils.h M source/blender/blenkernel/intern/bvhutils.c M source/blender/blenlib/BLI_kdopbvh.h M source/blender/blenlib/BLI_math_geom.h M source/blender/blenlib/intern/BLI_kdopbvh.c M source/blender/blenlib/intern/math_geom.c M source/blender/editors/transform/transform_snap_object.c =================================================================== diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h index 7ec91b0..80b248a 100644 --- a/source/blender/blenkernel/BKE_bvhutils.h +++ b/source/blender/blenkernel/BKE_bvhutils.h @@ -122,6 +122,14 @@ BVHTree *bvhtree_from_mesh_verts_ex( const bool vert_allocated, const BLI_bitmap *mask, int verts_num_active, float epsilon, int tree_type, int axis); +BVHTree *bvhtree_from_editmesh_edges( + BVHTreeFromEditMesh *data, struct BMEditMesh *em, + float epsilon, int tree_type, int axis); +BVHTree *bvhtree_from_editmesh_edges_ex( + BVHTreeFromEditMesh *data, struct BMEditMesh *em, + const BLI_bitmap *edges_mask, int edges_num_active, + float epsilon, int tree_type, int axis); + BVHTree *bvhtree_from_mesh_edges( struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis); diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c index a3cfe3f..264d87b 100644 --- a/source/blender/blenkernel/intern/bvhutils.c +++ b/source/blender/blenkernel/intern/bvhutils.c @@ -590,6 +590,77 @@ BVHTree *bvhtree_from_mesh_verts_ex( /** \name Edge Builder * \{ */ +static BVHTree *bvhtree_from_editmesh_edges_create_tree( + float epsilon, int tree_type, int axis, + BMEditMesh *em, const int edges_num, + const BLI_bitmap *edges_mask, int edges_num_active) +{ + BVHTree *tree = NULL; + int i; + BM_mesh_elem_table_ensure(em->bm, BM_EDGE); + if (edges_mask) { + BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edges_num)); + } + else { + edges_num_active = edges_num; + } + + tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis); + + if (tree) { + BMIter iter; + BMEdge *eed; + BM_ITER_MESH_INDEX (eed, &iter, em->bm, BM_EDGES_OF_MESH, i) { + if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) { + continue; + } + float co[2][3]; + copy_v3_v3(co[0], eed->v1->co); + copy_v3_v3(co[1], eed->v2->co); + + BLI_bvhtree_insert(tree, i, co[0], 2); + } + BLI_assert(BLI_bvhtree_get_size(tree) == edges_num_active); + BLI_bvhtree_balance(tree); + } + + return tree; +} + +/* Builds a bvh tree where nodes are the edges of the given em */ +BVHTree *bvhtree_from_editmesh_edges_ex( + BVHTreeFromEditMesh *data, BMEditMesh *em, + const BLI_bitmap *edges_mask, int edges_num_active, + float epsilon, int tree_type, int axis) +{ + int edge_num = em->bm->totedge; + + BVHTree *tree = bvhtree_from_editmesh_edges_create_tree( + epsilon, tree_type, axis, + em, edge_num, edges_mask, edges_num_active); + + if (tree) { + memset(data, 0, sizeof(*data)); + data->tree = tree; + data->em = em; + data->nearest_callback = NULL; /* TODO */ + data->raycast_callback = NULL; /* TODO */ + /* TODO: not urgent however since users currently define own callbacks */ + data->nearest_to_ray_callback = NULL; + } + + return tree; +} +BVHTree *bvhtree_from_editmesh_edges( + BVHTreeFromEditMesh *data, BMEditMesh *em, + float epsilon, int tree_type, int axis) +{ + return bvhtree_from_editmesh_edges_ex( + data, em, + NULL, -1, + epsilon, tree_type, axis); +} + /* Builds a bvh tree where nodes are the edges of the given dm */ BVHTree *bvhtree_from_mesh_edges( BVHTreeFromMesh *data, DerivedMesh *dm, diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h index fb8c252..91d3980 100644 --- a/source/blender/blenlib/BLI_kdopbvh.h +++ b/source/blender/blenlib/BLI_kdopbvh.h @@ -96,7 +96,8 @@ typedef void (*BVHTree_NearestPointCallback)(void *userdata, int index, const fl typedef void (*BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit); /* callback must update nearest in case it finds a nearest result */ -typedef void (*BVHTree_NearestToRayCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeNearest *nearest); +typedef void (*BVHTree_NearestToRayCallback)(void *userdata, const float ray_co[3], const float ray_dir[3], + const float scale[3], int index, BVHTreeNearest *nearest); /* callback to check if 2 nodes overlap (use thread if intersection results need to be stored) */ typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread); @@ -142,8 +143,16 @@ int BLI_bvhtree_find_nearest( BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata); +int BLI_bvhtree_find_nearest_to_ray_angle( + BVHTree *tree, const float co[3], const float dir[3], + const bool ray_is_normalized, const float scale[3], + BVHTreeNearest *nearest, + BVHTree_NearestToRayCallback callback, void *userdata); + int BLI_bvhtree_find_nearest_to_ray( - BVHTree *tree, const float co[3], const float dir[3], BVHTreeNearest *nearest, + BVHTree *tree, const float co[3], const float dir[3], + const bool ray_is_normalized, const float scale[3], + BVHTreeNearest *nearest, BVHTree_NearestToRayCallback callback, void *userdata); int BLI_bvhtree_ray_cast_ex( diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 54b824c9..84a25f5 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -115,6 +115,13 @@ float dist_signed_squared_to_corner_v3v3v3( const float p[3], const float v1[3], const float v2[3], const float v3[3], const float axis_ref[3]); +float dist_squared_to_ray_v3( + const float ray_origin[3], const float ray_direction[3], + const float co[3], float *r_depth); +float dist_squared_ray_to_seg_v3( + const float ray_origin[3], const float ray_direction[3], + const float v0[3], const float v1[3], + float r_point[3], float *r_depth); float closest_to_line_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2]); float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3]); void closest_to_line_segment_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2]); diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index 6cef192..51b79d1 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -163,12 +163,23 @@ typedef struct BVHNearestRayData { BVHTree *tree; BVHTree_NearestToRayCallback callback; void *userdata; - BVHTreeRay ray; - struct NearestRayToAABB_Precalc nearest_precalc; + struct { + bool sign[3]; + float origin[3]; + float direction[3]; + + float direction_scaled_square[3]; + float inv_dir[3]; + + float cdot_axis[3]; + } ray; bool pick_smallest[3]; + BVHTreeNearest nearest; + + float scale[3]; } BVHNearestRayData; /** \} */ @@ -1889,58 +1900,374 @@ void BLI_bvhtree_ray_cast_all( /* -------------------------------------------------------------------- */ -/** \name BLI_bvhtree_find_nearest_to_ray +/** \name BLI_bvhtree_find_nearest_to_ray functions * * \{ */ +static void dist_squared_ray_to_aabb_scaled_v3_precalc( + BVHNearestRayData *data, + const float ray_origin[3], const float ray_direction[3], + const bool ray_is_normalized, const float scale[3]) +{ + if (scale) { + copy_v3_v3(data->scale, scale); + } + else { + copy_v3_fl(data->scale, 1.0f); + } + /* un-normalize ray */ + if (ray_is_normalized && scale && + (data->scale[0] != 1.0f || data->scale[1] != 1.0f || data->scale[2] != 1.0f)) + { + data->ray.direction[0] = ray_direction[0] * data->scale[0]; + data->ray.direction[1] = ray_direction[1] * data->scale[1]; + data->ray.direction[2] = ray_direction[2] * data->scale[2]; + + mul_v3_v3fl(data->ray.direction, ray_direction, 1 / len_v3(data->ray.direction)); + } + else { + copy_v3_v3(data->ray.direction, ray_direction); + } + + float dir_sq[3]; + + for (int i = 0; i < 3; i++) { + data->ray.origin[i] = ray_origin[i]; + data->ray.inv_dir[i] = (data->ray.direction[i] != 0.0f) ? + (1.0f / data->ray.direction[i]) : FLT_MAX; + /* It has to be in function of `ray.inv_dir`, + * since the division of 1 by 0.0f, can be -inf or +inf */ + data->ray.sign[i] = (data->ray.inv_dir[i] < 0.0f); + + data->ray.direction_scaled_square[i] = data->ray.direction[i] * data->scale[i]; + + dir_sq[i] = SQUARE(data->ray.direction_scaled_square[i]); + + data->ray.direction_scaled_square[i] *= data->scale[i]; + } + + /* `diag_sq` Length square of each face diagonal */ + float diag_sq[3] = { + dir_sq[1] + dir_sq[2], + dir_sq[0] + dir_sq[2], + dir_sq[0] + dir_sq[1], + }; + + data->ray.cdot_axis[0] = (diag_sq[0] != 0.0f) ? data->ray.direction[0] / diag_sq[0] : FLT_MAX; + data->ray.cdot_axis[1] = (diag_sq[1] != 0.0f) ? data->ray.direction[1] / diag_sq[1] : FLT_MAX; + data->ray.cdot_axis[2] = (diag_sq[2] != 0.0f) ? data->ray.direction[2] / diag_sq[2] : FLT_MAX; +} + +/** + * Returns the squared distance from a ray to a bound-box `AABB`. + * It is based on `fast_ray_nearest_hit` solution to obtain + * the coordinates of the nearest edge of Bound Box to the ray + */ +MINLINE float dist_squared_ray_to_aabb_scaled_v3__impl( + const BVHNearestRayData *data, + const float bv[6], float *r_depth_sq, bool r_axis_closest[3]) +{ + + /* `tmin` is a vector that has the smaller distances to each of the + * infinite planes of the `AABB` faces (hit in nearest face X plane, + * nearest face Y plane and nearest face Z plane) */ + float local_bvmin[3], local_bvmax[3]; + + if (data->ray.sign[0]) { + local_bvmin[0] = bv[1]; + local_bvmax[0] = bv[0]; + } + else { + local_bvmin[0] = bv[0]; + local_bvmax[0] = bv[1]; + } + + if (data->ray.sign[1]) { + local_bvmin[1] = bv[3]; + local_bvmax[1] = bv[2]; + } + else { + local_bvmin[1] = bv[2]; + local_bvmax[1] = bv[3]; + } + + if (data->ray.sign[2]) { + local_bvmin[2] = bv[5]; + local_bvmax[2] = bv[4]; + } + else { + local_bvmin[2] = bv[4]; + local_bvmax[2] = bv[5]; + } + + sub @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org https://lists.blender.org/mailman/listinfo/bf-blender-cvs