Mesh: Re-implement face split solving issue mentioned earlier

Now new edges will be properly created between original and
new split vertices.

Now topology is correct, but shading is still not quite in
some special cases.

1 files changed, 146 insertions, 31 deletions

diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index 13a00594d04..75e2a13f069 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -66,6 +66,11 @@
 
 #include "DEG_depsgraph.h"
 
+/* Define for cases when you want extra validation of mesh
+ * after certain modifications.
+ */
+// #undef VALIDATE_MESH
+
 enum {
 	MESHCMP_DVERT_WEIGHTMISMATCH = 1,
 	MESHCMP_DVERT_GROUPMISMATCH,
@@ -2090,7 +2095,47 @@ void BKE_mesh_calc_normals_split(Mesh *mesh)
 	}
 }
 
-/* Spli faces based on the edge angle.
+static void mesh_clear_vert_flags(Mesh *mesh)
+{
+	const int num_verts = mesh->totvert;
+	MVert *mvert = mesh->mvert;
+	for (int i = 0; i < num_verts; ++i, ++mvert) {
+		mvert->flag &= ~ME_VERT_TMP_TAG;
+	}
+}
+
+static void mesh_clear_edge_flags(Mesh *mesh)
+{
+	const int num_edge = mesh->totedge;
+	MEdge *medge = mesh->medge;
+	for (int i = 0; i < num_edge; ++i, ++medge) {
+		medge->flag &= ~ME_EDGE_TMP_TAG;
+	}
+}
+
+static int count_split_vert(MVert *mvert)
+{
+	if ((mvert->flag & ME_VERT_TMP_TAG) == 0) {
+		mvert->flag |= ME_VERT_TMP_TAG;
+		return 0;
+	}
+	else {
+		return 1;
+	}
+}
+
+static int count_split_edge(MEdge *medge)
+{
+	if ((medge->flag & ME_EDGE_TMP_TAG) == 0) {
+		medge->flag |= ME_EDGE_TMP_TAG;
+		return 0;
+	}
+	else {
+		return 1;
+	}
+}
+
+/* Split faces based on the edge angle.
  * Matches behavior of face splitting in render engines.
  */
 void BKE_mesh_split_faces(Mesh *mesh)
@@ -2103,26 +2148,36 @@ void BKE_mesh_split_faces(Mesh *mesh)
 	MLoop *mloop = mesh->mloop;
 	MPoly *mpoly = mesh->mpoly;
 	float (*lnors)[3];
-	int poly, num_new_verts = 0;
+	int num_new_verts = 0, num_new_edges = 0;
 	if ((mesh->flag & ME_AUTOSMOOTH) == 0) {
 		return;
 	}
+	if (num_polys == 0) {
+		return;
+	}
 	BKE_mesh_tessface_clear(mesh);
 	/* Compute loop normals if needed. */
 	if (!CustomData_has_layer(&mesh->ldata, CD_NORMAL)) {
 		BKE_mesh_calc_normals_split(mesh);
 	}
 	lnors = CustomData_get_layer(&mesh->ldata, CD_NORMAL);
+	/* Clear runtime flags. */
+	mesh_clear_vert_flags(mesh);
+	mesh_clear_edge_flags(mesh);
 	/* Count number of vertices to be split. */
-	for (poly = 0; poly < num_polys; poly++) {
+	for (int poly = 0; poly < num_polys; poly++) {
 		MPoly *mp = &mpoly[poly];
 		for (int loop = 0; loop < mp->totloop; loop++) {
-			MLoop *ml = &mloop[mp->loopstart + loop];
+			const MLoop *ml = &mloop[mp->loopstart + loop];
 			MVert *mv = &mvert[ml->v];
 			float vn[3];
 			normal_short_to_float_v3(vn, mv->no);
 			if (!equals_v3v3(vn, lnors[mp->loopstart + loop])) {
-				num_new_verts++;
+				/* When vertex is adjacent to two faces and gets split we don't
+				 * want new vertex counted for both faces. We tag it for re-use
+				 * by one of the faces.
+				 */
+				num_new_verts += count_split_vert(mv);
 			}
 		}
 	}
@@ -2130,19 +2185,55 @@ void BKE_mesh_split_faces(Mesh *mesh)
 		/* No new vertices are to be added, can do early exit. */
 		return;
 	}
+	/* Count number of edges to be added. */
+	for (int poly = 0; poly < num_polys; poly++) {
+		MPoly *mp = &mpoly[poly];
+		int loop_prev = mp->totloop - 1;
+		for (int loop = 0; loop < mp->totloop; loop++) {
+			const int poly_loop_prev = mp->loopstart + loop_prev;
+			const MLoop *ml = &mloop[mp->loopstart + loop];
+			const MVert *mv = &mvert[ml->v];
+			const MLoop *ml_prev = &mloop[poly_loop_prev];
+			const MVert *mv_prev = &mvert[ml_prev->v];
+			MEdge *me_prev = &medge[ml_prev->e];
+			if (mv->flag & ME_VERT_TMP_TAG) {
+				if (mv_prev->flag & ME_VERT_TMP_TAG) {
+					/* Create new edge between twp split vertices. */
+					num_new_edges += count_split_edge(me_prev);
+				}
+				else {
+					/* Create new edge from existing vertex to a split one. */
+					num_new_edges += count_split_edge(me_prev);
+				}
+			}
+			else if (mv_prev->flag & ME_VERT_TMP_TAG) {
+				/* Create new edge from split vertex to existing one. */
+				num_new_edges += count_split_edge(me_prev);
+			}
+			loop_prev = loop;
+		}
+	}
+	/* Clear runtime flags again, they will be reused. */
+	mesh_clear_vert_flags(mesh);
+	mesh_clear_edge_flags(mesh);
 	/* Reallocate all vert and edge related data. */
 	mesh->totvert += num_new_verts;
-	mesh->totedge += 2 * num_new_verts;
+	mesh->totedge += num_new_edges;
 	CustomData_realloc(&mesh->vdata, mesh->totvert);
 	CustomData_realloc(&mesh->edata, mesh->totedge);
 	/* Update pointers to a newly allocated memory. */
 	BKE_mesh_update_customdata_pointers(mesh, false);
 	mvert = mesh->mvert;
 	medge = mesh->medge;
-	/* Perform actual vertex split. */
+	/* Perform actual split of vertices and adjacent edges. */
 	num_new_verts = 0;
-	for (poly = 0; poly < num_polys; poly++) {
+	num_new_edges = 0;
+	/* Mapping from original vertex index to a split one. */
+	for (int poly = 0; poly < num_polys; poly++) {
 		MPoly *mp = &mpoly[poly];
+		/* First we split all vertices to get proper flag whether they are
+		 * split or not for all of them before handling edges.
+		 */
 		for (int loop = 0; loop < mp->totloop; loop++) {
 			int poly_loop = mp->loopstart + loop;
 			MLoop *ml = &mloop[poly_loop];
@@ -2150,44 +2241,68 @@ void BKE_mesh_split_faces(Mesh *mesh)
 			float vn[3];
 			normal_short_to_float_v3(vn, mv->no);
 			if (!equals_v3v3(vn, lnors[mp->loopstart + loop])) {
-				const int poly_loop_prev = (loop == 0)
-				        ? mp->loopstart + mp->totloop - 1
-				        : mp->loopstart + loop - 1;
-				MLoop *ml_prev = &mloop[poly_loop_prev];
-				int new_edge_prev, new_edge;
+				if ((mv->flag & ME_VERT_TMP_TAG) == 0) {
+					/* Ignore first split on vertex, re-use it instead. */
+					mv->flag |= ME_VERT_TMP_TAG;
+					continue;
+				}
 				/* Cretae new vertex. */
 				int new_vert = num_verts + num_new_verts;
 				CustomData_copy_data(&mesh->vdata, &mesh->vdata,
 				                     ml->v, new_vert, 1);
 				normal_float_to_short_v3(mvert[new_vert].no,
 				                         lnors[poly_loop]);
-				/* Create new edges. */
-				new_edge_prev = num_edges + 2 * num_new_verts;
-				new_edge = num_edges + 2 * num_new_verts + 1;
-				CustomData_copy_data(&mesh->edata, &mesh->edata,
-				                     ml_prev->e, new_edge_prev, 1);
-				CustomData_copy_data(&mesh->edata, &mesh->edata,
-				                     ml->e, new_edge, 1);
-				if (medge[new_edge_prev].v1 == ml->v) {
-					medge[new_edge_prev].v1 = new_vert;
+				ml->v = new_vert;
+				num_new_verts++;
+			}
+		}
+		/* Connect new vertices with edges. */
+		int loop_prev = mp->totloop - 1;
+		for (int loop = 0; loop < mp->totloop; loop++) {
+			const int poly_loop_prev = mp->loopstart + loop_prev;
+			const MLoop *ml = &mloop[mp->loopstart + loop];
+			const MVert *mv = &mvert[ml->v];
+			MLoop *ml_prev = &mloop[poly_loop_prev];
+			const MVert *mv_prev = &mvert[ml_prev->v];
+			MEdge *me_prev = &medge[ml_prev->e];
+			bool need_edge = false;
+			if (mv->flag & ME_VERT_TMP_TAG) {
+				if (mv_prev->flag & ME_VERT_TMP_TAG) {
+					/* Create new edge between twp split vertices. */
+					need_edge = true;
 				}
 				else {
-					medge[new_edge_prev].v2 = new_vert;
+					/* Create new edge from existing vertex to a split one. */
+					need_edge = true;
 				}
-				if (medge[new_edge].v1 == ml->v) {
-					medge[new_edge].v1 = new_vert;
+			}
+			else if (mv_prev->flag & ME_VERT_TMP_TAG) {
+				/* Create new edge from split vertex to existing one. */
+				need_edge = true;
+			}
+			if (need_edge) {
+				if ((me_prev->flag & ME_EDGE_TMP_TAG) == 0) {
+					me_prev->flag |= ME_EDGE_TMP_TAG;
+					me_prev->v1 = ml_prev->v;
+					me_prev->v2 = ml->v;
 				}
 				else {
-					medge[new_edge].v2 = new_vert;
+					const int index = num_edges + num_new_edges;
+					CustomData_copy_data(&mesh->edata, &mesh->edata,
+					                     ml_prev->e, index, 1);
+					MEdge *me_new = &medge[index];
+					me_new->v1 = ml_prev->v;
+					me_new->v2 = ml->v;
+					ml_prev->e = index;
+					num_new_edges++;
 				}
-
-				ml->v = new_vert;
-				ml_prev->e = new_edge_prev;
-				ml->e = new_edge;
-				num_new_verts++;
 			}
+			loop_prev = loop;
 		}
 	}
+#ifdef VALIDATE_MESH
+	BKE_mesh_validate(mesh, true, true);
+#endif
 }
 
 /* settings: 1 - preview, 2 - render */