Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r--source/blender/blenlib/BLI_kdopbvh.h13
-rw-r--r--source/blender/blenlib/BLI_math_geom.h7
-rw-r--r--source/blender/blenlib/BLI_math_vector.h10
-rw-r--r--source/blender/blenlib/intern/BLI_kdopbvh.c416
-rw-r--r--source/blender/blenlib/intern/array_store.c14
-rw-r--r--source/blender/blenlib/intern/math_geom.c61
-rw-r--r--source/blender/blenlib/intern/math_interp.c32
-rw-r--r--source/blender/blenlib/intern/math_rotation.c3
-rw-r--r--source/blender/blenlib/intern/math_vector.c21
-rw-r--r--source/blender/blenlib/intern/math_vector_inline.c34
10 files changed, 559 insertions, 52 deletions
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index fb8c2520e67..91d39801645 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 54b824c91ac..84a25f533bf 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/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index 8a36b047bad..d15fe1a95dc 100644
--- a/source/blender/blenlib/BLI_math_vector.h
+++ b/source/blender/blenlib/BLI_math_vector.h
@@ -191,6 +191,12 @@ MINLINE float len_manhattan_v3v3(const float a[3], const float b[3]) ATTR_WARN_U
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT;
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT;
+MINLINE float normalize_v2_length(float r[2], const float unit_scale);
+MINLINE float normalize_v2_v2_length(float r[2], const float a[2], const float unit_scale);
+MINLINE float normalize_v3_length(float r[3], const float unit_scale);
+MINLINE float normalize_v3_v3_length(float r[3], const float a[3], const float unit_scale);
+MINLINE double normalize_v3_length_d(double n[3], const double unit_scale);
+
MINLINE float normalize_v2(float r[2]);
MINLINE float normalize_v2_v2(float r[2], const float a[2]);
MINLINE float normalize_v3(float r[3]);
@@ -215,6 +221,10 @@ bool interp_v2_v2v2_slerp(float target[2], const float a[2], const float b[2], c
void interp_v3_v3v3_slerp_safe(float target[3], const float a[3], const float b[3], const float t);
void interp_v2_v2v2_slerp_safe(float target[2], const float a[2], const float b[2], const float t);
+void interp_v2_v2v2v2v2_cubic(
+ float p[2], const float v1[2], const float v2[2], const float v3[2], const float v4[2],
+ const float u);
+
void interp_v3_v3v3_char(char target[3], const char a[3], const char b[3], const float t);
void interp_v3_v3v3_uchar(unsigned char target[3], const unsigned char a[3], const unsigned char b[3], const float t);
void interp_v4_v4v4_char(char target[4], const char a[4], const char b[4], const float t);
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 6cef1924e33..92f4e998206 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_v3_v3(local_bvmin, data->ray.origin);
+ sub_v3_v3(local_bvmax, data->ray.origin);
+
+ const float tmin[3] = {
+ local_bvmin[0] * data->ray.inv_dir[0],
+ local_bvmin[1] * data->ray.inv_dir[1],
+ local_bvmin[2] * data->ray.inv_dir[2],
+ };
+
+ /* `tmax` is a vector that has the longer distances to each of the
+ * infinite planes of the `AABB` faces (hit in farthest face X plane,
+ * farthest face Y plane and farthest face Z plane) */
+ const float tmax[3] = {
+ local_bvmax[0] * data->ray.inv_dir[0],
+ local_bvmax[1] * data->ray.inv_dir[1],
+ local_bvmax[2] * data->ray.inv_dir[2],
+ };
+ /* `v1` and `v3` is be the coordinates of the nearest `AABB` edge to the ray*/
+ float v1[3], v2[3];
+ /* `rtmin` is the highest value of the smaller distances. == max_axis_v3(tmin)
+ * `rtmax` is the lowest value of longer distances. == min_axis_v3(tmax)*/
+ float rtmin, rtmax, mul;
+ /* `main_axis` is the axis equivalent to edge close to the ray */
+ int main_axis;
+
+ r_axis_closest[0] = false;
+ r_axis_closest[1] = false;
+ r_axis_closest[2] = false;
+
+ /* *** min_axis_v3(tmax) *** */
+ if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) {
+ // printf("# Hit in X %s\n", data->sign[0] ? "min", "max");
+ rtmax = tmax[0];
+ v1[0] = v2[0] = local_bvmax[0];
+ mul = local_bvmax[0] * data->ray.direction_scaled_square[0];
+ main_axis = 3;
+ r_axis_closest[0] = data->ray.sign[0];
+ }
+ else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) {
+ // printf("# Hit in Y %s\n", data->sign[1] ? "min", "max");
+ rtmax = tmax[1];
+ v1[1] = v2[1] = local_bvmax[1];
+ mul = local_bvmax[1] * data->ray.direction_scaled_square[1];
+ main_axis = 2;
+ r_axis_closest[1] = data->ray.sign[1];
+ }
+ else {
+ // printf("# Hit in Z %s\n", data->sign[2] ? "min", "max");
+ rtmax = tmax[2];
+ v1[2] = v2[2] = local_bvmax[2];
+ mul = local_bvmax[2] * data->ray.direction_scaled_square[2];
+ main_axis = 1;
+ r_axis_closest[2] = data->ray.sign[2];
+ }
+
+ /* *** max_axis_v3(tmin) *** */
+ if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) {
+ // printf("# To X %s\n", data->sign[0] ? "max", "min");
+ rtmin = tmin[0];
+ v1[0] = v2[0] = local_bvmin[0];
+ mul += local_bvmin[0] * data->ray.direction_scaled_square[0];
+ main_axis -= 3;
+ r_axis_closest[0] = !data->ray.sign[0];
+ }
+ else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) {
+ // printf("# To Y %s\n", data->sign[1] ? "max", "min");
+ rtmin = tmin[1];
+ v1[1] = v2[1] = local_bvmin[1];
+ mul += local_bvmin[1] * data->ray.direction_scaled_square[1];
+ main_axis -= 1;
+ r_axis_closest[1] = !data->ray.sign[1];
+ }
+ else {
+ // printf("# To Z %s\n", data->sign[2] ? "max", "min");
+ rtmin = tmin[2];
+ v1[2] = v2[2] = local_bvmin[2];
+ mul += local_bvmin[2] * data->ray.direction_scaled_square[2];
+ main_axis -= 2;
+ r_axis_closest[2] = !data->ray.sign[2];
+ }
+ /* *** end min/max axis *** */
+
+ if (main_axis < 0)
+ main_axis += 3;
+
+ /* if rtmin < rtmax, ray intersect `AABB` */
+ if (rtmin <= rtmax) {
+#ifdef IGNORE_BEHIND_RAY
+ /* `if rtmax < depth_min`, the whole `AABB` is behind us */
+ if (rtmax < min_depth) {
+ return fallback;
+ }
+#endif
+ const float proj = rtmin * data->ray.direction[main_axis];
+
+ if (data->ray.sign[main_axis])
+ r_axis_closest[main_axis] = (proj - local_bvmax[main_axis]) < (local_bvmin[main_axis] - proj);
+ else
+ r_axis_closest[main_axis] = (proj - local_bvmin[main_axis]) < (local_bvmax[main_axis] - proj);
+
+ //if (r_depth_sq)
+ // *r_depth_sq = SQUARE(rtmin);
+
+ return 0.0f;
+ }
+#ifdef IGNORE_BEHIND_RAY
+ /* `if rtmin < depth_min`, the whole `AABB` is behing us */
+ else if (rtmin < min_depth) {
+ return fallback;
+ }
+#endif
+
+ if (data->ray.sign[main_axis]) {
+ v1[main_axis] = local_bvmax[main_axis];
+ v2[main_axis] = local_bvmin[main_axis];
+ }
+ else {
+ v1[main_axis] = local_bvmin[main_axis];
+ v2[main_axis] = local_bvmax[main_axis];
+ }
+ {
+ /* `proj` equals to nearest point on the ray closest to the edge `v1 v2` of the `AABB`. */
+ const float proj = mul * data->ray.cdot_axis[main_axis];
+ float depth_sq, r_point[3];
+ if (v1[main_axis] > proj) { /* the nearest point to the ray is the point v1 */
+ r_axis_closest[main_axis] = true;
+ /* `depth` is equivalent the distance of the the projection of v1 on the ray */
+ depth_sq = mul + data->ray.direction_scaled_square[main_axis] * v1[main_axis];
+
+ copy_v3_v3(r_point, v1);
+ }
+ else if (v2[main_axis] < proj) { /* the nearest point of the ray is the point v2 */
+ r_axis_closest[main_axis] = false;
+
+ depth_sq = mul + data->ray.direction_scaled_square[main_axis] * v2[main_axis];
+
+ copy_v3_v3(r_point, v2);
+ }
+ else { /* the nearest point of the ray is on the edge of the `AABB`. */
+ r_axis_closest[main_axis] = (proj - v1[main_axis]) < (v2[main_axis] - proj);
+
+ depth_sq = mul + data->ray.direction_scaled_square[main_axis] * proj;
+#if 0
+ r_point[0] = main_axis == 0 ? proj : v2[0];
+ r_point[1] = main_axis == 1 ? proj : v2[1];
+ r_point[2] = main_axis == 2 ? proj : v2[2];
+#else
+ v2[main_axis] = proj;
+ copy_v3_v3(r_point, v2);
+#endif
+ }
+ depth_sq *= depth_sq;
+
+ if (r_depth_sq)
+ *r_depth_sq = depth_sq;
+
+ /* TODO: scale can be optional */
+ r_point[0] *= data->scale[0];
+ r_point[1] *= data->scale[1];
+ r_point[2] *= data->scale[2];
+
+ return len_squared_v3(r_point) - depth_sq;
+ }
+}
+
+/**
+ * <pre>
+ * + r_point
+ * |
+ * | dist
+ * |
+ * +----depth----+orig <-- dir
+ *
+ * tangent = dist/depth
+ * </pre>
+ */
+static float calc_tangent_sq(BVHNearestRayData *data, BVHNode *node)
+{
+ float depth_sq;
+ const float dist_sq = dist_squared_ray_to_aabb_scaled_v3__impl(
+ data, node->bv, &depth_sq, data->pick_smallest);
+
+ return (dist_sq != 0.0f) ? (dist_sq / depth_sq) : 0.0f;
+}
+
static float calc_dist_sq_to_ray(BVHNearestRayData *data, BVHNode *node)
{
- const float *bv = node->bv;
- const float bb_min[3] = {bv[0], bv[2], bv[4]};
- const float bb_max[3] = {bv[1], bv[3], bv[5]};
- return dist_squared_ray_to_aabb_v3(&data->nearest_precalc, bb_min, bb_max, data->pick_smallest);
+ return dist_squared_ray_to_aabb_scaled_v3__impl(
+ data, node->bv, NULL,
+ data->pick_smallest);
}
-static void dfs_find_nearest_to_ray_dfs(BVHNearestRayData *data, BVHNode *node)
+static void dfs_find_lowest_tangent_dfs(BVHNearestRayData *data, BVHNode *node)
{
if (node->totnode == 0) {
if (data->callback) {
- data->callback(data->userdata, node->index, &data->ray, &data->nearest);
+ data->callback(data->userdata, data->ray.origin, data->ray.direction,
+ data->scale, node->index, &data->nearest);
+ }
+ else {
+ data->nearest.index = node->index;
+ data->nearest.dist_sq = calc_tangent_sq(data, node);
+ /* TODO: return a value to the data->nearest.co
+ * not urgent however since users currently define own callbacks */
+ }
+ }
+ else {
+ int i;
+ /* First pick the closest node to dive on */
+ if (data->pick_smallest[node->main_axis]) {
+ for (i = 0; i != node->totnode; i++) {
+ if (calc_tangent_sq(data, node->children[i]) < data->nearest.dist_sq) {
+ dfs_find_lowest_tangent_dfs(data, node->children[i]);
+ }
+ }
}
else {
- const float dist_sq = calc_dist_sq_to_ray(data, node);
- if (dist_sq != FLT_MAX) { /* not an invalid ray */
- data->nearest.index = node->index;
- data->nearest.dist_sq = dist_sq;
- /* TODO: return a value to the data->nearest.co
- * not urgent however since users currently define own callbacks */
+ for (i = node->totnode - 1; i >= 0; i--) {
+ if (calc_tangent_sq(data, node->children[i]) < data->nearest.dist_sq) {
+ dfs_find_lowest_tangent_dfs(data, node->children[i]);
+ }
}
}
}
+}
+
+static void dfs_find_nearest_to_ray_dfs(BVHNearestRayData *data, BVHNode *node)
+{
+ if (node->totnode == 0) {
+ if (data->callback) {
+ data->callback(data->userdata, data->ray.origin, data->ray.direction,
+ data->scale, node->index, &data->nearest);
+ }
+ else {
+ data->nearest.index = node->index;
+ data->nearest.dist_sq = calc_dist_sq_to_ray(data, node);
+ /* TODO: return a value to the data->nearest.co
+ * not urgent however since users currently define own callbacks */
+ }
+ }
else {
int i;
/* First pick the closest node to dive on */
if (data->pick_smallest[node->main_axis]) {
for (i = 0; i != node->totnode; i++) {
- if (calc_dist_sq_to_ray(data, node->children[i]) >= data->nearest.dist_sq) {
- continue;
+ if (calc_dist_sq_to_ray(data, node->children[i]) < data->nearest.dist_sq) {
+ dfs_find_nearest_to_ray_dfs(data, node->children[i]);
}
- dfs_find_nearest_to_ray_dfs(data, node->children[i]);
}
}
else {
for (i = node->totnode - 1; i >= 0; i--) {
- if (calc_dist_sq_to_ray(data, node->children[i]) >= data->nearest.dist_sq) {
- continue;
+ if (calc_dist_sq_to_ray(data, node->children[i]) < data->nearest.dist_sq) {
+ dfs_find_nearest_to_ray_dfs(data, node->children[i]);
}
- dfs_find_nearest_to_ray_dfs(data, node->children[i]);
}
}
}
}
-int BLI_bvhtree_find_nearest_to_ray(
- BVHTree *tree, const float co[3], const float dir[3], BVHTreeNearest *nearest,
+/**
+ * Returns the point whose tangent defined by the angle between the point and ray is the lowest
+ * nearest.dist_sq returns the angle's tangent
+ */
+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)
{
BVHNearestRayData data;
@@ -1951,11 +2278,46 @@ int BLI_bvhtree_find_nearest_to_ray(
data.callback = callback;
data.userdata = userdata;
- copy_v3_v3(data.ray.origin, co);
- copy_v3_v3(data.ray.direction, dir);
- data.ray.radius = 0.0f; /* unused here */
+ dist_squared_ray_to_aabb_scaled_v3_precalc(&data, co, dir, ray_is_normalized, scale);
+
+ if (nearest) {
+ memcpy(&data.nearest, nearest, sizeof(*nearest));
+ }
+ else {
+ data.nearest.index = -1;
+ data.nearest.dist_sq = FLT_MAX;
+ }
+
+ /* dfs search */
+ if (root) {
+ if (calc_tangent_sq(&data, root) < data.nearest.dist_sq)
+ dfs_find_lowest_tangent_dfs(&data, root);
+ }
+
+ /* copy back results */
+ if (nearest) {
+ memcpy(nearest, &data.nearest, sizeof(*nearest));
+ }
+
+ return data.nearest.index;
+}
+
+/* return the nearest point to ray */
+int BLI_bvhtree_find_nearest_to_ray(
+ 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)
+{
+ BVHNearestRayData data;
+ BVHNode *root = tree->nodes[tree->totleaf];
+
+ data.tree = tree;
+
+ data.callback = callback;
+ data.userdata = userdata;
- dist_squared_ray_to_aabb_v3_precalc(&data.nearest_precalc, co, dir);
+ dist_squared_ray_to_aabb_scaled_v3_precalc(&data, co, dir, ray_is_normalized, scale);
if (nearest) {
memcpy(&data.nearest, nearest, sizeof(*nearest));
diff --git a/source/blender/blenlib/intern/array_store.c b/source/blender/blenlib/intern/array_store.c
index 33565596c1f..6000c1a680c 100644
--- a/source/blender/blenlib/intern/array_store.c
+++ b/source/blender/blenlib/intern/array_store.c
@@ -249,7 +249,7 @@ typedef struct BArrayMemory {
/**
* Main storage for all states
*/
-typedef struct BArrayStore {
+struct BArrayStore {
/* static */
BArrayInfo info;
@@ -260,7 +260,7 @@ typedef struct BArrayStore {
* #BArrayState may be in any order (logic should never depend on state order).
*/
ListBase states;
-} BArrayStore;
+};
/**
* A single instance of an array.
@@ -272,13 +272,13 @@ typedef struct BArrayStore {
* While this could be moved to a memory pool,
* it makes it easier to trace invalid usage, so leave as-is for now.
*/
-typedef struct BArrayState {
+struct BArrayState {
/** linked list in #BArrayStore.states */
struct BArrayState *next, *prev;
struct BChunkList *chunk_list; /* BChunkList's */
-} BArrayState;
+};
typedef struct BChunkList {
ListBase chunk_refs; /* BChunkRef's */
@@ -1750,10 +1750,11 @@ bool BLI_array_store_is_valid(
} \
} ((void)0)
-
/* count chunk_list's */
- int totrefs = 0;
GHash *chunk_list_map = BLI_ghash_ptr_new(__func__);
+ GHash *chunk_map = BLI_ghash_ptr_new(__func__);
+
+ int totrefs = 0;
for (BArrayState *state = bs->states.first; state; state = state->next) {
GHASH_PTR_ADD_USER(chunk_list_map, state->chunk_list);
}
@@ -1771,7 +1772,6 @@ bool BLI_array_store_is_valid(
}
/* count chunk's */
- GHash *chunk_map = BLI_ghash_ptr_new(__func__);
GHASH_ITER (gh_iter, chunk_list_map) {
const struct BChunkList *chunk_list = BLI_ghashIterator_getKey(&gh_iter);
for (const BChunkRef *cref = chunk_list->chunk_refs.first; cref; cref = cref->next) {
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 82f527942e8..40454a93ec8 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -572,6 +572,67 @@ float dist_signed_squared_to_corner_v3v3v3(
}
}
+/**
+ * return the distance squared of a point to a ray.
+ */
+float dist_squared_to_ray_v3(
+ const float ray_origin[3], const float ray_direction[3],
+ const float co[3], float *r_depth)
+{
+ float dvec[3];
+ sub_v3_v3v3(dvec, co, ray_origin);
+ *r_depth = dot_v3v3(dvec, ray_direction);
+ return len_squared_v3(dvec) - SQUARE(*r_depth);
+}
+/**
+ * Find the closest point in a seg to a ray and return the distance squared.
+ * \param r_point : Is the point on segment closest to ray (or to ray_origin if the ray and the segment are parallel).
+ * \param depth: the distance of r_point projection on ray to the ray_origin.
+ */
+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 a[3], t[3], n[3], lambda;
+ sub_v3_v3v3(a, v1, v0);
+ sub_v3_v3v3(t, v0, ray_origin);
+ cross_v3_v3v3(n, a, ray_direction);
+ const float nlen = len_squared_v3(n);
+
+ /* if (nlen == 0.0f) the lines are parallel,
+ * has no nearest point, only distance squared.*/
+ if (nlen == 0.0f) {
+ /* Calculate the distance to the point v0 then */
+ copy_v3_v3(r_point, v0);
+ *r_depth = dot_v3v3(t, ray_direction);
+ }
+ else {
+ float c[3], cray[3];
+ sub_v3_v3v3(c, n, t);
+ cross_v3_v3v3(cray, c, ray_direction);
+ lambda = dot_v3v3(cray, n) / nlen;
+ if (lambda <= 0) {
+ copy_v3_v3(r_point, v0);
+
+ *r_depth = dot_v3v3(t, ray_direction);
+ }
+ else if (lambda >= 1) {
+ copy_v3_v3(r_point, v1);
+
+ sub_v3_v3v3(t, v1, ray_origin);
+ *r_depth = dot_v3v3(t, ray_direction);
+ }
+ else {
+ madd_v3_v3v3fl(r_point, v0, a, lambda);
+
+ sub_v3_v3v3(t, r_point, ray_origin);
+ *r_depth = dot_v3v3(t, ray_direction);
+ }
+ }
+ return len_squared_v3(t) - SQUARE(*r_depth);
+}
+
/* Adapted from "Real-Time Collision Detection" by Christer Ericson,
* published by Morgan Kaufmann Publishers, copyright 2005 Elsevier Inc.
*
diff --git a/source/blender/blenlib/intern/math_interp.c b/source/blender/blenlib/intern/math_interp.c
index 069d23e7147..8c361673715 100644
--- a/source/blender/blenlib/intern/math_interp.c
+++ b/source/blender/blenlib/intern/math_interp.c
@@ -284,16 +284,19 @@ BLI_INLINE void bilinear_interpolation(const unsigned char *byte_buffer, const f
if (x1 < 0) x1 = width - 1;
if (x2 >= width) x2 = 0;
}
+ else if (x2 < 0 || x1 >= width) {
+ copy_vn_fl(float_output, components, 0.0f);
+ return;
+ }
+
if (wrap_y) {
if (y1 < 0) y1 = height - 1;
if (y2 >= height) y2 = 0;
}
-
- CLAMP(x1, 0, width - 1);
- CLAMP(x2, 0, width - 1);
-
- CLAMP(y1, 0, height - 1);
- CLAMP(y2, 0, height - 1);
+ else if (y2 < 0 || y1 >= height) {
+ copy_vn_fl(float_output, components, 0.0f);
+ return;
+ }
/* sample including outside of edges of image */
if (x1 < 0 || y1 < 0) row1 = empty;
@@ -331,8 +334,21 @@ BLI_INLINE void bilinear_interpolation(const unsigned char *byte_buffer, const f
const unsigned char *row1, *row2, *row3, *row4;
unsigned char empty[4] = {0, 0, 0, 0};
- /* sample area entirely outside image? */
- if (x2 < 0 || x1 > width - 1 || y2 < 0 || y1 > height - 1) {
+ /* pixel value must be already wrapped, however values at boundaries may flip */
+ if (wrap_x) {
+ if (x1 < 0) x1 = width - 1;
+ if (x2 >= width) x2 = 0;
+ }
+ else if (x2 < 0 || x1 >= width) {
+ copy_vn_uchar(byte_output, components, 0);
+ return;
+ }
+
+ if (wrap_y) {
+ if (y1 < 0) y1 = height - 1;
+ if (y2 >= height) y2 = 0;
+ }
+ else if (y2 < 0 || y1 >= height) {
copy_vn_uchar(byte_output, components, 0);
return;
}
diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c
index d962e4f0fa7..b285a74b8ac 100644
--- a/source/blender/blenlib/intern/math_rotation.c
+++ b/source/blender/blenlib/intern/math_rotation.c
@@ -200,8 +200,7 @@ void mul_fac_qt_fl(float q[4], const float fac)
const float co = cosf(angle);
const float si = sinf(angle);
q[0] = co;
- normalize_v3(q + 1);
- mul_v3_fl(q + 1, si);
+ normalize_v3_length(q + 1, si);
}
/* skip error check, currently only needed by mat3_to_quat_is_ok */
diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c
index 988034349e0..95d5c9fde87 100644
--- a/source/blender/blenlib/intern/math_vector.c
+++ b/source/blender/blenlib/intern/math_vector.c
@@ -164,6 +164,27 @@ void interp_v2_v2v2_slerp_safe(float target[2], const float a[2], const float b[
}
}
+/** \name Cubic curve interpolation (bezier spline).
+ * \{ */
+
+void interp_v2_v2v2v2v2_cubic(
+ float p[2], const float v1[2], const float v2[2], const float v3[2], const float v4[2],
+ const float u)
+{
+ float q0[2], q1[2], q2[2], r0[2], r1[2];
+
+ interp_v2_v2v2(q0, v1, v2, u);
+ interp_v2_v2v2(q1, v2, v3, u);
+ interp_v2_v2v2(q2, v3, v4, u);
+
+ interp_v2_v2v2(r0, q0, q1, u);
+ interp_v2_v2v2(r1, q1, q2, u);
+
+ interp_v2_v2v2(p, r0, r1, u);
+}
+
+/** \} */
+
/* weight 3 vectors,
* 'w' must be unit length but is not a vector, just 3 weights */
void interp_v3_v3v3v3(float p[3], const float v1[3], const float v2[3], const float v3[3], const float w[3])
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index fd9f3d5ff99..e9fb77f6302 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -859,13 +859,13 @@ MINLINE float len_v3v3(const float a[3], const float b[3])
return len_v3(d);
}
-MINLINE float normalize_v2_v2(float r[2], const float a[2])
+MINLINE float normalize_v2_v2_length(float r[2], const float a[2], const float unit_length)
{
float d = dot_v2v2(a, a);
if (d > 1.0e-35f) {
d = sqrtf(d);
- mul_v2_v2fl(r, a, 1.0f / d);
+ mul_v2_v2fl(r, a, unit_length / d);
}
else {
zero_v2(r);
@@ -874,13 +874,22 @@ MINLINE float normalize_v2_v2(float r[2], const float a[2])
return d;
}
+MINLINE float normalize_v2_v2(float r[2], const float a[2])
+{
+ return normalize_v2_v2_length(r, a, 1.0f);
+}
MINLINE float normalize_v2(float n[2])
{
return normalize_v2_v2(n, n);
}
-MINLINE float normalize_v3_v3(float r[3], const float a[3])
+MINLINE float normalize_v2_length(float n[2], const float unit_length)
+{
+ return normalize_v2_v2_length(n, n, unit_length);
+}
+
+MINLINE float normalize_v3_v3_length(float r[3], const float a[3], const float unit_length)
{
float d = dot_v3v3(a, a);
@@ -888,7 +897,7 @@ MINLINE float normalize_v3_v3(float r[3], const float a[3])
* scaled down models with camera extreme close */
if (d > 1.0e-35f) {
d = sqrtf(d);
- mul_v3_v3fl(r, a, 1.0f / d);
+ mul_v3_v3fl(r, a, unit_length / d);
}
else {
zero_v3(r);
@@ -897,8 +906,12 @@ MINLINE float normalize_v3_v3(float r[3], const float a[3])
return d;
}
+MINLINE float normalize_v3_v3(float r[3], const float a[3])
+{
+ return normalize_v3_v3_length(r, a, 1.0f);
+}
-MINLINE double normalize_v3_d(double n[3])
+MINLINE double normalize_v3_length_d(double n[3], const double unit_length)
{
double d = n[0] * n[0] + n[1] * n[1] + n[2] * n[2];
@@ -908,7 +921,7 @@ MINLINE double normalize_v3_d(double n[3])
double mul;
d = sqrt(d);
- mul = 1.0 / d;
+ mul = unit_length / d;
n[0] *= mul;
n[1] *= mul;
@@ -921,6 +934,15 @@ MINLINE double normalize_v3_d(double n[3])
return d;
}
+MINLINE double normalize_v3_d(double n[3])
+{
+ return normalize_v3_length_d(n, 1.0);
+}
+
+MINLINE float normalize_v3_length(float n[3], const float unit_length)
+{
+ return normalize_v3_v3_length(n, n, unit_length);
+}
MINLINE float normalize_v3(float n[3])
{
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-29 04:52:46 +0300