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