Merge branch 'blender2.7'
[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   // Vertices.
60   const int num_vertices = converter->getNumVertices(converter);
61   setNumBaseVertices(refiner, num_vertices);
62   // If converter does not provide full topology, we are done.
63   if (!converter->specifiesFullTopology(converter)) {
64     return true;
65   }
66   // Edges and edge-faces.
67   const int num_edges = converter->getNumEdges(converter);
68   setNumBaseEdges(refiner, num_edges);
69   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
70     const int num_edge_faces =
71         converter->getNumEdgeFaces(converter, edge_index);
72     setNumBaseEdgeFaces(refiner, edge_index, num_edge_faces);
73   }
74   // Vertex-faces and vertex-edges.
75   for (int vertex_index = 0; vertex_index < num_vertices; ++vertex_index) {
76     const int num_vert_edges =
77         converter->getNumVertexEdges(converter, vertex_index);
78     const int num_vert_faces =
79         converter->getNumVertexFaces(converter, vertex_index);
80     setNumBaseVertexEdges(refiner, vertex_index, num_vert_edges);
81     setNumBaseVertexFaces(refiner, vertex_index, num_vert_faces);
82   }
83   return true;
84 }
85
86 template <>
87 inline bool
88 TopologyRefinerFactory<TopologyRefinerData>::assignComponentTopology(
89     TopologyRefiner& refiner,
90     const TopologyRefinerData& cb_data) {
91   using Far::IndexArray;
92   const OpenSubdiv_Converter* converter = cb_data.converter;
93   const bool full_topology_specified =
94           converter->specifiesFullTopology(converter);
95   // Face relations.
96   const int num_faces = converter->getNumFaces(converter);
97   for (int face_index = 0; face_index < num_faces; ++face_index) {
98     IndexArray dst_face_verts = getBaseFaceVertices(refiner, face_index);
99     converter->getFaceVertices(converter, face_index, &dst_face_verts[0]);
100     if (full_topology_specified) {
101       IndexArray dst_face_edges = getBaseFaceEdges(refiner, face_index);
102       converter->getFaceEdges(converter, face_index, &dst_face_edges[0]);
103     }
104   }
105   // If converter does not provide full topology, we are done.
106   if (!full_topology_specified) {
107     return true;
108   }
109   // Edge relations.
110   const int num_edges = converter->getNumEdges(converter);
111   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
112     // Edge-vertices.
113     IndexArray dst_edge_vertices = getBaseEdgeVertices(refiner, edge_index);
114     converter->getEdgeVertices(converter, edge_index, &dst_edge_vertices[0]);
115     // Edge-faces.
116     IndexArray dst_edge_faces = getBaseEdgeFaces(refiner, edge_index);
117     converter->getEdgeFaces(converter, edge_index, &dst_edge_faces[0]);
118   }
119   // TODO(sergey): Find a way to move this to an utility function.
120 #ifdef OPENSUBDIV_ORIENT_TOPOLOGY
121   // Make face normals consistent.
122   std::vector<bool> face_used(num_faces, false);
123   std::stack<int> traverse_stack;
124   int face_start = 0, num_traversed_faces = 0;
125   // Traverse all islands.
126   while (num_traversed_faces != num_faces) {
127     // Find first face of any untraversed islands.
128     while (face_used[face_start]) {
129       ++face_start;
130     }
131     // Add first face to the stack.
132     traverse_stack.push(face_start);
133     face_used[face_start] = true;
134     // Go over whole connected component.
135     while (!traverse_stack.empty()) {
136       int face = traverse_stack.top();
137       traverse_stack.pop();
138       IndexArray face_edges = getBaseFaceEdges(refiner, face);
139       ConstIndexArray face_vertices = getBaseFaceVertices(refiner, face);
140       for (int i = 0; i < face_edges.size(); ++i) {
141         const int edge = face_edges[i];
142         ConstIndexArray edge_faces = getBaseEdgeFaces(refiner, edge);
143         if (edge_faces.size() != 2) {
144           /* Can't make consistent normals for non-manifolds. */
145           continue;
146         }
147         ConstIndexArray edge_vertices = getBaseEdgeVertices(refiner, edge);
148         // Get winding of the reference face.
149         const int vert0_of_face = face_vertices.FindIndex(edge_vertices[0]);
150         const int vert1_of_face = face_vertices.FindIndex(edge_vertices[1]);
151         const int delta_face =
152             opensubdiv_capi::getLoopWinding(vert0_of_face, vert1_of_face);
153         for (int edge_face = 0; edge_face < edge_faces.size(); ++edge_face) {
154           const int other_face_index = edge_faces[edge_face];
155           // Never re-traverse faces, only move forward.
156           if (face_used[other_face_index]) {
157             continue;
158           }
159           IndexArray other_face_vertics =
160               getBaseFaceVertices(refiner, other_face_index);
161           const int vert0_of_other_face =
162               other_face_vertics.FindIndex(edge_vertices[0]);
163           const int vert1_of_other_face =
164               other_face_vertics.FindIndex(edge_vertices[1]);
165           const int delta_other_face = opensubdiv_capi::getLoopWinding(
166               vert0_of_other_face, vert1_of_other_face);
167           if (delta_face * delta_other_face > 0) {
168             IndexArray other_face_vertices =
169                 getBaseFaceVertices(refiner, other_face_index);
170             IndexArray other_face_edges =
171                 getBaseFaceEdges(refiner, other_face_index);
172             opensubdiv_capi::reverseFaceLoops(&other_face_vertices,
173                                               &other_face_edges);
174           }
175           traverse_stack.push(other_face_index);
176           face_used[other_face_index] = true;
177         }
178       }
179       ++num_traversed_faces;
180     }
181   }
182 #endif  // OPENSUBDIV_ORIENT_TOPOLOGY
183   // Vertex relations.
184   const int num_vertices = converter->getNumVertices(converter);
185   std::vector<int> vertex_faces, vertex_edges;
186   for (int vertex_index = 0; vertex_index < num_vertices; ++vertex_index) {
187     // Vertex-faces.
188     IndexArray dst_vertex_faces = getBaseVertexFaces(refiner, vertex_index);
189     const int num_vertex_faces =
190         converter->getNumVertexFaces(converter, vertex_index);
191     vertex_faces.resize(num_vertex_faces);
192     converter->getVertexFaces(converter, vertex_index, &vertex_faces[0]);
193     // Vertex-edges.
194     IndexArray dst_vertex_edges = getBaseVertexEdges(refiner, vertex_index);
195     const int num_vertex_edges =
196         converter->getNumVertexEdges(converter, vertex_index);
197     vertex_edges.resize(num_vertex_edges);
198     converter->getVertexEdges(converter, vertex_index, &vertex_edges[0]);
199 // TODO(sergey): Find a way to move this to an utility function.
200 #ifdef OPENSUBDIV_ORIENT_TOPOLOGY
201     // Order vertex edges and faces to be in a CCW order.
202     std::fill(face_used.begin(), face_used.end(), false);
203     // Number of edges and faces added to the ordered array.
204     int edge_count_ordered = 0, face_count_ordered = 0;
205     // Add loose edges straight into the edges array.
206     bool has_fan_connections = false;
207     for (int i = 0; i < num_vertex_edges; ++i) {
208       IndexArray edge_faces = getBaseEdgeFaces(refiner, vertex_edges[i]);
209       if (edge_faces.size() == 0) {
210         dst_vertex_edges[edge_count_ordered++] = vertex_edges[i];
211       } else if (edge_faces.size() > 2) {
212         has_fan_connections = true;
213       }
214     }
215     if (has_fan_connections) {
216       // OpenSubdiv currently doesn't give us clues how to handle fan face
217       // connections. and since handling such connections complicates the loop
218       // below we simply don't do special orientation for them.
219       memcpy(&dst_vertex_edges[0], &vertex_edges[0],
220              sizeof(int) * num_vertex_edges);
221       memcpy(&dst_vertex_faces[0], &vertex_faces[0],
222              sizeof(int) * num_vertex_faces);
223       continue;
224     }
225     // Perform at max numbder of vert-edges iteration and try to avoid
226     // deadlock here for malformed mesh.
227     for (int global_iter = 0; global_iter < num_vertex_edges; ++global_iter) {
228       // Number of edges and faces which are still to be ordered.
229       const int num_vertex_edges_remained =
230           num_vertex_edges - edge_count_ordered;
231       const int num_vertex_faces_remained =
232           num_vertex_faces - face_count_ordered;
233       if (num_vertex_edges_remained == 0 && num_vertex_faces_remained == 0) {
234         // All done, nothing to do anymore.
235         break;
236       }
237       // Face, edge and face-vertex index to start traversal from.
238       int face_start = -1, edge_start = -1, face_vertex_start = -1;
239       if (num_vertex_edges_remained == num_vertex_faces_remained) {
240         // Vertex is either complete manifold or is connected to several
241         // manifold islands (hourglass-like configuration), can pick up
242         // random edge unused and start from it.
243         //
244         // TODO(sergey): Start from previous edge from which traversal began at
245         // previous iteration.
246         for (int i = 0; i < num_vertex_edges; ++i) {
247           face_start = vertex_faces[i];
248           if (!face_used[face_start]) {
249             ConstIndexArray face_vertices =
250                 getBaseFaceVertices(refiner, face_start);
251             ConstIndexArray face_edges = getBaseFaceEdges(refiner, face_start);
252             face_vertex_start = face_vertices.FindIndex(vertex_index);
253             edge_start = face_edges[face_vertex_start];
254             break;
255           }
256         }
257       } else {
258         // Special handle of non-manifold vertex.
259         for (int i = 0; i < num_vertex_edges; ++i) {
260           edge_start = vertex_edges[i];
261           IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_start);
262           if (edge_faces.size() == 1) {
263             face_start = edge_faces[0];
264             if (!face_used[face_start]) {
265               ConstIndexArray face_vertices =
266                   getBaseFaceVertices(refiner, face_start);
267               ConstIndexArray face_edges =
268                   getBaseFaceEdges(refiner, face_start);
269               face_vertex_start = face_vertices.FindIndex(vertex_index);
270               if (edge_start == face_edges[face_vertex_start]) {
271                 break;
272               }
273             }
274           }
275           // Reset indices for sanity check below.
276           face_start = edge_start = face_vertex_start = -1;
277         }
278       }
279       // Sanity check.
280       assert(face_start != -1);
281       assert(edge_start != -1);
282       assert(face_vertex_start != -1);
283       // Traverse faces starting from the current one. */
284       int edge_first = edge_start;
285       dst_vertex_faces[face_count_ordered++] = face_start;
286       dst_vertex_edges[edge_count_ordered++] = edge_start;
287       face_used[face_start] = true;
288       while (edge_count_ordered < num_vertex_edges) {
289         IndexArray face_vertices = getBaseFaceVertices(refiner, face_start);
290         IndexArray face_edges = getBaseFaceEdges(refiner, face_start);
291         int face_edge_start = face_vertex_start;
292         int face_edge_next = (face_edge_start > 0) ? (face_edge_start - 1)
293                                                    : (face_vertices.size() - 1);
294         Index edge_next = face_edges[face_edge_next];
295         if (edge_next == edge_first) {
296           // Multiple manifolds found, stop for now and handle rest
297           // in the next iteration.
298           break;
299         }
300         dst_vertex_edges[edge_count_ordered++] = edge_next;
301         if (face_count_ordered < num_vertex_faces) {
302           IndexArray edge_faces = getBaseEdgeFaces(refiner, edge_next);
303           assert(edge_faces.size() != 0);
304           if (edge_faces.size() == 1) {
305             assert(edge_faces[0] == face_start);
306             break;
307           } else if (edge_faces.size() != 2) {
308             break;
309           }
310           assert(edge_faces.size() == 2);
311           face_start = edge_faces[(edge_faces[0] == face_start) ? 1 : 0];
312           face_vertex_start =
313               getBaseFaceEdges(refiner, face_start).FindIndex(edge_next);
314           dst_vertex_faces[face_count_ordered++] = face_start;
315           face_used[face_start] = true;
316         }
317         edge_start = edge_next;
318       }
319     }
320     // Verify ordering doesn't ruin connectivity information.
321     assert(face_count_ordered == num_vertex_faces);
322     assert(edge_count_ordered == num_vertex_edges);
323     opensubdiv_capi::checkOrientedVertexConnectivity(
324         num_vertex_edges, num_vertex_faces, &vertex_edges[0], &vertex_faces[0],
325         &dst_vertex_edges[0], &dst_vertex_faces[0]);
326     // For the release builds we're failing mesh construction so instead of
327     // nasty bugs the unsupported mesh will simply disappear from the viewport.
328     if (face_count_ordered != num_vertex_faces ||
329         edge_count_ordered != num_vertex_edges) {
330       return false;
331     }
332 #else   // OPENSUBDIV_ORIENT_TOPOLOGY
333     memcpy(&dst_vertex_edges[0], &vertex_edges[0],
334            sizeof(int) * num_vertex_edges);
335     memcpy(&dst_vertex_faces[0], &vertex_faces[0],
336            sizeof(int) * num_vertex_faces);
337 #endif  // OPENSUBDIV_ORIENT_TOPOLOGY
338   }
339   populateBaseLocalIndices(refiner);
340   return true;
341 }
342
343 template <>
344 inline bool TopologyRefinerFactory<TopologyRefinerData>::assignComponentTags(
345     TopologyRefiner& refiner,
346     const TopologyRefinerData& cb_data) {
347   using OpenSubdiv::Sdc::Crease;
348   const OpenSubdiv_Converter* converter = cb_data.converter;
349   const bool full_topology_specified =
350           converter->specifiesFullTopology(converter);
351   const int num_edges = converter->getNumEdges(converter);
352   for (int edge_index = 0; edge_index < num_edges; ++edge_index) {
353     const float sharpness =
354         converter->getEdgeSharpness(converter, edge_index);
355     if (sharpness < 1e-6f) {
356       continue;
357     }
358     if (full_topology_specified) {
359       setBaseEdgeSharpness(refiner, edge_index, sharpness);
360     } else {
361       int edge_vertices[2];
362       converter->getEdgeVertices(converter, edge_index, edge_vertices);
363       const int base_edge_index = findBaseEdge(
364           refiner, edge_vertices[0], edge_vertices[1]);
365       if (base_edge_index == OpenSubdiv::Far::INDEX_INVALID) {
366         printf("OpenSubdiv Error: failed to find reconstructed edge\n");
367         return false;
368       }
369       setBaseEdgeSharpness(refiner, base_edge_index, sharpness);
370     }
371   }
372   // OpenSubdiv expects non-manifold vertices to be sharp but at the time it
373   // handles correct cases when vertex is a corner of plane. Currently mark
374   // vertices which are adjacent to a loose edge as sharp, but this decision
375   // needs some more investigation.
376   const int num_vertices = converter->getNumVertices(converter);
377   for (int vertex_index = 0; vertex_index < num_vertices; ++vertex_index) {
378     ConstIndexArray vertex_edges = getBaseVertexEdges(refiner, vertex_index);
379     if (converter->isInfiniteSharpVertex(converter, vertex_index)) {
380       setBaseVertexSharpness(
381           refiner, vertex_index, Crease::SHARPNESS_INFINITE);
382       continue;
383     }
384     float sharpness = converter->getVertexSharpness(converter, vertex_index);
385     if (vertex_edges.size() == 2) {
386       const int edge0 = vertex_edges[0], edge1 = vertex_edges[1];
387       const float sharpness0 = refiner._levels[0]->getEdgeSharpness(edge0);
388       const float sharpness1 = refiner._levels[0]->getEdgeSharpness(edge1);
389       // TODO(sergey): Find a better mixing between edge and vertex sharpness.
390       sharpness += std::min(sharpness0, sharpness1);
391       sharpness = std::min(sharpness, 1.0f);
392     }
393     setBaseVertexSharpness(refiner, vertex_index, sharpness);
394   }
395   return true;
396 }
397
398 template <>
399 inline bool
400 TopologyRefinerFactory<TopologyRefinerData>::assignFaceVaryingTopology(
401     TopologyRefiner& refiner,
402     const TopologyRefinerData& cb_data) {
403   const OpenSubdiv_Converter* converter = cb_data.converter;
404   const int num_layers = converter->getNumUVLayers(converter);
405   if (num_layers <= 0) {
406     // No UV maps, we can skip any face-varying data.
407     return true;
408   }
409   const int num_faces = getNumBaseFaces(refiner);
410   for (int layer_index = 0; layer_index < num_layers; ++layer_index) {
411     converter->precalcUVLayer(converter, layer_index);
412     const int num_uvs = converter->getNumUVCoordinates(converter);
413     // Fill in per-corner index of the UV.
414     const int channel = createBaseFVarChannel(refiner, num_uvs);
415     // TODO(sergey): Need to check whether converter changed the winding of
416     // face to match OpenSubdiv's expectations.
417     for (int face_index = 0; face_index < num_faces; ++face_index) {
418       Far::IndexArray dst_face_uvs =
419           getBaseFaceFVarValues(refiner, face_index, channel);
420       for (int corner = 0; corner < dst_face_uvs.size(); ++corner) {
421         const int uv_index =
422            converter->getFaceCornerUVIndex(converter, face_index, corner);
423         dst_face_uvs[corner] = uv_index;
424       }
425     }
426     converter->finishUVLayer(converter);
427   }
428   return true;
429 }
430
431 template <>
432 inline void TopologyRefinerFactory<TopologyRefinerData>::reportInvalidTopology(
433     TopologyError /*errCode*/, const char* msg,
434     const TopologyRefinerData& /*mesh*/) {
435   printf("OpenSubdiv Error: %s\n", msg);
436 }
437
438 } /* namespace Far */
439 } /* namespace OPENSUBDIV_VERSION */
440 } /* namespace OpenSubdiv */
441
442 namespace opensubdiv_capi {
443
444 namespace {
445
446 OpenSubdiv::Sdc::Options::VtxBoundaryInterpolation
447 getVtxBoundaryInterpolationFromCAPI(
448     OpenSubdiv_VtxBoundaryInterpolation boundary_interpolation) {
449   using OpenSubdiv::Sdc::Options;
450   switch (boundary_interpolation) {
451     case OSD_VTX_BOUNDARY_NONE:
452       return Options::VTX_BOUNDARY_NONE;
453     case OSD_VTX_BOUNDARY_EDGE_ONLY:
454       return Options::VTX_BOUNDARY_EDGE_ONLY;
455     case OSD_VTX_BOUNDARY_EDGE_AND_CORNER:
456       return Options::VTX_BOUNDARY_EDGE_AND_CORNER;
457   }
458   assert(!"Unknown veretx boundary interpolation.");
459   return Options::VTX_BOUNDARY_EDGE_ONLY;
460 }
461
462 }  // namespace
463
464 OpenSubdiv::Far::TopologyRefiner* createOSDTopologyRefinerFromConverter(
465     OpenSubdiv_Converter* converter) {
466   using OpenSubdiv::Sdc::Options;
467   using OpenSubdiv::Far::TopologyRefinerFactory;
468   const OpenSubdiv::Sdc::SchemeType scheme_type =
469       getSchemeTypeFromCAPI(converter->getSchemeType(converter));
470   const Options::FVarLinearInterpolation linear_interpolation =
471       getFVarLinearInterpolationFromCAPI(
472           converter->getFVarLinearInterpolation(converter));
473   Options options;
474   options.SetVtxBoundaryInterpolation(
475       getVtxBoundaryInterpolationFromCAPI(
476           converter->getVtxBoundaryInterpolation(converter)));
477   options.SetCreasingMethod(Options::CREASE_UNIFORM);
478   options.SetFVarLinearInterpolation(linear_interpolation);
479
480   TopologyRefinerFactory<TopologyRefinerData>::Options topology_options(
481       scheme_type, options);
482 #ifdef OPENSUBDIV_VALIDATE_TOPOLOGY
483   topology_options.validateFullTopology = true;
484 #endif
485   TopologyRefinerData cb_data;
486   cb_data.converter = converter;
487   return TopologyRefinerFactory<TopologyRefinerData>::Create(
488       cb_data, topology_options);
489 }
490
491 }  // namespace opensubdiv_capi