[Bf-blender-cvs] [6202bc82b85] master: Fix T60935: More numerically stable distance to ray computation

Jacques Lucke noreply at git.blender.org
Wed Feb 6 11:52:13 CET 2019


Commit: 6202bc82b858d8f6876c6c20ec62dd0a16209087
Author: Jacques Lucke
Date:   Wed Feb 6 11:47:46 2019 +0100
Branches: master
https://developer.blender.org/rB6202bc82b858d8f6876c6c20ec62dd0a16209087

Fix T60935: More numerically stable distance to ray computation

The old function was numerically very unstable for 2 reasons:
computing the square and then subtracting the results.

In the example in T60935 all precision was lost and it returned the distance 0
for all points.

I also removed the `depth` parameter since it wasn't used and computing
it would have made the code more complicated.

Reviewers: brecht, campbellbarton

Differential Revision: https://developer.blender.org/D4308

===================================================================

M	source/blender/blenlib/BLI_math_geom.h
M	source/blender/blenlib/intern/math_geom.c
M	source/blender/editors/mesh/editmesh_select.c

===================================================================

diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index a564e5481b9..54a4a38b15e 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -109,9 +109,9 @@ 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(
+float dist_squared_to_ray_v3_normalized(
         const float ray_origin[3], const float ray_direction[3],
-        const float co[3], float *r_depth);
+        const float co[3]);
 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],
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 91de4005f48..aebff346432 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -553,16 +553,25 @@ float dist_signed_squared_to_corner_v3v3v3(
 }
 
 /**
- * return the distance squared of a point to a ray.
+ * Compute the squared distance of a point to a line (defined as ray).
+ * \param ray_origin: A point on the line.
+ * \param ray_direction: Normalized direction of the line.
+ * \param co: Point to which the distance is to be calculated.
  */
-float dist_squared_to_ray_v3(
+float dist_squared_to_ray_v3_normalized(
         const float ray_origin[3], const float ray_direction[3],
-        const float co[3], float *r_depth)
+        const float co[3])
 {
-	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);
+	float origin_to_co[3];
+	sub_v3_v3v3(origin_to_co, co, ray_origin);
+
+	float origin_to_proj[3];
+	project_v3_v3v3_normalized(origin_to_proj, origin_to_co, ray_direction);
+
+	float co_projected_on_ray[3];
+	add_v3_v3v3(co_projected_on_ray, ray_origin, origin_to_proj);
+
+	return len_squared_v3v3(co, co_projected_on_ray);
 }
 
 
diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c
index d09f3ba6f64..fd9e635f5e3 100644
--- a/source/blender/editors/mesh/editmesh_select.c
+++ b/source/blender/editors/mesh/editmesh_select.c
@@ -1153,16 +1153,13 @@ bool EDBM_unified_findnearest_from_raycast(
 					if ((BM_elem_flag_test(e, BM_ELEM_HIDDEN) == false) &&
 					    (BM_edge_is_boundary(e)))
 					{
-						float depth;
-
 						if (use_vert) {
 							for (uint j = 0; j < 2; j++) {
 								BMVert *v = *((&e->v1) + j);
 								float point[3];
 								mul_v3_m4v3(point, obedit->obmat, coords ? coords[BM_elem_index_get(v)] : v->co);
-								const float dist_sq_test = dist_squared_to_ray_v3(
-								        ray_origin, ray_direction,
-								        point, &depth);
+								const float dist_sq_test = dist_squared_to_ray_v3_normalized(
+								        ray_origin, ray_direction, point);
 								if (dist_sq_test < dist_sq_best) {
 									dist_sq_best = dist_sq_test;
 									best.base_index = base_index;
@@ -1186,9 +1183,8 @@ bool EDBM_unified_findnearest_from_raycast(
 								mid_v3_v3v3(point, e->v1->co, e->v2->co);
 							}
 							mul_m4_v3(obedit->obmat, point);
-							const float dist_sq_test = dist_squared_to_ray_v3(
-							        ray_origin, ray_direction,
-							        point, &depth);
+							const float dist_sq_test = dist_squared_to_ray_v3_normalized(
+							        ray_origin, ray_direction, point);
 							if (dist_sq_test < dist_sq_best) {
 								dist_sq_best = dist_sq_test;
 								best.base_index = base_index;
@@ -1208,10 +1204,8 @@ bool EDBM_unified_findnearest_from_raycast(
 						if (BM_elem_flag_test(v, BM_ELEM_HIDDEN) == false) {
 							float point[3];
 							mul_v3_m4v3(point, obedit->obmat, v->co);
-							float depth;
-							const float dist_sq_test = dist_squared_to_ray_v3(
-							        ray_origin, ray_direction,
-							        v->co, &depth);
+							const float dist_sq_test = dist_squared_to_ray_v3_normalized(
+							        ray_origin, ray_direction, v->co);
 							if (dist_sq_test < dist_sq_best) {
 								dist_sq_best = dist_sq_test;
 								best.base_index = base_index;
@@ -1233,10 +1227,8 @@ bool EDBM_unified_findnearest_from_raycast(
 								mid_v3_v3v3(point, e->v1->co, e->v2->co);
 							}
 							mul_m4_v3(obedit->obmat, point);
-							float depth;
-							const float dist_sq_test = dist_squared_to_ray_v3(
-							        ray_origin, ray_direction,
-							        point, &depth);
+							const float dist_sq_test = dist_squared_to_ray_v3_normalized(
+							        ray_origin, ray_direction, point);
 							if (dist_sq_test < dist_sq_best) {
 								dist_sq_best = dist_sq_test;
 								best.base_index = base_index;
@@ -1260,10 +1252,8 @@ bool EDBM_unified_findnearest_from_raycast(
 							BM_face_calc_center_median(f, point);
 						}
 						mul_m4_v3(obedit->obmat, point);
-						float depth;
-						const float dist_sq_test = dist_squared_to_ray_v3(
-						        ray_origin, ray_direction,
-						        point, &depth);
+						const float dist_sq_test = dist_squared_to_ray_v3_normalized(
+						        ray_origin, ray_direction, point);
 						if (dist_sq_test < dist_sq_best) {
 							dist_sq_best = dist_sq_test;
 							best.base_index = base_index;



More information about the Bf-blender-cvs mailing list