Workbench: Shadows: Add frustum check and camera occlusion test.

If the object is manifold and the camera is in the shadow side, we can
use the depth fail method to fix the inverted shadow glitch.

Unfortunately this does not really work for non-manifold.

Implementation details:
We try to be as efficient as we can, we precompute camera near plane
projected into 2D shadow space so we can test for intersection with the
shadow boundbox easily.

As the intersection test is done in 2D it's pretty fast.
Unfortunately, this means the shadow bounds are all aligned to the same
space and are not the smallest bound we could extract.

source/blender/draw/engines/workbench/workbench_deferred.c

@@ -49,6 +49,10 @@
 
 // #define DEBUG_SHADOW_VOLUME
 
+#ifdef DEBUG_SHADOW_VOLUME
+#  include "draw_debug.h"
+#endif
+
 static struct {
 	struct GPUShader *prepass_sh_cache[MAX_SHADERS];
 	struct GPUShader *composite_sh_cache[MAX_SHADERS];
@@ -161,6 +165,7 @@ static void workbench_init_object_data(ObjectEngineData *engine_data)
 {
 	WORKBENCH_ObjectData *data = (WORKBENCH_ObjectData *)engine_data;
 	data->object_id = e_data.next_object_id++;
+	data->shadow_bbox_dirty = true;
 }
 
 void workbench_deferred_engine_init(WORKBENCH_Data *vedata)
@@ -369,6 +374,8 @@ void workbench_deferred_cache_init(WORKBENCH_Data *vedata)
 			DRW_shgroup_uniform_float(grp, "shadowShift", &scene->display.shadow_shift, 1);
 			DRW_shgroup_call_add(grp, DRW_cache_fullscreen_quad_get(), NULL);
 #endif
+
+			studiolight_update_light(wpd, e_data.display.light_direction);
 		}
 		else {
 			psl->composite_pass = DRW_pass_create(
@@ -542,44 +549,60 @@ void workbench_deferred_solid_cache_populate(WORKBENCH_Data *vedata, Object *ob)
 					WORKBENCH_ObjectData *engine_object_data = (WORKBENCH_ObjectData *)DRW_object_engine_data_ensure(
 					        ob, &draw_engine_workbench_solid, sizeof(WORKBENCH_ObjectData), &workbench_init_object_data, NULL);
 
-					invert_m4_m4(ob->imat, ob->obmat);
-					mul_v3_mat3_m4v3(engine_object_data->shadow_dir, ob->imat, e_data.display.light_direction);
+					if (studiolight_object_cast_visible_shadow(wpd, ob, engine_object_data)) {
 
-					DRWShadingGroup *grp;
-					/* TODO(fclem): only use shadow pass technique if camera is not in shadow. */
-					const bool use_shadow_pass_technique = true;
-					if (use_shadow_pass_technique) {
-						if (is_manifold) {
-							grp = DRW_shgroup_create(e_data.shadow_pass_manifold_sh, psl->shadow_depth_pass_mani_pass);
+						invert_m4_m4(ob->imat, ob->obmat);
+						mul_v3_mat3_m4v3(engine_object_data->shadow_dir, ob->imat, e_data.display.light_direction);
+
+						DRWShadingGroup *grp;
+						bool use_shadow_pass_technique = !studiolight_camera_in_object_shadow(wpd, ob, engine_object_data);
+
+						/* Unless we expose a parameter to the user, it's better to use the depth pass technique if the object is
+						 * non manifold. Exposing a switch to the user to force depth fail in this case can be beneficial for
+						 * planes and non-closed terrains. */
+						if (!is_manifold) {
+							use_shadow_pass_technique = true;
 						}
-						else {
-							grp = DRW_shgroup_create(e_data.shadow_pass_sh, psl->shadow_depth_pass_pass);
-						}
-						DRW_shgroup_uniform_vec3(grp, "lightDirection", engine_object_data->shadow_dir, 1);
-						DRW_shgroup_call_object_add(grp, geom_shadow, ob);
-					}
-					else {
-						/* TODO(fclem): only use caps if they are in the view frustum. */
-						const bool need_caps = true;
-						if (need_caps) {
+
+						if (use_shadow_pass_technique) {
 							if (is_manifold) {
-								grp = DRW_shgroup_create(e_data.shadow_caps_manifold_sh, psl->shadow_depth_fail_caps_mani_pass);
+								grp = DRW_shgroup_create(e_data.shadow_pass_manifold_sh, psl->shadow_depth_pass_mani_pass);
 							}
 							else {
-								grp = DRW_shgroup_create(e_data.shadow_caps_sh, psl->shadow_depth_fail_caps_pass);
+								grp = DRW_shgroup_create(e_data.shadow_pass_sh, psl->shadow_depth_pass_pass);
 							}
 							DRW_shgroup_uniform_vec3(grp, "lightDirection", engine_object_data->shadow_dir, 1);
-							DRW_shgroup_call_object_add(grp, DRW_cache_object_surface_get(ob), ob);
-						}
-
-						if (is_manifold) {
-							grp = DRW_shgroup_create(e_data.shadow_fail_manifold_sh, psl->shadow_depth_fail_mani_pass);
+							DRW_shgroup_call_add(grp, geom_shadow, ob->obmat);
+#ifdef DEBUG_SHADOW_VOLUME
+							DRW_debug_bbox(&engine_object_data->shadow_bbox, (float[4]){1.0f, 0.0f, 0.0f, 1.0f});
+#endif
 						}
 						else {
-							grp = DRW_shgroup_create(e_data.shadow_fail_sh, psl->shadow_depth_fail_pass);
+							/* TODO(fclem): only use caps if they are in the view frustum. */
+							const bool need_caps = true;
+							if (need_caps) {
+								if (is_manifold) {
+									grp = DRW_shgroup_create(e_data.shadow_caps_manifold_sh, psl->shadow_depth_fail_caps_mani_pass);
+								}
+								else {
+									grp = DRW_shgroup_create(e_data.shadow_caps_sh, psl->shadow_depth_fail_caps_pass);
+								}
+								DRW_shgroup_uniform_vec3(grp, "lightDirection", engine_object_data->shadow_dir, 1);
+								DRW_shgroup_call_add(grp, DRW_cache_object_surface_get(ob), ob->obmat);
+							}
+
+							if (is_manifold) {
+								grp = DRW_shgroup_create(e_data.shadow_fail_manifold_sh, psl->shadow_depth_fail_mani_pass);
+							}
+							else {
+								grp = DRW_shgroup_create(e_data.shadow_fail_sh, psl->shadow_depth_fail_pass);
+							}
+							DRW_shgroup_uniform_vec3(grp, "lightDirection", engine_object_data->shadow_dir, 1);
+							DRW_shgroup_call_add(grp, geom_shadow, ob->obmat);
+#ifdef DEBUG_SHADOW_VOLUME
+							DRW_debug_bbox(&engine_object_data->shadow_bbox, (float[4]){0.0f, 1.0f, 0.0f, 1.0f});
+#endif
 						}
-						DRW_shgroup_uniform_vec3(grp, "lightDirection", engine_object_data->shadow_dir, 1);
-						DRW_shgroup_call_object_add(grp, geom_shadow, ob);
 					}
 				}
 			}

source/blender/draw/engines/workbench/workbench_private.h

@@ -127,6 +127,14 @@ typedef struct WORKBENCH_PrivateData {
 #endif
 	WORKBENCH_UBO_World world_data;
 	float shadow_multiplier;
+	float cached_shadow_direction[3];
+	float shadow_mat[4][4];
+	float shadow_inv[4][4];
+	float shadow_near_corners[4][3]; /* Near plane corners in shadow space. */
+	float shadow_near_min[2]; /* min and max of shadow_near_corners. allow fast test */
+	float shadow_near_max[2];
+	float shadow_near_sides[2][4]; /* This is a parallelogram, so only 2 normal and distance to the edges. */
+	bool shadow_changed;
 } WORKBENCH_PrivateData; /* Transient data */
 
 typedef struct WORKBENCH_MaterialData {
@@ -151,6 +159,9 @@ typedef struct WORKBENCH_ObjectData {
 	int recalc;
 	/* Shadow direction in local object space. */
 	float shadow_dir[3];
+	float shadow_min[3], shadow_max[3]; /* Min, max in shadow space */
+	BoundBox shadow_bbox;
+	bool shadow_bbox_dirty;
 
 	int object_id;
 } WORKBENCH_ObjectData;
@@ -191,6 +202,9 @@ void workbench_material_set_normal_world_matrix(
 
 /* workbench_studiolight.c */
 void studiolight_update_world(StudioLight *sl, WORKBENCH_UBO_World *wd);
+void studiolight_update_light(WORKBENCH_PrivateData *wpd, const float light_direction[3]);
+bool studiolight_object_cast_visible_shadow(WORKBENCH_PrivateData *wpd, Object *ob, WORKBENCH_ObjectData *oed);
+bool studiolight_camera_in_object_shadow(WORKBENCH_PrivateData *wpd, Object *ob, WORKBENCH_ObjectData *oed);
 
 /* workbench_data.c */
 void workbench_private_data_init(WORKBENCH_PrivateData *wpd);

source/blender/draw/engines/workbench/workbench_studiolight.c

@@ -27,7 +27,10 @@
 #include "DRW_engine.h"
 #include "workbench_private.h"
 
+#include "BKE_object.h"
+
 #include "BLI_math.h"
+#include "BKE_global.h"
 
 void studiolight_update_world(StudioLight *sl, WORKBENCH_UBO_World *wd)
 {
@@ -40,3 +43,134 @@ void studiolight_update_world(StudioLight *sl, WORKBENCH_UBO_World *wd)
 	copy_v3_v3(wd->diffuse_light_z_pos, sl->diffuse_light[STUDIOLIGHT_Z_POS]);
 	copy_v3_v3(wd->diffuse_light_z_neg, sl->diffuse_light[STUDIOLIGHT_Z_NEG]);
 }
+
+static void compute_parallel_lines_nor_and_dist(const float v1[2], const float v2[2], const float v3[2], float r_line[2])
+{
+	sub_v2_v2v2(r_line, v2, v1);
+	/* Find orthogonal vector. */
+	SWAP(float, r_line[0], r_line[1]);
+	r_line[0] = -r_line[0];
+	/* Edge distances. */
+	r_line[2] = dot_v2v2(r_line, v1);
+	r_line[3] = dot_v2v2(r_line, v3);
+	/* Make sure r_line[2] is the minimum. */
+	if (r_line[2] > r_line[3]) {
+		SWAP(float, r_line[2], r_line[3]);
+	}
+}
+
+void studiolight_update_light(WORKBENCH_PrivateData *wpd, const float light_direction[3])
+{
+	wpd->shadow_changed = !compare_v3v3(wpd->cached_shadow_direction, light_direction, 1e-5f);
+
+	if (wpd->shadow_changed) {
+		float up[3] = {0.0f, 0.0f, 1.0f};
+		unit_m4(wpd->shadow_mat);
+
+		/* TODO fix singularity. */
+		copy_v3_v3(wpd->shadow_mat[2], light_direction);
+		cross_v3_v3v3(wpd->shadow_mat[0], wpd->shadow_mat[2], up);
+		normalize_v3(wpd->shadow_mat[0]);
+		cross_v3_v3v3(wpd->shadow_mat[1], wpd->shadow_mat[2], wpd->shadow_mat[0]);
+
+		invert_m4_m4(wpd->shadow_inv, wpd->shadow_mat);
+
+		copy_v3_v3(wpd->cached_shadow_direction, light_direction);
+
+	}
+
+	BoundBox frustum_corners;
+	DRW_culling_frustum_corners_get(&frustum_corners);
+
+	mul_v3_mat3_m4v3(wpd->shadow_near_corners[0], wpd->shadow_inv, frustum_corners.vec[0]);
+	mul_v3_mat3_m4v3(wpd->shadow_near_corners[1], wpd->shadow_inv, frustum_corners.vec[3]);
+	mul_v3_mat3_m4v3(wpd->shadow_near_corners[2], wpd->shadow_inv, frustum_corners.vec[7]);
+	mul_v3_mat3_m4v3(wpd->shadow_near_corners[3], wpd->shadow_inv, frustum_corners.vec[4]);
+
+	INIT_MINMAX2(wpd->shadow_near_min, wpd->shadow_near_max);
+	for (int i = 0; i < 4; ++i) {
+		minmax_v2v2_v2(wpd->shadow_near_min, wpd->shadow_near_max, wpd->shadow_near_corners[i]);
+	}
+
+	compute_parallel_lines_nor_and_dist(wpd->shadow_near_corners[0], wpd->shadow_near_corners[1], wpd->shadow_near_corners[2], wpd->shadow_near_sides[0]);
+	compute_parallel_lines_nor_and_dist(wpd->shadow_near_corners[1], wpd->shadow_near_corners[2], wpd->shadow_near_corners[0], wpd->shadow_near_sides[1]);
+}
+
+static BoundBox *studiolight_object_shadow_bbox_get(WORKBENCH_PrivateData *wpd, Object *ob, WORKBENCH_ObjectData *oed)
+{
+	if ((oed->shadow_bbox_dirty) || (wpd->shadow_changed)) {
+		float tmp_mat[4][4];
+		mul_m4_m4m4(tmp_mat, wpd->shadow_inv, ob->obmat);
+
+		/* Get AABB in shadow space. */
+		INIT_MINMAX(oed->shadow_min, oed->shadow_max);
+
+		/* From object space to shadow space */
+		BoundBox *bbox = BKE_object_boundbox_get(ob);
+		for (int i = 0; i < 8; ++i) {
+			float corner[3];
+			mul_v3_m4v3(corner, tmp_mat, bbox->vec[i]);
+			minmax_v3v3_v3(oed->shadow_min, oed->shadow_max, corner);
+		}
+		/* Extend towards infinity. */
+		oed->shadow_max[2] += 1e4;
+
+		/* Get extended AABB in world space. */
+		BKE_boundbox_init_from_minmax(&oed->shadow_bbox, oed->shadow_min, oed->shadow_max);
+		for (int i = 0; i < 8; ++i) {
+			mul_m4_v3(wpd->shadow_mat, oed->shadow_bbox.vec[i]);
+		}
+	}
+
+	return &oed->shadow_bbox;
+}
+
+bool studiolight_object_cast_visible_shadow(WORKBENCH_PrivateData *wpd, Object *ob, WORKBENCH_ObjectData *oed)
+{
+	BoundBox *shadow_bbox = studiolight_object_shadow_bbox_get(wpd, ob, oed);
+	return DRW_culling_box_test(shadow_bbox);
+}
+
+bool studiolight_camera_in_object_shadow(WORKBENCH_PrivateData *wpd, Object *ob, WORKBENCH_ObjectData *oed)
+{
+	/* Just to be sure the min, max are updated. */
+	studiolight_object_shadow_bbox_get(wpd, ob, oed);
+
+	/* Separation Axis Theorem test */
+
+	/* Test bbox sides first (faster) */
+	if ((oed->shadow_min[0] > wpd->shadow_near_max[0]) ||
+	    (oed->shadow_max[0] < wpd->shadow_near_min[0]) ||
+	    (oed->shadow_min[1] > wpd->shadow_near_max[1]) ||
+	    (oed->shadow_max[1] < wpd->shadow_near_min[1]))
+	{
+		return false;
+	}
+
+	/* Test projected near rectangle sides */
+	float pts[4][2] = {
+	        {oed->shadow_min[0], oed->shadow_min[1]},
+	        {oed->shadow_min[0], oed->shadow_max[1]},
+	        {oed->shadow_max[0], oed->shadow_min[1]},
+	        {oed->shadow_max[0], oed->shadow_max[1]}
+	};
+
+	for (int i = 0; i < 2; ++i) {
+		float min_dst, max_dst;
+		for (int j = 0; j < 4; ++j) {
+			float dst = dot_v2v2(wpd->shadow_near_sides[i], pts[j]);
+			/* Do min max */
+			if (min_dst > dst) min_dst = dst;
+			if (max_dst < dst) max_dst = dst;
+		}
+
+		if ((wpd->shadow_near_sides[i][2] > max_dst) ||
+		    (wpd->shadow_near_sides[i][3] < min_dst))
+		{
+			return false;
+		}
+	}
+
+	/* No separation axis found. Both shape intersect. */
+	return true;
+}

source/blender/draw/intern/DRW_render.h

@@ -497,6 +497,8 @@ bool DRW_culling_sphere_test(BoundSphere *bsphere);
 bool DRW_culling_box_test(BoundBox *bbox);
 bool DRW_culling_plane_test(float plane[4]);
 
+void DRW_culling_frustum_corners_get(BoundBox *corners);
+
 /* Selection */
 void DRW_select_load_id(uint id);
 

source/blender/draw/intern/draw_manager_exec.c

@@ -707,6 +707,12 @@ bool DRW_culling_plane_test(float plane[4])
 	return false;
 }
 
+void DRW_culling_frustum_corners_get(BoundBox *corners)
+{
+	draw_clipping_setup_from_view();
+	memcpy(corners, &DST.clipping.frustum_corners, sizeof(BoundBox));
+}
+
 /** \} */
 
 /* -------------------------------------------------------------------- */