[Bf-blender-cvs] [dd1e7f1] master: OpenSubdiv: Work on better vert edge/face orientation code
Sergey Sharybin
noreply at git.blender.org
Mon Aug 3 14:57:49 CEST 2015
Commit: dd1e7f16ca2fd74c93937fac9009f52db2205f19
Author: Sergey Sharybin
Date: Mon Aug 3 13:20:41 2015 +0200
Branches: master
https://developer.blender.org/rBdd1e7f16ca2fd74c93937fac9009f52db2205f19
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.
===================================================================
M intern/opensubdiv/opensubdiv_converter.cc
===================================================================
diff --git a/intern/opensubdiv/opensubdiv_converter.cc b/intern/opensubdiv/opensubdiv_converter.cc
index 119a7bf..117edc4 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 = findI
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list