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
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
