Workbench: Optimize Shadows.

This makes the shadows ~10 times faster in the general case.

This only create extrusion geometry on the outline edges. Also we increment
or decrement the stencil buffer by 2 for each manifold edge and only by 1
for non manifold. This make the algorithm robust yet less heavy than creating
one prism for each triangles.

7 files changed, 218 insertions, 53 deletions

diff --git a/source/blender/draw/engines/workbench/shaders/workbench_shadow_geom.glsl b/source/blender/draw/engines/workbench/shaders/workbench_shadow_geom.glsl
index 854cbee571d..a6cadfcfc54 100644
--- a/source/blender/draw/engines/workbench/shaders/workbench_shadow_geom.glsl
+++ b/source/blender/draw/engines/workbench/shaders/workbench_shadow_geom.glsl
@@ -1,51 +1,53 @@
-layout(triangles) in;
-layout(triangle_strip, max_vertices=9) out;
+layout(lines_adjacency) in;
+layout(triangle_strip, max_vertices = 8) out;
 
-uniform mat4 ModelMatrix;
-uniform mat4 ModelViewProjectionMatrix;
+uniform mat4 ModelMatrixInverse;
 
 uniform vec3 lightDirection = vec3(0.57, 0.57, -0.57);
 
 in VertexData {
-	flat vec4 lightDirectionMS;
-	vec4 frontPosition;
+	vec3 pos;           /* local position */
+	vec4 frontPosition; /* final ndc position */
 	vec4 backPosition;
-} vertexData[];
+} vData[];
 
-vec3 face_normal(vec3 v1, vec3 v2, vec3 v3) {
-	return normalize(cross(v2 - v1, v3 - v1));
-}
 void main()
 {
-	vec4 light_direction = vertexData[0].lightDirectionMS;
-	vec4 v1 = gl_in[0].gl_Position;
-	vec4 v2 = gl_in[1].gl_Position;
-	vec4 v3 = gl_in[2].gl_Position;
-	bool backface = dot(face_normal(v1.xyz, v2.xyz, v3.xyz), light_direction.xyz) > 0.0;
-
-	int index0 = backface?0:2;
-	int index2 = backface?2:0;
-
-	/* back cap */
-	gl_Position = vertexData[index0].backPosition;
-	EmitVertex();
-	gl_Position = vertexData[1].backPosition;
-	EmitVertex();
-	gl_Position = vertexData[index2].backPosition;
-	EmitVertex();
-
-	/* sides */
-	gl_Position = vertexData[index2].frontPosition;
-	EmitVertex();
-	gl_Position = vertexData[index0].backPosition;
-	EmitVertex();
-	gl_Position = vertexData[index0].frontPosition;
-	EmitVertex();
-	gl_Position = vertexData[1].backPosition;
-	EmitVertex();
-	gl_Position = vertexData[1].frontPosition;
-	EmitVertex();
-	gl_Position = vertexData[index2].frontPosition;
-	EmitVertex();
+	/* TODO precompute light_direction */
+	vec3 light_dir = mat3(ModelMatrixInverse) * lightDirection;
+
+	vec3 v10 = vData[0].pos - vData[1].pos;
+	vec3 v12 = vData[2].pos - vData[1].pos;
+	vec3 v13 = vData[3].pos - vData[1].pos;
+	vec3 n1 = cross(v12, v10);
+	vec3 n2 = cross(v13, v12);
+	vec2 facing = vec2(dot(n1, light_dir),
+	                   dot(n2, light_dir));
+	bvec2 backface = greaterThan(facing, vec2(0.0));
+
+	if (backface.x == backface.y) {
+		/* Both faces face the same direction. Not an outline edge. */
+		return;
+	}
+
+	/* Reverse order if backfacing the light. */
+	ivec2 idx = ivec2(1, 2);
+	idx = (backface.x) ? idx.yx : idx.xy;
+
+	/* WATCH: maybe unpredictable in some cases. */
+	bool is_manifold = any(notEqual(vData[0].pos, vData[3].pos));
+
+	gl_Position = vData[idx.x].frontPosition; EmitVertex();
+	gl_Position = vData[idx.y].frontPosition; EmitVertex();
+	gl_Position = vData[idx.x].backPosition; EmitVertex();
+	gl_Position = vData[idx.y].backPosition; EmitVertex();
 	EndPrimitive();
+
+	if (is_manifold) {
+		gl_Position = vData[idx.x].frontPosition; EmitVertex();
+		gl_Position = vData[idx.y].frontPosition; EmitVertex();
+		gl_Position = vData[idx.x].backPosition; EmitVertex();
+		gl_Position = vData[idx.y].backPosition; EmitVertex();
+		EndPrimitive();
+	}
 }
diff --git a/source/blender/draw/engines/workbench/shaders/workbench_shadow_vert.glsl b/source/blender/draw/engines/workbench/shaders/workbench_shadow_vert.glsl
index 8ef1a8b589b..8f02ce26626 100644
--- a/source/blender/draw/engines/workbench/shaders/workbench_shadow_vert.glsl
+++ b/source/blender/draw/engines/workbench/shaders/workbench_shadow_vert.glsl
@@ -1,23 +1,24 @@
 #define EPSILON 0.0001
-#define INFINITE 100.0
+#define INFINITE 10000.0
 
 uniform mat4 ModelMatrixInverse;
 uniform mat4 ModelViewProjectionMatrix;
+uniform mat4 ViewProjectionMatrix;
 uniform vec3 lightDirection = vec3(0.57, 0.57, -0.57);
 
-in vec4 pos;
+in vec3 pos;
 
 out VertexData {
-	flat vec4 lightDirectionMS;
-	vec4 frontPosition;
+	vec3 pos;           /* local position */
+	vec4 frontPosition; /* final ndc position */
 	vec4 backPosition;
-} vertexData;
+} vData;
 
 void main()
 {
-	gl_Position = pos;
-	vertexData.lightDirectionMS = normalize(ModelMatrixInverse * vec4(lightDirection, 0.0));
-	vertexData.lightDirectionMS.w = 0.0;
-	vertexData.frontPosition = ModelViewProjectionMatrix * (pos + vertexData.lightDirectionMS * EPSILON);
-	vertexData.backPosition = ModelViewProjectionMatrix * (pos + vertexData.lightDirectionMS * INFINITE);
+	/* TODO precompute light_direction */
+	vec3 light_direction = mat3(ModelMatrixInverse) * lightDirection;
+	vData.pos = pos;
+	vData.frontPosition = ModelViewProjectionMatrix * vec4(pos, 1.0);
+	vData.backPosition  = ModelViewProjectionMatrix * vec4(pos + light_direction * INFINITE, 1.0);
 }
diff --git a/source/blender/draw/engines/workbench/workbench_materials.c b/source/blender/draw/engines/workbench/workbench_materials.c
index 1dcc8d0ec6d..944572729c1 100644
--- a/source/blender/draw/engines/workbench/workbench_materials.c
+++ b/source/blender/draw/engines/workbench/workbench_materials.c
@@ -620,10 +620,13 @@ void workbench_materials_solid_cache_populate(WORKBENCH_Data *vedata, Object *ob
 		}
 
 		if (SHADOW_ENABLED(wpd) && (ob->display.flag & OB_SHOW_SHADOW) > 0) {
-			struct Gwn_Batch *geom_shadow = DRW_cache_object_surface_get(ob);
+			struct Gwn_Batch *geom_shadow = DRW_cache_object_edge_detection_get(ob);
 			if (geom_shadow) {
 				if (is_sculpt_mode) {
-					DRW_shgroup_call_sculpt_add(wpd->shadow_shgrp, ob, ob->obmat);
+					/* Currently unsupported in sculpt mode. We could revert to the slow
+					 * method in this case but i'm not sure if it's a good idea given that
+					 * sculped meshes are heavy to begin with. */
+					// DRW_shgroup_call_sculpt_add(wpd->shadow_shgrp, ob, ob->obmat);
 				}
 				else {
 					DRW_shgroup_call_object_add(wpd->shadow_shgrp, geom_shadow, ob);
diff --git a/source/blender/draw/intern/draw_cache.c b/source/blender/draw/intern/draw_cache.c
index 96a6a616072..3197ba799be 100644
--- a/source/blender/draw/intern/draw_cache.c
+++ b/source/blender/draw/intern/draw_cache.c
@@ -501,6 +501,19 @@ Gwn_Batch *DRW_cache_object_wire_outline_get(Object *ob)
 	}
 }
 
+/* Returns a buffer texture. */
+Gwn_Batch *DRW_cache_object_edge_detection_get(Object *ob)
+{
+	switch (ob->type) {
+		case OB_MESH:
+			return DRW_cache_mesh_edge_detection_get(ob);
+
+		/* TODO, should match 'DRW_cache_object_surface_get' */
+		default:
+			return NULL;
+	}
+}
+
 Gwn_Batch *DRW_cache_object_surface_get(Object *ob)
 {
 	switch (ob->type) {
@@ -2493,6 +2506,14 @@ Gwn_Batch *DRW_cache_mesh_wire_outline_get(Object *ob)
 	return DRW_mesh_batch_cache_get_fancy_edges(me);
 }
 
+Gwn_Batch *DRW_cache_mesh_edge_detection_get(Object *ob)
+{
+	BLI_assert(ob->type == OB_MESH);
+
+	Mesh *me = ob->data;
+	return DRW_mesh_batch_cache_get_edge_detection(me);
+}
+
 Gwn_Batch *DRW_cache_mesh_surface_get(Object *ob)
 {
 	BLI_assert(ob->type == OB_MESH);
diff --git a/source/blender/draw/intern/draw_cache.h b/source/blender/draw/intern/draw_cache.h
index b9a569b3ace..8bc609ffe1f 100644
--- a/source/blender/draw/intern/draw_cache.h
+++ b/source/blender/draw/intern/draw_cache.h
@@ -48,6 +48,7 @@ struct Gwn_Batch *DRW_cache_screenspace_circle_get(void);
 
 /* Common Object */
 struct Gwn_Batch *DRW_cache_object_wire_outline_get(struct Object *ob);
+struct Gwn_Batch *DRW_cache_object_edge_detection_get(struct Object *ob);
 struct Gwn_Batch *DRW_cache_object_surface_get(struct Object *ob);
 struct Gwn_Batch **DRW_cache_object_surface_material_get(
         struct Object *ob, struct GPUMaterial **gpumat_array, uint gpumat_array_len,
@@ -116,6 +117,7 @@ void DRW_cache_mesh_normals_overlay_get(
         struct Gwn_Batch **r_tris, struct Gwn_Batch **r_ledges, struct Gwn_Batch **r_lverts);
 struct Gwn_Batch *DRW_cache_face_centers_get(struct Object *ob);
 struct Gwn_Batch *DRW_cache_mesh_wire_outline_get(struct Object *ob);
+struct Gwn_Batch *DRW_cache_mesh_edge_detection_get(struct Object *ob);
 struct Gwn_Batch *DRW_cache_mesh_surface_get(struct Object *ob);
 struct Gwn_Batch *DRW_cache_mesh_surface_weights_get(struct Object *ob);
 struct Gwn_Batch *DRW_cache_mesh_surface_vert_colors_get(struct Object *ob);
diff --git a/source/blender/draw/intern/draw_cache_impl.h b/source/blender/draw/intern/draw_cache_impl.h
index 7f745192f2f..3ca53b92946 100644
--- a/source/blender/draw/intern/draw_cache_impl.h
+++ b/source/blender/draw/intern/draw_cache_impl.h
@@ -109,6 +109,7 @@ struct Gwn_Batch *DRW_mesh_batch_cache_get_triangles_with_select_mask(struct Mes
 struct Gwn_Batch *DRW_mesh_batch_cache_get_points_with_normals(struct Mesh *me);
 struct Gwn_Batch *DRW_mesh_batch_cache_get_all_verts(struct Mesh *me);
 struct Gwn_Batch *DRW_mesh_batch_cache_get_fancy_edges(struct Mesh *me);
+struct Gwn_Batch *DRW_mesh_batch_cache_get_edge_detection(struct Mesh *me);
 struct Gwn_Batch *DRW_mesh_batch_cache_get_overlay_triangles(struct Mesh *me);
 struct Gwn_Batch *DRW_mesh_batch_cache_get_overlay_triangles_nor(struct Mesh *me);
 struct Gwn_Batch *DRW_mesh_batch_cache_get_overlay_loose_edges(struct Mesh *me);
diff --git a/source/blender/draw/intern/draw_cache_impl_mesh.c b/source/blender/draw/intern/draw_cache_impl_mesh.c
index a33cd49e776..bc805bfed0d 100644
--- a/source/blender/draw/intern/draw_cache_impl_mesh.c
+++ b/source/blender/draw/intern/draw_cache_impl_mesh.c
@@ -36,6 +36,7 @@
 #include "BLI_math_bits.h"
 #include "BLI_string.h"
 #include "BLI_alloca.h"
+#include "BLI_edgehash.h"
 
 #include "DNA_mesh_types.h"
 #include "DNA_meshdata_types.h"
@@ -55,6 +56,9 @@
 #include "GPU_batch.h"
 #include "GPU_draw.h"
 #include "GPU_material.h"
+#include "GPU_texture.h"
+
+#include "DRW_render.h"
 
 #include "draw_cache_impl.h"  /* own include */
 
@@ -1229,6 +1233,8 @@ static bool mesh_render_data_edge_vcos_manifold_pnors(
 			*r_is_manifold = true;
 		}
 		else {
+			*r_pnor1 = eed->l->f->no;
+			*r_pnor2 = eed->l->f->no;
 			*r_is_manifold = false;
 		}
 	}
@@ -1268,12 +1274,27 @@ static bool mesh_render_data_edge_vcos_manifold_pnors(
 
 		*r_vco1 = mvert[medge[edge_index].v1].co;
 		*r_vco2 = mvert[medge[edge_index].v2].co;
+		*r_pnor1 = pnors[eap[edge_index].face_index[0]];
+
+		float nor[3], v1[3], v2[3], r_center[3];
+		const MPoly *mpoly = rdata->mpoly + eap[edge_index].face_index[0];
+		const MLoop *mloop = rdata->mloop + mpoly->loopstart;
+
+		BKE_mesh_calc_poly_center(mpoly, mloop, mvert, r_center);
+		sub_v3_v3v3(v1, *r_vco2, *r_vco1);
+		sub_v3_v3v3(v2, r_center, *r_vco1);
+		cross_v3_v3v3(nor, v1, v2);
+
+		if (dot_v3v3(nor, *r_pnor1) < 0.0) {
+			SWAP(float *, *r_vco1, *r_vco2);
+		}
+
 		if (eap[edge_index].count == 2) {
-			*r_pnor1 = pnors[eap[edge_index].face_index[0]];
 			*r_pnor2 = pnors[eap[edge_index].face_index[1]];
 			*r_is_manifold = true;
 		}
 		else {
+			*r_pnor2 = pnors[eap[edge_index].face_index[0]];
 			*r_is_manifold = false;
 		}
 	}
@@ -1499,6 +1520,7 @@ typedef struct MeshBatchCache {
 	Gwn_VertBuf *pos_in_order;
 	Gwn_VertBuf *nor_in_order;
 	Gwn_IndexBuf *edges_in_order;
+	Gwn_IndexBuf *edges_adjacency; /* Store edges with adjacent vertices. */
 	Gwn_IndexBuf *triangles_in_order;
 
 	Gwn_Batch *all_verts;
@@ -1537,6 +1559,8 @@ typedef struct MeshBatchCache {
 	Gwn_Batch *points_with_normals;
 	Gwn_Batch *fancy_edges; /* owns its vertex buffer (not shared) */
 
+	Gwn_Batch *edge_detection;
+
 	/* Maybe have shaded_triangles_data split into pos_nor and uv_tangent
 	 * to minimise data transfer for skinned mesh. */
 	Gwn_VertFormat shaded_triangles_format;
@@ -1806,6 +1830,9 @@ static void mesh_batch_cache_clear(Mesh *me)
 
 	GWN_BATCH_DISCARD_SAFE(cache->fancy_edges);
 
+	GWN_INDEXBUF_DISCARD_SAFE(cache->edges_adjacency);
+	GWN_BATCH_DISCARD_SAFE(cache->edge_detection);
+
 	GWN_VERTBUF_DISCARD_SAFE(cache->shaded_triangles_data);
 	if (cache->shaded_triangles_in_order) {
 		for (int i = 0; i < cache->mat_len; ++i) {
@@ -3178,6 +3205,96 @@ static Gwn_IndexBuf *mesh_batch_cache_get_edges_in_order(MeshRenderData *rdata,
 	return cache->edges_in_order;
 }
 
+#define NO_EDGE INT_MAX
+static Gwn_IndexBuf *mesh_batch_cache_get_edges_adjacency(MeshRenderData *rdata, MeshBatchCache *cache)
+{
+	BLI_assert(rdata->types & (MR_DATATYPE_VERT | MR_DATATYPE_LOOP | MR_DATATYPE_LOOPTRI));
+
+	if (cache->edges_adjacency == NULL) {
+		const int vert_len = mesh_render_data_verts_len_get(rdata);
+		const int tri_len = mesh_render_data_looptri_len_get(rdata);
+
+		/* Allocate max but only used indices are sent to GPU. */
+		Gwn_IndexBufBuilder elb;
+		GWN_indexbuf_init(&elb, GWN_PRIM_LINES_ADJ, tri_len * 3, vert_len);
+
+		EdgeHash *eh = BLI_edgehash_new_ex(__func__, tri_len * 3);
+		/* Create edges for each pair of triangles sharing an edge. */
+		for (int i = 0; i < tri_len; i++) {
+			for (int e = 0; e < 3; ++e) {
+				unsigned int v0, v1, v2;
+				if (rdata->edit_bmesh) {
+					const BMLoop **bm_looptri = (const BMLoop **)rdata->edit_bmesh->looptris[i];
+					if (BM_elem_flag_test(bm_looptri[0]->f, BM_ELEM_HIDDEN)) {
+						break;
+					}
+					v0 = BM_elem_index_get(bm_looptri[e]->v);
+					v1 = BM_elem_index_get(bm_looptri[(e+1)%3]->v);
+					v2 = BM_elem_index_get(bm_looptri[(e+2)%3]->v);
+				}
+				else {
+					MLoop *mloop = rdata->mloop;
+					MLoopTri *mlt = rdata->mlooptri + i;
+					v0 = mloop[mlt->tri[e]].v;
+					v1 = mloop[mlt->tri[(e+1)%3]].v;
+					v2 = mloop[mlt->tri[(e+2)%3]].v;
+				}
+				bool inv_indices = (v1 > v2);
+				void **pval;
+				bool value_is_init = BLI_edgehash_ensure_p(eh, v1, v2, &pval);
+				int v_data = GET_INT_FROM_POINTER(*pval);
+				if (!value_is_init || v_data == NO_EDGE) {
+					/* Save the winding order inside the sign bit. Because the
+					 * edgehash sort the keys and we need to compare winding later. */
+					int value = (int)v0 + 1; /* Int 0 cannot be signed */
+					*pval = SET_INT_IN_POINTER((inv_indices) ? -value : value);
+				}
+				else {
+					/* HACK Tag as not used. Prevent overhead of BLI_edgehash_remove. */
+					*pval = SET_INT_IN_POINTER(NO_EDGE);
+					bool inv_opposite = (v_data < 0);
+					unsigned int v_opposite = (unsigned int)abs(v_data) - 1;
+
+					if (inv_opposite == inv_indices) {
+						/* Don't share edge if triangles have non matching winding. */
+						GWN_indexbuf_add_line_adj_verts(&elb, v0, v1, v2, v0);
+						GWN_indexbuf_add_line_adj_verts(&elb, v_opposite, v1, v2, v_opposite);
+					}
+					else {
+						GWN_indexbuf_add_line_adj_verts(&elb, v0, v1, v2, v_opposite);
+					}
+				} 
+			}
+		}
+		/* Create edges for remaning non manifold edges. */
+		EdgeHashIterator *ehi;
+		for (ehi = BLI_edgehashIterator_new(eh);
+		     BLI_edgehashIterator_isDone(ehi) == false;
+		     BLI_edgehashIterator_step(ehi))
+		{
+			unsigned int v1, v2;
+			int v_data = GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
+			if (v_data == NO_EDGE) {
+				continue;
+			}
+			BLI_edgehashIterator_getKey(ehi, &v1, &v2);
+			unsigned int v0 = (unsigned int)abs(v_data) - 1;
+			if (v_data < 0) { /* inv_opposite  */
+				SWAP(unsigned int, v1, v2);
+			}
+			GWN_indexbuf_add_line_adj_verts(&elb, v0, v1, v2, v0);
+		}
+		BLI_edgehashIterator_free(ehi);
+		BLI_edgehash_free(eh, NULL);
+
+		cache->edges_adjacency = GWN_indexbuf_build(&elb);
+	}
+
+	return cache->edges_adjacency;
+
+}
+#undef NO_EDGE
+
 static Gwn_IndexBuf *mesh_batch_cache_get_triangles_in_order(MeshRenderData *rdata, MeshBatchCache *cache)
 {
 	BLI_assert(rdata->types & (MR_DATATYPE_VERT | MR_DATATYPE_LOOPTRI));
@@ -3685,6 +3802,24 @@ Gwn_Batch *DRW_mesh_batch_cache_get_fancy_edges(Mesh *me)
 	return cache->fancy_edges;
 }
 
+Gwn_Batch *DRW_mesh_batch_cache_get_edge_detection(Mesh *me)
+{
+	MeshBatchCache *cache = mesh_batch_cache_get(me);
+
+	if (cache->edge_detection == NULL) {
+		const int options = MR_DATATYPE_VERT | MR_DATATYPE_LOOP | MR_DATATYPE_LOOPTRI;
+
+		MeshRenderData *rdata = mesh_render_data_create(me, options);
+
+		cache->edge_detection = GWN_batch_create_ex(GWN_PRIM_LINES_ADJ, mesh_batch_cache_get_vert_pos_and_nor_in_order(rdata, cache),
+		                                                                mesh_batch_cache_get_edges_adjacency(rdata, cache), 0);
+
+		mesh_render_data_free(rdata);
+	}
+
+	return cache->edge_detection;
+}
+
 static void mesh_batch_cache_create_overlay_batches(Mesh *me)
 {
 	BLI_assert(me->edit_btmesh != NULL);