diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2015-07-29 18:10:13 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2015-07-29 18:13:15 +0300 |
commit | b8e2b8ae8a65824ebe8a69d20971b5ad8474a875 (patch) | |
tree | 2cb0b8edf1e81da3a620fa437ec337c9488c4158 /intern/opensubdiv | |
parent | af6bbab5b485c83c20c0819f7171d3224e38b1e3 (diff) |
OpenSubdiv: Rework vert-edge and vert-face ordering
Now the code survives multiple non-manifolds happening on the vert.
Still not totally optimal but at least gives much better mesh support.
Diffstat (limited to 'intern/opensubdiv')
-rw-r--r-- | intern/opensubdiv/opensubdiv_converter.cc | 155 |
1 files changed, 126 insertions, 29 deletions
diff --git a/intern/opensubdiv/opensubdiv_converter.cc b/intern/opensubdiv/opensubdiv_converter.cc index 5ae9a6ea066..34ff17c3851 100644 --- a/intern/opensubdiv/opensubdiv_converter.cc +++ b/intern/opensubdiv/opensubdiv_converter.cc @@ -35,6 +35,8 @@ #include "opensubdiv_converter_capi.h" #include "opensubdiv_intern.h" +#include <stack> + namespace OpenSubdiv { namespace OPENSUBDIV_VERSION { namespace Far { @@ -49,6 +51,21 @@ inline int findInArray(T array, int value) } /* namespace */ +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; +}; + template <> inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::resizeComponentTopology( TopologyRefiner& refiner, @@ -118,45 +135,124 @@ inline bool TopologyRefinerFactory<OpenSubdiv_Converter>::assignComponentTopolog int *vert_edges = new int[num_vert_edges]; conv.get_vert_edges(&conv, vert, vert_edges); /* Order vertex edges and faces in a CCW order. */ - Index face_start = INDEX_INVALID; - Index edge_start = INDEX_INVALID; - int face_vert_start = 0; + /* TODO(sergey): Look into possible optimizations here. */ + bool *face_used = new bool[num_faces]; + memset(face_used, 0, sizeof(bool) * num_faces); + std::stack<StackElem> stack; + int edge_count_ordered = 0, face_count_ordered = 0; if (num_vert_edges == num_vert_faces) { - face_start = vert_faces[0]; - face_vert_start = findInArray(getBaseFaceVertices(refiner, face_start), vert); - edge_start = getBaseFaceEdges(refiner, face_start)[face_vert_start]; - } else { + /* 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)); + } + 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() == 1) { - edge_start = vert_edges[i]; - face_start = edge_faces[0]; - face_vert_start = findInArray(getBaseFaceVertices(refiner, face_start), vert); + 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]; + } + 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; + } + } + } + } + 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; + + dst_vert_faces[face_count_ordered++] = face_start; + if (append_start_edge) { + dst_vert_edges[edge_count_ordered++] = edge_start; + } + + while (edge_count_ordered < num_vert_edges) { + IndexArray face_verts = getBaseFaceVertices(refiner, face_start); + IndexArray face_edges = getBaseFaceEdges(refiner, face_start); + int face_edge_start = face_vert_start; + 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) { + break; + } + dst_vert_edges[edge_count_ordered++] = edge_next; + if (face_count_ordered < num_vert_faces) { + IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_next); + assert(edge_faces.size() != 0); + if (edge_faces.size() == 1) { + assert(edge_faces[0] == face_start); + 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)); + face_used[face_start] = true; + } + } + } break; } + assert(edge_faces.size() == 2); + face_start = edge_faces[(edge_faces[0] == face_start) ? 1 : 0]; + face_vert_start = findInArray(getBaseFaceEdges(refiner, face_start), edge_next); + dst_vert_faces[face_count_ordered++] = face_start; } + edge_start = edge_next; } } - int edge_count_ordered = 1; - int face_count_ordered = 1; - dst_vert_faces[0] = face_start; - dst_vert_edges[0] = edge_start; - while (edge_count_ordered < num_vert_edges) { - IndexArray fVerts = getBaseFaceVertices(refiner, face_start); - IndexArray fEdges = getBaseFaceEdges(refiner, face_start); - int feStart = face_vert_start; - int feNext = feStart ? (feStart - 1) : (fVerts.size() - 1); - Index eNext = fEdges[feNext]; - dst_vert_edges[edge_count_ordered++] = eNext; - if (face_count_ordered < num_vert_faces) { - IndexArray edge_faces = getBaseEdgeFaces(refiner, eNext); - face_start = edge_faces[edge_faces[0] == face_start]; - face_vert_start = findInArray(getBaseFaceEdges(refiner, face_start), eNext); - dst_vert_faces[face_count_ordered++] = face_start; + 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"); } - edge_start = eNext; } + 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"); + } + } +#endif delete [] vert_edges; delete [] vert_faces; @@ -216,7 +312,8 @@ struct OpenSubdiv_TopologyRefinerDescr *openSubdiv_createTopologyRefinerDescr( OpenSubdiv::Sdc::SchemeType scheme_type = get_capi_scheme_type(converter->get_type(converter)); OpenSubdiv::Sdc::Options options; - options.SetVtxBoundaryInterpolation(OpenSubdiv::Sdc::Options::VTX_BOUNDARY_EDGE_AND_CORNER); + options.SetVtxBoundaryInterpolation(OpenSubdiv::Sdc::Options::VTX_BOUNDARY_EDGE_ONLY); + options.SetCreasingMethod(OpenSubdiv::Sdc::Options::CREASE_UNIFORM); options.SetFVarLinearInterpolation(OpenSubdiv::Sdc::Options::FVAR_LINEAR_ALL); TopologyRefinerFactory<OpenSubdiv_Converter>::Options |