DrawManager: Add Edge Detection To DisplayLists

Objects that internally uses DispList do not cast shadow in the workbench.
Their outline is also not visible in object mode. The reason for this is
that edge detection was not implemented for Display Lists. This patch will
implement the edge detection.

Reviewed By: fclem

Maniphest Tasks: T62479

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

6 files changed, 228 insertions, 3 deletions

diff --git a/source/blender/draw/intern/draw_cache.c b/source/blender/draw/intern/draw_cache.c
index 482cc047bbc..cdbbcf9ec2b 100644
--- a/source/blender/draw/intern/draw_cache.c
+++ b/source/blender/draw/intern/draw_cache.c
@@ -705,8 +705,14 @@ GPUBatch *DRW_cache_object_edge_detection_get(Object *ob, bool *r_is_manifold)
 	switch (ob->type) {
 		case OB_MESH:
 			return DRW_cache_mesh_edge_detection_get(ob, r_is_manifold);
-
-		/* TODO, should match 'DRW_cache_object_surface_get' */
+		case OB_CURVE:
+			return DRW_cache_curve_edge_detection_get(ob, r_is_manifold);
+		case OB_SURF:
+			return DRW_cache_surf_edge_detection_get(ob, r_is_manifold);
+		case OB_FONT:
+			return DRW_cache_text_edge_detection_get(ob, r_is_manifold);
+		case OB_MBALL:
+			return DRW_cache_mball_edge_detection_get(ob, r_is_manifold);
 		default:
 			return NULL;
 	}
@@ -3179,6 +3185,19 @@ GPUBatch *DRW_cache_curve_face_wireframe_get(Object *ob)
 	}
 }
 
+GPUBatch *DRW_cache_curve_edge_detection_get(Object *ob, bool *r_is_manifold)
+{
+	BLI_assert(ob->type == OB_CURVE);
+	struct Curve *cu = ob->data;
+	struct Mesh *mesh_eval = ob->runtime.mesh_eval;
+	if (mesh_eval != NULL) {
+		return DRW_mesh_batch_cache_get_edge_detection(mesh_eval, r_is_manifold);
+	}
+	else {
+		return DRW_curve_batch_cache_get_edge_detection(cu, r_is_manifold);
+	}
+}
+
 /* Return list of batches */
 GPUBatch **DRW_cache_curve_surface_shaded_get(
         Object *ob, struct GPUMaterial **gpumat_array, uint gpumat_array_len)
@@ -3207,6 +3226,11 @@ GPUBatch *DRW_cache_mball_surface_get(Object *ob)
 	return DRW_metaball_batch_cache_get_triangles_with_normals(ob);
 }
 
+GPUBatch *DRW_cache_mball_edge_detection_get(Object *ob, bool *r_is_manifold) {
+	BLI_assert(ob->type == OB_MBALL);
+	return DRW_metaball_batch_cache_get_edge_detection(ob, r_is_manifold);
+}
+
 GPUBatch *DRW_cache_mball_face_wireframe_get(Object *ob)
 {
 	BLI_assert(ob->type == OB_MBALL);
@@ -3251,6 +3275,22 @@ GPUBatch *DRW_cache_text_surface_get(Object *ob)
 	}
 }
 
+GPUBatch *DRW_cache_text_edge_detection_get(Object *ob, bool *r_is_manifold)
+{
+	BLI_assert(ob->type == OB_FONT);
+	struct Curve *cu = ob->data;
+	struct Mesh *mesh_eval = ob->runtime.mesh_eval;
+	if (cu->editfont && (cu->flag & CU_FAST)) {
+		return NULL;
+	}
+	if (mesh_eval != NULL) {
+		return DRW_mesh_batch_cache_get_edge_detection(mesh_eval, r_is_manifold);
+	}
+	else {
+		return DRW_curve_batch_cache_get_edge_detection(cu, r_is_manifold);
+	}
+}
+
 GPUBatch *DRW_cache_text_loose_edges_get(Object *ob)
 {
 	BLI_assert(ob->type == OB_FONT);
@@ -3343,6 +3383,19 @@ GPUBatch *DRW_cache_surf_face_wireframe_get(Object *ob)
 	}
 }
 
+GPUBatch *DRW_cache_surf_edge_detection_get(Object *ob, bool *r_is_manifold)
+{
+	BLI_assert(ob->type == OB_SURF);
+	struct Curve *cu = ob->data;
+	struct Mesh *mesh_eval = ob->runtime.mesh_eval;
+	if (mesh_eval != NULL) {
+		return DRW_mesh_batch_cache_get_edge_detection(mesh_eval, r_is_manifold);
+	}
+	else {
+		return DRW_curve_batch_cache_get_edge_detection(cu, r_is_manifold);
+	}
+}
+
 GPUBatch *DRW_cache_surf_loose_edges_get(Object *ob)
 {
 	BLI_assert(ob->type == OB_SURF);
diff --git a/source/blender/draw/intern/draw_cache.h b/source/blender/draw/intern/draw_cache.h
index 287d970e298..2940a2c89f8 100644
--- a/source/blender/draw/intern/draw_cache.h
+++ b/source/blender/draw/intern/draw_cache.h
@@ -145,6 +145,7 @@ struct GPUBatch **DRW_cache_curve_surface_shaded_get(
 struct GPUBatch *DRW_cache_curve_loose_edges_get(struct Object *ob);
 struct GPUBatch *DRW_cache_curve_edge_wire_get(struct Object *ob);
 struct GPUBatch *DRW_cache_curve_face_wireframe_get(Object *ob);
+struct GPUBatch *DRW_cache_curve_edge_detection_get(struct Object *ob, bool *r_is_manifold);
 /* edit-mode */
 struct GPUBatch *DRW_cache_curve_edge_normal_get(struct Object *ob);
 struct GPUBatch *DRW_cache_curve_edge_overlay_get(struct Object *ob);
@@ -152,6 +153,7 @@ struct GPUBatch *DRW_cache_curve_vert_overlay_get(struct Object *ob, bool handle
 
 /* Font */
 struct GPUBatch *DRW_cache_text_surface_get(struct Object *ob);
+struct GPUBatch *DRW_cache_text_edge_detection_get(Object *ob, bool *r_is_manifold);
 struct GPUBatch *DRW_cache_text_loose_edges_get(struct Object *ob);
 struct GPUBatch *DRW_cache_text_edge_wire_get(struct Object *ob);
 struct GPUBatch **DRW_cache_text_surface_shaded_get(
@@ -165,6 +167,7 @@ struct GPUBatch *DRW_cache_surf_loose_edges_get(struct Object *ob);
 struct GPUBatch **DRW_cache_surf_surface_shaded_get(
         struct Object *ob, struct GPUMaterial **gpumat_array, uint gpumat_array_len);
 struct GPUBatch *DRW_cache_surf_face_wireframe_get(Object *ob);
+struct GPUBatch *DRW_cache_surf_edge_detection_get(struct Object *ob, bool *r_is_manifold);
 
 /* Lattice */
 struct GPUBatch *DRW_cache_lattice_verts_get(struct Object *ob);
@@ -188,5 +191,6 @@ struct GPUBatch *DRW_cache_particles_get_prim(int type);
 struct GPUBatch *DRW_cache_mball_surface_get(struct Object *ob);
 struct GPUBatch **DRW_cache_mball_surface_shaded_get(struct Object *ob, struct GPUMaterial **gpumat_array, uint gpumat_array_len);
 struct GPUBatch *DRW_cache_mball_face_wireframe_get(Object *ob);
+struct GPUBatch *DRW_cache_mball_edge_detection_get(struct Object *ob, bool *r_is_manifold);
 
 #endif /* __DRAW_CACHE_H__ */
diff --git a/source/blender/draw/intern/draw_cache_impl.h b/source/blender/draw/intern/draw_cache_impl.h
index 7a8cea23655..4e014711245 100644
--- a/source/blender/draw/intern/draw_cache_impl.h
+++ b/source/blender/draw/intern/draw_cache_impl.h
@@ -66,6 +66,7 @@ void DRW_curve_batch_cache_create_requested(struct Object *ob);
 
 struct GPUBatch *DRW_curve_batch_cache_get_wire_edge(struct Curve *cu);
 struct GPUBatch *DRW_curve_batch_cache_get_normal_edge(struct Curve *cu);
+struct GPUBatch *DRW_curve_batch_cache_get_edge_detection(struct Curve *cu, bool *r_is_manifold);
 struct GPUBatch *DRW_curve_batch_cache_get_edit_edges(struct Curve *cu);
 struct GPUBatch *DRW_curve_batch_cache_get_edit_verts(struct Curve *cu, bool handles);
 
@@ -73,12 +74,12 @@ struct GPUBatch *DRW_curve_batch_cache_get_triangles_with_normals(struct Curve *
 struct GPUBatch **DRW_curve_batch_cache_get_surface_shaded(
         struct Curve *cu, struct GPUMaterial **gpumat_array, uint gpumat_array_len);
 struct GPUBatch *DRW_curve_batch_cache_get_wireframes_face(struct Curve *cu);
-
 /* Metaball */
 struct GPUBatch *DRW_metaball_batch_cache_get_triangles_with_normals(struct Object *ob);
 struct GPUBatch **DRW_metaball_batch_cache_get_surface_shaded(
         struct Object *ob, struct MetaBall *mb, struct GPUMaterial **gpumat_array, uint gpumat_array_len);
 struct GPUBatch *DRW_metaball_batch_cache_get_wireframes_face(struct Object *ob);
+struct GPUBatch *DRW_metaball_batch_cache_get_edge_detection(struct Object *ob, bool *r_is_manifold);
 
 /* DispList */
 void DRW_displist_vertbuf_create_pos_and_nor(struct ListBase *lb, struct GPUVertBuf *vbo);
@@ -89,6 +90,7 @@ void DRW_displist_indexbuf_create_lines_in_order(struct ListBase *lb, struct GPU
 void DRW_displist_indexbuf_create_triangles_in_order(struct ListBase *lb, struct GPUIndexBuf *ibo);
 void DRW_displist_indexbuf_create_triangles_loop_split_by_material(
         struct ListBase *lb, struct GPUIndexBuf **ibo_mat, uint mat_len);
+void DRW_displist_indexbuf_create_edges_adjacency_lines(struct ListBase *lb, struct GPUIndexBuf *ibo, bool *r_is_manifold);
 
 /* Lattice */
 struct GPUBatch *DRW_lattice_batch_cache_get_all_edges(struct Lattice *lt, bool use_weight, const int actdef);
diff --git a/source/blender/draw/intern/draw_cache_impl_curve.c b/source/blender/draw/intern/draw_cache_impl_curve.c
index ebffedf9454..eecb6c3dd6a 100644
--- a/source/blender/draw/intern/draw_cache_impl_curve.c
+++ b/source/blender/draw/intern/draw_cache_impl_curve.c
@@ -366,6 +366,7 @@ typedef struct CurveBatchCache {
 		GPUIndexBuf *surfaces_tris;
 		GPUIndexBuf *surfaces_lines;
 		GPUIndexBuf *curves_lines;
+		GPUIndexBuf *edges_adj_lines;
 		/* Edit mode */
 		GPUIndexBuf *edit_verts_points; /* Only control points. Not handles. */
 		GPUIndexBuf *edit_lines;
@@ -380,6 +381,7 @@ typedef struct CurveBatchCache {
 		GPUBatch *edit_verts;
 		GPUBatch *edit_handles_verts;
 		GPUBatch *edit_normals;
+		GPUBatch *edge_detection;
 	} batch;
 
 	GPUIndexBuf **surf_per_mat_tris;
@@ -390,6 +392,9 @@ typedef struct CurveBatchCache {
 	/* settings to determine if cache is invalid */
 	bool is_dirty;
 	bool is_editmode;
+
+	/* Valid only if edge_detection is up to date. */
+	bool is_manifold;
 } CurveBatchCache;
 
 /* GPUBatch cache management. */
@@ -880,6 +885,17 @@ GPUBatch *DRW_curve_batch_cache_get_wireframes_face(Curve *cu)
 	return DRW_batch_request(&cache->batch.surfaces_edges);
 }
 
+GPUBatch *DRW_curve_batch_cache_get_edge_detection(Curve *cu, bool *r_is_manifold)
+{
+	CurveBatchCache *cache = curve_batch_cache_get(cu);
+	/* Even if is_manifold is not correct (not updated),
+	 * the default (not manifold) is just the worst case. */
+	if (r_is_manifold) {
+		*r_is_manifold = cache->is_manifold;
+	}
+	return DRW_batch_request(&cache->batch.edge_detection);
+}
+
 /** \} */
 
 /* -------------------------------------------------------------------- */
@@ -922,6 +938,10 @@ void DRW_curve_batch_cache_create_requested(Object *ob)
 		DRW_ibo_request(cache->batch.curves, &cache->ibo.curves_lines);
 		DRW_vbo_request(cache->batch.curves, &cache->ordered.curves_pos);
 	}
+	if (DRW_batch_requested(cache->batch.edge_detection, GPU_PRIM_LINES_ADJ)) {
+		DRW_ibo_request(cache->batch.edge_detection, &cache->ibo.edges_adj_lines);
+		DRW_vbo_request(cache->batch.edge_detection, &cache->ordered.pos_nor);
+	}
 
 	/* Edit mode */
 	if (DRW_batch_requested(cache->batch.edit_edges, GPU_PRIM_LINES)) {
@@ -963,6 +983,7 @@ void DRW_curve_batch_cache_create_requested(Object *ob)
 	DRW_ADD_FLAG_FROM_IBO_REQUEST(mr_flag, cache->ibo.surfaces_tris, CU_DATATYPE_SURFACE);
 	DRW_ADD_FLAG_FROM_IBO_REQUEST(mr_flag, cache->ibo.surfaces_lines, CU_DATATYPE_SURFACE);
 	DRW_ADD_FLAG_FROM_IBO_REQUEST(mr_flag, cache->ibo.curves_lines, CU_DATATYPE_WIRE);
+	DRW_ADD_FLAG_FROM_IBO_REQUEST(mr_flag, cache->ibo.edges_adj_lines, CU_DATATYPE_SURFACE);
 
 	DRW_ADD_FLAG_FROM_VBO_REQUEST(mr_flag, cache->edit.pos, CU_DATATYPE_OVERLAY);
 	DRW_ADD_FLAG_FROM_VBO_REQUEST(mr_flag, cache->edit.data, CU_DATATYPE_OVERLAY);
@@ -1010,6 +1031,9 @@ void DRW_curve_batch_cache_create_requested(Object *ob)
 	if (DRW_ibo_requested(cache->ibo.surfaces_lines)) {
 		DRW_displist_indexbuf_create_lines_in_order(lb, cache->ibo.surfaces_lines);
 	}
+	if (DRW_ibo_requested(cache->ibo.edges_adj_lines)) {
+		DRW_displist_indexbuf_create_edges_adjacency_lines(lb, cache->ibo.edges_adj_lines, &cache->is_manifold);
+	}
 
 	if (DRW_vbo_requested(cache->edit.pos) ||
 	    DRW_vbo_requested(cache->edit.data) ||
diff --git a/source/blender/draw/intern/draw_cache_impl_displist.c b/source/blender/draw/intern/draw_cache_impl_displist.c
index 63514acf1c2..dfac50e084c 100644
--- a/source/blender/draw/intern/draw_cache_impl_displist.c
+++ b/source/blender/draw/intern/draw_cache_impl_displist.c
@@ -28,6 +28,7 @@
 
 #include "BLI_alloca.h"
 #include "BLI_utildefines.h"
+#include "BLI_edgehash.h"
 #include "BLI_math_vector.h"
 
 #include "DNA_curve_types.h"
@@ -561,3 +562,97 @@ void DRW_displist_vertbuf_create_loop_pos_and_nor_and_uv(
 		}
 	}
 }
+
+/* Edge detection/adjecency */
+#define NO_EDGE INT_MAX
+static void set_edge_adjacency_lines_indices(EdgeHash *eh, GPUIndexBufBuilder *elb, bool *r_is_manifold, uint v1, uint v2, uint v3)
+{
+	bool inv_indices = (v2 > v3);
+	void **pval;
+	bool value_is_init = BLI_edgehash_ensure_p(eh, v2, v3, &pval);
+	int v_data = POINTER_AS_INT(*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)v1 + 1; /* Int 0 bm_looptricannot be signed */
+		*pval = POINTER_FROM_INT((inv_indices) ? -value : value);
+	}
+	else {
+		/* HACK Tag as not used. Prevent overhead of BLI_edgehash_remove. */
+		*pval = POINTER_FROM_INT(NO_EDGE);
+		bool inv_opposite = (v_data < 0);
+		uint v_opposite = (uint)abs(v_data) - 1;
+
+		if (inv_opposite == inv_indices) {
+			/* Don't share edge if triangles have non matching winding. */
+			GPU_indexbuf_add_line_adj_verts(elb, v1, v2, v3, v1);
+			GPU_indexbuf_add_line_adj_verts(elb, v_opposite, v2, v3, v_opposite);
+			*r_is_manifold = false;
+		}
+		else {
+			GPU_indexbuf_add_line_adj_verts(elb, v1, v2, v3, v_opposite);
+		}
+	}
+}
+
+static void set_edges_adjacency_lines_indices(void *thunk, uint v1, uint v2, uint v3)
+{
+	void **packed = (void**)thunk;
+	GPUIndexBufBuilder *elb = (GPUIndexBufBuilder*)packed[0];
+	EdgeHash *eh = (EdgeHash*)packed[1];
+	bool *r_is_manifold = (bool*)packed[2];
+
+	set_edge_adjacency_lines_indices(eh, elb, r_is_manifold, v1, v2, v3);
+	set_edge_adjacency_lines_indices(eh, elb, r_is_manifold, v2, v3, v1);
+	set_edge_adjacency_lines_indices(eh, elb, r_is_manifold, v3, v1, v2);
+}
+
+void DRW_displist_indexbuf_create_edges_adjacency_lines(struct ListBase *lb, struct GPUIndexBuf *ibo, bool *r_is_manifold)
+{
+	const int tri_len = curve_render_surface_tri_len_get(lb);
+	const int vert_len = curve_render_surface_vert_len_get(lb);
+
+	*r_is_manifold = true;
+
+	/* Allocate max but only used indices are sent to GPU. */
+	GPUIndexBufBuilder elb;
+	GPU_indexbuf_init(&elb, GPU_PRIM_LINES_ADJ, tri_len * 3, vert_len);
+
+	EdgeHash *eh = BLI_edgehash_new_ex(__func__, tri_len * 3);
+
+	/* pack values to pass to `set_edges_adjacency_lines_indices` function. */
+	void* thunk[3] = {&elb,eh, r_is_manifold};
+	int v_idx = 0;
+	for (const DispList *dl = lb->first; dl; dl = dl->next) {
+		displist_indexbufbuilder_set(
+		        (SetTriIndicesFn *)set_edges_adjacency_lines_indices,
+		        (SetTriIndicesFn *)set_edges_adjacency_lines_indices,
+		        thunk, dl, v_idx);
+		v_idx += dl_vert_len(dl);
+	}
+
+	/* Create edges for remaning non manifold edges. */
+	EdgeHashIterator *ehi;
+	for (ehi = BLI_edgehashIterator_new(eh);
+	     BLI_edgehashIterator_isDone(ehi) == false;
+	     BLI_edgehashIterator_step(ehi))
+	{
+		uint v1, v2;
+		int v_data = POINTER_AS_INT(BLI_edgehashIterator_getValue(ehi));
+		if (v_data == NO_EDGE) {
+			continue;
+		}
+		BLI_edgehashIterator_getKey(ehi, &v1, &v2);
+		uint v0 = (uint)abs(v_data) - 1;
+		if (v_data < 0) { /* inv_opposite  */
+			SWAP(uint, v1, v2);
+		}
+		GPU_indexbuf_add_line_adj_verts(&elb, v0, v1, v2, v0);
+		*r_is_manifold = false;
+	}
+	BLI_edgehashIterator_free(ehi);
+	BLI_edgehash_free(eh, NULL);
+
+	GPU_indexbuf_build_in_place(&elb, ibo);
+}
+#undef NO_EDGE
diff --git a/source/blender/draw/intern/draw_cache_impl_metaball.c b/source/blender/draw/intern/draw_cache_impl_metaball.c
index 811f01aa83a..46c247d67ea 100644
--- a/source/blender/draw/intern/draw_cache_impl_metaball.c
+++ b/source/blender/draw/intern/draw_cache_impl_metaball.c
@@ -47,6 +47,7 @@ static void metaball_batch_cache_clear(MetaBall *mb);
 typedef struct MetaBallBatchCache {
 	GPUBatch *batch;
 	GPUBatch **shaded_triangles;
+
 	int mat_len;
 
 	/* Shared */
@@ -57,8 +58,15 @@ typedef struct MetaBallBatchCache {
 		GPUBatch *batch;
 	} face_wire;
 
+	/* Edge detection */
+	GPUBatch *edge_detection;
+	GPUIndexBuf *edges_adj_lines;
+
 	/* settings to determine if cache is invalid */
 	bool is_dirty;
+
+	/* Valid only if edge_detection is up to date. */
+	bool is_manifold;
 } MetaBallBatchCache;
 
 /* GPUBatch cache management. */
@@ -87,6 +95,9 @@ static void metaball_batch_cache_init(MetaBall *mb)
 	cache->is_dirty = false;
 	cache->pos_nor_in_order = NULL;
 	cache->face_wire.batch = NULL;
+	cache->edge_detection = NULL;
+	cache->edges_adj_lines = NULL;
+	cache->is_manifold = false;
 }
 
 static MetaBallBatchCache *metaball_batch_cache_get(MetaBall *mb)
@@ -122,10 +133,13 @@ static void metaball_batch_cache_clear(MetaBall *mb)
 
 	GPU_BATCH_DISCARD_SAFE(cache->face_wire.batch);
 	GPU_BATCH_DISCARD_SAFE(cache->batch);
+	GPU_BATCH_DISCARD_SAFE(cache->edge_detection);
 	GPU_VERTBUF_DISCARD_SAFE(cache->pos_nor_in_order);
+	GPU_INDEXBUF_DISCARD_SAFE(cache->edges_adj_lines);
 	/* Note: shaded_triangles[0] is already freed by cache->batch */
 	MEM_SAFE_FREE(cache->shaded_triangles);
 	cache->mat_len = 0;
+	cache->is_manifold = false;
 }
 
 void DRW_mball_batch_cache_free(MetaBall *mb)
@@ -144,6 +158,16 @@ static GPUVertBuf *mball_batch_cache_get_pos_and_normals(Object *ob, MetaBallBat
 	return cache->pos_nor_in_order;
 }
 
+static GPUIndexBuf *mball_batch_cache_get_edges_adj_lines(Object *ob, MetaBallBatchCache *cache)
+{
+	if (cache->edges_adj_lines == NULL) {
+		ListBase *lb = &ob->runtime.curve_cache->disp;
+		cache->edges_adj_lines = MEM_callocN(sizeof(GPUVertBuf), __func__);
+		DRW_displist_indexbuf_create_edges_adjacency_lines(lb, cache->edges_adj_lines, &cache->is_manifold);
+	}
+	return cache->edges_adj_lines;
+}
+
 /* -------------------------------------------------------------------- */
 /** \name Public Object/MetaBall API
  * \{ */
@@ -219,3 +243,26 @@ GPUBatch *DRW_metaball_batch_cache_get_wireframes_face(Object *ob)
 
 	return cache->face_wire.batch;
 }
+
+struct GPUBatch *DRW_metaball_batch_cache_get_edge_detection(struct Object *ob, bool *r_is_manifold)
+{
+	if (!BKE_mball_is_basis(ob)) {
+		return NULL;
+	}
+
+	MetaBall *mb = ob->data;
+	MetaBallBatchCache *cache = metaball_batch_cache_get(mb);
+
+	if (cache->edge_detection == NULL) {
+		cache->edge_detection = GPU_batch_create(
+		        GPU_PRIM_LINES_ADJ,
+		        mball_batch_cache_get_pos_and_normals(ob, cache),
+		        mball_batch_cache_get_edges_adj_lines(ob, cache));
+	}
+
+	if (r_is_manifold) {
+		*r_is_manifold = cache->is_manifold;
+	}
+
+	return cache->edge_detection;
+}
\ No newline at end of file