diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2015-08-03 14:20:41 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2015-08-03 15:27:31 +0300 |
commit | dd1e7f16ca2fd74c93937fac9009f52db2205f19 (patch) | |
tree | be956bec809c4297fc0f9e516bd45d61b6dd567c /intern | |
parent | c2c4e02d4188347aafb5be173be482a21c17b5f2 (diff) |
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.
Diffstat (limited to 'intern')
-rw-r--r-- | intern/opensubdiv/opensubdiv_converter.cc | 267 |
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; }; |