OpenSubdiv: Work on better vert edge/face orientation code

Previous version of code didn't handle cases like hourglass connectivity
with loose edge. The new code is supposed to handle all this cases.

1 files changed, 156 insertions, 111 deletions

diff --git a/intern/opensubdiv/opensubdiv_converter.cc b/intern/opensubdiv/opensubdiv_converter.cc
index 119a7bf9340..117edc41bfc 100644
--- a/intern/opensubdiv/opensubdiv_converter.cc
+++ b/intern/opensubdiv/opensubdiv_converter.cc
@@ -49,22 +49,51 @@ inline int findInArray(T array, int value)
 	return (int)(std::find(array.begin(), array.end(), value) - array.begin());
 }
 
-}  /* namespace */
+#ifdef OPENSUBDIV_ORIENT_TOPOLOGY
+inline void check_oriented_vert_connectivity(const int num_vert_edges,
+                                             const int num_vert_faces,
+                                             const int *vert_edges,
+                                             const int *vert_faces,
+                                             const int *dst_vert_edges,
+                                             const int *dst_vert_faces)
+{
+#  ifndef NDEBUG
+	for (int i = 0; i < num_vert_faces; ++i) {
+		bool found = false;
+		for (int j = 0; j < num_vert_faces; ++j) {
+			if (vert_faces[i] == dst_vert_faces[j]) {
+				found = true;
+				break;
+			}
+		}
+		if (!found) {
+			assert(!"vert-faces connectivity ruined");
+		}
+	}
+	for (int i = 0; i < num_vert_edges; ++i) {
+		bool found = false;
+		for (int j = 0; j < num_vert_edges; ++j) {
+			if (vert_edges[i] == dst_vert_edges[j]) {
+				found = true;
+				break;
+			}
+		}
+		if (!found) {
+			assert(!"vert-edges connectivity ruined");
+		}
+	}
+#  else
+	(void)num_vert_edges;
+	(void)num_vert_faces;
+	(void)vert_edges;
+	(void)vert_faces;
+	(void)dst_vert_edges;
+	(void)dst_vert_faces;
+#  endif
+}
+#endif
 
-struct StackElem {
-	StackElem(int face_start,
-	          int edge_start,
-	          int face_vert_start,
-	          bool append_start_edge = true)
-	        : face_start(face_start),
-	          edge_start(edge_start),
-	          face_vert_start(face_vert_start),
-	          append_start_edge(append_start_edge){}
-	int face_start;
-	int edge_start;
-	int face_vert_start;
-	bool append_start_edge;
-};
+}  /* namespace */
 
 template <>
 inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::resizeComponentTopology(
@@ -123,7 +152,12 @@ inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::assignComponentTopolog
 	}
 	/* Vertex relations */
 	const int num_verts = conv.get_num_verts(&conv);
+#ifdef OPENSUBDIV_ORIENT_TOPOLOGY
+	/* Flags used to see if the face was traversed already or not. */
+	bool *face_used = new bool[num_faces];
+#endif
 	for (int vert = 0; vert < num_verts; ++vert) {
+
 		/* Vert-Faces */
 		IndexArray dst_vert_faces = getBaseVertexFaces(refiner, vert);
 		int num_vert_faces = conv.get_num_vert_faces(&conv, vert);
@@ -135,56 +169,101 @@ inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::assignComponentTopolog
 		int *vert_edges = new int[num_vert_edges];
 		conv.get_vert_edges(&conv, vert, vert_edges);
 #ifdef OPENSUBDIV_ORIENT_TOPOLOGY
-		/* Order vertex edges and faces in a CCW order. */
-		/* TODO(sergey): Look into possible optimizations here. */
-		bool *face_used = new bool[num_faces];
+		/* ** Order vertex edges and faces in a CCW order. ** */
 		memset(face_used, 0, sizeof(bool) * num_faces);
-		std::stack<StackElem> stack;
+		/* Number of edges and faces added to the ordered array. */
 		int edge_count_ordered = 0, face_count_ordered = 0;
-		if (num_vert_edges == num_vert_faces) {
-			/* Manifold vertex, start with any face and perform traversal. */
-			int face_start = vert_faces[0];
-			int face_vert_start = findInArray(getBaseFaceVertices(refiner, face_start), vert);
-			int edge_start = getBaseFaceEdges(refiner, face_start)[face_vert_start];
-			stack.push(StackElem(face_start, edge_start, face_vert_start));
+		/* Add loose edges straight into the edges array. */
+		bool has_fan_connections = false;
+		for (int i = 0; i < num_vert_edges; ++i) {
+			IndexArray edge_faces = getBaseEdgeFaces(refiner, vert_edges[i]);
+			if (edge_faces.size() == 0) {
+				dst_vert_edges[edge_count_ordered++] = vert_edges[i];
+			}
+			else if (edge_faces.size() > 2) {
+				has_fan_connections = true;
+			}
 		}
-		else {
-			/* ** Non-manifold vertex. Special handle here. ** */
-			/* Add all loose edges adjacent to the vertex. */
-			for (int i = 0; i < num_vert_edges; ++i) {
-				IndexArray edge_faces = getBaseEdgeFaces(refiner, vert_edges[i]);
-				if (edge_faces.size() == 0) {
-					/* Can't really orient loose edges, just add then straight
-					 * to the vert-edges array.
-					 */
-					dst_vert_edges[edge_count_ordered++] = vert_edges[i];
+		if (has_fan_connections) {
+			/* OpenSubdiv currently doesn't give us clues how to handle
+			 * fan face connections. and since handling such connections
+			 * complicates the loop below we simply don't do special
+			 * orientation for them.
+			 */
+			memcpy(&dst_vert_edges[0], vert_edges, sizeof(int) * num_vert_edges);
+			memcpy(&dst_vert_faces[0], vert_faces, sizeof(int) * num_vert_faces);
+			delete [] vert_edges;
+			delete [] vert_faces;
+			continue;
+		}
+		/* Perform at max numbder of vert-edges iteration and try to avoid
+		 * deadlock here for malformed mesh.
+		 */
+		for (int global_iter = 0; global_iter < num_vert_edges; ++global_iter) {
+			/* Numbr of edges and faces which are still to be ordered. */
+			int num_vert_edges_remained = num_vert_edges - edge_count_ordered,
+			    num_vert_faces_remained = num_vert_faces - face_count_ordered;
+			if (num_vert_edges_remained == 0 && num_vert_faces_remained == 0) {
+				/* All done, nothing to do anymore. */
+				break;
+			}
+			/* Face, edge and face-vertex inndex to start traversal from. */
+			int face_start = -1, edge_start = -1, face_vert_start = -1;
+			if (num_vert_edges_remained == num_vert_faces_remained) {
+				/* Vertex is eitehr complete manifold or is connected to seevral
+				 * manifold islands (hourglass-like configuration), can pick up
+				 * random edge unused and start from it.
+				 */
+				/* TODO(sergey): Start from previous edge from which traversal
+				 * began at previous iteration.
+				 */
+				for (int i = 0; i < num_vert_edges; ++i) {
+					face_start = vert_faces[i];
+					if (!face_used[face_start]) {
+						ConstIndexArray
+						    face_verts = getBaseFaceVertices(refiner, face_start),
+						    face_edges = getBaseFaceEdges(refiner, face_start);
+						face_vert_start = findInArray(face_verts, vert);
+						edge_start = face_edges[face_vert_start];
+						break;
+					}
 				}
-				else if (edge_faces.size() == 1) {
-					int edge_start = vert_edges[i];
-					int face_start = edge_faces[0];
-					int face_vert_start = findInArray(getBaseFaceVertices(refiner, face_start), vert);
-					if (edge_start == (getBaseFaceEdges(refiner, face_start)[face_vert_start])) {
-						stack.push(StackElem(face_start, edge_start, face_vert_start));
-						face_used[face_start] = true;
+			}
+			else {
+				/* Special handle of non-manifold vertex. */
+				for (int i = 0; i < num_vert_edges; ++i) {
+					bool start_found = false;
+					edge_start = vert_edges[i];
+					IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_start);
+					for (int j = 0; j < edge_faces.size(); ++j) {
+						face_start = edge_faces[j];
+						if (!face_used[face_start]) {
+							ConstIndexArray
+							    face_verts = getBaseFaceVertices(refiner, face_start),
+							    face_edges = getBaseFaceEdges(refiner, face_start);
+							face_vert_start = findInArray(face_verts, vert);
+							if (edge_start == face_edges[face_vert_start]) {
+								start_found = true;
+								break;
+							}
+						}
+					}
+					if (start_found) {
+						break;
 					}
+					/* Reset indices for sanity check below. */
+					face_start = edge_start = face_vert_start =  -1;
 				}
 			}
-		}
-		while (!stack.empty()) {
-			StackElem& top = stack.top();
-			int edge_start = top.edge_start;
-			int face_start = top.face_start;
-			int face_vert_start = top.face_vert_start;
-			bool append_start_edge = top.append_start_edge;
-			stack.pop();
-			Index edge_first = edge_start;
-
+			/* Sanity check. */
+			assert(face_start != -1 &&
+			       edge_start != -1 &&
+			       face_vert_start != -1);
+			/* Traverse faces starting from the current one. */
+			int edge_first = edge_start;
 			dst_vert_faces[face_count_ordered++] = face_start;
-			if (append_start_edge) {
-				dst_vert_edges[edge_count_ordered++] = edge_start;
-			}
+			dst_vert_edges[edge_count_ordered++] = edge_start;
 			face_used[face_start] = true;
-
 			while (edge_count_ordered < num_vert_edges) {
 				IndexArray face_verts = getBaseFaceVertices(refiner, face_start);
 				IndexArray face_edges = getBaseFaceEdges(refiner, face_start);
@@ -192,24 +271,9 @@ inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::assignComponentTopolog
 				int face_edge_next = (face_edge_start > 0) ? (face_edge_start - 1) : (face_verts.size() - 1);
 				Index edge_next = face_edges[face_edge_next];
 				if (edge_next == edge_first) {
-					/* TODO(sergey): Find more generic solution so non-manifold
-					 * edges combined with some manifold adjacent geometry is
-					 * handled correct.
+					/* Multiple manifolds found, stop for now and handle rest
+					 * in the next iteration.
 					 */
-					if (num_vert_edges == num_vert_faces &&
-					    edge_count_ordered != num_vert_edges)
-					{
-						IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_next);
-						for (int i = 0; i < num_vert_faces; ++i) {
-							int face_start = edge_faces[i];
-							if (!face_used[face_start]) {
-								int edge_start = edge_next;
-								int face_vert_start = findInArray(getBaseFaceVertices(refiner, face_start), vert);
-								stack.push(StackElem(face_start, edge_start, face_vert_start, false));
-								break;
-							}
-						}
-					}
 					break;
 				}
 				dst_vert_edges[edge_count_ordered++] = edge_next;
@@ -221,16 +285,6 @@ inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::assignComponentTopolog
 						break;
 					}
 					else if (edge_faces.size() != 2) {
-						for (int i = 0; i < edge_faces.size(); ++i) {
-							if (edge_faces[i] != face_start) {
-								int face_start = edge_faces[i];
-								if (!face_used[face_start]) {
-									int edge_start = edge_next;
-									int face_vert_start = findInArray(getBaseFaceVertices(refiner, face_start), vert);
-									stack.push(StackElem(face_start, edge_start, face_vert_start, false));
-								}
-							}
-						}
 						break;
 					}
 					assert(edge_faces.size() == 2);
@@ -242,45 +296,36 @@ inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::assignComponentTopolog
 				edge_start = edge_next;
 			}
 		}
-		delete [] face_used;
-
 		/* Verify ordering doesn't ruin connectivity information. */
 		assert(face_count_ordered == num_vert_faces);
 		assert(edge_count_ordered == num_vert_edges);
-#ifndef NDEBUG
-		for (int i = 0; i < num_vert_faces; ++i) {
-			bool found = false;
-			for (int j = 0; j < num_vert_faces; ++j) {
-				if (vert_faces[i] == dst_vert_faces[j]) {
-					found = true;
-					break;
-				}
-			}
-			if (!found) {
-				assert(!"vert-faces connectivity ruined");
-			}
-		}
-		for (int i = 0; i < num_vert_edges; ++i) {
-			bool found = false;
-			for (int j = 0; j < num_vert_edges; ++j) {
-				if (vert_edges[i] == dst_vert_edges[j]) {
-					found = true;
-					break;
-				}
-			}
-			if (!found) {
-				assert(!"vert-edges connectivity ruined");
-			}
+		check_oriented_vert_connectivity(num_vert_edges,
+		                                 num_vert_faces,
+		                                 vert_edges,
+		                                 vert_faces,
+		                                 &dst_vert_edges[0],
+		                                 &dst_vert_faces[0]);
+		/* For the release builds we're failing mesh construction so instead
+		 * of nasty bugs the unsupported mesh will simply disappear from the
+		 * viewport.
+		 */
+		if (face_count_ordered != num_vert_faces ||
+		    edge_count_ordered != num_vert_edges)
+		{
+			delete [] vert_edges;
+			delete [] vert_faces;
+			return false;
 		}
-#endif
 #else  /* OPENSUBDIV_ORIENT_TOPOLOGY */
 		memcpy(&dst_vert_edges[0], vert_edges, sizeof(int) * num_vert_edges);
 		memcpy(&dst_vert_faces[0], vert_faces, sizeof(int) * num_vert_faces);
 #endif  /* OPENSUBDIV_ORIENT_TOPOLOGY */
-
 		delete [] vert_edges;
 		delete [] vert_faces;
 	}
+#ifdef OPENSUBDIV_ORIENT_TOPOLOGY
+	delete [] face_used;
+#endif
 	populateBaseLocalIndices(refiner);
 	return true;
 };