Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / subdiv_converter_mesh.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2018 by Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Sergey Sharybin.
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/subdiv_converter_mesh.c
27  *  \ingroup bke
28  */
29
30 #include "subdiv_converter.h"
31
32 #include <string.h>
33
34 #include "DNA_mesh_types.h"
35 #include "DNA_meshdata_types.h"
36
37 #include "BLI_utildefines.h"
38 #include "BLI_bitmap.h"
39 #include "BLI_math_vector.h"
40
41 #include "BKE_customdata.h"
42 #include "BKE_mesh_mapping.h"
43 #include "BKE_subdiv.h"
44
45 #include "MEM_guardedalloc.h"
46
47 #include "opensubdiv_capi.h"
48 #include "opensubdiv_converter_capi.h"
49
50 /* Enable work-around for non-working CPU evaluator when using bilinear scheme.
51  * This forces Catmark scheme with all edges marked as infinitely sharp. */
52 #define BUGGY_SIMPLE_SCHEME_WORKAROUND 1
53
54 typedef struct ConverterStorage {
55         SubdivSettings settings;
56         const Mesh *mesh;
57         /* Indexed by loop index, value denotes index of face-varying vertex
58          * which corresponds to the UV coordinate.
59          */
60         int *loop_uv_indices;
61         int num_uv_coordinates;
62         /* Indexed by coarse mesh elements, gives index of corresponding element
63          * with ignoring all non-manifold entities.
64          *
65          * NOTE: This isn't strictly speaking manifold, this is more like non-loose
66          * geometry index. As in, index of element as if there were no loose edges
67          * or vertices in the mesh.
68          */
69         int *manifold_vertex_index;
70         /* Indexed by vertex index from mesh, corresponds to whether this vertex has
71          * infinite sharpness due to non-manifol topology.
72          */
73         BLI_bitmap *infinite_sharp_vertices_map;
74         /* Reverse mapping to above. */
75         int *manifold_vertex_index_reverse;
76         int *manifold_edge_index_reverse;
77         /* Number of non-loose elements. */
78         int num_manifold_vertices;
79         int num_manifold_edges;
80 } ConverterStorage;
81
82 static OpenSubdiv_SchemeType get_scheme_type(
83         const OpenSubdiv_Converter *converter)
84 {
85 #if BUGGY_SIMPLE_SCHEME_WORKAROUND
86         (void) converter;
87         return OSD_SCHEME_CATMARK;
88 #else
89         ConverterStorage *storage = converter->user_data;
90         if (storage->settings.is_simple) {
91                 return OSD_SCHEME_BILINEAR;
92         }
93         else {
94                 return OSD_SCHEME_CATMARK;
95         }
96 #endif
97 }
98
99 static OpenSubdiv_VtxBoundaryInterpolation get_vtx_boundary_interpolation(
100         const struct OpenSubdiv_Converter *converter) {
101         ConverterStorage *storage = converter->user_data;
102         return BKE_subdiv_converter_vtx_boundary_interpolation_from_settings(
103                 &storage->settings);
104 }
105
106 static OpenSubdiv_FVarLinearInterpolation get_fvar_linear_interpolation(
107         const OpenSubdiv_Converter *converter)
108 {
109         ConverterStorage *storage = converter->user_data;
110         return BKE_subdiv_converter_fvar_linear_from_settings(&storage->settings);
111 }
112
113 static bool specifies_full_topology(
114         const OpenSubdiv_Converter *UNUSED(converter))
115 {
116         return false;
117 }
118
119 static int get_num_faces(const OpenSubdiv_Converter *converter)
120 {
121         ConverterStorage *storage = converter->user_data;
122         return storage->mesh->totpoly;
123 }
124
125 static int get_num_edges(const OpenSubdiv_Converter *converter)
126 {
127         ConverterStorage *storage = converter->user_data;
128         return storage->num_manifold_edges;
129 }
130
131 static int get_num_vertices(const OpenSubdiv_Converter *converter)
132 {
133         ConverterStorage *storage = converter->user_data;
134         return storage->num_manifold_vertices;
135 }
136
137 static int get_num_face_vertices(const OpenSubdiv_Converter *converter,
138                                  int manifold_face_index)
139 {
140         ConverterStorage *storage = converter->user_data;
141         return storage->mesh->mpoly[manifold_face_index].totloop;
142 }
143
144 static void get_face_vertices(const OpenSubdiv_Converter *converter,
145                               int manifold_face_index,
146                               int *manifold_face_vertices)
147 {
148         ConverterStorage *storage = converter->user_data;
149         const MPoly *poly = &storage->mesh->mpoly[manifold_face_index];
150         const MLoop *mloop = storage->mesh->mloop;
151         for (int corner = 0; corner < poly->totloop; corner++) {
152                 manifold_face_vertices[corner] = storage->manifold_vertex_index[
153                         mloop[poly->loopstart + corner].v];
154         }
155 }
156
157 static void get_edge_vertices(const OpenSubdiv_Converter *converter,
158                               int manifold_edge_index,
159                               int *manifold_edge_vertices)
160 {
161         ConverterStorage *storage = converter->user_data;
162         const int edge_index =
163                 storage->manifold_edge_index_reverse[manifold_edge_index];
164         const MEdge *edge = &storage->mesh->medge[edge_index];
165         manifold_edge_vertices[0] = storage->manifold_vertex_index[edge->v1];
166         manifold_edge_vertices[1] = storage->manifold_vertex_index[edge->v2];
167 }
168
169 static float get_edge_sharpness(const OpenSubdiv_Converter *converter,
170                                 int manifold_edge_index)
171 {
172         ConverterStorage *storage = converter->user_data;
173 #if BUGGY_SIMPLE_SCHEME_WORKAROUND
174         if (storage->settings.is_simple) {
175                 return 10.0f;
176         }
177 #endif
178         const int edge_index =
179                 storage->manifold_edge_index_reverse[manifold_edge_index];
180         const MEdge *medge = storage->mesh->medge;
181         const float edge_crease =  (float)medge[edge_index].crease / 255.0f;
182         return edge_crease * edge_crease * 10.0f;
183 }
184
185 static bool is_infinite_sharp_vertex(const OpenSubdiv_Converter *converter,
186                                      int manifold_vertex_index)
187 {
188         ConverterStorage *storage = converter->user_data;
189 #if BUGGY_SIMPLE_SCHEME_WORKAROUND
190         if (storage->settings.is_simple) {
191                 return true;
192         }
193 #endif
194         const int vertex_index =
195                 storage->manifold_vertex_index_reverse[manifold_vertex_index];
196         return BLI_BITMAP_TEST_BOOL(storage->infinite_sharp_vertices_map,
197                                     vertex_index);
198 }
199
200 static float get_vertex_sharpness(const OpenSubdiv_Converter *UNUSED(converter),
201                                   int UNUSED(manifold_vertex_index))
202 {
203         return 0.0f;
204 }
205
206 static int get_num_uv_layers(const OpenSubdiv_Converter *converter)
207 {
208         ConverterStorage *storage = converter->user_data;
209         const Mesh *mesh = storage->mesh;
210         return CustomData_number_of_layers(&mesh->ldata, CD_MLOOPUV);
211 }
212
213 static void precalc_uv_layer(const OpenSubdiv_Converter *converter,
214                              const int layer_index)
215 {
216         ConverterStorage *storage = converter->user_data;
217         const Mesh *mesh = storage->mesh;
218         const MPoly *mpoly = mesh->mpoly;
219         const MLoop *mloop = mesh->mloop;
220         const MLoopUV *mloopuv = CustomData_get_layer_n(
221                 &mesh->ldata, CD_MLOOPUV, layer_index);
222         const int num_poly = mesh->totpoly;
223         const int num_vert = mesh->totvert;
224         const float limit[2] = {STD_UV_CONNECT_LIMIT, STD_UV_CONNECT_LIMIT};
225         /* Initialize memory required for the operations. */
226         if (storage->loop_uv_indices == NULL) {
227                 storage->loop_uv_indices = MEM_malloc_arrayN(
228                         mesh->totloop, sizeof(int), "loop uv vertex index");
229         }
230         UvVertMap *uv_vert_map = BKE_mesh_uv_vert_map_create(
231                 mpoly, mloop, mloopuv,
232                 num_poly, num_vert,
233                 limit,
234                 false, true);
235         /* NOTE: First UV vertex is supposed to be always marked as separate. */
236         storage->num_uv_coordinates = -1;
237         for (int vertex_index = 0; vertex_index < num_vert; ++vertex_index) {
238                 const UvMapVert *uv_vert = BKE_mesh_uv_vert_map_get_vert(uv_vert_map,
239                                                                          vertex_index);
240                 while (uv_vert != NULL) {
241                         if (uv_vert->separate) {
242                                 storage->num_uv_coordinates++;
243                         }
244                         const MPoly *mp = &mpoly[uv_vert->poly_index];
245                         const int global_loop_index = mp->loopstart +
246                                                       uv_vert->loop_of_poly_index;
247                         storage->loop_uv_indices[global_loop_index] =
248                                 storage->num_uv_coordinates;
249                         uv_vert = uv_vert->next;
250                 }
251         }
252         /* So far this value was used as a 0-based index, actual number of UV
253          * vertices is 1 more.
254          */
255         storage->num_uv_coordinates += 1;
256         BKE_mesh_uv_vert_map_free(uv_vert_map);
257 }
258
259 static void finish_uv_layer(const OpenSubdiv_Converter *UNUSED(converter))
260 {
261 }
262
263 static int get_num_uvs(const OpenSubdiv_Converter *converter)
264 {
265         ConverterStorage *storage = converter->user_data;
266         return storage->num_uv_coordinates;
267 }
268
269 static int get_face_corner_uv_index(const OpenSubdiv_Converter *converter,
270                                     const int face_index,
271                                     const int corner)
272 {
273         ConverterStorage *storage = converter->user_data;
274         const MPoly *mp = &storage->mesh->mpoly[face_index];
275         return storage->loop_uv_indices[mp->loopstart + corner];
276 }
277
278 static void free_user_data(const OpenSubdiv_Converter *converter)
279 {
280         ConverterStorage *user_data = converter->user_data;
281         MEM_SAFE_FREE(user_data->loop_uv_indices);
282         MEM_freeN(user_data->manifold_vertex_index);
283         MEM_freeN(user_data->infinite_sharp_vertices_map);
284         MEM_freeN(user_data->manifold_vertex_index_reverse);
285         MEM_freeN(user_data->manifold_edge_index_reverse);
286         MEM_freeN(user_data);
287 }
288
289 static void init_functions(OpenSubdiv_Converter *converter)
290 {
291         converter->getSchemeType = get_scheme_type;
292         converter->getVtxBoundaryInterpolation = get_vtx_boundary_interpolation;
293         converter->getFVarLinearInterpolation = get_fvar_linear_interpolation;
294         converter->specifiesFullTopology = specifies_full_topology;
295
296         converter->getNumFaces = get_num_faces;
297         converter->getNumEdges = get_num_edges;
298         converter->getNumVertices = get_num_vertices;
299
300         converter->getNumFaceVertices = get_num_face_vertices;
301         converter->getFaceVertices = get_face_vertices;
302         converter->getFaceEdges = NULL;
303
304         converter->getEdgeVertices = get_edge_vertices;
305         converter->getNumEdgeFaces = NULL;
306         converter->getEdgeFaces = NULL;
307         converter->getEdgeSharpness = get_edge_sharpness;
308
309         converter->getNumVertexEdges = NULL;
310         converter->getVertexEdges = NULL;
311         converter->getNumVertexFaces = NULL;
312         converter->getVertexFaces = NULL;
313         converter->isInfiniteSharpVertex = is_infinite_sharp_vertex;
314         converter->getVertexSharpness = get_vertex_sharpness;
315
316         converter->getNumUVLayers = get_num_uv_layers;
317         converter->precalcUVLayer = precalc_uv_layer;
318         converter->finishUVLayer = finish_uv_layer;
319         converter->getNumUVCoordinates = get_num_uvs;
320         converter->getFaceCornerUVIndex = get_face_corner_uv_index;
321
322         converter->freeUserData = free_user_data;
323 }
324
325 static void initialize_manifold_index_array(const BLI_bitmap *used_map,
326                                             const int num_elements,
327                                             int **indices_r,
328                                             int **indices_reverse_r,
329                                             int *num_manifold_elements_r)
330 {
331         int *indices = NULL;
332         if (indices_r != NULL) {
333                 indices = MEM_malloc_arrayN(
334                 num_elements, sizeof(int), "manifold indices");
335         }
336         int *indices_reverse = NULL;
337         if (indices_reverse_r != NULL) {
338                 indices_reverse = MEM_malloc_arrayN(
339                 num_elements, sizeof(int), "manifold indices reverse");
340         }
341         int offset = 0;
342         for (int i = 0; i < num_elements; i++) {
343                 if (BLI_BITMAP_TEST_BOOL(used_map, i)) {
344                         if (indices != NULL) {
345                                 indices[i] = i - offset;
346                         }
347                         if (indices_reverse != NULL) {
348                                 indices_reverse[i - offset] = i;
349                         }
350                 }
351                 else {
352                         if (indices != NULL) {
353                                 indices[i] = -1;
354                         }
355                         offset++;
356                 }
357         }
358         if (indices_r != NULL) {
359                 *indices_r = indices;
360         }
361         if (indices_reverse_r != NULL) {
362                 *indices_reverse_r = indices_reverse;
363         }
364         *num_manifold_elements_r = num_elements - offset;
365 }
366
367 static void initialize_manifold_indices(ConverterStorage *storage)
368 {
369         const Mesh *mesh = storage->mesh;
370         const MEdge *medge = mesh->medge;
371         const MLoop *mloop = mesh->mloop;
372         const MPoly *mpoly = mesh->mpoly;
373         /* Set bits of elements which are not loose. */
374         BLI_bitmap *vert_used_map = BLI_BITMAP_NEW(mesh->totvert, "vert used map");
375         BLI_bitmap *edge_used_map = BLI_BITMAP_NEW(mesh->totedge, "edge used map");
376         for (int poly_index = 0; poly_index < mesh->totpoly; poly_index++) {
377                 const MPoly *poly = &mpoly[poly_index];
378                 for (int corner = 0; corner < poly->totloop; corner++) {
379                         const MLoop *loop = &mloop[poly->loopstart + corner];
380                         BLI_BITMAP_ENABLE(vert_used_map, loop->v);
381                         BLI_BITMAP_ENABLE(edge_used_map, loop->e);
382                 }
383         }
384         initialize_manifold_index_array(vert_used_map,
385                                         mesh->totvert,
386                                         &storage->manifold_vertex_index,
387                                         &storage->manifold_vertex_index_reverse,
388                                         &storage->num_manifold_vertices);
389         initialize_manifold_index_array(edge_used_map,
390                                         mesh->totedge,
391                                         NULL,
392                                         &storage->manifold_edge_index_reverse,
393                                         &storage->num_manifold_edges);
394         /* Initialize infinite sharp mapping. */
395         storage->infinite_sharp_vertices_map =
396                 BLI_BITMAP_NEW(mesh->totvert, "vert used map");
397         for (int edge_index = 0; edge_index < mesh->totedge; edge_index++) {
398                 if (!BLI_BITMAP_TEST_BOOL(edge_used_map, edge_index)) {
399                         const MEdge *edge = &medge[edge_index];
400                         BLI_BITMAP_ENABLE(storage->infinite_sharp_vertices_map, edge->v1);
401                         BLI_BITMAP_ENABLE(storage->infinite_sharp_vertices_map, edge->v2);
402                 }
403         }
404         /* Free working variables. */
405         MEM_freeN(vert_used_map);
406         MEM_freeN(edge_used_map);
407 }
408
409 static void init_user_data(OpenSubdiv_Converter *converter,
410                            const SubdivSettings *settings,
411                            const Mesh *mesh)
412 {
413         ConverterStorage *user_data =
414                  MEM_mallocN(sizeof(ConverterStorage), __func__);
415         user_data->settings = *settings;
416         user_data->mesh = mesh;
417         user_data->loop_uv_indices = NULL;
418         initialize_manifold_indices(user_data);
419         converter->user_data = user_data;
420 }
421
422 void BKE_subdiv_converter_init_for_mesh(struct OpenSubdiv_Converter *converter,
423                                         const SubdivSettings *settings,
424                                         const Mesh *mesh)
425 {
426         init_functions(converter);
427         init_user_data(converter, settings, mesh);
428 }