48516cc80b7ccc04b1610f5f5c09fe9356286bdb
[blender.git] / intern / opensubdiv / internal / opensubdiv_converter_factory.cc
1 // Copyright 2015 Blender Foundation. All rights reserved.
2 //
3 // This program is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU General Public License
5 // as published by the Free Software Foundation; either version 2
6 // of the License, or (at your option) any later version.
7 //
8 // This program is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 // GNU General Public License for more details.
12 //
13 // You should have received a copy of the GNU General Public License
14 // along with this program; if not, write to the Free Software Foundation,
15 // Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
16 //
17 // Author: Sergey Sharybin
18
19 #ifdef _MSC_VER
20 #  include <iso646.h>
21 #endif
22
23 #include "internal/opensubdiv_converter_factory.h"
24
25 #include <cassert>
26 #include <cstdio>
27 #include <stack>
28 #include <vector>
29
30 #include <opensubdiv/far/topologyRefinerFactory.h>
31
32 #include "internal/opensubdiv_converter_internal.h"
33 #include "internal/opensubdiv_converter_orient.h"
34 #include "internal/opensubdiv_internal.h"
35 #include "opensubdiv_converter_capi.h"
36
37 struct TopologyRefinerData {
38   const OpenSubdiv_Converter* converter;
39 };
40
41 namespace OpenSubdiv {
42 namespace OPENSUBDIV_VERSION {
43 namespace Far {
44
45 template <>
46 inline bool
47 TopologyRefinerFactory<TopologyRefinerData>::resizeComponentTopology(
48     TopologyRefiner& refiner,
49     const TopologyRefinerData& cb_data) {
50   const OpenSubdiv_Converter* converter = cb_data.converter;
51   /// Faces and face-vertices.
52   const int num_faces = converter->getNumFaces(converter);
53   setNumBaseFaces(refiner, num_faces);
54   for (int face_index = 0; face_index < num_faces; ++face_index) {
55     const int num_face_vertices =
56         converter->getNumFaceVertices(converter, face_index);
57     setNumBaseFaceVertices(refiner, face_index, num_face_vertices);
58   }
59   // Edges and edge-faces.
60   const int num_edges = converter->getNumEdges(converter);
61   setNumBaseEdges(refiner, num_edges);
62   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
63     const int num_edge_faces =
64         converter->getNumEdgeFaces(converter, edge_index);
65     setNumBaseEdgeFaces(refiner, edge_index, num_edge_faces);
66   }
67   // Vertices and vertex-faces and vertex-edges.
68   const int num_vertices = converter->getNumVertices(converter);
69   setNumBaseVertices(refiner, num_vertices);
70   for (int vertex_index = 0; vertex_index < num_vertices; ++vertex_index) {
71     const int num_vert_edges =
72         converter->getNumVertexEdges(converter, vertex_index);
73     const int num_vert_faces =
74         converter->getNumVertexFaces(converter, vertex_index);
75     setNumBaseVertexEdges(refiner, vertex_index, num_vert_edges);
76     setNumBaseVertexFaces(refiner, vertex_index, num_vert_faces);
77   }
78   return true;
79 }
80
81 template <>
82 inline bool
83 TopologyRefinerFactory<TopologyRefinerData>::assignComponentTopology(
84     TopologyRefiner& refiner,
85     const TopologyRefinerData& cb_data) {
86   using Far::IndexArray;
87   const OpenSubdiv_Converter* converter = cb_data.converter;
88   // Face relations.
89   const int num_faces = converter->getNumFaces(converter);
90   for (int face_index = 0; face_index < num_faces; ++face_index) {
91     IndexArray dst_face_verts = getBaseFaceVertices(refiner, face_index);
92     converter->getFaceVertices(converter, face_index, &dst_face_verts[0]);
93     IndexArray dst_face_edges = getBaseFaceEdges(refiner, face_index);
94     converter->getFaceEdges(converter, face_index, &dst_face_edges[0]);
95   }
96   // Edge relations.
97   const int num_edges = converter->getNumEdges(converter);
98   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
99     // Edge-vertices.
100     IndexArray dst_edge_vertices = getBaseEdgeVertices(refiner, edge_index);
101     converter->getEdgeVertices(converter, edge_index, &dst_edge_vertices[0]);
102     // Edge-faces.
103     IndexArray dst_edge_faces = getBaseEdgeFaces(refiner, edge_index);
104     converter->getEdgeFaces(converter, edge_index, &dst_edge_faces[0]);
105   }
106 // TODO(sergey): Find a way to move this to an utility function.
107 #ifdef OPENSUBDIV_ORIENT_TOPOLOGY
108   // Make face normals consistent.
109   std::vector<bool> face_used(num_faces, false);
110   std::stack<int> traverse_stack;
111   int face_start = 0, num_traversed_faces = 0;
112   // Traverse all islands.
113   while (num_traversed_faces != num_faces) {
114     // Find first face of any untraversed islands.
115     while (face_used[face_start]) {
116       ++face_start;
117     }
118     // Add first face to the stack.
119     traverse_stack.push(face_start);
120     face_used[face_start] = true;
121     // Go over whole connected component.
122     while (!traverse_stack.empty()) {
123       int face = traverse_stack.top();
124       traverse_stack.pop();
125       IndexArray face_edges = getBaseFaceEdges(refiner, face);
126       ConstIndexArray face_vertices = getBaseFaceVertices(refiner, face);
127       for (int i = 0; i < face_edges.size(); ++i) {
128         const int edge = face_edges[i];
129         ConstIndexArray edge_faces = getBaseEdgeFaces(refiner, edge);
130         if (edge_faces.size() != 2) {
131           /* Can't make consistent normals for non-manifolds. */
132           continue;
133         }
134         ConstIndexArray edge_vertices = getBaseEdgeVertices(refiner, edge);
135         // Get winding of the reference face.
136         const int vert0_of_face = face_vertices.FindIndex(edge_vertices[0]);
137         const int vert1_of_face = face_vertices.FindIndex(edge_vertices[1]);
138         const int delta_face =
139             opensubdiv_capi::getLoopWinding(vert0_of_face, vert1_of_face);
140         for (int edge_face = 0; edge_face < edge_faces.size(); ++edge_face) {
141           const int other_face_index = edge_faces[edge_face];
142           // Never re-traverse faces, only move forward.
143           if (face_used[other_face_index]) {
144             continue;
145           }
146           IndexArray other_face_vertics =
147               getBaseFaceVertices(refiner, other_face_index);
148           const int vert0_of_other_face =
149               other_face_vertics.FindIndex(edge_vertices[0]);
150           const int vert1_of_other_face =
151               other_face_vertics.FindIndex(edge_vertices[1]);
152           const int delta_other_face = opensubdiv_capi::getLoopWinding(
153               vert0_of_other_face, vert1_of_other_face);
154           if (delta_face * delta_other_face > 0) {
155             IndexArray other_face_vertices =
156                 getBaseFaceVertices(refiner, other_face_index);
157             IndexArray other_face_edges =
158                 getBaseFaceEdges(refiner, other_face_index);
159             opensubdiv_capi::reverseFaceLoops(&other_face_vertices,
160                                               &other_face_edges);
161           }
162           traverse_stack.push(other_face_index);
163           face_used[other_face_index] = true;
164         }
165       }
166       ++num_traversed_faces;
167     }
168   }
169 #endif  // OPENSUBDIV_ORIENT_TOPOLOGY
170   // Vertex relations.
171   const int num_vertices = converter->getNumVertices(converter);
172   std::vector<int> vertex_faces, vertex_edges;
173   for (int vertex_index = 0; vertex_index < num_vertices; ++vertex_index) {
174     // Vertex-faces.
175     IndexArray dst_vertex_faces = getBaseVertexFaces(refiner, vertex_index);
176     const int num_vertex_faces =
177         converter->getNumVertexFaces(converter, vertex_index);
178     vertex_faces.resize(num_vertex_faces);
179     converter->getVertexFaces(converter, vertex_index, &vertex_faces[0]);
180     // Vertex-edges.
181     IndexArray dst_vertex_edges = getBaseVertexEdges(refiner, vertex_index);
182     const int num_vertex_edges =
183         converter->getNumVertexEdges(converter, vertex_index);
184     vertex_edges.resize(num_vertex_edges);
185     converter->getVertexEdges(converter, vertex_index, &vertex_edges[0]);
186 // TODO(sergey): Find a way to move this to an utility function.
187 #ifdef OPENSUBDIV_ORIENT_TOPOLOGY
188     // Order vertex edges and faces to be in a CCW order.
189     std::fill(face_used.begin(), face_used.end(), false);
190     // Number of edges and faces added to the ordered array.
191     int edge_count_ordered = 0, face_count_ordered = 0;
192     // Add loose edges straight into the edges array.
193     bool has_fan_connections = false;
194     for (int i = 0; i < num_vertex_edges; ++i) {
195       IndexArray edge_faces = getBaseEdgeFaces(refiner, vertex_edges[i]);
196       if (edge_faces.size() == 0) {
197         dst_vertex_edges[edge_count_ordered++] = vertex_edges[i];
198       } else if (edge_faces.size() > 2) {
199         has_fan_connections = true;
200       }
201     }
202     if (has_fan_connections) {
203       // OpenSubdiv currently doesn't give us clues how to handle fan face
204       // connections. and since handling such connections complicates the loop
205       // below we simply don't do special orientation for them.
206       memcpy(&dst_vertex_edges[0], &vertex_edges[0],
207              sizeof(int) * num_vertex_edges);
208       memcpy(&dst_vertex_faces[0], &vertex_faces[0],
209              sizeof(int) * num_vertex_faces);
210       continue;
211     }
212     // Perform at max numbder of vert-edges iteration and try to avoid
213     // deadlock here for malformed mesh.
214     for (int global_iter = 0; global_iter < num_vertex_edges; ++global_iter) {
215       // Number of edges and faces which are still to be ordered.
216       const int num_vertex_edges_remained =
217           num_vertex_edges - edge_count_ordered;
218       const int num_vertex_faces_remained =
219           num_vertex_faces - face_count_ordered;
220       if (num_vertex_edges_remained == 0 && num_vertex_faces_remained == 0) {
221         // All done, nothing to do anymore.
222         break;
223       }
224       // Face, edge and face-vertex index to start traversal from.
225       int face_start = -1, edge_start = -1, face_vertex_start = -1;
226       if (num_vertex_edges_remained == num_vertex_faces_remained) {
227         // Vertex is either complete manifold or is connected to several
228         // manifold islands (hourglass-like configuration), can pick up
229         // random edge unused and start from it.
230         //
231         // TODO(sergey): Start from previous edge from which traversal began at
232         // previous iteration.
233         for (int i = 0; i < num_vertex_edges; ++i) {
234           face_start = vertex_faces[i];
235           if (!face_used[face_start]) {
236             ConstIndexArray face_vertices =
237                 getBaseFaceVertices(refiner, face_start);
238             ConstIndexArray face_edges = getBaseFaceEdges(refiner, face_start);
239             face_vertex_start = face_vertices.FindIndex(vertex_index);
240             edge_start = face_edges[face_vertex_start];
241             break;
242           }
243         }
244       } else {
245         // Special handle of non-manifold vertex.
246         for (int i = 0; i < num_vertex_edges; ++i) {
247           edge_start = vertex_edges[i];
248           IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_start);
249           if (edge_faces.size() == 1) {
250             face_start = edge_faces[0];
251             if (!face_used[face_start]) {
252               ConstIndexArray face_vertices =
253                   getBaseFaceVertices(refiner, face_start);
254               ConstIndexArray face_edges =
255                   getBaseFaceEdges(refiner, face_start);
256               face_vertex_start = face_vertices.FindIndex(vertex_index);
257               if (edge_start == face_edges[face_vertex_start]) {
258                 break;
259               }
260             }
261           }
262           // Reset indices for sanity check below.
263           face_start = edge_start = face_vertex_start = -1;
264         }
265       }
266       // Sanity check.
267       assert(face_start != -1);
268       assert(edge_start != -1);
269       assert(face_vertex_start != -1);
270       // Traverse faces starting from the current one. */
271       int edge_first = edge_start;
272       dst_vertex_faces[face_count_ordered++] = face_start;
273       dst_vertex_edges[edge_count_ordered++] = edge_start;
274       face_used[face_start] = true;
275       while (edge_count_ordered < num_vertex_edges) {
276         IndexArray face_vertices = getBaseFaceVertices(refiner, face_start);
277         IndexArray face_edges = getBaseFaceEdges(refiner, face_start);
278         int face_edge_start = face_vertex_start;
279         int face_edge_next = (face_edge_start > 0) ? (face_edge_start - 1)
280                                                    : (face_vertices.size() - 1);
281         Index edge_next = face_edges[face_edge_next];
282         if (edge_next == edge_first) {
283           // Multiple manifolds found, stop for now and handle rest
284           // in the next iteration.
285           break;
286         }
287         dst_vertex_edges[edge_count_ordered++] = edge_next;
288         if (face_count_ordered < num_vertex_faces) {
289           IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_next);
290           assert(edge_faces.size() != 0);
291           if (edge_faces.size() == 1) {
292             assert(edge_faces[0] == face_start);
293             break;
294           } else if (edge_faces.size() != 2) {
295             break;
296           }
297           assert(edge_faces.size() == 2);
298           face_start = edge_faces[(edge_faces[0] == face_start) ? 1 : 0];
299           face_vertex_start =
300               getBaseFaceEdges(refiner, face_start).FindIndex(edge_next);
301           dst_vertex_faces[face_count_ordered++] = face_start;
302           face_used[face_start] = true;
303         }
304         edge_start = edge_next;
305       }
306     }
307     // Verify ordering doesn't ruin connectivity information.
308     assert(face_count_ordered == num_vertex_faces);
309     assert(edge_count_ordered == num_vertex_edges);
310     opensubdiv_capi::checkOrientedVertexConnectivity(
311         num_vertex_edges, num_vertex_faces, &vertex_edges[0], &vertex_faces[0],
312         &dst_vertex_edges[0], &dst_vertex_faces[0]);
313     // For the release builds we're failing mesh construction so instead of
314     // nasty bugs the unsupported mesh will simply disappear from the viewport.
315     if (face_count_ordered != num_vertex_faces ||
316         edge_count_ordered != num_vertex_edges) {
317       return false;
318     }
319 #else   // OPENSUBDIV_ORIENT_TOPOLOGY
320     memcpy(&dst_vertex_edges[0], &vertex_edges[0],
321            sizeof(int) * num_vertex_edges);
322     memcpy(&dst_vertex_faces[0], &vertex_faces[0],
323            sizeof(int) * num_vertex_faces);
324 #endif  // OPENSUBDIV_ORIENT_TOPOLOGY
325   }
326   populateBaseLocalIndices(refiner);
327   return true;
328 }
329
330 template <>
331 inline bool TopologyRefinerFactory<TopologyRefinerData>::assignComponentTags(
332     TopologyRefiner& refiner,
333     const TopologyRefinerData& cb_data) {
334   using OpenSubdiv::Sdc::Crease;
335   const OpenSubdiv_Converter* converter = cb_data.converter;
336   const int num_edges = converter->getNumEdges(converter);
337   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
338     const float sharpness =
339         opensubdiv_capi::getCompatibleEdgeSharpness(converter, edge_index);
340     setBaseEdgeSharpness(refiner, edge_index, sharpness);
341   }
342   // OpenSubdiv expects non-manifold vertices to be sharp but at the time it
343   // handles correct cases when vertex is a corner of plane. Currently mark
344   // vertices which are adjacent to a loose edge as sharp, but this decision
345   // needs some more investigation.
346   const int num_vertices = converter->getNumVertices(converter);
347   for (int vertex_index = 0; vertex_index < num_vertices; ++vertex_index) {
348     ConstIndexArray vertex_edges = getBaseVertexEdges(refiner, vertex_index);
349     for (int i = 0; i < vertex_edges.size(); ++i) {
350       const int edge_index = vertex_edges[i];
351       ConstIndexArray edge_faces = getBaseEdgeFaces(refiner, edge_index);
352       if (edge_faces.size() == 0) {
353         setBaseVertexSharpness(refiner, vertex_index,
354                                Crease::SHARPNESS_INFINITE);
355         break;
356       }
357     }
358     if (vertex_edges.size() == 2) {
359       const int edge0 = vertex_edges[0], edge1 = vertex_edges[1];
360       const float sharpness0 = converter->getEdgeSharpness(converter, edge0);
361       const float sharpness1 = converter->getEdgeSharpness(converter, edge1);
362       const float sharpness = std::min(sharpness0, sharpness1);
363       setBaseVertexSharpness(refiner, vertex_index, sharpness);
364     }
365   }
366   return true;
367 }
368
369 template <>
370 inline bool
371 TopologyRefinerFactory<TopologyRefinerData>::assignFaceVaryingTopology(
372     TopologyRefiner& refiner,
373     const TopologyRefinerData& cb_data) {
374   const OpenSubdiv_Converter* converter = cb_data.converter;
375   const int num_layers = converter->getNumUVLayers(converter);
376   if (num_layers <= 0) {
377     // No UV maps, we can skip any face-varying data.
378     return true;
379   }
380   const int num_faces = getNumBaseFaces(refiner);
381   for (int layer_index = 0; layer_index < num_layers; ++layer_index) {
382     converter->precalcUVLayer(converter, layer_index);
383     const int num_uvs = converter->getNumUVCoordinates(converter);
384     // Fill in per-corner index of the UV.
385     const int channel = createBaseFVarChannel(refiner, num_uvs);
386     // TODO(sergey): Need to check whether converter changed the winding of
387     // face to match OpenSubdiv's expectations.
388     for (int face_index = 0; face_index < num_faces; ++face_index) {
389       Far::IndexArray dst_face_uvs =
390           getBaseFaceFVarValues(refiner, face_index, channel);
391       for (int corner = 0; corner < dst_face_uvs.size(); ++corner) {
392         const int uv_index =
393            converter->getFaceCornerUVIndex(converter, face_index, corner);
394         dst_face_uvs[corner] = uv_index;
395       }
396     }
397     converter->finishUVLayer(converter);
398   }
399   return true;
400 }
401
402 template <>
403 inline void TopologyRefinerFactory<TopologyRefinerData>::reportInvalidTopology(
404     TopologyError /*errCode*/, const char* msg,
405     const TopologyRefinerData& /*mesh*/) {
406   printf("OpenSubdiv Error: %s\n", msg);
407 }
408
409 } /* namespace Far */
410 } /* namespace OPENSUBDIV_VERSION */
411 } /* namespace OpenSubdiv */
412
413 namespace opensubdiv_capi {
414
415 OpenSubdiv::Far::TopologyRefiner* createOSDTopologyRefinerFromConverter(
416     OpenSubdiv_Converter* converter) {
417   using OpenSubdiv::Sdc::Options;
418   using OpenSubdiv::Far::TopologyRefinerFactory;
419   const OpenSubdiv::Sdc::SchemeType scheme_type =
420       getSchemeTypeFromCAPI(converter->getSchemeType(converter));
421   const Options::FVarLinearInterpolation linear_interpolation =
422       getFVarLinearInterpolationFromCAPI(
423           converter->getFVarLinearInterpolation(converter));
424   Options options;
425   options.SetVtxBoundaryInterpolation(Options::VTX_BOUNDARY_EDGE_ONLY);
426   options.SetCreasingMethod(Options::CREASE_UNIFORM);
427   options.SetFVarLinearInterpolation(linear_interpolation);
428
429   TopologyRefinerFactory<TopologyRefinerData>::Options topology_options(
430       scheme_type, options);
431 #ifdef OPENSUBDIV_VALIDATE_TOPOLOGY
432   topology_options.validateFullTopology = true;
433 #endif
434   TopologyRefinerData cb_data;
435   cb_data.converter = converter;
436   return TopologyRefinerFactory<TopologyRefinerData>::Create(
437       cb_data, topology_options);
438 }
439
440 }  // namespace opensubdiv_capi