BVH-raycast: Use watertight intersections

By default watertight intersections are used,
For callbacks where its not needed,
BLI_bvhtree_ray_cast_ex can be called without the BVH_RAYCAST_WATERTIGHT flag.

Fixes T45286

8 files changed, 121 insertions, 29 deletions

diff --git a/source/blender/blenkernel/intern/boids.c b/source/blender/blenkernel/intern/boids.c
index fdc5524e84c..489e26c5cbe 100644
--- a/source/blender/blenkernel/intern/boids.c
+++ b/source/blender/blenkernel/intern/boids.c
@@ -189,6 +189,7 @@ static int rule_goal_avoid(BoidRule *rule, BoidBrainData *bbd, BoidValues *val,
 
 static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues *val, ParticleData *pa)
 {
+	const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT);
 	BoidRuleAvoidCollision *acbr = (BoidRuleAvoidCollision*) rule;
 	KDTreeNearest *ptn = NULL;
 	ParticleTarget *pt;
@@ -225,8 +226,11 @@ static int rule_avoid_collision(BoidRule *rule, BoidBrainData *bbd, BoidValues *
 			col.current = coll->ob;
 			col.md = coll->collmd;
 
-			if (col.md && col.md->bvhtree)
-				BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, BKE_psys_collision_neartest_cb, &col);
+			if (col.md && col.md->bvhtree) {
+				BLI_bvhtree_ray_cast_ex(
+				        col.md->bvhtree, col.co1, ray_dir, radius, &hit,
+				        BKE_psys_collision_neartest_cb, &col, raycast_flag);
+			}
 		}
 		/* then avoid that object */
 		if (hit.index>=0) {
@@ -759,6 +763,7 @@ static void set_boid_values(BoidValues *val, BoidSettings *boids, ParticleData *
 
 static Object *boid_find_ground(BoidBrainData *bbd, ParticleData *pa, float ground_co[3], float ground_nor[3])
 {
+	const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT);
 	BoidParticle *bpa = pa->boid;
 
 	if (bpa->data.mode == eBoidMode_Climbing) {
@@ -802,8 +807,11 @@ static Object *boid_find_ground(BoidBrainData *bbd, ParticleData *pa, float grou
 			col.md = coll->collmd;
 			col.fac1 = col.fac2 = 0.f;
 
-			if (col.md && col.md->bvhtree)
-				BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, BKE_psys_collision_neartest_cb, &col);
+			if (col.md && col.md->bvhtree) {
+				BLI_bvhtree_ray_cast_ex(
+				        col.md->bvhtree, col.co1, ray_dir, radius, &hit,
+				        BKE_psys_collision_neartest_cb, &col, raycast_flag);
+			}
 		}
 		/* then use that object */
 		if (hit.index>=0) {
@@ -826,8 +834,11 @@ static Object *boid_find_ground(BoidBrainData *bbd, ParticleData *pa, float grou
 			col.current = coll->ob;
 			col.md = coll->collmd;
 
-			if (col.md && col.md->bvhtree)
-				BLI_bvhtree_ray_cast(col.md->bvhtree, col.co1, ray_dir, radius, &hit, BKE_psys_collision_neartest_cb, &col);
+			if (col.md && col.md->bvhtree) {
+				BLI_bvhtree_ray_cast_ex(
+				        col.md->bvhtree, col.co1, ray_dir, radius, &hit,
+				        BKE_psys_collision_neartest_cb, &col, raycast_flag);
+			}
 		}
 		/* then use that object */
 		if (hit.index>=0) {
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index 2ecae21d494..fa2fcd97ec3 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -60,8 +60,14 @@ float bvhtree_ray_tri_intersection(
 {
 	float dist;
 
+#ifdef USE_KDOPBVH_WATERTIGHT
+	if (isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc, v0, v1, v2, &dist, NULL))
+#else
 	if (isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
+#endif
+	{
 		return dist;
+	}
 
 	return FLT_MAX;
 }
diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c
index 0e619f28622..07706a38deb 100644
--- a/source/blender/blenkernel/intern/editmesh_bvh.c
+++ b/source/blender/blenkernel/intern/editmesh_bvh.c
@@ -278,8 +278,13 @@ static void bmbvh_ray_cast_cb(void *userdata, int index, const BVHTreeRay *ray,
 	isect = (ray->radius > 0.0f ?
 	         isect_ray_tri_epsilon_v3(ray->origin, ray->direction,
 	                                  tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv, ray->radius) :
+#ifdef USE_KDOPBVH_WATERTIGHT
+	         isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc,
+	                                     tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
+#else
 	         isect_ray_tri_v3(ray->origin, ray->direction,
 	                          tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
+#endif
 
 	if (isect && dist < hit->dist) {
 		hit->dist = dist;
diff --git a/source/blender/blenkernel/intern/effect.c b/source/blender/blenkernel/intern/effect.c
index 6459e2ee7e6..bf53acc1d95 100644
--- a/source/blender/blenkernel/intern/effect.c
+++ b/source/blender/blenkernel/intern/effect.c
@@ -391,6 +391,7 @@ static void eff_tri_ray_hit(void *UNUSED(userData), int UNUSED(index), const BVH
 // get visibility of a wind ray
 static float eff_calc_visibility(ListBase *colliders, EffectorCache *eff, EffectorData *efd, EffectedPoint *point)
 {
+	const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT);
 	ListBase *colls = colliders;
 	ColliderCache *col;
 	float norm[3], len = 0.0;
@@ -422,7 +423,10 @@ static float eff_calc_visibility(ListBase *colliders, EffectorCache *eff, Effect
 			hit.dist = len + FLT_EPSILON;
 
 			/* check if the way is blocked */
-			if (BLI_bvhtree_ray_cast(collmd->bvhtree, point->loc, norm, 0.0f, &hit, eff_tri_ray_hit, NULL)>=0) {
+			if (BLI_bvhtree_ray_cast_ex(
+			        collmd->bvhtree, point->loc, norm, 0.0f, &hit,
+			        eff_tri_ray_hit, NULL, raycast_flag) != -1)
+			{
 				absorption= col->ob->pd->absorption;
 
 				/* visibility is only between 0 and 1, calculated from 1-absorption */
diff --git a/source/blender/blenkernel/intern/particle_system.c b/source/blender/blenkernel/intern/particle_system.c
index 8b925fff415..dd43e63b9c3 100644
--- a/source/blender/blenkernel/intern/particle_system.c
+++ b/source/blender/blenkernel/intern/particle_system.c
@@ -2586,6 +2586,7 @@ void BKE_psys_collision_neartest_cb(void *userdata, int index, const BVHTreeRay
 }
 static int collision_detect(ParticleData *pa, ParticleCollision *col, BVHTreeRayHit *hit, ListBase *colliders)
 {
+	const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT);
 	ColliderCache *coll;
 	float ray_dir[3];
 
@@ -2616,8 +2617,11 @@ static int collision_detect(ParticleData *pa, ParticleCollision *col, BVHTreeRay
 		col->fac1 = (col->old_cfra - coll->collmd->time_x) / (coll->collmd->time_xnew - coll->collmd->time_x);
 		col->fac2 = (col->cfra - coll->collmd->time_x) / (coll->collmd->time_xnew - coll->collmd->time_x);
 
-		if (col->md && col->md->bvhtree)
-			BLI_bvhtree_ray_cast(col->md->bvhtree, col->co1, ray_dir, col->radius, hit, BKE_psys_collision_neartest_cb, col);
+		if (col->md && col->md->bvhtree) {
+			BLI_bvhtree_ray_cast_ex(
+			        col->md->bvhtree, col->co1, ray_dir, col->radius, hit,
+			        BKE_psys_collision_neartest_cb, col, raycast_flag);
+		}
 	}
 
 	return hit->index >= 0;
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index ce7f3ab25fe..0c359c7f090 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -41,6 +41,7 @@ extern "C" {
 
 struct BVHTree;
 typedef struct BVHTree BVHTree;
+#define USE_KDOPBVH_WATERTIGHT
 
 typedef struct BVHTreeOverlap {
 	int indexA;
@@ -59,6 +60,9 @@ typedef struct BVHTreeRay {
 	float origin[3];    /* ray origin */
 	float direction[3]; /* ray direction */
 	float radius;       /* radius around ray */
+#ifdef USE_KDOPBVH_WATERTIGHT
+	struct IsectRayPrecalc *isect_precalc;
+#endif
 } BVHTreeRay;
 
 typedef struct BVHTreeRayHit {
@@ -68,6 +72,12 @@ typedef struct BVHTreeRayHit {
 	float dist;         /* distance to the hit point */
 } BVHTreeRayHit;
 
+enum {
+	/* calculate IsectRayPrecalc data */
+	BVH_RAYCAST_WATERTIGHT		= (1 << 0),
+};
+#define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT)
+
 /* callback must update nearest in case it finds a nearest result */
 typedef void (*BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest);
 
@@ -105,12 +115,21 @@ float BLI_bvhtree_getepsilon(const BVHTree *tree);
 int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest,
                              BVHTree_NearestPointCallback callback, void *userdata);
 
-int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
-                         BVHTree_RayCastCallback callback, void *userdata);
-
-/* Calls the callback for every ray intersection */
-int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius,
-                             BVHTree_RayCastCallback callback, void *userdata);
+int BLI_bvhtree_ray_cast_ex(
+        BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
+        BVHTree_RayCastCallback callback, void *userdata,
+        int flag);
+int BLI_bvhtree_ray_cast(
+        BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
+        BVHTree_RayCastCallback callback, void *userdata);
+
+int BLI_bvhtree_ray_cast_all_ex(
+        BVHTree *tree, const float co[3], const float dir[3], float radius,
+        BVHTree_RayCastCallback callback, void *userdata,
+        int flag);
+int BLI_bvhtree_ray_cast_all(
+        BVHTree *tree, const float co[3], const float dir[3], float radius,
+        BVHTree_RayCastCallback callback, void *userdata);
 
 float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3]);
 
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 1b9b6e38208..ddb61e415ac 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -139,6 +139,10 @@ typedef struct BVHRayCastData {
 
 	BVHTreeRay ray;
 
+#ifdef USE_KDOPBVH_WATERTIGHT
+	struct IsectRayPrecalc isect_precalc;
+#endif
+
 	/* initialized by bvhtree_ray_cast_data_precalc */
 	float ray_dot_axis[13];
 	float idot_axis[13];
@@ -1626,7 +1630,7 @@ static void iterative_raycast(BVHRayCastData *data, BVHNode *node)
 }
 #endif
 
-static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data)
+static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data, int flag)
 {
 	int i;
 
@@ -1642,10 +1646,24 @@ static void bvhtree_ray_cast_data_precalc(BVHRayCastData *data)
 		data->index[2 * i]   += 2 * i;
 		data->index[2 * i + 1] += 2 * i;
 	}
+
+#ifdef USE_KDOPBVH_WATERTIGHT
+	if (flag & BVH_RAYCAST_WATERTIGHT) {
+		isect_ray_tri_watertight_v3_precalc(&data->isect_precalc, data->ray.direction);
+		data->ray.isect_precalc = &data->isect_precalc;
+	}
+	else {
+		data->ray.isect_precalc = NULL;
+	}
+#else
+	UNUSED_VARS(flag);
+#endif
 }
 
-int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
-                         BVHTree_RayCastCallback callback, void *userdata)
+int BLI_bvhtree_ray_cast_ex(
+        BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
+        BVHTree_RayCastCallback callback, void *userdata,
+        int flag)
 {
 	BVHRayCastData data;
 	BVHNode *root = tree->nodes[tree->totleaf];
@@ -1661,10 +1679,11 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], f
 	copy_v3_v3(data.ray.direction, dir);
 	data.ray.radius = radius;
 
-	bvhtree_ray_cast_data_precalc(&data);
+	bvhtree_ray_cast_data_precalc(&data, flag);
 
-	if (hit)
+	if (hit) {
 		memcpy(&data.hit, hit, sizeof(*hit));
+	}
 	else {
 		data.hit.index = -1;
 		data.hit.dist = FLT_MAX;
@@ -1682,6 +1701,13 @@ int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], f
 	return data.hit.index;
 }
 
+int BLI_bvhtree_ray_cast(
+        BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
+        BVHTree_RayCastCallback callback, void *userdata)
+{
+	return BLI_bvhtree_ray_cast_ex(tree, co, dir, radius, hit, callback, userdata, BVH_RAYCAST_DEFAULT);
+}
+
 float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
 {
 	BVHRayCastData data;
@@ -1707,8 +1733,13 @@ float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], cons
 	
 }
 
-int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius,
-                             BVHTree_RayCastCallback callback, void *userdata)
+/**
+ * Calls the callback for every ray intersection
+ */
+int BLI_bvhtree_ray_cast_all_ex(
+        BVHTree *tree, const float co[3], const float dir[3], float radius,
+        BVHTree_RayCastCallback callback, void *userdata,
+        int flag)
 {
 	BVHRayCastData data;
 	BVHNode *root = tree->nodes[tree->totleaf];
@@ -1724,7 +1755,7 @@ int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3
 	copy_v3_v3(data.ray.direction, dir);
 	data.ray.radius = radius;
 
-	bvhtree_ray_cast_data_precalc(&data);
+	bvhtree_ray_cast_data_precalc(&data, flag);
 
 	data.hit.index = -1;
 	data.hit.dist = FLT_MAX;
@@ -1736,6 +1767,13 @@ int BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3
 	return data.hit.index;
 }
 
+int BLI_bvhtree_ray_cast_all(
+        BVHTree *tree, const float co[3], const float dir[3], float radius,
+        BVHTree_RayCastCallback callback, void *userdata)
+{
+	return BLI_bvhtree_ray_cast_all_ex(tree, co, dir, radius, callback, userdata, BVH_RAYCAST_DEFAULT);
+}
+
 /**
  * Range Query - as request by broken :P
  *
diff --git a/source/blender/editors/armature/meshlaplacian.c b/source/blender/editors/armature/meshlaplacian.c
index d49deae6aac..b8dc4e1e7ab 100644
--- a/source/blender/editors/armature/meshlaplacian.c
+++ b/source/blender/editors/armature/meshlaplacian.c
@@ -379,27 +379,32 @@ typedef struct BVHCallbackUserData {
 	LaplacianSystem *sys;
 } BVHCallbackUserData;
 
-static void bvh_callback(void *userdata, int index, const BVHTreeRay *UNUSED(ray), BVHTreeRayHit *hit)
+static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
 {
 	BVHCallbackUserData *data = (struct BVHCallbackUserData *)userdata;
 	const MLoopTri *lt = &data->sys->heat.mlooptri[index];
 	const MLoop *mloop = data->sys->heat.mloop;
 	float (*verts)[3] = data->sys->heat.verts;
 	const float *vtri_co[3];
-	float lambda, dir[3];
+	float dist_test;
 
-	mul_v3_v3fl(dir, data->vec, hit->dist);
 	vtri_co[0] = verts[mloop[lt->tri[0]].v];
 	vtri_co[1] = verts[mloop[lt->tri[1]].v];
 	vtri_co[2] = verts[mloop[lt->tri[2]].v];
 
-	if (isect_ray_tri_v3(data->start, dir, UNPACK3(vtri_co), &lambda, NULL)) {
-		if (lambda < 1.0f) {
+#ifdef USE_KDOPBVH_WATERTIGHT
+	if (isect_ray_tri_watertight_v3(data->start, ray->isect_precalc, UNPACK3(vtri_co), &dist_test, NULL))
+#else
+	UNUSED_VARS(ray);
+	if (isect_ray_tri_v3(data->start, data->vec, UNPACK3(vtri_co), &dist_test, NULL))
+#endif
+	{
+		if (dist_test < hit->dist) {
 			float n[3];
 			normal_tri_v3(n, UNPACK3(vtri_co));
 			if (dot_v3v3(n, data->vec) < -1e-5f) {
 				hit->index = index;
-				hit->dist *= lambda;
+				hit->dist = dist_test;
 			}
 		}
 	}