d9fcdf52969ca5d6b0b6f73d7e896d39270adfdd
[blender.git] / source / blender / blenkernel / intern / subdiv_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_mesh.c
27  *  \ingroup bke
28  */
29
30 #include "BKE_subdiv_mesh.h"
31
32 #include "atomic_ops.h"
33
34 #include "DNA_mesh_types.h"
35 #include "DNA_meshdata_types.h"
36 #include "DNA_key_types.h"
37
38 #include "BLI_alloca.h"
39 #include "BLI_bitmap.h"
40 #include "BLI_math_vector.h"
41 #include "BLI_task.h"
42
43 #include "BKE_mesh.h"
44 #include "BKE_key.h"
45 #include "BKE_subdiv.h"
46 #include "BKE_subdiv_eval.h"
47 #include "BKE_subdiv_foreach.h"
48
49 #include "MEM_guardedalloc.h"
50
51 /* =============================================================================
52  * Subdivision context.
53  */
54
55 typedef struct SubdivMeshContext {
56         const Mesh *coarse_mesh;
57         Subdiv *subdiv;
58         Mesh *subdiv_mesh;
59         /* Cached custom data arrays for fastter access. */
60         int *vert_origindex;
61         int *edge_origindex;
62         int *loop_origindex;
63         int *poly_origindex;
64         /* UV layers interpolation. */
65         int num_uv_layers;
66         MLoopUV *uv_layers[MAX_MTFACE];
67 } SubdivMeshContext;
68
69 static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx)
70 {
71         Mesh *subdiv_mesh = ctx->subdiv_mesh;
72         ctx->num_uv_layers =
73                 CustomData_number_of_layers(&subdiv_mesh->ldata, CD_MLOOPUV);
74         for (int layer_index = 0; layer_index < ctx->num_uv_layers; ++layer_index) {
75                 ctx->uv_layers[layer_index] = CustomData_get_layer_n(
76                         &subdiv_mesh->ldata, CD_MLOOPUV, layer_index);
77         }
78 }
79
80 static void subdiv_mesh_ctx_cache_custom_data_layers(SubdivMeshContext *ctx)
81 {
82         Mesh *subdiv_mesh = ctx->subdiv_mesh;
83         /* Pointers to original indices layers. */
84         ctx->vert_origindex = CustomData_get_layer(
85                 &subdiv_mesh->vdata, CD_ORIGINDEX);
86         ctx->edge_origindex = CustomData_get_layer(
87                 &subdiv_mesh->edata, CD_ORIGINDEX);
88         ctx->loop_origindex = CustomData_get_layer(
89                 &subdiv_mesh->ldata, CD_ORIGINDEX);
90         ctx->poly_origindex = CustomData_get_layer(
91                 &subdiv_mesh->pdata, CD_ORIGINDEX);
92         /* UV layers interpolation. */
93         subdiv_mesh_ctx_cache_uv_layers(ctx);
94 }
95
96 /* =============================================================================
97  * Loop custom data copy helpers.
98  */
99
100 typedef struct LoopsOfPtex {
101         /* First loop of the ptex, starts at ptex (0, 0) and goes in u direction. */
102         const MLoop *first_loop;
103         /* Last loop of the ptex, starts at ptex (0, 0) and goes in v direction. */
104         const MLoop *last_loop;
105         /* For quad coarse faces only. */
106         const MLoop *second_loop;
107         const MLoop *third_loop;
108 } LoopsOfPtex;
109
110 static void loops_of_ptex_get(
111         const SubdivMeshContext *ctx,
112         LoopsOfPtex *loops_of_ptex,
113         const MPoly *coarse_poly,
114         const int ptex_of_poly_index)
115 {
116         const MLoop *coarse_mloop = ctx->coarse_mesh->mloop;
117         const int first_ptex_loop_index =
118                 coarse_poly->loopstart + ptex_of_poly_index;
119         /* Loop which look in the (opposite) V direction of the current
120          * ptex face.
121          *
122          * TODO(sergey): Get rid of using module on every iteration.
123          */
124         const int last_ptex_loop_index =
125                 coarse_poly->loopstart +
126                 (ptex_of_poly_index + coarse_poly->totloop - 1) %
127                         coarse_poly->totloop;
128         loops_of_ptex->first_loop = &coarse_mloop[first_ptex_loop_index];
129         loops_of_ptex->last_loop = &coarse_mloop[last_ptex_loop_index];
130         if (coarse_poly->totloop == 4) {
131                 loops_of_ptex->second_loop = loops_of_ptex->first_loop + 1;
132                 loops_of_ptex->third_loop = loops_of_ptex->first_loop + 2;
133         }
134         else {
135                 loops_of_ptex->second_loop = NULL;
136                 loops_of_ptex->third_loop = NULL;
137         }
138 }
139
140 /* =============================================================================
141  * Vertex custom data interpolation helpers.
142  */
143
144 /* TODO(sergey): Somehow de-duplicate with loops storage, without too much
145  * exception cases all over the code.
146  */
147
148 typedef struct VerticesForInterpolation {
149         /* This field points to a vertex data which is to be used for interpolation.
150          * The idea is to avoid unnecessary allocations for regular faces, where
151          * we can simply
152          */
153         const CustomData *vertex_data;
154         /* Vertices data calculated for ptex corners. There are always 4 elements
155          * in this custom data, aligned the following way:
156          *
157          *   index 0 -> uv (0, 0)
158          *   index 1 -> uv (0, 1)
159          *   index 2 -> uv (1, 1)
160          *   index 3 -> uv (1, 0)
161          *
162          * Is allocated for non-regular faces (triangles and n-gons).
163          */
164         CustomData vertex_data_storage;
165         bool vertex_data_storage_allocated;
166         /* Infices within vertex_data to interpolate for. The indices are aligned
167          * with uv coordinates in a similar way as indices in loop_data_storage.
168          */
169         int vertex_indices[4];
170 } VerticesForInterpolation;
171
172 static void vertex_interpolation_init(
173         const SubdivMeshContext *ctx,
174         VerticesForInterpolation *vertex_interpolation,
175         const MPoly *coarse_poly)
176 {
177         const Mesh *coarse_mesh = ctx->coarse_mesh;
178         const MLoop *coarse_mloop = coarse_mesh->mloop;
179         if (coarse_poly->totloop == 4) {
180                 vertex_interpolation->vertex_data = &coarse_mesh->vdata;
181                 vertex_interpolation->vertex_indices[0] =
182                         coarse_mloop[coarse_poly->loopstart + 0].v;
183                 vertex_interpolation->vertex_indices[1] =
184                         coarse_mloop[coarse_poly->loopstart + 1].v;
185                 vertex_interpolation->vertex_indices[2] =
186                         coarse_mloop[coarse_poly->loopstart + 2].v;
187                 vertex_interpolation->vertex_indices[3] =
188                         coarse_mloop[coarse_poly->loopstart + 3].v;
189                 vertex_interpolation->vertex_data_storage_allocated = false;
190         }
191         else {
192                 vertex_interpolation->vertex_data =
193                         &vertex_interpolation->vertex_data_storage;
194                 /* Allocate storage for loops corresponding to ptex corners. */
195                 CustomData_copy(&ctx->coarse_mesh->vdata,
196                                 &vertex_interpolation->vertex_data_storage,
197                                 CD_MASK_EVERYTHING,
198                                 CD_CALLOC,
199                                 4);
200                 /* Initialize indices. */
201                 vertex_interpolation->vertex_indices[0] = 0;
202                 vertex_interpolation->vertex_indices[1] = 1;
203                 vertex_interpolation->vertex_indices[2] = 2;
204                 vertex_interpolation->vertex_indices[3] = 3;
205                 vertex_interpolation->vertex_data_storage_allocated = true;
206                 /* Interpolate center of poly right away, it stays unchanged for all
207                  * ptex faces.
208                  */
209                 const float weight = 1.0f / (float)coarse_poly->totloop;
210                 float *weights = BLI_array_alloca(weights, coarse_poly->totloop);
211                 int *indices = BLI_array_alloca(indices, coarse_poly->totloop);
212                 for (int i = 0; i < coarse_poly->totloop; ++i) {
213                         weights[i] = weight;
214                         indices[i] = coarse_mloop[coarse_poly->loopstart + i].v;
215                 }
216                 CustomData_interp(&coarse_mesh->vdata,
217                                   &vertex_interpolation->vertex_data_storage,
218                                   indices,
219                                   weights, NULL,
220                                   coarse_poly->totloop,
221                                   2);
222         }
223 }
224
225 static void vertex_interpolation_from_corner(
226         const SubdivMeshContext *ctx,
227         VerticesForInterpolation *vertex_interpolation,
228         const MPoly *coarse_poly,
229         const int corner)
230 {
231         if (coarse_poly->totloop == 4) {
232                 /* Nothing to do, all indices and data is already assigned. */
233         }
234         else {
235                 const CustomData *vertex_data = &ctx->coarse_mesh->vdata;
236                 const Mesh *coarse_mesh = ctx->coarse_mesh;
237                 const MLoop *coarse_mloop = coarse_mesh->mloop;
238                 LoopsOfPtex loops_of_ptex;
239                 loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, corner);
240                 /* Ptex face corner corresponds to a poly loop with same index. */
241                 CustomData_copy_data(
242                         vertex_data,
243                         &vertex_interpolation->vertex_data_storage,
244                         coarse_mloop[coarse_poly->loopstart + corner].v,
245                         0,
246                         1);
247                 /* Interpolate remaining ptex face corners, which hits loops
248                  * middle points.
249                  *
250                  * TODO(sergey): Re-use one of interpolation results from previous
251                  * iteration.
252                  */
253                 const float weights[2] = {0.5f, 0.5f};
254                 const int first_loop_index = loops_of_ptex.first_loop - coarse_mloop;
255                 const int last_loop_index = loops_of_ptex.last_loop - coarse_mloop;
256                 const int first_indices[2] = {
257                         coarse_mloop[first_loop_index].v,
258                         coarse_mloop[coarse_poly->loopstart +
259                                 (first_loop_index - coarse_poly->loopstart + 1) %
260                                         coarse_poly->totloop].v};
261                 const int last_indices[2] = {coarse_mloop[first_loop_index].v,
262                                              coarse_mloop[last_loop_index].v};
263                 CustomData_interp(vertex_data,
264                                   &vertex_interpolation->vertex_data_storage,
265                                   first_indices,
266                                   weights, NULL,
267                                   2,
268                                   1);
269                 CustomData_interp(vertex_data,
270                                   &vertex_interpolation->vertex_data_storage,
271                                   last_indices,
272                                   weights, NULL,
273                                   2,
274                                   3);
275         }
276 }
277
278 static void vertex_interpolation_end(
279         VerticesForInterpolation *vertex_interpolation)
280 {
281         if (vertex_interpolation->vertex_data_storage_allocated) {
282                 CustomData_free(&vertex_interpolation->vertex_data_storage, 4);
283         }
284 }
285
286 /* =============================================================================
287  * Loop custom data interpolation helpers.
288  */
289
290 typedef struct LoopsForInterpolation {
291  /* This field points to a loop data which is to be used for interpolation.
292          * The idea is to avoid unnecessary allocations for regular faces, where
293          * we can simply
294          */
295         const CustomData *loop_data;
296         /* Loops data calculated for ptex corners. There are always 4 elements
297          * in this custom data, aligned the following way:
298          *
299          *   index 0 -> uv (0, 0)
300          *   index 1 -> uv (0, 1)
301          *   index 2 -> uv (1, 1)
302          *   index 3 -> uv (1, 0)
303          *
304          * Is allocated for non-regular faces (triangles and n-gons).
305          */
306         CustomData loop_data_storage;
307         bool loop_data_storage_allocated;
308         /* Infices within loop_data to interpolate for. The indices are aligned with
309          * uv coordinates in a similar way as indices in loop_data_storage.
310          */
311         int loop_indices[4];
312 } LoopsForInterpolation;
313
314 static void loop_interpolation_init(
315         const SubdivMeshContext *ctx,
316         LoopsForInterpolation *loop_interpolation,
317         const MPoly *coarse_poly)
318 {
319         const Mesh *coarse_mesh = ctx->coarse_mesh;
320         if (coarse_poly->totloop == 4) {
321                 loop_interpolation->loop_data = &coarse_mesh->ldata;
322                 loop_interpolation->loop_indices[0] = coarse_poly->loopstart + 0;
323                 loop_interpolation->loop_indices[1] = coarse_poly->loopstart + 1;
324                 loop_interpolation->loop_indices[2] = coarse_poly->loopstart + 2;
325                 loop_interpolation->loop_indices[3] = coarse_poly->loopstart + 3;
326                 loop_interpolation->loop_data_storage_allocated = false;
327         }
328         else {
329                 loop_interpolation->loop_data = &loop_interpolation->loop_data_storage;
330                 /* Allocate storage for loops corresponding to ptex corners. */
331                 CustomData_copy(&ctx->coarse_mesh->ldata,
332                                 &loop_interpolation->loop_data_storage,
333                                 CD_MASK_EVERYTHING,
334                                 CD_CALLOC,
335                                 4);
336                 /* Initialize indices. */
337                 loop_interpolation->loop_indices[0] = 0;
338                 loop_interpolation->loop_indices[1] = 1;
339                 loop_interpolation->loop_indices[2] = 2;
340                 loop_interpolation->loop_indices[3] = 3;
341                 loop_interpolation->loop_data_storage_allocated = true;
342                 /* Interpolate center of poly right away, it stays unchanged for all
343                  * ptex faces.
344                  */
345                 const float weight = 1.0f / (float)coarse_poly->totloop;
346                 float *weights = BLI_array_alloca(weights, coarse_poly->totloop);
347                 int *indices = BLI_array_alloca(indices, coarse_poly->totloop);
348                 for (int i = 0; i < coarse_poly->totloop; ++i) {
349                         weights[i] = weight;
350                         indices[i] = coarse_poly->loopstart + i;
351                 }
352                 CustomData_interp(&coarse_mesh->ldata,
353                                   &loop_interpolation->loop_data_storage,
354                                   indices,
355                                   weights, NULL,
356                                   coarse_poly->totloop,
357                                   2);
358         }
359 }
360
361 static void loop_interpolation_from_corner(
362         const SubdivMeshContext *ctx,
363         LoopsForInterpolation *loop_interpolation,
364         const MPoly *coarse_poly,
365         const int corner)
366 {
367         if (coarse_poly->totloop == 4) {
368                 /* Nothing to do, all indices and data is already assigned. */
369         }
370         else {
371                 const CustomData *loop_data = &ctx->coarse_mesh->ldata;
372                 const Mesh *coarse_mesh = ctx->coarse_mesh;
373                 const MLoop *coarse_mloop = coarse_mesh->mloop;
374                 LoopsOfPtex loops_of_ptex;
375                 loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, corner);
376                 /* Ptex face corner corresponds to a poly loop with same index. */
377                 CustomData_free_elem(&loop_interpolation->loop_data_storage, 0, 1);
378                 CustomData_copy_data(loop_data,
379                                      &loop_interpolation->loop_data_storage,
380                                      coarse_poly->loopstart + corner,
381                                      0,
382                                      1);
383                 /* Interpolate remaining ptex face corners, which hits loops
384                  * middle points.
385                  *
386                  * TODO(sergey): Re-use one of interpolation results from previous
387                  * iteration.
388                  */
389                 const float weights[2] = {0.5f, 0.5f};
390                 const int first_indices[2] = {
391                         loops_of_ptex.first_loop - coarse_mloop,
392                         (loops_of_ptex.first_loop + 1 - coarse_mloop) %
393                                 coarse_poly->totloop};
394                 const int last_indices[2] = {
395                         loops_of_ptex.last_loop - coarse_mloop,
396                         loops_of_ptex.first_loop - coarse_mloop};
397                 CustomData_interp(loop_data,
398                                   &loop_interpolation->loop_data_storage,
399                                   first_indices,
400                                   weights, NULL,
401                                   2,
402                                   1);
403                 CustomData_interp(loop_data,
404                                   &loop_interpolation->loop_data_storage,
405                                   last_indices,
406                                   weights, NULL,
407                                   2,
408                                   3);
409         }
410 }
411
412 static void loop_interpolation_end(LoopsForInterpolation *loop_interpolation)
413 {
414         if (loop_interpolation->loop_data_storage_allocated) {
415                 CustomData_free(&loop_interpolation->loop_data_storage, 4);
416         }
417 }
418
419 /* =============================================================================
420  * TLS.
421  */
422
423 typedef struct SubdivMeshTLS {
424         bool vertex_interpolation_initialized;
425         VerticesForInterpolation vertex_interpolation;
426         const MPoly *vertex_interpolation_coarse_poly;
427         int vertex_interpolation_coarse_corner;
428
429         bool loop_interpolation_initialized;
430         LoopsForInterpolation loop_interpolation;
431         const MPoly *loop_interpolation_coarse_poly;
432         int loop_interpolation_coarse_corner;
433 } SubdivMeshTLS;
434
435 static void subdiv_mesh_tls_free(void *tls_v)
436 {
437         SubdivMeshTLS *tls = tls_v;
438         if (tls->vertex_interpolation_initialized) {
439                 vertex_interpolation_end(&tls->vertex_interpolation);
440         }
441         if (tls->loop_interpolation_initialized) {
442                 loop_interpolation_end(&tls->loop_interpolation);
443         }
444 }
445
446 /* =============================================================================
447  * Evaluation helper functions.
448  */
449
450 static void eval_final_point_and_vertex_normal(
451         Subdiv *subdiv,
452         const int ptex_face_index,
453         const float u, const float v,
454         float r_P[3], short r_N[3])
455 {
456         if (subdiv->displacement_evaluator == NULL) {
457                 BKE_subdiv_eval_limit_point_and_short_normal(
458                         subdiv, ptex_face_index, u, v, r_P, r_N);
459         }
460         else {
461                 BKE_subdiv_eval_final_point(
462                         subdiv, ptex_face_index, u, v, r_P);
463         }
464 }
465
466 /* =============================================================================
467  * Displacement helpers
468  */
469
470 static void subdiv_accumulate_vertex_displacement(
471         Subdiv *subdiv,
472         const int ptex_face_index,
473         const float u, const float v,
474         MVert *subdiv_vert)
475 {
476         float dummy_P[3], dPdu[3], dPdv[3], D[3];
477         BKE_subdiv_eval_limit_point_and_derivatives(
478                 subdiv, ptex_face_index, u, v, dummy_P, dPdu, dPdv);
479         BKE_subdiv_eval_displacement(subdiv,
480                                      ptex_face_index, u, v,
481                                      dPdu, dPdv,
482                                      D);
483         add_v3_v3(subdiv_vert->co, D);
484         if (subdiv_vert->flag & ME_VERT_TMP_TAG) {
485                 mul_v3_fl(subdiv_vert->co, 0.5f);
486         }
487         subdiv_vert->flag |= ME_VERT_TMP_TAG;
488 }
489
490 /* =============================================================================
491  * Callbacks.
492  */
493
494 static bool subdiv_mesh_topology_info(
495         const SubdivForeachContext *foreach_context,
496         const int num_vertices,
497         const int num_edges,
498         const int num_loops,
499         const int num_polygons)
500 {
501         SubdivMeshContext *subdiv_context = foreach_context->user_data;
502         subdiv_context->subdiv_mesh = BKE_mesh_new_nomain_from_template(
503                 subdiv_context->coarse_mesh,
504                 num_vertices,
505                 num_edges,
506                 0,
507                 num_loops,
508                 num_polygons);
509         subdiv_mesh_ctx_cache_custom_data_layers(subdiv_context);
510         return true;
511 }
512
513 /* =============================================================================
514  * Vertex subdivision process.
515  */
516
517 static void subdiv_vertex_data_copy(
518         const SubdivMeshContext *ctx,
519         const MVert *coarse_vertex,
520         MVert *subdiv_vertex)
521 {
522         const Mesh *coarse_mesh = ctx->coarse_mesh;
523         Mesh *subdiv_mesh = ctx->subdiv_mesh;
524         const int coarse_vertex_index = coarse_vertex - coarse_mesh->mvert;
525         const int subdiv_vertex_index = subdiv_vertex - subdiv_mesh->mvert;
526         subdiv_vertex->flag &= ~ME_VERT_TMP_TAG;
527         CustomData_copy_data(&coarse_mesh->vdata,
528                              &ctx->subdiv_mesh->vdata,
529                              coarse_vertex_index,
530                              subdiv_vertex_index,
531                              1);
532 }
533
534 static void subdiv_vertex_data_interpolate(
535         const SubdivMeshContext *ctx,
536         MVert *subdiv_vertex,
537         const VerticesForInterpolation *vertex_interpolation,
538         const float u, const float v)
539 {
540         const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_mesh->mvert;
541         const float weights[4] = {(1.0f - u) * (1.0f - v),
542                                   u * (1.0f - v),
543                                   u * v,
544                                   (1.0f - u) * v};
545         subdiv_vertex->flag &= ~ME_VERT_TMP_TAG;
546         CustomData_interp(vertex_interpolation->vertex_data,
547                           &ctx->subdiv_mesh->vdata,
548                           vertex_interpolation->vertex_indices,
549                           weights, NULL,
550                           4,
551                           subdiv_vertex_index);
552         if (ctx->vert_origindex != NULL) {
553                 ctx->vert_origindex[subdiv_vertex_index] = ORIGINDEX_NONE;
554         }
555 }
556
557 static void evaluate_vertex_and_apply_displacement_copy(
558         const SubdivMeshContext *ctx,
559         const int ptex_face_index,
560         const float u, const float v,
561         const MVert *coarse_vert,
562         MVert *subdiv_vert)
563 {
564         /* Displacement is accumulated in subdiv vertex position.
565          * need to back it up before copying data from original vertex.
566          */
567         float D[3];
568         copy_v3_v3(D, subdiv_vert->co);
569         subdiv_vertex_data_copy(ctx, coarse_vert, subdiv_vert);
570         BKE_subdiv_eval_limit_point_and_short_normal(
571                 ctx->subdiv,
572                 ptex_face_index,
573                 u, v,
574                 subdiv_vert->co, subdiv_vert->no);
575         /* Apply displacement. */
576         add_v3_v3(subdiv_vert->co, D);
577 }
578
579 static void evaluate_vertex_and_apply_displacement_interpolate(
580         const SubdivMeshContext *ctx,
581         const int ptex_face_index,
582         const float u, const float v,
583         VerticesForInterpolation *vertex_interpolation,
584         MVert *subdiv_vert)
585 {
586         /* Displacement is accumulated in subdiv vertex position.
587          * need to back it up before copying data from original vertex.
588          */
589         float D[3];
590         copy_v3_v3(D, subdiv_vert->co);
591         subdiv_vertex_data_interpolate(ctx,
592                                        subdiv_vert,
593                                        vertex_interpolation,
594                                        u, v);
595         BKE_subdiv_eval_limit_point_and_short_normal(
596                 ctx->subdiv,
597                 ptex_face_index,
598                 u, v,
599                 subdiv_vert->co, subdiv_vert->no);
600         /* Apply displacement. */
601         add_v3_v3(subdiv_vert->co, D);
602 }
603
604 static void subdiv_mesh_vertex_every_corner_or_edge(
605         const SubdivForeachContext *foreach_context,
606         void *UNUSED(tls),
607         const int ptex_face_index,
608         const float u, const float v,
609         const int subdiv_vertex_index)
610 {
611         SubdivMeshContext *ctx = foreach_context->user_data;
612         Subdiv *subdiv = ctx->subdiv;
613         Mesh *subdiv_mesh = ctx->subdiv_mesh;
614         MVert *subdiv_mvert = subdiv_mesh->mvert;
615         MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index];
616         subdiv_accumulate_vertex_displacement(
617                 subdiv, ptex_face_index, u, v, subdiv_vert);
618 }
619
620 static void subdiv_mesh_vertex_every_corner(
621         const SubdivForeachContext *foreach_context,
622         void *tls,
623         const int ptex_face_index,
624         const float u, const float v,
625         const int UNUSED(coarse_vertex_index),
626         const int UNUSED(coarse_poly_index),
627         const int UNUSED(coarse_corner),
628         const int subdiv_vertex_index)
629 {
630         subdiv_mesh_vertex_every_corner_or_edge(
631                 foreach_context, tls, ptex_face_index, u, v, subdiv_vertex_index);
632 }
633
634 static void subdiv_mesh_vertex_every_edge(
635         const SubdivForeachContext *foreach_context,
636         void *tls,
637         const int ptex_face_index,
638         const float u, const float v,
639         const int UNUSED(coarse_edge_index),
640         const int UNUSED(coarse_poly_index),
641         const int UNUSED(coarse_corner),
642         const int subdiv_vertex_index)
643 {
644         subdiv_mesh_vertex_every_corner_or_edge(
645                 foreach_context, tls, ptex_face_index, u, v, subdiv_vertex_index);
646 }
647
648 static void subdiv_mesh_vertex_corner(
649         const SubdivForeachContext *foreach_context,
650         void *UNUSED(tls),
651         const int ptex_face_index,
652         const float u, const float v,
653         const int coarse_vertex_index,
654         const int UNUSED(coarse_poly_index),
655         const int UNUSED(coarse_corner),
656         const int subdiv_vertex_index)
657 {
658         BLI_assert(coarse_vertex_index != ORIGINDEX_NONE);
659         SubdivMeshContext *ctx = foreach_context->user_data;
660         const Mesh *coarse_mesh = ctx->coarse_mesh;
661         const MVert *coarse_mvert = coarse_mesh->mvert;
662         Mesh *subdiv_mesh = ctx->subdiv_mesh;
663         MVert *subdiv_mvert = subdiv_mesh->mvert;
664         const MVert *coarse_vert = &coarse_mvert[coarse_vertex_index];
665         MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index];
666         evaluate_vertex_and_apply_displacement_copy(
667                 ctx, ptex_face_index, u, v, coarse_vert, subdiv_vert);
668 }
669
670 static void subdiv_mesh_ensure_vertex_interpolation(
671         SubdivMeshContext *ctx,
672         SubdivMeshTLS *tls,
673         const MPoly *coarse_poly,
674         const int coarse_corner)
675 {
676         /* Check whether we've moved to another corner or polygon. */
677         if (tls->vertex_interpolation_initialized) {
678                 if (tls->vertex_interpolation_coarse_poly != coarse_poly ||
679                     tls->vertex_interpolation_coarse_corner != coarse_corner)
680                 {
681                         vertex_interpolation_end(&tls->vertex_interpolation);
682                         tls->vertex_interpolation_initialized = false;
683                 }
684         }
685         /* Initialize the interpolation. */
686         if (!tls->vertex_interpolation_initialized) {
687                 vertex_interpolation_init(ctx, &tls->vertex_interpolation, coarse_poly);
688         }
689         /* Update it for a new corner if needed. */
690         if (!tls->vertex_interpolation_initialized ||
691             tls->vertex_interpolation_coarse_corner != coarse_corner)
692         {
693                 vertex_interpolation_from_corner(
694                         ctx, &tls->vertex_interpolation, coarse_poly, coarse_corner);
695         }
696         /* Store settings used for the current state of interpolator. */
697         tls->vertex_interpolation_initialized = true;
698         tls->vertex_interpolation_coarse_poly = coarse_poly;
699         tls->vertex_interpolation_coarse_corner = coarse_corner;
700 }
701
702 static void subdiv_mesh_vertex_edge(
703         const SubdivForeachContext *foreach_context,
704         void *tls_v,
705         const int ptex_face_index,
706         const float u, const float v,
707         const int UNUSED(coarse_edge_index),
708         const int coarse_poly_index,
709         const int coarse_corner,
710         const int subdiv_vertex_index)
711 {
712         SubdivMeshContext *ctx = foreach_context->user_data;
713         SubdivMeshTLS *tls = tls_v;
714         const Mesh *coarse_mesh = ctx->coarse_mesh;
715         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
716         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
717         Mesh *subdiv_mesh = ctx->subdiv_mesh;
718         MVert *subdiv_mvert = subdiv_mesh->mvert;
719         MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index];
720         subdiv_mesh_ensure_vertex_interpolation(
721                 ctx, tls, coarse_poly, coarse_corner);
722         evaluate_vertex_and_apply_displacement_interpolate(
723                 ctx,
724                 ptex_face_index, u, v,
725                 &tls->vertex_interpolation,
726                 subdiv_vert);
727 }
728
729 static void subdiv_mesh_vertex_inner(
730         const SubdivForeachContext *foreach_context,
731         void *tls_v,
732         const int ptex_face_index,
733         const float u, const float v,
734         const int coarse_poly_index,
735         const int coarse_corner,
736         const int subdiv_vertex_index)
737 {
738         SubdivMeshContext *ctx = foreach_context->user_data;
739         SubdivMeshTLS *tls = tls_v;
740         Subdiv *subdiv = ctx->subdiv;
741         const Mesh *coarse_mesh = ctx->coarse_mesh;
742         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
743         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
744         Mesh *subdiv_mesh = ctx->subdiv_mesh;
745         MVert *subdiv_mvert = subdiv_mesh->mvert;
746         MVert *subdiv_vert = &subdiv_mvert[subdiv_vertex_index];
747         subdiv_mesh_ensure_vertex_interpolation(
748                 ctx, tls, coarse_poly, coarse_corner);
749         subdiv_vertex_data_interpolate(
750                 ctx, subdiv_vert, &tls->vertex_interpolation, u, v);
751         eval_final_point_and_vertex_normal(
752                 subdiv, ptex_face_index, u, v, subdiv_vert->co, subdiv_vert->no);
753 }
754
755 /* =============================================================================
756  * Edge subdivision process.
757  */
758
759 static void subdiv_copy_edge_data(
760         SubdivMeshContext *ctx,
761         MEdge *subdiv_edge,
762         const MEdge *coarse_edge)
763 {
764         const int subdiv_edge_index = subdiv_edge - ctx->subdiv_mesh->medge;
765         if (coarse_edge == NULL) {
766                 subdiv_edge->crease = 0;
767                 subdiv_edge->bweight = 0;
768                 subdiv_edge->flag = 0;
769                 if (ctx->edge_origindex != NULL) {
770                         ctx->edge_origindex[subdiv_edge_index] = ORIGINDEX_NONE;
771                 }
772                 return;
773         }
774         const int coarse_edge_index = coarse_edge - ctx->coarse_mesh->medge;
775         CustomData_copy_data(&ctx->coarse_mesh->edata,
776                              &ctx->subdiv_mesh->edata,
777                              coarse_edge_index,
778                              subdiv_edge_index,
779                              1);
780 }
781
782 static void subdiv_mesh_edge(
783         const SubdivForeachContext *foreach_context,
784         void *UNUSED(tls),
785         const int coarse_edge_index,
786         const int subdiv_edge_index,
787         const int subdiv_v1, const int subdiv_v2)
788 {
789         SubdivMeshContext *ctx = foreach_context->user_data;
790         Mesh *subdiv_mesh = ctx->subdiv_mesh;
791         MEdge *subdiv_medge = subdiv_mesh->medge;
792         MEdge *subdiv_edge = &subdiv_medge[subdiv_edge_index];
793         const MEdge *coarse_edge = NULL;
794         if (coarse_edge_index != ORIGINDEX_NONE) {
795                 const Mesh *coarse_mesh = ctx->coarse_mesh;
796                 const MEdge *coarse_medge = coarse_mesh->medge;
797                 coarse_edge = &coarse_medge[coarse_edge_index];
798         }
799         subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
800         subdiv_edge->v1 = subdiv_v1;
801         subdiv_edge->v2 = subdiv_v2;
802 }
803
804 /* =============================================================================
805  * Loops creation/interpolation.
806  */
807
808 static void subdiv_interpolate_loop_data(
809         const SubdivMeshContext *ctx,
810         MLoop *subdiv_loop,
811         const LoopsForInterpolation *loop_interpolation,
812         const float u, const float v)
813 {
814         const int subdiv_loop_index = subdiv_loop - ctx->subdiv_mesh->mloop;
815         const float weights[4] = {(1.0f - u) * (1.0f - v),
816                                   u * (1.0f - v),
817                                   u * v,
818                                   (1.0f - u) * v};
819         CustomData_interp(loop_interpolation->loop_data,
820                           &ctx->subdiv_mesh->ldata,
821                           loop_interpolation->loop_indices,
822                           weights, NULL,
823                           4,
824                           subdiv_loop_index);
825         /* TODO(sergey): Set ORIGINDEX. */
826 }
827
828 static void subdiv_eval_uv_layer(SubdivMeshContext *ctx,
829                                  MLoop *subdiv_loop,
830                                  const int ptex_face_index,
831                                  const float u, const float v)
832 {
833         if (ctx->num_uv_layers == 0) {
834                 return;
835         }
836         Subdiv *subdiv = ctx->subdiv;
837         const int mloop_index = subdiv_loop - ctx->subdiv_mesh->mloop;
838         for (int layer_index = 0; layer_index < ctx->num_uv_layers; layer_index++) {
839                 MLoopUV *subdiv_loopuv = &ctx->uv_layers[layer_index][mloop_index];
840                 BKE_subdiv_eval_face_varying(subdiv,
841                                              layer_index,
842                                              ptex_face_index,
843                                              u, v,
844                                              subdiv_loopuv->uv);
845         }
846 }
847
848 static void subdiv_mesh_ensure_loop_interpolation(
849         SubdivMeshContext *ctx,
850         SubdivMeshTLS *tls,
851         const MPoly *coarse_poly,
852         const int coarse_corner)
853 {
854         /* Check whether we've moved to another corner or polygon. */
855         if (tls->loop_interpolation_initialized) {
856                 if (tls->loop_interpolation_coarse_poly != coarse_poly ||
857                     tls->loop_interpolation_coarse_corner != coarse_corner)
858                 {
859                         loop_interpolation_end(&tls->loop_interpolation);
860                         tls->loop_interpolation_initialized = false;
861                 }
862         }
863         /* Initialize the interpolation. */
864         if (!tls->loop_interpolation_initialized) {
865                 loop_interpolation_init(ctx, &tls->loop_interpolation, coarse_poly);
866         }
867         /* Update it for a new corner if needed. */
868         if (!tls->loop_interpolation_initialized ||
869             tls->loop_interpolation_coarse_corner != coarse_corner)
870         {
871                 loop_interpolation_from_corner(
872                         ctx, &tls->loop_interpolation, coarse_poly, coarse_corner);
873         }
874         /* Store settings used for the current state of interpolator. */
875         tls->loop_interpolation_initialized = true;
876         tls->loop_interpolation_coarse_poly = coarse_poly;
877         tls->loop_interpolation_coarse_corner = coarse_corner;
878 }
879
880 static void subdiv_mesh_loop(
881         const SubdivForeachContext *foreach_context,
882         void *tls_v,
883         const int ptex_face_index,
884         const float u, const float v,
885         const int UNUSED(coarse_loop_index),
886         const int coarse_poly_index,
887         const int coarse_corner,
888         const int subdiv_loop_index,
889         const int subdiv_vertex_index, const int subdiv_edge_index)
890 {
891         SubdivMeshContext *ctx = foreach_context->user_data;
892         SubdivMeshTLS *tls = tls_v;
893         const Mesh *coarse_mesh = ctx->coarse_mesh;
894         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
895         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
896         Mesh *subdiv_mesh = ctx->subdiv_mesh;
897         MLoop *subdiv_mloop = subdiv_mesh->mloop;
898         MLoop *subdiv_loop = &subdiv_mloop[subdiv_loop_index];
899         subdiv_mesh_ensure_loop_interpolation(
900                 ctx, tls, coarse_poly, coarse_corner);
901         subdiv_interpolate_loop_data(
902                 ctx, subdiv_loop, &tls->loop_interpolation, u, v);
903         subdiv_eval_uv_layer(ctx, subdiv_loop, ptex_face_index, u, v);
904         subdiv_loop->v = subdiv_vertex_index;
905         subdiv_loop->e = subdiv_edge_index;
906 }
907
908 /* =============================================================================
909  * Polygons subdivision process.
910  */
911
912 static void subdiv_copy_poly_data(const SubdivMeshContext *ctx,
913                                   MPoly *subdiv_poly,
914                                   const MPoly *coarse_poly)
915 {
916         const int coarse_poly_index = coarse_poly - ctx->coarse_mesh->mpoly;
917         const int subdiv_poly_index = subdiv_poly - ctx->subdiv_mesh->mpoly;
918         CustomData_copy_data(&ctx->coarse_mesh->pdata,
919                              &ctx->subdiv_mesh->pdata,
920                              coarse_poly_index,
921                              subdiv_poly_index,
922                              1);
923 }
924
925 static void subdiv_mesh_poly(
926         const SubdivForeachContext *foreach_context,
927         void *UNUSED(tls),
928         const int coarse_poly_index,
929         const int subdiv_poly_index,
930         const int start_loop_index, const int num_loops)
931 {
932         BLI_assert(coarse_poly_index != ORIGINDEX_NONE);
933         SubdivMeshContext *ctx = foreach_context->user_data;
934         const Mesh *coarse_mesh = ctx->coarse_mesh;
935         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
936         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
937         Mesh *subdiv_mesh = ctx->subdiv_mesh;
938         MPoly *subdiv_mpoly = subdiv_mesh->mpoly;
939         MPoly *subdiv_poly = &subdiv_mpoly[subdiv_poly_index];
940         subdiv_copy_poly_data(ctx, subdiv_poly, coarse_poly);
941         subdiv_poly->loopstart = start_loop_index;
942         subdiv_poly->totloop = num_loops;
943 }
944
945 /* =============================================================================
946  * Loose elements subdivision process.
947  */
948
949 static void subdiv_mesh_vertex_loose(
950         const SubdivForeachContext *foreach_context,
951         void *UNUSED(tls),
952         const int coarse_vertex_index,
953         const int subdiv_vertex_index)
954 {
955         SubdivMeshContext *ctx = foreach_context->user_data;
956         const Mesh *coarse_mesh = ctx->coarse_mesh;
957         const MVert *coarse_mvert = coarse_mesh->mvert;
958         const MVert *coarse_vertex = &coarse_mvert[coarse_vertex_index];
959         Mesh *subdiv_mesh = ctx->subdiv_mesh;
960         MVert *subdiv_mvert = subdiv_mesh->mvert;
961         MVert *subdiv_vertex = &subdiv_mvert[subdiv_vertex_index];
962         subdiv_vertex_data_copy(ctx, coarse_vertex, subdiv_vertex);
963 }
964
965 /* Get neighbor edges of the given one.
966  * - neighbors[0] is an edge adjacent to edge->v1.
967  * - neighbors[1] is an edge adjacent to edge->v1.
968  */
969 static void find_edge_neighbors(const SubdivMeshContext *ctx,
970                                 const MEdge *edge,
971                                 const MEdge *neighbors[2])
972 {
973         const Mesh *coarse_mesh = ctx->coarse_mesh;
974         const MEdge *coarse_medge = coarse_mesh->medge;
975         neighbors[0] = NULL;
976         neighbors[1] = NULL;
977         for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) {
978                 const MEdge *current_edge = &coarse_medge[edge_index];
979                 if (current_edge == edge) {
980                         continue;
981                 }
982                 if (ELEM(edge->v1, current_edge->v1, current_edge->v2)) {
983                         neighbors[0] = current_edge;
984                 }
985                 if (ELEM(edge->v2, current_edge->v1, current_edge->v2)) {
986                         neighbors[1] = current_edge;
987                 }
988         }
989 }
990
991 static void points_for_loose_edges_interpolation_get(
992         SubdivMeshContext *ctx,
993         const MEdge *coarse_edge,
994         const MEdge *neighbors[2],
995         float points_r[4][3])
996 {
997         const Mesh *coarse_mesh = ctx->coarse_mesh;
998         const MVert *coarse_mvert = coarse_mesh->mvert;
999         /* Middle points corresponds to the edge. */
1000         copy_v3_v3(points_r[1], coarse_mvert[coarse_edge->v1].co);
1001         copy_v3_v3(points_r[2], coarse_mvert[coarse_edge->v2].co);
1002         /* Start point, duplicate from edge start if no neighbor. */
1003         if (neighbors[0] != NULL) {
1004                 if (neighbors[0]->v1 == coarse_edge->v1) {
1005                         copy_v3_v3(points_r[0], coarse_mvert[neighbors[0]->v2].co);
1006                 }
1007                 else {
1008                         copy_v3_v3(points_r[0], coarse_mvert[neighbors[0]->v1].co);
1009                 }
1010         }
1011         else {
1012                 sub_v3_v3v3(points_r[0], points_r[1], points_r[2]);
1013                 add_v3_v3(points_r[0], points_r[1]);
1014         }
1015         /* End point, duplicate from edge end if no neighbor. */
1016         if (neighbors[1] != NULL) {
1017                 if (neighbors[1]->v1 == coarse_edge->v2) {
1018                         copy_v3_v3(points_r[3], coarse_mvert[neighbors[1]->v2].co);
1019                 }
1020                 else {
1021                         copy_v3_v3(points_r[3], coarse_mvert[neighbors[1]->v1].co);
1022                 }
1023         }
1024         else {
1025                 sub_v3_v3v3(points_r[3], points_r[2], points_r[1]);
1026                 add_v3_v3(points_r[3], points_r[2]);
1027         }
1028 }
1029
1030 static void subdiv_mesh_vertex_of_loose_edge(
1031         const struct SubdivForeachContext *foreach_context,
1032         void *UNUSED(tls),
1033         const int coarse_edge_index,
1034         const float u,
1035         const int subdiv_vertex_index)
1036 {
1037         SubdivMeshContext *ctx = foreach_context->user_data;
1038         const Mesh *coarse_mesh = ctx->coarse_mesh;
1039         const MEdge *coarse_edge = &coarse_mesh->medge[coarse_edge_index];
1040         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1041         MVert *subdiv_mvert = subdiv_mesh->mvert;
1042         /* Find neighbors of the current loose edge. */
1043         const MEdge *neighbors[2];
1044         find_edge_neighbors(ctx, coarse_edge, neighbors);
1045         /* Get points for b-spline interpolation. */
1046         float points[4][3];
1047         points_for_loose_edges_interpolation_get(
1048                 ctx, coarse_edge, neighbors, points);
1049         /* Perform interpolation. */
1050         float weights[4];
1051         key_curve_position_weights(u, weights, KEY_BSPLINE);
1052
1053         MVert *subdiv_vertex = &subdiv_mvert[subdiv_vertex_index];
1054         interp_v3_v3v3v3v3(subdiv_vertex->co,
1055                            points[0],
1056                            points[1],
1057                            points[2],
1058                            points[3],
1059                            weights);
1060         /* Reset flags and such. */
1061         subdiv_vertex->flag = 0;
1062         subdiv_vertex->bweight = 0.0f;
1063         /* Reset normal. */
1064         subdiv_vertex->no[0] = 0.0f;
1065         subdiv_vertex->no[1] = 0.0f;
1066         subdiv_vertex->no[2] = 1.0f;
1067 }
1068
1069 /* =============================================================================
1070  * Initialization.
1071  */
1072
1073 static void setup_foreach_callbacks(SubdivForeachContext *foreach_context,
1074                                     const Subdiv *subdiv)
1075 {
1076         memset(foreach_context, 0, sizeof(*foreach_context));
1077         /* General information. */
1078         foreach_context->topology_info = subdiv_mesh_topology_info;
1079         /* Every boundary geometry. Used for dispalcement averaging. */
1080         if (subdiv->displacement_evaluator != NULL) {
1081                 foreach_context->vertex_every_corner = subdiv_mesh_vertex_every_corner;
1082                 foreach_context->vertex_every_edge = subdiv_mesh_vertex_every_edge;
1083         }
1084         else {
1085                 foreach_context->vertex_every_corner = NULL;
1086                 foreach_context->vertex_every_edge = NULL;
1087         }
1088         foreach_context->vertex_corner = subdiv_mesh_vertex_corner;
1089         foreach_context->vertex_edge = subdiv_mesh_vertex_edge;
1090         foreach_context->vertex_inner = subdiv_mesh_vertex_inner;
1091         foreach_context->edge = subdiv_mesh_edge;
1092         foreach_context->loop = subdiv_mesh_loop;
1093         foreach_context->poly = subdiv_mesh_poly;
1094         foreach_context->vertex_loose = subdiv_mesh_vertex_loose;
1095         foreach_context->vertex_of_loose_edge = subdiv_mesh_vertex_of_loose_edge;
1096         foreach_context->user_data_tls_free = subdiv_mesh_tls_free;
1097 }
1098
1099 /* =============================================================================
1100  * Public entry point.
1101  */
1102
1103 Mesh *BKE_subdiv_to_mesh(
1104         Subdiv *subdiv,
1105         const SubdivToMeshSettings *settings,
1106         const Mesh *coarse_mesh)
1107 {
1108         BKE_subdiv_stats_begin(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
1109         /* Make sure evaluator is up to date with possible new topology, and that
1110          * is is refined for the new positions of coarse vertices.
1111          */
1112         if (!BKE_subdiv_eval_update_from_mesh(subdiv, coarse_mesh)) {
1113                 /* This could happen in two situations:
1114                  * - OpenSubdiv is disabled.
1115                  * - Something totally bad happened, and OpenSubdiv rejected our
1116                  *   topology.
1117                  * In either way, we can't safely continue.
1118                  */
1119                 if (coarse_mesh->totpoly) {
1120                         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
1121                         return NULL;
1122                 }
1123         }
1124         /* Initialize subdivion mesh creation context/ */
1125         SubdivMeshContext subdiv_context = {0};
1126         subdiv_context.coarse_mesh = coarse_mesh;
1127         subdiv_context.subdiv = subdiv;
1128         /* Multi-threaded traversal/evaluation. */
1129         BKE_subdiv_stats_begin(&subdiv->stats,
1130                                SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY);
1131         SubdivForeachContext foreach_context;
1132         setup_foreach_callbacks(&foreach_context, subdiv);
1133         SubdivMeshTLS tls = {0};
1134         foreach_context.user_data = &subdiv_context;
1135         foreach_context.user_data_tls_size = sizeof(SubdivMeshTLS);
1136         foreach_context.user_data_tls = &tls;
1137         BKE_subdiv_foreach_subdiv_geometry(subdiv,
1138                                            &foreach_context,
1139                                            settings,
1140                                            coarse_mesh);
1141         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY);
1142         Mesh *result = subdiv_context.subdiv_mesh;
1143         // BKE_mesh_validate(result, true, true);
1144         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
1145         if (subdiv->displacement_evaluator != NULL) {
1146                 result->runtime.cd_dirty_vert |= CD_MASK_NORMAL;
1147         }
1148         return result;
1149 }