33813905105d06ed9e56180942f4d23ec74c372e
[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.h"
31
32 #include "atomic_ops.h"
33
34 #include "DNA_mesh_types.h"
35 #include "DNA_meshdata_types.h"
36
37 #include "BLI_alloca.h"
38 #include "BLI_bitmap.h"
39 #include "BLI_math_vector.h"
40 #include "BLI_task.h"
41
42 #include "BKE_mesh.h"
43
44 #include "MEM_guardedalloc.h"
45
46 /* =============================================================================
47  * General helpers.
48  */
49
50 /* Number of ptex faces for a given polygon. */
51 BLI_INLINE int num_ptex_faces_per_poly_get(const MPoly *poly)
52 {
53         return (poly->totloop == 4) ? 1 : poly->totloop;
54 }
55
56 BLI_INLINE int num_edges_per_ptex_face_get(const int resolution)
57 {
58         return 2 * (resolution - 1) * resolution;
59 }
60
61 BLI_INLINE int num_inner_edges_per_ptex_face_get(const int resolution)
62 {
63         if (resolution < 2) {
64                 return 0;
65         }
66         return (resolution - 2) * resolution +
67                (resolution - 1) * (resolution - 1);
68 }
69
70 /* Number of subdivision polygons per ptex face. */
71 BLI_INLINE int num_polys_per_ptex_get(const int resolution)
72 {
73         return (resolution - 1) * (resolution - 1);
74 }
75
76 /* Subdivision resolution per given polygon's ptex faces. */
77 BLI_INLINE int ptex_face_resolution_get(const MPoly *poly, int resolution)
78 {
79         return (poly->totloop == 4) ? (resolution)
80                                     : ((resolution >> 1) + 1);
81 }
82
83 /* =============================================================================
84  * Mesh subdivision context.
85  */
86
87 typedef struct SubdivMeshContext {
88         const Mesh *coarse_mesh;
89         Subdiv *subdiv;
90         Mesh *subdiv_mesh;
91         const SubdivToMeshSettings *settings;
92         /* Cached custom data arrays for fastter access. */
93         int *vert_origindex;
94         int *edge_origindex;
95         int *loop_origindex;
96         int *poly_origindex;
97         /* UV layers interpolation. */
98         int num_uv_layers;
99         MLoopUV *uv_layers[MAX_MTFACE];
100         /* Counters of geometry in subdivided mesh, initialized as a part of
101          * offsets calculation.
102          */
103         int num_subdiv_vertices;
104         int num_subdiv_edges;
105         int num_subdiv_loops;
106         int num_subdiv_polygons;
107         /* Offsets of various geometry in the subdivision mesh arrays. */
108         int vertices_corner_offset;
109         int vertices_edge_offset;
110         int vertices_inner_offset;
111         int edge_boundary_offset;
112         int edge_inner_offset;
113         /* Indexed by coarse polygon index, indicates offset in subdivided mesh
114          * vertices, edges and polygons arrays, where first element of the poly
115          * begins.
116          */
117         int *subdiv_vertex_offset;
118         int *subdiv_edge_offset;
119         int *subdiv_polygon_offset;
120         /* Indexed by base face index, element indicates total number of ptex faces
121          * created for preceding base faces.
122          */
123         int *face_ptex_offset;
124         /* Bitmap indicating whether vertex was used already or not.
125          * - During patch evaluation indicates whether coarse vertex was already
126          *   evaluated and its position on limit is already known.
127          */
128         BLI_bitmap *coarse_vertices_used_map;
129         /* Bitmap indicating whether edge was used already or not. This includes:
130          * - During context initialization it indicates whether subdivided verticies
131          *   for corresponding edge were already calculated or not.
132          * - During patch evaluation it indicates whether vertices along this edge
133          *   were already evaluated.
134          */
135         BLI_bitmap *coarse_edges_used_map;
136 } SubdivMeshContext;
137
138 static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx)
139 {
140         Mesh *subdiv_mesh = ctx->subdiv_mesh;
141         ctx->num_uv_layers =
142                 CustomData_number_of_layers(&subdiv_mesh->ldata, CD_MLOOPUV);
143         for (int layer_index = 0; layer_index < ctx->num_uv_layers; ++layer_index) {
144                 ctx->uv_layers[layer_index] = CustomData_get_layer_n(
145                         &subdiv_mesh->ldata, CD_MLOOPUV, layer_index);
146         }
147 }
148
149 static void subdiv_mesh_ctx_cache_custom_data_layers(SubdivMeshContext *ctx)
150 {
151         Mesh *subdiv_mesh = ctx->subdiv_mesh;
152         /* Pointers to original indices layers. */
153         ctx->vert_origindex = CustomData_get_layer(
154                 &subdiv_mesh->vdata, CD_ORIGINDEX);
155         ctx->edge_origindex = CustomData_get_layer(
156                 &subdiv_mesh->edata, CD_ORIGINDEX);
157         ctx->loop_origindex = CustomData_get_layer(
158                 &subdiv_mesh->ldata, CD_ORIGINDEX);
159         ctx->poly_origindex = CustomData_get_layer(
160                 &subdiv_mesh->pdata, CD_ORIGINDEX);
161         /* UV layers interpolation. */
162         subdiv_mesh_ctx_cache_uv_layers(ctx);
163 }
164
165 /* NOTE: Expects edge map to be zeroed. */
166 static void subdiv_mesh_ctx_count(SubdivMeshContext *ctx)
167 {
168         /* Reset counters. */
169         ctx->num_subdiv_vertices = 0;
170         ctx->num_subdiv_edges = 0;
171         ctx->num_subdiv_loops = 0;
172         ctx->num_subdiv_polygons = 0;
173         /* Static geometry counters. */
174         const int resolution = ctx->settings->resolution;
175         const int no_quad_patch_resolution = ((resolution >> 1) + 1);
176         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
177         const int num_inner_vertices_per_quad = (resolution - 2) * (resolution - 2);
178         const int num_inner_vertices_per_noquad_patch =
179                 (no_quad_patch_resolution - 2) * (no_quad_patch_resolution - 2);
180         const Mesh *coarse_mesh = ctx->coarse_mesh;
181         const MLoop *coarse_mloop = coarse_mesh->mloop;
182         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
183         ctx->num_subdiv_vertices = coarse_mesh->totvert;
184         ctx->num_subdiv_edges =
185                 coarse_mesh->totedge * (num_subdiv_vertices_per_coarse_edge + 1);
186         for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
187                 const MPoly *coarse_poly = &coarse_mpoly[poly_index];
188                 const int num_ptex_faces_per_poly =
189                         num_ptex_faces_per_poly_get(coarse_poly);
190                 for (int corner = 0; corner < coarse_poly->totloop; corner++) {
191                          const MLoop *loop = &coarse_mloop[coarse_poly->loopstart + corner];
192                          const bool is_edge_used =
193                                  BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, loop->e);
194                         /* Edges which aren't counted yet. */
195                         if (!is_edge_used) {
196                                 BLI_BITMAP_ENABLE(ctx->coarse_edges_used_map, loop->e);
197                                 ctx->num_subdiv_vertices += num_subdiv_vertices_per_coarse_edge;
198                         }
199                 }
200                 /* Inner verticies of polygon. */
201                 if (num_ptex_faces_per_poly == 1) {
202                         ctx->num_subdiv_vertices += num_inner_vertices_per_quad;
203                         ctx->num_subdiv_edges +=
204                                 num_edges_per_ptex_face_get(resolution - 2) +
205                                 4 * num_subdiv_vertices_per_coarse_edge;
206                         ctx->num_subdiv_polygons += num_polys_per_ptex_get(resolution);
207                 }
208                 else {
209                         ctx->num_subdiv_vertices +=
210                                 1 +
211                                 num_ptex_faces_per_poly * (no_quad_patch_resolution - 2) +
212                                 num_ptex_faces_per_poly * num_inner_vertices_per_noquad_patch;
213                         ctx->num_subdiv_edges +=
214                                 num_ptex_faces_per_poly *
215                                         (num_inner_edges_per_ptex_face_get(
216                                                  no_quad_patch_resolution - 1) +
217                                          (no_quad_patch_resolution - 2) +
218                                          num_subdiv_vertices_per_coarse_edge);
219                         if (no_quad_patch_resolution >= 3) {
220                                 ctx->num_subdiv_edges += coarse_poly->totloop;
221                         }
222                         ctx->num_subdiv_polygons +=
223                                 num_ptex_faces_per_poly *
224                                 num_polys_per_ptex_get(no_quad_patch_resolution);
225                 }
226         }
227         ctx->num_subdiv_loops = ctx->num_subdiv_polygons * 4;
228 }
229
230 static void subdiv_mesh_ctx_init_offsets(SubdivMeshContext *ctx)
231 {
232         const Mesh *coarse_mesh = ctx->coarse_mesh;
233         const int resolution = ctx->settings->resolution;
234         const int resolution_2 = resolution - 2;
235         const int resolution_2_squared = resolution_2 * resolution_2;
236         const int no_quad_patch_resolution = ((resolution >> 1) + 1);
237         const int num_irregular_vertices_per_patch =
238                 (no_quad_patch_resolution - 2) * (no_quad_patch_resolution - 1);
239         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
240         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
241         /* Constant offsets in arrays. */
242         ctx->vertices_corner_offset = 0;
243         ctx->vertices_edge_offset = coarse_mesh->totvert;
244         ctx->vertices_inner_offset =
245                 ctx->vertices_edge_offset +
246                 coarse_mesh->totedge * num_subdiv_vertices_per_coarse_edge;
247         ctx->edge_boundary_offset = 0;
248         ctx->edge_inner_offset =
249                 ctx->edge_boundary_offset +
250                 coarse_mesh->totedge * num_subdiv_edges_per_coarse_edge;
251         /* "Indexed" offsets. */
252         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
253         int vertex_offset = 0;
254         int edge_offset = 0;
255         int polygon_offset = 0;
256         int face_ptex_offset = 0;
257         for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
258                 const MPoly *coarse_poly = &coarse_mpoly[poly_index];
259                 const int num_ptex_faces_per_poly =
260                         num_ptex_faces_per_poly_get(coarse_poly);
261                 ctx->face_ptex_offset[poly_index] = face_ptex_offset;
262                 ctx->subdiv_vertex_offset[poly_index] = vertex_offset;
263                 ctx->subdiv_edge_offset[poly_index] = edge_offset;
264                 ctx->subdiv_polygon_offset[poly_index] = polygon_offset;
265                 face_ptex_offset += num_ptex_faces_per_poly;
266                 if (num_ptex_faces_per_poly == 1) {
267                         vertex_offset += resolution_2_squared;
268                         edge_offset += num_edges_per_ptex_face_get(resolution - 2) +
269                                        4 * num_subdiv_vertices_per_coarse_edge;
270                         polygon_offset += num_polys_per_ptex_get(resolution);
271                 }
272                 else {
273                         vertex_offset +=
274                                 1 +
275                                 num_ptex_faces_per_poly * num_irregular_vertices_per_patch;
276                         edge_offset +=
277                                 num_ptex_faces_per_poly *
278                                         (num_inner_edges_per_ptex_face_get(
279                                                  no_quad_patch_resolution - 1) +
280                                          (no_quad_patch_resolution - 2) +
281                                          num_subdiv_vertices_per_coarse_edge);
282                         if (no_quad_patch_resolution >= 3) {
283                                 edge_offset += coarse_poly->totloop;
284                         }
285                         polygon_offset +=
286                                 num_ptex_faces_per_poly *
287                                 num_polys_per_ptex_get(no_quad_patch_resolution);
288                 }
289         }
290 }
291
292 static void subdiv_mesh_ctx_init(SubdivMeshContext *ctx)
293 {
294         const Mesh *coarse_mesh = ctx->coarse_mesh;
295         /* Allocate maps and offsets. */
296         ctx->coarse_vertices_used_map =
297                 BLI_BITMAP_NEW(coarse_mesh->totvert, "vertices used map");
298         ctx->coarse_edges_used_map =
299                 BLI_BITMAP_NEW(coarse_mesh->totedge, "edges used map");
300         ctx->subdiv_vertex_offset = MEM_malloc_arrayN(
301                 coarse_mesh->totpoly,
302                 sizeof(*ctx->subdiv_vertex_offset),
303                 "vertex_offset");
304         ctx->subdiv_edge_offset = MEM_malloc_arrayN(
305                 coarse_mesh->totpoly,
306                 sizeof(*ctx->subdiv_edge_offset),
307                 "subdiv_edge_offset");
308         ctx->subdiv_polygon_offset = MEM_malloc_arrayN(
309                 coarse_mesh->totpoly,
310                 sizeof(*ctx->subdiv_polygon_offset),
311                 "subdiv_edge_offset");
312         ctx->face_ptex_offset = MEM_malloc_arrayN(coarse_mesh->totpoly,
313                                                   sizeof(*ctx->face_ptex_offset),
314                                                   "face_ptex_offset");
315         /* Initialize all offsets. */
316         subdiv_mesh_ctx_init_offsets(ctx);
317         /* Calculate number of geometry in the result subdivision mesh. */
318         subdiv_mesh_ctx_count(ctx);
319         /* Re-set maps which were used at this step. */
320         BLI_BITMAP_SET_ALL(ctx->coarse_edges_used_map, false, coarse_mesh->totedge);
321 }
322
323 static void subdiv_mesh_ctx_init_result(SubdivMeshContext *ctx)
324 {
325         subdiv_mesh_ctx_cache_custom_data_layers(ctx);
326 }
327
328 static void subdiv_mesh_ctx_free(SubdivMeshContext *ctx)
329 {
330         MEM_freeN(ctx->coarse_vertices_used_map);
331         MEM_freeN(ctx->coarse_edges_used_map);
332         MEM_freeN(ctx->subdiv_vertex_offset);
333         MEM_freeN(ctx->subdiv_edge_offset);
334         MEM_freeN(ctx->subdiv_polygon_offset);
335         MEM_freeN(ctx->face_ptex_offset);
336 }
337
338 /* =============================================================================
339  * Loop custom data copy helpers.
340  */
341
342 typedef struct LoopsOfPtex {
343         /* First loop of the ptex, starts at ptex (0, 0) and goes in u direction. */
344         const MLoop *first_loop;
345         /* Last loop of the ptex, starts at ptex (0, 0) and goes in v direction. */
346         const MLoop *last_loop;
347         /* For quad coarse faces only. */
348         const MLoop *second_loop;
349         const MLoop *third_loop;
350 } LoopsOfPtex;
351
352 static void loops_of_ptex_get(
353         const SubdivMeshContext *ctx,
354         LoopsOfPtex *loops_of_ptex,
355         const MPoly *coarse_poly,
356         const int ptex_of_poly_index)
357 {
358         const MLoop *coarse_mloop = ctx->coarse_mesh->mloop;
359         const int first_ptex_loop_index =
360                 coarse_poly->loopstart + ptex_of_poly_index;
361         /* Loop which look in the (opposite) V direction of the current
362          * ptex face.
363          *
364          * TOOD(sergey): Get rid of using module on every iteration.
365          */
366         const int last_ptex_loop_index =
367                 coarse_poly->loopstart +
368                 (ptex_of_poly_index + coarse_poly->totloop - 1) %
369                         coarse_poly->totloop;
370         loops_of_ptex->first_loop = &coarse_mloop[first_ptex_loop_index];
371         loops_of_ptex->last_loop = &coarse_mloop[last_ptex_loop_index];
372         if (coarse_poly->totloop == 4) {
373                 loops_of_ptex->second_loop = loops_of_ptex->first_loop + 1;
374                 loops_of_ptex->third_loop = loops_of_ptex->first_loop + 2;
375         }
376         else {
377                 loops_of_ptex->second_loop = NULL;
378                 loops_of_ptex->third_loop = NULL;
379         }
380 }
381
382 /* =============================================================================
383  * Vertex custom data interpolation helpers.
384  */
385
386 /* TODO(sergey): Somehow de-duplicate with loops storage, without too much
387  * exception cases all over the code.
388  */
389
390 typedef struct VerticesForInterpolation {
391         /* This field points to a vertex data which is to be used for interpolation.
392          * The idea is to avoid unnecessary allocations for regular faces, where
393          * we can simply
394          */
395         const CustomData *vertex_data;
396         /* Vertices data calculated for ptex corners. There are always 4 elements
397          * in this custom data, aligned the following way:
398          *
399          *   index 0 -> uv (0, 0)
400          *   index 1 -> uv (0, 1)
401          *   index 2 -> uv (1, 1)
402          *   index 3 -> uv (1, 0)
403          *
404          * Is allocated for non-regular faces (triangles and n-gons).
405          */
406         CustomData vertex_data_storage;
407         bool vertex_data_storage_allocated;
408         /* Infices within vertex_data to interpolate for. The indices are aligned
409          * with uv coordinates in a similar way as indices in loop_data_storage.
410          */
411         int vertex_indices[4];
412 } VerticesForInterpolation;
413
414 static void vertex_interpolation_init(
415         const SubdivMeshContext *ctx,
416         VerticesForInterpolation *vertex_interpolation,
417         const MPoly *coarse_poly)
418 {
419         const Mesh *coarse_mesh = ctx->coarse_mesh;
420         const MLoop *coarse_mloop = coarse_mesh->mloop;
421         if (coarse_poly->totloop == 4) {
422                 vertex_interpolation->vertex_data = &coarse_mesh->vdata;
423                 vertex_interpolation->vertex_indices[0] =
424                         coarse_mloop[coarse_poly->loopstart + 0].v;
425                 vertex_interpolation->vertex_indices[1] =
426                         coarse_mloop[coarse_poly->loopstart + 1].v;
427                 vertex_interpolation->vertex_indices[2] =
428                         coarse_mloop[coarse_poly->loopstart + 2].v;
429                 vertex_interpolation->vertex_indices[3] =
430                         coarse_mloop[coarse_poly->loopstart + 3].v;
431                 vertex_interpolation->vertex_data_storage_allocated = false;
432         }
433         else {
434                 vertex_interpolation->vertex_data =
435                         &vertex_interpolation->vertex_data_storage;
436                 /* Allocate storage for loops corresponding to ptex corners. */
437                 CustomData_copy(&ctx->coarse_mesh->vdata,
438                                 &vertex_interpolation->vertex_data_storage,
439                                 CD_MASK_EVERYTHING,
440                                 CD_CALLOC,
441                                 4);
442                 /* Initialize indices. */
443                 vertex_interpolation->vertex_indices[0] = 0;
444                 vertex_interpolation->vertex_indices[1] = 1;
445                 vertex_interpolation->vertex_indices[2] = 2;
446                 vertex_interpolation->vertex_indices[3] = 3;
447                 vertex_interpolation->vertex_data_storage_allocated = true;
448                 /* Interpolate center of poly right away, it stays unchanged for all
449                  * ptex faces.
450                  */
451                 const float weight = 1.0f / (float)coarse_poly->totloop;
452                 float *weights = BLI_array_alloca(weights, coarse_poly->totloop);
453                 int *indices = BLI_array_alloca(indices, coarse_poly->totloop);
454                 for (int i = 0; i < coarse_poly->totloop; ++i) {
455                         weights[i] = weight;
456                         indices[i] = coarse_mloop[coarse_poly->loopstart + i].v;
457                 }
458                 CustomData_interp(&coarse_mesh->vdata,
459                                   &vertex_interpolation->vertex_data_storage,
460                                   indices,
461                                   weights, NULL,
462                                   coarse_poly->totloop,
463                                   2);
464         }
465 }
466
467 static void vertex_interpolation_from_ptex(
468         const SubdivMeshContext *ctx,
469         VerticesForInterpolation *vertex_interpolation,
470         const MPoly *coarse_poly,
471         const int ptex_of_poly_index)
472 {
473         if (coarse_poly->totloop == 4) {
474                 /* Nothing to do, all indices and data is already assigned. */
475         }
476         else {
477                 const CustomData *vertex_data = &ctx->coarse_mesh->vdata;
478                 const Mesh *coarse_mesh = ctx->coarse_mesh;
479                 const MLoop *coarse_mloop = coarse_mesh->mloop;
480                 LoopsOfPtex loops_of_ptex;
481                 loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, ptex_of_poly_index);
482                 /* Ptex face corner corresponds to a poly loop with same index. */
483                 CustomData_copy_data(
484                         vertex_data,
485                         &vertex_interpolation->vertex_data_storage,
486                         coarse_mloop[coarse_poly->loopstart + ptex_of_poly_index].v,
487                         0,
488                         1);
489                 /* Interpolate remaining ptex face corners, which hits loops
490                  * middle points.
491                  *
492                  * TODO(sergey): Re-use one of interpolation results from previous
493                  * iteration.
494                  */
495                 const float weights[2] = {0.5f, 0.5f};
496                 const int first_loop_index = loops_of_ptex.first_loop - coarse_mloop;
497                 const int last_loop_index = loops_of_ptex.last_loop - coarse_mloop;
498                 const int first_indices[2] = {
499                         coarse_mloop[first_loop_index].v,
500                         coarse_mloop[coarse_poly->loopstart +
501                                 (first_loop_index - coarse_poly->loopstart + 1) %
502                                         coarse_poly->totloop].v};
503                 const int last_indices[2] = {coarse_mloop[first_loop_index].v,
504                                              coarse_mloop[last_loop_index].v};
505                 CustomData_interp(vertex_data,
506                                   &vertex_interpolation->vertex_data_storage,
507                                   first_indices,
508                                   weights, NULL,
509                                   2,
510                                   1);
511                 CustomData_interp(vertex_data,
512                                   &vertex_interpolation->vertex_data_storage,
513                                   last_indices,
514                                   weights, NULL,
515                                   2,
516                                   3);
517         }
518 }
519
520 static void vertex_interpolation_end(
521         VerticesForInterpolation *vertex_interpolation)
522 {
523         if (vertex_interpolation->vertex_data_storage_allocated) {
524                 CustomData_free(&vertex_interpolation->vertex_data_storage, 4);
525         }
526 }
527
528 /* =============================================================================
529  * Loop custom data interpolation helpers.
530  */
531
532 typedef struct LoopsForInterpolation {
533  /* This field points to a loop data which is to be used for interpolation.
534          * The idea is to avoid unnecessary allocations for regular faces, where
535          * we can simply
536          */
537         const CustomData *loop_data;
538         /* Loops data calculated for ptex corners. There are always 4 elements
539          * in this custom data, aligned the following way:
540          *
541          *   index 0 -> uv (0, 0)
542          *   index 1 -> uv (0, 1)
543          *   index 2 -> uv (1, 1)
544          *   index 3 -> uv (1, 0)
545          *
546          * Is allocated for non-regular faces (triangles and n-gons).
547          */
548         CustomData loop_data_storage;
549         bool loop_data_storage_allocated;
550         /* Infices within loop_data to interpolate for. The indices are aligned with
551          * uv coordinates in a similar way as indices in loop_data_storage.
552          */
553         int loop_indices[4];
554 } LoopsForInterpolation;
555
556 static void loop_interpolation_init(
557         const SubdivMeshContext *ctx,
558         LoopsForInterpolation *loop_interpolation,
559         const MPoly *coarse_poly)
560 {
561         const Mesh *coarse_mesh = ctx->coarse_mesh;
562         if (coarse_poly->totloop == 4) {
563                 loop_interpolation->loop_data = &coarse_mesh->ldata;
564                 loop_interpolation->loop_indices[0] = coarse_poly->loopstart + 0;
565                 loop_interpolation->loop_indices[1] = coarse_poly->loopstart + 1;
566                 loop_interpolation->loop_indices[2] = coarse_poly->loopstart + 2;
567                 loop_interpolation->loop_indices[3] = coarse_poly->loopstart + 3;
568                 loop_interpolation->loop_data_storage_allocated = false;
569         }
570         else {
571                 loop_interpolation->loop_data = &loop_interpolation->loop_data_storage;
572                 /* Allocate storage for loops corresponding to ptex corners. */
573                 CustomData_copy(&ctx->coarse_mesh->ldata,
574                                 &loop_interpolation->loop_data_storage,
575                                 CD_MASK_EVERYTHING,
576                                 CD_CALLOC,
577                                 4);
578                 /* Initialize indices. */
579                 loop_interpolation->loop_indices[0] = 0;
580                 loop_interpolation->loop_indices[1] = 1;
581                 loop_interpolation->loop_indices[2] = 2;
582                 loop_interpolation->loop_indices[3] = 3;
583                 loop_interpolation->loop_data_storage_allocated = true;
584                 /* Interpolate center of poly right away, it stays unchanged for all
585                  * ptex faces.
586                  */
587                 const float weight = 1.0f / (float)coarse_poly->totloop;
588                 float *weights = BLI_array_alloca(weights, coarse_poly->totloop);
589                 int *indices = BLI_array_alloca(indices, coarse_poly->totloop);
590                 for (int i = 0; i < coarse_poly->totloop; ++i) {
591                         weights[i] = weight;
592                         indices[i] = coarse_poly->loopstart + i;
593                 }
594                 CustomData_interp(&coarse_mesh->ldata,
595                                   &loop_interpolation->loop_data_storage,
596                                   indices,
597                                   weights, NULL,
598                                   coarse_poly->totloop,
599                                   2);
600         }
601 }
602
603 static void loop_interpolation_from_ptex(
604         const SubdivMeshContext *ctx,
605         LoopsForInterpolation *loop_interpolation,
606         const MPoly *coarse_poly,
607         const int ptex_face_index)
608 {
609         if (coarse_poly->totloop == 4) {
610                 /* Nothing to do, all indices and data is already assigned. */
611         }
612         else {
613                 const CustomData *loop_data = &ctx->coarse_mesh->ldata;
614                 const Mesh *coarse_mesh = ctx->coarse_mesh;
615                 const MLoop *coarse_mloop = coarse_mesh->mloop;
616                 LoopsOfPtex loops_of_ptex;
617                 loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, ptex_face_index);
618                 /* Ptex face corner corresponds to a poly loop with same index. */
619                 CustomData_copy_data(loop_data,
620                                      &loop_interpolation->loop_data_storage,
621                                      coarse_poly->loopstart + ptex_face_index,
622                                      0,
623                                      1);
624                 /* Interpolate remaining ptex face corners, which hits loops
625                  * middle points.
626                  *
627                  * TODO(sergey): Re-use one of interpolation results from previous
628                  * iteration.
629                  */
630                 const float weights[2] = {0.5f, 0.5f};
631                 const int first_indices[2] = {
632                         loops_of_ptex.first_loop - coarse_mloop,
633                         (loops_of_ptex.first_loop + 1 - coarse_mloop) %
634                                 coarse_poly->totloop};
635                 const int last_indices[2] = {
636                         loops_of_ptex.last_loop - coarse_mloop,
637                         loops_of_ptex.first_loop - coarse_mloop};
638                 CustomData_interp(loop_data,
639                                   &loop_interpolation->loop_data_storage,
640                                   first_indices,
641                                   weights, NULL,
642                                   2,
643                                   1);
644                 CustomData_interp(loop_data,
645                                   &loop_interpolation->loop_data_storage,
646                                   last_indices,
647                                   weights, NULL,
648                                   2,
649                                   3);
650         }
651 }
652
653 static void loop_interpolation_end(LoopsForInterpolation *loop_interpolation)
654 {
655         if (loop_interpolation->loop_data_storage_allocated) {
656                 CustomData_free(&loop_interpolation->loop_data_storage, 4);
657         }
658 }
659
660 /* =============================================================================
661  * Vertex subdivision process.
662  */
663
664 /* Custom data interpolation helpers. */
665
666 static void subdiv_vertex_data_copy(
667         const SubdivMeshContext *ctx,
668         const MVert *coarse_vertex,
669         MVert *subdiv_vertex)
670 {
671         const Mesh *coarse_mesh = ctx->coarse_mesh;
672         Mesh *subdiv_mesh = ctx->subdiv_mesh;
673         const int coarse_vertex_index = coarse_vertex - coarse_mesh->mvert;
674         const int subdiv_vertex_index = subdiv_vertex - subdiv_mesh->mvert;
675         CustomData_copy_data(&coarse_mesh->vdata,
676                              &ctx->subdiv_mesh->vdata,
677                              coarse_vertex_index,
678                              subdiv_vertex_index,
679                              1);
680 }
681
682 static void subdiv_vertex_data_interpolate(
683         const SubdivMeshContext *ctx,
684         MVert *subdiv_vertex,
685         const VerticesForInterpolation *vertex_interpolation,
686         const float u, const float v)
687 {
688         const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_mesh->mvert;
689         const float weights[4] = {(1.0f - u) * (1.0f - v),
690                                   u * (1.0f - v),
691                                   u * v,
692                                   (1.0f - u) * v};
693         CustomData_interp(vertex_interpolation->vertex_data,
694                           &ctx->subdiv_mesh->vdata,
695                           vertex_interpolation->vertex_indices,
696                           weights, NULL,
697                           4,
698                           subdiv_vertex_index);
699         if (ctx->vert_origindex != NULL) {
700                 ctx->vert_origindex[subdiv_vertex_index] = ORIGINDEX_NONE;
701         }
702 }
703
704 /* Evaluation of corner vertices. They are coming from coarse vertices. */
705
706 static void subdiv_evaluate_corner_vertices_regular(
707         SubdivMeshContext *ctx,
708         const MPoly *coarse_poly)
709 {
710         const float weights[4][2] = {{0.0f, 0.0f},
711                                      {1.0f, 0.0f},
712                                      {1.0f, 1.0f},
713                                      {0.0f, 1.0f}};
714         Subdiv *subdiv = ctx->subdiv;
715         const Mesh *coarse_mesh = ctx->coarse_mesh;
716         const MVert *coarse_mvert = coarse_mesh->mvert;
717         const MLoop *coarse_mloop = coarse_mesh->mloop;
718         Mesh *subdiv_mesh = ctx->subdiv_mesh;
719         MVert *subdiv_mvert = subdiv_mesh->mvert;
720         const int poly_index = coarse_poly - coarse_mesh->mpoly;
721         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
722         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
723                 const MLoop *coarse_loop =
724                     &coarse_mloop[coarse_poly->loopstart + corner];
725                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_vertices_used_map,
726                                                    coarse_loop->v))
727                 {
728                         continue;
729                 }
730                 const MVert *coarse_vert = &coarse_mvert[coarse_loop->v];
731                 MVert *subdiv_vert = &subdiv_mvert[
732                         ctx->vertices_corner_offset + coarse_loop->v];
733                 subdiv_vertex_data_copy(ctx, coarse_vert, subdiv_vert);
734                 BKE_subdiv_eval_limit_point_and_short_normal(
735                         subdiv,
736                         ptex_face_index,
737                         weights[corner][0], weights[corner][1],
738                         subdiv_vert->co, subdiv_vert->no);
739         }
740 }
741
742 static void subdiv_evaluate_corner_vertices_special(
743         SubdivMeshContext *ctx,
744         const MPoly *coarse_poly)
745 {
746         Subdiv *subdiv = ctx->subdiv;
747         const Mesh *coarse_mesh = ctx->coarse_mesh;
748         const MVert *coarse_mvert = coarse_mesh->mvert;
749         const MLoop *coarse_mloop = coarse_mesh->mloop;
750         Mesh *subdiv_mesh = ctx->subdiv_mesh;
751         MVert *subdiv_mvert = subdiv_mesh->mvert;
752         const int poly_index = coarse_poly - coarse_mesh->mpoly;
753         int ptex_face_index = ctx->face_ptex_offset[poly_index];
754         for (int corner = 0;
755              corner < coarse_poly->totloop;
756              corner++, ptex_face_index++)
757         {
758                 const MLoop *coarse_loop =
759                     &coarse_mloop[coarse_poly->loopstart + corner];
760                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_vertices_used_map,
761                                                    coarse_loop->v))
762                 {
763                         continue;
764                 }
765                 const MVert *coarse_vert = &coarse_mvert[coarse_loop->v];
766                 MVert *subdiv_vert = &subdiv_mvert[
767                         ctx->vertices_corner_offset + coarse_loop->v];
768                 subdiv_vertex_data_copy(ctx, coarse_vert, subdiv_vert);
769                 BKE_subdiv_eval_limit_point_and_short_normal(
770                         subdiv,
771                         ptex_face_index,
772                         0.0f, 0.0f,
773                         subdiv_vert->co, subdiv_vert->no);
774         }
775 }
776
777 static void subdiv_evaluate_corner_vertices(SubdivMeshContext *ctx,
778                                             const MPoly *coarse_poly)
779 {
780         if (coarse_poly->totloop == 4) {
781                 subdiv_evaluate_corner_vertices_regular(ctx, coarse_poly);
782         }
783         else {
784                 subdiv_evaluate_corner_vertices_special(ctx, coarse_poly);
785         }
786 }
787
788 /* Evaluation of edge vertices. They are coming from coarse edges. */
789
790 static void subdiv_evaluate_edge_vertices_regular(
791         SubdivMeshContext *ctx,
792         const MPoly *coarse_poly,
793         VerticesForInterpolation *vertex_interpolation)
794 {
795         const int resolution = ctx->settings->resolution;
796         const int resolution_1 = resolution - 1;
797         const float inv_resolution_1 = 1.0f / (float)resolution_1;
798         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
799         Subdiv *subdiv = ctx->subdiv;
800         const Mesh *coarse_mesh = ctx->coarse_mesh;
801         const MEdge *coarse_medge = coarse_mesh->medge;
802         const MLoop *coarse_mloop = coarse_mesh->mloop;
803         Mesh *subdiv_mesh = ctx->subdiv_mesh;
804         MVert *subdiv_mvert = subdiv_mesh->mvert;
805         const int poly_index = coarse_poly - coarse_mesh->mpoly;
806         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
807         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
808                 const MLoop *coarse_loop =
809                     &coarse_mloop[coarse_poly->loopstart + corner];
810                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_edges_used_map,
811                                                    coarse_loop->e))
812                 {
813                         continue;
814                 }
815                 vertex_interpolation_from_ptex(ctx,
816                                                vertex_interpolation,
817                                                coarse_poly,
818                                                corner);
819                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
820                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
821                 MVert *subdiv_vert = &subdiv_mvert[
822                         ctx->vertices_edge_offset +
823                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge];
824                 for (int vertex_index = 0;
825                      vertex_index < num_subdiv_vertices_per_coarse_edge;
826                      vertex_index++, subdiv_vert++)
827                 {
828                         float fac = (vertex_index + 1) * inv_resolution_1;
829                         if (flip) {
830                                 fac = 1.0f - fac;
831                         }
832                         if (corner >= 2) {
833                                 fac = 1.0f - fac;
834                         }
835                         float u, v;
836                         if ((corner & 1) == 0) {
837                                 u = fac;
838                                 v = (corner == 2) ? 1.0f : 0.0f;
839                         }
840                         else {
841                                 u = (corner == 1) ? 1.0f : 0.0f;
842                                 v = fac;
843                         }
844                         subdiv_vertex_data_interpolate(ctx,
845                                                        subdiv_vert,
846                                                        vertex_interpolation,
847                                                        u, v);
848                         BKE_subdiv_eval_limit_point_and_short_normal(
849                                 subdiv,
850                                 ptex_face_index,
851                                 u, v,
852                                 subdiv_vert->co, subdiv_vert->no);
853                 }
854         }
855 }
856
857 static void subdiv_evaluate_edge_vertices_special(
858         SubdivMeshContext *ctx,
859         const MPoly *coarse_poly,
860         VerticesForInterpolation *vertex_interpolation)
861 {
862         const int resolution = ctx->settings->resolution;
863         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
864         const int num_vertices_per_ptex_edge = ((resolution >> 1) + 1);
865         const float inv_ptex_resolution_1 =
866                 1.0f / (float)(num_vertices_per_ptex_edge - 1);
867         Subdiv *subdiv = ctx->subdiv;
868         const Mesh *coarse_mesh = ctx->coarse_mesh;
869         const MEdge *coarse_medge = coarse_mesh->medge;
870         const MLoop *coarse_mloop = coarse_mesh->mloop;
871         Mesh *subdiv_mesh = ctx->subdiv_mesh;
872         MVert *subdiv_mvert = subdiv_mesh->mvert;
873         const int poly_index = coarse_poly - coarse_mesh->mpoly;
874         const int ptex_face_start_index = ctx->face_ptex_offset[poly_index];
875         int ptex_face_index = ptex_face_start_index;
876         for (int corner = 0;
877              corner < coarse_poly->totloop;
878              corner++, ptex_face_index++)
879         {
880                 const MLoop *coarse_loop =
881                         &coarse_mloop[coarse_poly->loopstart + corner];
882                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_edges_used_map,
883                                                    coarse_loop->e))
884                 {
885                         continue;
886                 }
887                 vertex_interpolation_from_ptex(ctx,
888                                                vertex_interpolation,
889                                                coarse_poly,
890                                                corner);
891                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
892                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
893                 MVert *subdiv_vert = &subdiv_mvert[
894                         ctx->vertices_edge_offset +
895                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge];
896                 int veretx_delta = 1;
897                 if (flip) {
898                         subdiv_vert += num_subdiv_vertices_per_coarse_edge - 1;
899                         veretx_delta = -1;
900                 }
901                 for (int vertex_index = 1;
902                      vertex_index < num_vertices_per_ptex_edge;
903                      vertex_index++, subdiv_vert += veretx_delta)
904                 {
905                         float u = vertex_index * inv_ptex_resolution_1;
906                         subdiv_vertex_data_interpolate(ctx,
907                                                        subdiv_vert,
908                                                        vertex_interpolation,
909                                                        u, 0.0f);
910                         BKE_subdiv_eval_limit_point_and_short_normal(
911                                 subdiv,
912                                 ptex_face_index,
913                                 u, 0.0f,
914                                 subdiv_vert->co, subdiv_vert->no);
915                 }
916                 const int next_ptex_face_index =
917                         ptex_face_start_index + (corner + 1) % coarse_poly->totloop;
918                 for (int vertex_index = 1;
919                      vertex_index < num_vertices_per_ptex_edge - 1;
920                      vertex_index++, subdiv_vert += veretx_delta)
921                 {
922                         float v = 1.0f - vertex_index * inv_ptex_resolution_1;
923                         subdiv_vertex_data_interpolate(ctx,
924                                                        subdiv_vert,
925                                                        vertex_interpolation,
926                                                        0.0f, v);
927                         BKE_subdiv_eval_limit_point_and_short_normal(
928                                 subdiv,
929                                 next_ptex_face_index,
930                                 0.0f, v,
931                                 subdiv_vert->co, subdiv_vert->no);
932                 }
933         }
934 }
935
936 static void subdiv_evaluate_edge_vertices(
937         SubdivMeshContext *ctx,
938         const MPoly *coarse_poly,
939         VerticesForInterpolation *vertex_interpolation)
940 {
941         if (coarse_poly->totloop == 4) {
942                 subdiv_evaluate_edge_vertices_regular(
943                         ctx, coarse_poly, vertex_interpolation);
944         }
945         else {
946                 subdiv_evaluate_edge_vertices_special(
947                         ctx, coarse_poly, vertex_interpolation);
948         }
949 }
950
951 /* Evaluation of inner vertices, they are coming from ptex patches. */
952
953 static void subdiv_evaluate_inner_vertices_regular(
954         SubdivMeshContext *ctx,
955         const MPoly *coarse_poly,
956         VerticesForInterpolation *vertex_interpolation)
957 {
958         const int resolution = ctx->settings->resolution;
959         const float inv_resolution_1 = 1.0f / (float)(resolution - 1);
960         Subdiv *subdiv = ctx->subdiv;
961         const Mesh *coarse_mesh = ctx->coarse_mesh;
962         Mesh *subdiv_mesh = ctx->subdiv_mesh;
963         MVert *subdiv_mvert = subdiv_mesh->mvert;
964         const int poly_index = coarse_poly - coarse_mesh->mpoly;
965         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
966         const int start_vertex_index = ctx->subdiv_vertex_offset[poly_index];
967         MVert *subdiv_vert =
968                 &subdiv_mvert[ctx->vertices_inner_offset + start_vertex_index];
969         vertex_interpolation_from_ptex(ctx,
970                                        vertex_interpolation,
971                                        coarse_poly,
972                                        0);
973         for (int y = 1; y < resolution - 1; y++) {
974                 const float v = y * inv_resolution_1;
975                 for (int x = 1; x < resolution - 1; x++, subdiv_vert++) {
976                         const float u = x * inv_resolution_1;
977                         subdiv_vertex_data_interpolate(ctx,
978                                                        subdiv_vert,
979                                                        vertex_interpolation,
980                                                        u, v);
981                         BKE_subdiv_eval_limit_point_and_short_normal(
982                                 subdiv,
983                                 ptex_face_index,
984                                 u, v,
985                                 subdiv_vert->co, subdiv_vert->no);
986                 }
987         }
988 }
989
990 static void subdiv_evaluate_inner_vertices_special(
991         SubdivMeshContext *ctx,
992         const MPoly *coarse_poly,
993         VerticesForInterpolation *vertex_interpolation)
994 {
995         const int resolution = ctx->settings->resolution;
996         const int ptex_face_resolution = ptex_face_resolution_get(
997                 coarse_poly, resolution);
998         const float inv_ptex_face_resolution_1 =
999                 1.0f / (float)(ptex_face_resolution - 1);
1000         Subdiv *subdiv = ctx->subdiv;
1001         const Mesh *coarse_mesh = ctx->coarse_mesh;
1002         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1003         MVert *subdiv_mvert = subdiv_mesh->mvert;
1004         const int poly_index = coarse_poly - coarse_mesh->mpoly;
1005         int ptex_face_index = ctx->face_ptex_offset[poly_index];
1006         const int start_vertex_index = ctx->subdiv_vertex_offset[poly_index];
1007         MVert *subdiv_vert =
1008                 &subdiv_mvert[ctx->vertices_inner_offset + start_vertex_index];
1009         vertex_interpolation_from_ptex(ctx,
1010                                        vertex_interpolation,
1011                                        coarse_poly,
1012                                        0);
1013         subdiv_vertex_data_interpolate(ctx,
1014                                        subdiv_vert,
1015                                        vertex_interpolation,
1016                                        1.0f, 1.0f);
1017         BKE_subdiv_eval_limit_point_and_short_normal(
1018                 subdiv,
1019                 ptex_face_index,
1020                 1.0f, 1.0f,
1021                 subdiv_vert->co, subdiv_vert->no);
1022         subdiv_vert++;
1023         for (int corner = 0;
1024              corner < coarse_poly->totloop;
1025              corner++, ptex_face_index++)
1026         {
1027                 if (corner != 0) {
1028                         vertex_interpolation_from_ptex(ctx,
1029                                                        vertex_interpolation,
1030                                                        coarse_poly,
1031                                                        corner);
1032                 }
1033                 for (int y = 1; y < ptex_face_resolution - 1; y++) {
1034                         const float v = y * inv_ptex_face_resolution_1;
1035                         for (int x = 1; x < ptex_face_resolution; x++, subdiv_vert++) {
1036                                 const float u = x * inv_ptex_face_resolution_1;
1037                                 subdiv_vertex_data_interpolate(ctx,
1038                                                                subdiv_vert,
1039                                                                vertex_interpolation,
1040                                                                u, v);
1041                                 BKE_subdiv_eval_limit_point_and_short_normal(
1042                                         subdiv,
1043                                         ptex_face_index,
1044                                         u, v,
1045                                         subdiv_vert->co, subdiv_vert->no);
1046                         }
1047                 }
1048         }
1049 }
1050
1051 static void subdiv_evaluate_inner_vertices(
1052         SubdivMeshContext *ctx,
1053         const MPoly *coarse_poly,
1054         VerticesForInterpolation *vertex_interpolation)
1055 {
1056         if (coarse_poly->totloop == 4) {
1057                 subdiv_evaluate_inner_vertices_regular(
1058                         ctx, coarse_poly, vertex_interpolation);
1059         }
1060         else {
1061                 subdiv_evaluate_inner_vertices_special(
1062                         ctx, coarse_poly, vertex_interpolation);
1063         }
1064 }
1065
1066 /* Evaluate all vertices which are emitted from given coarse polygon. */
1067 static void subdiv_evaluate_vertices(SubdivMeshContext *ctx,
1068                                      const int poly_index)
1069 {
1070         /* Base/coarse mesh information. */
1071         const Mesh *coarse_mesh = ctx->coarse_mesh;
1072         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1073         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1074         /* Initialize vertex interpolation, it is reused by corner vertices, coarse
1075          * edges and patch evaluation.
1076          */
1077         VerticesForInterpolation vertex_interpolation;
1078         vertex_interpolation_init(ctx, &vertex_interpolation, coarse_poly);
1079         (void) vertex_interpolation;
1080         subdiv_evaluate_corner_vertices(ctx, coarse_poly);
1081         subdiv_evaluate_edge_vertices(ctx, coarse_poly, &vertex_interpolation);
1082         subdiv_evaluate_inner_vertices(ctx, coarse_poly, &vertex_interpolation);
1083         vertex_interpolation_end(&vertex_interpolation);
1084 }
1085
1086 /* =============================================================================
1087  * Edge subdivision process.
1088  */
1089
1090 static void subdiv_copy_edge_data(
1091         SubdivMeshContext *ctx,
1092         MEdge *subdiv_edge,
1093         const MEdge *coarse_edge)
1094 {
1095         const int subdiv_edge_index = subdiv_edge - ctx->subdiv_mesh->medge;
1096         if (coarse_edge == NULL) {
1097                 subdiv_edge->crease = 0;
1098                 subdiv_edge->bweight = 0;
1099                 subdiv_edge->flag = 0;
1100                 if (ctx->edge_origindex != NULL) {
1101                         ctx->edge_origindex[subdiv_edge_index] = ORIGINDEX_NONE;
1102                 }
1103                 return;
1104         }
1105         const int coarse_edge_index = coarse_edge - ctx->coarse_mesh->medge;
1106         CustomData_copy_data(&ctx->coarse_mesh->edata,
1107                              &ctx->subdiv_mesh->edata,
1108                              coarse_edge_index,
1109                              subdiv_edge_index,
1110                              1);
1111 }
1112
1113 static MEdge *subdiv_create_edges_row(SubdivMeshContext *ctx,
1114                                       MEdge *subdiv_edge,
1115                                       const MEdge *coarse_edge,
1116                                       const int start_vertex_index,
1117                                       const int num_edges_per_row)
1118 {
1119         int vertex_index = start_vertex_index;
1120         for (int edge_index = 0;
1121              edge_index < num_edges_per_row - 1;
1122              edge_index++, subdiv_edge++)
1123         {
1124                 subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1125                 subdiv_edge->v1 = vertex_index;
1126                 subdiv_edge->v2 = vertex_index + 1;
1127                 vertex_index += 1;
1128         }
1129         return subdiv_edge;
1130 }
1131
1132 static MEdge *subdiv_create_edges_column(SubdivMeshContext *ctx,
1133                                          MEdge *subdiv_edge,
1134                                          const MEdge *coarse_start_edge,
1135                                          const MEdge *coarse_end_edge,
1136                                          const int start_vertex_index,
1137                                          const int num_edges_per_row)
1138 {
1139         int vertex_index = start_vertex_index;
1140         for (int edge_index = 0;
1141              edge_index < num_edges_per_row;
1142              edge_index++, subdiv_edge++)
1143         {
1144                 const MEdge *coarse_edge = NULL;
1145                 if (edge_index == 0) {
1146                         coarse_edge = coarse_start_edge;
1147                 }
1148                 else if (edge_index == num_edges_per_row - 1) {
1149                         coarse_edge = coarse_end_edge;
1150                 }
1151                 subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1152                 subdiv_edge->v1 = vertex_index;
1153                 subdiv_edge->v2 = vertex_index + num_edges_per_row;
1154                 vertex_index += 1;
1155         }
1156         return subdiv_edge;
1157 }
1158
1159 /* Create edges between inner vertices of patch, and also edges to the
1160  * boundary.
1161  */
1162
1163 /* Consider a subdivision of base face at level 1:
1164  *
1165  *  y
1166  *  ^
1167  *  |   (6) ---- (7) ---- (8)
1168  *  |    |        |        |
1169  *  |   (3) ---- (4) ---- (5)
1170  *  |    |        |        |
1171  *  |   (0) ---- (1) ---- (2)
1172  *  o---------------------------> x
1173  *
1174  * This is illustrate which parts of geometry is created by code below.
1175  */
1176
1177 static void subdiv_create_edges_all_patches_regular(
1178         SubdivMeshContext *ctx,
1179         const MPoly *coarse_poly)
1180 {
1181         const Mesh *coarse_mesh = ctx->coarse_mesh;
1182         const MEdge *coarse_medge = coarse_mesh->medge;
1183         const MLoop *coarse_mloop = coarse_mesh->mloop;
1184         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1185         const int poly_index = coarse_poly - coarse_mpoly;
1186         const int resolution = ctx->settings->resolution;
1187         const int start_vertex_index =
1188                 ctx->vertices_inner_offset +
1189                 ctx->subdiv_vertex_offset[poly_index];
1190         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1191         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1192         MEdge *subdiv_medge = subdiv_mesh->medge;
1193         MEdge *subdiv_edge = &subdiv_medge[
1194                 ctx->edge_inner_offset + ctx->subdiv_edge_offset[poly_index]];
1195         /* Create bottom row of edges (0-1, 1-2). */
1196         subdiv_edge = subdiv_create_edges_row(
1197                 ctx,
1198                 subdiv_edge,
1199                 NULL,
1200                 start_vertex_index,
1201                 resolution - 2);
1202         /* Create remaining edges. */
1203         for (int row = 0; row < resolution - 3; row++) {
1204                 const int start_row_vertex_index =
1205                         start_vertex_index + row * (resolution - 2);
1206                 /* Create vertical columns.
1207                  *
1208                  * At first iteration it will be edges (0-3. 1-4, 2-5), then it
1209                  * will be (3-6, 4-7, 5-8) and so on.
1210                  */
1211                 subdiv_edge = subdiv_create_edges_column(
1212                         ctx,
1213                         subdiv_edge,
1214                         NULL,
1215                         NULL,
1216                         start_row_vertex_index,
1217                         resolution - 2);
1218                 /* Create horizontal edge row.
1219                  *
1220                  * At first iteration it will be edges (3-4, 4-5), then it will be
1221                  * (6-7, 7-8) and so on.
1222                  */
1223                 subdiv_edge = subdiv_create_edges_row(
1224                         ctx,
1225                         subdiv_edge,
1226                         NULL,
1227                         start_row_vertex_index + resolution - 2,
1228                         resolution - 2);
1229         }
1230         /* Connect inner part of patch to boundary. */
1231         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1232                 const MLoop *coarse_loop =
1233                         &coarse_mloop[coarse_poly->loopstart + corner];
1234                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1235                 const int start_edge_vertex = ctx->vertices_edge_offset +
1236                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1237                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
1238                 int side_start_index = start_vertex_index;
1239                 int side_stride = 0;
1240                 /* Calculate starting veretx of corresponding inner part of ptex. */
1241                 if (corner == 0) {
1242                         side_stride = 1;
1243                 }
1244                 else if (corner == 1) {
1245                         side_start_index += resolution - 3;
1246                         side_stride = resolution - 2;
1247                 }
1248                 else if (corner == 2) {
1249                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1250                                             num_subdiv_vertices_per_coarse_edge - 1;
1251                         side_stride = -1;
1252                 }
1253                 else if (corner == 3) {
1254                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1255                                             (num_subdiv_vertices_per_coarse_edge - 1);
1256                         side_stride = -(resolution - 2);
1257                 }
1258                 for (int i = 0; i < resolution - 2; i++, subdiv_edge++) {
1259                         subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1260                         if (flip) {
1261                                 subdiv_edge->v1 = start_edge_vertex + (resolution - i - 3);
1262                         }
1263                         else {
1264                                 subdiv_edge->v1 = start_edge_vertex + i;
1265                         }
1266                         subdiv_edge->v2 = side_start_index + side_stride * i;
1267                 }
1268         }
1269 }
1270
1271 static void subdiv_create_edges_all_patches_special(
1272         SubdivMeshContext *ctx,
1273         const MPoly *coarse_poly)
1274 {
1275         const Mesh *coarse_mesh = ctx->coarse_mesh;
1276         const MEdge *coarse_medge = coarse_mesh->medge;
1277         const MLoop *coarse_mloop = coarse_mesh->mloop;
1278         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1279         const int poly_index = coarse_poly - coarse_mpoly;
1280         const int resolution = ctx->settings->resolution;
1281         const int ptex_face_resolution =
1282                 ptex_face_resolution_get(coarse_poly, resolution);
1283         const int ptex_face_inner_resolution = ptex_face_resolution - 2;
1284         const int num_inner_vertices_per_ptex =
1285                 (ptex_face_resolution - 1) * (ptex_face_resolution - 2);
1286         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1287         const int center_vertex_index =
1288                 ctx->vertices_inner_offset +
1289                 ctx->subdiv_vertex_offset[poly_index];
1290         const int start_vertex_index = center_vertex_index + 1;
1291         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1292         MEdge *subdiv_medge = subdiv_mesh->medge;
1293         MEdge *subdiv_edge = &subdiv_medge[
1294                 ctx->edge_inner_offset + ctx->subdiv_edge_offset[poly_index]];
1295         /* Create inner ptex edges. */
1296         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1297                 const int start_ptex_face_vertex_index =
1298                         start_vertex_index + corner * num_inner_vertices_per_ptex;
1299                 /* Similar steps to regular patch case. */
1300                 subdiv_edge = subdiv_create_edges_row(
1301                         ctx,
1302                         subdiv_edge,
1303                         NULL,
1304                         start_ptex_face_vertex_index,
1305                         ptex_face_inner_resolution + 1);
1306                 for (int row = 0; row < ptex_face_inner_resolution - 1; row++) {
1307                         const int start_row_vertex_index =
1308                                 start_ptex_face_vertex_index +
1309                                 row * (ptex_face_inner_resolution + 1);
1310                         subdiv_edge = subdiv_create_edges_column(
1311                                 ctx,
1312                                 subdiv_edge,
1313                                 NULL,
1314                                 NULL,
1315                                 start_row_vertex_index,
1316                                 ptex_face_inner_resolution + 1);
1317                         subdiv_edge = subdiv_create_edges_row(
1318                                 ctx,
1319                                 subdiv_edge,
1320                                 NULL,
1321                                 start_row_vertex_index + ptex_face_inner_resolution + 1,
1322                                 ptex_face_inner_resolution + 1);
1323                 }
1324         }
1325         /* Create connections between ptex faces. */
1326         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1327                 const int next_corner = (corner + 1) % coarse_poly->totloop;
1328                 int current_patch_vertex_index =
1329                         start_vertex_index + corner * num_inner_vertices_per_ptex +
1330                         ptex_face_inner_resolution;
1331                 int next_path_vertex_index =
1332                         start_vertex_index + next_corner * num_inner_vertices_per_ptex +
1333                         num_inner_vertices_per_ptex - ptex_face_resolution + 1;
1334                 for (int row = 0;
1335                      row < ptex_face_inner_resolution;
1336                      row++, subdiv_edge++)
1337                 {
1338                         subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1339                         subdiv_edge->v1 = current_patch_vertex_index;
1340                         subdiv_edge->v2 = next_path_vertex_index;
1341                         current_patch_vertex_index += ptex_face_inner_resolution + 1;
1342                         next_path_vertex_index += 1;
1343                 }
1344         }
1345         /* Create edges from center. */
1346         if (ptex_face_resolution >= 3) {
1347                 for (int corner = 0;
1348                      corner < coarse_poly->totloop;
1349                      corner++, subdiv_edge++)
1350                 {
1351                         const int current_patch_end_vertex_index =
1352                                 start_vertex_index + corner * num_inner_vertices_per_ptex +
1353                                 num_inner_vertices_per_ptex - 1;
1354                         subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1355                         subdiv_edge->v1 = center_vertex_index;
1356                         subdiv_edge->v2 = current_patch_end_vertex_index;
1357                 }
1358         }
1359         /* Connect inner path of patch to boundary. */
1360         const MLoop *prev_coarse_loop =
1361                 &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1362         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1363                 const MLoop *coarse_loop =
1364                         &coarse_mloop[coarse_poly->loopstart + corner];
1365                 {
1366                         const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1367                         const int start_edge_vertex = ctx->vertices_edge_offset +
1368                                 coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1369                         const bool flip = (coarse_edge->v2 == coarse_loop->v);
1370                         int side_start_index;
1371                         if (ptex_face_resolution >= 3) {
1372                                 side_start_index =
1373                                         start_vertex_index + num_inner_vertices_per_ptex * corner;
1374                         }
1375                         else {
1376                                 side_start_index = center_vertex_index;
1377                         }
1378                         for (int i = 0; i < ptex_face_resolution - 1; i++, subdiv_edge++) {
1379                                 subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1380                                 if (flip) {
1381                                         subdiv_edge->v1 = start_edge_vertex + (resolution - i - 3);
1382                                 }
1383                                 else {
1384                                         subdiv_edge->v1 = start_edge_vertex + i;
1385                                 }
1386                                 subdiv_edge->v2 = side_start_index + i;
1387                         }
1388                 }
1389                 if (ptex_face_resolution >= 3) {
1390                         const MEdge *coarse_edge = &coarse_medge[prev_coarse_loop->e];
1391                         const int start_edge_vertex = ctx->vertices_edge_offset +
1392                                 prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1393                         const bool flip = (coarse_edge->v2 == coarse_loop->v);
1394                         int side_start_index =
1395                                 start_vertex_index + num_inner_vertices_per_ptex * corner;
1396                         for (int i = 0; i < ptex_face_resolution - 2; i++, subdiv_edge++) {
1397                                 subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1398                                 if (flip) {
1399                                         subdiv_edge->v1 = start_edge_vertex + (resolution - i - 3);
1400                                 }
1401                                 else {
1402                                         subdiv_edge->v1 = start_edge_vertex + i;
1403                                 }
1404                                 subdiv_edge->v2 = side_start_index +
1405                                                   (ptex_face_inner_resolution + 1) * i;
1406                         }
1407                 }
1408                 prev_coarse_loop = coarse_loop;
1409         }
1410 }
1411
1412 static void subdiv_create_edges_all_patches(
1413         SubdivMeshContext *ctx,
1414         const MPoly *coarse_poly)
1415 {
1416         if (coarse_poly->totloop == 4) {
1417                 subdiv_create_edges_all_patches_regular(ctx, coarse_poly);
1418         }
1419         else {
1420                 subdiv_create_edges_all_patches_special(ctx, coarse_poly);
1421         }
1422 }
1423
1424 static void subdiv_create_edges(SubdivMeshContext *ctx, int poly_index)
1425 {
1426         const Mesh *coarse_mesh = ctx->coarse_mesh;
1427         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1428         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1429         subdiv_create_edges_all_patches(ctx, coarse_poly);
1430 }
1431
1432 static void subdiv_create_boundary_edges(
1433         SubdivMeshContext *ctx,
1434         int edge_index)
1435 {
1436         const Mesh *coarse_mesh = ctx->coarse_mesh;
1437         const MEdge *coarse_medge = coarse_mesh->medge;
1438         const MEdge *coarse_edge = &coarse_medge[edge_index];
1439         const int resolution = ctx->settings->resolution;
1440         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1441         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1442         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1443         MEdge *subdiv_medge = subdiv_mesh->medge;
1444         MEdge *subdiv_edge = &subdiv_medge[
1445                 ctx->edge_boundary_offset +
1446                 edge_index * num_subdiv_edges_per_coarse_edge];
1447         int last_vertex_index = ctx->vertices_corner_offset + coarse_edge->v1;
1448         for (int i = 0;
1449              i < num_subdiv_edges_per_coarse_edge - 1;
1450              i++, subdiv_edge++)
1451         {
1452                 subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1453                 subdiv_edge->v1 = last_vertex_index;
1454                 subdiv_edge->v2 =
1455                         ctx->vertices_edge_offset +
1456                         edge_index * num_subdiv_vertices_per_coarse_edge +
1457                         i;
1458                 last_vertex_index = subdiv_edge->v2;
1459         }
1460         subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1461         subdiv_edge->v1 = last_vertex_index;
1462         subdiv_edge->v2 = ctx->vertices_corner_offset + coarse_edge->v2;
1463 }
1464
1465 /* =============================================================================
1466  * Loops creation/interpolation.
1467  */
1468
1469 static void subdiv_copy_loop_data(
1470         const SubdivMeshContext *ctx,
1471         MLoop *subdiv_loop,
1472         const LoopsForInterpolation *loop_interpolation,
1473         const float u, const float v)
1474 {
1475         const int subdiv_loop_index = subdiv_loop - ctx->subdiv_mesh->mloop;
1476         const float weights[4] = {(1.0f - u) * (1.0f - v),
1477                                   u * (1.0f - v),
1478                                   u * v,
1479                                   (1.0f - u) * v};
1480         CustomData_interp(loop_interpolation->loop_data,
1481                           &ctx->subdiv_mesh->ldata,
1482                           loop_interpolation->loop_indices,
1483                           weights, NULL,
1484                           4,
1485                           subdiv_loop_index);
1486         /* TODO(sergey): Set ORIGINDEX. */
1487 }
1488
1489 static void subdiv_eval_uv_layer(SubdivMeshContext *ctx,
1490                                  MLoop *subdiv_loop,
1491                                  const int ptex_face_index,
1492                                  const float u, const float v,
1493                                  const float du, const float dv)
1494 {
1495         if (ctx->num_uv_layers == 0) {
1496                 return;
1497         }
1498         Subdiv *subdiv = ctx->subdiv;
1499         const int mloop_index = subdiv_loop - ctx->subdiv_mesh->mloop;
1500         for (int layer_index = 0; layer_index < ctx->num_uv_layers; layer_index++) {
1501                 MLoopUV *subdiv_loopuv = &ctx->uv_layers[layer_index][mloop_index];
1502                 BKE_subdiv_eval_face_varying(subdiv,
1503                                              ptex_face_index,
1504                                              u, v,
1505                                              subdiv_loopuv[0].uv);
1506                 BKE_subdiv_eval_face_varying(subdiv,
1507                                              ptex_face_index,
1508                                              u + du, v,
1509                                              subdiv_loopuv[1].uv);
1510                 BKE_subdiv_eval_face_varying(subdiv,
1511                                              ptex_face_index,
1512                                              u + du, v + dv,
1513                                              subdiv_loopuv[2].uv);
1514                 BKE_subdiv_eval_face_varying(subdiv,
1515                                              ptex_face_index,
1516                                              u, v + dv,
1517                                              subdiv_loopuv[3].uv);
1518                 /* TODO(sergey): Currently evaluator only has single UV layer, so can
1519                  * not evaluate more than that. Need to be solved.
1520                  */
1521                 break;
1522         }
1523 }
1524
1525 static void rotate_indices(const int rot, int *a, int *b, int *c, int *d)
1526 {
1527         int values[4] = {*a, *b, *c, *d};
1528         *a = values[(0 - rot + 4) % 4];
1529         *b = values[(1 - rot + 4) % 4];
1530         *c = values[(2 - rot + 4) % 4];
1531         *d = values[(3 - rot + 4) % 4];
1532 }
1533
1534 static void subdiv_create_loops_of_poly(
1535         SubdivMeshContext *ctx,
1536         LoopsForInterpolation *loop_interpolation,
1537         MLoop *subdiv_loop_start,
1538         const int ptex_face_index,
1539         const int rotation,
1540         /*const*/ int v0, /*const*/ int e0,
1541         /*const*/ int v1, /*const*/ int e1,
1542         /*const*/ int v2, /*const*/ int e2,
1543         /*const*/ int v3, /*const*/ int e3,
1544         const float u, const float v,
1545         const float du, const float dv)
1546 {
1547         rotate_indices(rotation, &v0, &v1, &v2, &v3);
1548         rotate_indices(rotation, &e0, &e1, &e2, &e3);
1549         subdiv_copy_loop_data(ctx,
1550                               &subdiv_loop_start[0],
1551                               loop_interpolation,
1552                               u, v);
1553         subdiv_loop_start[0].v = v0;
1554         subdiv_loop_start[0].e = e0;
1555         subdiv_copy_loop_data(ctx,
1556                               &subdiv_loop_start[1],
1557                               loop_interpolation,
1558                               u + du, v);
1559         subdiv_loop_start[1].v = v1;
1560         subdiv_loop_start[1].e = e1;
1561         subdiv_copy_loop_data(ctx,
1562                               &subdiv_loop_start[2],
1563                               loop_interpolation,
1564                               u + du, v + dv);
1565         subdiv_loop_start[2].v = v2;
1566         subdiv_loop_start[2].e = e2;
1567         subdiv_copy_loop_data(ctx,
1568                               &subdiv_loop_start[3],
1569                               loop_interpolation,
1570                               u, v + dv);
1571         subdiv_loop_start[3].v = v3;
1572         subdiv_loop_start[3].e = e3;
1573         /* Interpolate UV layers using OpenSubdiv. */
1574         subdiv_eval_uv_layer(ctx,
1575                              subdiv_loop_start,
1576                              ptex_face_index,
1577                              u, v, du, dv);
1578 }
1579
1580 static void subdiv_create_loops_regular(SubdivMeshContext *ctx,
1581                                         const MPoly *coarse_poly)
1582 {
1583         const int resolution = ctx->settings->resolution;
1584         /* Base/coarse mesh information. */
1585         const Mesh *coarse_mesh = ctx->coarse_mesh;
1586         const MEdge *coarse_medge = coarse_mesh->medge;
1587         const MLoop *coarse_mloop = coarse_mesh->mloop;
1588         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1589         const int poly_index = coarse_poly - coarse_mpoly;
1590         const int ptex_resolution =
1591                 ptex_face_resolution_get(coarse_poly, resolution);
1592         const int ptex_inner_resolution = ptex_resolution - 2;
1593         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1594         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1595         const float inv_ptex_resolution_1 = 1.0f / (float)(ptex_resolution - 1);
1596         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
1597         const int start_vertex_index =
1598                 ctx->vertices_inner_offset +
1599                 ctx->subdiv_vertex_offset[poly_index];
1600         const int start_edge_index =
1601                 ctx->edge_inner_offset +
1602                 ctx->subdiv_edge_offset[poly_index];
1603         const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
1604         const int start_loop_index = 4 * start_poly_index;
1605         const float du = inv_ptex_resolution_1;
1606         const float dv = inv_ptex_resolution_1;
1607         /* Hi-poly subdivided mesh. */
1608         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1609         MLoop *subdiv_loopoop = subdiv_mesh->mloop;
1610         MLoop *subdiv_loop = &subdiv_loopoop[start_loop_index];
1611         LoopsForInterpolation loop_interpolation;
1612         loop_interpolation_init(ctx, &loop_interpolation, coarse_poly);
1613         loop_interpolation_from_ptex(ctx,
1614                                      &loop_interpolation,
1615                                      coarse_poly,
1616                                      0);
1617         /* Loops for inner part of ptex. */
1618         for (int y = 1; y < ptex_resolution - 2; y++) {
1619                 const float v = y * inv_ptex_resolution_1;
1620                 const int inner_y = y - 1;
1621                 for (int x = 1; x < ptex_resolution - 2; x++, subdiv_loop += 4) {
1622                         const int inner_x = x - 1;
1623                         const float u = x * inv_ptex_resolution_1;
1624                         /* Vertex indicies ordered counter-clockwise. */
1625                         const int v0 = start_vertex_index +
1626                                        (inner_y * ptex_inner_resolution + inner_x);
1627                         const int v1 = v0 + 1;
1628                         const int v2 = v0 + ptex_inner_resolution + 1;
1629                         const int v3 = v0 + ptex_inner_resolution;
1630                         /* Edge indicies ordered counter-clockwise. */
1631                         const int e0 = start_edge_index +
1632                                 (inner_y * (2 * ptex_inner_resolution - 1) + inner_x);
1633                         const int e1 = e0 + ptex_inner_resolution;
1634                         const int e2 = e0 + (2 * ptex_inner_resolution - 1);
1635                         const int e3 = e0 + ptex_inner_resolution - 1;
1636                         subdiv_create_loops_of_poly(
1637                                 ctx, &loop_interpolation, subdiv_loop, ptex_face_index, 0,
1638                                 v0, e0, v1, e1, v2, e2, v3, e3,
1639                                 u, v, du, dv);
1640                 }
1641         }
1642         /* Loops for faces connecting inner ptex part with boundary. */
1643         const MLoop *prev_coarse_loop =
1644                 &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1645         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1646                 const MLoop *coarse_loop =
1647                         &coarse_mloop[coarse_poly->loopstart + corner];
1648                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1649                 const MEdge *prev_coarse_edge = &coarse_medge[prev_coarse_loop->e];
1650                 const int start_edge_vertex = ctx->vertices_edge_offset +
1651                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1652                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
1653                 int side_start_index = start_vertex_index;
1654                 int side_stride = 0;
1655                 int v0 = ctx->vertices_corner_offset + coarse_loop->v;
1656                 int v3, e3;
1657                 int e2_offset, e2_stride;
1658                 float u, v, delta_u, delta_v;
1659                 if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1660                         v3 = ctx->vertices_edge_offset +
1661                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1662                         num_subdiv_vertices_per_coarse_edge - 1;
1663                         e3 = ctx->edge_boundary_offset +
1664                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1665                                  num_subdiv_edges_per_coarse_edge - 1;
1666                 }
1667                 else {
1668                         v3 = ctx->vertices_edge_offset +
1669                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1670                         e3 = ctx->edge_boundary_offset +
1671                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge;
1672                 }
1673                 /* Calculate starting veretx of corresponding inner part of ptex. */
1674                 if (corner == 0) {
1675                         side_stride = 1;
1676                         e2_offset = 0;
1677                         e2_stride = 1;
1678                         u = 0.0f;
1679                         v = 0.0f;
1680                         delta_u = du;
1681                         delta_v = 0.0f;
1682                 }
1683                 else if (corner == 1) {
1684                         side_start_index += resolution - 3;
1685                         side_stride = resolution - 2;
1686                         e2_offset = 2 * num_subdiv_edges_per_coarse_edge - 4;
1687                         e2_stride = 2 * num_subdiv_edges_per_coarse_edge - 3;
1688                         u = 1.0f - du;
1689                         v = 0;
1690                         delta_u = 0.0f;
1691                         delta_v = dv;
1692                 }
1693                 else if (corner == 2) {
1694                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1695                                             num_subdiv_vertices_per_coarse_edge - 1;
1696                         side_stride = -1;
1697                         e2_offset = num_edges_per_ptex_face_get(resolution - 2) - 1;
1698                         e2_stride = -1;
1699                         u = 1.0f - du;
1700                         v = 1.0f - dv;
1701                         delta_u = -du;
1702                         delta_v = 0.0f;
1703                 }
1704                 else if (corner == 3) {
1705                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1706                                             (num_subdiv_vertices_per_coarse_edge - 1);
1707                         side_stride = -(resolution - 2);
1708                         e2_offset = num_edges_per_ptex_face_get(resolution - 2) -
1709                                     (2 * num_subdiv_edges_per_coarse_edge - 3);
1710                         e2_stride = -(2 * num_subdiv_edges_per_coarse_edge - 3);
1711                         u = 0.0f;
1712                         v = 1.0f - dv;
1713                         delta_u = 0.0f;
1714                         delta_v = -dv;
1715                 }
1716                 for (int i = 0; i < resolution - 2; i++, subdiv_loop += 4) {
1717                         int v1;
1718                         if (flip) {
1719                                 v1 = start_edge_vertex + (resolution - i - 3);
1720                         }
1721                         else {
1722                                 v1 = start_edge_vertex + i;
1723                         }
1724                         const int v2 = side_start_index + side_stride * i;
1725                         int e0;
1726                         if (flip) {
1727                                 e0 = ctx->edge_boundary_offset +
1728                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1729                                          num_subdiv_edges_per_coarse_edge - i - 1;
1730                         }
1731                         else {
1732                                 e0 = ctx->edge_boundary_offset +
1733                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1734                                          i;
1735                         }
1736                         int e1 = start_edge_index +
1737                                 num_edges_per_ptex_face_get(resolution - 2) +
1738                                 corner * num_subdiv_vertices_per_coarse_edge +
1739                                 i;
1740                         int e2;
1741                         if (i == 0) {
1742                                 e2 = start_edge_index +
1743                                         num_edges_per_ptex_face_get(resolution - 2) +
1744                                         ((corner - 1 + coarse_poly->totloop) %
1745                                                 coarse_poly->totloop) *
1746                                                         num_subdiv_vertices_per_coarse_edge +
1747                                         num_subdiv_vertices_per_coarse_edge - 1;
1748                         }
1749                         else {
1750                                 e2 = start_edge_index + e2_offset + e2_stride * (i - 1);
1751                         }
1752                         subdiv_create_loops_of_poly(
1753                                 ctx, &loop_interpolation, subdiv_loop,
1754                                 ptex_face_index, corner,
1755                                 v0, e0, v1, e1, v2, e2, v3, e3,
1756                                 u + delta_u * i, v + delta_v * i, du, dv);
1757                         v0 = v1;
1758                         v3 = v2;
1759                         e3 = e1;
1760                 }
1761                 prev_coarse_loop = coarse_loop;
1762         }
1763         loop_interpolation_end(&loop_interpolation);
1764 }
1765
1766 static void subdiv_create_loops_special(SubdivMeshContext *ctx,
1767                                         const MPoly *coarse_poly)
1768 {
1769         const int resolution = ctx->settings->resolution;
1770         /* Base/coarse mesh information. */
1771         const Mesh *coarse_mesh = ctx->coarse_mesh;
1772         const MEdge *coarse_medge = coarse_mesh->medge;
1773         const MLoop *coarse_mloop = coarse_mesh->mloop;
1774         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1775         const int poly_index = coarse_poly - coarse_mpoly;
1776         const int ptex_face_resolution =
1777                 ptex_face_resolution_get(coarse_poly, resolution);
1778         const int ptex_face_inner_resolution = ptex_face_resolution - 2;
1779         const float inv_ptex_resolution_1 =
1780                1.0f / (float)(ptex_face_resolution - 1);
1781         const int num_inner_vertices_per_ptex =
1782                 (ptex_face_resolution - 1) * (ptex_face_resolution - 2);
1783         const int num_inner_edges_per_ptex_face =
1784                 num_inner_edges_per_ptex_face_get(
1785                         ptex_face_inner_resolution + 1);
1786         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1787         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1788         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
1789         const int center_vertex_index =
1790                 ctx->vertices_inner_offset +
1791                 ctx->subdiv_vertex_offset[poly_index];
1792         const int start_vertex_index = center_vertex_index + 1;
1793         const int start_inner_vertex_index = center_vertex_index + 1;
1794         const int start_edge_index = ctx->edge_inner_offset +
1795                                      ctx->subdiv_edge_offset[poly_index];
1796         const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
1797         const int start_loop_index = 4 * start_poly_index;
1798         const float du = inv_ptex_resolution_1;
1799         const float dv = inv_ptex_resolution_1;
1800         /* Hi-poly subdivided mesh. */
1801         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1802         MLoop *subdiv_loopoop = subdiv_mesh->mloop;
1803         MLoop *subdiv_loop = &subdiv_loopoop[start_loop_index];
1804         LoopsForInterpolation loop_interpolation;
1805         loop_interpolation_init(ctx, &loop_interpolation, coarse_poly);
1806         for (int corner = 0;
1807              corner < coarse_poly->totloop;
1808              corner++)
1809         {
1810                 const int corner_vertex_index =
1811                         start_vertex_index + corner * num_inner_vertices_per_ptex;
1812                 const int corner_edge_index =
1813                         start_edge_index + corner * num_inner_edges_per_ptex_face;
1814                 loop_interpolation_from_ptex(ctx,
1815                                              &loop_interpolation,
1816                                              coarse_poly,
1817                                              corner);
1818                 for (int y = 1; y < ptex_face_inner_resolution; y++) {
1819                         const float v = y * inv_ptex_resolution_1;
1820                         const int inner_y = y - 1;
1821                         for (int x = 1;
1822                              x < ptex_face_inner_resolution + 1;
1823                              x++, subdiv_loop += 4)
1824                         {
1825                                 const int inner_x = x - 1;
1826                                 const float u = x * inv_ptex_resolution_1;
1827                                 /* Vertex indicies ordered counter-clockwise. */
1828                                 const int v0 =
1829                                         corner_vertex_index +
1830                                         (inner_y * (ptex_face_inner_resolution + 1) + inner_x);
1831                                 const int v1 = v0 + 1;
1832                                 const int v2 = v0 + ptex_face_inner_resolution + 2;
1833                                 const int v3 = v0 + ptex_face_inner_resolution + 1;
1834                                 /* Edge indicies ordered counter-clockwise. */
1835                                 const int e0 = corner_edge_index +
1836                                           (inner_y * (2 * ptex_face_inner_resolution + 1) + inner_x);
1837                                 const int e1 = e0 + ptex_face_inner_resolution + 1;
1838                                 const int e2 = e0 + (2 * ptex_face_inner_resolution + 1);
1839                                 const int e3 = e0 + ptex_face_inner_resolution;
1840                                 subdiv_create_loops_of_poly(
1841                                         ctx, &loop_interpolation, subdiv_loop,
1842                                         ptex_face_index + corner, 0,
1843                                         v0, e0, v1, e1, v2, e2, v3, e3,
1844                                         u, v, du, dv);
1845                         }
1846                 }
1847         }
1848         /* Create connections between ptex faces. */
1849         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1850                 const int next_corner = (corner + 1) % coarse_poly->totloop;
1851                 const int corner_edge_index =
1852                         start_edge_index + corner * num_inner_edges_per_ptex_face;
1853                 const int next_corner_edge_index =
1854                         start_edge_index + next_corner * num_inner_edges_per_ptex_face;
1855                 int current_patch_vertex_index =
1856                         start_inner_vertex_index +
1857                         corner * num_inner_vertices_per_ptex +
1858                         ptex_face_inner_resolution;
1859                 int next_path_vertex_index =
1860                         start_inner_vertex_index +
1861                         next_corner * num_inner_vertices_per_ptex +
1862                         num_inner_vertices_per_ptex - ptex_face_resolution + 1;
1863                 int v0 = current_patch_vertex_index;
1864                 int v1 = next_path_vertex_index;
1865                 current_patch_vertex_index += ptex_face_inner_resolution + 1;
1866                 next_path_vertex_index += 1;
1867                 int e0 = start_edge_index +
1868                          coarse_poly->totloop * num_inner_edges_per_ptex_face +
1869                          corner * (ptex_face_resolution - 2);
1870                 int e1 = next_corner_edge_index + num_inner_edges_per_ptex_face -
1871                          ptex_face_resolution + 2;
1872                 int e3 = corner_edge_index + 2 * ptex_face_resolution - 4;
1873                 loop_interpolation_from_ptex(ctx,
1874                                              &loop_interpolation,
1875                                              coarse_poly,
1876                                              next_corner);
1877                 for (int row = 1;
1878                      row < ptex_face_inner_resolution;
1879                      row++, subdiv_loop += 4)
1880                 {
1881                         const int v2 = next_path_vertex_index;
1882                         const int v3 = current_patch_vertex_index;
1883                         const int e2 = e0 + 1;
1884                         const float u = row * du;
1885                         const float v = 1.0f - dv;
1886                         subdiv_create_loops_of_poly(
1887                                 ctx, &loop_interpolation, subdiv_loop,
1888                                 ptex_face_index + next_corner, 3,
1889                                 v0, e0, v1, e1, v2, e2, v3, e3,
1890                                 u, v, du, dv);
1891                         current_patch_vertex_index += ptex_face_inner_resolution + 1;
1892                         next_path_vertex_index += 1;
1893                         v0 = v3;
1894                         v1 = v2;
1895                         e0 = e2;
1896                         e1 += 1;
1897                         e3 += 2 * ptex_face_resolution - 3;
1898                 }
1899         }
1900         /* Create loops from center. */
1901         if (ptex_face_resolution >= 3) {
1902                 const int start_center_edge_index =
1903                         start_edge_index +
1904                         (num_inner_edges_per_ptex_face +
1905                          ptex_face_inner_resolution) * coarse_poly->totloop;
1906                 const int start_boundary_edge =
1907                         start_edge_index +
1908                         coarse_poly->totloop * num_inner_edges_per_ptex_face +
1909                         ptex_face_inner_resolution - 1;
1910                 for (int corner = 0, prev_corner = coarse_poly->totloop - 1;
1911                      corner < coarse_poly->totloop;
1912                      prev_corner = corner, corner++, subdiv_loop += 4)
1913                 {
1914                         loop_interpolation_from_ptex(ctx,
1915                                                      &loop_interpolation,
1916                                                      coarse_poly,
1917                                                      corner);
1918                         const int corner_edge_index =
1919                                 start_edge_index +
1920                                 corner * num_inner_edges_per_ptex_face;
1921                         const int current_patch_end_vertex_index =
1922                                 start_vertex_index + corner * num_inner_vertices_per_ptex +
1923                                 num_inner_vertices_per_ptex - 1;
1924                         const int prev_current_patch_end_vertex_index =
1925                                 start_vertex_index + prev_corner *
1926                                         num_inner_vertices_per_ptex +
1927                                 num_inner_vertices_per_ptex - 1;
1928                         const int v0 = center_vertex_index;
1929                         const int v1 = prev_current_patch_end_vertex_index;
1930                         const int v2 = current_patch_end_vertex_index - 1;
1931                         const int v3 = current_patch_end_vertex_index;
1932                         const int e0 = start_center_edge_index + prev_corner;
1933                         const int e1 = start_boundary_edge +
1934                                        prev_corner * (ptex_face_inner_resolution);
1935                         const int e2 = corner_edge_index +
1936                                        num_inner_edges_per_ptex_face - 1;
1937                         const int e3 = start_center_edge_index + corner;
1938                         const float u = 1.0f - du;
1939                         const float v = 1.0f - dv;
1940                         subdiv_create_loops_of_poly(
1941                                 ctx, &loop_interpolation, subdiv_loop,
1942                                 ptex_face_index + corner, 2,
1943                                 v0, e0, v1, e1, v2, e2, v3, e3,
1944                                 u, v, du, dv);
1945                 }
1946         }
1947         /* Loops for faces connecting inner ptex part with boundary. */
1948         const MLoop *prev_coarse_loop =
1949                 &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1950         for (int prev_corner = coarse_poly->totloop - 1, corner = 0;
1951              corner < coarse_poly->totloop;
1952              prev_corner = corner, corner++)
1953         {
1954                 loop_interpolation_from_ptex(ctx,
1955                                              &loop_interpolation,
1956                                              coarse_poly,
1957                                              corner);
1958                 const MLoop *coarse_loop =
1959                         &coarse_mloop[coarse_poly->loopstart + corner];
1960                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1961                 const MEdge *prev_coarse_edge = &coarse_medge[prev_coarse_loop->e];
1962                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
1963                 const int start_edge_vertex = ctx->vertices_edge_offset +
1964                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1965                 const int corner_vertex_index =
1966                         start_vertex_index + corner * num_inner_vertices_per_ptex;
1967                 const int corner_edge_index =
1968                         start_edge_index + corner * num_inner_edges_per_ptex_face;
1969                 /* Create loops for polygons along U axis. */
1970                 int v0 = ctx->vertices_corner_offset + coarse_loop->v;
1971                 int v3, e3;
1972                 if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1973                         v3 = ctx->vertices_edge_offset +
1974                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1975                         num_subdiv_vertices_per_coarse_edge - 1;
1976                         e3 = ctx->edge_boundary_offset +
1977                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1978                                  num_subdiv_edges_per_coarse_edge - 1;
1979                 }
1980                 else {
1981                         v3 = ctx->vertices_edge_offset +
1982                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1983                         e3 = ctx->edge_boundary_offset +
1984                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge;
1985                 }
1986                 for (int i = 0;
1987                      i <= ptex_face_inner_resolution;
1988                      i++, subdiv_loop += 4)
1989                 {
1990                         int v1;
1991                         if (flip) {
1992                                 v1 = start_edge_vertex + (resolution - i - 3);
1993                         }
1994                         else {
1995                                 v1 = start_edge_vertex + i;
1996                         }
1997                         int v2;
1998                         if (ptex_face_inner_resolution >= 1) {
1999                                 v2 = corner_vertex_index + i;
2000                         }
2001                         else {
2002                                 v2 = center_vertex_index;
2003                         }
2004                         int e0;
2005                         if (flip) {
2006                                 e0 = ctx->edge_boundary_offset +
2007                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
2008                                          num_subdiv_edges_per_coarse_edge - i - 1;
2009                         }
2010                         else {
2011                                 e0 = ctx->edge_boundary_offset +
2012                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
2013                                          i;
2014                         }
2015                         int e1 = start_edge_index +
2016                                  corner * (2 * ptex_face_inner_resolution + 1);
2017                         if (ptex_face_resolution >= 3) {
2018                                 e1 += coarse_poly->totloop * (num_inner_edges_per_ptex_face +
2019                                                               ptex_face_inner_resolution + 1) +
2020                                       i;
2021                         }
2022                         int e2 = 0;
2023                         if (i == 0 && ptex_face_resolution >= 3) {
2024                                 e2 = start_edge_index +
2025                                          coarse_poly->totloop *
2026                                                  (num_inner_edges_per_ptex_face +
2027                                                   ptex_face_inner_resolution + 1) +
2028                                          corner * (2 * ptex_face_inner_resolution + 1) +
2029                                          ptex_face_inner_resolution + 1;
2030                         }
2031                         else if (i == 0 && ptex_face_resolution < 3) {
2032                                 e2 = start_edge_index +
2033                                  prev_corner * (2 * ptex_face_inner_resolution + 1);
2034                         }
2035                         else {
2036                                 e2 = corner_edge_index + i - 1;
2037                         }
2038                         const float u = du * i;
2039                         const float v = 0.0f;
2040                         subdiv_create_loops_of_poly(
2041                                 ctx, &loop_interpolation, subdiv_loop,
2042                                 ptex_face_index + corner, 0,
2043                                 v0, e0, v1, e1, v2, e2, v3, e3,
2044                                 u, v, du, dv);
2045                         v0 = v1;
2046                         v3 = v2;
2047                         e3 = e1;
2048                 }
2049                 /* Create loops for polygons along V axis. */
2050                 const bool flip_prev = (prev_coarse_edge->v2 == coarse_loop->v);
2051                 v0 = corner_vertex_index;
2052                 if (prev_coarse_loop->v == prev_coarse_edge->v1) {
2053                         v3 = ctx->vertices_edge_offset +
2054                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
2055                         num_subdiv_vertices_per_coarse_edge - 1;
2056                 }
2057                 else {
2058                         v3 = ctx->vertices_edge_offset +
2059                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
2060                 }
2061                 e3 = start_edge_index +
2062                          coarse_poly->totloop *
2063                                  (num_inner_edges_per_ptex_face +
2064                                   ptex_face_inner_resolution + 1) +
2065                          corner * (2 * ptex_face_inner_resolution + 1) +
2066                          ptex_face_inner_resolution + 1;
2067                 for (int i = 0;
2068                      i <= ptex_face_inner_resolution - 1;
2069                      i++, subdiv_loop += 4)
2070                 {
2071                         int v1;
2072                         int e0, e1;
2073                         if (i == ptex_face_inner_resolution - 1) {
2074                                 v1 = start_vertex_index +
2075                                      prev_corner * num_inner_vertices_per_ptex +
2076                                      ptex_face_inner_resolution;
2077                                 e1 = start_edge_index +
2078                                          coarse_poly->totloop *
2079                                                  (num_inner_edges_per_ptex_face +
2080                                                   ptex_face_inner_resolution + 1) +
2081                                          prev_corner * (2 * ptex_face_inner_resolution + 1) +
2082                                          ptex_face_inner_resolution;
2083                                 e0 = start_edge_index +
2084                                       coarse_poly->totloop * num_inner_edges_per_ptex_face +
2085                                       prev_corner * ptex_face_inner_resolution;
2086                         }
2087                         else {
2088                                 v1 = v0 + ptex_face_inner_resolution + 1;
2089                                 e0 = corner_edge_index + ptex_face_inner_resolution +
2090                                          i * (2 * ptex_face_inner_resolution + 1);
2091                                 e1 = e3 + 1;
2092                         }
2093                         int v2 = flip_prev ? v3 - 1 : v3 + 1;
2094                         int e2;
2095                         if (flip_prev) {
2096                                 e2 = ctx->edge_boundary_offset +
2097                                          prev_coarse_loop->e *
2098                                                  num_subdiv_edges_per_coarse_edge +
2099                                          num_subdiv_edges_per_coarse_edge - 2 - i;
2100                         }
2101                         else {
2102                                 e2 = ctx->edge_boundary_offset +
2103                                          prev_coarse_loop->e *
2104                                                  num_subdiv_edges_per_coarse_edge + 1 + i;
2105                         }
2106                         const float u = 0.0f;
2107                         const float v = du * (i + 1);
2108                         subdiv_create_loops_of_poly(
2109                                 ctx, &loop_interpolation, subdiv_loop,
2110                                 ptex_face_index + corner, 1,
2111                                 v0, e0, v1, e1, v2, e2, v3, e3,
2112                                 u, v, du, dv);
2113                         v0 = v1;
2114                         v3 = v2;
2115                         e3 = e1;
2116                 }
2117                 prev_coarse_loop = coarse_loop;
2118         }
2119         loop_interpolation_end(&loop_interpolation);
2120 }
2121
2122 static void subdiv_create_loops(SubdivMeshContext *ctx, int poly_index)
2123 {
2124         const Mesh *coarse_mesh = ctx->coarse_mesh;
2125         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
2126         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
2127         if (coarse_poly->totloop == 4) {
2128                 subdiv_create_loops_regular(ctx, coarse_poly);
2129         }
2130         else {
2131                 subdiv_create_loops_special(ctx, coarse_poly);
2132         }
2133 }
2134
2135 /* =============================================================================
2136  * Polygons subdivision process.
2137  */
2138
2139 static void subdiv_copy_poly_data(const SubdivMeshContext *ctx,
2140                                   MPoly *subdiv_poly,
2141                                   const MPoly *coarse_poly)
2142 {
2143         const int coarse_poly_index = coarse_poly - ctx->coarse_mesh->mpoly;
2144         const int subdiv_poly_index = subdiv_poly - ctx->subdiv_mesh->mpoly;
2145         CustomData_copy_data(&ctx->coarse_mesh->pdata,
2146                              &ctx->subdiv_mesh->pdata,
2147                              coarse_poly_index,
2148                              subdiv_poly_index,
2149                              1);
2150 }
2151
2152 static void subdiv_create_polys(SubdivMeshContext *ctx, int poly_index)
2153 {
2154         const int resolution = ctx->settings->resolution;
2155         const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
2156         /* Base/coarse mesh information. */
2157         const Mesh *coarse_mesh = ctx->coarse_mesh;
2158         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
2159         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
2160         const int num_ptex_faces_per_poly =
2161                 num_ptex_faces_per_poly_get(coarse_poly);
2162         const int ptex_resolution =
2163                 ptex_face_resolution_get(coarse_poly, resolution);
2164         const int num_polys_per_ptex = num_polys_per_ptex_get(ptex_resolution);
2165         const int num_loops_per_ptex = 4 * num_polys_per_ptex;
2166         const int start_loop_index = 4 * start_poly_index;
2167         /* Hi-poly subdivided mesh. */
2168         Mesh *subdiv_mesh = ctx->subdiv_mesh;
2169         MPoly *subdiv_mpoly = subdiv_mesh->mpoly;
2170         MPoly *subdiv_mp = &subdiv_mpoly[start_poly_index];
2171         for (int ptex_of_poly_index = 0;
2172              ptex_of_poly_index < num_ptex_faces_per_poly;
2173              ptex_of_poly_index++)
2174         {
2175                 for (int subdiv_poly_index = 0;
2176                      subdiv_poly_index < num_polys_per_ptex;
2177                      subdiv_poly_index++, subdiv_mp++)
2178                 {
2179                         subdiv_copy_poly_data(ctx, subdiv_mp, coarse_poly);
2180                         subdiv_mp->loopstart = start_loop_index +
2181                                                (ptex_of_poly_index * num_loops_per_ptex) +
2182                                                (subdiv_poly_index * 4);
2183                         subdiv_mp->totloop = 4;
2184                 }
2185         }
2186 }
2187
2188 /* =============================================================================
2189  * Subdivision process entry points.
2190  */
2191
2192 static void subdiv_eval_task(
2193         void *__restrict userdata,
2194         const int poly_index,
2195         const ParallelRangeTLS *__restrict UNUSED(tls))
2196 {
2197         SubdivMeshContext *ctx = userdata;
2198         /* Evaluate hi-poly vertex coordinates and normals. */
2199         subdiv_evaluate_vertices(ctx, poly_index);
2200         /* Create mesh geometry for the given base poly index. */
2201         subdiv_create_edges(ctx, poly_index);
2202         subdiv_create_loops(ctx, poly_index);
2203         subdiv_create_polys(ctx, poly_index);
2204 }
2205
2206 static void subdiv_create_boundary_edges_task(
2207         void *__restrict userdata,
2208         const int edge_index,
2209         const ParallelRangeTLS *__restrict UNUSED(tls))
2210 {
2211         SubdivMeshContext *ctx = userdata;
2212         subdiv_create_boundary_edges(ctx, edge_index);
2213 }
2214
2215 Mesh *BKE_subdiv_to_mesh(
2216         Subdiv *subdiv,
2217         const SubdivToMeshSettings *settings,
2218         const Mesh *coarse_mesh)
2219 {
2220         BKE_subdiv_stats_begin(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
2221         /* Make sure evaluator is up to date with possible new topology, and that
2222          * is is refined for the new positions of coarse vertices.
2223          */
2224         BKE_subdiv_eval_update_from_mesh(subdiv, coarse_mesh);
2225         SubdivMeshContext ctx = {0};
2226         ctx.coarse_mesh = coarse_mesh;
2227         ctx.subdiv = subdiv;
2228         ctx.settings = settings;
2229         subdiv_mesh_ctx_init(&ctx);
2230         Mesh *result = BKE_mesh_new_nomain_from_template(
2231                 coarse_mesh,
2232                 ctx.num_subdiv_vertices,
2233                 ctx.num_subdiv_edges,
2234                 0,
2235                 ctx.num_subdiv_loops,
2236                 ctx.num_subdiv_polygons);
2237         ctx.subdiv_mesh = result;
2238         subdiv_mesh_ctx_init_result(&ctx);
2239         /* Multi-threaded evaluation. */
2240         ParallelRangeSettings parallel_range_settings;
2241         BKE_subdiv_stats_begin(&subdiv->stats,
2242                                SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY);
2243         BLI_parallel_range_settings_defaults(&parallel_range_settings);
2244         BLI_task_parallel_range(0, coarse_mesh->totpoly,
2245                                 &ctx,
2246                                 subdiv_eval_task,
2247                                 &parallel_range_settings);
2248         BLI_task_parallel_range(0, coarse_mesh->totedge,
2249                                 &ctx,
2250                                 subdiv_create_boundary_edges_task,
2251                                 &parallel_range_settings);
2252         subdiv_mesh_ctx_free(&ctx);
2253         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY);
2254         // BKE_mesh_validate(result, true, true);
2255         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
2256         return result;
2257 }